Построение полярных подкодов и упрощённые методы их кодирования и декодирования тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Морозов Руслан Александрович

• Морозов Руслан Александрович
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Морозов Руслан Александрович

Оглавление

Реферат

Synopsis

Введение

Глава 1. Полярные коды и их обобщения

1.1. Полярные коды

1.1.1. Определение полярных кодов

1.1.2. Декодирование методом последовательного исключения

1.1.3. Построение полярных кодов для стирающего канала

1.1.4. Полярные коды как обобщённые каскадные коды

1.2. Полярные подкоды

1.3. Последовательный алгоритм декодирования полярных кодов

1.3.1. Высокоуровневое описание алгоритма

1.3.2. Стоимость пути

1.4. Полярные коды с ядром Рида-Соломона

1.5. Свёрточные полярные коды

1.6. Постановка задачи

Глава 2. Свёрточные полярные подкоды

2.1. Декодирование методом последовательного исключения

2.1.1. Рекурсивные формулы для вычисления вероятностей

2.1.2. Кластеры вероятностей

2.2. Эффективное декодирование свёрточных полярных кодов

2.2.1. Переход в логарифмическую область

6

2.2.2. Снижение потребляемой памяти

2.2.3. Списочное декодирование

2.3. Минимальное расстояние свёрточных полярных кодов

2.3.1. Обобщение метода последовательного исключения

2.3.2. Нижняя оценка минимального расстояния линейных кодов

2.3.3. Восстановимые и стёртые векторы

2.3.4. Вес смежных классов и конфигурации стирания

2.3.5. Нижняя оценка минимального расстояния СвПК

2.4. Свёрточные полярные подкоды

2.4.1. Построение

2.4.2. Численные результаты

2.5. Вывод

Глава 3. Кодирование полярных подкодов

3.1. Компактная спецификация

3.1.1. ДСтК-аппроксимация замороженного множества

3.1.2. Рекурсивная спецификация

3.1.3. Границы на значение |𝐷|

3.1.4. Спецификация полярных подкодов

3.1.5. Развёртывание компактной спецификации

3.1.6. Численные результаты

3.2. Быстрое систематическое кодирование

3.2.1. Систематическое кодирование

3.2.2. Алгоритм Саркиса-Тала

3.2.3. Алгоритм Вангалы-Витербо

3.2.4. Систематическое кодирование полярных подкодов

3.2.5. Двухэтапное систематическое кодирование

7

3.2.6. Последовательное систематическое кодирование

3.2.7. Сравнение эффективности

3.3. Выводы

Глава 4. Последовательное декодирование полярных подкодов

4.1. Критерий раннего останова

4.1.1. Введение порога на стоимость пути

4.1.2. Численные результаты

4.2. Последовательное декодирование в случае ядра Рида-Соломона

4.2.1. Метрика пути

4.2.2. Продолжение путей

4.2.3. Гауссовская аппроксимация

4.3. Выводы

Заключение

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

Список иллюстративного материала

Список таблиц

Список публикаций автора по теме исследования

Приложение 1. Акт о внедрении

Приложение 2. Тексты публикаций автора по теме исследования

Введение диссертации (часть автореферата) на тему «Построение полярных подкодов и упрощённые методы их кодирования и декодирования»

Актуальность темы исследования

Интенсивное развитие вычислительных систем и быстрый рост объёма дан­

ных, доступных в цифровой форме, требуют создания высокоскоростных систем

надёжной передачи информации. Обеспечение современных и перспективных тре­

бований к скорости обмена данными, задержке передачи информации и энерге­

тической спектральной эффективности невозможны без использования методов

помехоустойчивого кодирования.

Несмотря на обилие теоретических результатов, связанных с построением,

декодированием и анализом свойств корректирующих кодов (А. Варди, И. И. Ду­

мер, К. Ш. Зигангиров, В. А. Зиновьев, В. В. Зяблов, Г. А. Кабатянский, И. Тал,

Р. Урбанке), полученных в теории кодирования, построение кодовых конструк­

ций и алгоритмов декодирования, которые соответствовали бы перспективным

требованиям к системам связи, вызывает значительные затруднения. Применяе­

