Главная страница

Сверточные коды. 4 Дисер с 15 СК и Мягкое дек с 55. Программноаппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов рида соломона в адаптивных системах обмена данными


Скачать 5.5 Mb.
НазваниеПрограммноаппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов рида соломона в адаптивных системах обмена данными
АнкорСверточные коды
Дата09.03.2020
Размер5.5 Mb.
Формат файлаdocx
Имя файла4 Дисер с 15 СК и Мягкое дек с 55.docx
ТипДиссертация
#111324
страница6 из 21
1   2   3   4   5   6   7   8   9   ...   21

Декодирование кодов Рида – Соломона



Коды РС были открыты в 1960 году американскими учеными Ридом и Соломоном, как частный случай недвоичных кодов Боуза - Чоудхури - Хоквингема (БЧХ). В настоящее время коды РС являются

одним из наиболее востребованных видов помехоустойчивого кодирования. Связано это с тем, что коды РС эффективно справляются с исправлением группирующихся ошибок, которые возникают при воздействии на канал связи импульсной помехи.

Способы декодирования кодов РС достаточно хорошо проработаны в теоретическом и реализационном плане, но, тем не менее, представляют собой довольно сложную задачу [17]. Типовая схема декодирования, получившая название авторегрессионого спектрального метода декодирования, состоит из следующих шагов [4, 19, 31]:

  • вычисления синдрома ошибки (синдромный декодер);

  • построения полинома локаторов ошибок, осуществляемого либо посредством высокоэффективного, но сложно реализуемого алгоритма Берлекэмпа – Месси (БМА), либо посредством простого, но медленного алгоритма Евклида;

  • нахождения корней данного полинома, обычно решающегося полным перебором всех возможных значений (алгоритм Ченя);

  • определения характера ошибки, сводящегося к построению битовой маски, вычисляемой на основе обращения алгоритма Форни или любого другого алгоритма обращения матрицы;

  • исправления ошибочных символов путем наложения битовой маски на информационное слово и последовательного инвертирования всех искаженных бит с помощью операции XOR.

Схема быстрого декодирования кодов РС приведена на рисунке 1.7. Здесь особого внимания и более детального рассмотрения заслуживают алгоритм по поиску локаторов искажений, а также алгоритм определения характера ошибок, предложенный Форни [23].



Приёмник

𝐶 𝑥 = 𝑢 𝑥 + 𝑒 𝑥

Искаженные данные
Вычисление компонентов синдрома

𝑆𝑗 = 𝐶 𝛼𝑗 𝑗 = 1, … , 2𝑡

2t синдром

Вычисление полинома локаторов ошибок (стираний) Λ(х) с помощью алгоритма Берлекэмпа-Месси
Локаторы искажений

Нахождение корней полинома Λ(х) по алгоритму Ченя

X𝑙 = 𝑙 = 1, … , 𝑣

Определение характера ошибки на основе алгоритма Форни

Ω 𝑥 = 𝑆 𝑥 ∙ Λ 𝑥 𝑚𝑜𝑑 𝑥2𝑡

𝑣

Λ 𝑥 = 𝑗 ∙ Λ𝑗 ∙ 𝑥𝑗 −1

𝑗 =1

Ω 𝑋−1

𝑌𝑙 = 𝑙

Λ 𝑋−1

𝑙

e𝑙 = 𝑌𝑙 ∙ 𝑋𝑙


Корректировка полученных данных

𝑢 𝑥 = 𝐶 𝑥 xor e 𝑥

Рисунок 1.7 – Схема быстрого декодирования кодов Рида – Соломона



      1. Алгоритм Форни


Предположим, что в приемник аппаратуры передачи данных (АПД) поступила кодовая комбинация кода РС с замешанным в нее шумом:

Cx ux ex,

(1.21)

где u(x) – переданная передатчиком АПД кодовая комбинация, в которой в процессе передачи по каналу связи произошло v ошибок, отображаемых

