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

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

Данный способ позволяет найти значения ошибок через ключевое уравнение (1.23) и многочлен локаторов ошибок (1.27), однако решение самого уравнения и нахождение многочлена локаторов ошибок является также сложной и трудоемкой процедурой. Наиболее распространенной из них является алгоритм Берлекэмпа – Месси.

2. 
   Алгоритм Берлекэмпа – Месси
   

Нахождение решения ключевого уравнения (1.23), имеющего минимальную степень, эквивалентно построению регистра сдвига минимальной длины с обратными связями, отображающими Λ(x), порождающими первые 2t членов S(x). Основное содержание БМА формулируется следующим образом. Вначале находят самый короткий регистр сдвига, генерирующий S₁. Далее проверяют,

порождает ли этот регистр также S₁. Если порождает, то данный регистр по-прежнему остается наилучшим решением, и нужно проверить, порождает ли он следующие символы синдромного многочлена. На определенном шаге очередной символ уже не будет генерироваться. В этот момент нужно изменить регистр таким образом, чтобы он:

• 
  правильно предсказывал следующий символ,
  
• 
  не менял предсказание предыдущих символов,
  
• 
  увеличивал длину регистра на минимально возможную величину.
  

Процесс вычисления продолжается до тех пор, пока не будут порождены первые 2t символов синдрома [5, 6].

Алгоритм строится на основе итеративной процедуры. При каждой итерации должны сохраняться как многочлен связей Λ(x), так и добавка B(x). Для каждого нового члена S(x) предусматривается проверка правильности предсказания этого символа текущим многочленом связи. Если предсказание правильно, то многочлен связей не меняется, а добавка умножается на x. Если предсказание неправильно (невязка Δr ≠ 0), то изменяют текущий многочлен связей, прибавляя к нему добавку. После этого проверяют, увеличилась ли длина регистра. Если она не увеличилась, то текущую добавку оставляют без изменений. Если длина регистра возрастает, то лучшей добавкой считают предыдущий многочлен связей. Для недвоичных полей добавку нормируют, чтобы невязка стала равной 1. Далее при каждом исправлении эту нормализованную добавку умножают на значение текущей невязки [87].

Блок-схема БМА приведена на рисунке 1.8. Алгоритм выполняется за 2t = n – k итераций.

При этом многочлен значений ошибок находится непосредственным умножением по формуле ключевого уравнения (1.23).

Начальные значения r = 0, Λ(x) = 1, L = 0, B(x) = 1, Ω(x) = 0, A(x) = 1 r ← r + 1 Вычисление ошибки в следующем компоненте синдрома 𝐿 Δ𝑟 = Λ𝑗 ∙ 𝑆𝑟−𝑗 𝑗 =0 Генерирует ли Да, отводы обратной связи существующий остаются без изменений регистр сдвига Δr = 0 следующий компонент Нет, отводы обратной синдрома? связи необходимо изменить Вычисление нового многочлена связей, для которого Δr = 0 𝑀 𝑥 = Λ 𝑥 + Δ𝑟 ∙ 𝑥 ∙ 𝐵 𝑥 Надо ли увеличивать длину Нет регистра? 2L ≤ r- 1 Λ 𝑥 ← 𝑀 𝑥 Да 𝐵 𝑥 ← Δ−1 ∙ 𝐵 𝑥 Сохранение прежнего 𝑟 регистра после нормализации 𝐵 𝑥 ← 𝑥 ∙ 𝐵 𝑥 Λ 𝑥 ← 𝑀 𝑥 Модификация регистра сдвига 𝐿 ← 𝑟 − 𝐿 Изменение длины регистра Многочлен значений ошибок, соответствующий Λr(x) : Ω𝑟 𝑥 ← Ω𝑟−1 𝑥 + Δ𝑟 ∙ 𝐴𝑟−1 𝑥 Да Lr– Lr-1 = 0 Ar(x) ←x∙Ar-1(x) Нет Вычисление новой добавки для Ω(x) : A𝑟 𝑥 ← Δ−1 ∙ 𝑥 ∙ Ω 𝑥 𝑟 𝑟−1 В принятой Нет комбинации более t r = 2t ошибок Да Нет Да К следующему этапу Стоп deg Λ(x) = L декодирования

Рисунок 1.8 – Алгоритм Берлекэмпа – Месси

Принятые обозначения на рисунке 1.8:

r – номер итерации, r = 0, 1, 2, … , n – k = 2t;

S_r– компонент синдрома;

r – ошибка в вычислении S_r(r-я невязка);

(x) – многочлен локаторов ошибок, в соответствии с компонентами которого строится регистр сдвига минимальной длины;

