Полярный код (теория кодирования)

В теории информации полярный код — это линейный блочный код, исправляющий ошибки . Конструкция кода основана на множественной рекурсивной конкатенации короткого кода ядра, который преобразует физический канал в виртуальные внешние каналы. Когда количество рекурсий становится большим, виртуальные каналы имеют тенденцию иметь либо высокую надежность, либо низкую надежность (другими словами, они поляризуются или становятся разреженными), и биты данных распределяются по наиболее надежным каналам. Это первый код с явной конструкцией, позволяющий доказуемо достичь пропускной способности канала для симметричных дискретных каналов без памяти с двоичным входом (B-DMC) с полиномиальной зависимостью от разрыва в пропускной способности. ^[1] Полярные коды были разработаны Эрдалом Ариканом , профессором электротехники Билькентского университета.

Примечательно, что полярные коды имеют умеренную сложность кодирования и декодирования $O (n log n)$ , что делает их привлекательными для многих приложений. Более того, энергетическая сложность кодирования и декодирования обобщенных полярных кодов может достигать фундаментальных нижних границ энергопотребления двумерных схем с точностью до $O (n е полилог n)$ коэффициент для любого $ε > 0$ . ^[2]

Промышленное применение

Полярные коды имеют некоторые ограничения при использовании в промышленных целях. Прежде всего, первоначальная конструкция полярных кодов достигает пропускной способности, когда размеры блоков асимптотически велики с помощью декодера с последовательным подавлением. Однако при размерах блоков, используемых в промышленности, производительность последовательного подавления низкая по сравнению с четко определенными и реализованными схемами кодирования, такими как код с низкой плотностью проверки четности (LDPC) и турбокод . Производительность Polar можно улучшить с помощью последовательного декодирования списка отмены, но ее применимость в реальных приложениях все еще сомнительна из-за очень низкой эффективности реализации, вызванной итеративным подходом. ^[3]

В октябре 2016 года компания Huawei объявила, что достигла скорости 27 Гбит/с в 5G полевых испытаниях с использованием полярных кодов для кодирования каналов. Улучшения были внесены так, что производительность канала теперь практически сократила разрыв с пределом Шеннона , который устанавливает планку максимальной скорости для заданной полосы пропускания и заданного уровня шума. ^[4]

В ноябре 2016 года 3GPP согласился принять полярные коды для каналов управления eMBB (Enhanced Mobile Broadband) для интерфейса 5G NR (New Radio). На той же встрече 3GPP согласился использовать LDPC для соответствующего канала данных. ^[5]

PAC-код

В 2020 году Арикан представил новый метод полярного кодирования, получивший название сверточных кодов с корректировкой поляризации (PAC). На коротких длинах блоков такие коды превосходят как сверточные коды , так и декодирование списка с помощью CRC обычных полярных кодов. ^[6]^[7]

Нейронные полярные декодеры

Нейронные полярные декодеры (NPD) ^[8] представляют собой достижение в области канального кодирования, которое объединяет нейронные сети (НС) с полярными кодами, обеспечивая унифицированное декодирование для каналов с памятью или без нее, не требуя явной модели канала. Они используют четыре нейронные сети для аппроксимации функций полярного декодирования: NN внедрения (E), NN контрольного узла (F), NN битового узла (G) и NN внедрения в LLR (H). Веса этих нейронных сетей определяются путем оценки взаимной информации синтетических каналов. К концу обучения веса NPD фиксируются и затем могут использоваться для декодирования.

Вычислительная сложность NPD определяется параметризацией нейронных сетей, в отличие от решетчатых декодеров последовательного подавления (SC), ^[9] сложность которых определяется моделью канала и обычно используются для каналов с конечным состоянием (FSC). Вычислительная сложность NPD составляет ${\textstyle O(kdN\log _{2}N)}$ , где $k$ количество скрытых блоков в нейронных сетях, $d$ - размерность вложения, а $N$ длина блока. Напротив, вычислительная сложность решетчатых декодеров SC составляет $O(|{\mathcal {S}}|^{3}N\log _{2}N)$ , где ${\mathcal {S}}$ — пространство состояний модели канала.

NPD могут быть интегрированы в декодирование SC. ^[1] такие схемы, как декодирование списка SC и декодирование SC с помощью CRC. ^[10] Они также совместимы с неравномерными и неравномерными входными распределениями путем их интеграции в схему Хонды-Ямамото. ^[11] Такая гибкость позволяет использовать NPD в различных сценариях декодирования, улучшая производительность исправления ошибок при сохранении управляемой сложности вычислений.

Ссылки

