ЖУРНАЛ РАДИОЭЛЕКТРОНИКИ" N 9, 2014

оглавление

УДК 621.391.01

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

Л. Е. Назаров, В. В. Батанов, О. О. Кузнецов

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

Статья получена 17 сентября 2014 г.

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

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

Abstract. This paper presents the symbol-by-symbol decoding algorithms for serial block turbo-codes (block product codes) based on simple single-parity-check codes.

Key words: block product codes, iterative decoding, word-rate rate.

 

Введение

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

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

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

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

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

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

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

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

2. Алгоритмы итеративного приема турбо-кодов на основе составляющих блоковых кодов с проверкой на четность

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

.                                          (1)

Здесь  - амплитуда сигналов с двоичной фазовой манипуляцией (ФМ2),  - помеховая компонента аддитивного белого гауссовского шума с односторонней спектральной плотностью .

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

Перед выполнением итерации алгоритма MIN_SUM_BP для посимвольного приема кодового символа  производится инициализация величин ,  и , . Итерация включает выполнение следующих шагов обработки последовательностей ,  [8]:

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

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

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

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

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

Более сложным по отношению к изложенному алгоритму MIN_SUM_BP является алгоритм итеративного посимвольного приема BP (belief propagation) [7]. При использовании алгоритма BP требуется оценка энергетического параметра канала, однако, в общем случае этот алгоритм является более эффективным, чем алгоритм MIN_SUM_BP по отношению к вероятностно-энергетическим характеристикам. Приведем описание алгоритма BP.

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

1) вычисляются элементы массивов  и массива

,                                 (2)

,                              (3)

,                                                 (4)

.                                              (5)

 

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

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

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

Точное вычисление вероятностных характеристик (вероятность ошибочного приема кодовых слов , вероятность ошибочного приема информационных битов ) при оптимальном приеме сигналов представляет сложную проблему [1]. Аналитические выражения относительно  при наличии канального аддитивного белого гауссовского шума и при реализации правила максимального приема известны лишь для ограниченного класса ансамблей сигналов, включающего ансамбли ортогональных и биортогональных сигналов, ансамбли симплексных сигналов. Более сложной является задача оценивания вероятностных характеристик для оптимального посимвольного приема [9,10].

Вследствие этого оценивание вероятностных характеристик исследуемых ансамблей сигналов производится с использованием формульных соотношений, определяющих верхние границы вероятностей  и . Для ансамблей сигналов известны верхние границы , наиболее используемой из которых является аддитивная граница [1]. Более точной по отношению к аддитивной границе является мультипликативная граница при эквивалентной сложности их вычисления, которая применяется для сигналов с манипуляцией ФМ2 на основе линейных блоковых двоичных кодов [11]

.                               (6)

Здесь  - энергия сигналов на бит,  - количество кодовых слов с весом Хэмминга ,  - длительность кодовых слов.

Известно соотношение, определяющее связь  и  [1]

.                                                           (7)

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

При вычислении соотношения (6) необходимо знание спектра расстояний Хэмминга . Для рассматриваемых турбо-кодов относительно  известно выражение [5]

,                  (8)

.                                          (9)

Количество кодовых слов  с расстоянием Хэмминга  соответствует множителю при слагаемом  в многочлене (8).

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

Требуемое количество вычислительных экспериментов  определяется размером доверительного интервала, вероятностью , доверительной вероятностью . При условии  справедливо соотношение [12]

,             (10)

.                                       

Например, для ,  (доверительный интервал []),  требуемое количество экспериментов, вычисленное с использованием (10), оценивается значением >1540000.

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

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

Результаты моделирования показали, что приведенные алгоритмы итеративного посимвольного приема MIN_SUM_BP и BP рассматриваемых турбо-кодов эквивалентны относительно их вероятностно-энергетических характеристик для АБГШ канала.

В качестве примера на рис.1 приведены полученные зависимости вероятности ошибки на бит  и вероятности ошибки на кодовое слово  от отношения сигнал/помеха  при применении рассмотренных алгоритмов итеративного приема для турбо-кода, формируемого на основе блокового кода с проверкой на четность (10,9): длительность кодовых слов равна , информационный объем равен  при наличии АБГШ. Единая кривая 1 и кривая 2 относятся к случаю применения алгоритмов итеративного приема MIN_SUM_BP и BP и соответствуют вероятности ошибки на информационный бит  и на кодовое слово .

 

