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