мые в настоящее время кодовые конструкции демонстрируют вероятность ошиб­

ки, значительно превышающую известные нижние границы. Широко используе­

мые турбо-коды и коды с малой плотностью проверок на чётность (МППЧ) требу­

ют внесения весьма значительного числа проверочных символов для обеспечения

заданной вероятности ошибки. Предложенные недавно Э. Ариканом полярные ко­

ды, хотя и достигают асимптотически предела Шеннона, на практике на длинах

более нескольких тысяч проигрывают по корректирующей способности известным

кодам МППЧ. Кроме того, для обеспечения приемлемой корректирующей способ­

ности полярные коды Арикана и их обобщения (полярные коды с CRC и полярные

подкоды) требуют применения списочных методов декодирования.

Свёрточные полярные коды предложены Э. Феррисом, К. Хиршем и Д. Пу­

лином как модификация полярных кодов, имеющая высокую скорость поляриза­

9

ции и потому высокую корректирующую способность. Однако, оригинальный ал­

горитм декодирования методом последовательного исключения для свёрточных

полярных кодов в общем случае не обеспечивает декодирование по максимуму

правдоподобия. Кроме того, из-за низкого минимального расстояния и большого

количества кодовых слов малого веса оригинальные свёрточные полярные коды

имеют недостаточно низкую вероятность ошибки даже при декодировании по мак­

симуму правдоподобия на практически значимых длинах (от нескольких сотен до

нескольких тысяч бит).

Данная диссертация посвящена вопросам построения, кодирования и деко­

дирования кодов, использующих эффект поляризации канала.

Цели и задачи диссертационной работы

Целью диссертации является построение эффективных методов кодирова­

ния и декодирования полярных кодов и их модификаций. Разработанные мето­

ды должны достигать меньшей вероятности ошибки и/или иметь меньшую слож­

ность декодирования по сравнению с существующими кодовыми конструкциями

и алгоритмами кодирования и декодирования. Для достижения цели в рамках

диссертационной работы решаются следующие задачи:

1. Построение кодов с корректирующей способностью выше, чем у существую­

щих свёрточных полярных кодов.

2. Разработка эффективного алгоритма декодирования свёрточных полярных

кодов, обеспечивающего вероятность ошибки ниже, чем вероятность ошибки

декодирования методом последовательного исключения.

3. Разработка метода компактной спецификации полярных кодов.

4. Разработка метода систематического кодирования полярных подкодов.

10

5. Разработка алгоритма декодирования с направленным поиском для поляр­

ных подкодов с ядром Рида-Соломона.

Объектом исследования являются полярные коды и алгоритмы их декодиро­

вания. Результаты диссертации основаны на методах алгебраической и комбина­

торной теории кодирования, линейной алгебры и теории вероятностей.

Научная новизна

Научная новизна полученных результатов состоит в следующем:

1. Предложена нижняя граница минимального расстояния свёрточных поляр­

ных кодов, сложность вычисления которой линейна относительно длины ко­

да. Полученная граница точна для всех исследованных кодов, построенных

для двоичного стирающего канала и канала с АБГШ. Ранее минимальное

расстояние свёрточных полярных кодов можно было вычислить лишь пере­

бором всех кодовых слов, а для оценки существовали только общие границы

на минимальное расстояние линейных блоковых кодов, которые не являются

точными.

2. Разработана новая кодовая конструкция — свёрточные полярные подкоды.

Её отличие от свёрточных полярных кодов состоит в наличии не только ста­

тически замороженных символов, равных нулю и передаваемых по наименее

надёжным подканалам поляризующего преобразования, но также и динами­

чески замороженных символов, равных линейной комбинации предыдущих

символов. Позиции динамически замороженных символов вычисляются как

позиции символов, ненулевые значения которых отвечают за порождение ко­

довых слов минимального веса. Предложенная процедура вычисления мини­

11

мального веса кодового слова, порождаемого ненулевым значением каждого

из входных символов, является новой в случае свёрточных полярных кодов.

3. Разработан метод компактной спецификации полярных кодов на основе ап­

проксимации исходного множества замороженных символов множеством за­

