Современные проблемы дистанционного зондирования Земли из космоса. 2020. Т. 17. № 4. С. 9-26
Обзор проблем полярных кодов с позиции технологий Оптимизационной Теории помехоустойчивого кодирования
Н.А. Кузнецов
1 , В.В. Золотарев
2 , Г.В. Овечкин
3 , Р.Р. Назиров
2 , Д.Ж. Сатыбалдина
4 , Е.Д. Омирбаев
4 1 Институт радиотехники и электроники им. В.А. Котельникова РАН, Москва, Россия
2 Институт космических исследований РАН, Москва, Россия
3 Рязанский государственный радиотехнический университет имени В.Ф. Уткина, Рязань, Россия
4 Евразийский национальный университет им. Л.Н. Гумилева, Астана, Республика Казахстан
Одобрена к печати: 29.06.2020
DOI: 10.21046/2070-7401-2020-17-4-9-26
Рассмотрена общая ситуация в прикладных вопросах теории кодирования. Изложены основные проблемы, возникающие в области декодирования помехоустойчивых кодов. Особое внимание наряду с корректирующей способностью уделяется вычислительной сложности данных алгоритмов. Представлены последние результаты в области алгоритмов декодирования для полярных кодов (ПК), изложены основные проблемы их развития. Выполнено сопоставление прикладных результатов Оптимизационной Теории (ОТ) и имеющихся крайне ограниченных материалов для ПК. Кратко упомянуты результаты для низкоплотностных кодов. Представлены результаты сравнительного анализа характеристик ПК и блоковой версии алгоритма Витерби для коротких кодов. Также выполнено сравнение возможностей ПК и многопороговых декодеров алгоритмов, в том числе и при использовании каскадирования. Даны основные направления развития и улучшения характеристик алгоритмов ОТ. По итогам сравнения сделан вывод о безусловном лидерстве ОТ и об отсутствии необходимости применения ПК и ряда других кодов где-либо вообще в силу неизбежно слабых возможностей и большого списка недостатков декодеров этих направлений и методов их разработок в исследованиях для новых проектов спутниковой и космической связи, а также для систем дистанционного зондирования Земли.
Ключевые слова: граница Шеннона, пропускная способность канала, сложность алгоритмов, полярные коды, списочное декодирование, оптимальное декодирование, Оптимизационная Теория, блоковый алгоритм Витерби, коды Рида – Соломона, низкоплотностные и турбо-коды, многопороговые декодеры, параллельное каскадирование, дивергентный принцип, декодеры с прямым контролем метрики
Полный текстСписок литературы:
- Афанасьев В. Б., Давыдов А. А., Зигангиров Д. К. Оценка доли стираний, исправляемых линейными кодами // Информац. процессы. 2016. Т. 16. № 4. С. 352–404.
- Зигангиров Д. К., Зигангиров К. Ш. Декодирование низкоплотностных кодов с проверочными матрицами, составленными из перестановочных матриц, при передаче по каналу со стираниями // Проблемы передачи информации. 2006. Т. 42. Вып. 2. С. 44–52.
- Золотарёв В. В. Многопороговое декодирование в недвоичных каналах // Вопросы радиоэлектроники. Сер. ЭВТ. 1984. Вып. 12. С. 73–76.
- Золотарёв В. В. Теория и алгоритмы многопорогового декодирования / под ред. Ю. Б. Зубарева. М.: Изд-во «Горячая линия – Телеком», 2006. 266 с. URL: https://mtdbest.ru/articles/теория и алгоритмы 2006.pdf.
- Золотарёв В. В. Теория кодирования как задача поиска глобального экстремума (Оптимизационная Теория помехоустойчивого кодирования — новая «квантовая механика» теории информации) / под ред. Н. А. Кузнецова. М.: Изд-во «Горячая линия – Телеком», 2018. 222 с.
- Золотарёв В. В., Овечкин Г. В. Помехоустойчивое кодирование. Методы и алгоритмы: справ. М.: Изд-во «Горячая линия – Телеком», 2004. 126 с.
- Золотарёв В. В., Овечкин Г. В. Эффективное многопороговое декодирование недвоичных кодов // Радиотехника и электроника. 2010. Т. 55. № 3. С. 324–329.
- Золотарёв В. В., Овечкин Г. В. Применение многопороговых методов декодирования помехоустойчивых кодов в высокоскоростных системах передачи данных // Электросвязь. 2014. № 12. С. 10–14.
- Золотарёв В. В., Овечкин Г. В. О сопоставлении новых методов помехоустойчивого кодирования // Докл. 18-й Международ. конф. «Цифровая обработка сигналов и ее применение». М., 2016. Т. 1. С. 59–65.
- Золотарёв В. В., Овечкин П. В. Способ кодирования и декодирования блокового кода с использованием алгоритма Витерби. Патент РФ 2608872. Рег. 25.01.2017.
- Золотарёв В. В., Зубарев Ю. Б., Овечкин Г. В. Многопороговые декодеры и оптимизационная теория кодирования / под ред. В. К. Левина. М.: Изд-во «Горячая линия — Телеком», 2012. 238 с.
- Золотарёв В. В., Зубарев Ю. Б., Овечкин Г. В., Аверин С. В., Овечкин П. В. 25 лет оптимизационной теории кодирования: новые перспективы // Материалы 18-й Международ. научно-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». М.: Изд во «Горячая линия – Телеком», 2015. С. 10–17.
- Золотарёв В. В., Овечкин Г. В., Назиров Р. Р. О передаче Оптимизационной Теории лидерства от прикладной классической теории помехоустойчивого кодирования // Некоторые аспекты современных проблем механики и информатики: сб. науч. ст. М.: ИКИ РАН, 2018. С. 82–90.
- Зубарев Ю. Б., Золотарёв В. В., Овечкин Г. В. Новые технологии и парадигмы помехоустойчивого кодирования: после решения проблемы Шеннона // Электросвязь. 2019. № 9. С. 56–61. URL: http://www.mtdbest.ru/articles/elsv2020.pdf.
- Зяблов В. В., Рыбин П. С. Исправление стираний кодами с малой плотностью проверок // Проблемы передачи информации. 2009. Т. 45. Вып. 3. С. 15–32.
- Зяблов В. В., Рыбин П. С. Анализ связи свойств МПП-кодов и графа Таннера // Проблемы передачи информации. 2012. Т. 48. Вып. 4. С. 3–29.
- Зяблов В. В., Йоханнессон Р., Лончар М. Просто декодируемые коды с малой плотностью проверок на основе кодов Хемминга // Проблемы передачи информации. 2009. Т. 45. Вып. 2. С. 25–40.
- Кудряшов Б. Д. Основы теории кодирования: учебное пособие для вузов. СПб.: БХВ-Санкт-Петербург, 2016. 393 с.
- Кузнецов Н. А., Золотарёв В. В., Овечкин Г. В., Овечкин П. В. Недвоичные многопороговые декодеры и другие методы коррекции ошибок в символьной информации // Радиотехника. 2010. № 6. Вып. 141. С. 4–9.
- Кузнецов Н. А., Золотарёв В. В., Зубарев Ю. Б., Овечкин Г. В., Назиров Р. Р., Аверин С. В. Проблемы и открытия Оптимизационной Теории помехоустойчивого кодирования. М.: ИКИ РАН, 2020. 36 c. URL: http://www.mtdbest.ru/articles/comics.pdf.
- Магаршак Ю. Число, возведенное в абсолют // Независимая газета. 09.09.2009. URL: https://www.ng.ru/science/2009-09-09/11_maths.html.
- Милославская В. Д. Методы построения и декодирования полярных кодов: дис. ... канд. техн. наук. СПб., 2015. 206 с.
- Морозов Р. А. Декодирование полярных кодов с помощью алгоритма Думера – Шабунова // Список-2013: материалы всероссийской науч. конф. по проблемам информатики. 23–26 апр. 2013, Санкт-Петербург. СПб.: Изд-во ВВМ, 2013. С. 261–262. URL: spisok.math.spbu.ru/2013/txt/papers/s7_1.odt.
- Назаров Л. Е., Щеглов М. А. Характеристики полных и укороченных помехоустойчивых низкоплотностных кодов на основе конечных геометрий // Успехи современной радиоэлектроники. 2017. № 6. С. 38–48.
- Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976. 594 с.
- Трифонов П. В. Методы построения и декодирования многочленных кодов: дис. ... д-ра техн. наук. СПб., 2018. 254 с.
- Федоренко С. В. Методы быстрого декодирования линейных блоковых кодов. СПб., 2008. 198 с.
- Ammar H. Optimisation and analysis of polar codes in communication systems: Doctoral Thesis. University of Manchester, 2018. 177 p.
- Arikan E. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels // IEEE Trans. Information Theory. 2009. V. 55. No. 7. P. 3051–3073.
- Dumer I., Shabunov K. Soft-Decision Decoding of Reed-Muller Codes: Recursive Lists // IEEE Trans. Information Theory. 2006. V. 52. No. 3. P. 1260–1266.
- Giard P., Sarkis G., Thibeault C., Gross W. J. Fast Software Polar Decoders // Proc. IEEE Intern. Conf. Acoustics, Speech and Signal Processing (ICASSP). 2014. 5 p.
- Ozgur U. A Performance Comparison of Polar Codes with Convolutional Turbo Codes: Doctoral Thesis. 2009. 166 p.
- Sarkis G., Giard P., Vardy A., Thibeault G., Gross W. J. Fast list decoders for polar codes // IEEE J. Selected Areas in Communications. 2016. V. 34. No. 2. P. 318–328.
- Seidl M., Huber J. B. An Efficient Length- and Rate-Preserving Concatenation of Polar and Repetition Codes // Computer Science, Mathematics. 2013.
- Tal I., Vardy A. List decoding of polar codes // IEEE Trans. Information Theory. 2015. V. 61. P. 2213–2226.
- Zolotarev V. V. Coding Theory as a Simple Optimal Decoding near Shannon’s Bound. Optimization Theory of error-correcting coding — is a new “quantum mechanics” of information theory. M.: Hot Line – Telecom, 2018. 333 p. URL: https://mtdbest.ru/articles/mtd_book_2019.pdf.
- Zolotarev V. V., Zubarev Yu. B., Ovechkin G. V. Optimization Coding Theory and Multithreshold Algorithms. Switzerland: ITU, 2015. 158 p. URL: https://mtdbest.ru/articles/Zolotarev_ITU.pdf.
- Zolotarev V., Ovechkin G., Ovechkin P., Satybaldina D., Tashatov N., Sankibayev D. High Throughput Software Multithreshold Decoder on GPU // 3rd Intern. Conf. Mathematics and Computers in Sciences and in Industry (MCSI). Chania, Greece, Aug. 27–29, 2016.
- Zolotarev V. V., Ovechkin G. V., Chulkov I. V., Ovechkin P. V., Averin S. V., Satybaldina D. Zh., Kao V. T. Review of Achievements in the Optimization Coding Theory for Satellite Channels and Earth Remote Sensing Systems: 25 Years of Evolution // Sovremennye problemy distantsionnogo zondirovaniya Zemli iz kosmosa. 2017. V. 14. No. 1. P. 9–24.