^ Jump up to: ^а ^б Арикан, Эрдал (2009). «Поляризация канала: метод построения кодов достижения пропускной способности для симметричных каналов без памяти с двоичным входом» . Транзакции IEEE по теории информации . 55 (7): 3051–3073. arXiv : 0807.3917 . дои : 10.1109/TIT.2009.2021379 . ISSN 0018-9448 .
^ Блейк, Кристофер Г. (2017). «Энергопотребление цепей кодирования контроля ошибок» (PDF) . Университет Торонто . Проверено 18 октября 2019 г.
^ Ураган Эрдал; Наджиб уль Хасан; Лентмайер, Майкл; Монторси, Гвидо; Сайир, Джосси (2015). «Проблемы и некоторые новые направления кодирования каналов». arXiv : 1504.03916 [ cs.IT ].
^ «Huawei достигает скорости 5G 27 Гбит/с с помощью Polar Code» . Проверено 10 октября 2016 г.
^ «Итоговый отчет заседания №87 3GPP РАН1» . 3ГПП . Проверено 31 августа 2017 г. ^{[ мертвая ссылка ]}
^ Моради, Мохсен; Мозаммель, Амир; Цинь, Канцзян; Арикан, Эрдал (2020). «Производительность и сложность последовательного декодирования PAC-кодов». arXiv : 2012.04990 [ cs.IT ].
^ Яо, Ханвен; Фазели, Арман; Варди, Александр (2021). «Список расшифровки PAC-кодов Арикана» . Энтропия . 23 (7): 841. arXiv : 2005.13711 . Бибкод : 2021Entrp..23..841Y . дои : 10.3390/e23070841 . ПМЦ 8303677 . ПМИД 34209050 .
^ Ахарони, Зив; Хулейхель, Башар; Пфистер, Генри Д.; Пермутер, Хаим Х. (6 сентября 2023 г.). «Управляемые данными нейронные полярные коды для неизвестных каналов с памятью и без нее». arXiv : 2309.03148 [ cs.IT ].
^ Ван, Жуньсинь; Хонда, Юнья; Ямамото, Хиросукэ; Лю, Жунке; Хоу, Йи (2015). «Построение полярных кодов для каналов с памятью» . Семинар IEEE по теории информации 2015 г. – осень (ITW) . IEEE. стр. 187–191. дои : 10.1109/ITWF.2015.7360760 . ISBN 978-1-4673-7852-9 .
^ Таль, Идо; Варди, Александр (2015). «Списочная расшифровка полярных кодов» . Транзакции IEEE по теории информации . 61 (5): 2213–2226. arXiv : 1206.0050 . дои : 10.1109/TIT.2015.2410251 . ISSN 0018-9448 .
^ Хонда, Юнья; Ямамото, Хиросуке (2013). «Полярное кодирование без расширения алфавита для асимметричных моделей» . Транзакции IEEE по теории информации . 59 (12): 7829–7838. дои : 10.1109/TIT.2013.2282305 . ISSN 0018-9448 .

Внешние ссылки

Домашняя страница AFF3CT: Набор инструментов для быстрого исправления ошибок для высокоскоростного моделирования полярного кода в программном обеспечении.

[:0-1] Jump up to: ^а ^б Арикан, Эрдал (2009). «Поляризация канала: метод построения кодов достижения пропускной способности для симметричных каналов без памяти с двоичным входом» . Транзакции IEEE по теории информации . 55 (7): 3051–3073. arXiv : 0807.3917 . дои : 10.1109/TIT.2009.2021379 . ISSN 0018-9448 .

[2] Блейк, Кристофер Г. (2017). «Энергопотребление цепей кодирования контроля ошибок» (PDF) . Университет Торонто . Проверено 18 октября 2019 г.

[:1-3] Ураган Эрдал; Наджиб уль Хасан; Лентмайер, Майкл; Монторси, Гвидо; Сайир, Джосси (2015). «Проблемы и некоторые новые направления кодирования каналов». arXiv : 1504.03916 [ cs.IT ].

[:2-4] «Huawei достигает скорости 5G 27 Гбит/с с помощью Polar Code» . Проверено 10 октября 2016 г.

[:3-5] «Итоговый отчет заседания №87 3GPP РАН1» . 3ГПП . Проверено 31 августа 2017 г. ^{[ мертвая ссылка ]}

[:4-6] Моради, Мохсен; Мозаммель, Амир; Цинь, Канцзян; Арикан, Эрдал (2020). «Производительность и сложность последовательного декодирования PAC-кодов». arXiv : 2012.04990 [ cs.IT ].

[7] Яо, Ханвен; Фазели, Арман; Варди, Александр (2021). «Список расшифровки PAC-кодов Арикана» . Энтропия . 23 (7): 841. arXiv : 2005.13711 . Бибкод : 2021Entrp..23..841Y . дои : 10.3390/e23070841 . ПМЦ 8303677 . ПМИД 34209050 .

[8] Ахарони, Зив; Хулейхель, Башар; Пфистер, Генри Д.; Пермутер, Хаим Х. (6 сентября 2023 г.). «Управляемые данными нейронные полярные коды для неизвестных каналов с памятью и без нее». arXiv : 2309.03148 [ cs.IT ].

[9] Ван, Жуньсинь; Хонда, Юнья; Ямамото, Хиросукэ; Лю, Жунке; Хоу, Йи (2015). «Построение полярных кодов для каналов с памятью» . Семинар IEEE по теории информации 2015 г. – осень (ITW) . IEEE. стр. 187–191. дои : 10.1109/ITWF.2015.7360760 . ISBN 978-1-4673-7852-9 .

[10] Таль, Идо; Варди, Александр (2015). «Списочная расшифровка полярных кодов» . Транзакции IEEE по теории информации . 61 (5): 2213–2226. arXiv : 1206.0050 . дои : 10.1109/TIT.2015.2410251 . ISSN 0018-9448 .

[11] Хонда, Юнья; Ямамото, Хиросуке (2013). «Полярное кодирование без расширения алфавита для асимметричных моделей» . Транзакции IEEE по теории информации . 59 (12): 7829–7838. дои : 10.1109/TIT.2013.2282305 . ISSN 0018-9448 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]