4551
правка
Декодирование при помощи линейных программ: различия между версиями
Материал из WEGA
Декодирование при помощи линейных программ (посмотреть исходный код)
Версия от 20:31, 12 марта 2023
, 12 марта 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> всегда является кодовым словом линейного кода; это пригодится позже. Когда код используется для коммуникации, кодовое слово y | ''Двоичный код с исправлением ошибок'' представляет собой подмножество <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>\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) выглядит следующим образом: пусть имеется полученное слово y € {0,1gn; найти кодовое слово y* 2 C, которое с наибольшей вероятностью было передано по каналу. Определив вектор у € {-1; +1gn, где Yi = 1 - 2j>, легко показать: | ''Задача декодирования по принципу максимального правдоподобия'' (ML) выглядит следующим образом: пусть имеется полученное слово y € {0,1gn; найти кодовое слово y* 2 C, которое с наибольшей вероятностью было передано по каналу. Определив вектор у € {-1; +1gn, где Yi = 1 - 2j>, легко показать: | ||
(1) у* =argminYVy, уес | (1) у* =argminYVy, уес | ||
