2.3. Важные классы групповых кодов

В этом разделе опишем некоторые наиболее важные классы групповых кодов. Эти коды либо являются циклическими, либо получаются видоизменением циклических кодов. Рассмотрим свойства этих кодов достаточно подробно, с тем чтобы в следующих главах иметь возможность исследовать вычисление их характеристик и привести описание практических алгоритмов декодирования. Остальные свойства кодов, а также их связь с другими классами кодов можно найти в классических учебниках алгебраической теории кодирования [1, 2, 8].

2.3.1. Коды БЧХ

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

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

Таким образом, порождающий многочлен кода БЧХ можно записать в виде

Коды с называются кодами БЧХ в узком смысле. Непримитивные коды БЧХ определяются аналогично, но а заменяется на непримитивный элемент поля и длина блока становится равной порядку Список порождающих многочленов для примитивных и непримитивных двоичных кодов БЧХ приведен в приложении А.

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

Таким образом, порождающий многочлен имеет вид

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

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

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

Заметим, что степень равна 21, так что для исправления ошибок требуется только 21 проверочных символов. Обычно выбирается значение При этом код позволяет исправлять -ичные символы, т. е. пакеты ошибок. Такие коды очень полезны в схемах двухуровневого «каскадного» кодирования (подробно описанных в гл. 8).

Пример. Пусть нужно построить порождающий многочлен для кода Рида-Соломона длиной 7, исправляющего ошибки в двух символах. Снова предположим, что задается табл. 2.4. Используя (2.21), получаем порождающий многочлен в виде

Таким образом, порождает -код, который может исправлять все двойные ошибки Заметим, что коэффициенты порождающего многочлена являются обычно элементами

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

Ранее был приведен спектр кодов Хемминга. Известен также спектр -кодов Рида — Соломона; он имеет вид при