мороженных символов полярного кода, построенного для двоичного стираю­

щего канала. Ранее методов компактной спецификации полярных кодов не

предлагалось.

4. Предложено два быстрых алгоритма систематического кодирования для по­

лярных подкодов. Показана область применимости предложенных методов.

Ранее для полярных подкодов применялось несистематическое кодирование,

при котором вероятность битовой ошибки выше, чем при систематическом

кодировании. Систематическое кодирование для полярных подкодов не пред­

лагалось.

Практическая значимость

Разработанная конструкция свёрточных полярных подкодов в сочетании с

предложенным списочным алгоритмом декодирования имеет вероятность ошиб­

ки декодирования ниже, чем свёрточные полярные коды, полярные коды и поляр­

ные подкоды с тем же размером списка. В частности, для кода с параметрами

(4096, 2048) для целевой вероятности ошибки 0.0002 требуемая сложность декоди­

рования примерно на 20% ниже, чем при использовании полярных подкодов Ари­

кана. Также можно сказать, что при фиксированной сложности 8 · 107 операций

предложенная конструкция позволяет обеспечить вероятность ошибки в полтора

раза ниже, чем при использовании полярных кодов Арикана. Кроме того, алго­

ритм не требует выполнения операций умножения, что упрощает его реализацию

для мобильных устройств.

12

Предложенный метод компактной спецификации снижает количество памя­

ти, необходимое для хранения построенных полярных кодов и подкодов, что позво­

ляет использовать большие семейства заранее оптимизированных полярных кодов

и подкодов в устройствах с небольшим объёмом памяти.

Разработанные методы систематического кодирования полярных подкодов

упрощают операцию извлечения данных из восстановленного кодового слова, что

приводит к снижению сложности и задержки декодирования полярных подкодов.

Кроме того, предложенные методы уменьшают вероятность битовой ошибки, что

может быть применено в тех сценариях, где допустимы ошибки декодирования,

но требуется, чтобы восстановленные данные были как можно ближе к исходным

в метрике Хэмминга. Такие сценарии возникают при передаче данных, не чув­

ствительных к единичным ошибкам, таких как видео- или аудиопоток, а также в

каскадных кодовых конструкциях. Предложены два алгоритма систематического

кодирования полярных подкодов, один из которых имеет малую задержку коди­

рования, а другой — малое число операций, что позволяет использовать данные

методы в различных сценариях передачи данных и при различных требованиях.

Положения, выносимые на защиту

1. Предложенная граница минимального расстояния свёрточных полярных ко­

дов справедлива. Основанный на предложенной границе минимального рас­

стояния метод построения свёрточных полярных подкодов позволяет стро­

ить коды с лучшей корректирующей способностью, чем у свёрточных поляр­

ных кодов с аналогичными параметрами.

2. Предложенный алгоритм декодирования свёрточных полярных (под)кодов

обладает меньшей сложностью, чем существующие аналоги.

3. Предложенные алгоритмы систематического кодирования для полярных

13

подкодов позволяют снизить вероятность битовой ошибки декодирования

полярных подкодов.

4. Предложенный метод компактной спецификации полярных кодов позволяет

значительно снизить размер потребляемой памяти для хранения специфи­

каций полярных кодов.

Степень достоверности результатов

Предложенные алгоритмы построения кодов, кодирования и декодирования

были реализованы программно на языке C++. Для исследования поведения си­

стемы, использущей предложенные алгоритмы, проведено статистическое модели­

рование. Предложенная нижняя граница минимального расстояния свёрточных

полярных кодов доказана в виде теоремы.

Апробация результатов

Основные результаты диссертации докладывались на следующих конферен­

циях:

1. IEEE International Symposium on Information Theory (ISIT-2019) [21].

2. IEEE International Symposium on Information Theory and Its Applications

(ISITA-2018) [19].

3. International Symposium «Problems of Redundancy in Information and Control

Systems» (REDUNDANCY-2016) [18].

4. International Symposium «Problems of Redundancy in Information and Control

Systems» (REDUNDANCY-2018) [17].

14

Область применения результатов

Полученные результаты могут быть применены в системах мобильной свя­

