УДК 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]
Здесь 
-
энергия сигналов на бит, 
- количество кодовых
слов с весом Хэмминга 
, -
длительность кодовых слов.
Известно соотношение,
определяющее связь и [1]
Соотношения (6), (7) используются для оценивания вероятностей ошибочных решений для алгоритмов оптимального приема, реализующих правило максимального правдоподобия и правило посимвольного приема соответственно.
При вычислении
соотношения (6) необходимо знание спектра расстояний Хэмминга . Для рассматриваемых турбо-кодов
относительно известно выражение [5]
Количество кодовых слов с расстоянием Хэмминга соответствует множителю при слагаемом 
в многочлене (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 с.