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

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

Вероятность успеха LP-декодера равна общей вероятностной мере Ny(T) при распределении на векторах затрат, определяемых каналом. Вероятность успеха ML-декодирования аналогичным образом связана с вероятностной мерой в нормальном конусе Ny(C). Таким образом, расхождение между нормальными конусами P и C является мерой разрыва между точным ML- и расслабленным LP-декодированием.

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