Декодирование при помощи линейных программ: различия между версиями
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-сертификации'', которым не обладает большинство других стандартных субоптимальных декодеров. Это свойство открывает возможность использования широкого спектра эвристик для улучшения производительности декодирования, некоторые из которых были проанализированы, но в основном остаются неизученными. | ||
Версия от 17:12, 12 апреля 2023
Ключевые слова и синонимы
LP-декодирование; коды с исправлением ошибок; коды с малой плотностью проверок на четность; LDPC-коды; псевдокодовые слова; распространение доверия
Постановка задачи
Коды с исправлением ошибок являются фундаментальными инструментами, используемыми для передачи цифровой информации по ненадежным каналам. Их изучение восходит к работам Хэмминга и Шеннона, которые использовали их в качестве основы для разработки теории передачи информации. Проблема декодирования исходной информации вплоть до полной реализации потенциала системы коррекции ошибок часто является очень сложной, особенно для современных кодов, которые приближаются к теоретическим пределам каналов связи.
Под LP-декодированием [4, 5, 8] понимается применение релаксации линейного программирования (LP) к задаче декодирования кода с исправлением ошибок. Релаксация линейного программирования является стандартной техникой в алгоритмах аппроксимации и исследовании операций и занимает центральное место при изучении эффективных алгоритмов для поиска хороших (хотя и субоптимальных) решений очень сложных задач оптимизации [13]. LP-декодеры имеют строгие комбинаторные характеристики успеха декодирования, которые можно использовать для анализа эффективности исправления ошибок.
Наибольшую актуальность приобрело LP-декодирование кодов с малой плотностью проверок на четность (LDPC-кодов) [9] в силу высокого качества исправления ими ошибок. Применение LP-декодера для анализа этих кодов особенно привлекательно, потому что стандартные алгоритмы передачи сообщений, такие как распространение доверия (см. [15]), используемые для декодирования, часто трудно поддаются анализу, а производительность LP-декодирования тесно связана с этими методами.
Коды с исправлением ошибок и декодирование по принципу максимального правдоподобия
Вначале представим очень краткий обзор кодов с исправлением ошибок, достаточный для формулировки понятия LP-декодера. Более полное описание кодов с исправлением ошибок в данном контексте можно найти в учебниках, посвященных данному вопросу (например, [11]).
Двоичный код с исправлением ошибок представляет собой подмножество
Задача декодирования по принципу максимального правдоподобия (ML) выглядит следующим образом: пусть имеется принятое слово
(1)
Сложность задачи ML-декодирования сильно зависит от используемого кода. Для простых кодов, таких как код повторения
LP-декодирование
Поскольку ML-декодирование в общем случае может быть очень трудным, приходится обращаться к субоптимальным решениям, которые могут быть найдены эффективным образом. Вместо того, чтобы пытаться решить (1), LP-декодирование ослабляет ограничение
(2)
При этом политоп должен включать все кодовые слова и не включать ни одного целого некодового слова. Такой политоп
LP-декодер работает следующим образом. Нужно решить линейную программу в (2), чтобы получить
Сравнение с ML-декодированием
Успешным считается декодер, который выдает изначальное кодовое слово, переданное по каналу, а качество алгоритма измеряется вероятностью того, что это произойдет. (Другой распространенной невероятностной мерой является гарантия производительности в наихудшем случае, которая измеряет, сколько инвертированных разрядов может допустить алгоритм, чтобы при этом гарантированно добиться успеха). Заметим, что у* – это наиболее вероятное переданное кодовое слово у, но не всегда случается так, что
Рисунок 1. Политоп декодирования
На рисунке 1 представлена геометрическая перспектива LP-декодирования и его связь с точным ML-декодированием. Оба декодера используют одну и ту же целевую функцию LP, но с разными наборами ограничений. При точном ML-декодировании набор ограничений представляет собой выпуклую оболочку C кодовых слов (т. е. множество точек, которые являются выпуклыми комбинациями кодовых слов из C), тогда как в ослабленном LP-декодировании используется более объемный политоп
Нормальные конусы и С-симметрия
(Отрицательные) нормальные конусы для у (также называемые фундаментальными конусами [10]) определяется следующим образом:
Заметим, что
Вероятность успеха LP-декодера равна общей вероятностной мере
Этот анализ выполнен для конкретного переданного кодового слова
Определение 1. Правильный политоп
Использование двойной вспомогательной линии для доказательства границ ошибок
Для доказательства успешности LP-декодирования необходимо показать, что
(На самом деле, поскольку существование двойственной точки с нулевой стоимостью доказывает только то, что
Основные результаты
LP-декодеры в основном изучались в контексте кодов с малой плотностью проверок на четность [9] и их обобщений на коды расширителей [12]. Также были определены LP-декодеры для турбокодов [2], но результаты их применения не столь хороши. В данном кратком изложении основных результатов приводятся границы вероятности ошибки в кодовом слове (WER), или вероятности того, что декодер не выдает переданное слово при наличии шума в канале. Эти границы относятся к конкретным семействам кодов, которые определяются как бесконечное множество кодов возрастающей длины, чья скорость ограничена снизу некоторой константой. Границы даются в асимптотической форме (без инстанцирования констант) и только для двоичного симметричного канала.
Для LP-декодирования и смежных понятий были получены другие важные результаты, которые здесь не упоминаются. Некоторые из этих общих областей рассматриваются в следующем разделе; подробную библиографию можно найти в работе [3].
Коды с малой плотностью проверок на четность
Политоп
Теорема 1 [6]. Для любого коэффициента r > 0 имеется константа
Коды расширителей
Пропускная способность канала связи ограничивает сверху коэффициент, которого можно достичь для семейства кодов и при этом получить вероятность ошибок в кодовых словах, стремящуюся к нулю по мере увеличения длины кода. Пропускная способность
Теорема 2 [7]. Для любого p > 0 и любой скорости
Турбокоды
Преимуществом турбокодов [2] является то, что они могут быть кодироваться за линейное время, даже в потоковом режиме. Простой формой турбокода являются коды повторного накопления. LP-декодер для турбокодов и их разновидностей был впервые определен в [4, 5] и основан на решетчатой структуре компонентных сверточных кодов. Из-за некоторых свойств турбокодов невозможно доказать для них столь же сильные границы, как для LDPC-кодов, однако известно следующее:
Теорема 3 [5]. Существует семейство 1/2 - o(1) кодов повторного накопления длины n и константа
Сам метод декодирования может быть расширен многими способами. Добавляя избыточную информацию к описанию кода, можно получить более жесткие наборы ограничений для повышения производительности декодера при исправлении ошибок, хотя и с увеличением сложности. Адаптивные алгоритмы, которые пытаются добавить ограничения «на лету», также исследовались при помощи метода ветвления и границ или других техник. Кроме того, LP-декодирование стало мотивацией к использованию других методов из теории оптимизации при декодировании кодов с исправлением ошибок; соответствующие ссылки см. в [3].
Открытые вопросы
Метод LP-декодирования предлагает простой, эффективный и поддающийся анализу подход к декодированию кодов с исправлением ошибок. Известные на данный момент результаты служат доказательством того, что сильные границы возможны, но пока еще остаются без ответа важные вопросы. Хотя LP-декодеры могут достигать максимальной пропускной способности со временем декодирования, полиномиальным от длины кода, сложность декодера все еще экспоненциально зависит от разрыва между скоростью и пропускной способностью (как и для всех других известных доказуемо эффективных декодеров, также достигающих пропускной способности). Уменьшение этой зависимости было бы большим достижением, и теоретически LP-декодирование могло бы помочь в этом. Также важным направлением дальнейших исследований является повышение доли ошибок, исправляемых LP-декодированием.
Еще один интересный вопрос – существуют ли семейства кодов с линейным расстоянием и постоянной скоростью, для точного декодирования которых можно разработать линейные программы полиномиального размера. Другими словами, есть ли семейства кодов с описанными характеристиками, выпуклые обочки которых имеют полиномиальное число граней? Если да, то для такого семейства LP-декодирование будет эквивалентно ML-декодированию. Если нет, то это служит убедительным доказательством распространенного мнения, заключающегося в том, что субоптимальное декодирование при использовании хороших кодов неизбежно.
Преимуществом LP-декодирования является упомянутое ранее свойство ML-сертификации, которым не обладает большинство других стандартных субоптимальных декодеров. Это свойство открывает возможность использования широкого спектра эвристик для улучшения производительности декодирования, некоторые из которых были проанализированы, но в основном остаются неизученными.
LP-декодирование исследовалось большей частью для LDPC-кодов в симметричных каналах без запоминания данных. Линейные программы для турбокодов были определены, но доказанные до сих пор границы ошибок не являются удовлетворительным объяснением превосходной производительности, наблюдаемой на практике. Другие типы кодов и каналов были удостоены гораздо меньшего внимания или вообще остались вне поля зрения.
См. также
- Декодирование кодов Рида–Соломона
- Изучение высоких коэффициентов Фурье булевых функций
- Проверка линейности / тестирование кодов Адамара
- Списочное декодирование в приближении к максимальной пропускной способности: свернутые коды Рида–Соломона
Литература
1. Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24,384-386(1978)
2. Berrou, C., Glavieux, A., Thitimajshima, P.: Near Shannon limit error-correcting coding and decoding: turbo-codes. In: Proc. IEEE Int. Conf. Comm. (ICC), pp. 1064-1070. Geneva, 23-26 May 1993
3. Boston, N., Ganesan, A., Koetter, R., Pazos, S., Vontobel, P.: Papers on pseudocodewords. HP Labs, Palo Alto. http://www.pseudocodewords.info.
4. Feldman, J.: Decoding Error-Correcting Codes via Linear Programming. Ph.D. thesis, Massachusetts Institute of Technology (2003)
5. Feldman, J., Karger, D.R.: Decoding turbo-like codes via linear programming. In: Proc. 43rd annual IEEE Symposium on Foundations of Computer Science (FOCS), Vancouver, 16-19 November 2002
6. Feldman, J., Malkin, T., Servedio, R.A., Stein, C., Wainwright, M.J.: LP decoding corrects a constant fraction of errors. In: Proc. IEEE International Symposium on Information Theory, Chicago, 27 June - 2 July 2004
7. Feldman, J., Stein, C.: LP decoding achieves capacity. In: Symposium on Discrete Algorithms (SODA '05), Vancouver, January (2005)
8. Feldman, J., Wainwright, M.J., Karger, D.R.: Using linear programming to decode linear codes. In: 37th annual Conf. on Information Sciences and Systems (CISS '03), Baltimore, 12-14 March 2003
9. Gallager, R.: Low-density parity-check codes. IRE Trans. Inform. Theory, IT-8 , pp. 21 -28 (1962)
10. Koetter, R., Vontobel, P.: Graph covers and iterative decoding of finite-length codes. In: Proc. 3rd International Symposium on Turbo Codes and Related Topics, pp. 75-82, September 2003. Brest, France (2003)
11. MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. North-Holland, Amsterdam (1981)
12. Sipser, M., Spielman, D.: Expander codes. IEEE Trans. Inf. Theory 42,1710-1722(1996)
13. Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2003)
14. Wainwright, M., Jordan, M.: Variational inference in graphical models: the view from the marginal polytope. In: Proc. 41st Allerton Conf. on Communications, Control, and Computing, Monticello, October (2003)
15. Wiberg, N.: Codes and Decoding on General Graphs, Ph. D. thesis, Linkoping University, Sweden (1996)