Материал: Проблемы обеспечения надежности и качества приборов, устройств и систем. сборник научных трудов. Муратов А.В., Макаров О.Ю
fn (xn ) ln p(xn / yn ),
где p(xn / yn ) - условное распределение входного сим-
вола данных n при значении xn, обозначенных символом выход-
ных данных n при |
значении yn. fn (0) fn (xn ), равен |
ln(p(xn/ yn )/ p(0/ yn )) |
- это отношение логарифмической |
функции правдоподобия (LLR) входных символьных данных n при значении xn против значения 0.
В этих обозначениях максимальная вероятность декодирования может быть сформулирована как задача оптимизации с ограничениями [1,2],
|
n |
|
|
x ,minx ,...,x |
fn (xn ) |
при условии, что HxT 0. |
(1) |
1 2 |
N n 1 |
|
|
Допустим Х будет множество всех переменных. Учитывая m ограничения, будет .Hm xT 0, пусть Хm – подмноже-
ство всех переменных, соответствующих ненулевым элементам в Нm, т.е. Xm xn | hmn 0 .
Пусть fXm (Xm) |
функция, определенная на Xm как |
||||
fX |
|
0, |
если |
Hm xT 0; |
, |
(Xm ) |
все |
остальное. |
|||
|
m |
, |
|
||
|
|
|
|
|
|
fXm (Xm) называется функцией ограничения, представ-
ляющей m-ое ограничение. Использование функций ограничений, проблему декодирования (1) можно переформулировать как безусловную комбинаторную задачу оптимизации следующей целевой функцией,
M |
N |
|
E(x) fXm |
(X m) fn (xn ) |
(2) |
m 1 |
n 1 |
|
Обобщенный алгоритм min-sum для LDPC на GF (q).
131
L(mnk) (xn ) - это логарифмическое отношение правдоподо-
бия того, что проверка узла m выполняется, когда входной символ n фиксирован на значение 0 в сравнении с значением хn и другие символы являются независимыми от коэффициента логарифмического отношения правдоподобия
Zmn' (0) Zmn' (xn' ), |
n' M (m) \ n. |
Псевдо-код обобщенного алгоритма декодирования minsum LDPC кода для GF(Q) задается следующим образом.
Инициализация. Для n=1, 2, ….,N и m=1, 2,..., M,
Zmn(0) (xn ) fn (xn ).
Итерация (k=1,2,3, …)
1) Горизонтальное сканирование
Рассчитывается L(mnk) (xn ), для каждого xn GF(q),
L(mnk) (xn ) min |
Zmn(k '1) (xn') |
(3) |
|||
X |
m |
\x |
n n' N(m)\n |
|
|
|
|
|
|||
hmn'xn' 0, n' N(m)
Нормализация L(mnk) (xn ) |
|
|
Для каждого m, и каждого |
n N(m), |
L(mnk) (xn ) от |
L(mnk) (0), |
|
|
L(mnk) (xn ) L(mnk) (xn ) L(mnk) (0) . |
|
|
2) Вертикальное сканирование |
|
|
Для n=1,2,…,N, |
|
|
Zmn(k) (xn ) fn(xn) |
L(mk')n(xn). |
(4) |
m' M(n)\m |
|
|
3) Декодирование Для каждого символа рассчитывается его апостериорное
логарифмическое отношение правдоподобия (LLR)
132
Zn(k) (xn) fn (xn ) L(mnk) (xn ). |
(5) |
m M(n)
Затем оценивается оригинальное кодовое слово xˆ(k) ,
xˆn(k) argmin Zn(k) (xn ), для n=1,2, … ,N
xn
Если H xˆ(k) T 0 или число итераций превышает не-
которое значение, итерация останавливается и выход xˆ(k) как декодируемое кодовое слово.
В приведенном выше алгоритме Zmn(k) (0) Zmn(k) (xn ) апо-
стериорное LLR для значения xn в итерации k.
Одним из возможных способов повысить производительность обобщенного алгоритма min-sum изменить уравнение
(4) и уравнение (5) в виде
Zmn(k) (xn ) fn (xn ) k |
L(mk')n (xn ), |
m' M(n)\m |
|
Zn(k) (xn ) fn (xn ) k |
L(mnk) (xn ), |
|
m M(n) |
где αk является масштабированной постоянной при итерации k, удовлетворяющая 0< αk<1. С учетом этих изменений, алгоритм декодирования называется нормализованным алго-
ритмом min-sum.
Другой возможный способ повысить производительность - изменить уравнения (4) и (5) как
Zmn(k) (xn ) fn (xn ) |
max L(mk')n (xn ) k ,0 , |
m' M(n)\m |
|
Zn(k) (xn) fn(xn) |
maxL(mnk) (xn) k ,0 , |
m M(n)
где βk – изменение динамической постоянной в проходе алгоритма k, входящее в условие βk >0. При данном упрощении, алгоритм декодирования следует обозначать как (offset) minsum. Для возможности увеличения силы декодирования, коэффициент масштабирования αk или постоянной смещение βk могут быть определены экспериментально или методом развития плотности.
133
Эта проблема решается с помощью двух проверок. Первая – это так называемая левосторонняя проверка. Вторая имеет обратный порядок, от хN до х1, так называемый правосторонняя проверка. Каждая проверка имеет N-1 шагов, шаг n=1,2,…,N-1. Рассмотрим левостороннюю проверку. Правосторонняя проверка может быть получена просто меняя порядок переменных [3].
Для левосторонней проверки на этапе n, используем переменную sn, sn GF(q), чтобы представить результат в следующем суммировании
n
sn hmn' xn' . n' 1
Кроме того, зададим действительное значение rnL (sn )
для каждого состояния sn, которое хранит результат следующей условной задачи оптимизации,
|
n |
n |
|
|
rnL (sn ) xmin,...,x |
gn' xn' , |
hmn' xn' |
sn , |
(6) |
1 n n' 1 |
n' 1 |
|
|
|
где индекс «L» означает левостороннюю проверку. Когда n=1, r1L (s1 ), инициализируется как
r1L (s1 ) g1 hm11s1 .
|
Для каждого шага n, n=2,3,…,N-1, вычисляет динамиче- |
||||||||||||||||||||||
ское программирование |
rL (s |
n |
) для каждого |
s |
n |
, |
s |
n |
GF(q) |
||||||||||||||
следующим образом |
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
rL (s |
n |
) min g |
n |
x |
n |
rL |
s |
n 1 |
, |
s |
n 1 |
h |
mn |
x |
n |
s |
n |
. |
(7) |
||||
n |
xn ,sn 1 |
|
|
|
n 1 |
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Аналогично, |
для |
правого |
сканирования, |
когда |
n=N, |
|||||||||||||||||
rnR (sn )
rNR (sN ) gN hm1,N sN .
Рассчитаем rnR (sn ), для n=N-1, N-2,…, 2 следующим
образом |
|
|
|
|
|
x |
|
rR |
s |
|
, s |
|
|
|
|
|
|
|
|
|
rR (s |
n |
) min |
g |
n |
n |
n 1 |
n 1 |
h |
mn |
x |
n |
s |
n |
. |
(8) |
|||||
n |
xn |
,sn 1 |
|
|
n 1 |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
134
Можем получить результат минимизации для (6) rnL (sn )
и rnR (sn ) непосредственно. Для 1<n<N, имеем
L(k) |
(x |
n |
) min |
rL |
s |
n 1 |
rR |
|
s |
n 1 |
s |
n 1 |
h |
mn |
x |
n |
s |
n |
1 |
0. (9) |
|||||||||||||||
mn |
|
sn 1,sn 1 |
|
n 1 |
|
|
n 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
можно переписать уравнение (9) в форме, более понят- |
||||||||||||||||||||||||||||||||
ной для вычислений |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
L(k) (x |
n |
) min rL |
s |
n 1 |
rR |
s |
n 1 |
h |
mn |
x |
n |
|
(10) |
|||||||||||||||||||
|
|
|
mn |
|
|
|
|
|
n 1 |
|
|
|
n 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
sn 1,sn 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
дальше |
Для GF(q), q=2m, уравнение (10) может быть упрощено |
||||||||||||||||||||||||||||||||||
L(k) |
|
|
|
) min rL |
|
s |
|
rR |
|
s |
|
|
|
|
|
|
|
|
|
|
. |
|
|||||||||||||
|
|
|
(x |
n |
|
n 1 |
|
n 1 |
h |
mn |
x |
n |
(11) |
||||||||||||||||||||||
|
|
|
mn |
|
|
|
|
sn 1,sn 1 |
n 1 |
|
|
|
|
n 1 |
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
При n=N, |
|
|
|
L(k) x |
|
rL |
|
h |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
N |
1 |
mN |
x |
N |
|
|
|
|
|
|
|
|
(12) |
|||||||||||||
|
|
|
|
|
|
|
|
|
m,N |
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
При n=1, |
|
|
|
|
|
L(k) |
x |
|
rL |
h |
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
1 |
m1 |
x |
|
|
|
|
|
|
|
|
|
(13) |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
m,1 |
|
|
|
2 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|||||
Отношение (BER) поля Галуа GF(4) и GF(8)
135