зи для уменьшения энергопотребления конечных устройств, увеличения радиуса

действия базовых станций, снижения задержки передачи данных. Разработанное

формальное описание конструкции и декодирования свёрточных полярных кодов

может быть применено в дальнейших исследованиях свёрточных полярных кодов.

Заключение диссертации по теме «Теоретические основы информатики», Морозов Руслан Александрович

Заключение

В данной работе представлено обобщение конструкции свёрточных полярных

кодов, называемое свёрточные полярные подкоды. Для них предложена эффек­

тивная реализация алгоритма декодирования последовательного исключения и

его обобщение на случай списочного декодирования. Предложенная кодовая кон­

струкция и алгоритм декодирования позволяют получить вероятность ошибки в

1.5 раза ниже, чем у полярных подкодов, при той же сложности. Предложенная

кодовая конструкция позволяет достичь вероятности ошибки примерно в 8 раз ни­

же, чем коды с МППЧ из стандарта CCSDS. Кроме того, предложен метод вычис­

ления нижней границы минимального расстояния свёрточных полярных кодов.

Таким образом, поставленная цель достигнута.

Предложен метод компактной спецификации полярных кодов и подкодов,

что позволяет компактно хранить заранее оптимизированные полярные коды и

подкоды в устройствах с ограниченной памятью. Объём памяти, требуемой для

хранения спецификаций полярных (под)кодов, может быть снижен до 40 раз.

Предложен критерий раннего останова для последовательного декодирова­

ния полярных кодов, позволяющий снизить среднюю задержку декодирования в

1.5–3 раза за счёт небольшого увеличения вероятности ошибки декодирования.

Предложено два алгоритма систематического кодирования полярных подко­

дов, позволяющие снизить вероятность ошибки декодирования на бит в 2–4 раза

по сравнению с несистематическим кодированием.

Предложено обобщение декодирования методом ПИ на случай последова­

тельного декодирования для полярных кодов с ядром Рида-Соломона. В сочета­

нии с построенными полярными подкодами с ядром Рида-Соломона предложен­

ный алгоритм декодирования позволяет достичь снижения вероятности ошибки

до 10 раз по сравнению с полярными кодами с ядром Рида-Соломона.

Список литературы диссертационного исследования кандидат наук Морозов Руслан Александрович, 2020 год

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

1. Морозов, . Компактная спецификация полярных кодов / Р.А. Морозов,

П.В. Трифонов // Информационно-управляющие системы. — 2019. — Т. 2019,

№ 1. — С. 40–47.

2. Кабатянский, . . Два обобщения произведения кодов / Г. А. Кабатянский //

Доклады академии наук СССР. — 1977. — Т. 232, № 6. — С. 1277–1280.

3. Зигангиров, . Некоторые последовательные процедуры декодирования /

К.Ш. Зигангиров // Проблемы передачи информации. — 1966. — Т. 2, № 4. —

С. 13–25.

4. Arıkan, E. Channel polarization: A method for constructing capacity-achieving

codes for symmetric binary-input memoryless channels / E. Arıkan // IEEE

Transactions on Information Theory. –– 2009. –– July. –– Vol. 55, no. 7. –– P. 3051–

3073.

5. Canteaut, A. A new algorithm for finding minimum-weight words in a linear

code: Application to McEliece’s cryptosystem and to narrow-sense BCH codes

of length 511 / A. Canteaut, F. Chabaud // IEEE Transactions on Information

Theory. –– 1998. –– January. –– Vol. 44, no. 1. –– P. 367–378.

6. Chung, S.-Y. Analysis of sum-product decoding of low-density parity-check

codes using a Gaussian approximation / S.-Y. Chung, T. J. Richardson, R. L. Ur-

banke // IEEE Transactions on Information Theory. –– 2001. –– February. ––

Vol. 47, no. 2.

7. Convolutional polar codes: LLR-based successive cancellation decoder and list

decoding performance / H. Saber, Y. Ge, R. Zhang et al. // 2018 IEEE Inter-

national Symposium on Information Theory (ISIT). –– 2018. –– June. –– P. 1480–

1484.

