Современные проблемы дистанционного зондирования Земли из космоса. 2014. Т. 11. №2. С. 138-151
Методы ускорения алгоритмов декодирования символьных кодов
В.В. Золотарев
1 , И.В. Чулков
1 , Г.В. Овечкин
1 , Д.Ж. Сатыбалдина
2 1 Институт космических исследований РАН, Москва, Россия
2 Евразийский национальный университет им. Л.Н. Гумилева, Астана, Республика Казахстан
В некоторых системах передачи и хранения данных предпочтительнее использовать недвоичные помехоустойчивые коды. Показано, что известные символьные помехоустойчивые коды, такие как коды Рида-Соломона и q-ичные низкоплотностные коды, обладают низкой эффективностью или высокой сложностью реализации. Также рассмотрены недвоичные многопороговые декодеры (qМПД) символьных самоортогональных кодов (qСОК). Показано, что qМПД выполняет почти оптимальное декодирование qСОК с низким уровнем размножения ошибок всего лишь с линейной зависимостью сложности реализации от длины кода. Анализируется сложность реализации символьного порогового элемента (qПЭ), являющегося единственным вычислительно сложным блоком qМПД. Показано, что сложность обычной программной реализации qПЭ пропорциональна d2, где d – кодовое расстояние. Предложены несколько методов ускорения работы qПЭ, обладающие разными требованиями к оперативной памяти. Данные методы обеспечивают существенное уменьшение числа выполняемых арифметических операций по сравнению с неоптимизированной реализацией qПЭ. Лучший из предложенных методов обеспечивает линейную зависимость числа выполняемых операций от кодового расстояния применяемого кода. В результате оказывается возможным увеличить быстродействие qМПД для типичных параметров кодов в 2 и более раз по сравнению со стандартным алгоритмом работы qПЭ без потери в эффективности декодирования.
Ключевые слова: итеративное декодирование, недвоичные (символьные) многопороговые декодеры, недвоичные самоортогональные коды, пороговый элемент, сложность декодирования
Полный текстСписок литературы:
- Золотарев В.В., Зубарев Ю.Б., Овечкин Г.В. Многопороговые декодеры и оптимизационная теория кодирования. М.: Горячая линия – Телеком, 2012. 239 с.
- Золотарев В.В., Зубарев Ю.Б., Овечкин Г.В. Обзор методов помехоустойчивого кодирования с использованием многопороговых алгоритмов // Цифровая обработка сигналов. 2008. №1. C. 2–11.
- Золотарев В.В., Зубарев Ю.Б., Овечкин Г.В., Дмитриева Т.А. Многопороговые алгоритмы для спутниковых сетей с оптимальными характеристиками // Электросвязь. 2006. № 10. С. 9–11.
- Золотарев В.В., Овечкин Г.В. Эффективное многопороговое декодирование недвоичных кодов // Радиотехника и электроника. 2010. Т. 55. № 3. С. 324–329.
- Овечкин Г.В., Овечкин П.В. Использование недвоичного многопорогового декодера в каскадных схемах коррекции ошибок // Вестник РГРТУ. 2009. № 4 (выпуск 30). С. 7–12.
- Berlekamp E. R. Algebraic Coding Theory. McGraw-Hill. New York, 1968.
- Massey J. Threshold decoding. M.I.T. Press. Cambridge. Massachusetts, 1963.
- Ullah M.A., Okada K., Ogivara H. Multi-Stage Threshold Decoding for Self-Orthogonal Convolutional Codes. IEICE Trans. Fundamentals. 2010. Vol. E93-A. No.11. pp. 19321941.
- Wu C. New list decoding algorithms for Reed-Solomon and BCH codes IEEE Transactions on Information Theory. 2008. Vol. 54. pp. 36113630.
- Zhang F., Pfister H. List-Message Passing Achieves Capacity on the q-ary Symmetric Channel for Large q // Proc. IEEE Global Telecom. Conf. Washington, DC. Nov. 2007. pp. 283–287.