Тема 5. Кодирование канала (часть 3) (Материалы лекций), страница 3

Если синдром отличен от нуля, значит, обнаружена ошибка и принятый вектор — это искаженное кодовое слово; данная ошибка исправляется путем прибавления к принятому вектору вектора ошибки (указанной синдромом), т.е. аналогично процедуре, описанной в разделе 6.4.8. Этот метод декодирования хорош лля простых кодов. Более сложные коды для практического использования требуют применения алгебраических методик. 8.8.1. Коды Хэмммнга Коды Хзмминга (Наппшпй собез) — это простой класс блочных кодов, которые имеют следующую структуру: (а, А) = (2 — 1, 2 — 1 — ги), (6.71) где ю=2,3, ....

Минимальное расстояние этих кодов равно З„поэтому, согласно уравнениям (6.44) и (6.47), они способны исправлять все однобитовые ошибки или определять все модели ошибки из двух или малого числа ошибок в блоке. Декодирование с помощью синдромов особенно хорошо подходит к кодам Хэмминга. Фактически синдром можно превратить в двоичный указатель местоположения ошибки (5). Хотя коды Хзмминга не являются слишком мощными, они принадлежат к очень ограниченному классу блочных кодов, называемых совершеииыми; их особенности описывались в разделе 6.5.4. 6.0.

Известные блочные коды 39т 1001011 100101 10010 1001 100 10 1 6.8. Известные блочные коды 00 100 110 011 011 111 101 (000 ) Синдром В этой главе рассматривается сверточное кодирование. В главе б обсуждались основы линейных блочных кодов, которые описываются двумя целыми числами, и и к, и полиномиальным или матричным генератором. Целое число к указывает на число бит данных, которые образуют вход блочного кодера. Целое число и — это суммарное количество разрядов в соответствующем кодовом слове на выходе кодера.

