6.3. ДВОИЧНЫЕ СВЕРТОЧНЫЕ КОДЫ

Вычисления, проведенные в предыдущем разделе, доказали возможность выбора такой схемы приема с квантованием, у которой Вв — показатель экспоненты достижимой вероятности ошибки — лишь не намного меньше показателя экспоненты достижимой вероятности ошибки для приемника без квантования. При этом предполагалось, что за квантующим устройством следует оптимальный декодер, т. е. вычислительное устройство, определяющее, для какого из сообщений апостериорная вероятность максимальна; вектор на выходе квантующего устройства.

Для равновероятных сообщений апостериорная вероятность пропорциональна Однако ранее мы видели, что для больших К и, следовательно, очень больших значений практически невозможно вычислить для каждого Проблема декодирования состоит в том, как избежать экспоненциального увеличения сложности декодера при возрастании К. При этом приходится идти на дополнительное ухудшение экспоненты вероятности ошибки, которое является следствием неоптимальности метода обработки данных в блоке, обозначенном на фиг. 6.14 словом «декодер». Оставшаяся часть этой главы посвящена исследованию таких методов обработки данных в декодере, при которых ухудшение коэффициента в экспоненте вероятности ошибки мало по сравнению с

«Идеальная» схема декодирования должна обладать следующими свойствами:

1. Вероятность ошибки убывает экспоненциально при возрастании длины кодовых ограничений К в соответствии с верхней границей вероятности ошибки для случайного кодирования.

2. Сложность декодера пропорциональна К.

3. Необходимая вычислительная скорость декодера не зависит от К.

К сожалению, до сих пор не предложено схемы декодирования, полностью удовлетворяющей всем трем условиям.

Несмотря на это, можно указать несколько разных подходов [31, 57, 66, 96] к проблеме декодирования, которые уже привели к хорошим результатам и к построению практически применимых инженерных решений. Мы, в частности, остановимся на одном из таких методов, носящем название последовательное декодирование, характеристики которого в некотором отношении приближаются к идеальным.

Процедуры последовательного декодирования применимы к подклассу кодов с проверкой на четность, называемому сверточными кодами, и могут использоваться в широком классе каналов. Легче всего, однако, объяснить главную идею и методику последовательного декодирования, сконцентрировав внимание на двоичном симметричном канале (ДСК).

ДВОИЧНЫЙ СИММЕТРИЧНЫЙ КАНАЛ

Мы уже знакомы с ДСК (фиг. 6.20); выше он был получен из канала с аддитивным белым гауссовским шумом в предположении, что по этому каналу передаются сигналы лежащие в вершинах гиперкуба, а компоненты принимаемого сигнала симметрично квантуются на два уровня. Обычно буквы как входного, так и выходного алфавитов получаемого дискретного канала обозначают парой символов Диаграмма переходных вероятностей для ДСК в этих обозначениях приведена на фиг. 6.27; здесь через обозначена вероятность неправильного приема каждой отдельной компоненты передаваемого вектора.

Можно представлять себе передачу по ДСК так, как это изображено на фиг. 6.28, где вектор у (с компонентами, принимающими значения 0 и 1)

Фиг. 6.27. Двоичный симметричный канал.

Фиг. 6.28. Передача по

поступает в канал непосредственно с выхода кодера с проверкой на четность. Вектор , получаемый на выходе канала, в свою очередь непосредственно подается в декодирующее вычислительное устройство. Действия модулятора передатчика, шумов в гауссовском канале и квантующего устройства в приемнике описываются все одним и тем же параметром вероятностью искажения символа в В тех случаях, когда некоторая совокупность -мерных двоичных векторов служит для передачи одного из равновероятных сообщений по ДСК, оптимальный приемник сравнивает принимаемый -мерный вектор с каждым из векторов совокупности и определяет, для какого вероятность максимальна. Вероятность искажения любого отдельного символа в ДСК равна и последовательные символы в канале статистически независимы. Поэтому если у векторов отличаются символов, то

Величина называется расстоянием Хемминга [39] между

Правая часть в равенстве монотонно убывает при возрастании для Таким образом, оптимальный декодер ДСК может определить вычислив совокупность расстояний Хемминга и выбрав в качестве то из сообщений для которого минимально.

Так как компонента вектора равна 1 только в том случае, если соответствующие компоненты векторов отличаются, то расстояние Хемминга удобно получать, вычисляя и подсчитывая число получающихся единиц. Число единиц в двоичном векторе а принято называть его весом и обозначать . В этих обозначениях

