ПОДХОД К ПОСТРОЕНИЮ БЛОЧНО-ПЕРЕСТАНОВОЧНЫХ КОДОВ С МАЛОЙ ПЛОТНОСТЬЮ ПРОВЕРОК НА ЧЕТНОСТЬ
КОДЫ, ИСПРАВЛЯЮЩИЕ ОШИБКИ
УДК 621.391
А. В. КОЗЛОВ, Е. А. КРУК, А. А. ОВЧИННИКОВ
ПОДХОД К ПОСТРОЕНИЮ БЛОЧНО-ПЕРЕСТАНОВОЧНЫХ КОДОВ С МАЛОЙ ПЛОТНОСТЬЮ ПРОВЕРОК НА ЧЕТНОСТЬ
Предложены некоторые способы построения кодов с малой плотностью проверок на четность, приводятся конструкции кодов и результаты их использования для передачи в канале с аддитивным белым гауссовым шумом.
Ключевые слова: LDPC-коды, коды Гилберта, блочно-перестановочные конструкции.
Введение и основные понятия. Коды с малой плотностью проверок на четность (LDPC-коды) были предложены Р. Галлагером в 1963 г. [1], авторы статьи [2] доказали, что они обладают уникальными свойствами. LDPC-коды обеспечивают экспоненциальное убывание вероятности ошибки с увеличением длины кода при логарифмическом росте числа операций, необходимых для декодирования одного символа кодового слова. Однако долгое время исследования в области LDPC-кодов носили в основном теоретический характер. Это было связано, прежде всего, с тем, что высокая корректирующая способность этих кодов достигается при большой длине кодовых слов (порядка нескольких тысяч символов). Реализация декодеров таких кодов представляла трудности. В последние годы развитие микроэлектронных технологий вернуло интерес к исследованиям практических аспектов применения LDPCкодов. Развитие новых стандартов связи, таких как IEEE 802.3an (10G Ethernet), IEEE 802.15.3c (передача данных на частоте 60 ГГц), IEEE 802.11n (WiFi), IEEE 802.16e (WiMAX), а также систем хранения данных — многоуровневой флэш-памяти, магнитных носителей с высокой плотностью хранения информации, требующих обеспечения скоростей декодирования в несколько гигабит в секунду, — привело к необходимости поиска методов кодирования/декодирования, способных функционировать на таких скоростях при одновременном обеспечении требуемого уровня помехоустойчивости.
LDPC-код задается своей проверочной матрицей Н, обладающей свойством разреженности, т.е. строки и столбцы матрицы содержат мало ненулевых позиций по сравнению с ее размерностью. Определим (п, γ, ρ)-код как линейный код длины n , каждый столбец и каждая строка проверочной матрицы которого содержит соответственно γ и ρ ненулевых позиций.
Минимальное расстояние Хэмминга рассматриваемых кодов, через которое определяется число исправляемых кодом ошибок, будем обозначать d0 . Расстояние LDPC-кодов, как правило, невелико, тем не менее эти коды показывают очень хорошие результаты. Связано это, с одной стороны, с хорошими спектральными свойствами кода, т.е. в коде присутствует лишь незначительное количество слов малого веса, а с другой — с особенностями работы декодера.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
10 А. В. Козлов, Е. А. Крук, А. А. Овчинников
Итеративный алгоритм декодирования LDPC-кодов принимает решения по каждому
символу в отдельности. Таким образом, даже при большом числе возникших в канале ошибок
и принятии декодером неправильного решения о кодовом слове в целом вероятность ошибки
на информационный бит для LDPC-кодов может оставаться достаточно низкой.
Несмотря на большое число публикаций [1—6] задача построения эффективных LDPC-
кодов далека от своего решения. В настоящей статье предлагаются некоторые подходы к по-
строению этих кодов.
Блочно-перестановочные конструкции. Наиболее общий подход к построению
LDPC-кодов, предложенный еще в работе Р. Галлагера [1], — использование проверочной
матрицы Н, состоящей из блоков:
⎡ H1,1 H1,2 ... H1,ρ ⎤
H=
⎢⎢H2,1
⎢ ⎢
...
H2,2 ...
... ...
H2,ρ ...
⎥ ⎥ ⎥ ⎥
.
⎢⎣Hγ,1 Hγ,2 ... Hγ,ρ ⎥⎦
(1)
В качестве блоков Hi,j могут быть выбраны, например, матрицы перестановки, в каждой строке и столбце которых содержится ровно одна единица, и тогда такая конструкция задает
регулярный LDPC-код. Наиболее часто в качестве блока рассматривается матрица цикличе-
ской перестановки, степень которой задает параметр циклического сдвига. Например, коды
такого семейства представлены в стандартах IEEE 802.16e и IEEE 802.11n.
В случае γ=2 такие коды становятся кодами Гилберта, исследованными в [6—8]:
Hl
=
⎡Im ⎢⎢⎣Im
Im C
Im C2
... ...
Im Cl −1
⎤ ⎥ ⎥⎦
,
(2)
где Im — единичная (m × m) -матрица, а С — (m × m) -матрица циклической перестановки. Такие коды имеют минимальное расстояние d0 = 4 , однако его можно повысить, выбрав другие степени С.
Теорема 1. Пусть Hl — матрица вида (2), Zl = {0, 1, ..., l −1} — множество вычетов по
модулю l −1 . Тогда в коде с проверочной матрицей Hl есть слово веса 2ω, если существуют наборы чисел {ai} , {bi} такие, что выполняется равенство:
∑ω−1
(
−1)i
( ai
−
bi
)
=
0
mod m ,
i=0
где ai ∈ Zl , bi ∈ Zl , a0 ≠ b0, aω−1 ≠ bω−1, ai ≠ ai−1, bi ≠ bi−1 .
{ }Пользуясь этой теоремой, можно показать, что если z1, ..., zρ — разностное (т, ρ, 1)-
множество, тогда код с проверочной матрицей
⎡0 0 ... 0 ⎤
H = ⎣⎢⎢Cz1
Cz2
...
C
zρ
⎥ ⎦⎥
(3)
имеет
длину п=тρ, скорость
R
=
m(ρ − 2) +1 mρ
и минимальное расстояние
d0
=6.
Обобщим конструкцию кодов Гилберта до случая γ > 2 :
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Подход к построению блочно-перестановочных кодов с малой плотностью проверок на четность 11
⎡Im ⎢⎢C0 Hs,l = ⎢⎢Ci0(3) ⎢⎢... ⎣⎢Ci0( s )
Im C1 Ci1(3) ...
Ci1( s )
Im C2 Ci1(3) ...
Ci2( s )
... Im ⎤
...
Cl −1
⎥ ⎥
...
Cil(−31)
⎥ ⎥
,
... ...
⎥ ⎥
...
Cil(−s1)
⎥ ⎦
(4)
где Hs,l — ( s × l )-матрица, i(jk) ∈{0,…, m −1} . Так как одним из параметров LDPC-кода является
длина
минимального
цикла
в
графе,
соответствующем
проверочной
матрице,
числа
i(k) j
в
лю-
{ }бой полосе k не должны повторяться. Тогда множество i(jk) : j = 0, ..., l −1 задается переста-
новкой различных вычетов целых чисел по модулю m . В этом случае кодовому слову соответствует набор связанных вложенных циклов
(рис. 1, γ=3), поэтому добавление полос может обеспечить увеличение расстояния LDPCкодов.
Рис. 1
В работе [9] предложено в качестве степеней матрицы циклической перестановки выби-
рать степени примитивного элемента матрицы Вандермонда:
⎡Im Im ...
Im ⎤
HW
=
⎢ ⎢ ⎢
Im ...
C ...
... ...
Cρ−1 ...
⎥
⎥ ⎥
,
⎢⎥
⎢⎣Im Cγ−1 ... C(γ−1)(ρ−1) ⎦⎥
(5)
где ρ ≤ m . Такие коды имеют длину п=тρ, и γ +1 ≤ d0 ≤ 2m .
Дальнейшую модификацию блочно-перестановочной конструкции (1) можно получить,
если рассмотреть в качестве варианта заполнения блока Hi,j матрицей, состоящей из всех нулей. С одной стороны, это позволяет получать нерегулярные LDPC-коды и оптимизировать
распределения весов строк и столбцов. С другой, как было показано на рис. 1, кодовым сло-
вам в блочно-перестановочной конструкции соответствуют множества вложенных циклов и
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
12 А. В. Козлов, Е. А. Крук, А. А. Овчинников
добавление нулевого блока может „разрывать“ эти циклы, уменьшая, таким образом, количество слов малого веса и улучшая спектр кода.
Выбор мест для расстановки нулевых блоков является отдельной задачей и зависит от конкретной проверочной матрицы. Несколько вариантов шаблонов, сохраняющих регулярную структуру матрицы, приведено на рис. 2.
Рис. 2
На рис. 3, 4 приведены результаты моделирования описанных конструкций в канале с аддитивным белым гауссовым шумом (BER — вероятность ошибки на информационный бит; SNR — отношение сигнал/шум). На рис. 3 сравнивается классический код Гилберта (2) при m = 29 с кодом GGC (3), вторая полоса которого образована разностным множеством {0,5,7,18,19,28}. Код Гилберта имеет минимальное расстояние d0 = 4 , а у кода на основе (3) d0 = 6 .
BER
10–2
10–3
10–4
10–5
10–6
10–7
10–8 2
34
56
7 SNR, дБ
Рис. 3
На рис. 4 представлены кривые для кодов из четырех полос. Здесь W-LDPC обозначает
выбор степеней в соответствии с матрицей Вандермонда (5) при m = 79 , ρ=8, γ=4.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Подход к построению блочно-перестановочных кодов с малой плотностью проверок на четность 13 В качестве GGC использован код с проверочной матрицей
⎡0 0 0 0 0 0 0 0 ⎤
H
=
⎢⎢0 ⎢0
5 10
12 24
15 30
16 32
29 58
35 70
37⎥⎥ 1⎥
,
⎣⎢0 15 36 45 48 14 32 38⎦⎥
(6)
где D = {0,5,12,15,16, 29, 35,37} — разностное множество, использованное для построения второй полосы проверочной матрицы. Третья и четвертая полосы получены как 2D mod 73 и 3D mod 73 соответственно. Выбранный таким образом код дает выигрыш над W-LDPC около 1 дБ при вероятности ошибки 10−6 .
BER
10–2
10–3
10–4
10–5
10–6
10–7
2
2,5 3
3,5 4 4,5 SNR, дБ
Рис. 4
Наконец, код GGCw0 соответствует проверочной матрице (6) с добавленными нулевыми блоками:
⎡0 0 0 0 0 0 0 0⎤
H
=
⎢ ⎢
0
⎢−1
−1 10
12 −1
−1 30
16 −1
−1 58
35 −1
−1⎥⎥ 1⎥
,
⎢ ⎣
0
15
36
45 48 14
32 38⎥⎦
где −1 соответствует нулевому блоку. Полученный код является регулярным LDPC-кодом с
γ=3, он дает 0,5—0,25 дБ преимущества по сравнению с первоначальным GGC кодом при од-
новременном снижении сложности декодирования, так как содержит меньше ненулевых по-
зиций в проверочной матрице. Однако этот выигрыш снижается с ростом отношения сиг-
нал/шум, так как выигрыш в спектре кода, полученный за счет нулевых блоков, дает преиму-
щество при достаточно высоком уровне шума, однако с ростом отношения сигнал/шум, когда
ошибки в канале сами по себе редки, вероятность ошибки определяется минимальным рас-
стоянием кода.
Заключение. В настоящей статье рассмотрены подходы к построению кодов с малой
плотностью проверок на четность с использованием блочно-перестановочных конструкций.
Приведены методики выбора блоков на основе разностных множеств, а также подход к улуч-
шению спектральных свойств кода на основе использования нулевых блоков.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
14 М. О. Алексеев
СПИСОК ЛИТЕРАТУРЫ
1. Gallager R. G. Low Density Parity Check Codes. Cambridge, MA: MIT Press, 1963.
2. Зяблов В. В., Пинскер М. С. Оценка сложности исправления ошибок низкоплотностными кодами Галлагера // Проблемы передачи информации. 1975. Т. XI(1). С. 23—26.
3. Белоголовый А. В., Крук Е. А. Многопороговое декодирование кодов с низкой плотностью проверок на четность // ИУС. 2005. № 1(14). С. 25—31.
4. Овчинников А. А. К вопросу о построении LDPC-кодов на основе Евклидовых геометрий // ИУС. 2005. № 1(14). С. 32—40.
5. Козлов А. В. Декодирование LDPC-кодов в дискретном канале flash-памяти // ИУС. 2007. № 5(30). С. 31—35.
6. Gilbert E. A problem in binary encoding // Proc. of the Symp. in Applied Mathematics. 1960. Vol. 10. P. 291—297.
7. Krouk E., Semenov S. Low-density parity-check burst error-correcting codes // Proc. of 2nd Intern. Workshop on Algebraic and combinatorial coding theory. Leningrad, 1990. P. 121—124.
8. Овчинников A. А. Об одном классе кодов, исправляющих пакеты ошибок // Тез. докл. 2-й Междунар. школысеминара БИКАМП'99. СПб, 1999. С. 34—35.
9. Kabatiansky G., Krouk E., Semenov S. Error correcting coding and security for data networks: Analysis of the superchannel concept. Wiley, 2005.
Сведения об авторах
Александр Владимирович Козлов — Санкт-Петербургский государственный университет аэрокосмическо-
го приборостроения, кафедра безопасности информационных систем;
ведущий программист; E-mail: akozlov@vu.spb.ru
Евгений Аврамович Крук
— д-р техн. наук, профессор; Санкт-Петербургский государственный
университет аэрокосмического приборостроения, кафедра безопасно-
сти информационных систем; E-mail: ekrouk@vu.spb.ru
Андрей Анатольевич Овчинников — канд. техн. наук, доцент; Санкт-Петербургский государственный уни-
верситет аэрокосмического приборостроения, кафедра безопасности
информационных систем; E-mail: mldoc@vu.spb.ru
Рекомендована кафедрой № 51 безопасности информационных систем
Поступила в редакцию 01.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
УДК 621.391
А. В. КОЗЛОВ, Е. А. КРУК, А. А. ОВЧИННИКОВ
ПОДХОД К ПОСТРОЕНИЮ БЛОЧНО-ПЕРЕСТАНОВОЧНЫХ КОДОВ С МАЛОЙ ПЛОТНОСТЬЮ ПРОВЕРОК НА ЧЕТНОСТЬ
Предложены некоторые способы построения кодов с малой плотностью проверок на четность, приводятся конструкции кодов и результаты их использования для передачи в канале с аддитивным белым гауссовым шумом.
Ключевые слова: LDPC-коды, коды Гилберта, блочно-перестановочные конструкции.
Введение и основные понятия. Коды с малой плотностью проверок на четность (LDPC-коды) были предложены Р. Галлагером в 1963 г. [1], авторы статьи [2] доказали, что они обладают уникальными свойствами. LDPC-коды обеспечивают экспоненциальное убывание вероятности ошибки с увеличением длины кода при логарифмическом росте числа операций, необходимых для декодирования одного символа кодового слова. Однако долгое время исследования в области LDPC-кодов носили в основном теоретический характер. Это было связано, прежде всего, с тем, что высокая корректирующая способность этих кодов достигается при большой длине кодовых слов (порядка нескольких тысяч символов). Реализация декодеров таких кодов представляла трудности. В последние годы развитие микроэлектронных технологий вернуло интерес к исследованиям практических аспектов применения LDPCкодов. Развитие новых стандартов связи, таких как IEEE 802.3an (10G Ethernet), IEEE 802.15.3c (передача данных на частоте 60 ГГц), IEEE 802.11n (WiFi), IEEE 802.16e (WiMAX), а также систем хранения данных — многоуровневой флэш-памяти, магнитных носителей с высокой плотностью хранения информации, требующих обеспечения скоростей декодирования в несколько гигабит в секунду, — привело к необходимости поиска методов кодирования/декодирования, способных функционировать на таких скоростях при одновременном обеспечении требуемого уровня помехоустойчивости.
LDPC-код задается своей проверочной матрицей Н, обладающей свойством разреженности, т.е. строки и столбцы матрицы содержат мало ненулевых позиций по сравнению с ее размерностью. Определим (п, γ, ρ)-код как линейный код длины n , каждый столбец и каждая строка проверочной матрицы которого содержит соответственно γ и ρ ненулевых позиций.
Минимальное расстояние Хэмминга рассматриваемых кодов, через которое определяется число исправляемых кодом ошибок, будем обозначать d0 . Расстояние LDPC-кодов, как правило, невелико, тем не менее эти коды показывают очень хорошие результаты. Связано это, с одной стороны, с хорошими спектральными свойствами кода, т.е. в коде присутствует лишь незначительное количество слов малого веса, а с другой — с особенностями работы декодера.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
10 А. В. Козлов, Е. А. Крук, А. А. Овчинников
Итеративный алгоритм декодирования LDPC-кодов принимает решения по каждому
символу в отдельности. Таким образом, даже при большом числе возникших в канале ошибок
и принятии декодером неправильного решения о кодовом слове в целом вероятность ошибки
на информационный бит для LDPC-кодов может оставаться достаточно низкой.
Несмотря на большое число публикаций [1—6] задача построения эффективных LDPC-
кодов далека от своего решения. В настоящей статье предлагаются некоторые подходы к по-
строению этих кодов.
Блочно-перестановочные конструкции. Наиболее общий подход к построению
LDPC-кодов, предложенный еще в работе Р. Галлагера [1], — использование проверочной
матрицы Н, состоящей из блоков:
⎡ H1,1 H1,2 ... H1,ρ ⎤
H=
⎢⎢H2,1
⎢ ⎢
...
H2,2 ...
... ...
H2,ρ ...
⎥ ⎥ ⎥ ⎥
.
⎢⎣Hγ,1 Hγ,2 ... Hγ,ρ ⎥⎦
(1)
В качестве блоков Hi,j могут быть выбраны, например, матрицы перестановки, в каждой строке и столбце которых содержится ровно одна единица, и тогда такая конструкция задает
регулярный LDPC-код. Наиболее часто в качестве блока рассматривается матрица цикличе-
ской перестановки, степень которой задает параметр циклического сдвига. Например, коды
такого семейства представлены в стандартах IEEE 802.16e и IEEE 802.11n.
В случае γ=2 такие коды становятся кодами Гилберта, исследованными в [6—8]:
Hl
=
⎡Im ⎢⎢⎣Im
Im C
Im C2
... ...
Im Cl −1
⎤ ⎥ ⎥⎦
,
(2)
где Im — единичная (m × m) -матрица, а С — (m × m) -матрица циклической перестановки. Такие коды имеют минимальное расстояние d0 = 4 , однако его можно повысить, выбрав другие степени С.
Теорема 1. Пусть Hl — матрица вида (2), Zl = {0, 1, ..., l −1} — множество вычетов по
модулю l −1 . Тогда в коде с проверочной матрицей Hl есть слово веса 2ω, если существуют наборы чисел {ai} , {bi} такие, что выполняется равенство:
∑ω−1
(
−1)i
( ai
−
bi
)
=
0
mod m ,
i=0
где ai ∈ Zl , bi ∈ Zl , a0 ≠ b0, aω−1 ≠ bω−1, ai ≠ ai−1, bi ≠ bi−1 .
{ }Пользуясь этой теоремой, можно показать, что если z1, ..., zρ — разностное (т, ρ, 1)-
множество, тогда код с проверочной матрицей
⎡0 0 ... 0 ⎤
H = ⎣⎢⎢Cz1
Cz2
...
C
zρ
⎥ ⎦⎥
(3)
имеет
длину п=тρ, скорость
R
=
m(ρ − 2) +1 mρ
и минимальное расстояние
d0
=6.
Обобщим конструкцию кодов Гилберта до случая γ > 2 :
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Подход к построению блочно-перестановочных кодов с малой плотностью проверок на четность 11
⎡Im ⎢⎢C0 Hs,l = ⎢⎢Ci0(3) ⎢⎢... ⎣⎢Ci0( s )
Im C1 Ci1(3) ...
Ci1( s )
Im C2 Ci1(3) ...
Ci2( s )
... Im ⎤
...
Cl −1
⎥ ⎥
...
Cil(−31)
⎥ ⎥
,
... ...
⎥ ⎥
...
Cil(−s1)
⎥ ⎦
(4)
где Hs,l — ( s × l )-матрица, i(jk) ∈{0,…, m −1} . Так как одним из параметров LDPC-кода является
длина
минимального
цикла
в
графе,
соответствующем
проверочной
матрице,
числа
i(k) j
в
лю-
{ }бой полосе k не должны повторяться. Тогда множество i(jk) : j = 0, ..., l −1 задается переста-
новкой различных вычетов целых чисел по модулю m . В этом случае кодовому слову соответствует набор связанных вложенных циклов
(рис. 1, γ=3), поэтому добавление полос может обеспечить увеличение расстояния LDPCкодов.
Рис. 1
В работе [9] предложено в качестве степеней матрицы циклической перестановки выби-
рать степени примитивного элемента матрицы Вандермонда:
⎡Im Im ...
Im ⎤
HW
=
⎢ ⎢ ⎢
Im ...
C ...
... ...
Cρ−1 ...
⎥
⎥ ⎥
,
⎢⎥
⎢⎣Im Cγ−1 ... C(γ−1)(ρ−1) ⎦⎥
(5)
где ρ ≤ m . Такие коды имеют длину п=тρ, и γ +1 ≤ d0 ≤ 2m .
Дальнейшую модификацию блочно-перестановочной конструкции (1) можно получить,
если рассмотреть в качестве варианта заполнения блока Hi,j матрицей, состоящей из всех нулей. С одной стороны, это позволяет получать нерегулярные LDPC-коды и оптимизировать
распределения весов строк и столбцов. С другой, как было показано на рис. 1, кодовым сло-
вам в блочно-перестановочной конструкции соответствуют множества вложенных циклов и
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
12 А. В. Козлов, Е. А. Крук, А. А. Овчинников
добавление нулевого блока может „разрывать“ эти циклы, уменьшая, таким образом, количество слов малого веса и улучшая спектр кода.
Выбор мест для расстановки нулевых блоков является отдельной задачей и зависит от конкретной проверочной матрицы. Несколько вариантов шаблонов, сохраняющих регулярную структуру матрицы, приведено на рис. 2.
Рис. 2
На рис. 3, 4 приведены результаты моделирования описанных конструкций в канале с аддитивным белым гауссовым шумом (BER — вероятность ошибки на информационный бит; SNR — отношение сигнал/шум). На рис. 3 сравнивается классический код Гилберта (2) при m = 29 с кодом GGC (3), вторая полоса которого образована разностным множеством {0,5,7,18,19,28}. Код Гилберта имеет минимальное расстояние d0 = 4 , а у кода на основе (3) d0 = 6 .
BER
10–2
10–3
10–4
10–5
10–6
10–7
10–8 2
34
56
7 SNR, дБ
Рис. 3
На рис. 4 представлены кривые для кодов из четырех полос. Здесь W-LDPC обозначает
выбор степеней в соответствии с матрицей Вандермонда (5) при m = 79 , ρ=8, γ=4.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Подход к построению блочно-перестановочных кодов с малой плотностью проверок на четность 13 В качестве GGC использован код с проверочной матрицей
⎡0 0 0 0 0 0 0 0 ⎤
H
=
⎢⎢0 ⎢0
5 10
12 24
15 30
16 32
29 58
35 70
37⎥⎥ 1⎥
,
⎣⎢0 15 36 45 48 14 32 38⎦⎥
(6)
где D = {0,5,12,15,16, 29, 35,37} — разностное множество, использованное для построения второй полосы проверочной матрицы. Третья и четвертая полосы получены как 2D mod 73 и 3D mod 73 соответственно. Выбранный таким образом код дает выигрыш над W-LDPC около 1 дБ при вероятности ошибки 10−6 .
BER
10–2
10–3
10–4
10–5
10–6
10–7
2
2,5 3
3,5 4 4,5 SNR, дБ
Рис. 4
Наконец, код GGCw0 соответствует проверочной матрице (6) с добавленными нулевыми блоками:
⎡0 0 0 0 0 0 0 0⎤
H
=
⎢ ⎢
0
⎢−1
−1 10
12 −1
−1 30
16 −1
−1 58
35 −1
−1⎥⎥ 1⎥
,
⎢ ⎣
0
15
36
45 48 14
32 38⎥⎦
где −1 соответствует нулевому блоку. Полученный код является регулярным LDPC-кодом с
γ=3, он дает 0,5—0,25 дБ преимущества по сравнению с первоначальным GGC кодом при од-
новременном снижении сложности декодирования, так как содержит меньше ненулевых по-
зиций в проверочной матрице. Однако этот выигрыш снижается с ростом отношения сиг-
нал/шум, так как выигрыш в спектре кода, полученный за счет нулевых блоков, дает преиму-
щество при достаточно высоком уровне шума, однако с ростом отношения сигнал/шум, когда
ошибки в канале сами по себе редки, вероятность ошибки определяется минимальным рас-
стоянием кода.
Заключение. В настоящей статье рассмотрены подходы к построению кодов с малой
плотностью проверок на четность с использованием блочно-перестановочных конструкций.
Приведены методики выбора блоков на основе разностных множеств, а также подход к улуч-
шению спектральных свойств кода на основе использования нулевых блоков.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
14 М. О. Алексеев
СПИСОК ЛИТЕРАТУРЫ
1. Gallager R. G. Low Density Parity Check Codes. Cambridge, MA: MIT Press, 1963.
2. Зяблов В. В., Пинскер М. С. Оценка сложности исправления ошибок низкоплотностными кодами Галлагера // Проблемы передачи информации. 1975. Т. XI(1). С. 23—26.
3. Белоголовый А. В., Крук Е. А. Многопороговое декодирование кодов с низкой плотностью проверок на четность // ИУС. 2005. № 1(14). С. 25—31.
4. Овчинников А. А. К вопросу о построении LDPC-кодов на основе Евклидовых геометрий // ИУС. 2005. № 1(14). С. 32—40.
5. Козлов А. В. Декодирование LDPC-кодов в дискретном канале flash-памяти // ИУС. 2007. № 5(30). С. 31—35.
6. Gilbert E. A problem in binary encoding // Proc. of the Symp. in Applied Mathematics. 1960. Vol. 10. P. 291—297.
7. Krouk E., Semenov S. Low-density parity-check burst error-correcting codes // Proc. of 2nd Intern. Workshop on Algebraic and combinatorial coding theory. Leningrad, 1990. P. 121—124.
8. Овчинников A. А. Об одном классе кодов, исправляющих пакеты ошибок // Тез. докл. 2-й Междунар. школысеминара БИКАМП'99. СПб, 1999. С. 34—35.
9. Kabatiansky G., Krouk E., Semenov S. Error correcting coding and security for data networks: Analysis of the superchannel concept. Wiley, 2005.
Сведения об авторах
Александр Владимирович Козлов — Санкт-Петербургский государственный университет аэрокосмическо-
го приборостроения, кафедра безопасности информационных систем;
ведущий программист; E-mail: akozlov@vu.spb.ru
Евгений Аврамович Крук
— д-р техн. наук, профессор; Санкт-Петербургский государственный
университет аэрокосмического приборостроения, кафедра безопасно-
сти информационных систем; E-mail: ekrouk@vu.spb.ru
Андрей Анатольевич Овчинников — канд. техн. наук, доцент; Санкт-Петербургский государственный уни-
верситет аэрокосмического приборостроения, кафедра безопасности
информационных систем; E-mail: mldoc@vu.spb.ru
Рекомендована кафедрой № 51 безопасности информационных систем
Поступила в редакцию 01.02.13 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8