Декодирование при помощи линейных программ: различия между версиями

Для LP-декодирования и смежных понятий были получены другие важные результаты, которые здесь не упоминаются. Некоторые из этих общих областей рассматриваются в следующем разделе; подробную библиографию можно найти в работе [3].

Политоп <math>\mathcal{P}</math> для LDPC-кодов, впервые определенный в [4, 8, 10], основан на лежащем в основе кода ''графе Таннера'' и имеет линейное число переменных и ограничений. Если граф Таннера достаточным образом расширен, то известно, что LP-декодирование способно исправить постоянную долю ошибок в канале и, таким образом, имеет обратный экспоненциальному коэффициент ошибок. Это было доказано с помощью двойного свидетельства:

'''Теорема 1 [6]. Для любого коэффициента r > 0 имеется константа <math>\epsilon > 0</math> такая, что существует семейство <math>r</math> LDPC-кодов длины n, при работе с которым LP-декодер успешен до тех пор, пока каналом инвертированы не более <math>\epsilon n</math> разрядов. Отсюда следует, что существует константа <math>\epsilon' > 0</math>, такая, что вероятность ошибок в кодовых словах при <math>BSC_p</math> с <math>p < \epsilon'</math> составляет не более <math>2^{- \Omega(n)}</math>.'''

''Пропускная способность'' канала связи ограничивает сверху коэффициент, которого можно достичь для семейства кодов и при этом получить вероятность ошибок в кодовых словах, стремящуюся к нулю по мере увеличения длины кода. Пропускная способность <math>BSC_p</math> обозначается как <math>\mathcal{C}_p</math>. Используя семейство кодов, основанных на расширителях [12], LP-декодирование может достичь скорости, приближающейся к пропускной способности. Однако, по сравнению с LDPC-кодами, это достигается ценой увеличения сложности декодирования, так как размер линейной программы экспоненциально зависит от разницы между скоростью и пропускной способностью.

'''Теорема 2 [7]. Для любого p > 0 и любой скорости <math>r < \mathcal{C}_p</math> существует семейство кодов расширителей длины n, такое, что вероятность ошибок в кодовых словах при LP-декодировании в <math>BSC_p</math> составляет не более <math>2^{- \Omega(n)}</math>.'''

Преимуществом турбокодов [2] является то, что они могут быть кодироваться за линейное время, даже в потоковом режиме. Простой формой турбокода являются ''коды повторного накопления''. LP-декодер для турбокодов и их разновидностей был впервые определен в [4, 5] и основан на ''решетчатой'' структуре компонентных ''сверточных'' кодов. Из-за некоторых свойств турбокодов невозможно доказать для них столь же сильные границы, как для LDPC-кодов, однако известно следующее:

'''Теорема 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>.'''

 

Еще один интересный вопрос – существуют ли семейства кодов с линейным расстоянием и постоянной скоростью, для точного декодирования которых можно разработать линейные программы полиномиального размера. Другими словами, есть ли семейства кодов с описанными характеристиками, выпуклые обочки которых имеют полиномиальное число граней? Если да, то для такого семейства LP-декодирование будет эквивалентно ML-декодированию. Если нет, то это служит убедительным доказательством распространенного мнения, заключающегося в том, что субоптимальное декодирование при использовании хороших кодов неизбежно.