Методы мягкого декодирования линейных блоковых кодов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Каракчиева Людмила Валерьевна

• Каракчиева Людмила Валерьевна
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Каракчиева Людмила Валерьевна

Оглавление

Реферат

Synopsis

Введение

Глава 1 Линейные блоковые коды и методы их декодирования

1.1 Декодирование линейных блоковых кодов

1.1.1 Линейные коды

1.1.2 Декодирование по максимуму правдоподобия

1.1.3 Посимвольное декодирование по максимуму апостериорной вероятности

1.1.4 Рекурсивные MAB декодеры

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

1.2.1 Декодирование двоичных полярных кодов

1.2.2 Обработка ядра на базе рекурсивных решеток

1.2.3 Недвоичные ядра поляризации

1.2.4 Декодирование недвоичных полярных кодов

1.2.5 Построение недвоичных полярных кодов

1.2.6 Схема Хонды-Ямамото

Глава 2 Рекурсивный алгоритм декодирования с мягким

входом и мягким выходом

2.1 Рекурсивное декодирование с двумя проходами по дереву рекурсииЮЭ

2.1.1 Вероятностный декодер

2.1.2 Log-Max аппроксимация

2.1.3 Обобщенный алгоритм

2.1.4 Обработка коротких секций

2.1.5 Сложность и оптимальное разбиение на секции

2.1.6 Анализ сложности для случайных кодов

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

2.1.8 Сравнение с другими рекурсивными подходами

2.1.9 Выводы

2.2 Рекурсивное декодирование с использованием дуального кода

2.2.1 Преобразование Хартманна-Рудольфа

2.2.2 Вероятностная версия алгоритма rSISO на дуальных кодах

2.2.3 Логарифмическая реализация рекурсивного алгоритма декодирования на базе дуальных кодов

2.2.4 Сложность и оптимальное секционирование

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

2.2.6 Выводы

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

недвоичными ядрами

3.1 Эффективное декодирование недвоичных полярных кодов

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

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

3.1.3 Выводы

3.2 Приближенный метод построения недвоичных полярных кодов

3.2.1 Пропускные способности подканалов

3.2.2 Предлагаемый алгоритм построения

3.2.3 Сложность вычисления

3.2.4 Численные резултаты

3.2.5 Выводы

3.3 Построение недвоичных полярных кодов с шейпингом

3.3.1 Кодирование

3.3.2 Декодирование

3.3.3 Построение кода

3.3.4 Недвоичные полярные подкоды

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

3.3.6 Выводы

Заключение

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

Список иллюстраций

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

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

Приложение В Копии публикаций

Введение диссертации (часть автореферата) на тему «Методы мягкого декодирования линейных блоковых кодов»

Реферат

Общая характеристика диссертации

Актуальность работы. Стремительный рост объемов обрабатываемой информации ведет к повышению требований к системам передачи данных: встают вопросы снижения задержки, улучшения надежности и энергетической эффективности систем связи. Для решения данных проблем необходимы методы помехоустойчивого кодирования, однако многие известные методы не способны удовлетворить современным требованиям к телекоммуникационным системам.

В последнее время получили распространение каскадные кодовые конструкции, которые требуют наличия эффективных процедур построения и декодирования компонентных кодов. Полярные коды, предложенные Э. Ари-каном в 2008 году, являются частным случаем обобщенных каскадных кодов, а также могут сами использоваться как компонентные в составе каскадных. Несмотря на свою относительную новизну, данная кодовая конструкция уже зарекомендовала себя на практике и была включена в стандарт систем связи пятого поколения (50). Известно, что недвоичные полярные коды обеспечивают асимптотически оптимальные параметры, но для них пока отсутствуют эффективные методы построения и декодирования.

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

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

1. Обзор и анализ существующих конструкций, методов построения и декодирования линейных блоковых кодов.

2. Разработка упрощенного алгоритма мягкого декодирования линейных блоковых кодов.

3. Разработка упрощенного метода обработки недвоичных поляризующих ядер.

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

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

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

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

Методы исследования. Для решения задач, поставленных в данной работе, использовались методы линейной алгебры, теории информации и кодирования, дискретной математики, а также теории вероятности.

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

