Кодированиеи декодирование кодов PC

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

Рис. 6.1. Кодирующее устройство кода Рида—Соломона с образую­щим многочленом g(х)=(х+ 1 )(х+ a) (x+a²) (x+a³) в поле GF(2³)

Пример построения кодирующего устройства кода PC пред­ставлен на рис. 6.1. Кодер содержит r = 4 ячеек памяти, спо­собных хранить элементы поля GF (2^т), представленные двоич­ными векторами длины т = 3. Таким образом, каждая ячейка памяти может быть построена из т триггеров. Кроме того, ко­дер содержит по r = 4 сумматоров и умножителей на фиксиро­ванные элементы поля GF (2³). При этом каждый сумматор со­стоит из двухвходовых сумматоров по модулю два, на входы которых поступают параллельно m-элементные двоичные ком­бинации.

Умножители на фиксированные элементы аⁱ поля GF (2^т) реализуются как умножители на матрицу Fⁱ при помощи комбинаторных схем или ПЗУ с т входами и т выходами. Прак­тическая реализация умножения приведена в [6].

Алгоритм работы кодера ничем не отличается от описанного ранее для циклического кода, исправляющего однократные ошибки (рис. 3.1).

Декодирование кодов PC включает более сложные процеду­ры. Рассмотрим наиболее широко применяемый принцип алге­браического декодирования.

Пусть некоторая разрешенная кодовая комбинация длины п представлена в общем виде полиномом f (х) (6.1).

Коды PC обладают всеми свойствами циклических кодов, одним из которых является делимость полинома f (х) на обра­зующий полином g (х) без остатка. Отсюда следует, что корни 1, а, а²,..., а^г-1 полинома g (x) являются также корнями по­линомов f (х), т. е. имеют место равенства:

Систему уравнений (6.3) можно записать в виде

{f}H^T=0, (6.4)

где {f} = {с₀ c₁ c₂…c_n-1}, с_i€GF (2^m), а матрица H является проверочной матрицей кода PC и имеет вид:

Комбинация, поступающая на вход декодера, представленная в виде полинома h (х)= h₀ + h₁x +…+h_n-1x^n-1, равна сум­ме h (х) = f (x)+e(x),, где f (х) —разрешенная кодовая ком­бинация и е (х) — полином ошибок, равный е (х) = e₀+e₁x+e₂x²+…+e_n-1x^n-1, где e_i €GF(2^m). Таким образом, h_i=c_i+e(mod 2), т. е. h_i—это сумма по mod 2 двоичных m- элементныхкомбинаций, соответствующих элементам с_i и e_i. В декодере осуществляется умножение входного вектора {h} = {h₀ h₁h₂... h_n-1} на проверочную матрицу Н, в резуль­тате чего, с учетом (6.4), получим

={e}H^T={S_oS₁S₂... S_r-1}. (6.6)

Таким образом, первым этапом декодирования является получение синдромов S_o, S₁,…S_r-1 значения которых определя­ются выражениями:

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

Рассмотрим теперь процедуру исправления ошибок. Пусть требуется построить код PC, исправляющий ошибки кратности t и менее. Очевидно в этом случае минимальное кодовое рас­стояние должно быть равно d_min=2t+ 1. Следовательно, для кодов PC с исправлением i и менее ошибок степень образую­щего полинома g (х) будет равна r= 2t.

Полином t-кратной ошибки можно записать: е (х) = е_i1x^t1+…+e_itx^it, где коэффициенты ошибок e_i1, e_i2,…,e_it отличны от нуля и принадлежат полю GF (2^m). На первом этапе декодирования в результате умножения вектора {h} или, что то же самое, вектора ошибок {е} на проверочную матрицу H^T будут получены синдромы

S,=e(a^j) =ΣY_iX_t^j; j=0,1,…,(r-1), (6.8)

где величины Х₁ =aⁱ¹, X₂=aⁱ²,…,X_t=a^it,, указывающие место расположения ошибок, называют локаторами ошибок; а величины Y₁ = еⁱ¹, Y₂=eⁱ², …,Y_t=e^it — значения самих ошибок. Таким образом, для исправления t ошибок необходимо на втором этапе декодирования найти значения tпар (X_t, У,-) путем решения системы из It уравнений (6.8), в которых изве­стными величинами являются полученные ранее синдромы.

Как и в двоичных кодах БЧХ, будем считать, что искомые ошибочные позиции Х₁, Х₂..., X_t являются корнями некото­рого многочлена локаторов ошибок

Ψ(X)=Xt+p₁X^t-1+p₂X^t-2+…+p_t-1X+p_t (6-9)

Очевидно, что при X = X_t имеем

Ψ(X_i)=X^t_i+p₁X^t-1_t+p₂X_i^t-2+…+p_t-1X_i+p_t=0 (6.10)

