Циклические коды БЧХ

Коды Боуза—Чоудхури—Хоквингема(БЧХ-коды) представ­ляют собой большой класс циклических кодов, исправляющих независимые ошибки кратности 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 и менее.

Дата добавления: 2015-07-16