5. Циклические коды бчх

Коды Боуза—Чоудхури—Хоквингема (БЧХ-коды) представ­ляют собой большой класс циклических кодов, исправляющих независимые ошибки кратности t и менее. Для кодов БЧХ ха­рактерны все основные свойства циклических кодов. Чаще все­го коды БЧХ описывают с помощью корней порождающего мно­гочлена Р (х) степени 2t. В качестве корней Р (х) выбирают 2t последовательных элементов а^j,a^j+1 ..., а^j+2i-1поля Галуа GF (р'^п), где 1≤ j≤p^m— 1. Если при этом элемент а является примитивным (первообразным) в поле GF(p^m), то такой код БЧХ называют примитивным с длиной кодовой комбинации п=р^т—1 над полем GF (р). Для двоичных примитивных ко­дов БЧХ п = 2ⁿ — 1 над полем GF (2). В случае, если ряд кор­ней многочлена Р(х) для кода БЧХ начинается с j=1, т. е. а, а², .... а^2t, то такой код называют кодом БЧХ в узком смысле.

Код БЧХ, у которого корень а не является примитивным элементом поля GF (р^m), т. е. имеет порядок d < р^т —1, на­зывают непримитивным с длиной комбинации п =d.

Пусть а^j-элемент расширения простого числового поля. Тогда по определению, данному в [7], некоторый нормирован­ный многочлен т(х) наименьшей степени, для которого т(а^j ) = 0, называют минимальной функцией для аⁱ.

Отметим, что минимальные функции m(х) являются непри-водимыми многочленами. Если предположить, что каждому из корней аⁱ производящего многочлена Р (х) соответствует своя минимальная функция т_i (х), то производящий многочлен Р (х) должен быть наименьшим общим кратным всех минимальных функций, т. е.

P(x)=НОК[m₁(x),m₂(x), ... m_2t(x)]. (51)

Таким образом, вектор, представленный многочленом f (x),будет кодовым тогда и только тогда, когда он делится без ос­татка как на каждую из минимальных функций т₁ (х), m₂(x), ..., т_2t (х), так и на их наименьшее общее кратное.

Тогда для любого из корней а, а², ....a^2t справедливо урав­нение f (аⁱ) = с₀ + с₁ аⁱ +с₂(аⁱ )²+…c_n-1 (aⁱ)^n-1 = 0, которое можно записать в виде произведения двух матриц (c_oc₁c₂…c_n-1)*[laⁱ(aⁱ)²…(aⁱ)^n-1]^T=0. Но так как корнями f(х) должны быть все элементы a, a² …,a^2t, то можно сделать вывод, что вектор (c₀c₁…c_n-1_) будет кодовым тогда и только тогда, когда он принадлежит нулевому прост­ранству матрицы

Может оказаться, что элементы аⁱ и а^j из совокупности а, а², ..., а^2t соответствуют одной и той же минимальной функ­ции, т. е. т_i (х) = m_j(х). Вследствие того, что производящий многочлен Р(х) равен наименьшему общему кратному всех ми­нимальных функций m_j(х), в качестве сомножителя в разложе­нии многочлена Р(х) следует взять только одну из нескольких равных между собой минимальных функций.

Из свойства 1.6 полей следует, что если аⁱ корень какой-либо минимальной неприводимой по модулю 2 функции m_i (х)степени к, то остальными корнями будут (аⁱ)²,((аⁱ)²)²,...,(aⁱ)^{2^(k-1)}.Следовательно, в разложении многочлена Р (х) каждая из различных минимальных функций m_i (х) должна вхо­дить только один раз, а для построения матрицы (5.2) нужно использовать только по одному корню каждой из минимальных функций, входящих в разложение многочлена Р (х). Таким об­разом, если в качестве совокупности корней многочлена Р (х) выбраны элементы поля Галуа GF (2^m) а, а², а³, ..., а^2t, то при построении матрицы Н должны быть использованы только нечетные степени а, а³, ..., а^2t-1, а многочлен Р (х) будет иметь вид

P(x)=m₁(x)m₃(x) ... m_2t-1(x). (5.3)

Рассмотрим следующий пример.

Пример 5.1. Пусть имеем двоичный циклический код БЧХ. к которому вектор {f (х)} будет принадлежать только тогда, когда элементы а, a², а³, а⁴, а⁵, а⁶ будут корнями многочлена f (х). Кроме того, предполагается, что a — примитивный эле­мент поля Галуа GF (2⁴). Тогда а¹⁵ = 1 и т_i (х) обозначает минимальную функцию для а^j .

В соответствие со свойством 1.6 элементы a, а², а⁴ и а⁸ — корни одной и той же минимальной функции четвертой степе­ни, следовательно, m₁(х) = т₂ (х)= т₄ (х) = т₈ (х). Анало­гично, а³, а⁶, а¹² и а²⁴ = а⁹ — корни минимальной функции чет­вертой степени и m₃ (х) = т₆ (х) = m₉ (х) = т₁₂(х), а элемен­ты a⁵ и а¹⁰ являются корнями минимальной функции второй степени и, следовательно, т₅ (х)=т₁₀(х). Отсюда, Р (х) яв­ляется многочленом

P(x)= m_l(x)m₃(x)m₅(x) (5.4)

степень которого равна 10.

Таким образом, к искомому циклическому коду БЧХ будет принадлежать любой вектор {f (х)}, если f (х) делится на Р(х). В то же время циклический код будет нулевым пространством матрицы

Так как а^j является элементом поля GF (2^т ) и представляет собой вектор из т двоичных элементов 0 и I, то матрица H^T имеет размерность п * mt.

Из свойства 2.2 следует, что многочлен Р (х) является де­лителем многочлена F (х) = хⁿ — 1, где п = 2^m—1. В то же время, многочлен Р (х) для кодов БЧХ равен произведению ми­нимальных функций. Следовательно, любая из минимальных функций, входящих в разложение многочлена Р(х), должна быть делителем функции F (х) = хⁿ— 1 = х^{2^m-1}— 1. При этом, как следует из высшей алгебры [4, 7], степень каждой мини­мальной функции не может быть больше т. А так как таких функций t, то степень многочлена Р (х) не превосходит mt. Отсюда каждая комбинация циклического примитивного кода БЧХ при длине, равной n = 2^m—1, имеет число информационных разрядов, равное k≥2^m— 1—mt.

Рассмотрим конкретный пример построения циклического кода БЧХ.

Пример 5.2. Построить двоичный примитивный циклический код БЧХ для т = 4 и t= 3.

В этом случае длина кодовой комбинации равна п = 2^m— 1 = 15, а вектор {f (х)} будет принадлежать этому цикличе­скому коду, если элементы поля GF (2⁴) а, a², ..., а⁶ будут корнями многочлена f(х). Кроме того, отметим, что а — при­митивный элемент поля, а минимальной функцией для него пусть будет примитивный неприводимый многочлен т₁ (х) = 1 +x+x⁴.

Как видим, этот пример является непосредственным про­должением примера 5.1, из которого следует, что производящий многочлен Р (х) имеет вид Р (х) = m₁(х) т₃ (х) т₅ (х), где т₁ (х) и m₃ (х) — минимальные многочлены четвертой степени, а т₅ (х) — минимальный многочлен второй степени, вследствие чего степень многочлена Р (х) равна 10. Кроме того, было по­казано, что матрица Н имеет вид (5.5).

Т ак как примитивный элемент а — корень минимального многочлена т_х(х)=1 + х + х⁴, то, подставив вместо каждого элемента матрицы H его значение из табл. 1.1, получим транс­понированную матрицу Н^Т;

В [7] показано, что m₃(x)=1+x+x²+x³+x⁴, m₅(x)=1+x+x², тогда степень многочлена P(x) равна 10, что не превышает mt.

В рассмотренном примере

Т огда производящая матрица G искомого систематического кода имеет вид :

Образованный таким образом циклический (n,k)=(15,5) код БЧХ позволяет исправить любую совокупность ошибок кратности t=3 и менее.

Принципы исправления ошибок кодами БЧХ

Предположим, что передавая кодовый вектор {f(x)}, представление которого в виде многочлена будет иметь вид: f(x)=c₀+c₁x+…+c_n-1x^n-1. Пусть далее вследствие ошибок вместо вектора {f(x)} принят вектор {f(x)+e(x)}= {f(x)}+ {e(x)}, где {e(x)}-вектор ошибок.

Обозначим принятый с ошибками вектор {f(x)+e(x)} через вектор {h(x)}=(h₀h₁h₂…h_n-1).Принятую комбинацию можно представить в виде многочлена степени n-1, т.е. h(x)=h₀+h₁x+h₂x²+…+h_n-1x^n-1. В результате умножения вектора {h(x)} на матрицу (5.2) получим вектор из t компонент [h(a), h(a³),…h(a^2t-1)],где h(a)=h₀+h₁a+h₂a²+…+h_n-1a^n-1; h(a³)=h₀+h₁a³+h₂(a³)²+…+h_n-1(a³)^n-1

И т.д.

В то же время {h(x)}= {f(x)+e(x)}, следовательно, h(x)= f(x)+e(x). Тогда h(aⁱ)=f(aⁱ)+e(aⁱ), где i=1,3,…,2t-1, но так как f(x) делится на P(x) без остатка, то f(a)=f(a³)=…=f(a^2t-1)≡0, так что h(aⁱ)≡e(aⁱ).

При умножении вектора {h(x)} на первый столбец матрицы H^T , образованной из (5.5), получаем элемент

Отсюда следует, что имеется взаимнооднозначное соответствие между элементами вектора ошибок и элементами поля GF(2^m). Каждому ошибочному элементу e_i соответствует элемент i-й строки (i=0,1,2,…,n-1) первого столбца транспонированной матрицы H^T, т.е. элемент поля aⁱ.

Предположим, что ошибки произошли на позициях i₁,i₂,…,i_t, для которых e_i=1, а для всех остальных e_j=0, тогда (5.8) может быть переписана следующим образом:

Обозначим каждый из элементов а^k через Х_k (k = 1, 2, ...i_t) и назовем их локаторами ошибок, тогда (5.9) может быть переписана так:

Умножив вектор {h(x)} на какой-либо другой j-й столбец матрицы H^Tполучим

h(a^j)=e(a^j)=(a^j)ⁱ¹+(a^j)ⁱ²+…+(a^j)^it=

где j= 1, 3, .... 2t— 1.

Выражения (5.11) представляют t симметрических функций Sj от нечетных степеней элементов Х₁, Х₂ X_t, которые

имеют вид

Функции Sj называют синдромами.

Таким образом, функции S_j дают t уравнений вида (5.12) с t неизвестными Х₁, Х₂..., X_t. Кроме того, из (5.12) можно найти также симметрические функции для четных j = 2, 4, .., 2t, т. е. можно получить дополнительно t уравнений вида (5.12) с теми же неизвестными. Действительно, учитывая свойство 1.4 для р = 2, получим

Решение указанных уравнений относительно Х_k определит номера ошибочных позиций. Поскольку имеется конечное число решений, то значения Х_k могут быть найдены путем подстано­вок в эти уравнения различных элементов поля GF (2^m). Но подстановка всех комбинаций no t из 2^m — 1 ненулевых эле­ментов поля требует большого числа вычислений.

Для кодов БЧХ имеются более эффективные алгебраические алгоритмы декодирования. Рассмотрим один из них.

Так как суммы j-x степеней элементов Х₁,Х₂, ..., X_t пред­ставляют собой симметрические функции Sj, то эти элементы могут рассматриваться [8] как корни некоторого многочлена степени t

X^t+p₁X^t-1+p₂X^t-2+…+p_t (5.I4)

разложение которого на линейные множители дает уравнение

(X-X₁)(Х-Х₂) ... (X-X_t)=0. (5.16)

Коэффициенты р₁, р₂, ..., р_t являются простейшими симмет­рическими функциями, которые связаны с симметрическими функциями Sj тождествами Ньютона [1, 7]:

S₃-p₁S₂+p₂S₁-3p₃=0

S₄-p₁S₃+p₂S₂-p₃S₁+4p₄=0 и т. д.

При операциях по модулю 2 тождества Ньютона выписываются по формуле

где δ = 0 при i—четном и δ=1- при нечетном.

С учетом последнего тождества Ньютона можно перепи­сать так:

S_t=p₁S_t-1+p₂S_t-2+…+p_t-1S₁+ δp_t

Если тождества (5.16) решить относительно простейших сим­метрических функций pi и найденные значения р_i, подставить в (5.14), то корни этого многочлена Х₁, Х₂, ..., X_t можно оп­ределить последовательной подстановкой в него каждого из п = 2^m — 1 элементов поля. Если подставленный вместо X эле­мент аⁱ не является корнем, то соответствующий символ век­тора {h (x)} принят правильно. Если же элемент aⁱ является корнем, то соответствующий i-й символ вектора {h (х)} принят ошибочным и должен быть исправлен.

Однако в силу зависимости (5.13) следует рассматривать не все тождества (5.16), а лишь те, которые определяют S_j для нечетных j, т. е.

S_t-1=p₁S_t-2+p₂S_t-3+…+p_t-2S₁+p_t-1 (при t —четном) или S_t=p₁S_t-1+p₂S_t-2+…p_t-1S₁+p_t (при t— нечетном). Отсюда видно, что имеется i/2 (при t—четном) или (t+1)/2 (при t — нечетном) уравнений, которых недостаточно для определения t неизвестных р₁, р₂, ..., р_i. Однако в резуль­тате умножения {h(x)}*H^T можно определить все симметриче­ские функции S₁, S₃,…,S_2t-1. Знание симметрических функ­ций Sj с нечетными значениями j' вплоть до 2t—1позволяет составить дополнительные уравнения, которые вместе с (5.17) дадут t независимых уравнений с t неизвестными р₁,р₂, .... р_t Эти уравнения можно уже решить относительно p_t.

Выше было показано, как составить тождества Ньютона, когда j при Sj принимает целые значения, не превосходя­щие t, т. е. степени многочлена (5.14). Можно показать, что аналогично можно составить тождества Ньютона для значений j > t.

Действительно, если обозначить многочлен (5.14) через ψ(X) и подставить вместо X какой-либо из корней Х₁, X₂ .... X_t, то получим уравнение

Умножение обоих частей уравнения (5.18) на X_i^c-t дает

Где c>t. Если теперь просуммируем (5.19) по всем корням, т.е.

То получим

Решаем уравнения (5.17) совместно с (5.22) относительно не­известных р_i Найденные значения р_i подставляем в (5.14) и, как было указано, последовательной подстановкой вместо X элементов поля GF (2^m) находим корни этого многочлена. Этим самым мы устанавливаем ошибочные позиции принятого век­тора {h (х)}.

Если произошло в действительности t — 1 ошибок, то один из корней Х₁, Х₂,…X_t должен быть равен нулю. Следова­тельно, при решении уравнений (5.17) и (5.22) мы должны по­лучить p_t =0. Если произошло t — 2 ошибки, то два корня рав­ны нулю и, следовательно, p_t= р_t-1= 0 и так далее.

Пример 5.3. Рассмотрим процесс исправления тройных оши­бок (t = 3) циклическим кодом БЧХ, построение которого рас­сматривалось в примере 5.2. Многочлен (5.14) для такого кода будет иметь вид Х³ + р₁Х² + р₂Х + р₃

На основании (5.17) и (5.22) составляем уравнения:

Сложение по модулю 2 соответствующих столбцов матрицы H^T(5.6) позволяет найти значения S₁,S₃, S₅. Кроме того, при операциях по модулю 2 S₂ = S₁², a S₄ = S₁⁴ Решая уравнения относительно р_t, находим [7]:

при условии, что S₁³+S₃≠0.

Рассмотрим случай, когда ошибки появляются на 2, 5 и 7-м местах, т.е. {e(x)}=(010010100000000), тогда {h(x)}H^T=(1011,1111,1000), т.е. S₁=(1011), S₃=(1111), S₅=(1000).

Теперь найдем S₂ и S₄, обращаясь к табл. 1.1,

По формулам (5.24) находим p₁=S₁=a¹³,

Теперь путем подстановки элементов поля в уравнение X³+ + а¹³X²+ а⁹X +a¹¹= 0 находим, что корни этого уравнения бу­дут а, а⁴ а⁶. Следовательно, в принятом векторе {h (x)} ошибки находятся на 2, 5 и 7-м местах. Если произошла только одна ошибка, то р₂ = р₃ = 0, а из уравнений (5.23) p_i=S₁. Следовательно, номер ошибочной позиции можно определить, решая, уравнение X +р₁= 0.