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

(Отрицательные) ''нормальные конусы'' для <math>\dot{y}</math> (также называемые ''фундаментальными конусами'' [10]) определяются следующим образом:

Заметим, что <math>N_{\dot{y}}(\mathcal{P})</math> соответствует множеству векторов стоимости <math>\gamma</math>, таких, что <math>\dot{y}</math> является оптимальным решением (2). Множество <math>N_{\dot{y}}(\mathcal{C})</math> имеет аналогичную интерпретацию как множество векторов стоимости <math>\gamma</math>, для которых <math>\dot{y}</math> является кодовым словом при декодировании по принципу максимального правдоподобия (ML). Поскольку <math>\mathcal{P} \subset \mathcal{C}</math>, из определения следует, что <math>N_y(\mathcal{C}) \supset N_y(\mathcal{P})</math> для всех <math>y \in C</math>. На рис. 1 показаны эти два конуса и их взаимосвязь.

Вероятность успеха LP-декодера равна общей вероятностной мере <math>N_{\dot{y}}(\mathcal{P})</math> при распределении на векторах стоимости, определяемом каналом. Вероятность успеха ML-декодирования аналогичным образом связана с вероятностной мерой в нормальном конусе <math>N_y(\mathcal{C})</math>. Таким образом, расхождение между нормальными конусами <math>\mathcal{P}</math> и <math>\mathcal{C}</math> является мерой разрыва между точным ML- и расслабленным LP-декодированием.

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

'''Определение 1'''. Правильный политоп <math>\mathcal{P}</math> для двоичного кода C является C-симметричным, если для всех <math>y \in \mathcal{P}</math> и <math>\dot{y} \in C</math> имеет место <math>y \in \mathcal{P}</math>, где <math>y'_i = |y_i - \dot{y}_i |</math>.

'''Использование двойственной задачи для доказательства границ ошибок'''

Для доказательства успешности LP-декодирования необходимо показать, что <math>\dot{y}</math> является оптимальным решением линейной программы (2). Если код C линейный, а релаксация – правильная и C-симметричная, то можно предположить, что <math>\dot{y} = 0^n</math>, а затем показать, что <math>0^n</math> является оптимальным. Рассмотрим ''двойственную задачу'' LP-декодирования в (2). Если существует допустимая точка двойственной линейной программы, имеющая ту же (т. е. нулевую) стоимость, что и точка <math>0^n</math> прямой линейной программы, то <math>0^n</math> должна быть оптимальной точкой в задаче LP-декодирования. Поэтому, чтобы доказать успешность LP-декодера, достаточно показать точку с нулевой стоимостью двойственной задачи.

''(На самом деле, поскольку существование точки двойственной задачи с нулевой стоимостью доказывает только то, что <math>0^n</math> является одной из возможно многих оптимальных точек решения прямой задачи, необходимо проявить несколько большую осторожность; в данной статье рассмотрение этого вопроса не предусматривается).''

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

'''Теорема 2 [7]. Для любого p > 0 и любой скорости <math>r < \mathcal{C}_p</math> существует семейство передаваемых со скоростью <math>r</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-декодированию. Если нет, то это служит убедительным доказательством распространенного мнения, заключающегося в том, что субоптимальное декодирование при использовании хороших кодов неизбежно.