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

Размещено на http://www.allbest.ru/

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

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

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

Аннотация

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

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

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.

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

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

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

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

Размещено на Allbest.ru