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

Предположим, что передавая кодовый вектор {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 от нечетных степеней элементов Х₁, Х_2...... 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.

---

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