“ЖУРНАЛ РАДИОЭЛЕКТРОНИКИ” N 1, 2011

оглавление

УДК 621.391.01

АЛГОРИТМЫ ИТЕРАТИВНОГО ДЕКОДИРОВАНИЯ КОДОВ-ПРОИЗВЕДЕНИЙ С ПРОВЕРКОЙ НА ЧЕТНОСТЬ

Л. Е. Назаров¹, И. В. Головкин²

¹Институт радиотехники и электроники им. В.А.Котельникова РАН, г.Фрязино

²ОАО “Российские космические системы”, г. Москва


Получена 18 января 2010 г.

 

Аннотация. Приведены описания и результаты моделирования алгоритмов итеративного декодирования кодов-произведений, формируемых на основе простейших кодов с проверкой на четность.

Ключевые слова: коды-произведения, турбо-коды, низкоплотностные коды, итеративное декодирование.

Abstract. The results of simulation of iterative decoding for product codes based on single-parity check codes are presented in the article.

Key words: product-codes, turbo-codes, low density parity check codes, iterative decoding.


Введение

Помехоустойчивые коды применяются в цифровых системах связи с целью повышения надежности передачи информации по радиофизическим каналам [1]. Рассматриваемые в настоящей статье кодовые конструкции входят в класс помехоустойчивых кодов, известных в литературе как коды-произведения [1].

Особенностью рассматриваемых кодов-произведений является то, что они формируются на основе простейших блоковых кодов с одним проверочным символом. Они обладают рядом замечательных свойств, определяющих перспективность их использования и их исследованию посвящен ряд работ [2,3,4,5]. Эти коды находят применение в системах связи широкого назначения, в частности, в оптических системах связи и в системах магнитной записи [3,4]. Это обусловливает актуальность проблемы разработки и исследования эффективных алгоритмов их декодирования.

В статье приведены описания и результаты моделирования ряда алгоритмов итеративного декодирования рассматриваемых кодов-произведений, дается сравнительный анализ эффективности этих алгоритмов.


1. Постановка задачи

Помехоустойчивые коды с параметрами  задаются порождающими матрицами размером  либо проверочными матрицами размером  [1]. Здесь ,  - длительность последовательностей символов кодовых слов и информационных символов.

Порождающие матрицы рассматриваемых кодов-произведений эквивалентны двумерной матрице - ее строки и столбцы являются кодовыми словами блоковых кодов ,  с параметрами , . Коды ,  являются простейшими кодами с проверкой на четность. Длительность кодовых слов этих кодов-произведений равна , информационный объем равен , кодовая скорость равна .

Разработка эффективных алгоритмов декодирования кодов-произведений, формируемых на основе блоковых кодов с проверкой на четность, составляет суть рассматриваемой задачи. Ниже приведены описания наиболее эффективных алгоритмов декодирования, основу которых составляют свойства данных кодов-произведений, рассматриваемых как турбо-коды и как низкоплотностные коды.
 

2. Декодирование кодов-произведений, рассматриваемых как турбо-коды

Пусть  - последовательность информационных символов, образующих матрицу в составе матрицы кодового слова  кода-произведения;  - реализация на входе декодера, отсчеты которой представляют сумму сигнальной и помеховой компонентов.

Рассматриваемые коды-произведения относятся к классу блоковых турбо-кодов [5]. Поэтому при их декодировании может быть применен формализованный подход, общий для декодирования турбо-кодов [6]. Его основу составляет итеративная обработка реализации . Итерация включает выполнение двух этапов.

На первом этапе -ой итерации вычисляются величины  для символов ,  кодового слова  кода . На основе  вычисляются приращения апостериорных вероятностей символов

.                   (1)

 

Здесь  - реализации в составе , соответствующие кодовым словам , образующих строки матрицы ; ,  - отношения условных плотностей вероятностей для  и отношения априорных вероятностей для .