1. Разработан новый упрощенный алгоритм декодирования с мягким выходом, использующий рекурсивные решетки кода и работающий по принципу "разделяй и властвуй". Двукратный проход по дереву рекурсии позволяет значительно уменьшить вычислительную и пространственную сложность декодирования по сравнению с существующими рекурсивными и нерекурсивными подходами, решающими ту же задачу.

2. Разработан алгоритм обработки недвоичных ядер, основанный на рекурсивных решетках расширенных кодов, построенных на базе матрицы поляризующего ядра. Предложенный метод демонстрирует заметно меньшую вычислительную сложность в сравнении с известным алгоритмом Витерби.

3. Разработан приближенный метод построения недвоичных полярных кодов. Для оценки надежностей подканалов он использует набор ядроза-висимых функций пропускных способностей, позволяющих рекурсивно

построить код любой длины п = 1т. Генерация набора функций осуществляется только один раз для одного слоя поляризующего преобразования, что делает данный подход вычислительно простым в сравнении с методом Монте-Карло, где в статистическом анализе участвуют сразу т слоев. Показано, что наличие канального адаптера существенно улучшает результаты оценки надежностей подканалов.

4. Разработан метод построения полярных кодов с шейпингом, основанный на обобщении схемы Хонды-Ямамото на случай недвоичных ядер поляризации. Применение такого подхода позволяет избавиться от необходимости использования многоуровневых конструкций, как это делается в случае двоичных кодов, демонстрируя заметный выигрыш от шейпинга и улучшение корректирующей способности в сравнении с многоуровневыми двоичными полярными кодами.

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

1. Упрощенный алгоритм мягкого декодирования линейных блоковых кодов на базе рекурсивных решеток, использующий два прохода по дереву разложения кода.

2. Быстрый рекурсивный метод обработки недвоичных ядер, учитывающий структуру коротких кодов, возникающих в дереве разложения.

3. Упрощенный метод построения полярных кодов с недвоичными ядрами, основанный на использовании функций пропускной способности подканалов ядра.

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

их программная реализация на языке С++, которая использовалась для проведения статистического моделирования.

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

Практическая значимость. Разработанный метод рекурсивного декодирования с мягким выходом обладает меньшей вычислительной сложностью в сравнении с существующими алгоритмами, решающими задачу декодирования линейных блоковых кодов по максимуму апостериорной вероятности, что позволяет сократить общую сложность декодирования каскадных кодов.

Разработанные упрощенные алгоритмы построения и декодирования полярных кодов с недвоичными ядрами позволяют улучшить производительность и энергоэффективность систем связи.

Внедрение результатов. Результаты диссертации были использованы в деятельности ООО НПП "НТТ" при разработке технологий производства и создания оборудования беспроводного широкополосного доступа на основе спецификаций 3GPP LTE, что подтверждается актом о внедрении.

Апробация результатов работы. По результатам диссертации были сделаны доклады на следующих конференциях:

1. IEEE Information Theory Workshop (2021);

2. IEEE International Symposium on Information Theory (2022);

3. International Symposium on Problems of Redundancy in Information and Control Systems (2023).

Кроме того, результаты работы были представлены на семинарах по теории кодирования Института проблем передачи информации им. A.A. Харкевича РАН (руководитель - Л.А. Бассалыго), Сколковского института науки и технологий (руководитель - Г.А. Кабатянский), а также на семинаре лаборатории теории информации и кодирования университета ИТМО (руководитель - П.В. Трифонов).

Личный вклад автора. В работе [ ] автору принадлежит обобщение рекурсивного метода обработки двоичных ядер на случай недвоичных полярных кодов; Трифонову П.В. принадлежит идея использования рекурсивных решеток для решения задачи обработки ядра поляризации и разработка соответствующих) алгоритма обработки для двоичных ядер.

В других работах, которые были выполнены в соавторстве с научным руководителем Трифоновым П.В., Каракчиевой Л.В. принадлежат соответствующие новые методы и решения, а также полученные результаты вычислительных экспериментов; вклад научного руководителя заключается в постановке задачи.

