4551
правка
Декодирование при помощи линейных программ: различия между версиями
Перейти к навигации
Перейти к поиску
Декодирование при помощи линейных программ (посмотреть исходный код)
Версия от 23:43, 12 марта 2023
, 12 марта 2023→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
''Задача декодирования по принципу максимального правдоподобия'' (ML) выглядит следующим образом: пусть имеется | ''Задача декодирования по принципу максимального правдоподобия'' (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) | (1) <math>y^* = \arg min _{y \in C} \sum_i \gamma_i y_i</math> | ||
Сложность задачи ML-декодирования сильно зависит от используемого кода. Для простых кодов, таких как код повторения C = | Сложность задачи ML-декодирования сильно зависит от используемого кода. Для простых кодов, таких как ''код повторения'' <math>C = \{ 0^n, 1^n \}</math>, она проста; для более сложных (и высокоскоростных) кодов, таких как LDPC-коды, ML-декодирование является NP-трудной задачей [1]. | ||
'''LP-декодирование''' | '''LP-декодирование''' | ||
Поскольку ML-декодирование в общем случае может быть очень трудным, приходится обращаться к субоптимальным решениям, которые могут быть найдены эффективным образом. Вместо того, чтобы пытаться решить (1), LP-декодирование ослабляет ограничение y | Поскольку 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> | |||