Архив
Том 21, 2024
Том 20, 2023
Том 19, 2022
Том 18, 2021
Том 17, 2020
Том 16, 2019 г.
Том 15, 2018 г.
Том 14, 2017 г.
Том 13, 2016 г.
Том 12, 2015 г.
Том 11, 2014 г.
Том 10, 2013 г.
Том 9, 2012 г.
Том 8, 2011 г.
Том 7, 2010 г.
Выпуск 6, 2009 г.
Выпуск 5, 2008 г.
Выпуск 4, 2007 г.
Выпуск 3, 2006 г.
Выпуск 2, 2005 г.
Выпуск 1, 2004 г.
Поиск
Найти:
Подписка/отписка
на рассылку новостей
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.