На втором этапе -ой итерации подобная процедура выполняется для вычисления приращений апостериорных вероятностей  символов ,  кодового слова  блокового кода , образующего столбцы матрицы . Приращения апостериорных вероятностей  используются как отношения априорных символьных вероятностей для первого этапа ()-ой итерации .

На последней итерации принимается решение  при условии , иначе .

Общее соотношение для вычисления  на основе  и  имеет вид

.                                 (2)

При вычислении (2) требуется оценка параметра сигнал/помеха, что усложняет процедуру итеративного декодирования. В приложениях применяются простые выражения, являющиеся приближением к (2). Ниже рассмотрены два наиболее эффективных алгоритма приближенного вычисления . При их использовании не требуется оценка энергетического параметра.

Первое приближение к выражению (2) для канала с аддитивным белым гауссовским шумом (АБГШ канал) и для символов составляющего кода с проверкой на четность имеет вид

.          (3)

Здесь , если  и , если .

Алгоритм вычисления  в этом случае может быть представлен последовательностью следующих шагов:

1) на основе последовательности отсчетов  вычисляется последовательность “жестких” решений: , если , иначе , и вычисляется сумма ;

2) вычисляется минимальное значение ;

3) вычисляются нормализованные значения  по правилу .

Второе приближение к (2) имеет вид

.                               (4)

Соответствующий алгоритм вычисления  для АБГШ канала и для кода с проверкой на четность может быть записан как последовательность следующих шагов:

1) на основе последовательности  формируется последовательность “жестких” решений: , если , иначе , и вычисляется сумма ;

2) вычисляются первый и второй минимальные значения ,  и их номера  для последовательности ;

3) вычисляются нормализованные значения , если , иначе .


3. Декодирование кодов-произведений, рассматриваемых как низкоплотностные коды

Рассматриваемые коды-произведения входят в класс низкоплотностных кодов и при их декодировании можно применять методы, разработанные для низкоплотностных кодов, в частности, аппарат графов. Вершины графа, соответствующие кодовым символам, соединены с вершинами графа, соответствующим проверочным соотношениям, включающим эти символы. На рис.1 приведен вид графа для кода-произведения, формируемого на основе кода (3,2) (длительность кодовых слов равна 9, информационный объем 4 бита).

Рис.1. Граф для кода-произведения, формируемого на основе кода (3,2).

 

Видно, что для каждого кодового символа ,,,,,,,, существуют два проверочных соотношения на четность для последовательностей длительностью  и . Эти последовательности имеют лишь один общий элемент. Данные свойства являются общими для исследуемых кодов-произведений с произвольными параметрами ().

Алгоритм MIN_SUM_BP (belief propagation) является наиболее эффективным алгоритмом декодирования низкоплотностных кодов. При его использовании не требуется оценка энергетического параметра. Данный алгоритм декодирования также итеративный.

Перед выполнением итерации производится инициализация величин , ; .

Итерация включает выполнение следующих шагов обработки последовательностей :

1) формируются две последовательности “жестких” решений: , если , иначе , и вычисляются суммы  ();

2) вычисляются минимальные значения  и ;

3) для каждого кодового символа вычисляются последовательности нормализованных значений  и  по правилу , ; .

4) для каждого кодового символа вычисляются новые величины , .

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

Ниже приведены результаты исследования вероятностных характеристик рассматриваемых кодов-произведений, полученные путем компьютерного моделирования процедур итеративного декодирования.
 

4. Результаты моделирования

Анализ процедур декодирования кодов-произведений, реализующих принцип итеративного декодирования блоковых турбо-кодов, показывает, что приведенные два алгоритма (3) и (4) практически эквивалентны относительно их сложности, определяемой требуемым объемом памяти и объемом вычислительных операций при выполнении одной итерации. Сложность выполнения итерации алгоритма декодирования MIN_SUM_BP, реализующего принцип декодирования низкоплотностных кодов, превышает почти в два раза сложность алгоритмов (3) и (4).

