eng
Выпуск #1/2025
В.В.Зяблов, С.Л.Портной, С.Е.Никитин, А.Д.Волошин, Н.С.Клюев
Новый класс кодов с локализацией ошибок и его помехоустойчивость: основная идея
Новый класс кодов с локализацией ошибок и его помехоустойчивость: основная идея
Просмотры: 861
DOI: 10.22184/2070-8963.2025.125.1.64.69
Рассматривается возможность переосмысления устоявшихся кодовых конструкций. Предлагается новая модификация традиционных каскадных и обобщенных каскадных кодов, что в свою очередь создает принципиально новое семейство кодов и открывает перспективы для разработки новых алгоритмов декодирования. Приведены три примера построения кодов с локализацией ошибок и результаты их моделирования. Описаны направления дальнейших исследований новых классов кодов.
Рассматривается возможность переосмысления устоявшихся кодовых конструкций. Предлагается новая модификация традиционных каскадных и обобщенных каскадных кодов, что в свою очередь создает принципиально новое семейство кодов и открывает перспективы для разработки новых алгоритмов декодирования. Приведены три примера построения кодов с локализацией ошибок и результаты их моделирования. Описаны направления дальнейших исследований новых классов кодов.
Теги: cascade codes cascading of codes with error localisation codes with error localisation noise-immune coding reed – solomon code каскадирование кодов с локализацией ошибок каскадные коды код рида – соломона коды с локализацией ошибок помехоустойчивое кодирование
Новый класс кодов с локализацией ошибок и его помехоустойчивость: основная идея
В.В.Зяблов, д.т.н., главный научный сотрудник ИППИ РАН им А.А. Харкевича / zyablov@iitp.ru,
С.Л.Портной, д.т.н., проф. Московского института электроники и математики им. А. Н.Тихонова НИУ ВШЭ / sportnoy@hse.ru,
С.Е.Никитин, ст. преподаватель МИЭМ НИУ ВШЭ / snikitin@hse.ru,
А.Д.Волошин, магистрант МИЭМ НИУ ВШЭ / advoloshin@edu.hse.ru,
Н.С.Клюев, магистрант МИЭМ НИУ ВШЭ / nsklyuev@edu.hse.ru
УДК 621.391, DOI: 10.22184/2070-8963.2025.125.1.64.69
Рассматривается возможность переосмысления устоявшихся кодовых конструкций. Предлагается новая модификация традиционных каскадных и обобщенных каскадных кодов, что в свою очередь создает принципиально новое семейство кодов и открывает перспективы для разработки новых алгоритмов декодирования. Приведены три примера построения кодов с локализацией ошибок и результаты их моделирования. Описаны направления дальнейших исследований новых классов кодов.
Введение
С появлением первых работ Шеннона и Хемминга [1, 2] начавшая уже тогда формироваться как отдельная самостоятельная наука теория помехоустойчивого кодирования всегда надолго опережала возможности ее практической реализации. Причем не всегда единственной причиной разрыва между теорией и практикой была задержка в развитии элементной базы. Часто, если не всегда, необходимо было посмотреть на одну и ту же проблему под другим углом. А это можно было сделать только по прошествии некоторого времени.
Приведем примеры:
Исходя из изложенного, нет ничего удивительного в том, что иногда свежий взгляд на давно известную кодовую конструкцию позволяет получить новое качество.
В данной работе предлагается еще одна модификация давно известных каскадных и обобщенных каскадных кодов, что приводит к созданию принципиально нового семейства кодов, и, как следствие, новых алгоритмов декодирования.
Краткое описание кодовой конструкции
Алгоритм кодирования описывается с использованием следующих терминов. Рассмотрим каскадный код, состоящий из двоичного кода (n1, k1, d1) [код 1] и кода Рида ‒ Соломона (n2, k2, d2) над полем GF(2k1) [код 2]. Также существует код (n2, k3, d3) над полем GF(2n1 – k1) [код 3]. Код 1 будем называть внутренним кодом, код 2 – внешним кодом, код 3 – кодом локализации ошибок.
Алгоритм кодирования состоит в следующем. k информационных символов записываются в две матрицы:
k1 х k2 и (n1 – k1) х k3.
Таким образом, k = k1 * k2 + (n1 – k1) * k3, n = n1 * n2.
Кодируем k2 символов поля GF(2k1) кодом 2.
Каждый символ кода 2 кодируем кодом 1 и получаем матрицу n1 x n2.
Кодируем k3 символов поля GF(2n1 – k1) кодом 3.
Умножаем символы кода 3 в недвоичном случае на квазислучайные элементы поля GF(2n1 – k1), последовательность которых известна на передающей и приемной стороне.
Прибавляем поразрядно символы кода 3 к нижней части матрицы каскадного кода.
Результирующая матрица является словом (n, k) кода и постолбцово передается в канал.
Хотя кодирование кода и состоит из линейных операций, оно не представляется в виде единой порождающей матрицы, поэтому в общем случае код не является линейным. Результирующий код является кодом с локализацией ошибок (КЛО). Иллюстрация процесса кодирования такого кода приведена на рис.1.
Сформулируем общую идею декодирования.
Декодирование кодового слова, принятого из канала, осуществляется в нескольких смежных классах. Число смежных классов, в которых осуществляется декодирование, определяется числом возможных позиций стираний в заданном смежном классе. Код 3 при этом выступает в качестве кода, локализующего ошибки и несущего дополнительные информационные символы.
Для каждого слова, декодируемого в смежном классе, сначала осуществляется декодирование кодом 1, а затем кодом 2.
Каскадирование кодов с локализацией ошибок длинными внешними кодами
Конструкции кодов с локализацией ошибок можно улучшить путем применения длинных внешних кодов (например, кодов Рида – Соломона). В таком случае мы будем получать трехмерную каскадную конструкцию с локализацией ошибок.
Для улучшения помехоустойчивости трехмерной каскадной конструкции можно дополнительно реализовать декодирование внешним кодом Рида – Соломона с исправлением ошибок и стираний, так как во внутреннем блоковом коде очень легко реализовать стирания блоков.
Такая комбинация данных кодов удобна в сценариях управления (в каналах с телеметрией), так как позволяет гибко подключать внешний код в зависимости от условий передачи.
Некоторые частные примеры
Пример 1. Описание кода (32, 16) с внешними кодами длины 8
В качестве кода 2 выступает код Рида – Соломона (8, 5, 4) над полем GF(8), в качестве кода 1 – двоичный код (4, 3, 2) с проверкой на четность, в качестве кода 3 – двоичный код (8, 1, 8).
Процесс кодирования совпадает с описанным выше. Пять символов поля GF(8) кодируются кодом 2, затем записываются в двоичном представлении в виде матрицы и по столбцам кодируются двоичным кодом 1. Затем, в зависимости от последнего информационного символа, к нижней строке результирующей матрицы прибавляется слово кода 3 (нижняя строка либо инвертируется, либо нет в зависимости от информационного символа).
Важно отметить, что предлагаемый алгоритм декодирования для кода (32, 16) позволяет приблизиться к помехоустойчивости, которую обеспечивает декодирование по максимуму правдоподобия кода (32, 15) со значительным снижением требуемых вычислений (перебор по 56 вариантам стираний вместо перебора по 32786 кодовым словам каскадного кода). Результаты моделирования такого кода и сравнения декодирования согласно предлагаемому алгоритму и декодирования по максимуму правдоподобия приведены на рис.2. На нем же приведен и результат моделирования кода (32, 15) согласно предлагаемому алгоритму.
Пример 2. Описание кодов с внешними кодами длины 4–6
В данном примере рассмотрим ряд кодов с локализацией ошибок, где в качестве кода 2 выбираются коды Рида – Соломона длины 4:
В качестве кода 2 выступает код Рида – Соломона (4, 3, 2) над полем GF(16), в качестве кода 1 – двоичный код Хэмминга (8, 4, 4), в качестве кода 3 – код Рида – Соломона (4, 1, 4) над GF(16). Получаем результирующий код (32, 16) как в предыдущем примере.
В качестве кода 2 выступает код Рида – Соломона (5, 4, 2) над полем GF(16), в качестве кода 1 – двоичный код Хэмминга (8, 4, 4), в качестве кода 3 – код Рида – Соломона (5, 1, 5) над GF(16). Получаем результирующий код (40, 20).
В качестве кода 2 выступает код Рида – Соломона (6, 5, 2) над полем GF(16), в качестве кода 1 – двоичный код Хэмминга (8, 4, 4), в качестве кода 3 – код Рида – Соломона (6, 1, 6) над GF(16). Получаем результирующий код (48, 24).
Процесс кодирования не отличается от описанного выше в общем случае. Результат моделирования этих кодов приведен на рис.3. Помимо КЛО с внешним кодом длины 4 на рисунке приведена вероятность ошибки на бит для кода примера 1 с внешним кодом Рида – Соломона длины 8.
Результаты моделирования показывают, что данная конструкция для кода (32,16) незначительно проигрывает конструкции, рассмотренной в предыдущем примере, но для кодов (40, 20) и (48, 24) становится значительно лучше.
Сравнение с полярными кодами
Полярные коды являются классом линейных блочных кодов с высокими корректирующими свойствами. Они были предложены Э.Ариканом в 2009 году [12]. Поскольку в стандарте 5G NewRadio [13] представлен ряд полярных кодов с длиной блока, сопоставимой с рассматриваемой в примерах выше, целесообразно сравнить коды, приведенные в примерах, с полярными кодами. Оценки полярных кодов производились с использованием инструментов MATLAB R2023a. Сравнение вероятности ошибки на блок КЛО и полярных кодов приведено на рис.4.
Крестиками и звездочками показаны кривые для полярных кодов 5G NR, точками – кривые для КЛО. Из рисунка видно, что при сравнимой и даже при увеличенной в полтора раза длине блока полярные коды существенно проигрывают предлагаемой конструкции и начинают выигрывать только при длине блока в три раза большей длины КЛО.
Оценка сложности декодирования предлагаемой конструкции
Рассмотрим сложность декодирования примера 1. Процесс декодирования состоит из 56 декодирований кода Рида – Соломона (8,5) над полем GF(16). Каждое декодирование представляет собой решение трех линейных уравнений в поле GF(16), что представляет 15 шестнадцатеричных сложений по модулю 2. Таким образом производится 16 итераций. Таким образом, декодирование требует 53760 сложений по модулю 2. Остальными операциями можно пренебречь. Следует отметить, данная оценка сложности является оценкой сверху даже при существующей реализации и легко оптимизируется во много раз.
Рассмотрим сложность декодирования примера 2. К декодированию добавляется декодирование по максимуму правдоподобия кодов Хэмминга (8, 4), но существенно уменьшается число декодирований кодами Рида – Соломона. И поскольку при декодировании кодов Рида – Соломона исправляется только одно стирание, то основную сложность представляет многократное декодирование кода Хэмминга (8, 4) по МП, которое тоже легко оптимизируется. Всего на один декодер таких декодирований приходится n2 × 16. В настоящее время в проработке находится алгоритм, существенно уменьшающий число таких декодирований.
Направления дальнейших исследований
Следует отметить, что в настоящей работе приведены лишь первые результаты рассмотрения принципиально новой кодовой конструкции и новые методы декодирования как составляющих кодов, так и конструкции в целом.
В качестве направлений дальнейших исследований авторами рассматриваются:
Выводы
Предложена платформа создания декодеров коротких блоковых кодов, которая близка к максимуму правдоподобия и состоит в большинстве случаев из простейших логических операций.
Разработанная платформа имеет несколько принципиальных особенностей:
Благодарность
Авторы выражают признательность студентам МИЭМ НИУ ВШЭ Муляру А.А. и Ракланову Д.В. за участие в моделировании рассматриваемых в статье кодов.
ЛИТЕРАТУРА
Shannon C.E. A mathematical theory of communication // The Bell System Technical Journal. 1948. Vol. 27. No. 3. PP. 379–423.
Hamming R.W. Error detecting and error correcting codes // The Bell System Technical Journal. 1950. Vol. 29. No. 2. PP. 147–160.
Elias P. Error-free Coding // Transactions of the IRE Professional Group on Information Theory. 1954. Vol. 4. No. 4. PP. 29–37.
Berrou C. et al. Near Shannon limit error-correcting coding and decoding: Turbo-codes // Proceedings of IEEE International Conference on Communications, Geneva, Switzerland. 1993. Vol. 2. PP. 1064–1070.
Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974. 720 c.
Gallager R. Low-density parity-check codes // IRE Transactions on Information Theory. 1962. Vol. 8. No. 1. PP. 21–28.
Форни Д. Каскадные коды. М.: Наука, 1970. 207 c.
Блох Э., Зяблов В. Обобщение каскадных кодов. М.: Связь, 1976. 240 c.
Гинзбург В.В. Многомерные сигналы для непрерывного канала // Проблемы передачи информации. 1984. Т. 20. № 1. С. 28–46.
Ungerboeck G. Trellis-coded modulation with redundant signal sets. Part I: introduction // IEEE Communications Magazine. 1987. Vol. 25. No. 2. PP. 5–11.
Зяблов В.В. и др. Высокоскоростная передача сообщений в реальных каналах. М.: Радио и связь, 1991. 287 c.
Arıkan E. Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels // IEEE Transactions on Information Theory. 2009. Vol. 55. No. 7. PP. 3051–3073.
PP TS 38.212. Multiplexing and channel coding (Release 18). 2023.
В.В.Зяблов, д.т.н., главный научный сотрудник ИППИ РАН им А.А. Харкевича / zyablov@iitp.ru,
С.Л.Портной, д.т.н., проф. Московского института электроники и математики им. А. Н.Тихонова НИУ ВШЭ / sportnoy@hse.ru,
С.Е.Никитин, ст. преподаватель МИЭМ НИУ ВШЭ / snikitin@hse.ru,
А.Д.Волошин, магистрант МИЭМ НИУ ВШЭ / advoloshin@edu.hse.ru,
Н.С.Клюев, магистрант МИЭМ НИУ ВШЭ / nsklyuev@edu.hse.ru
УДК 621.391, DOI: 10.22184/2070-8963.2025.125.1.64.69
Рассматривается возможность переосмысления устоявшихся кодовых конструкций. Предлагается новая модификация традиционных каскадных и обобщенных каскадных кодов, что в свою очередь создает принципиально новое семейство кодов и открывает перспективы для разработки новых алгоритмов декодирования. Приведены три примера построения кодов с локализацией ошибок и результаты их моделирования. Описаны направления дальнейших исследований новых классов кодов.
Введение
С появлением первых работ Шеннона и Хемминга [1, 2] начавшая уже тогда формироваться как отдельная самостоятельная наука теория помехоустойчивого кодирования всегда надолго опережала возможности ее практической реализации. Причем не всегда единственной причиной разрыва между теорией и практикой была задержка в развитии элементной базы. Часто, если не всегда, необходимо было посмотреть на одну и ту же проблему под другим углом. А это можно было сделать только по прошествии некоторого времени.
Приведем примеры:
- Итеративные коды (коды-произведения) были представлены Элайесом в 50-х годах прошлого века [3], и только в середине 90-х годов Клод Берру предложил на этой базе турбо-коды [4]. Да, конечно, Берру предлагал турбо-коды на основе сверточных кодов, а Элайес предлагал блочные, но идея турбирования применима и к тем, и к другим;
- конструкция OFDM, без которой немыслимы большинство современных радиотелекоммуникационных стандартов, была предложена Р.Галлагером как способ расширения доказательства теоремы Шеннона на каналы с переменными во времени параметрами также в 50-х годах прошлого века [5] и только спустя 30 лет появились первые разработки для телефонных dial-up-каналов, DSL и DVB, и только потом пришла очередь wireless;
- то же самое касается и LDPC, которые были предложены в докторской диссертации Р.Галлагера в 1963 году [6], но первые серьезные реализации начались более 30-ти лет спустя, хотя технически это можно было сделать гораздо раньше;
- не обошли этой участи и каскадные коды, предложенные Д.Форни в 1960-х [7]. Немного позже данная конструкция была обобщена Э.Блохом и В.Зябловым [8]. Много лет спустя из этой конструкции вышли полярные коды. Также она была обобщена на случай сигнально-кодовых конструкций (СКК) В.Гинзбургом [9], Г.Унгербеком [10], В.Зябловым и С.Портным [11].
Исходя из изложенного, нет ничего удивительного в том, что иногда свежий взгляд на давно известную кодовую конструкцию позволяет получить новое качество.
В данной работе предлагается еще одна модификация давно известных каскадных и обобщенных каскадных кодов, что приводит к созданию принципиально нового семейства кодов, и, как следствие, новых алгоритмов декодирования.
Краткое описание кодовой конструкции
Алгоритм кодирования описывается с использованием следующих терминов. Рассмотрим каскадный код, состоящий из двоичного кода (n1, k1, d1) [код 1] и кода Рида ‒ Соломона (n2, k2, d2) над полем GF(2k1) [код 2]. Также существует код (n2, k3, d3) над полем GF(2n1 – k1) [код 3]. Код 1 будем называть внутренним кодом, код 2 – внешним кодом, код 3 – кодом локализации ошибок.
Алгоритм кодирования состоит в следующем. k информационных символов записываются в две матрицы:
k1 х k2 и (n1 – k1) х k3.
Таким образом, k = k1 * k2 + (n1 – k1) * k3, n = n1 * n2.
Кодируем k2 символов поля GF(2k1) кодом 2.
Каждый символ кода 2 кодируем кодом 1 и получаем матрицу n1 x n2.
Кодируем k3 символов поля GF(2n1 – k1) кодом 3.
Умножаем символы кода 3 в недвоичном случае на квазислучайные элементы поля GF(2n1 – k1), последовательность которых известна на передающей и приемной стороне.
Прибавляем поразрядно символы кода 3 к нижней части матрицы каскадного кода.
Результирующая матрица является словом (n, k) кода и постолбцово передается в канал.
Хотя кодирование кода и состоит из линейных операций, оно не представляется в виде единой порождающей матрицы, поэтому в общем случае код не является линейным. Результирующий код является кодом с локализацией ошибок (КЛО). Иллюстрация процесса кодирования такого кода приведена на рис.1.
Сформулируем общую идею декодирования.
Декодирование кодового слова, принятого из канала, осуществляется в нескольких смежных классах. Число смежных классов, в которых осуществляется декодирование, определяется числом возможных позиций стираний в заданном смежном классе. Код 3 при этом выступает в качестве кода, локализующего ошибки и несущего дополнительные информационные символы.
Для каждого слова, декодируемого в смежном классе, сначала осуществляется декодирование кодом 1, а затем кодом 2.
Каскадирование кодов с локализацией ошибок длинными внешними кодами
Конструкции кодов с локализацией ошибок можно улучшить путем применения длинных внешних кодов (например, кодов Рида – Соломона). В таком случае мы будем получать трехмерную каскадную конструкцию с локализацией ошибок.
Для улучшения помехоустойчивости трехмерной каскадной конструкции можно дополнительно реализовать декодирование внешним кодом Рида – Соломона с исправлением ошибок и стираний, так как во внутреннем блоковом коде очень легко реализовать стирания блоков.
Такая комбинация данных кодов удобна в сценариях управления (в каналах с телеметрией), так как позволяет гибко подключать внешний код в зависимости от условий передачи.
Некоторые частные примеры
Пример 1. Описание кода (32, 16) с внешними кодами длины 8
В качестве кода 2 выступает код Рида – Соломона (8, 5, 4) над полем GF(8), в качестве кода 1 – двоичный код (4, 3, 2) с проверкой на четность, в качестве кода 3 – двоичный код (8, 1, 8).
Процесс кодирования совпадает с описанным выше. Пять символов поля GF(8) кодируются кодом 2, затем записываются в двоичном представлении в виде матрицы и по столбцам кодируются двоичным кодом 1. Затем, в зависимости от последнего информационного символа, к нижней строке результирующей матрицы прибавляется слово кода 3 (нижняя строка либо инвертируется, либо нет в зависимости от информационного символа).
Важно отметить, что предлагаемый алгоритм декодирования для кода (32, 16) позволяет приблизиться к помехоустойчивости, которую обеспечивает декодирование по максимуму правдоподобия кода (32, 15) со значительным снижением требуемых вычислений (перебор по 56 вариантам стираний вместо перебора по 32786 кодовым словам каскадного кода). Результаты моделирования такого кода и сравнения декодирования согласно предлагаемому алгоритму и декодирования по максимуму правдоподобия приведены на рис.2. На нем же приведен и результат моделирования кода (32, 15) согласно предлагаемому алгоритму.
Пример 2. Описание кодов с внешними кодами длины 4–6
В данном примере рассмотрим ряд кодов с локализацией ошибок, где в качестве кода 2 выбираются коды Рида – Соломона длины 4:
В качестве кода 2 выступает код Рида – Соломона (4, 3, 2) над полем GF(16), в качестве кода 1 – двоичный код Хэмминга (8, 4, 4), в качестве кода 3 – код Рида – Соломона (4, 1, 4) над GF(16). Получаем результирующий код (32, 16) как в предыдущем примере.
В качестве кода 2 выступает код Рида – Соломона (5, 4, 2) над полем GF(16), в качестве кода 1 – двоичный код Хэмминга (8, 4, 4), в качестве кода 3 – код Рида – Соломона (5, 1, 5) над GF(16). Получаем результирующий код (40, 20).
В качестве кода 2 выступает код Рида – Соломона (6, 5, 2) над полем GF(16), в качестве кода 1 – двоичный код Хэмминга (8, 4, 4), в качестве кода 3 – код Рида – Соломона (6, 1, 6) над GF(16). Получаем результирующий код (48, 24).
Процесс кодирования не отличается от описанного выше в общем случае. Результат моделирования этих кодов приведен на рис.3. Помимо КЛО с внешним кодом длины 4 на рисунке приведена вероятность ошибки на бит для кода примера 1 с внешним кодом Рида – Соломона длины 8.
Результаты моделирования показывают, что данная конструкция для кода (32,16) незначительно проигрывает конструкции, рассмотренной в предыдущем примере, но для кодов (40, 20) и (48, 24) становится значительно лучше.
Сравнение с полярными кодами
Полярные коды являются классом линейных блочных кодов с высокими корректирующими свойствами. Они были предложены Э.Ариканом в 2009 году [12]. Поскольку в стандарте 5G NewRadio [13] представлен ряд полярных кодов с длиной блока, сопоставимой с рассматриваемой в примерах выше, целесообразно сравнить коды, приведенные в примерах, с полярными кодами. Оценки полярных кодов производились с использованием инструментов MATLAB R2023a. Сравнение вероятности ошибки на блок КЛО и полярных кодов приведено на рис.4.
Крестиками и звездочками показаны кривые для полярных кодов 5G NR, точками – кривые для КЛО. Из рисунка видно, что при сравнимой и даже при увеличенной в полтора раза длине блока полярные коды существенно проигрывают предлагаемой конструкции и начинают выигрывать только при длине блока в три раза большей длины КЛО.
Оценка сложности декодирования предлагаемой конструкции
Рассмотрим сложность декодирования примера 1. Процесс декодирования состоит из 56 декодирований кода Рида – Соломона (8,5) над полем GF(16). Каждое декодирование представляет собой решение трех линейных уравнений в поле GF(16), что представляет 15 шестнадцатеричных сложений по модулю 2. Таким образом производится 16 итераций. Таким образом, декодирование требует 53760 сложений по модулю 2. Остальными операциями можно пренебречь. Следует отметить, данная оценка сложности является оценкой сверху даже при существующей реализации и легко оптимизируется во много раз.
Рассмотрим сложность декодирования примера 2. К декодированию добавляется декодирование по максимуму правдоподобия кодов Хэмминга (8, 4), но существенно уменьшается число декодирований кодами Рида – Соломона. И поскольку при декодировании кодов Рида – Соломона исправляется только одно стирание, то основную сложность представляет многократное декодирование кода Хэмминга (8, 4) по МП, которое тоже легко оптимизируется. Всего на один декодер таких декодирований приходится n2 × 16. В настоящее время в проработке находится алгоритм, существенно уменьшающий число таких декодирований.
Направления дальнейших исследований
Следует отметить, что в настоящей работе приведены лишь первые результаты рассмотрения принципиально новой кодовой конструкции и новые методы декодирования как составляющих кодов, так и конструкции в целом.
В качестве направлений дальнейших исследований авторами рассматриваются:
- выход на оптимальное декодирование блоковых кодов длины порядка 128 с эффективностью практически МП и невысокой сложностью. Основой этого должно явиться декодирование в самом коде и в его смежных классах;
- получение результатов трехмерной каскадной конструкции лучших, чем каскадная пара (255, 223) с алгоритмом Витерби k = 7, за счет улучшения внутреннего блокового кода и перехода к исправлению ошибок и стираний во внешнем коде Рида – Соломона;
- распространение данного подхода на сигнально-кодовые конструкции с целью таким способом получить оптимальный обмен скорости, помехоустойчивости и сложности декодирования.
Выводы
Предложена платформа создания декодеров коротких блоковых кодов, которая близка к максимуму правдоподобия и состоит в большинстве случаев из простейших логических операций.
Разработанная платформа имеет несколько принципиальных особенностей:
- специфическое декодирование внутреннего кода;
- списочное декодирование внешнего кода Рида – Соломона;
- составляющие коды очень короткие, и сложность суммарного декодера невысока;
- для повышения скорости кодирования используются новые типы кодов с декодированием по смежному классу и кодов локализации ошибок.
Благодарность
Авторы выражают признательность студентам МИЭМ НИУ ВШЭ Муляру А.А. и Ракланову Д.В. за участие в моделировании рассматриваемых в статье кодов.
ЛИТЕРАТУРА
Shannon C.E. A mathematical theory of communication // The Bell System Technical Journal. 1948. Vol. 27. No. 3. PP. 379–423.
Hamming R.W. Error detecting and error correcting codes // The Bell System Technical Journal. 1950. Vol. 29. No. 2. PP. 147–160.
Elias P. Error-free Coding // Transactions of the IRE Professional Group on Information Theory. 1954. Vol. 4. No. 4. PP. 29–37.
Berrou C. et al. Near Shannon limit error-correcting coding and decoding: Turbo-codes // Proceedings of IEEE International Conference on Communications, Geneva, Switzerland. 1993. Vol. 2. PP. 1064–1070.
Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974. 720 c.
Gallager R. Low-density parity-check codes // IRE Transactions on Information Theory. 1962. Vol. 8. No. 1. PP. 21–28.
Форни Д. Каскадные коды. М.: Наука, 1970. 207 c.
Блох Э., Зяблов В. Обобщение каскадных кодов. М.: Связь, 1976. 240 c.
Гинзбург В.В. Многомерные сигналы для непрерывного канала // Проблемы передачи информации. 1984. Т. 20. № 1. С. 28–46.
Ungerboeck G. Trellis-coded modulation with redundant signal sets. Part I: introduction // IEEE Communications Magazine. 1987. Vol. 25. No. 2. PP. 5–11.
Зяблов В.В. и др. Высокоскоростная передача сообщений в реальных каналах. М.: Радио и связь, 1991. 287 c.
Arıkan E. Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels // IEEE Transactions on Information Theory. 2009. Vol. 55. No. 7. PP. 3051–3073.
PP TS 38.212. Multiplexing and channel coding (Release 18). 2023.
Отзывы читателей
