Важнейшие классы полиномиальных кодов

Коды БЧХ. Циклический код, исправляющий более одной ошибки, т.е. код с d  5, в общем случае можно построить следующим образом:

а) по заданному k определить необходимое для исправления одной ошибки n-k и построить (n,k)-код описанным ранее методом;

б) рассматривая этот (n,k)-код как некорректирующий n-разрядный код, определить количество n₁-n дополнительных контрольных разрядов для обеспечения исправления одной ошибки в этом коде и построить тем самым (n₁,n)-код;

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

Однако код, построенный таким образом, не будет оптимальным с точки зрения количества контрольных символов при данной величине k, т.е. будет обладать излишней избыточностью. Минимальное число контрольных символов при данном k и данной корректирующей способности может быть получено при использовании одной из разновидностей полиномиальных кодов, называемой кодами Боуза – Чоудхури – Хоквингема или БЧХ-кодами.

Заданными при кодировании с помощью БЧХ-кодов является число ошибок s, которое требуется исправлять, и общая длина кодовой комбинации n. На выбор величины n накладывается ограничение: n=2^f – 1, где f – любое целое число больше нуля. Число информационных символов k и число контрольных символов n-k и их состав подлежат определению.

При заданной величине s кодовое расстояние кода может быть определено следующим образом:

(3.33)

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

Образующий полином g(x) БЧХ-кода находится как наименьшее общее кратное (НОК) так называемых минимальных полиномов до номера 2s-1 или d-2 включительно, т.е. g(x) = НОК [M_i(x)], где i = 1,3,5, . . ., 2s-1 – номера минимальных полиномов. Поскольку минимальные полиномы по определению являются простыми и неприводимыми, то, условившись об отбрасывании возможных одинаковых M_i(x), можно НОК заменить произведением полиномов

, (3.34)

число которых в этом произведении L=s. Далее определяется старшая степень j минимального полинома. Степень j есть такое наименьшее число, при котором 2^j – 1 нацело делится на n, отсюда следует, что j=f. После того, как определены число минимальных полиномов и старшая степень полинома, сами полиномы, из которых составляется произведение (3.34) выписываются из справочных таблиц. При этом, если в таблицах отсутствует полином нужного номера данной степени, то следует взять ближайший с нужным номером, но меньшей степени. Кроме того, если среди выбранных полиномов окажутся два одинаковых, то в (3.34) включают только один из них. После того, как (3.34) сформировано, можно определить степень  образующего полинома g(x), перемножив входящие в него полиномы, при этом

. (3.35)

Знак нестрогого равенства появился как результат того, что степени некоторых M_i(x) могут быть меньше j.

Далее можно определить число контрольных разрядов n-k, которое по определению равно степени образующего полинома, т.е. n-k = , после чего становится возможным и определение числа информационных разрядов k=n-(n-k). Если получившееся k окажется меньше требуемого для передачи заданного объема информации, необходимо перейти к следующему по порядку разрешенному n=2^f – 1 и выбрать для формирования g(x) минимальные полиномы степени f. Далее по описанной ранее методике для обычных циклических кодов при известном g(x) могут быть построены образующая и проверочная матрицы кода и, тем самым, код полностью построен и описан. Минимальные полиномы различных степеней и номеров являются справочными данными.

Для декодирования БЧХ-кодов могут быть использованы как алгоритмы анализа остатка от деления и мажоритарного декодирования, так и другие алгоритмы.

Важнейший подкласс БЧХ-кодов образуют коды Рида – Соломона, являющиеся недвоичными БЧХ-кодами. Они достаточно широко используются в системах двухуровневого каскадного кодирования.