многочленом e(x) степени v. Каждый ненулевой компонент e(x) описывается парой элементов: Yi– величина ошибок и Xi– номер позиции ошибки (локатор ошибки). Yi, Xi– элементы GF(q), при этом элемент Xi= αi, αi GF(q).

Для описания ошибок используются:

Многочлен локаторов ошибок:


v

x 1 x X xv   xv1   x   ,

i v v1 1 0

i1

(1.22)

имеющий корни Xi-1, i = 1, …, v, взаимные к локаторам ошибок, то есть Xiαi= 1.

Многочлен значений ошибок

x:



x Sxx mod x2t,

(1.23)


где S(x) – синдромный многочлен бесконечной степени, для которого известны только 2t коэффициентов для поступившей комбинации РС-кода. Синдром рассчитывается согласно формуле (1.24):

2t 2t v

Sx Sx jY X jx j.

j i i

j1 j1 i1

(1.24)


S  v Y X jejj

Здесь

j i i i1

– элемент синдрома, α

– корень порождающего

многочлена РС-кода. Значения
j


S ej задаются проверками:




Sj C u e e,

j j j j

(1.25)




где

m0

j m0 2t1

при

m0 1.


Равенство (1.23) определяет множество из (2t – v) уравнений и называется ключевым уравнением, так как оно представляется «ключом» решения задачи декодирования. Это становится понятным, если учесть, что степень Ω(x) не превышает (v – 1), и поэтому справедливо:
n


x Sx 2t 1 0 ,

v

(1.26)




где xn
m


m

xm

m1

xm1 ...

xn .

Из равенства (1.23) необходимо получить v уравнений для v неизвестных коэффициентов Λ(x). Эти уравнения являются линейными. Они могут быть решены обычными методами, либо с помощью итерационных процедур. После нахождения многочлена Λ(x) ключевое уравнение позволяет найти неизвестные

компоненты вектора e(x) и по ним выходной вектор декодера

Cx ux ex

[26].

Простейшим путем нахождения корней многочлена Λ(x) является метод полного перебора всех возможных значений заданного поля, известный как процедура Ченя. Эта процедура состоит в последовательном вычислении Λ(α j) для каждого j и сравнении полученных значений с нулем. Если величина Λ(α-k) равна нулю, то αkявляется взаимной к корню многочлена локаторов ошибок, и k-й элемент кодовой комбинации содержит ошибку. Наиболее простым способом вычисления значения Λ(x) в точке β является схема Горнера:

...v v1 v2 v3 ... 0 .

(1.27)

Для вычисления Λ(β) по схеме Горнера требуется только v умножений и v

сложений, где v – степень Λ(x).

После определения локаторов ошибок с помощью ключевого уравнения рассчитываются значения ошибок. Для этого, используя значения сомножителей, входящих в равенство для Ω(x), ключевое уравнение переписывается следующим образом:

   2t v jj1 v  2t

xYiXix 1 Xix mod x

j 1 i1 i1

v 2t

YX 1 Xx Xxj1 1 Xxmod x2t.

i i i i l

i1 j1 li



(1.28)

После сворачивания выражения в квадратных скобках, получим:


x Y X 1 X 2tx2t1 X xmod x2t.

v
i i i l

i1 li

(1.29)




Приводя выражение (1.29) по модулю

x2t , получим:




v

x YiXi1 Xlx.

i1 li

(1.30)




После чего вычисляется многочлен значений ошибок на позиции
l


l : x X1.




X 1 Y X 1 XX 1 ,

l i j l

j l


(1.31)


откуда

X 1  X 1

Y l l .

l1 X X1

j l

j l


(1.32)




Далее рассчитывается производная

x от многочлена локаторов ошибок:




x X 1 x X .

v
i j

i1 jl

(1.33)


Для l-й позиции получим:

X 1 X1 X X 1 .

l l j l

j l


(1.34)




С учетом выражения (1.32) Yl

значение ошибки на позиции l примет вид:




X1

Yl.

l X 1

l


(1.35)
1   2   3   4   5   6   7   8   9   ...   21


написать администратору сайта