Всего в том числе;pdf

Корректирующие свойства кодов с единичной памятью с малой
плотностью проверок∗
Кондрашов К.А.
ИППИ РАН
[email protected]
Зяблов В.В.
ИППИ РАН
[email protected]
Аннотация
3 описывается алгоритм декодирования, в главе 4
приводятся результаты моделирования.
В работе проводится исследование корректирующих свойств сверточных кодов с (частично) единичной памятью (ЕП), построенных на основе блоковых кодов с малой плотностью проверок (МПП),
при декодировании итеративным алгоритмом ”распространения доверия“(belief propagation).
2. Ансамбль (Ч)ЕП-МПП-кодов
В качестве блоковых кодов при построении
(Ч)ЕП-МПП-кодов используются коды с малой
плотностью проверок, предложенные впервые Галлагером [9]. МПП-коды Галлагера описываются разреженными проверочными матрицами, состоящими
из так называемых “слоев”, следующего вида:


H0 0 . . . 0
 0 H0 . . . 0 


H∗ =  .
,
(1)
..
.. 
.
.
.
 .
.
.
. 
0
0 . . . H0 b×bn
1. Введение
Коды с единичной памятью (ЕП) были вынесены Ли в 1976 году [1] из общего класса сверточных кодов с произвольной памятью m. ЕП-коды –
это сверточные (N, K, m, ν)-коды, где N – длина кодового блока, K – размерность, m = 1 – память и
ν = K – общая длина кодового ограничения. В случае, если ν < K, коды обладают частично единичной памятью (ЧЕП) [2]. В 1986 году К. Томмесен и
Й. Юстесен вывели границу свободного расстояния
ЕП-кодов [3] и показали, что ЕП-коды могут обладать свойствами, превосходящими свойства сверточных кодов с произвольной памятью при сравнимых
параметрах.
Коды с (Ч)ЕП памятью строятся на основе
блоковых кодов, например кодов БЧХ [4], [5] или
Рида–Соломона [6]. В работе [7] были представлены
(Ч)ЕП-коды, построенные из блоковых кодов Галлагера с малой плотностью проверок [9]. Граница свободного расстояния (Ч)ЕП-МПП-кодов совпадает с
границей Томмесена-Юстесена при R ≤ 0.5 и ухудшается при больших скоростях [8]. В данной работе
проводится исследование корректирующих свойств
представленных (Ч)ЕП-МПП-кодов при декодировании итеративным алгоритмом ”распространения доверия“.
Работа устроена следующим образом: в главе 2
вводятся основные понятия и определения, в главе
0
где H0 – проверка на четность длины n0 :
H0 = (1 1 . . . 1) .
| {z }
(2)
n0
Пусть π (H∗ ) обозначает матрицу, полученную из
матрицы H∗ случайной перестановкой столбцов. Тогда проверочная матрица МПП-кода Галлагера с `
слоями имеет вид:


π1 (H∗ )
 π2 (H∗ ) 


HLDPC = 
.
(3)

..


.
πl (H∗ )
`b×bn0
Все возможные независимые равновероятные перестановки столбцов в разных слоях π1 , . . . π` порождают ансамбль E (n0 , `, b) МПП-кодов Галлагера со
скоростью R ≥ 1 − `/n0 и длиной N = bn0 . МПП-коды
Галлагера могут быть также описаны с помощью
графа Таннера [10].
Определим ансамбль (N, K, ν) сверточных кодов
с (частично) единичной памятью, полученных из
блочных кодов с малой плотностью проверок, с по-
∗ Работа выполнена при поддержке гранта РФФИ 12-0731035 “мол_а”
502
активные
проверки
активные
проверки
активные
проверки
Рис. 1. Работа процессоров с проверками
кода вида

мощью полубесконечных проверочных матриц следующего вида:















H p (0)
Hc (0)
H f (1) H p (1)
Hc (1)
H f (2) H p (2)
Hc (2)
H f (3)
Gc (0)
 G f (0) G p (1)


Gc (1)


G
f (1) G p (2)


Gc (2)


G
f (2) G p (3)

..
.








,
.. 
. 

.. 
. 

..
.
(4)






,




(5)
где подматрицы Gc (t) и G f (t), G p (t) — матрицы полного ранга размеров (K 0 − ν 0 ) × N и ν 0 × N, соответственно.
3. Алгоритм декодирования
где подматрицы H p (t), H f (t) имеют размер ν × N
и выбираются независимо из ансамбля E (n0 , ν/b, b)
блочных МПП–кодов Галлагера, а подматрицы Hc (t)
имеют размер (N − K − ν) × N и выбираются независимо из ансамбля E (n0 , (N − K − ν)/b, b) блочных
МПП–кодов Галлагера. Значение ν ограничено следующими условиями: ν ≤ K, ν + K ≤ N.
Итеративный алгоритм декодирования “распространения доверия” [11] работает с графом Таннера, описывающим МПП-код. Кодовые символы соответствуют символьным вершинам в графе, а строки
проверочной матрицы – проверки на четность – соответствуют проверочным вершинам графа. На первом этапе проверочные узлы получают сообщения
от смежных с ними символьных узлов и, используя полученную информацию, формируют сообщения для символьных узлов. На втором этапе проверочные узлы посылают вновь сформированные сообщения смежным с ними символьным узлам, а те,
в свою очередь, формируют новые сообщения, которые будут посланы ими на первой фазе следующего
шага итеративного процесса декодирования.
В графе Таннера сверточного МПП-кода возможно бесконечное число символьных вершин, однако никакие символьные вершины кодовых блоков,
разнесенных более чем на m моментов времени, не
участвуют в одних и тех же проверках. Поэтому
По построению МПП–кодов Галлагера, их проверочные матрицы могут иметь неполный ранг. Будем
считать, что rk H p (t) = rk H f (t) = ν 0 ≤ ν, а rk Hc (t) =
N − K 0 − ν 0 ≤ N − K − ν. Отметим, что при b → ∞ с
вероятностью p → 1 ранги rk H p (t), rk H f (t) → ν и
rk Hc (t) → N − K − ν.
Ансамбль E pum (N, K, ν) (Ч)ЕП-МПП–кодов, ν ≤
K, ν + K ≤ N, состоит из проверочных матриц вида (4), полученных независимым случайным равновероятным выбором подматриц H p (t), Hc (t), H f (t)
из соответствующих ансамблей блочных МПП-кодов
Галлагера.
Можно показать, что проверочной матрице вида (4) соответствует порождающая матрица (Ч)ЕП-
503
10−1
10−2
Память
декодера
10−3
BER
вход
10−4
выход
10−5
10−6
0.5
300 × 10
600 × 10
300 × 10, ЦЗ
600 × 10, ЦЗ
1
2
1.5
2.5
3
3.5
Eb /N0 db
Рис. 2. Декодирование при циклическом замыкании хвоста
Рис. 3. Результаты декодирования ЕП-МПП кодов, построенных на основе блоковых (3, 6)-МПП
кодов.
непересекающиеся участки кодовой последовательности декодируются параллельно процессорами Di ,
i = 0, 1 . . .. Каждый из процессоров Di в момент времени t работает с двумя последовательными кодовыми блоками vti , vti +1 . Процессоры активируют те проверочные символы, которые должны давать нулевые
синдромы на выделенных кодовых блоках. Кодовые
последовательности сверточных кодов принято терминировать на некоторой глубине L, подавая на вход
кодера m нулевых блоков, таким образом кодирование начинается и завершается в нулевом состоянии.
Поэтому множества проверок первых двух и последних двух кодовых блоков больше, чем у промежуточных блоков. Распределение активных проверок
представлено на рис. 1.
При терминировании кодовых последовательностей сверточного кода нулевыми блоками возникает
потеря в скорости. Так, при передаче L информационных блоков длины K в канал поступает L + m кодовых блоков длины N. Результирующая скорость
m
L
· NK и потеря доли скорости составляет L+m
.
Rˆ = L+m
На практике, для избежания потерь, также используют терминирование методом “циклического замыкания хвоста” (ЦЗ). В этом случае кодирование начинается и заканчивается в одном и том же не обязательно нулевом состоянии. Проверочная матрица
получающегося блокового кода имеет вид:















H p (0)
Hc (0)
H f (1) H p (1)
Hc (1)
H f (2)
H f (L + 1)
..
.
..
.
..
.
H p (L)
Hc (L)
При циклическом замыкании хвоста первый и последний блоки терминированного (Ч)ЕП-МПП-кода
оказываются “сцепленными” и декодирование процессорами Di выполняется по кругу (рис. 2).
4. Результаты моделирования
Декодирование проводилось методом компьютерного моделирования. В качестве модели канала использовался канал с аддитивным белым гауссовским шумом (АБГШ). Декодирование проводилось для ЕП-МПП-кодов, терминированных нулевым хвостом или циклическим замыканием хвоста,
построенных из блочных (3, 6) МПП-кодов (R = 0.5)
и (5, 25) МПП-кодов (R = 0.8). Результаты декодирования представлены на рис. 3 и 5, где в подписях
вида N × L, N – длина блокового кода, L – количество
блоков, переданных в канал.
При скорости R = 0.5 терминирование нулевым
хвостом дает лучшее исправление ошибок, чем терминирование методом циклического замыкания хвоста, что объясняется существенным усилением первого и последнего блоков, которое при итеративном декодировании постепенно распространяется на
остальные блоки. Однако при высокой скорости, R =
0.8, дополнительных проверок оказывавется недостаточно, в дополнение, сказывается проигрыш в
скорости – при циклическом замыкании хвоста на
больших скоростях исправляется больше ошибок.








.






(6)
Список литературы
[1] Lee L.-N. Short Unit-Memory Byte-Oriented Binary
Convolutional Codes Having Maximal Free Distance.
504
10−2
BER
10−3
10−4
10−5
10−6
3.5
3200 × 10
4000 × 8
3200 × 10, ЦЗ
4000 × 8, ЦЗ
3.75
4
4.25
4.5
4.75
5
Eb /N0 db
Рис. 4. Результаты декодирования ЧЕП-МПП кодов, построенных на основе блоковых (5, 25)-МПП
кодов.
Рис. 5. R = 0.8
IEEE Transactions on Information Theory. 1976, pp.
349–352.
[2] Lauer G. S. Some Optimal Partial-Unit Memory Codes.
IEEE Transactions on Information Theory. 1979, vol.
23, pp. 240–243.
[3] Thommesen C., Justesen J. Bounds on distances
and error exponents of unit memory codes. IEEE
Transactions on Information Theory. 1983, vol. 29, pp.
637–649.
[4] Dettmar U., Shavgulidze S. New Optimal Partial Unit
Memory Codes. Electronic Letters. 1992, vol. 28, pp.
1748–1749.
[5] Dettmar U., Sorger U. New optimal partial unit
memory codes based on extended BCH codes. Electronic
Letters. 1993, vol. 29, pp. 2024–2025.
[6] Zyablov V.V., Sidorenko V.R. On Periodic (Partial)
Unit Memory Codes with Maximum Free Distance.
Lecture Notes in Computer Science. 1994, vol. 829, pp.
74–79.
[7] Kondrashov K.A., Zyablov. V.V. On the lower bound of
the free distance of partial unit memory codes based on
LDPC Codes Information Theory Proceedings (ISIT),
IEEE International Symposium. 2011, pp. 1831–1835.
[8] В.В. Зяблов, К.А. Кондрашов, О.Д. Скопинцев
Оценка активных расстояний сверточных кодов (частично )единичной памяти с малой плотностью проверок . Информационные процессы, Том 12, 4, 2012,
стр. 372-388.
[9] Gallager R.G. Low-Density Parity-Check Codes The
MIT Press: 1972.
[10] R. M. Tanner A recursive approach to low complexity
codes. IEEE Trans. Inf. Theory. vol. IT-27, no. 9, pp.
533–547, Sept. 1981.
[11] K. Engdahl, M. Lentmaier, K. Sh. Zigangirov On the
theory of low-density convolutional codes. AAECC-13,
vol. 1719, pp. 77–86, Springer-Verlag, 1999.
505