4551
правка
Декодирование при помощи линейных программ: различия между версиями
Перейти к навигации
Перейти к поиску
Декодирование при помощи линейных программ (посмотреть исходный код)
Версия от 17:12, 12 апреля 2023
, 12 апреля 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 103: | Строка 103: | ||
Теорема 2 [7]. Для любого p > 0 и любой скорости <math>r < \mathcal{C}_p</math> существует семейство кодов расширителей длины n, такое, что вероятность ошибок в кодовых словах при LP-декодировании в <math>BSC_p</math> составляет не более <math>2^{- \Omega(n)}</math>. | '''Теорема 2 [7]. Для любого p > 0 и любой скорости <math>r < \mathcal{C}_p</math> существует семейство кодов расширителей длины n, такое, что вероятность ошибок в кодовых словах при LP-декодировании в <math>BSC_p</math> составляет не более <math>2^{- \Omega(n)}</math>.''' | ||
| Строка 111: | Строка 111: | ||
Теорема 3 [5]. Существует семейство 1/2 - o(1) кодов повторного накопления длины n и константа | '''Теорема 3 [5]. Существует семейство 1/2 - o(1) кодов повторного накопления длины n и константа <math>\epsilon > 0</math>, такая, что в <math>BSC_p</math> и при <math>p < \epsilon</math> вероятность ошибок LP-декодера в кодовых словах не превышает <math>n^{- \Omega(1)}.''' | ||
== Применение == | |||
До недавних пор наибольшее внимание в контексте LP-декодирования уделялось LDPC-кодам. Применение линейных программ для этого семейства кодов не только служит интересной альтернативой более традиционным итерационным методам [ ], но и дает полезный инструмент для анализа этих методов; эта идея впервые была рассмотрена в работах [8, 10, 14]. Итеративные методы, такие как распространение доверия, используют локальные вычисления на графе Таннера для обновления аппроксимаций предельных вероятностей каждого бита кода. В этом типе анализа вершины политопа P называются псевдокодовыми словами и, как правило, совпадают с неподвижными точками этого итеративного процесса. Другие понятия структур, подобных псевдокодовым словам, такие как множества остановки, также совпадают с вершинами политопа. Понимание этих структур вдохновило разработчиков на создание новых кодов для итеративного и LP-декодирования. (Более полную библиографию этой работы см. в [3]). | До недавних пор наибольшее внимание в контексте LP-декодирования уделялось LDPC-кодам. Применение линейных программ для этого семейства кодов не только служит интересной альтернативой более традиционным итерационным методам [15], но и дает полезный инструмент для анализа этих методов; эта идея впервые была рассмотрена в работах [8, 10, 14]. Итеративные методы, такие как ''распространение доверия'', используют локальные вычисления на графе Таннера для обновления аппроксимаций предельных вероятностей каждого бита кода. В этом типе анализа вершины политопа <math>\mathcal{P}</math> называются ''псевдокодовыми словами'' и, как правило, совпадают с неподвижными точками этого итеративного процесса. Другие понятия структур, подобных псевдокодовым словам, такие как ''множества остановки'', также совпадают с вершинами политопа. Понимание этих структур вдохновило разработчиков на создание новых кодов для итеративного и LP-декодирования. (Более полную библиографию этой работы см. в [3]). | ||
Сам метод декодирования может быть расширен многими способами. Добавляя избыточную информацию к описанию кода, можно получить более жесткие наборы ограничений для повышения производительности декодера при исправлении ошибок, хотя и с увеличением сложности. Адаптивные алгоритмы, которые пытаются добавить ограничения «на лету», также исследовались при помощи метода ветвления и границ или других техник. Кроме того, LP-декодирование стало мотивацией к использованию других методов из теории оптимизации при декодировании кодов с исправлением ошибок; соответствующие ссылки см. в [3]. | Сам метод декодирования может быть расширен многими способами. Добавляя избыточную информацию к описанию кода, можно получить более жесткие наборы ограничений для повышения производительности декодера при исправлении ошибок, хотя и с увеличением сложности. Адаптивные алгоритмы, которые пытаются добавить ограничения «на лету», также исследовались при помощи метода ветвления и границ или других техник. Кроме того, LP-декодирование стало мотивацией к использованию других методов из теории оптимизации при декодировании кодов с исправлением ошибок; соответствующие ссылки см. в [3]. | ||
== Открытые вопросы == | |||
Метод LP-декодирования предлагает простой, эффективный и поддающийся анализу подход к декодированию кодов с исправлением ошибок. Известные на данный момент результаты служат доказательством того, что сильные границы возможны, но пока еще остаются без ответа важные вопросы. Хотя LP-декодеры могут достигать максимальной пропускной способности со временем декодирования, полиномиальным от длины кода, сложность декодера все еще экспоненциально зависит от разрыва между скоростью и пропускной способностью (как и для всех других известных доказуемо эффективных декодеров, также достигающих пропускной способности). Уменьшение этой зависимости было бы большим достижением, и теоретически LP-декодирование могло бы помочь в этом. Также важным направлением дальнейших исследований является повышение доли ошибок, исправляемых LP-декодированием. | Метод LP-декодирования предлагает простой, эффективный и поддающийся анализу подход к декодированию кодов с исправлением ошибок. Известные на данный момент результаты служат доказательством того, что сильные границы возможны, но пока еще остаются без ответа важные вопросы. Хотя LP-декодеры могут достигать максимальной пропускной способности со временем декодирования, полиномиальным от длины кода, сложность декодера все еще экспоненциально зависит от разрыва между скоростью и пропускной способностью (как и для всех других известных доказуемо эффективных декодеров, также достигающих пропускной способности). Уменьшение этой зависимости было бы большим достижением, и теоретически LP-декодирование могло бы помочь в этом. Также важным направлением дальнейших исследований является повышение доли ошибок, исправляемых LP-декодированием. | ||
| Строка 127: | Строка 127: | ||
Преимуществом LP-декодирования является упомянутое ранее свойство ML-сертификации, которым не обладает большинство других стандартных субоптимальных декодеров. Это свойство открывает возможность использования широкого спектра эвристик для улучшения производительности декодирования, некоторые из которых были проанализированы, но в основном остаются неизученными. | Преимуществом LP-декодирования является упомянутое ранее свойство ''ML-сертификации'', которым не обладает большинство других стандартных субоптимальных декодеров. Это свойство открывает возможность использования широкого спектра эвристик для улучшения производительности декодирования, некоторые из которых были проанализированы, но в основном остаются неизученными. | ||