Корректирующие свойства кодов с единичной памятью с малой плотностью проверок∗ Кондрашов К.А. ИППИ РАН [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
© Copyright 2022 DropDoc
