Канальное кодирование

Все преимущества цифрового представления сигналов могут быть реализованы только при условии безошибочной передачи данных по каналам связи. Последствия неверно принятого бита данных значительно более серьезны, чем в аналоговом телевидении. Канальное кодирование необходимо для повышения помехоустойчивости передачи данных. Принцип канального кодирования основан на использовании специальных кодов, позволяющих обнаруживать и восстанавливать истинные значения данных, искаженных за счет влияния помех в канале связи. Теоретической основой таких кодов является добавление к передаваемым данным избыточной информации. В простейшем случае ошибки обнаруживают путем добавления к каждому кодовому слову бита, дополняющего число единиц до четного значения. На приемном конце производят проверку на четность. Если кодовая группа не проходит эту проверки, то в ней содержится ошибка. Можно замаскировать эту ошибку, заменяя принятую кодовую комбинацию предыдущей.

Чтобы получить возможность исправлять ошибки, нужно вводить дополнительную избыточную информацию (рис. 10). Две проверки на четность (по вертикали и по горизонтали) позволяют выявить ошибочный бит. На практике используют значительно более сложные и эффективные коды с исправлением ошибок. Коды, корректирующие ошибки передачи, применяют последовательно, с учетом их различных свойств и способности корректировать ошибки различного характера. (рис. 11). Код, применяемый на передающей стороне первым, должен декодироваться на приемной стороне последним. Такой код называют внешним. Соответственно, код, применяемый на передающей стороне последним, декодируют на приемном устройстве первым – это внутренний код.

Число ошибок, которые корректирующий код может исправить в определенном интервале последовательности двоичных символов, называют исправляющей способностью кода. Основной принцип построения корректирующих кодов состоит в том, что в каждую передаваемую кодовую комбинацию из информационных символов вводят дополнительных двоичных символов. В результате получается новая кодовая комбинация, содержащая двоичных символов. Этот код называют . Избыточность такого кода . Из общего числа комбинаций разрешенные (правильные) , остальные ошибочные (запрещенные). Появление одной из запрещенных комбинаций на приемной стороне означает, что имеется ошибка. Для оценки корректирующей способности кода используют понятие кодового расстояния Хемминга которое определено суммарным числом несовпадающих бит. Одиночная кодовая ошибка дает кодовое расстояние . Следовательно, кодовое расстояние между разрешенными комбинациями должно составлять не менее . Дл обнаружения ошибок кодовое расстояние должно быть . Для исправления одиночных ошибок нужно, чтобы кодовое расстояние между двумя любыми разрешенными кодовыми комбинациями было не менее 3. В этом случае принятую запрещенную кодовую комбинацию заменяют ближайшей к ней разрешенной комбинацией. В общем случае для коррекции ошибок в кодовой комбинации расстояние между двумя разрешенными комбинациями .
Для увеличения кодового расстояния между разрешенными кодовыми комбинациями нужно увеличивать число контрольных (избыточных) символов .

Суммой двух полиномов f(x) и g(x) называется полином, который получен сложением по mod2 коэффициентов при одинаковых степенях х, определяемый следующим образом:

(X3 + X2 + 0×X + 1)+ (X2 + X + 1)=

X3 + 0 + X + 0 = X3 +X.

Произведение полиномов получают по обычному правилу перемножения степенных функций, однако получаемые коэффициенты при данной степени Х складываются по . Например:

(X3 + X2 + 0 + 1)*(X + 1)= X3 + X2 + 0 + 1 X4 + X3 + 0 + X X4 + 0 + X2 + X + 1 = X4 + X2 + X +1

Первое уравнение есть результат умножения на 1; второе – на Х. При формировании результата суммируют по модулю 2 коэффициенты при одинаковых степенях Х.

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

(X 3 + X2 + 0 + 1)* (X2 + X)= X4 + X3 + 0 + X X5 + X 4 + 0 + X2 X5 + 0 + X3 + X2 + X = X5 + X3 + X2 + X.

Первый многочлен получился после умножения на Х, а второй – на Х ².

При суммировании единичные коэффициенты при степени 4 дали нуль.

 

