4.1.2. БЧХ-коды

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

Определение 4.1.17. Подпространство С -мерного двоичного векторного пространства называется циклическим подпространством или циклическим кодом, если для каждого вектора кода С вектор полученный из v «циклическим сдвигом» на одну позицию вправо, также принадлежит С.

Определение 4.1.18. Множество полиномов называется идеалом тогда и только тогда, когда оно состоит из всех кратных некоторого полинома.

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

наших рассуждениях мы используем просто термин «идеал». Кроме того, для описания циклических кодов мы будет использовать алгебру полиномов по модулю также тот факт, что полином степени может быть представлен вектором в последнее всегда предполагается двоичным векторным пространством, даже когда это явно не упоминается.

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

Столбцы проверочной матрицы Н (-кода Хэмминга суть двоичные векторы длины 3. Мы знаем, что их можно рассматривать как полиномы степени 2 над ). Это наводит на мысль, что столбцы матрицы Н могут индексироваться элементами из Более точно, если а — корень полинома то семь ненулевых элементов поля — это степени и они соответствуют столбцам матрицы Н. (Имеется соответствие, аналогичное табл. 3.3.1, и читатель может построить подобную таблицу, чтобы в этом убедиться; см. также теорему 3.3.11.) Аналогичным образом кодовые слова в (-коде Хэмминга могут быть записаны в виде двоичных полиномов степени 6; в этом случае кодовые слова — это все полиномы ) степени , для которых а является корнем.

