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

• Название: Программноаппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов рида соломона в адаптивных системах обмена данными
• Анкор: Сверточные коды
• Дата: 09.03.2020
• Размер: 5.5 Mb.
• Имя файла: 4 Дисер с 15 СК и Мягкое дек с 55.docx
• Тип: Диссертация; #111324
• страница: 6 из 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. 
   Алгоритм Форни
   

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

Cx  ux ex,

(1.21)

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

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

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

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

v x  1 x X    xv   xv1    x   , i v v1 1 0 i1

(1.22)

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

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

x_:

x  Sxx mod x2t,

(1.23)

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

2t 2t v Sx  S x j Y  X j x j. j i i j1 j1 i1

(1.24)

S  v Y  X ^j e^j ^j

Здесь

j  i i i1

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

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

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


^{S  ej } задаются проверками:

Sj  C u e e, j j j j

(1.25)

где

m₀ 

j m₀  2t1

при

m₀  1_.

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

 x Sx  2t 1 0 , v

(1.26)

где ^{x}n
m


 _m

x^m

m1

x^m1  ... 

^xn .

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

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

C^x  ux ex

[26].

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

   ...v  v1   v2   v3   ... 0 .

(1.27)

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

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

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

    2t v j j1   v    2t xYiXix  1 Xix mod x  j 1 i1   i1  v  2t   YX 1 Xx Xxj1  1 Xxmod x2t. i i i i l i1  j1  li

(1.28)

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

x  Y X  1 X 2tx2t1 X xmod x2t. v i i i l i1 li

(1.29)

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

^x2t , получим:

v x  YiXi1 Xlx. i1 li

(1.30)

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


l : x  X^1.

X 1  Y X 1 XX 1 , l i j l j l

(1.31)

откуда

X 1  X 1 Y   l l . l1 X X1 j l j l

(1.32)

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

^{x} от многочлена локаторов ошибок:

x   X 1 x  X . v i j i1 jl

(1.33)

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

X 1   X1 X  X 1 . l l j l j l

(1.34)

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

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

X1  Y l. l X 1  l

(1.35)