8. Ferris, A. J. Convolutional polar codes / Andrew James Ferris,

168

Christoph Hirche, David Poulin // CoRR. –– 2017. –– Vol. abs/1704.00715. ––

http://arxiv.org/abs/1704.00715.

9. Ferris, A. J. Branching MERA codes: a natural extension of polar codes /

Andrew J. Ferris, David Poulin // CoRR. –– 2013. –– Vol. abs/1312.4575. ––

http://arxiv.org/abs/1312.4575.

10. Flexible and low-complexity encoding and decoding of systematic polar codes /

Gabi Sarkis, Ido Tal, Pascal Giard et al. // IEEE Transactions on Communi-

cations. –– 2016. –– July. –– Vol. 64, no. 7.

11. Introduction to Algorithms / Thomas H. Cormen, Charles E. Leiserson,

Ronald L. Rivest, Clifford Stein. –– 2 edition. –– The MIT Press, 2001.

12. Johannesson, R. Fundamentals of Convolutional Coding / Rolf Johannesson,

K.Sh. Zigangirov. –– IEEE Press, 1998.

13. Miloslavskaya, V. Sequential decoding of polar codes / V. Miloslavskaya, P. Tri-

fonov // IEEE Communications Letters. –– 2014. –– Vol. 18, no. 7. –– P. 1127–

1130.

14. Mondelli, M. Construction of polar codes with sublinear complexity /

Marco Mondelli, Hamed Hassani, Ruediger L Urbanke // Proceedings of IEEE

International Symposium on Information Theory. –– 2017.

15. Mori, R. Performance of polar codes with the construction using density evo-

lution / Ryuhei Mori, Toshiyuki Tanaka // IEEE Comm. Letters. –– 2009. ––

Vol. 13, no. 7.

16. Mori, R. Channel polarization on 𝑞-ary discrete memoryless channels by ar-

bitrary kernels / R. Mori, T. Tanaka // Proceedings of IEEE International

Symposium on Information Theory. –– 2010.

17. Morozov, R. A simplified lower bound on minimum distance of convolutional po-

lar codes / R. Morozov // 2019 XVI International Symposium ”Problems of Re-

dundancy in Information and Control Systems” (REDUNDANCY). –– 2019. ––

169

Oct. –– P. 7–11.

18. Morozov, R. Directed search decoding of polar codes with reed-solomon kernel /

R. Morozov, P. Trifonov // 2016 15th International Symposium on Problems

of Redundancy in Information and Control Systems, REDUNDANCY 2016. ––

Saint Peterburg, Russia: IEEE, 2016. –– P. 87–91.

19. Morozov, R. Efficient SC decoding of convolutional polar codes / R. Morozov,

P. Trifonov // Proceedings of International Symposium on Information Theory

and Applications. –– Singapore, Singapore: IEEE, 2018. –– P. 442–446.

20. Morozov, R. Compact specification of polar codes / R.A. Morozov, P.V. Tri-

fonov // Informatsionno-Upravliaiushchie Sistemy. –– 2019. –– Vol. 2019,

no. 1. –– P. 40–47.

21. Morozov, R. A lower bound on minimum distance of convolutional polar codes /

R. Morozov, P. Trifonov // 2019 IEEE International Symposium on Information

Theory (ISIT). –– Paris, France: IEEE, 2019. –– July. –– P. 2104–2108.

22. Morozov, R. On distance properties of convolutional polar codes / R. Moro-

zov, P. Trifonov // IEEE Transactions on Communications. –– 2019. –– July. ––

Vol. 67, no. 7. –– P. 4585–4592.

23. Morozov, R. Successive and two-stage systematic encoding of polar subcodes /

R. Morozov, P. Trifonov // IEEE Wireless Communications Letters. –– 2019. ––

February. –– Vol. 8, no. 3. –– P. 877–880.

24. Niu, K. Stack decoding of polar codes / K. Niu, K. Chen // Electronics Let-

ters. –– 2012. –– June. –– Vol. 48, no. 12. –– P. 695–697.

25. Poltyrev, G. Bounds on the decoding error probability of binary linear codes via

