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

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

Выход :

λ_i2t  _ti2t ,

_i2t  _i2t ,

i  0,1, ..., t .

i  0,1, ..., t 1 .

Предложенная архитектура значительно сокращает время, затрачиваемое на решение ключевого уравнения, что в свою очередь ведет к увеличению пропускной способности декодера. Кроме того, такая регулярная структура позволяет создавать схемы декодера с прогнозируемой длиной критического пути для различных кодов РС с разными параметрами m и t. Это свойство будет лежать в основе адаптивного декодера кодов РС [118, 120].

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

Таблица 3.2. Сложность различных алгоритмов решения ключевого уравнения

Алгоритм	Сумматоры	Умножители	Регистры	Мульти- плексоры	Число тактов	Критический путь
Евклида	2t 1	2t 1	10t  5	14t  7	12t	Tmult  Tadd  Tmux
iBM	2t 1	3t  3	4t  2	t 1	3t	 2  Tmult Tadd
miBM	3t 1	6t  2	6t  2	3t 1	2t	Tmult  Tadd

3. 
   Оптимальная реализацияCSEE-блока
   

Для дальнейшего декодирования принятого блока кода РС следует

определить позиции символов, на которых произошли ошибки, и значения этих ошибок. Для определения позиций искаженных символов необходимо найти

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

^x, рассчитанного в KES-блоке.

Реализовать это можно с помощью простой процедуры полного перебора всех 2^m – 1 возможных значений, известной как алгоритм Ченя [82].

Определение значения ошибки реализуется с помощью алгоритма Форни согласно формуле (3.3). В целях экономии аппаратных ресурсов оба алгоритма (Ченя и Форни) удобно реализовать в одном устройстве. При этом алгоритм Ченя

за 2^m – 1 тактов перебирает все возможные элементы поля Галуа. На каждом такте

осуществляется проверка, обращает ли данное значение полином

x

в ноль, то

есть является ли оно его корнем. Если значение является корнем многочлена локаторов ошибок, то согласно алгоритму Форни вычисляется значение ошибки и ее корректировки. Алгоритм выглядит следующим образом [14, 16]:

for

i  1 step

1 until

2^m1 do

begin

if

 ⁱ  0

end

then

end

Ωαⁱ


^Y2^m1i^{ R}2^m1i^ _αⁱ_

Вычисление ошибочных позиций и значения этих ошибок требует расчета

трех полиномов:

 ⁱ

степени t,

 ⁱ

степени t – 1 и

^ ⁱ

степени t – 1.

Представим полином

^x в виде суммы двух многочленов:

x  even x odd x ,

(3.8)

где

^even ^x

включает компоненты полинома с четными степенями, а

_oddx  x ^x

включает только нечетные степени. Таким образом, сначала

рассчитываются многочлены

_even x и

_odd x, затем

^x, а производная

^x

вычисляется автоматически [79, 83].

Элементарная ячейка, осуществляющая перебор Ченя, изображена на рисунке 3.18а. Полная схема, реализующая алгоритм Ченя, состоящая из восьми таких ячеек, представлена на рисунке 3.18б.

а б λ3 λ5 λ7 1 C2 C4 C6 C1 λʹ(αi) Cx λ1 D D 1 D Ci 0 D D 0 1 λ0 0 λ(αi) αi D D D D 1 C2 C4 C6 C8 λ2 λ4 λ6 λ8

Рисунок 3.18 – Схема устройства, реализующего перебор Ченя

На рисунке 3.19 представлена схема устройства, исправляющего ошибки, которое работает согласно алгоритму Форни.

ω3 ω5 ω7 i C3 C5 C7 λ(α ) D D D ω1 C1 λʹ(α ) ROM D Y i ω0 i 0 D D D D ω(α ) D 1 C2 C4 C6 FIFO R ω2 ω4 ω6

Рисунок 3.19 – Схема устройства, работающего согласно алгоритму Форни

Память ROM содержит таблицу обратных элементов поля Галуа

_^ i _{ }2^m1i _,

необходимых для осуществления операции деления. Блок FIFO содержит принятые из канала связи символы R. На этапе коррекции из этих символов R вычитается значение ошибки Y, рассчитанное по алгоритму Форни, после чего исправленные символы покидают декодер. Стоит отметить, что в конечном поле арифметические операции сложения и вычитания идентичны, поэтому на этапе коррекции используется сумматор.

Листинги программ, реализующих описанные выше устройства, иожно найти, обратившись к Приложению Б.

