ISSN 2070-7401 (Print), ISSN 2411-0280 (Online)
Современные проблемы дистанционного зондирования Земли из космоса
физические основы, методы и технологии мониторинга окружающей среды, потенциально опасных явлений
и объектов

  

Современные проблемы дистанционного зондирования Земли из космоса. 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ПЭ без потери в эффективности декодирования.
Ключевые слова: итеративное декодирование, недвоичные (символьные) многопороговые декодеры, недвоичные самоортогональные коды, пороговый элемент, сложность декодирования
Полный текст

Список литературы:

  1. Золотарев В.В., Зубарев Ю.Б., Овечкин Г.В. Многопороговые декодеры и оптимизационная теория кодирования. М.: Горячая линия – Телеком, 2012. 239 с.
  2. Золотарев В.В., Зубарев Ю.Б., Овечкин Г.В. Обзор методов помехоустойчивого кодирования с использованием многопороговых алгоритмов // Цифровая обработка сигналов. 2008. №1. C. 2–11.
  3. Золотарев В.В., Зубарев Ю.Б., Овечкин Г.В., Дмитриева Т.А. Многопороговые алгоритмы для спутниковых сетей с оптимальными характеристиками // Электросвязь. 2006. № 10. С. 9–11.
  4. Золотарев В.В., Овечкин Г.В. Эффективное многопороговое декодирование недвоичных кодов // Радиотехника и электроника. 2010. Т. 55. № 3. С. 324–329.
  5. Овечкин Г.В., Овечкин П.В. Использование недвоичного многопорогового декодера в каскадных схемах коррекции ошибок // Вестник РГРТУ. 2009. № 4 (выпуск 30). С. 7–12.
  6. Berlekamp E. R. Algebraic Coding Theory. McGraw-Hill. New York, 1968.
  7. Massey J. Threshold decoding. M.I.T. Press. Cambridge. Massachusetts, 1963.
  8. 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. 19321941.
  9. Wu C. New list decoding algorithms for Reed-Solomon and BCH codes IEEE Transactions on Information Theory. 2008. Vol. 54. pp. 36113630.
  10. 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.