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

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




Источник — http://pco.iis.nsk.su/wega/index.php/Декодирование_при_помощи_линейных_программ