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

''Двоичный код с исправлением ошибок'' представляет собой подмножество <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) выглядит следующим образом: пусть имеется принятое слово <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>, легко показать:

(2) <math>y_{LP} = \arg min _{y \in \mathcal{P}} \sum_i^n \gamma_i y_i</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.

Успешным считается декодер, который выдает изначальное кодовое слово, переданное по каналу, а качество алгоритма измеряется вероятностью того, что это произойдет. (Другой распространенной невероятностной мерой является гарантия производительности ''в наихудшем случае'', которая измеряет, сколько инвертированных разрядов может допустить алгоритм, чтобы при этом гарантированно добиться успеха). Заметим, что у* – это ''наиболее вероятное'' переданное кодовое слово у, но не всегда случается так, что <math>y^* = \dot{y}</math>. Однако ни один декодер не может работать лучше ML-декодера, поэтому полезно использовать ML-декодирование в качестве основы для сравнения.

На рисунке 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-декодера в некотором смысле является виной самого кода, а не декодера.

(Отрицательные) нормальные конусы для у (также называемые фундаментальными конусами [10]) определяется следующим образом:

Заметим, что <math>N_{\dot{y}}(\mathcal{P})</math> соответствует множеству векторов затрат <math>\gamma</math>, таких, что <math>\dot{y}</math> является оптимальным решением (2). Множество <math>N_{\dot{y}}(\mathcal{C})</math> имеет аналогичную интерпретацию как множество векторов затрат <math>\gamma</math>, для которых <math>\dot{y}</math> является кодовым словом при декодировании по принципу максимального правдоподобия (ML). Поскольку <math>\mathcal{P} \subset \mathcal{C}</math>, из определения следует, что <math>N_y(\mathcal{C}) \supset N_y(\mathcal{P})</math> для всех <math>y \in \mathcal{C}</math>. На рис. 1 показаны эти два конуса и их взаимосвязь.

Вероятность успеха LP-декодера равна общей вероятностной мере <math>N_{\dot{y}}(\mathcal{P})</math> при распределении на векторах затрат, определяемых каналом. Вероятность успеха ML-декодирования аналогичным образом связана с вероятностной мерой в нормальном конусе <math>N_y(\mathcal{C})</math>. Таким образом, расхождение между нормальными конусами <math>\mathcal{P}</math> и <math>\mathcal{C}</math> является мерой разрыва между точным ML- и расслабленным LP-декодированием.

Этот анализ выполнен для конкретного переданного кодового слова <math>\dot{y}</math>, но хотелось бы применить его в общем случае. При работе с линейными кодами для большинства декодеров обычно можно предположить, что передается произвольное кодовое слово, поскольку область принятия решения для успешного декодирования симметрична. То же самое справедливо и для LP-декодирования (доказательство см. в [4]), при условии, что политоп <math>\mathcal{P}</math> является <math>\mathcal{C}</math>-''симметричным'', что определяется следующим образом:

'''Определение 1'''. Правильный политоп <math>\mathcal{P}</math> для двоичного кода <math>\mathcal{C}</math> является <math>\mathcal{C}</math>-симметричным, если для всех <math>y \in \mathcal{P}</math> и <math>\dot{y} \in \mathcal{C}</math> верно <math>y \in \mathcal{P}</math>, где <math>y'_i = |y_i - \dot{y}_i |</math>.

'''Использование двойной вспомогательной линии для доказательства границ ошибок'''

Для доказательства успешности LP-декодирования необходимо показать, что <math>\dot{y}</math> является оптимальным решением LP в (2). Если код <math>\mathcal{C}</math> линейный, а релаксация – правильная и <math>\mathcal{C}</math>-симметричная, можно предположить, что <math>\dot{y} = 0^n</math>, а затем показать, что <math>0^n</math> является оптимальным. Рассмотрим ''двойственную задачу'' LP-декодирования в (2). Если существует достижимая точка двойственной линейной программы, имеющая ту же стоимость (т. е. нулевую), что и точка <math>0^n</math> первичной линейной программы, то <math>0^n</math> должна быть оптимальной точкой в задаче LP-декодирования. Поэтому, чтобы доказать успешность LP-декодера, достаточно показать точку с нулевой стоимостью двойственной задачи.