Чтобы лучше понять задачу связи по ДСК, сформулируем задачу выбора решения геометрически аналогично тому, как это делалось выше.

Ранее был рассмотрен канал с аддитивным белым гауссовским шумом для случая двоичных сигналов и при приеме без квантования. При этом модулятор, изображенный на фиг. 6.1, может генерировать любую из вершин гиперкуба, лежащего в -мерном пространстве сигналов. Для скоростей кодер определяет подмножество из этих вершин в качестве совокупности сигналов. В тех случаях, когда входные сообщения равновероятны, оптимальный приемник без квантования полагает если евклидово расстояние от принятого

Фиг. 6.29. Пример, когда оптимальный двоичный декодер, использующий предварительное квантование данных с не ставит в соответствие принятому вектору сигнал, минимально удаленный от него в смысле евклидова расстояния.

Фиг. 6.30. Абстрактное представление пространства принятых сигналов для Каждой из точек соответствует свой особый -мерный двоичный вектор. Отмеченные кружками точки соответствуют векторам сигнала.

векторного сигнала до меньше, чем до любого другого вектора сигнала, т. е. если минимально.

При квантовании сигналов на выходах согласованных фильтров декодер должен принимать решение на основе квантованных выходных сигналов без учета Интерпретируем это решение геометрически, предварительно заметив, что симметричное квантование на два уровня соответствует отображению вектора в ближайшую к нему вершину гиперкуба При и равновероятных сообщепиях вершина будет соответствовать наиболее вероятному переданному сигналу. Ранее, в разд. 4.5 [см. соотношение ], мы видели, что при передаче отдельных символов такие решения оптимальны, если При однако, вершина у может не быть вектором сигнала; когда велико, доля вершин, которые соответствуют векторам сигналов, равная очень мала. Задача декодера — отобразить в один из векторов совокупности Если у векторов и отличаются компонент, то

где энергия, приходящаяся на одну компоненту.

В принятых для ДСК обозначениях (т. е. в предположении, что компоненты векторов принимают значения 0, 1, а не вершина соответствует выходному сигналу сигнал входному вектору ДСК число отличающихся координат — расстоянию Хемминга Согласно соотношению оптимальный декодер определяет минимальное следовательно, минимальное Таким образом, симметричное двоичное квантование с последующим оптимальным декодированием соответствует двухэтапной процедуре, в которой первый этап состоит в нахождении минимального а второй — в нахождении минимального Такая двухэтанная процедура решения, вообще говоря, не является оптимальной; иллюстрирующий пример приведен на фиг. 6.29, где вектор отображается квантующим устройством в вершину а та в свою очередь оптимальным декодером квантованных сигналов отображается несмотря на то что .

Конечно, двоичный симметричный канал можно также получать и при квантовании негауссовских каналов, так что этот канал является интересной и правомерной математической абстракцией. Поэтому полезно описать пространство

сигналов ДСК, не используя геометрию евклидова гиперкуба. В связи с этим представим себе совокупность всех двоичных -мерных) векторов с компонентами 0 и 1 как точек дискретного пространства сигналов (фиг. 6.30). Подмножество этого множества точек, состоящее из векторов соответствует совокупности сигналов с расстояниями Хемминга между ними определяемыми равенствами

Искажение вектора сигнала у при передаче по ДСК можно описать, введя понятие вектора случайного шума определяемого соотношением

Согласно этому определению, любая компонента вектора равна 1 в случае искажения символа, переданного по каналу, и равна 0, если искажения не произошло. При получим

и

Существует полная аналогия между задачами выбора решения в ДСК и в канале с белым гауссовским шумом. В обоих случаях имеются совокупность векторов сигналов и аддитивный шум. Основное отличие заключается в том, что сложение в ДСК производится по модулю 2, а расстояние определяется через вес, а не длину. Полезность этой аналогии связана с тем, что в обоих случаях «вероятность» монотонно зависит от «расстояния». Например, оптимальный приемник для ДСК также разбивает все пространство принимаемых сигналов на неперекрывающихся областей решения как показано на фиг. 6.31. При равновероятных сообщениях каждая область содержит те точки пространства принимаемых сигналов, расстояние Хемминга которых до меньше, чем расстояние Хемминга до любого другого вектора совокупности сигналов