Публикации. Результаты, представленные в диссертации, опубликованы в 6 печатных изданиях, индексируемых Scopus и Web of Science. В их числе 3 статьи — в сборниках трудов конференций и 3 статьи — в рецензируемых журналах.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Полный объём диссертации составляет 224 страница. Текст диссертации содержит 57 рисунков и 17 таблиц. Список литературы включает 48 наименований.

Заключение диссертации по теме «Другие cпециальности», Каракчиева Людмила Валерьевна

Заключение

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

1. Разработан новый упрощенный алгоритм декодирования двоичных линейных блоковых кодов с мягким выходом, использующий рекурсивные решетки кода и работающий по принципу "разделяй и властвуй". Двукратный проход по дереву рекурсии позволяет значительно уменьшить вычислительную и пространственную сложность декодирования по сравнению с существующими рекурсивными и нерекурсивными подходами, решающими ту же задачу.

2. Разработан алгоритм обработки недвоичных ядер, основанный на рекурсивных решетках расширенного кода, построенного на базе матрицы поляризующего ядра. Предложенный метод демонстрирует заметно меньшую вычислительную сложность в сравнении с известным алгоритмом Витерби.

3. Разработан приближенный метод построения недвоичных полярных кодов. Для оценки надежностей подканалов он использует набор ядроза-висимых функций пропускных способностей, позволяющих рекурсивно построить код любой длины п = 1т. Генерация набора функций осуществляется только один раз для одного слоя поляризующего преобразования, что делает данный подход вычислительно простым в сравнении с методом Монте-Карло, где в статистическом анализе участвуют сразу т слоев. Показано, что наличие канального адаптера существенно улучшает результаты оценки надежностей подканалов.

4. Разработан метод построения полярных кодов с шейпингом, основанный на обобщении схемы Хонды-Ямамото на случай недвоичных ядер

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

Возможные направления дальнейших исследований:

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

2. Разработка упрощенного алгоритма декодирования с мягким выходом для конкретных кодовых конструкций (коды Рида-Маллера, полярные коды).

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

Список литературы диссертационного исследования кандидат наук Каракчиева Людмила Валерьевна, 2024 год

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

1. A Low-Complexity Dual Trellis Decoding Algorithm for High-Rate Convolution^ Codes / V. H. S. Le [и др.] // 2020 IEEE Wireless Communications and Networking Conference (WCNC). — 2020. — C. 1—7.

2. A Trellis-Based Recursive Maximum-Likelihood Decoding Algorithm for Binary Linear Block Codes / T. Fujiwara [и др.] // IEEE Transactions On Information Theory. — 1998. — Март. — T. 44, № 2.

3. Arikan, E. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels / E. Arikan // IEEE Transactions on Information Theory. — 2009. — T. 55, Л'0 7. - C. 3051 3073.

4. Вalatsoukas-Slimming, A. LLR-based Successive Cancellation List Decoding of Polar Codes / A. Balatsoukas-Stimming, M. B. Parizi, A. Burg // Proceedings of the 39th International Conference on Acoustics, Speech, and Signal Processing. — 2014.

5. Bioglio, V. On the Marginalization of Polarizing Kernels / V. Bioglio, I. Land // Proceedings of International Symposium on Turbo Codes and Iterative Information Processing. — 2018.

6. Blake, I. F. Properties of random matrices and applications / I. F. Blake, C. Studholme // Unpublished report available at litt}): www. cs. toronto. edu cvs/coding. — 2006.

7. Blokh, E. Coding of generalized concatenated codes / E. Blokh, V. Zyablov // Problems of Information Transmission. — 1974. — T. 10, № 3. — C. 45 50.

8. Griesser, H. A Posteriory Probability Decoding of Nonsystematically Encoded Block Codes / H. Griesser, V. R. Sidorenko // Problems of Information Transmission. - 2002. - T. 38, № 3.

9. Gulcu, Т. С. Construction of Polar Codes for Arbitrary Discrete Memoryless Channels / T. C. Gulcu, M. Ye, A. Barg // IEEE Transactions On Information Theory. 2018. Янв. T. 64, № 1. URL: http://arxiv.org/abs/1603. 05736.

