Материал: 5856

91

состоящий из q = 3 ошибок (эти позиции затемнены), то после деперемежения окажется лишь по одной ошибке в 1, 3 и 4 комбинациях.

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

Перемежение по частоте имеет смысл проводить лишь в том случае, когда на разных ортогональных несущих (см. разд. 2.12) одновременно передаются символы не одной, а нескольких кодовых комбинаций.

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

3.8 Комбинирование кодов

Рассмотрим ситуацию, когда передаваемое сообщение участвует не в одном, как это предполагалось ранее, а в нескольких актах помехоустойчивого кодирования. Существуют последовательные и параллельные методы комбинирования кодов.

Код, получающийся в результате последовательной реализации нескольких процедур кодирования (кодами одного типа или разными), называется каскадным. Допустим, на каждом этапе применяются линейные блочные коды. Тогда первый кодер, получив k информационных символов, добавляет к ним r1 проверочных символов и все вместе подает на вход второго кодера в качестве информационных символов. Тот, в свою очередь, добавляет к ним еще r2 проверочных символов и т.д. Первый код в этой цепи называется внутренним кодом.

В итоге после прохождения цепочки из р кодеров на выходе имеем комбинацию линейного блочного кода, содержащую те же k информационных символов и r = r1 +…+ rp проверочных символов. Возрастают избыточность кода и его корректирующая способность.

Пример 1. Двумерный композиционный код получается следующим образом. Прямоугольная таблица, содержащая n1 столбцов и n2 строк, делится на четыре блока. Левый верхний блок (k1 столбцов и k2 строк) заполняется информационными символами от источника. Затем каждая строка отдельно кодируется (n1,k1) линейным блочным кодом, при этом r1 = n1 – k1 проверочных символов каждой строки помещают в правый верхний блок. Далее каждый столбец кодируется (n2,k2)-кодом. В итоге получим новый (n,k)-код, где n = n1n2, k = k1k2. На рис. 3.9 приведен пример кодирования, когда на обоих этапах используется код с проверкой на четность.

92

Рис. 3.9. Пример кодирования двумерным композиционным кодом (32,21)

Одиночная ошибка нарушает условие четности в соответствующих строке и столбце, поэтому ее положение может быть определено, но две ошибки код уже исправить не может. Однократное кодирование кодом с проверкой на четность позволяет лишь обнаруживать одиночные ошибки, но не исправлять их. Итак, применение двукратного кодирования позволило повысить корректирующую способность кода. При этом интересно посмотреть, велика ли цена. Из Приложения 1 мы видим, что примерно те же значения параметров имеет (31,21)-код БЧХ, но он способен исправлять и любые двукратные ошибки.

Пример 2. Поступающие на вход кодера k 2r 1 r информационных символов кодируются кодом Хэмминга, а затем к полученным символам добавляется еще один проверочный символ, чтобы организовать общую проверку на четность. В итоге кодовое расстояние кода повышается с трех до четырех, и он приобретает способность обнаруживать ошибки до трехкратной включительно.

Декодирование кода также проводится в два этапа. На первом этапе принятая комбинация подвергается общей проверке на четность, в результате которой получают ответ на вопрос, четной или нечетной является кратность ошибок. Затем последний проверочный символ отбрасывается, и по оставшимся символам вычисляется синдром по правилам декодирования кода Хэмминга. Сопоставление результатов на обоих этапах позволяет даже определить кратность ошибки (сам по себе код Хэмминга на это не способен) и в зависимости от этого предпринять нужные действия (если ошибка однократная, код Хэмминга ее может исправить; если двукратная или трехкратная, нужно сделать запрос на повторную передачу комбинации). Снова отметим, что такими же характеристиками обладает код Рида-Малера с кодовым расстоянием, равным четырем.

Множество примеров показывает, что всегда можно найти такой код, который при тех же значениях n и k при использовании одноэтапной процедуры кодирования обеспечивает лучшую (или не худшую) помехоустойчивость, чем каскадный код, формируемый в несколько этапов. Зачем же тогда применяются каскадные коды? Лишь потому, что на каждом этапе можно использовать относительно простые и короткие коды и менее трудоемкие методы кодирования и декодирования. В частности, при записи на компакт-

93

диск требуется применять код, способный исправлять пакеты, содержащие тысячи ошибок. И он реализуется путем многократного последовательного выполнения операций перемежения и кодирования кодом Рида-Соломона.

Возможно и параллельное использование нескольких процедур кодиро-

вания. Здесь последовательность информационных символов одновременно кодируется, допустим, двумя систематическими кодами. Лучше, если на вход второго кодера она будет подаваться после перемежения. Далее по линии передаются сами информационные символы и проверочные символы с выходов обоих кодеров. Очевидно, что в отличие от кодирования, имеет смысл лишь

совместная работа декодеров путем взаимного обмена информацией в про-