4. 
   Разработка оптимального АЛУ для реализации арифметических операций в поляхГалуа
   

Важным этапом оптимизации всего кодека является оптимальная реализация арифметических операций в конечных полях [48]. Все описанные выше операции сложения, умножения происходят в поле Галуа. Для разрабатываемой СПК поле имеет байтовую размерность, то есть GF(2⁸).

Существуют разные подходы к аппаратной реализации арифметических операций в поле Галуа. Одним из таких подходов является предварительная подготовка сверочных таблиц, хранящих результаты арифметических операций. На каждую операцию потребуется по одной такой таблице, которые должны храниться в памяти кодека. Такие таблицы на примере поля Галуа GF(2³) имеют следующий вид [8, 20, 47]:

Таблица 3.3. Сложение в поле GF2³  Таблица 3.4. Умножение в поле GF2³ 

+	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	0	3	2	5	4	7	6
2	2	3	0	1	6	7	4	5
3	3	2	1	0	7	6	5	4
4	4	5	6	7	0	1	2	3
5	5	4	7	6	1	0	3	2
6	6	7	4	5	2	3	0	1
7	7	6	5	4	3	2	1	0

×	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7
2	0	2	4	6	3	1	7	5
3	0	3	6	5	7	4	1	2
4	0	4	3	7	6	2	5	1
5	0	5	1	4	2	7	3	6
6	0	6	7	1	5	3	2	4
7	0	7	5	2	1	6	4	3

Для реализации операции сложения (вычитания) в поле Галуа заготовка сверочных таблиц практического смысла не имеет, так как эта операция замещается простым побитовым сложением по модулю 2 [30]. Для байтового поля сумматор, вычисляющий выражение A + B = C, примет вид:

b7 a7 b6 a6 b5 a5 b4 a4 b3 a3 b2 a2 b1 a1 b0 a0 c7 c6 c5 c4 c3 c2 c1 c0

Рисунок 3.20 – Аппаратная реализация операции сложения в поле Галуа GF28 

Гораздо сложнее реализовать операцию умножение. Для байтовых полей сверочная таблица операции умножения займет 256  256 байт. Так как в кодеке произведения вычисляются одновременно сразу несколькими блоками, для распараллеливания вычислений таких таблиц необходимо иметь большое количество, что, учитывая размер каждой таблицы, оказывается весьма расточительным. Поэтому оптимальным с точки зрения затрачиваемых ресурсов решением будет реализация операции умножении на вентильном уровне [51].

Для реализации умножения на вентильном уровне необходимо представить операнды в полиноминальной форме [61]. Так операнд A примет вид:

A a m1  a m2  ...  a a . m1 m2 1 0

(3.9)

Тогда умножение операндов A и B будет выглядеть следующим образом:

2m2 m1 W  A B  d hkdhk, k k km k0

(3.10)

где

d  _a b

. Так как

h^kGF2^m, существует единственный

^k     

k i ki
k


i0

g_i 0 i m1

такой, что
m1

k ki
h  _ g h


i
для всех
m  k  2m  2 . В этом случае выражение (3.10)

примет вид:

i0

m1 W  hk, k k 0

(3.11)

где

_k  d_k

2m2

• 
  d
  
  
  k
  
  j
  
  

jm

g ^{j. Формула (3.11) представляет собой конечное выражение для}

вычисления произведения двух чисел в поле Галуа. Операция состоит из двух процедур: непосредственно умножения и деления по модулю. Данные внутри каждой операции независимы, и их обработка может осуществляться параллельно.

В полиноминальном виде произведение (3.10) в конечном поле будет выглядеть как ^{W x  Ax Bxmod px}. Это выражение можно привести к виду:

Wx  ...0  Axb7 x Axb6 x ...  Axb1 x Axb0

(3.12)

В аппаратном виде выражение

Axb_j

вычисляется с помощью бинарной

операции AND, а сложения в выражении (3.12) замещаются операцией XOR. Аппаратный умножитель в поле Галуа GF(2⁸) представлен на рисунке 3.21.

... d14 d13 d12 d5 d4 d3 d2 d1 d0 ... ... W7 W4 W3 W2 W1 W0

Рисунок 3.21 – Аппаратный умножитель в поле Галуа GF28 

Устройство содержит 64 вентиля AND и 77 элементов XOR. Верхняя часть схемы отвечает за умножение двух операндов, а нижняя осуществляет деление по модулю.