Умножив уравнение (6.10) на Y_tX{, получим

Составив такие уравнения для всех локаторов ошибок Х\, Х₂,..., X_t и просуммировав их, получим t уравнений вида

гдеj = 0, 1,..., (t—1).

Решив эту систему уравнений относительно неизвестных р₁, р₂,..., p_t и подставив их в многочлен локаторов ошибок (6.9), определим ошибочные позиции Х\, Х₂,..., X_f, используя про­цедуру Ченя и уравнения (6.10). Подставим найденные значе­ния локаторов ошибок Х_i в уравнения (6.8) и решим эту си­стему относительно неизвестных значений ошибок Y₁, Y₂,...,• Y_t Рассмотрим пример алгебраического декодирования кода PC с образующим полиномом g (х) = (х +1 )(x+a)(х +α² ) (х +а³), где а — примитивный элемент поля GF(2³), образован­ного полиномом Р (х) = 1+x+x³. Полином g (х) образует си­стематический (п, k) = (7, 3) код Рида—Соломона с d_mln = = 5 (рис. 6.1). Легко проверить, что исходной комбинации, представленной, например полиномом φ (х) = а + а³х + х², со­ответствует закодированная комбинация, выраженная полино­мом

где п — k = 4 младших разрядов являются проверочными эле­ментами кода.

Рассмотрим пример исправления двух ошибок, полином ко­торых имеет вид е (х) = а⁵х³ +ax⁵. Здесь, в соответствии с вве­денными выше обозначениями е (х) = Y₁X₁ + Y₂X₂, имеем: Х₁ = х³ и Х₂ = х⁵ — места расположения ошибок (локаторы); Y₁ = а⁵ и У₂ = а — соответствующие значения ошибок.

Для определения синдромов воспользуемся формулой (6.8), при этом получим:

На первом этапе декодирования необходимо определить син­дромы S_o, Si, S₂, S₃, которые получаются путем умножения входной комбинации, соответствующей полиному h (x) =f(x)+е(х), на проверочную матрицу Н, имеющую вид:

Рис. 6.2. Схема реализации блока вычисления

синдромов S_o. 5,, S₂, S-> для многочлена Р(х) =

= 1 + х + X^s

Практическая реализация блока вычисления синдромов для рассматриваемого примера представлена на рис. 6.2, где пред­ставлены четыре регистра с сумматорами по модулю два, пред­назначенные соответственно для определения синдромов. Верх­ний регистр реализует суммирование по модулю два всех эле­ментов принятойкомбинации, формируя синдром S_o. Осталь­ные синдромы формируются тремя другими регистрами по схе­ме Горнера. Рассмотрим подробнее формирование синдрома S_t. Пусть принятый полином имеет вид:

Тогда синдром Si будет получен путем умножения входного вектора {h₀ h₁ h₂ h₃ h₄ h₅ h₆} на транспорированную строку про­верочной матрицы [1 а а² а³ а⁴ а⁵ а⁶], т. е.

Очевидно, что это же выражение может быть записано по схе­ме Горнера следующим образом:

Аналогично могут быть записаны выражения для S₂ и 5₃:

Таким образом, в процессе получения синдрома S1, реализуется умножение на а, синдрома S₂ — на элемент а² и синдрома S₃ — на элемент а³. Как показано в п. 6.4.1 умножению входного вектора на постоянные элементы поля а, а², а³ соответствует умножение на матрицы F, F², F³, которые для полинома Р(х) = 1 + х + х³ имеют вид:

Как следует из (6.9), при исправлении t = 2 ошибок искомые локаторы ошибок Х₁ и Х₂ являются корнями многочлена ψ (X) = X² + Р₁Х + Р₂ Для определения коэффициентов p₁ и р₂ многочлена локаторов ошибок составим в соответствии с (6.11) следующую систему уравнений:

Решая полученную систему уравнений относительно неизвестных p₁ и p₂, запишем их выражениями в общем виде:

при условии, что S²₁+ S₀S₂≠ 0.

Подставив в эти выражения значения синдромов, получим ре­шения: p₁ = а² и р₂ = а. Таким образом, многочлен локаторов ошибок будет иметь следующий вид:

Ψ(x)=X²+α²X+α. (6.15)

Корни этого многочлена, являющиеся локаторами ошибок X₁ и Х₂, могут быть практически найдены на основе процедуры Ченя [6], суть которой сводится не к явному решению уравнения ψ(аⁱ) = 0, а к последовательной подстановке элементов поля a ^-1, а^-2, а^-3,... в многочлен ψ (X) вместо переменной X. При этом локаторами ошибок Х₁ и Х₂ будут те элементы поля GF (2³), для которых W (Х₁) = W (Х₂) = 0. Подставив все нену­левые элементы поля GF (2³) в ψ (X), получим:

ψ(a^-2)= ψ(a⁵)=0; ψ (a^-4)= ψ (a³)=0

т. е. ошибки возникли в четвертой с^з и шестой с⁵, позициях, ко­да и локаторы ошибок равны Х₁ = а³, X₂ = а⁵.

Удобство процедуры Ченя заключается в том, что вычисле­ние локаторов ошибок производится параллельно с выводом принятой комбинации (h_o h₁ h₂ h₃ h₄ h₅ h₆) из буферного нако­пителя. В частности, при выводе элемента h₆ вычисляется зна­чение локатора ошибок ψ (a^-1) = ψ(а⁶) при выводе h₅ — вы­числяется ψ(а^-2) = ψ(а⁵) и т. д. В те моменты, когда много­член локаторов ошибок становится равным нулю, т. е. ψ (а^j) = 0, из буферного накопителя выводится ошибочный элемент кода h_j и к нему необходимо добавить вычисленное значение ошибки Y_j. При этом будет получен правильный элемент c _j = h_j +У_j, т. е. происходит исправление ошибок.

Рассмотрим теперь практическую реализацию блока вычис­ления локаторов ошибок. Заметим при этом, что если на i-м шаге было вычислено значение многочлена локаторов ошибок

(6.9) при Х = а^-I; т. е. ψ(a^-i)= (a^-i)^t +p₁(a^-i)^t-1+ … +p_t-1a^-i+p_t,

то на (i+ 1)-м шаге будет вычислено следую­щее значение, а именно

ψ (a^-i-1)=a^-(i+1)t+p₁a^-(i+1)t+p₁a^-(i+1)(t-1)+…+p_t-1a^(-i+1)+p_t.

Если последнее выражение записать следующим образом:

то становится очевидным, что первый член многочлена ψ(a^-i) умножен на а^-t, второй — на а^(t-1), предпоследний — на а^-1, а последний остается без изменения. Отсюда следует, что блок вычисления локаторов ошибок может быть реализован с по­мощью t+ 1 регистров, первый из которых (R₁) реализует ум­ножение содержимого на F^-t, второй регистр (R₂) — умноже­ние на F^-(t+1) и т. д. Последний регистр не меняет своего зна­чения.

В исходном состоянии в регистры R1, R2,... записываются коэффициенты многочлена ψ(x)соответственно 1, р₁,... p_t. Схема, реализующая процедуру Ченя вычисления локаторов ошибок в общем виде, представлена на рис. 6.3.

Для рассматриваемого примера кода (7, 3) с исправлением двухкратных ошибок в поле GF(2³) с примитивным полиномом Р (х) = 1 + х + x³ многочлен ψ(x)имеет вид (6.15) с коэффи­циентами р₁ = а² и p₂ = а. Для данного полинома Р (х) мат-рицы F^{- l} и F^-2 являются обратными по отношению к матрицам F и F² иимеют следующий вид:

Рис. 6.3. Схема вычисления локаторов ошибок

В результате умножения некоторого вектора (а₀, a₁, а₂) на эти матрицы будем иметь

(а₀, а₁, a₂)F^-1 = [(a₀+a_l), а₂, а_о];

(а_а а₁, a₂)F^-2=[(а_о+а₁+а₂), а₀, (a_o+a₁)].

Схема вычисления локаторов ошибок X₁ и Х₂ для данного при­мера приведена на рис. 6.4. На рисунке верхний регистр реализует умножение на F^-2, средний регистр — на F^-1, а нижний регистр представляет собой память, где запоминается коэффициент р₂ многочлена ψ(x).

Рассмотрим теперь один из алгоритмов исправления оши­бок. Как было показано, дешифратор нуля в схеме вычисления локаторов ошибок (рис. 6.4) срабатывает в моменты вывода ошибочных позиций X₁ и Х₂ из буферного накопителя. Исполь­зуя этот факт, легко определить значения X₁ и Х₂, запустив с началом вывода кодовой комбинации из буферного накопите­ля генератор обратных элементов поля Галуа а^-(n-j), где п — = 2^т — 1. При первом срабатывании дешифратора нуля

(рис. 6.4), т. е. когда из буфера выводится первый ошибочный элемент, генератор будет формировать элемент Х₂ = a^j. Для исправления этого ошибочного элемента к нему необходимо до­бавить по модулю два значение ошибки Y₂, которое можно лег­ко вычислить, зная значение Х₂. Действительно, решая уравне­ния (6.12) для синдромов S_o и S₁ относительно Yi и Y₂, нахо­дим, что

■

Рис. 6.4. Схема вычисления локаторов ошибок для многочлена ψ(x)= X² + p₁X + р_г, где p₁=a², p₂=a

при этом учтем, что сумма (X₁+X₂) была вычислена раньше как коэффициент р₁ многочлена локаторов ошибок по (6.14). Определив Y₁ и учитывая выражение для синдрома S_o, нахо­дим, что Y₂ = S_o + Y₁

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

то, учитывая (6.16), находим значения ошибок:

Y₁= (a⁵+a⁶a⁵)/a²=a⁵, Y₂=S₀+Y₁=a⁶+a⁵=a.

Схема алгоритма декодирования в общем виде для кода Рида—Соломона, исправляющего двухкратные ошибки, пред­ставлена на рис. 6.5.

Рассмотренный алгоритм является классическим алгоритмом алгебраического декодирования кодов Рида-Соломона. Вместе с тем существуют и другие алгоритмы алгебраического декодирования. В частности в [4] предложен более простой в реализации алгоритм исправления двухкратных ошибок кодами Рида-Соломона. Другие обобщенные алгоритмы декодирования кодов Рида-Соломона рассмотрены в [2].

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