10. Hartmann, С. An optimum symbol-by-symbol decoding rule for linear codes / C. Hartmann, L. Rudolph // IEEE Transactions on Information Theory. 1976. Септ. T. 22, № 5. C. 514 517.

11. Honda, J. Polar Coding Without Alphabet Extension for Asymmetric Models / J. Honda, H. Yamamoto // IEEE Transactions On Information Theory. 2013. Дек. T. 59, № 12.

12. Karakchieva, L. An Approximate Method for Construction of Polar Codes With Kernels Over F2, / L. Karakchieva, P. Trifonov // IEEE Communications Letters. 2020. T. 24, № 9. C. 1857 1860.

13. Karakchieva, L. A recursive SISO decoding algorithm / L. Karakchieva, P. Trifonov // Proceedings of IEEE Information Theory Workshop. 2021. C. 1 6.

14. Karakchieva, L. A Recursive Soft-Input Soft-Output Decoding Algorithm / L. Karakchieva, P. Trifonov // IEEE Transactions on Communications. 2024. T. 72, № 3. C. 1290 1302.

15. Karakchieva, L. Design of non-binary polar codes with shaping / L. Karakchieva, P. Trifonov // Proceedings of XVIII International Symposium Problems of Redundancy in Information and Control Systems (REDUNDANCY). 2023. C. 178 182.

16. Karakchieva, L. Dual-domain recursive SISO decoding of linear block codes / L. Karakchieva, P. Trifonov // Proceedings of IEEE International Symposium on Information Theory. 2022. C. 192 197.

17. Korada, S. B. Polar Codes: Characterization of Exponent, Bounds, and Constructions / S. B. Korada, E. Sasoglu, R. Urbanke // IEEE Transactions on Information Theory. 2010. Дек. T. 56, № 12. С. 6253 6264.

18. Kschischang, F. Optimal Nonuniform Signaling for Gaussian Channels / F. Kschischang, S. Pasupathy // IEEE Transactions on Information Theory. — 1993. _ Май. - T. 39, № 3. - С. 913 929.

19. Lafourcade, A. Optimal Sectionalization of a Trellis / A. Lafourcade, A. Vardy // IEEE Transactions On Information Theory. — 1996. — Май. — T. 42, № 3. - С. 689 702.

20. Li, G. Density Evolution for Nonbinary LDPC Codes Under Gaussian Approximation / G. Li, I. Fair, W. A. Krzymien // IEEE Transactions on Information Theory. — 2009. — Март. — T. 55, № 3.

21. Lint, J. van. A Course in Combinatorics / J. van Lint, R. Wilson. — Cambridge, 1992.

22. MAP and LogMAP Decoding Algorithms for Linear Block Codes Using a Code Structure / Y. Kaji [и др.] // IEICE Transactions on Fundamentals. — 2000. — Окт. - T. E83 A. № 10.

23. Miloslavskaya, V. Design of polar codes with arbitrary kernels / V. Miloslavskaya, P. Trifonov // Proceedings of IEEE Information Theory Workshop. - 2012. - C. 119-123.

24. Miloslavskaya, V. Sequential Decoding of Polar Codes / V. Miloslavskaya, P. Trifonov // IEEE Communications Letters. — 2014. — T. 18, № 7. — C. 1127—1130.

25. Miloslavskaya, V. Sequential Decoding of Polar Codes with Arbitrary Binary Kernel / V. Miloslavskaya, P. Trifonov // Proceedings of IEEE Information Theory Workshop. - Hobart, Australia : IEEE, 2014. - C. 377-381.

26. Montorsi, G. An additive version of the SISO algorithm for the dual code / G. Montorsi, S. Benedetto // Proceedings of 2001 IEEE International Symposium on Information Theory. — IEEE. 2001. — C. 27.

27. Mori, R. Non-Binary Polar Codes using Reed-Solomon Codes and Algebraic Geometry Codes / R. Mori, T. Tanaka // Proceedings of IEEE Information Theory Workshop. - Dublin, 2010. - C. 1-5.

