Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Поля Галуа и их свойства | Сложение многочленов | Умножение многочленов | Деление многочленов | Реализация операций умножения и деления многочленов в поле двоичных чисел | Матричное представление циклических кодов | Принципы обнаружения и исправления ошибок циклическими кодами | ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ПАЧКИ ОШИБОК (КОДЫ ФАЙРА) | ЦИКЛИЧЕСКИЕ КОДЫ БЧХ | Принципы исправления ошибок кодами БЧХ |


Читайте также:
  1. I. АЛГЕБРАИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ЦИКЛИЧЕСКИХ КОДОВ
  2. III. Регистры и уровни рекламных кодов
  3. Артикуляция визуальных кодов
  4. Вы получаете космические энергии с целью восстановления функционирования особых кодов сознания в человеческой форме.
  5. Вывод ASCII кодов на ассемблере.
  6. Декодирование циклических кодов
  7. Использование кодов Рида—Соломона для исправления стираний

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

 

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

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

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

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

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

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

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


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

{f}HT=0, (6.4)

где {f} = 0 c1 c2…cn-1}, сi€GF (2m), а матрица H является проверочной матрицей кода PC и имеет вид:

 

 

Комбинация, поступающая на вход декодера, представленная в виде полинома h (х)= h0 + h1x +…+hn-1xn-1, равна сум­ме h (х) = f (x)+e(x),, где f (х) —разрешенная кодовая ком­бинация и е (х) — полином ошибок, равный е (х) = e0+e1x+e2x2+…+en-1xn-1, где ei €GF(2m). Таким образом, hi=ci+e(mod 2), т. е. hi—это сумма по mod 2 двоичных m- элементныхкомбинаций, соответствующих элементам сi и ei. В декодере осуществляется умножение входного вектора {h} = {h0 h1h2... hn-1} на проверочную матрицу Н, в резуль­тате чего, с учетом (6.4), получим

={e}HT={SoS1S2... Sr-1}. (6.6)

 

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



 


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

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

Полином t-кратной ошибки можно записать: е (х) = еi1xt1+…+eitxit, где коэффициенты ошибок ei1, ei2,…,eit отличны от нуля и принадлежат полю GF (2m). На первом этапе декодирования в результате умножения вектора {h} или, что то же самое, вектора ошибок {е} на проверочную матрицу HT будут получены синдромы

S,=e(aj) =ΣYiXtj; j=0,1,…,(r-1), (6.8)


где величины Х1 =ai1, X2=ai2,…,Xt=ait,, указывающие место расположения ошибок, называют локаторами ошибок; а величины Y1 = еi1, Y2=ei2, …,Yt=eit — значения самих ошибок. Таким образом, для исправления t ошибок необходимо на втором этапе декодирования найти значения tпар (Xt, У,-) путем решения системы из It уравнений (6.8), в которых изве­стными величинами являются полученные ранее синдромы.

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

Ψ(X)=Xt+p1Xt-1+p2Xt-2+…+pt-1X+pt (6-9)

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

Ψ(Xi)=Xti+p1Xt-1t+p2Xit-2+…+pt-1Xi+pt=0 (6.10)



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

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

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

Решив эту систему уравнений относительно неизвестных р1, р2,..., pt и подставив их в многочлен локаторов ошибок (6.9), определим ошибочные позиции Х\, Х2,..., Xf, используя про­цедуру Ченя и уравнения (6.10). Подставим найденные значе­ния локаторов ошибок Хi в уравнения (6.8) и решим эту си­стему относительно неизвестных значений ошибок Y1, Y2,...,• Yt Рассмотрим пример алгебраического декодирования кода PC с образующим полиномом g (х) = (х +1 )(x+a)(х2 ) (х3), где а — примитивный элемент поля GF(23), образован­ного полиномом Р (х) = 1+x+x3. Полином g (х) образует си­стематический (п, k) = (7, 3) код Рида—Соломона с dmln = = 5 (рис. 6.1). Легко проверить, что исходной комбинации, представленной, например полиномом φ (х) = а + а3х + х2, со­ответствует закодированная комбинация, выраженная полино­мом

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

