4430
правок
Декодирование при помощи линейных программ: различия между версиями
Перейти к навигации
Перейти к поиску
Декодирование при помощи линейных программ (посмотреть исходный код)
Версия от 16:18, 12 апреля 2023
, 12 апреля 2023→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 74: | Строка 74: | ||
Определение 1. Правильный политоп P для двоичного кода C является C-симметричным, если для всех y | '''Определение 1'''. Правильный политоп <math>\mathcal{P}</math> для двоичного кода <math>\mathcal{C}</math> является <math>\mathcal{C}</math>-симметричным, если для всех <math>y \in \mathcal{P}</math> и <math>\dot{y} \in \mathcal{C}</math> верно <math>y \in \mathcal{P}</math>, где <math>y'_i = |y_i - \dot{y}_i |</math>. | ||
'''Использование двойной вспомогательной линии для доказательства границ ошибок''' | '''Использование двойной вспомогательной линии для доказательства границ ошибок''' | ||
Для доказательства успешности LP-декодирования необходимо показать, что | Для доказательства успешности LP-декодирования необходимо показать, что <math>\dot{y}</math> является оптимальным решением LP в (2). Если код <math>\mathcal{C}</math> линейный, а релаксация – правильная и <math>\mathcal{C}</math>-симметричная, можно предположить, что <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> является одной из возможно многих оптимальных точек решения прямой задачи, необходимо проявить несколько большую осторожность; в данной статье рассмотрение этого вопроса не предусматривается).'' | ||
== Основные результаты == | == Основные результаты == | ||