цессе декодирования. Именно на этих принципах построено использование турбо-кодов. Дальнейшее развитие этих идей дано в разд. 5.7.

Вопросы для самоконтроля по главе 3

1.Чем определяется корректирующая способность кода? Поясните на примере.

2.Какие коды называются корректирующими?

3.Что значит “обнаружить ошибки” при декодировании кодовой комбинации?

4.Что значит “исправить ошибки” при декодировании кодовой комбинации?

5.Каков характерный признак, позволяющий отличить кодовую таблицу линейного блочного кода от кодовых таблиц других кодов?

6.Что такое проверочная матрица линейного блочного кода? Как она используется при обнаружении ошибок в принятой комбинации?

7.Каков характерный признак, позволяющий отличить кодовую таблицу циклического кода от кодовых таблиц других кодов?

8.Чему равно количество комбинации в кодовой таблице линейного блочного кода?

9.Почему в проверочной матрице не может быть нулевых: столбцов? строк?

10.Какой смысл имеют строки проверочной матрицы?

11.По каким признакам можно определить, что проверочная матрица принадлежит коду, способному исправить любую одиночную ошибку?

12.Чем обусловлена популярность циклических кодов? Из каких логических элементов состоят кодер и декодер?

13.В чем заключается фундаментальное свойство комбинаций циклического кода?

14.Может ли помехоустойчивый код быть безизбыточным?

15.Почему декодирование по минимуму расстояния применяется

94

редко?

16.Являются ли сверточные коды блочными и чем обусловлена их популярность?

17.Какова цель перемежения символов?

18.Какие способы комбинирования кодов используют в системах свя-

зи?

4 КОДИРОВАНИЕ ИСТОЧНИКА

Сначала определим, сколько информации содержится в сообщении Х на выходе источника информации. Сообщение имеет цифровую форму, и ради упрощения обозначений полагаем, что Х – это m-ичный символ, а х1,x2,…,xm – его возможные значения.

Чтобы исключить влияние остальных элементов тракта передачи на рис. 2.1 (передатчик, линия, приемник), полагаем, что получатель имеет возможность непосредственно наблюдать сообщение, выдаваемое источником, то есть Y=Х. Конечная цель получателя заключается в том, чтобы определить, какое именно значение xj появилось на выходе источника. Эту задачу он может решить столь же успешно, если находится на другом конце цифрового канала без помех, в котором каждому из возможных сигналов уk соответствует единственное значение хj, поэтому по принятому сигналу всегда можно безошибочно восстановить переданное сообщение. Например, канал, в котором производится тождественное преобразование передаваемого сообщения xj yj, является самой простой и наглядной формой канала без помех.

Пусть задано полное вероятностное описание переданного сообщения

определенность относительно того, какое именно значение появится на вы-

ходе источника. После появления конкретного значения, например х3, неопределенность исчезает, и объем знаний наблюдателя возрастает (не знал – узнал).

Количество информации, получаемой наблюдателем при появлении

и назвал эту величину собственной информацией символа хj.

Выбор основания логарифма а определяет единицу количества информации. Если а=2, то единица называется двоичной (бит), при а = e 2,72 –

95

натуральной, а при а = 10 – десятичной. Переход от одной системы логарифмов к другой равносилен изменению единицы количества информации

то есть 1 нат. ед.=log2e бит 1,443 бит,

1дес. ед.=log210 бит 3,32 бит.

Втехники связи наиболее широко применяются двоичные сигналы, об-

ладающие равновозможными состояниями x1 и x2. Тогда количество информации, содержащейся в любом из этих сигналов, одинаково и равно I(x1) =

I(x2) = –log(1/2) = 1 бит.

Поэтому двоичные единицы информации используются наиболее часто. В дальнейшем по умолчанию мы также будем использовать двоичные единицы (отметим, что не следует путать два различных значения слова “бит”: 1) двоичный сигнал; 2) двоичная единица количества информации).

Определение (4.2) не является единственно возможным. Предложены и другие способы определения количества информации (см. разд. 4.6), но к настоящему времени именно теория информации по Шеннону позволила получить наибольшее количество полезных для практики результатов.

Свойства собственной информации:

1)I(xj) 0, причем знак равенства имеет место лишь в ситуации, когда X

–детерминированный сигнал, т.е. p(x1)=1 , следовательно, любые другие состояния сигнала невозможны (m=1);

2)величина собственной информации тем больше, чем менее вероятно данное состояние;

3)обычно заранее не известно, сколько информации будет содержать

сигнал, поскольку заранее не известно, какое именно значение xj появится на выходе источника.

Последнее обстоятельство позволяет саму величину Ij=I(xj) считать одним из возможных значений некоторой дискретной случайной величины, имеющей ряд распределения

Например, пусть четверичный сигнал с двукратной ФМ характеризуется значениями начальной фазы

тогда ряд распределения для величины собственной информации имеет вид