Рассмотрим пример исправления двух ошибок, полином ко­торых имеет вид е (х) = а5х3 +ax5. Здесь, в соответствии с вве­денными выше обозначениями е (х) = Y1X1 + Y2X2, имеем: Х1 = х3 и Х2 = х5 — места расположения ошибок (локаторы); Y1 = а5 и У2 = а — соответствующие значения ошибок.


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


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


 

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

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

= 1 + х + Xs

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

 

 

Тогда синдром Si будет получен путем умножения входного вектора {h0 h1 h2 h3 h4 h5 h6} на транспорированную строку про­верочной матрицы [1 а а2 а3 а4 а5 а6], т. е.

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



 


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



 


Таким образом, в процессе получения синдрома S1, реализуется умножение на а, синдрома S2 — на элемент а2 и синдрома S3 — на элемент а3. Как показано в п. 6.4.1 умножению входного вектора на постоянные элементы поля а, а2, а3 соответствует умножение на матрицы F, F2, F3, которые для полинома Р(х) = 1 + х + х3 имеют вид:



 


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

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


 


при условии, что S21+ S0S2 0.

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

Ψ(x)=X22X+α. (6.15)

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

ψ(a-2)= ψ(a5)=0; ψ (a-4)= ψ (a3)=0

т. е. ошибки возникли в четвертой сз и шестой с5, позициях, ко­да и локаторы ошибок равны Х1 = а3, X2 = а5.

Удобство процедуры Ченя заключается в том, что вычисле­ние локаторов ошибок производится параллельно с выводом принятой комбинации (ho h1 h2 h3 h4 h5 h6) из буферного нако­пителя. В частности, при выводе элемента h6 вычисляется зна­чение локатора ошибок ψ (a-1) = ψ(а6) при выводе h5 — вы­числяется ψ(а-2) = ψ(а5) и т. д. В те моменты, когда много­член локаторов ошибок становится равным нулю, т. е. ψ j) = 0, из буферного накопителя выводится ошибочный элемент кода hj и к нему необходимо добавить вычисленное значение ошибки Yj. При этом будет получен правильный элемент c j = hjj, т. е. происходит исправление ошибок.

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

(6.9) при Х = а-I; т. е. ψ(a-i)= (a-i)t +p1(a-i)t-1+ … +pt-1a-i+pt,

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

ψ (a-i-1)=a-(i+1)t+p1a-(i+1)t+p1a-(i+1)(t-1)+…+pt-1a(-i+1)+pt.

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

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

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

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



 

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

В результате умножения некоторого вектора 0, a1, а2) на эти матрицы будем иметь

0, а1, a2)F-1 = [(a0+al), а2, ао];

а а1, a2)F-2=[(ао12), а0, (ao+a1)].

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

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

(рис. 6.4), т. е. когда из буфера выводится первый ошибочный элемент, генератор будет формировать элемент Х2 = aj. Для исправления этого ошибочного элемента к нему необходимо до­бавить по модулю два значение ошибки Y2, которое можно лег­ко вычислить, зная значение Х2. Действительно, решая уравне­ния (6.12) для синдромов So и S1 относительно Yi и Y2, нахо­дим, что

Рис. 6.4. Схема вычисления локаторов ошибок для многочлена ψ(x)= X2 + p1X + рг, где p1=a2, p2=a

при этом учтем, что сумма (X1+X2) была вычислена раньше как коэффициент р1 многочлена локаторов ошибок по (6.14). Определив Y1 и учитывая выражение для синдрома So, нахо­дим, что Y2 = So + Y1

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

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

Y1= (a5+a6a5)/a2=a5, Y2=S0+Y1=a6+a5=a.

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



 


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

 


Дата добавления: 2015-07-16; просмотров: 154 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
ЦИКЛИЧЕСКИЕ КОДЫ РИДА—СОЛОМОНА| Построение кодов Рида-Соломона

mybiblioteka.su - 2015-2024 год. (0.016 сек.)