''(На самом деле, поскольку существование двойственной точки с нулевой стоимостью доказывает только то, что <math>0^n</math> является одной из возможно многих оптимальных точек решения прямой задачи, необходимо проявить несколько большую осторожность; в данной статье рассмотрение этого вопроса не предусматривается).''

Для LP-декодирования и смежных понятий были получены другие важные результаты, которые здесь не упоминаются. Некоторые из этих общих областей рассматриваются в следующем разделе; подробную библиографию можно найти в работе [3].

Политоп <math>\mathcal{P}</math> для LDPC-кодов, впервые определенный в [4, 8, 10], основан на лежащем в основе кода ''графе Таннера'' и имеет линейное число переменных и ограничений. Если граф Таннера достаточным образом расширен, то известно, что LP-декодирование способно исправить постоянную долю ошибок в канале и, таким образом, имеет обратный экспоненциальному коэффициент ошибок. Это было доказано с помощью двойного свидетельства:

'''Теорема 1 [6]. Для любого коэффициента r > 0 имеется константа <math>\epsilon > 0</math> такая, что существует семейство <math>r</math> LDPC-кодов длины n, при работе с которым LP-декодер успешен до тех пор, пока каналом инвертированы не более <math>\epsilon n</math> разрядов. Отсюда следует, что существует константа <math>\epsilon' > 0</math>, такая, что вероятность ошибок в кодовых словах при <math>BSC_p</math> с <math>p < \epsilon'</math> составляет не более <math>2^{- \Omega(n)}</math>.'''

''Пропускная способность'' канала связи ограничивает сверху коэффициент, которого можно достичь для семейства кодов и при этом получить вероятность ошибок в кодовых словах, стремящуюся к нулю по мере увеличения длины кода. Пропускная способность <math>BSC_p</math> обозначается как <math>\mathcal{C}_p</math>. Используя семейство кодов, основанных на расширителях [12], LP-декодирование может достичь скорости, приближающейся к пропускной способности. Однако, по сравнению с LDPC-кодами, это достигается ценой увеличения сложности декодирования, так как размер линейной программы экспоненциально зависит от разницы между скоростью и пропускной способностью.

'''Теорема 2 [7]. Для любого p > 0 и любой скорости <math>r < \mathcal{C}_p</math> существует семейство кодов расширителей длины n, такое, что вероятность ошибок в кодовых словах при LP-декодировании в <math>BSC_p</math> составляет не более <math>2^{- \Omega(n)}</math>.'''

Преимуществом турбокодов [2] является то, что они могут быть кодироваться за линейное время, даже в потоковом режиме. Простой формой турбокода являются ''коды повторного накопления''. LP-декодер для турбокодов и их разновидностей был впервые определен в [4, 5] и основан на ''решетчатой'' структуре компонентных ''сверточных'' кодов. Из-за некоторых свойств турбокодов невозможно доказать для них столь же сильные границы, как для LDPC-кодов, однако известно следующее:

'''Теорема 3 [5]. Существует семейство 1/2 - o(1) кодов повторного накопления длины n и константа <math>\epsilon > 0</math>, такая, что в <math>BSC_p</math> и при <math>p < \epsilon</math> вероятность ошибок LP-декодера в кодовых словах не превышает <math>n^{- \Omega(1)}</math>.'''

 

Еще один интересный вопрос – существуют ли семейства кодов с линейным расстоянием и постоянной скоростью, для точного декодирования которых можно разработать линейные программы полиномиального размера. Другими словами, есть ли семейства кодов с описанными характеристиками, выпуклые обочки которых имеют полиномиальное число граней? Если да, то для такого семейства LP-декодирование будет эквивалентно ML-декодированию. Если нет, то это служит убедительным доказательством распространенного мнения, заключающегося в том, что субоптимальное декодирование при использовании хороших кодов неизбежно.