4551
правка
Декодирование при помощи линейных программ: различия между версиями
Материал из WEGA
Декодирование при помощи линейных программ (посмотреть исходный код)
Версия от 23:05, 11 апреля 2023
, 11 апреля 2023→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 43: | Строка 43: | ||
'''Сравнение с ML-декодированием''' | '''Сравнение с ML-декодированием''' | ||
Успешным считается декодер, который выдает изначальное кодовое слово, переданное по каналу, а качество алгоритма измеряется вероятностью того, что это произойдет. (Другой распространенной невероятностной мерой является гарантия производительности в наихудшем случае, которая измеряет, сколько инвертированных разрядов может допустить алгоритм, чтобы при этом гарантированно добиться успеха). Заметим, что у* – это ''наиболее вероятное'' переданное кодовое слово у, но не всегда случается так, что <math>y^* = \dot{y}</math>. Однако ни один декодер не может работать лучше ML-декодера, поэтому полезно использовать ML-декодирование в качестве основы для сравнения. | Успешным считается декодер, который выдает изначальное кодовое слово, переданное по каналу, а качество алгоритма измеряется вероятностью того, что это произойдет. (Другой распространенной невероятностной мерой является гарантия производительности ''в наихудшем случае'', которая измеряет, сколько инвертированных разрядов может допустить алгоритм, чтобы при этом гарантированно добиться успеха). Заметим, что у* – это ''наиболее вероятное'' переданное кодовое слово у, но не всегда случается так, что <math>y^* = \dot{y}</math>. Однако ни один декодер не может работать лучше ML-декодера, поэтому полезно использовать ML-декодирование в качестве основы для сравнения. | ||
[[Файл:LP_decoding.png]] | |||
Рисунок 1. Политоп декодирования <math>\mathcal{P}</math> (пунктирная линия) и выпуклая оболочка <math>\mathcal{C}</math> (сплошная линия) кодовых слов <math>\dot{y}, y_1, y_2</math> и <math>y_3</math>. Также показаны четыре возможных случая (a-d) целевой функции и нормальные конусы для <math>\mathcal{P}</math> и <math>\mathcal{C}</math>. | |||
На рисунке 1 представлена геометрическая перспектива LP-декодирования и его связь с точным ML-декодированием. Оба декодера используют одну и ту же целевую функцию LP, но с разными наборами ограничений. При точном ML-декодировании набор ограничений представляет собой выпуклую оболочку C кодовых слов (т. е. множество точек, которые являются выпуклыми комбинациями кодовых слов из C), тогда как в ослабленном LP-декодировании используется более объемный политоп P. На рис. 1 четыре стрелки, обозначенные (a)-(d), соответствуют различным «зашумленным» версиям целевой функции LP. (a) Если шум очень мал, то целевая функция указывает на переданное кодовое слово | |||
На рисунке 1 представлена геометрическая перспектива LP-декодирования и его связь с точным ML-декодированием. Оба декодера используют одну и ту же целевую функцию LP, но с разными наборами ограничений. При точном ML-декодировании набор ограничений представляет собой выпуклую оболочку C кодовых слов (т. е. множество точек, которые являются выпуклыми комбинациями кодовых слов из C), тогда как в ослабленном LP-декодировании используется более объемный политоп <math>\mathcal{P}</math>. На рис. 1 четыре стрелки, обозначенные (a)-(d), соответствуют различным «зашумленным» версиям целевой функции LP. (a) Если шум очень мал, то целевая функция указывает на переданное кодовое слово <math>\dot{y}</math>, и, следовательно, и ML-декодирование, и LP-декодирование оказываются успешными, поскольку оба представляют переданное кодовое слово у в качестве оптимальной точки. (b) При повышении уровня шума ML-декодирование срабатывает, а LP-декодирование не удается, так как дробная вершина y' является оптимальной для релаксации. (c) При еще большем росте шума ML-декодирование не срабатывает, так как оптимальной теперь является вершина <math>y_3</math>; у LP-декодирования все еще имеется дробный оптимум y', так что эта ошибка в некотором смысле обнаружена. (d) Наконец, при сильном шуме и ML-декодирование, и LP-декодирование в качестве оптимума выбирают <math>y_3</math>, поэтому оба метода терпят неудачу, и ошибка не обнаружена. Заметим, что в последних двух случаях (c, d), когда ML-декодирование не срабатывает, неудача LP-декодера в некотором смысле является виной самого кода, а не декодера. | |||