Особенностью линейного блочного кода является то, что каждый из и-кортежей кодовых слов однозначно определяется А-кортежем входного сообщения. Отношение Мп, называемое степенью кодирования кода (соде га!е), является мерой добавленной избыточности. Сверточный код описывается тремя целыми числами н, к и К„где отношение к/и имеет такое же значение степени кодирования (информация, приходящаяся на закодированный бит), как и для блочного кода; однако и не определяет длину блока или кодового слова, как это было в блочных кодах. Целое число К является параметром, называемым длиной кодового ограничения (сопмга!и! !епя!)з); оно указывает число разрядов к-кортежа в кодируюшем регистре сдвига. Важная особенность сверточных кодов, в отличие от блочных, состоит в том, что кодер имеет память — я-кортежи, получаемые при сверточком кодировании, являются функцией нс только одного входного (-кортежа, но и предыдуших К-1 входных йкортежей.

На практике и и к — это небольшие целые числа, а К изменяется с целью контроля мощности и сложности кода. 7.1. Сверточное кодирование На рис. 1.2 представлена типичная функциональная схема системы цифровой связи. Разновидность такой схемы, относящаяся, в первую очередь, к сверточному кодированию/декодированию и модуляции/демодуляции, показана на рис. 7.1. Исходное сообщение на входе обозначается последовательностью ш = ть ть ..., т„..., где т, — двоичный знак (бит), а ! — индекс времени. Если быть точным, то элементы га следовало бы дополнять индексом члена класса (например, для бинарного кода, 1 или 0) и индексом времени. Однако в этой главе для простоты будет использоваться только индекс, обозначающий время (или расположение элемента внутри последовательности).

Мы будем предполагать, что все т, равновероятно равны единице или нулю и независимы между собой. Будучи независимой, последовательность битов нуждается в некоторой избыточности, т.с. знание о бите т; не дает никакой информации о бите т, (при ~ «Я. Кодер преобразует каждую последовательность га в уникальную последовательность кодовых слов () = б(ш). Даже несмотря на то что последовательносп ш однозначно определяет последовательность (1, ключевой особенностью свсрточных кодов является то, что данный к-коргеж вну1ри пз нв однозначно определяет связанные с ним и-кортежи внутри (), поскольку кодирование каждого из к-кортежей является функцией не только к-коргежей, но и предыдуших К вЂ” 1 ккортежей.

Последовательность () можно разделить на последовательность кодовых слов: $3 = (/ь (/ь ..., ()ь .... Каждое кодовое слово (/; состоит из двоичных кодовых символов, часто называемых канальными символами, канальными битами, или битами кода; в отличие от битов входного сообщения, кодовые символы не являются независимыми. В типичных системах связи последовательность кодовых слов О модулируется сигналом л(г).

В ходе передачи сигнал искажается шумом, в результате чего, как показано на рис. 7.1, получается сигнал л(г) и демодулированная последовательность л. = Уь Е„..., ~л .... Задача декодера состоит в получении оценки й = т,,тз,...,т, исходной последовательности сообшения с помошью полученной последовательности Е и априорных знаний о процедуре кодирования. т тите -,ть -. Е к дп 2з, ..., 2ь ..., гдвд~=г1ь ...,зл,, зм и гл — вгорй символ кодового слова 4 нв выходе демодулятора Рис. 7.1. Кодирование/декодированив и модуляция/двмодуляция в каназв связи 1 2 3 ...

ЛК в=тыл - тгВходная послвдоввтвльность 1сдвнгввтся нв 'к позиций зв один такт) кк-рвзрядный регистр сдвига л сумматоров по модулю 2 витальность кодового слова и = уп йз, ..., ц, гдв О, = ии... ир, ... иь;- г-я ветвь кодовых алов иуг-Рй двоичный кодовый символ кодовогослова Ц Рис. 72 Свврточный кодер с длиной кодовою Оентичагия К и степенью кодированшг 1г/л Ф07 7.1. Свеоточное кодноованне Обычный сверточный кодер, показанный на рис. 7.2, реализуется с кК-разрядным регистром сдвига и л сумматорами по модулю 2, где К вЂ” длина кодового ограничения. Длина кодового ограничения — это количество к-битовых сдвигов, после которых один информационный бит может повлиять на выходной сигнал кодера.

В каждый момент времени на место первых к разрядов регистра перемешаются гс новых бит; все биты в регистре смешаются на к разрядов вправо, и выходные данные и сумматоров последовательно дискретизируются, давая, в результате, биты кода. Затем эти символы кода используются модулятором для формирования сигналов, которые будут переданы по каналу. Поскольку для каждой входной группы из гс бит сообшения имеется и бит кола, степень кодирования равна кгл бнт сообшения на бит кода, где й с и. Мы будем рассматривать только наиболее часто используемые двоичные сверточные кодеры, для которых /г = 1, т.е. те кодируюшне устройства, в которых биты сообщения сдвигаются по одному биту за рвз, хотя обобщение на алфавиты более высоких порядков не вызывает никаких затруднений [1, 2[.

Для кодера с /г = 1, за /-й момент времени бит сообщения т; будет перемещен на место первого разряда регистра сдвига„все предыдущие биты в регистре будут смещены на один разряд вправо, а выходной сигнал и сумматоров будет последовательно оцифрован и передан. Поскольку для каждого бита сообщения имеется и бит кода, степень кодирования равна 1/и. Имеющиеся в момент времени г; и кодовых символов составляют /-е кодовое слово ветви, (/; = ии, ии, ..., и ., гле ия (/= 1, 2, ..., и) — это /-й кодовый символ, принадлежащий /-му кодовому слову ветви. Отметим„что для кодера со степенью кодирования 1/и, АК- разрядный регистр сдвига для простоты можно называть К-разрядным регистром, а длину кодового ограничения К, которая выражается в единицах разрядов К-кортежей, можно именовать длиной кодового ограничения в битах.

7.2. Представление сверточного кодера Чтобы иметь возможность описывать сверточный код, необходимо определить кодируюшую функцию б(ш) так, чтобы по данной входной последовательности пз можно было быстро вычислить выходную последовательность (). Для реализации сверточного кодирования используется несколько методов; наиболее распространенными из них являются графическая сеязь, гекторы, полиномы связи, диаграмма состояния„древоеидная и решетчатая диаграммы. Все они рассматриваются ниже.

7.2.1. Представление связи При обсуждении сверточных кодеров в качестве модели будем использовать свсрточный кодер, показанный на рис. 7.3. На этом рисунке изображен сверточный кодер (2, 1) с длиной кодового ограничения К = 3. В нем имеется и = 2 сумматора по модулю 2; следовательно, степень кодирования кода Мп равна 1/2. При каждом поступлении бит помещается в крайний левый разряд, а биты регистра смещаются на одну позицию вправо. Затем коммутатор на выходе дискретизирует выходы всех сумматоров по модулю 2 (т.е. сначала верхний сумматор, затем нижний), в результате чего формируются пары кодовых символов, образующих кодовое слово, связанное с только что поступившим битом. Это выполняется для каждого входного бита.

Выбор связи между сумматорами и разрядами регистра влияет на характеристики кода. Всякое изменение в выборе связей приводит в результате к различным кодам. Связь, конечно же, выбирается и изменяется не произвольным образом. Задача выбора связей, дающая оптимальные дистанционные свойства, сложна и в общем случае не решается; однако для всех значений длины кодового ограничения, меньших 20, с помощью компьютеров были найдены хорошие коды [3 — 5[, В отличие от блочных кодов, имеющих фиксированную длину слова и, в сверточных кодах нет определенного размера блока.

Однако с помощью периодического отбрасыеания сверточным кодам часто принудительно придают блочную структуру. Это требует некоторого количества нулевых разрядов, присоединенных к концу входной последовательности данных, которые служат для очистки (или промыеки) регистра сдвига от бит данных. Поскольку добавленные нули не несут дополнительной инфор- Глинн 7 кнннплнон копноонянне: часть 2 аол мации, эффективнал степень кодирования будет ниже й)л. Чтобы степень кодирования оставалась близкой к ккл, период отбрасывания чаше всего делают настолько боль- шим, насколько зто возможно. и )Первый ' ) кодовый оимеол Выходное кодовое слово и ) Второй 1 кодовый оимеол Входной бит Рнс.