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

(Отрицательные) ''нормальные конусы'' для <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-декодера, достаточно показать точку с нулевой стоимостью двойственной задачи.