Наконец, можно сформулировать теорему о делении полиномов: для каждой пары полиномов С(х) и d(x), d(x) ≠ 0 существует единственная пара полиномов q(x) — частное и r(х) — остаток, такие, что

С (х) = q(x)× d(x) + r(х), (1.58)

где степень остатка r(х) меньше степени делителя d(x).

Иными словами, деление полиномов производится по правилам деления степенных функций, при этом операция вычитания заменяется суммированием по mod2. Например:

X3 + X2 + X+ 1/(X3 +X2) X3 + X2 =1+ остаток (x+1) результат деления

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

Еще один пример деления полиномов:

Пусть нужно разделить на полином . Делим в столбик, как обычно! Но нужно помнить, что вычитание эквивалентно сложению, которое ведется по модулю 2!

Делитель

Результат деления

-остаток!

 

Основная идея помехозащитного кодирования Рида-Соломона заключается в умножении информационного слова, представленного в виде полинома D, на неприводимый полином G [3], известный обеим сторонам, в результате чего получается кодовое слово C, опять-таки представленное в виде полинома.

Декодирование осуществляется в обратном порядке: если при делении кодового слова C на полином G декодер получает остаток, то он может рапортовать наверх об ошибке. Соответственно, если кодовое слово разделилось нацело, его передача завершилась успешно.

Если степень полинома G (называемого также порождающим полиномом) превосходит степень кодового слова, по меньшей мере, на две степени, то декодер может не только обнаруживать, но и исправлять одиночные ошибки. Если же превосходство степени порождающего полинома над кодовым словом равно четырем, то восстановлению поддаются и двойные ошибки. Короче говоря, степень полинома связана с максимальным числом исправляемых ошибок следующим образом: . Следовательно, кодовое слово должно содержать два дополнительных символа на одну исправляемую ошибку. В то же время, максимальное число обнаруженных ошибок равно , т.е. избыточность составляет один символ на каждую распознаваемую ошибку.

 

Произведем умножение полиномов согласно изложенным выше правилам.

Видно, что все получилось правильно.

Формирование кодовых групп реализуем путем умножения информационного вектора размером , где , на производящую матрицу размером , где . В результате умножения получим векторы кодовых групп размерностью .

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

Получилось, что всего 16 разрешенных информационных кодовых групп, или 2^k=4 . Запрещенных кодовых групп 2 ⁿ -2 ^k = 128-16=112. Минимальное расстояние по Хеммингу между разрешенными кодовыми группами равно 3, т. е. числу проверочных бит . Значит такой код может обнаруживать две одиночные ошибки и исправлять одну.

 

Лучше записать происходящее, как умножение исправляющей матрицы размером 3*7 на вектор принятой кодовой комбинации размером 7*1, в результате которого получаем вектор размером 3*1:

;

 

Среди большого числа циклических кодов к числу наиболее эффективных и широко используемых относятся коды Бозе-Чоудхурия-Хоквингема (БЧХ-коды).

 

Код Рида-Соломона обладает способностью исправлять пакетные ошибки, когда ошибочные символы следуют друг за другом. Его используют для внешнего кодирования. Код Рида-Соломона требует добавления двух проверочных символов на одну исправляемую ошибку. На каждый пакет общего транспортного потока длиной 188 байт добавляют 16 проверочных байт. Это позволяет исправить 8 байт, искаженных помехой в ходе передачи. Такой код в литературе называют (204, 188, 8).

Корректирующей способности этого кода может не хватить для исправления длинного пакета ошибок (импульсная помеха, царапина на лазерном диске и пр.). Важно преобразовать пакетную ошибку в последовательность одиночных ошибок. Простейшим способом такого преобразования является запись кодированного внешним кодером сигнала в память построчно, а считывание по столбцам. Тогда длинная горизонтальная последовательность ошибок превращается в последовательность одиночных ошибок (рис. 9).. Но значительно лучшие результаты получают при использовании перемешивания информации (скремблирования) (рис. 10). Скремблирование применяют и для шифровки передаваемых данных, так как восстановить правильный порядок следования битов при дескремблировании можно только обладая информацией о правилах перестановки битов.