their spectra / Gregory Poltyrev // IEEE Transactions on Information The-

ory. –– 1994. –– July. –– Vol. 40, no. 4.

26. Prinz, T. Successive cancellation list decoding of BMERA codes with application

to higher-order modulation / Tobias Prinz, Peihong Yuan // 2018 International

170

Symposium on Turbo Codes and Iterative Information Processing (ITW). ––

2018. –– December.

27. Sason, I. Performance analysis of linear codes under maximum-likelihood de-

coding: A tutorial / Igal Sason, Shlomo Shamai // Foundations and Trends in

Communications and Information Theory. –– 2006. –– Vol. 3, no. 1–2. –– P. 1–

222. –– http://dx.doi.org/10.1561/0100000009.

28. Sloane, N. J. A. The on-line encyclopedia of integer sequences. –– https://

oeis.org/.

29. Staircase codes: Fec for 100 gb/s otn / B. P. Smith, A. Farhood, A. Hunt

et al. // Journal of Lightwave Technology. –– 2012. –– Jan. –– Vol. 30, no. 1. ––

P. 110–117.

30. Tal, I. How to construct polar codes / Ido Tal, Alexander Vardy // IEEE

Transactions on Information Theory. –– 2013. –– October. –– Vol. 59, no. 10. ––

P. 6562–6582.

31. Tal, I. List decoding of polar codes / Ido Tal, A. Vardy // IEEE Transactions

On Information Theory. –– 2015. –– May. –– Vol. 61, no. 5. –– P. 2213–2226.

32. Trifonov, P. Efficient design and decoding of polar codes / Peter Tri-

fonov // IEEE Transactions on Communications. –– 2012. –– November. ––

Vol. 60, no. 11. –– P. 3221 – 3227.

33. Trifonov, P. Binary successive cancellation decoding of polar codes with Reed-

Solomon kernel / P. Trifonov // Proceedings of IEEE International Symposium

on Information Theory. –– Honolulu, USA: IEEE, 2014. –– P. 2972 – 2976.

34. Trifonov, P. A score function for sequential decoding of polar codes / P. Tri-

fonov // Proceedings of IEEE International Symposium on Information The-

ory. –– Vail, USA, 2018.

35. Trifonov, P. Polar subcodes / P. Trifonov, V. Miloslavskaya // IEEE Journal

on Selected Areas in Communications. –– 2016. –– February. –– Vol. 34, no. 2. ––

171

P. 254–266.

36. Trifonov, P. A randomized construction of polar subcodes / P. Trifonov,

G. Trofimiuk // Proceedings of IEEE International Symposium on Information

Theory. –– Aachen, Germany: IEEE, 2017. –– P. 1863–1867.

37. Vangala, H. Efficient algorithms for systematic polar encoding / Harish Van-

gala, Yi Hong, Emanuele Viterbo // IEEE Communications Letters. –– 2016. ––

January. –– Vol. 20, no. 1.

38. Zhuang, Q. Bounds on the ML decoding error probability of RS-coded modu-

lation over AWGN channels / Qiutao Zhuang, Xiao Ma, Aleksandar Kavcic //

CoRR. –– 2014. –– October. –– Vol. abs/1401.5305. –– http://arxiv.org/abs/

1401.5305.

39. Zyablov, V. An introduction to generalized concatenated codes / V. Zyablov,

S. Shavgulidze, M. Bossert // European transactions on telecommunications. ––

1999. –– Vol. 10, no. 6. –– P. 609–622.

172

Список иллюстративного материала

1.1 Рекурсивная схема СвПП 𝑄(𝑛) . . . . . . . . . . . . . . . . . . . . . 78

1.2 Алгоритм кодирования для СвПК . . . . . . . . . . . . . . . . . . . 79

2.1 Схемы преобразований кластеров вероятностей . . . . . . . . . . . . 82

(2)

а 𝑊2 (𝑎, 𝑏, 𝑐|𝑦) . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

(2)

б 𝑊𝜆 (𝑎, 𝑏, 𝑐|𝑦) . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

(Λ−1)

в 𝑊𝜆 𝑢Λ−4