Путем компьютерного моделирования показано также, что для  алгоритмов итеративного декодирования (3) и (4), реализующих принцип декодирования турбо-кодов, применение пяти итераций обеспечивает сходимость вероятностных характеристик. Для алгоритма декодирования MIN_SUM_BP, реализующего принцип декодирования низкоплотностных кодов, необходимое число итераций превышает 15.

 

Рис.2. Зависимости вероятности ошибки  от отношения  для кода-произведения с кодовой скоростью , формируемого на основе блокового кода с проверкой на четность (58,57): 1 - применение алгоритма итеративного декодирования (3); 2 - применение алгоритма итеративного декодирования (4); 3 - применение алгоритма декодирования MIN_SUM_BP.

 

На рис.2 приведены зависимости вероятности ошибки на бит  от отношения сигнал/помеха  при применении рассмотренных алгоритмов итеративного декодирования для кода-произведения с кодовой скоростью , формируемого на основе блокового кода с проверкой на четность (58,57): длительность кодовых слов равна , информационный объем равен . Здесь - энергия сигналов на бит,  - одностороння спектральная плотность помех. Кривая 1 относится к случаю применения процедуры итеративного декодирования с использованием алгоритма вычисления функции отношения апостериорных символьных вероятностей (2), соответствующего первому приближению (3). Кривая 2 относится к случаю применения процедуры итеративного декодирования с использованием алгоритма вычисления функции отношения апостериорных символьных вероятностей, соответствующего второму приближению (4). Видно, что эти вероятностные кривые практически совпадают для значений , для больших значений вероятностей ошибки процедура итеративного декодирования на основе второго приближения (4) является более эффективной, чем процедура итеративного декодирования на основе алгоритма вычисления функции отношения апостериорных символьных вероятностей, соответствующего первому приближению (3).

Кривая 3 относится к случаю применения алгоритма декодирования MIN_SUM_BP, реализующего принцип декодирования низкоплотностных кодов. Видно, что эта кривая практически совпадает с вероятностной кривой 2 для анализируемых значений вероятностей ошибки . Следует также отметить, что вероятность ошибки  в этом случае достигается при  дБ что отличается лишь на 1.5 дБ от предела Шеннона для дискретно-непрерывного канала с аддитивным белым гауссовским шумом и с использованием сигналов с двоичной фазовой манипуляцией, соответствующих кодам с кодовой скоростью 0.966.
 

Заключение

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

Показано, что код-произведение из рассматриваемого класса с кодовой скоростью 0.966 и информационным объемом 3249 битов в совокупности с разработанным алгоритмом итеративного декодирования обеспечивает достижение вероятности ошибки на бит  при отношении  дБ, что отличается лишь на 1.5 дБ от предела Шеннона для дискретно-непрерывного канала с аддитивным белым гауссовским шумом и с использованием сигналов с двоичной фазовой манипуляцией, соответствующих кодам с кодовой скоростью 0.966.

 

Литература

1. Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. Пер. с англ. М.: Радио и связь., 1987. 390 с.

2. Jing Li., Narayanan R., Georghiades .N. Product accumulate codes: a class of codes with near-capacity performance and low decoding complexity. //IEEE Transactions on Information Theory. 2004. V.50. N1. P.31-46.

3. Farhadi G., Jamali S.H. Performance Analysis of Fiber-Optic BPPM CDMA Systems With Single Parity-Check Product Codes. // IEEE Transactions on Communications. 2006. V.54. N9. P.1643-1653.

4. Li J., Narayanan R., Kurtas E., Georghiades C.N. On the Performance of High-Rate TPC/SPC Codes and LDPC Codes Over Partial Response Channels. // IEEE Transactions on Communications. 2002. V.50. N5. P.723-734.

5. Ping Li, Chan S., Yeng K.L. Efficient soft-in-soft-out sub-optimal decoding rule for single parity check codes.// Electronic Letters. 1997. V.33. N19. P.1614-1616.

6. Hagenauer J., Offer E., Papke L. Iterative decoding of binary block and convolutinal codes. // IEEE Transactions on Information Theory. 1996. V.42. N2. P.429-448.