4430
правок
Декодирование при помощи линейных программ: различия между версиями
Материал из WEGA
Декодирование при помощи линейных программ (посмотреть исходный код)
Версия от 15:54, 11 апреля 2023
, 11 апреля 2023→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
При этом политоп должен включать все кодовые слова и не включать ни одного целого некодового слова. Такой политоп P называется правильным | При этом политоп должен включать все кодовые слова и не включать ни одного целого некодового слова. Такой политоп <math>\mathcal{P}</math> называется ''правильным'' для кода C, если <math>\mathcal{P} \cap \{ 0, 1 \}^n = C</math>. | ||
LP-декодер работает следующим образом. | LP-декодер работает следующим образом. Нужно решить линейную программу в (2), чтобы получить <math>y_{LP} \in [0, 1]^n</math>. Если <math>y_{LP}</math> является целочисленным (т. е. все его элементы равны 0 или 1), вывести <math>y_{LP}</math>; в противном случае вывести «ошибка». Согласно определению правильного политопа, если LP-декодер выводит кодовое слово, то оно гарантированно равно ML-кодовому слову y*. Данный факт известен как ''свойство сертификата'' ML. | ||
'''Сравнение с ML-декодированием''' | '''Сравнение с ML-декодированием''' | ||
Успешным считается декодер, который выдает изначальное кодовое слово, переданное по каналу, а качество алгоритма измеряется вероятностью того, что это произойдет. (Другой распространенной невероятностной мерой является гарантия производительности в наихудшем случае, которая измеряет, сколько инвертированных разрядов может допустить алгоритм, чтобы при этом гарантированно добиться успеха). Заметим, что у* – это наиболее вероятное переданное кодовое слово у, но не всегда случается так, что | Успешным считается декодер, который выдает изначальное кодовое слово, переданное по каналу, а качество алгоритма измеряется вероятностью того, что это произойдет. (Другой распространенной невероятностной мерой является гарантия производительности в наихудшем случае, которая измеряет, сколько инвертированных разрядов может допустить алгоритм, чтобы при этом гарантированно добиться успеха). Заметим, что у* – это ''наиболее вероятное'' переданное кодовое слово у, но не всегда случается так, что <math>y^* = \dot{y}</math>. Однако ни один декодер не может работать лучше ML-декодера, поэтому полезно использовать ML-декодирование в качестве основы для сравнения. | ||
| Строка 78: | Строка 78: | ||
'''Использование двойной вспомогательной линии для доказательства границ ошибок''' | '''Использование двойной вспомогательной линии для доказательства границ ошибок''' | ||
Для доказательства успешности LP-декодирования необходимо показать, что у является оптимальным решением LP в (2). Если код C линейный, а релаксация – | Для доказательства успешности LP-декодирования необходимо показать, что у является оптимальным решением LP в (2). Если код C линейный, а релаксация – правильная и C-симметричная, можно предположить, что у = 0n, а затем показать, что 0n является оптимальным. Рассмотрим двойственную задачу LP-декодирования в (2). Если существует достижимая точка двойственной линейной программы, имеющая ту же стоимость (т. е. нулевую), что и точка 0n первичной линейной программы, то 0n должна быть оптимальной точкой в задаче LP-декодирования. Поэтому, чтобы доказать успешность LP-декодера, достаточно показать точку с нулевой стоимостью двойственной задачи. | ||
(На самом деле, поскольку существование двойственной точки с нулевой стоимостью доказывает только то, что 0n является одной из возможно многих оптимальных точек решения прямой задачи, необходимо проявить несколько большую осторожность; в данной статье рассмотрение этого вопроса не предусматривается). | (На самом деле, поскольку существование двойственной точки с нулевой стоимостью доказывает только то, что 0n является одной из возможно многих оптимальных точек решения прямой задачи, необходимо проявить несколько большую осторожность; в данной статье рассмотрение этого вопроса не предусматривается). | ||
