4501
правка
Декодирование при помощи линейных программ: различия между версиями
Перейти к навигации
Перейти к поиску
Декодирование при помощи линейных программ (посмотреть исходный код)
Версия от 22:20, 13 апреля 2023
, 13 апреля 2023→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
''Двоичный код с исправлением ошибок'' представляет собой подмножество <math>C \subseteq \{ 0, 1 \}</math>. ''Скорость'' кода C равна r = log(|C|)/n. ''Линейный'' двоичный код – это линейное подпространство <math> \{0, 1 \}^n</math>. ''Кодовое слово'' представляет собой вектор <math>y \in C</math>. Заметим, что <math>0^n</math> всегда является кодовым словом линейного кода; | ''Двоичный код с исправлением ошибок'' представляет собой подмножество <math>C \subseteq \{ 0, 1 \}^n</math>. ''Скорость'' кода C равна <math>r = log(|C|)/n</math>. ''Линейный'' двоичный код – это линейное подпространство <math> \{0, 1 \}^n</math>. ''Кодовое слово'' представляет собой вектор <math>y \in C</math>. Заметим, что <math>0^n</math> всегда является кодовым словом линейного кода; этот факт пригодится позже. Когда код используется для коммуникации, кодовое слово <math>\dot{y} \in C</math> передается по ''зашумленному каналу'', в результате чего на приемник поступает некоторое ''принятое слово'' <math>\hat{y} \in \Sigma^n</math>, где <math>\Sigma</math> – некоторый алфавит, зависящий от модели канала. Обычно при LP-декодировании предполагается ''симметричный канал без запоминания данных''. Одним из распространенных примеров таких каналов является ''двоичный симметричный канал'' (BSC) с параметром p, который будем называть <math>BSC_p</math>, где 0 < p < 1/2. В канале <math>BSC_p</math> поддерживается алфавит <math>\Sigma = \{ 0, 1 \}</math>; для каждого i принятый символ <math>\hat{y}_i</math> равен <math>\dot{y}_i</math> с вероятностью p и <math>\hat{y}_i = 1 - \dot{y}_i</math> в противном случае. LP-декодирование работает с более широким спектром каналов, но далее будет рассматриваться схема <math>BSC_p</math>. | ||
''Задача декодирования по принципу максимального правдоподобия'' (ML) выглядит следующим образом: пусть имеется принятое слово <math>\hat{y} \in \{ 0, 1 \}^n</math>; найти кодовое слово <math>y^* \in C</math>, которое с наибольшей вероятностью было передано по каналу. Определив вектор <math>\gamma \in \{ -1, +1 \}^n</math>, где <math>\gamma_i = 1 - 2 \hat{y}_i</math>, легко показать: | ''Задача декодирования по принципу максимального правдоподобия'' (ML) выглядит следующим образом: пусть имеется принятое слово <math>\hat{y} \in \{ 0, 1 \}^n</math>; необходимо найти кодовое слово <math>y^* \in C</math>, которое с наибольшей вероятностью было передано по каналу. Определив вектор <math>\gamma \in \{ -1, +1 \}^n</math>, где <math>\gamma_i = 1 - 2 \hat{y}_i</math>, легко показать: | ||
(1) <math>y^* = \arg min _{y \in C} \sum_i \gamma_i y_i</math> | (1) <math>y^* = \arg min _{y \in C} \sum_i \gamma_i y_i</math> | ||
| Строка 32: | Строка 32: | ||
Поскольку ML-декодирование в общем случае может быть очень трудным, приходится обращаться к субоптимальным решениям, которые могут быть найдены эффективным образом. Вместо того, чтобы пытаться решить (1), LP-декодирование ослабляет ограничение <math>y \in C</math> и требует, чтобы выполнялось <math>y \in \mathcal{P}</math> для некоторого кратко описываемого линейного политопа <math>\mathcal{P} \subseteq [ 0, 1 ]^n</math>, что дает следующую линейную программу: | Поскольку ML-декодирование в общем случае может быть очень трудным, приходится обращаться к субоптимальным решениям, которые могут быть найдены эффективным образом. Вместо того, чтобы пытаться решить (1), LP-декодирование ослабляет ограничение <math>y \in C</math> и требует, чтобы выполнялось <math>y \in \mathcal{P}</math> для некоторого кратко описываемого линейного политопа <math>\mathcal{P} \subseteq [ 0, 1 ]^n</math>, что дает следующую линейную программу: | ||
(2) <math>y_{LP} = \arg min _{y \in \mathcal{P}} \ | (2) <math>y_{LP} = \arg min _{y \in \mathcal{P}} \sum_{i = 1}^n \gamma_i y_i</math> | ||
| Строка 38: | Строка 38: | ||
LP-декодер работает следующим образом. Нужно решить линейную программу в (2), чтобы получить <math>y_{LP} \in [0, 1]^n</math>. Если <math>y_{LP}</math> является | LP-декодер работает следующим образом. Нужно решить линейную программу в (2), чтобы получить <math>y_{LP} \in [0, 1]^n</math>. Если <math>y_{LP}</math> является целым (т. е. все его элементы равны 0 или 1), вывести <math>y_{LP}</math>; в противном случае вывести «ошибка». Согласно определению правильного политопа, если LP-декодер выводит кодовое слово, то оно гарантированно равно ML-кодовому слову y*. Данный факт известен как ''свойство сертификата'' ML. | ||