28. Mori, R. Source and Channel Polarization over Finite Fields and Reed-Solomon Matrices / R. Mori, T. Tanaka // IEEE Transactions on Information Theory. — 2014. - Май. - T. 60, № 5. - С. 2720-2736.

29. Moskovskaya, E. Design of BCH Polarization Kernels with Reduced Processing Complexity / E. Moskovskaya, P. Trifonov // IEEE Communications Letters. - 2020. - Июль. - T. 24, № 7. - С. 1383-1386.

30. Niu, К. CRC-Aided Decoding of Polar Codes / K. Niu, K. Chen // IEEE Communications Letters. - 2012. - Окт. - T. 16, № 10. - С. 1668-1671.

31. Pfister, H. D. Near-Optimal Finite-Length Scaling for Polar Codes Over Large Alphabets / H. D. Pfister, R. L. Urbanke // IEEE Transactions on Information Theory. - 2019. - T. 65, № 9. - C. 5643-5655.

32. Sauer, T. Numerical analysis / T. Sauer. — Addison-Wesley Publishing Company, 2011.

33. Shibuya, R. An efficient MAP decoding algorithm which uses the BCJR and the recursive techniques / R. Shibuya, Y. Kaji // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. — 2001. - T. 84, № 10. - C. 2389-2396.

34. Srinivasan, S. Decoding of high rate convolutional codes using the dual trellis / S. Srinivasan, S. S. Pietrobon // IEEE Transactions on Information Theory. — 2009. - T. 56, № 1. - C. 273-295.

35. Srinivasan, S. Log domain implementation of the dual-APP algorithm / S. Srinivasan, S. S. Pietrobon // Proceedings of Australian Communications Theory Workshop. - IEEE. 2005. - C. 107-111.

36. Tal, I. How to Construct Polar Codes / I. Tal, A. Vardy // IEEE Transactions on Information Theory. - 2013. - Окт. - T. 59, № 10. - С. 6562-6582.

37. Та/, I. List Decoding of Polar Codes / I. Tal, A. Vardy // IEEE Transactions on Information Theory. - 2015. - Май. - T. 61, № 5. - С. 2213-2226.

38. Trifonov, P. A score function for sequential decoding of polar codes / P. Trifonov // Proceedings of IEEE International Symposium on Information Theory. - Vail, USA, 2018.

39. 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. — C. 2972-2976.

40. Trifonov, P. Design of Multilevel Polar Codes with Shaping / P. Trifonov // Proceedings of IEEE International Symposium on Information Theory. — 2022.

41. Trifonov, P. On Construction of Polar Subcodes with Large Kernels / P. Trifonov // Proceedings of IEEE International Symposium on Information Theory. — Paris, France, 2019.

42. Trifonov, P. Recursive Processing Algorithm for Low Complexity Decoding of Polar Codes with Large Kernels / P. Trifonov, L. Karakchieva // IEEE Transactions on Communications. — 2023. — CenT. — T. 71, № 9. — C. 5039-5050.

43. Trifonov, P. A Randomized Construction of Polar Subcodes / P. Trifonov, G. Trofimiuk // Proceedings of IEEE International Symposium on Information Theory. - Aachen, Germany : IEEE, 2017. - C. 1863-1867.

44. Trifonov, P. Efficient Design and Decoding of Polar Codes / P. Trifonov // IEEE Transactions on Communications. — 2012. — Hoa6. — T. 60, № 11. — C. 3221-3227.

45. Trifonov, P. Recursive Trellis Decoding Techniques of Polar Codes / P. Trifonov // Proceedings of IEEE International Symposium on Information Theory. - 2020.

46. Trifonov, P. Recursive Trellis Processing of Large Polarization Kernels / P. Trifonov // Proceedings of IEEE International Symposium on Information Theory. — 2021.

47. Viterbi, A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm / A. Viterbi // IEEE Transactions on Information Theory. - 1967. - T. 13, № 2. - C. 260-269.

48. Wu, B. Conditional Entropy-Based Construction of Multilevel Polar-Coded Modulation With Probabilistic Shaping / B. Wu, K. Niu, J. Dai // IEEE Communications Letters. - 2023. - T. 27, № 5. - C. 1262-1266.