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

LP-декодер работает следующим образом. Нужно решить линейную программу в (2), чтобы получить <math>y_{LP} \in [0, 1]^n</math>. Если <math>y_{LP}</math> является целым (т. е. все его элементы равны 0 или 1), вывести <math>y_{LP}</math>; в противном случае вывести «ошибка». Согласно определению правильного политопа, если LP-декодер выводит кодовое слово, то оно гарантированно равно ML-кодовому слову y*. Данный факт известен как ''свойство сертификата'' ML.

Успешным считается декодер, который выдает изначальное кодовое слово, переданное по каналу, а качество алгоритма измеряется вероятностью того, что это произойдет. (Другой распространенной невероятностной мерой является гарантия производительности ''в наихудшем случае'', которая измеряет, сколько инвертированных разрядов может допустить алгоритм, чтобы при этом гарантированно добиться успеха). Заметим, что у* – это ''наиболее вероятное'' переданное кодовое слово у, но не всегда случается так, что <math>y^* = \dot{y}</math>. Однако ни один декодер не может работать лучше ML-декодера, поэтому полезно использовать ML-декодирование в качестве основы для сравнения.

На рисунке 1 представлена геометрическая перспектива LP-декодирования и его связь с точным ML-декодированием. Оба декодера используют одну и ту же целевую функцию LP, но с разными наборами ограничений. При точном ML-декодировании набор ограничений представляет собой выпуклую оболочку C кодовых слов (т. е. множество точек, которые являются выпуклыми комбинациями кодовых слов из C), тогда как в ослабленном LP-декодировании используется более объемный политоп <math>\mathcal{P}</math>. На рис. 1 четыре стрелки, обозначенные (a)-(d), соответствуют различным «зашумленным» версиям целевой функции LP. (a) Если шум очень мал, то целевая функция указывает на переданное кодовое слово <math>\dot{y}</math>, и, следовательно, и ML-декодирование, и LP-декодирование оказываются успешными, поскольку оба представляют переданное кодовое слово у в качестве оптимальной точки. (b) При повышении уровня шума ML-декодирование срабатывает, а LP-декодирование не удается, так как дробная вершина y' является оптимальной для релаксации. (c) При еще большем росте шума ML-декодирование не срабатывает, так как оптимальной теперь является вершина <math>y_3</math>; у LP-декодирования все еще имеется дробный оптимум y', так что эта ошибка в некотором смысле обнаружена. (d) Наконец, при сильном шуме и ML-декодирование, и LP-декодирование в качестве оптимума выбирают <math>y_3</math>, поэтому оба метода терпят неудачу, и ошибка не обнаружена. Заметим, что в последних двух случаях (c, d), когда ML-декодирование не срабатывает, неудача LP-декодера в некотором смысле является виной самого кода, а не декодера.