Итак, — минимальный полином элемента а над GF(2), и все полиномы, для которых а является корнем, — это в точности элементы идеала, порожденного полиномом в кольце Поскольку а - элемент порядка 7 (т.е. а — корень полинома ), мы имеем Рассмотрим факторкольцо и образ порожденного идеала в этом факторкольце. Ясно, что если дано какое-то кратное полинома то после деления его на мы получим . Лалее, ), и поскольку ), то — кратное полинома Поэтому образ идеала, порожденного полиномом при естественном отображении из можно рассматривать как совокупность в точности тех полиномов степени б, которые делятся на Таким образом, мы получаем описание (-кода Хэмминга в виде идеала, порожденного образом полинома ) . Далее мы обобщим приведенные рассуждения, но сначала представим альтернативную схему кодирования/декодирования для (-кода Хэмминга.

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

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

Пример. Чтобы передать информацию (1,0,0,1), мы разделим полином на чтобы получить остаток передается кодовое слово (1,0,0,1,1,1,0). Заметим, что значение полинома в точке а равно нулю. (Отметим, что ) Если теперь получен вектор (0, 0,0,1,1,1,0), то мы вычисляем значение соответствующего полинома в точке а и получаем из этого мы заключаем, что ошибка произошла в коэффициенте при

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

Теорема 4.1.19. Пусть J — идеал алгебры полиномов по модулю и пусть — один из ненулевых полиномов наименьшей степени в J. Тогда полином принадлежит J в том и только том случае, когда Более того,

Доказательство. Применяя алгоритм деления полиномов, получаем , где . Отсюда следует, что и поскольку и принадлежат также принадлежит J. Однако — полином наименьшей степени в J, так что должен быть нулевым полиномом, — кратное полинома Рассматривая имеем и поскольку то откуда . Подобными рассуждениями получаем, что

Таким образом, каждый идеал алгебры полиномов по модулю порожден полиномом степень которого меньше степени любого другого полинома в J, и элементы идеала J — это кратные полинома Если то идеал J имеет размерность . Действительно, J — векторное подпространство и векторы линейно независимы, потому что их линейная комбинация не мажет быть равной поскольку его степень Очевидно, каждый полином в J мажет быть выражен через эти базисные векторы. Полином называется образующим идеала J или его порождающим полиномом.

Мы говорим, что полином ортогонален идеалу J, если для любого полинома

Теорема 4.1.20. Рассмотрим полиномы где Тогда в алгебре полиномов по модулю полином ортогонален идеалу, порожденному полиномом тогда и только тогда, когда принадлежит идеалу, порожденному полиномом

Доказательство. Предположим, что принадлежит идеалу, порожденному полиномом и что принадлежит идеалу, порожденному полиномом тогда по теореме

Обратно, если ортогонален идеалу, порожденному полиномом , то , т.е. — кратное полинома Отсюда мы заключаем, что должен быть кратным полинома и поэтому принадлежит идеалу, порожденному полиномом

Пример. Рассмотрим алгебру полиномов по модулю поскольку коэффициенты принадлежат мы имеем — следовательно, Будем теперь работать с Полином делит , и, значит, в силу теоремы 4.1.19 мы можем рассматривать его как образующий идеала с базисными векторами Полином принадлежит этому идеалу. С учетом соответствия между векторами и полиномами этот идеал есть не что иное, как подпространство векторного пространства с базисными векторами , а полином — это вектор

Идеал, ортогональный к упомянутому выше, — это идеал, порожденный полиномом а базисными векторами являются

Заметим, что в алгебре полиномов по модулю размерность идеала равна , где — степень его образующего полинома. Размерность ортогонального ему идеала равна , и степень его порождающего полинома равна . В приведенном выше примере и размерности соответствующих идеалов равны 4 и 3.

Теорема 4.1.21. В алгебре полиномов по модулю подпространство пространства является циклическим тогда и только тогда, когда оно — идеал.

Локазательство. Основное замечание в этом случае состоит в том, что умножение по модулю полинома на эквивалентно циклическому сдвигу, потому что

Если С — циклическое подпространство пространства то из следует, что все принадлежат С, и по определению С — идеал.

Обратно, если подпространство С пространства является идеалом, то из следует, что , а поскольку коэффициенты полинома v получены циклическим сдвигом коэффициентов полинома v, мы заключаем, что С — циклическое подпространство.

Таким образом, циклический код полностью определяется порождающим полиномом, который делит Сообщение (максимальной длины к) может быть закодировано с использованием кода С путем вычисления произведения где — полином, соответствующий во, и является образующим идеала С, размерность которого равна

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

Очевидно, что для этого кода сообщение может иметь не более четырех битов информации.

Эквивалентно, код может быть определен как подпространство, ортогональное идеалу, порожденному полиномом . Заметим, что . Если , то размерность кода равна . Элемент принадлежит коду тогда и только тогда, когда или, эквивалентно, тогда и только тогда, когда Чтобы доказать это в одном направлении, рассмотрим полином в коде; тогда имеется полином такой, что . Однако поскольку то качестве упражнения читателю остается доказательство в обратном направлении. Из мы заключаем, что коэффициент при в произведении задается формулой , где индексы вычисляются по модулю . Это объясняет тот факт, что матрица Н, соответствующая полиному имеет обратный порядок элементов. Детали даны в приводимом ниже примере. Например, в приведенном выше примере кодовое слово соответствует полиному Ясно, что Полином называется проверочным полиномом кода, порожденного полиномом Поскольку он может быть также использован как порождающий полином другого кода дуального коду С. Аналогия с введенным выше дуальным кодом, а также соответствие между полиномами и матрицами G и Н становится понятнее, если разобрать следующий пример.

Пример. Рассмотрим полином . Полином порождает циклический код С, у которого . Элементы образуют базис кода, и, следовательно, матрицу G можно рассматривать как порождающую матрицу кода.

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

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

Легко убедиться, что GHT — нулевая матрица. Этот код эквивалентен -коду Хэмминга.

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

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

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

Пример. Пусть а — примитивный элемент поля Рассмотрим код, в котором каждый полином имеет корни для а мы имеем соотношение

Однако полином, имеющий корень а, будет также иметь корни Аналогично, полином с корнем будет также иметь корни и, наконец, полином с корнем будет также иметь корень Поэтому

Полином имеет степень 10, длина кода равна и он содержит информационных битов.

Теперь мы подытожим простое правило кодирования и декодирования, соответствующее этому определению циклического кода.

Кодирование. Пусть — порождающий полином кода, и пусть — сообщение с информационными битами. Тогда это сообщение рассматривается как полином над GF(2) и кодируется как

Декодирование. Полученный вектор делим на [остаток от этого деления — это синдром вектора ]. Если в результате деления получен ненулевой остаток, то должна иметь место ошибка передачи. Чтобы распознать ошибку мы вычисляем произведение где — проверочный полином кода. В соответствии со сделанными ранее замечаниями

. Тогда, разделив произведение на получим полином ошибки Разделив на мы получаем переданное сообщение.

Пример. Пусть — порождающий полином кода (7,4), который мы рассматривали в предыдущем примере. Сообщение (1,1,1,0) кодируется как (1,0,0,0,1,1,0).

Предположим теперь, что получен вектор (с двумя ошибками); тогда, разделив на мы получим в остатке ; значит, при передаче произошла ошибка. Проверочным полиномом является равен . Итак, , и, разделив на мы получим . Таким образом, и, разделив полученное на мы получим переданный вектор (1,1,1,0).

Если имеется только одна ошибка передачи, то и мы исправляем i-й бит.

В общем случае если дгхг — порождающий полином кода, то полиномы являются кодовыми словами. Таким образом, строки следующей матрицы — это все кодовые слова:

Очевидно, что строки матрицы G линейно независимы и ее ранг равен , что совпадает с размерностью кода.

Мы придем к другому представлению циклического кода, если предположим, что полином принадлежит коду тогда и только тогда, когда элементы из поля будут его корнями. Тогда если то

для . Это можно также записать в виде произведения матриц

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

откуда мы делаем вывод, что проверочная матрица равна

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

а поскольку это пространство состоит в точности из тех полиномов, которые делятся на минимальный полином элемента где оно является идеалом. [Матричная форма легко получается, если заменить каждую степень элемента -столбцом, соответствующим его векторному представлению, как в табл. 3.3.1.] Поскольку размерность ортогонального пространства матрицы равна размерность пространства ее строк равна Отметим, что коэффициенты полиномов, представляющих кодовые слова, лежат в GF(2), в то время как элементы -находятся в Однако мы упомянули, что элементы поля можно рассматривать как векторы, имеющие компонент из GF(2), следовательно, размерность пространства строк матрицы над GF(2) равна . См. также приведенный ниже пример.

Если имеют одинаковые минимальные полиномы, то их ортогональные пространства совпадают, и, следовательно, пространства строк соответствующих матриц вида рассматриваемых как пространства над GF(2), также совпадают. Итак, для

того чтобы построить матрицу Н, нам нужно знать только один корень для каждого неприводимого сомножителя полинома

Пример. Мы хотим построить двоичный циклический код, для которого полином будет кодовым словом тогда и только тогда, когда его корнями являются элементы где — примитивный элемент поля . Минимальный полином элемента имеет также корни . Аналогично, минимальный полином элемента имеет корни минимальный полином элемента имеет также корень Таким образом,

и достаточно проверить, что каждый полином имеет корни а, Значит, искомый код — это ортогональное пространство матрицы

или, принимая во внимание векторное представление каждой степени элемента а (см. табл. 3.3.1), матрице Н можно придать вид

Разложение полинома на неприводимые множители имеет вид

и легко убедиться, что , где этом месте читатель должен обратить внимание на потребность эффективной процедуры разложения на множители полиномов с коэффициентами из конечного поля; эта тема обсуждается в гл. 6.)