(^ 0 , 𝑎, 𝑏, 𝑐|𝑦) . . . . . . . . . . . . . . . . . . . . . . . 82

(Λ−1)

г 𝑊𝜆 𝑢Λ−3

(^ 0 , 𝑎, 𝑏|𝑦) . . . . . . . . . . . . . . . . . . . . . . . . 82

(2𝑖+3)

д 𝑊𝜆 0 , 𝑎, 𝑏, 𝑐|𝑦) . . . . . . . . . . . . . . . . . . . . . . . .

𝑢2𝑖

(^ 82

(2𝑖+4)

е 𝑊𝜆 𝑢02𝑖+1 , 𝑎, 𝑏, 𝑐|𝑦)

(^ . . . . . . . . . . . . . . . . . . . . . . 82

2.2 Алгоритм последовательного исключения для декодирования СвПК

с эффективным использованием памяти . . . . . . . . . . . . . . . . 90

2.3 Алгоритм распространения принятых решений . . . . . . . . . . . . 92

2.4 Алгоритм вычисления ЛОПП для текущего символа 𝑢𝜙 . . . . . . . 93

2.5 ̃︀(𝐽) . . . . . . . . . . . . . . . . .

Алгоритм выбора преобразования 𝑅 94

2.6 Декодирование свёрточных полярных кодов методом ПИ . . . . . . 95

2.7 Алгоритм списочного декодирования для СвПК . . . . . . . . . . . 99

2.8 Алгоритм вычисления ЛОПП в списочном алгоритм декодирования

СвПК . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

2.9 Вероятность ошибки декодирования СвПК списочным алгоритмом 101

(𝑖)

2.10 Алгоритм вычисления 𝑑𝑛 , 𝑛 = 2𝑚 для всех 𝑖 ∈ [𝑛] . . . . . . . . . . 118

(−1) (0)

2.11 Алгоритм вычисления Δ𝑛,* по входным Δ𝑛,* . . . . . . . . . . . . . 119

2.12 Зависимость минимального расстояния полярных и свёрточных по­

лярных кодов длины 16384 от скорости . . . . . . . . . . . . . . . . 119

2.13 Минимальное расстояние полярных кодов, СвПК и свёрточных по­

лярных подкодов в зависимости от скорости . . . . . . . . . . . . . 122

173

2.14 Вероятность ошибки декодирования (1024, 512) свёрточного поляр­

ного подкода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

2.15 Вероятность ошибки декодирования (4096, 2048)-свёрточного поляр­

ного подкода с 𝑓 = 12 списочным алгоритмом при различных раз­

мерах списка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

2.16 Зависимость вероятности ошибки декодирования

(4096, 2048)-свёрточного полярного подкода с 𝑓 = 12 списоч­

ным алгоритмом декодирования от сложности . . . . . . . . . . . . 125

2.17 Сравнение вероятности ошибки декодирования

(2048, 1024)-свёрточного полярного подкода с (2048, 1024) ко­

дом с МППЧ из стандарта CCSDS . . . . . . . . . . . . . . . . . . . 126

2.18 Весовые спектры полярного кода, полярного подкода, СвПК и свёр­

точного полярного подкода с параметрами (128, 43) . . . . . . . . . 127

2.19 Верхняя граница Полтырева [25] вероятности ошибки декодирова­

ния по максимуму правдоподобия для канала с АБГШ для полярно­

го кода, полярного подкода, СвПК и свёрточного полярного подкода

с параметрами (128, 43) . . . . . . . . . . . . . . . . . . . . . . . . . 128

3.1 Алгоритм построения ДСтК-аппроксимации полярного кода . . . . 131

3.2 Алгоритм построения компактной спецификации полярного кода . 133

3.3 Размер полных и компактных спецификаций (ДСтК-аппроксима­

ции и рекурсивной спецификации) полярных кодов в зависимости

от длины кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

3.4 Размер полных и компактных спецификаций полярных подкодов в

зависимости от длины кода . . . . . . . . . . . . . . . . . . . . . . . 139

3.5 Алгоритм систематического кодирования Вангалы-Витербо . . . . . 144

3.6 Схема вычислений, производимых в алгоритме Вангалы-Витербо

для случая 𝑚 = 3 и ℱ = (0, 2, 4) . . . . . . . . . . . . . . . . . . . . 145

174

3.7 Схема работы двухэтапного алгоритма кодирования для полярных

подкодов в случае 𝑛 = 8, 𝑘 = 4, ℱ = {0, 2, 4}, 𝒟 = {5}, 𝑢5 = 𝑢1 + 𝑢3 . 148

3.8 Обобщённый алгоритм кодирования Вангалы-Витербо для поляр­

ных подкодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

3.9 Пример работы последовательного кодирования для полярных под­

кодов в случае 𝑛 = 8, 𝑘 = 4, ℱ = {0, 2, 4}, 𝒟 = {5}, 𝒟′ = {1}, 𝑢5 =

𝑢1 + 𝑢3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

3.10 Вероятность ошибки на бит при систематическом кодировании по­

лярных подкодов кодов БЧХ . . . . . . . . . . . . . . . . . . . . . . 152

3.11 Вероятность ошибки на бит при систематическом кодировании ран­

домизированных полярных подкодов [36] . . . . . . . . . . . . . . . 152

4.1 Аппроксимация порога T раннего останова для полярного

(1024, 736, 16)-подкода БЧХ . . . . . . . . . . . . . . . . . . . . . . . 156

4.2 Вероятность ошибки и сложность последовательного декодирова­

ния с использованием критерия раннего останова . . . . . . . . . . 157

4.3 Алгоритм вычисления выходных вероятностей для ядра Рида-Соло­

мона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

4.4 Распределение ЛОПП на выходе декодера ядра . . . . . . . . . . . 164

4.5 Среднее число итераций, проделанных алгоритмом декодирования

(1024, 512)-кода с 𝐿 = 64, Θ = 16384 для значений Ω(𝑖), вычислен­

ных различными способами . . . . . . . . . . . . . . . . . . . . . . . 164

4.6 Вероятность ошибки декодирования полярных кодов с ядром Рида­

Соломона и динамически замороженными символами . . . . . . . . 165

175

Список таблиц

2.1 Сложность преобразований кластеров вероятностей . . . . . . . . . 94

3.1 Сравнение сложности и задержки алгоритмов систематического ко­

дирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

4.1 Параметры раннего останова . . . . . . . . . . . . . . . . . . . . . . 158

176

Список публикаций автора по теме исследования

1. Morozov, R. A simplified lower bound on minimum distance of convolutional

polar codes / R. Morozov // 2019 XVI International Symposium "Problems of

Redundancy in Information and Control Systems"(REDUNDANCY). — 2019.

— Oct. — P. 7–11.

2. Morozov, R. Directed search decoding of polar codes with reed-solomon kernel /

R. Morozov, P. Trifonov // 2016 15th International Symposium on Problems

of Redundancy in Information and Control Systems, REDUNDANCY 2016. —

Saint Peterburg, Russia: IEEE, 2016. — P. 87–91.

3. Morozov, R. Efficient SC decoding of convolutional polar codes / R. Morozov,

P. Trifonov // Proceedings of International Symposium on Information Theory

and Applications. — Singapore, Singapore: IEEE, 2018. — P. 442–446.

4. Морозов, Р. Компактная спецификация полярных кодов / Р.А. Морозов,

П.В. Трифонов // Информационно-управляющие системы. — 2019. — Т.

2019, № 1. — С. 40–47.

5. Morozov, R. A lower bound on minimum distance of convolutional polar codes /

R. Morozov, P. Trifonov // 2019 IEEE International Symposium on Information

Theory (ISIT). — Paris, France: IEEE, 2019. — July. — P. 2104–2108.

6. Morozov, R. On distance properties of convolutional polar codes / R. Morozov,

P. Trifonov // IEEE Transactions on Communications. — 2019. — July. —

Vol. 67, no. 7. — P. 4585–4592.

7. Morozov, R. Successive and two-stage systematic encoding of polar subcodes /

R. Morozov, P. Trifonov // IEEE Wireless Communications Letters. — 2019. —

February. — Vol. 8, no. 3. — P. 877–880.