Рис.1. Вероятности ошибки на бит  (кривая 1) и вероятности ошибки на кодовое слово  (кривая 2)
при применении алгоритмов итеративного приема
MIN_SUM_BP и BP для турбо-кода на основе блокового код
 с проверкой на четность (10,9) при наличии АБГШ:
3 - верхняя мультипликативная граница для ; 4 - верхняя граница для .

Кривая 3 и кривая 4 на рис.1 соответствуют верхней мультипликативной границе для вероятности ошибки на кодовое слово  (6) и границе для вероятности ошибки на информационный бит  (7) для рассматриваемого турбо-кода. Вычисление спектра расстояний Хэмминга  произведено с использованием соотношений (8), (9). Вид спектра приведен на рис.2, количество кодовых векторов с минимальным расстоянием Хэмминга  равно 2025.

 

Рис.2. Спектр расстояний Хэмминга  турбо-кода, формируемого на основе блокового кода
с проверкой на четность (10,9): длительность кодовых слов , информационный объем
(
количество кодовых векторов с минимальным расстоянием Хэмминга  равно 2025).

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

На рис.3 приведены вероятностные характеристики алгоритмов итеративного приема MIN_SUM_BP и BP для турбо-кода на основе блокового кода с проверкой на четность (10,9) при наличии АБГШ и при релеевских замираниях сигналов. Кривые получены путем моделирования алгоритмов приема. По оси абсцисс отложены средние значения сигнал/помеха. Кривая 1 и кривая 2 соответствуют вероятностям ошибки на бит  для алгоритма BP и для алгоритма MIN_SUM_BP, полагая известным энергетический параметр канала . Кривая 3 и кривая 4 соответствуют вероятностям ошибки на кодовое слово  для алгоритма BP и для алгоритма MIN_SUM_BP. Видно, что в этом случае энергетический проигрыш при применении алгоритма MIN_SUM_BP по отношению к алгоритму ВР достигает 0.8 дБ.

 

Рис.3. Вероятностные характеристики алгоритмов итеративного приема для турбо-кода на основе блокового код
 с проверкой на четность (10,9) при наличии АБГШ и при релеевских замираниях сигналов (по оси абсцисс
отложены средние значения сигнал/помеха):
1 - вероятности ошибки на бит  для алгоритма ВР;
2 - вероятности  для алгоритма
MIN_SUM_BP;
3 - вероятности ошибки на кодовое слово  для алгоритма
BP;
4 - вероятности ошибки  для алгоритма
MIN_SUM_BP.

Заключение

Приведены описания алгоритмов MIN_SUM_BP и BP (belief propagation) итеративного приема турбо-кодов, формируемых на основе простейших блоковых кодов с одним проверочным символом.

Приведены методики оценивания вероятностных характеристик рассматриваемых турбо-кодов при использовании алгоритмов их итеративного приема.

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

Для канала с релеевскими замираниями сигналов и АБГШ энергетический проигрыш при применении алгоритма MIN_SUM_BP по отношению к алгоритму ВР, требующему знания относительно энергетического параметра канала передачи, достигает 0.8 дБ.

 

Литература

1. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир. 1976. 594 с.

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

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. 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.

6. Назаров Л.Е., Головкин И.В. Последовательные высокоскоростные турбо-коды с пониженной сложностью алгоритмов приема. // Радиотехника и электроника. 2010. Т.55. №10. Стр.1193-1199.

7. 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.

8. Назаров Л.Е., Головкин И.В. Алгоритмы итеративного декодирования кодов-произведений с проверкой на четность. // Журнал радиоэлектроники [электронный журнал]. 2011. №1. URL: http://jre.cplire.ru/jan11/3/text.pdf

9. Назаров Л.Е. Вероятностные характеристики при оптимальном посимвольном приеме сигналов, соответствующих двоичным блоковым кодам. // Радиотехника и электроника. 1999. Т.44. №10. Стр. 1231-1235.

10. Назаров Л.Е., Головкин И.В. Границы ошибки при посимвольном приеме сигналов на основе линейных блоковых кодов. // Известия Вузов. Электроника. 2009. №5. Стр.44-49.

11. Смольянинов В.М., Назаров Л.Е. Мультипликативная граница вероятности правильного распознавания при когерентном приеме. // Радиотехника и электроника. 1987. Т.32. №2. Стр. 446-449.

12. Дунин-Барковский И.В., Смирнов Н.В. Теория вероятностей и математическая статистика в технике. М.: Гос. издательство технико-теоретической литературы. 1955. 556 с.