Коды максимальной длины. Кодами максимальной длины называются циклические коды с параметрами (2^k-1, k), у которых в качестве образующего полинома выбран проверочный полином, полученный описанным ранее образом. Например, требуется построить код (15,4) максимальной дины. Выбрав по описанным выше правилам примитивный полином четвертой степени, например x⁴ + x + 1, найдем для него проверочный полином, который и будет образующим полиномом для кода (15,4) максимальной длины . Этот полином является полиномом кодовой комбинации кода. Остальные 14 ненулевых кодовых комбинаций являются четырнадцатью циклическими сдвигами этой комбинации (полинома). Отсюда вытекает одно важное свойство этих кодов. Поскольку все ненулевые комбинации являются циклическими сдвигами одной ненулевой комбинации, то все комбинации этого кода имеют один и тот же вес. Такие коды называются эквидистантными или симплексными. Кодеры для таких кодов иногда называют регистрами сдвига с линейными обратными связями, формирующими последовательности максимальной длины. Они имеют несколько различных применений. При большом числе разрядов такой регистр формирует последовательность с очень хорошими свойствами случайности. Такие устройства используются на практике в качестве генераторов псевдослучайных последовательностей.

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

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

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

Образующий полином кода Файра определяется выражением , где g(x)- неприводимый полином степени m, причем m>b, где b- длина исправляемого пакета ошибок, а c2b-1, причем с должно выбираться таким, чтобы оно не делилось нацело на число e=2^m-1. Число контрольных разрядов в кодовой комбинации кода Файра определяется по формуле n-k = c+m, а общее число разрядов в кодовой комбинации n находится как наименьшее общее кратное чисел с и е, т.е. n = НОК(с,е).

Коды Файра являются высокоскоростными кодами с малой избыточностью. Если использовать код БЧХ с той же корректирующей способностью, то он будет обладать большим коэффициентом избыточности. Вывод очевиден, поскольку исправить ошибки, сгруппированные в пакет проще, чем ошибки, рассредоточенные по всей длине комбинации.

Контрольные

вопросы к

лекции 15

15-1. Какие коды называются полиномиальными?

15-2. Какое конечное алгебраическое поле называется простым?

15-3. Какие коды называются циклическими?

15-4. Опишите процесс нахождения значений контрольных разрядов циклического (n,k)-кода при полиномиальном представлении?

15-5. Какими свойствами должен обладать образующий полином циклического (n,k)-кода?

15-6. Какой полином называется неприводимым?

15-7. Как по заданному образующему полиному построить каноническую образующую матрицу циклического (n,k)-кода?

15-8. Как по заданному образующему полиному построить неканоническую образующую матрицу циклического (n,k)-кода?

15-9. Какое свойство циклического (n,k)-кода позволяет осуществить переход от неканонической образующей матрицы к канонической?

15-10. Как обнаруживается наличие ошибки в принятой комбинации циклического (n,k)-кода при полиномиальном представлении?

15-11. Какое устройство используется для аппаратной реализации операции деления полиномов в кодерах и декодерах циклических кодов?

15-12. Сколько двухвходовых сумматоров по модулю два входит в состав кодера циклического кода?

15-13. Чем определяется расположение двухвходовых сумматоров по модулю два в составе кодера циклического кода?

15-14. Чем определяется количество входов сумматора по модулю два в составе кодера циклического кода на основе k-разрядного регистра сдвига?

15-15. Чем определяется соединение входов сумматора по модулю два с выходами триггеров регистра в составе кодера циклического кода на основе k-разрядного регистра сдвига?

15-16. Как находится проверочный полином циклического кода?

15-17. Когда применим метод мажоритарного декодирования?

15-18. Какая система проверочных уравнений называется ортогональной?

15-19. Какую функцию реализует мажоритарный элемент в составе мажоритарного декодера?

15-20. Как находится образующий полином БЧХ-кода?

15-21. Какие коды называются кодами максимальной длины?

15-22. Какие коды называются эквидистантными или симплексными?

15-23. Что называется пакетом ошибок?

15-24. Как находится образующий полином кода Файра?

15-25. В чем преимущество кодов Файра по сравнению с БЧХ-кодами?

Лекция 16

Сверточные

коды.