Покажем теперь, что -коды Хэмминга, с которыми мы уже сталкивались, эквивалентны циклическим кодам.

Пусть — примитивный элемент поля и рассмотрим код с проверочной матрицей

Если степени элемента а представлены векторами (столбцами) длины над GF(2), то каждый ненулевой вектор длины m появляется ровно один раз как столбец матрицы Н. Таким образом, Н действительно описывает код Хэмминга. Его можно описать как циклический код, если мы скажем, что полином — кодовое слово тогда и только тогда, когда является корнем полинома Минимальный полином элемента является с-примитивным полиномом, следовательно, порождающий полином с-примитивен. Аналогично, каждый код, порожденный с-примитивным полиномом, является кодом Хэмминга.

Пример. Пусть и пусть — корень с-примитивного полинома Тогда проверочная матрица -кода Хэмминга, порожденного этим полиномом, имеет вид

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

образом, либо источник должен иметь возможность приостанавливать и повторно начинать передачу, либо должен использоваться временной буфер.

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

Кодирование циклического -кода, порожденного полиномом достигается с помощью схемы, изображенной на рис. 4.1.5, где используется -разрядный регистр; соединения регистра соответствуют полиному Информационные биты первоначально размещаются в к элементах памяти, а затем происходят циклические сдвиги. Первые к битов, выходящие из регистра, являются информационными, а остальные — проверочными для кодового слова из битов. (См. упр. 5 к этому разделу.)