L – длина регистра сдвига, L  deg (x);

B(x) – нормирующая добавка;

(x) – многочлен значений ошибок.

В [107] приводится дополнение к БМА, позволяющее в ходе решения ключевого уравнения одновременно с нахождением значения многочлена локаторов ошибок Λ(x) степени меньшей или равной t находить многочлен значений ошибок Ω(x) степени меньшей или равной t – 1

Это дополнение на рисунке 1.8 представлено отдельными блоками.

Поскольку Ω(x) находится умножением Λ(x) на S(x), можно задать последовательность многочленов Ω_r(x), удовлетворяющих тем же рекуррентным соотношениям, что и многочлены Λ_r(x). Чтобы избежать путаницы, обозначим добавку при нахождении Ω(x) через A_r(x). Тогда, положив Ω₀ (x) = 0 и A₀ (x) = 1, получим [13]:

r1x  rx r Arx, A x  x Arx, если Lr 1  Lr . r1 x x r1 , если L  L  r r1 r

(1.36)

Как видно из (1.36), решение ключевого уравнения с помощью БМА требует запуска итеративной процедуры. На практике для реализации алгоритма необходимо проектировать специальный сдвиговый регистр с обратными связями [74].

3. 
   АлгоритмЕвклида
   

В основе этого алгоритма лежит известная процедура нахождения наибольшего общего делителя (НОД) двух полиномов. Задача декодирования кодов РС в данном случае может быть переформулирована как задача определения многочлена (x), удовлетворяющего ключевому уравнению (1.23). Решение может быть найдено применением расширенного алгоритма Евклида к многочленам r₀(x) = x^dи r₁(x) = S(x), где d = 2t + 1 – кодовое расстояние, а S(x) – синдромный многочлен. Если на j-ом шаге алгоритма получено решение:

rj (x)  aj(x)x  b(x)  S(x) d j

(1.37)

такое, что deg( r_j(x) ) ≤ t, то (x) = r_j(x) и Λ(x) = b_j(x). В данном случае полином α_j(x) не представляет интереса, так как решение уравнения (1.23) ищется по модулю x^d[110].

Расширенный алгоритм Евклида, вычисляющий НОД ( r₀(x), r₁(x) ) , состоит из следующих этапов:

• 
  устанавливаются начальные условия: a₀(x) = 1, a₁(x) = 0, b₀(x) = 0,
  

b₁(x) = 1;

• 
  на вход арифметико-логического устройства (АЛУ) согласно (1.37) подаются значения r₀(x) и r₁(x), при этом deg( r₀(x) ) ≥ deg( r₁(x) );
  
• 
  на шаге j( j ≥ 2 ) применяется длинное деление к многочленам r_j-2(x) и
  

r_j-1(x), результат деления представляется в виде:

rj2 (x)  qj (x)rj1 (x)  rj (x) , 0  degr(x) degr (x), j j1

(1.38)

где q_j(x) – неполное частное, а r_j(x) – остаток от деления на j-ом шаге;

• 
  вычисляется множитель b_j(x):
  

bj (x)  bj 2 (x)  qj (x)bj 1(x) ;

(1.39)

• 
  проверяется степень полученного многочлена r_j(x), если deg( r_j(x) ) ≤ t , то выполнение алгоритма заканчивается, в противном случае алгоритм переходит на следующий шаг, и процедура повторяется;
  
• 
  на выходе АЛУ возвращает рассчитанные значения многочлена значений ошибок (x) = r_j(x) и многочлена локаторов ошибо Λ(x) = b_j(x) [110].
  

Блок-схема вычисления полинома локаторов ошибок и решения ключевого уравнения согласно алгоритму Евклида представлена на рисунке 1.9

Начало Инициализация r0  x , d r1  S ( x ), b 0  0 , b1  1; Деление многочленов rj  2 x   rj 1 x  rj2 x  qxrj1 x rjx Обновление множителей ajx  aj2 x qjxaj1 x , bjx  bj 2 x  qjxbj1 x . deg rjx  t нет j  j1 да x  rj x x  bj x К следующему этапу декодирования

Рисунок 1.9 – Алгоритм Евклида

4. 
   Алгоритм Гурусвами –Судана
   

Алгоритм списочного декодирования Гурусвами – Судана (ГСА) обобщенных кодов РС состоит из двух основных этапов [28]:

• 
  интерполяции;
  
• 
  факторизации.
  

На первом этапе по полученному из канала связи кодовому слову строится полином двух переменных специального вида Q(x, y), такого что:

wdeg1,k  Q(x, y)  l ,

(1.40)

где (1, k) – взвешенная степень wdeg_{(1, k)} Q(x, y) многочлена Q(x, y), равная максимуму (1, k)-взвешенных степеней его ненулевых членов. При этом точки (x_i, y_i) являются корнями этого многочлена кратности r:

Q j1, j2  (x, y)  0 , j  j  r, i 1, ... , n. i i 1 2

(1.41)

На втором этапе полином Q(x, y) разлагается на сомножители, по которым строится список. Для этого ищутся все многочлены f ^(j) (x), удовлетворяющие условиям (1.42). Далее строятся соответствующие им кодовые слова и выбираются те из них, которые отличаются от принятого вектора менее чем в τ позициях.

deg f  j x  k , Qx, f j x 0 .

(1.42)

Доказательство справедливости приведенного выше алгоритма, а также выражения, связывающие параметры l, r, τ, k, n, в рамках этой работы приводиться не будут. Их можно найти в [28].

В настоящее время существуют эффективные алгоритмы построения многочлена Q(x, y). Наиболее распространен среди них итеративный интерполяционный алгоритм (ИИА) [121]. Он состоит в том, что вместо построения одного многочлена, удовлетворяющего вышеперечисленным условиям, строятся ρ + 1 интерполяционных многочленов, при этом их степени по y не превышают ρ. Величина ρ выбирается таким образом, чтобы искомый многочлен, удовлетворяющий условиям (1.40), гарантированно присутствовал среди этих многочленов. Для лучшего понимания алгоритма представим вектор многочленов

 Q x, y  q xyi, j 0 , ... ,  j ij i 0

(1.43)

в виде произведения Y∙Q(x, y), где Q(x) – некоторый матричный многочлен

Qx  qij x ,

(1.44)

а – Y вектор вида Y = ( y⁰ , y¹ , … , y ^ρ).

На начальном этапе полагается Q(x) = I. Последовательно обрабатывая интерполяционные точки (x_i, y_i) и соответствующие им уравнения (1.41), на каждом шаге необходимо домножать Q(x) справа на матрицу вида:

 1 0  0  0     0 1  0  0          i, j1 , j2        ,  0  1  x x       i   j j j  0 0 0           0 0  0  1 

(1.45)

где

^{  Q j1 , j2 x , y },

^j₀ ^{ arg min Q}_j ^{(x, y)} , причем минимальный многочлен

j j i i

j: _j 0

определяется на основе градуированного лексикографического порядка. Элемент x – x_iрасполагается в столбце j₀ и строке j₀. Умножение на данную матрицу приводит к тому, что производные Хассе порядка [ j₁, j₂ ] всех многочленов Q(x, y) в точке (x_i, y_i) обращаются в ноль. После обработки всех интерполяционных точек многочлены Q _j(x, y) будут удовлетворять уравнениям
j

(1.41), а их старшие члены будут иметь вид

LT Qx, y  x^ijy^j,

j  0, ... , _{, причем}

показатели степеней i_jбудут минимально возможными. После чего среди этих многочленов выбирается многочлен с наименьшей взвешенной степенью, который и является решением задачи интерполяции [121].

На этапе факторизации ГСА требуется нахождение всех f ^(j) (x) полученного многочлена Q(x, y) , таких что:

Qx, f j x 0 , deg f j x  k.

(1.46)

Наиболее эффективным способом решения данной задачи является алгоритм Рота – Рукенштейна [121]. Данный алгоритм позволяет найти
x

коэффициенты многочленов

f^{ j}(x)  _ f ⁱ

i
ji


в порядке возрастания i

одновременно для всех j. Для нахождения коэффициентов всех f _j,0 необходимо поделить Q(x, y) на максимально возможную степень x. Тогда из (1.46) следует, что:

Q0, f Q0, f j0 0 . j,0

(1.47)

Применяя стандартные методы поиска корней многочленов от одной переменной из уравнения (1.47), можно найти все значения f _j,0. Тогда:

0  Qx, f jx Qx, f x f jx Q jx, f jx. j,0

(1.48)

Оставшиеся коэффициенты

^{f  j (x)} , обозначенные в (1.48) как

^{f j (x)} ,

могут быть найдены из (1.49) аналогичным образом:

Q j x, y  Qx, f  xy. j,0

(1.49)

Таким образом, ГСА позволяет произвести списочное декодирование кодов РС за полиноминальное время, которое может оказаться чрезмерно большим для практического применения. При этом наиболее трудоемким шагом является построение интерполяционного многочлена от двух переменных, проходящего с некоторой кратностью точки, соответствующие принятым символам [121].