Рис. 4.1.5. Кодирование циклического (-кода.

При использовании -разрядного регистра процедура кодирования выглядит следующим образом: кодовое слово может быть образовано умножением произвольного полинома степени не более коэффициенты которого — информационные биты, на полином который порождает код. Это может быть достигнуто использованием либо схемы, показанной на рис. 3.3.2, либо схемы на рис. 3.3.3. Информационные биты теперь меняются и могут быть получены из кодового слова делением соответствующего полинома на для этой цели может использоваться схема рис. 3.3.6. (См. упр. 6 к этому разделу.)

Процедура обнаружения ошибок для циклических кодов также совсем проста. Если — принятый полином, то достаточно

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

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

Теорема 4.1.22. В циклическом (-коде никакое кодовое слово не является пакетом ошибок длины не более . Таким образом, каждый циклический код может обнаруживать любой пакет ошибок длины, не превосходящей .

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

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

Теорема 4.1.23. Пусть — порождающий полином двоичного циклического кода длины , и пусть — корни полинома где — элемент порядка в некотором поле Галуа. Тогда кодовое расстояние этого кода больше, чем максимальное число последовательных целых чисел в множестве

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

Теперь, если мы докажем, что никакая линейная комбинация столбцов подматрицы

не обращается в нуль, то, очевидно, то же самое будет верно для столбцов матрицы Н, и по теореме 4.1.12 кодовое расстояние будет не меньше, чем

Тот факт, что выписаннал матрица S обладает нужным свойством, может быть доказан демонстрацией того, что определитель матрицы, полученной взятием любого множества столбцов матрицы S, отличен от нуля. Действительно, такой определитель может быть записан в виде

который, в свою очередь, может быть записан как

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

Определение 4.1.24. Пусть а — элемент поля . Тогда для данных то и код, порожденный полиномом является БЧХ-кодом в том и только том случае, когда минимальный полином над GF(2), корнями которого являются элементы

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

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

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

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

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

Теорема 4.1.25. Для любой пары положительных целых чисел существует двоичный БЧХ-код длины который исправляет все комбинации не более ошибок и имеет не больше, чем проверочных битов.

Пример. Рассмотрим поле и пусть — примитивный элемент этого поля, т.е. Рассмотрим, кроме того, БЧХ-код, состоящий из всех полиномов, имеющих корни а и Минимальные полиномы для а и суть соответственно. Оба этих полинома делят Циклический код С над GF(2) определяется порождающим полиномом степени 8 и проверочной матрицей

Из сказанного выше мы знаем, что кодовое расстояние этого кода 5 (в этом случае это подразумевает, что код монсет исправлять до двух ошибок; С — это (-код. Далее тогда и только тогда, когда ), синдром вектора v, равен 0, т.е. тогда и только тогда, когда или тогда и только тогда, когда где — компоненты синдрома вектора v относительно H. Если мы используем векторное представление для элементов поля то получим (-матрицу Н, подобную которой мы видели в предыдущем примере.

Предположим, что принятый вектор — вектор с самое большее двумя ошибками. Пусть — вектор ошибок. Мы имеем

Кроме того, если то и после некоторых манипуляций мы видим, что если встретились две ошибки, то — два корня в полинома локаторов ошибок

Если случилась только одна ошибка, то Следовательно, . И наконец, если ошибок не было, то

Из приведенного примера мы видим, что, для того чтобы иметь возможность исправлять две ошибки, мы должны специальным образом удвоить число строк матрицы Н, используемой в кодах Хэмминга. В литературе имеются более общие процедуры декодирования для исправления любого числа ошибок; см. например, (Berlekamp, 1968; Childs, 1979; Mackiw, 1985; MacWilliams, 1977; Peterson и др., 1972).