Декодирование при помощи линейных программ

Ключевые слова и синонимы LP-декодирование; коды с исправлением ошибок; коды с малой плотностью проверок на четность; LDPC-коды; псевдокодовые слова; распространение доверия

Постановка задачи Коды с исправлением ошибок являются фундаментальными инструментами, используемыми для передачи цифровой информации по ненадежным каналам. Их изучение восходит к работам Хэмминга и Шеннона, которые использовали их в качестве основы для разработки теории передачи информации. Проблема декодирования исходной информации вплоть до полной реализации потенциала системы коррекции ошибок часто является очень сложной, особенно для современных кодов, которые приближаются к теоретическим пределам каналов связи.

Под LP-декодированием [4, 5, 8] понимается применение релаксации линейного программирования (LP) к задаче декодирования кода с исправлением ошибок. Релаксация линейного программирования является стандартной техникой в алгоритмах аппроксимации и исследовании операций и занимает центральное место при изучении эффективных алгоритмов для поиска хороших (хотя и субоптимальных) решений очень сложных задач оптимизации [13]. LP-декодеры имеют строгие комбинаторные характеристики успеха декодирования, которые можно использовать для анализа эффективности исправления ошибок.

Наибольшую актуальность приобрело LP-декодирование кодов с малой плотностью проверок на четность (LDPC-кодов) [9] в силу высокого качества исправления ими ошибок. Применение LP-декодера для анализа этих кодов особенно привлекательно, потому что стандартные алгоритмы передачи сообщений, такие как распространение доверия (см. [ ]), используемые для декодирования, часто трудно поддаются анализу, а производительность LP-декодирования тесно связана с этими методами.

Коды с исправлением ошибок и декодирование по принципу максимального правдоподобия Вначале представим очень краткий обзор кодов с исправлением ошибок, достаточный для формулировки понятия LP-декодера. Более полное описание кодов с исправлением ошибок в данном контексте можно найти в учебниках, посвященных данному вопросу (например, [11]).

Двоичный код с исправлением ошибок представляет собой подмножество C С {0,1gn. Скорость кода C равна r = log(jCj)/n. Линейный двоичный код – это линейное подпространство f0; 1gn. Кодовое слово представляет собой вектор y 2 C. Заметим, что 0n всегда является кодовым словом линейного кода; это пригодится позже. Когда код используется для коммуникации, кодовое слово y € С передается по зашумленному каналу, в результате чего приемник получает некоторое слово у € Е", где Е – некоторый алфавит, зависящий от модели канала. Обычно при LP-декодировании предполагается симметричный канал без запоминания данных. Одним из распространенных примеров таких каналов является двоичный симметричный канал (BSC) с параметром p, который будем называть BSCp, где 0 < p < 1/2. В канале BSCp поддерживается алфавит £ = f0; 1g; для каждого i принятый символ j>, равен y с вероятностью p, y,i = 1 - j>j в противном случае. LP-декодирование работает с более широким спектром каналов, но далее будет рассматриваться схема BSCp.

Задача декодирования по принципу максимального правдоподобия (ML) выглядит следующим образом: пусть имеется полученное слово y € {0,1gn; найти кодовое слово y* 2 C, которое с наибольшей вероятностью было передано по каналу. Определив вектор у € {-1; +1gn, где Yi = 1 - 2j>, легко показать: (1) у* =argminYVy, уес

Сложность задачи ML-декодирования сильно зависит от используемого кода. Для простых кодов, таких как код повторения C = f0n; 1ng, она проста; Для более сложных (и высокоскоростных) кодов, таких как LDPC-коды, ML-декодирование является NP-трудной задачей [ ].

LP-декодирование Поскольку ML-декодирование в общем случае может быть очень трудным, приходится обращаться к субоптимальным решениям, которые могут быть найдены эффективным образом. Вместо того, чтобы пытаться решить (1), LP-декодирование ослабляет ограничение y 2 C и требует, чтобы выполнялось y 2 P для некоторого кратко описываемого линейного политопа ?C [0;1]n, что дает следующую линейную программу:

При этом политоп должен включать все кодовые слова и не включать ни одного целого некодового слова. Такой политоп P называется правильным (подходящим) для кода C, если P\f0;1gn = C:

LP-декодер работает следующим образом. Решить линейную программу в (2), чтобы получить YLP 2 [0; 1]n. Если YLP является целочисленным (т.е. все элементы равны 0 или 1), вывести YLP; в противном случае вывести «ошибка». Согласно определению правильного политопа, если LP-декодер выводит кодовое слово, то оно гарантированно равно ML-кодовому слову y*. Данный факт известен как свойство сертификата ML.

Сравнение с ML-декодированием Успешным считается декодер, который выдает изначальное кодовое слово, переданное по каналу, а качество алгоритма измеряется вероятностью того, что это произойдет. (Другой распространенной невероятностной мерой является гарантия производительности в наихудшем случае, которая измеряет, сколько инвертированных разрядов может допустить алгоритм, чтобы при этом гарантированно добиться успеха). Заметим, что у* – это наиболее вероятное переданное кодовое слово у, но не всегда случается так, что у* = у. Однако ни один декодер не может работать лучше ML-декодера, поэтому полезно использовать ML-декодирование в качестве основы для сравнения.

Политоп декодирования P (пунктирная линия) и выпуклая оболочка C (сплошная линия) кодовых слов у, y1, y2 и y3. Также показаны четыре возможных случая (a-d) целевой функции и нормальные конусы для P и C. Рисунок 1.

На рисунке 1 представлена геометрическая перспектива LP-декодирования и его связь с точным ML-декодированием. Оба декодера используют одну и ту же целевую функцию LP, но с разными наборами ограничений. При точном ML-декодировании набор ограничений представляет собой выпуклую оболочку C кодовых слов (т. е. множество точек, которые являются выпуклыми комбинациями кодовых слов из C), тогда как в ослабленном LP-декодировании используется более объемный политоп P. На рис. 1 четыре стрелки, обозначенные (a)-(d), соответствуют различным «зашумленным» версиям целевой функции LP. (a) Если шум очень мал, то целевая функция указывает на переданное кодовое слово у, и, следовательно, и ML-декодирование, и LP-декодирование оказываются успешными, поскольку оба представляют переданное кодовое слово у в качестве оптимальной точки. (b) При повышении уровня шума ML-декодирование срабатывает, а LP-декодирование не удается, так как дробная вершина y0 является оптимальной для релаксации. (c) При еще большем росте шума ML-декодирование не срабатывает, так как оптимальной теперь является вершина y3; у LP-декодирования все еще имеется дробный оптимум y0, так что эта ошибка в некотором смысле обнаружена. (d) Наконец, при сильном шуме и ML-декодирование, и LP-декодирование в качестве оптимума выбирают y3, поэтому оба метода терпят неудачу, и ошибка не обнаружена. Заметим, что в последних двух случаях (c, d), когда ML-декодирование не срабатывает, неудача LP-декодера в некотором смысле является виной самого кода, а не декодера.

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

Щ(Т) = {y 2 Rn : J2 i(yi ~ 9i) > 0 для всех y 2 T), Ny(C) = {у 2 Rn : J2 i(yi ~ ji) > ° для всех y 2 c) :

Заметим, что Ny(T) соответствует множеству векторов затрат у, таких, что у является оптимальным решением (2). Множество Ny(C) имеет аналогичную интерпретацию как множество векторов затрат у, для которых у является кодовым словом при декодировании по принципу максимального правдоподобия (ML). Поскольку Р С С, из определения следует, что Ny(C) D Ny(P) для всех y 2 C. На рис. 1 показаны эти два конуса и их взаимосвязь.

Вероятность успеха LP-декодера равна общей вероятностной мере Ny(T) при распределении на векторах затрат, определяемых каналом. Вероятность успеха ML-декодирования аналогичным образом связана с вероятностной мерой в нормальном конусе Ny(C). Таким образом, расхождение между нормальными конусами P и C является мерой разрыва между точным ML- и расслабленным LP-декодированием.

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

Определение 1. Правильный политоп P для двоичного кода C является C-симметричным, если для всех y 2 P и y € С верно / € T, где yi0 = jyi - y{.

Использование двойной вспомогательной линии для доказательства границ ошибок Для доказательства успешности LP-декодирования необходимо показать, что у является оптимальным решением LP в (2). Если код C линейный, а релаксация – подходящая и C-симметричная, можно предположить, что у = 0n, а затем показать, что 0n является оптимальным. Рассмотрим двойственную задачу LP-декодирования в (2). Если существует достижимая точка двойственной линейной программы, имеющая ту же стоимость (т. е. нулевую), что и точка 0n первичной линейной программы, то 0n должна быть оптимальной точкой в задаче LP-декодирования. Поэтому, чтобы доказать успешность LP-декодера, достаточно показать точку с нулевой стоимостью двойственной задачи.

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

Основные результаты LP-декодеры в основном изучались в контексте кодов с малой плотностью проверок на четность [9] и их обобщений на коды расширителей [ ]. Также были определены LP-декодеры для турбокодов [2], но результаты их применения не столь хороши. В данном кратком изложении основных результатов приводятся границы вероятности ошибки в кодовом слове (WER), или вероятности того, что декодер не выдает переданное слово при наличии шума в канале. Эти границы относятся к конкретным семействам кодов, которые определяются как бесконечное множество кодов возрастающей длины, чья скорость ограничена снизу некоторой константой. Границы даются в асимптотической форме (без инстанцирования констант) и только для двоичного симметричного канала.

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

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

Теорема 1 [6]. Для любой скорости r > 0 имеется константа e > 0 такая, что существует семейство r LDPC-кодов длины n, при работе с которым LP-декодер успешен до тех пор, пока каналом инвертированы не более en разрядов. Отсюда следует, что существует константа e' > 0, такая, что вероятность ошибок в кодовых словах при BSCp с p < e' составляет не более 2-i2(n).

Коды расширителей Пропускная способность канала связи ограничивает сверху скорость, которую можно получить от семейства кодов и при этом получить вероятность ошибок в кодовых словах, стремящуюся к нулю по мере увеличения длины кода. Пропускная способность BSCp обозначается как Cp. Используя семейство кодов, основанных на расширителях [12], LP-декодирование может достичь скорости, приближающейся к пропускной способности. Однако, по сравнению с LDPC-кодами, это достигается ценой увеличения сложности декодирования, так как размер линейной программы экспоненциально зависит от разницы между скоростью и пропускной способностью.

Теорема 2 [ ]. Для любого p > 0 и любой скорости r < Cp существует семейство кодов расширителей длины n, такое, что вероятность ошибок в кодовых словах при LP-декодировании в BSCp составляет не более 2-Q(n).

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

Теорема 3 [5]. Существует семейство 1/2 - o(1) кодов повторного накопления длины n и константа e > 0, такая, что в BSCp и при p < e вероятность ошибок LP-декодера в кодовых словах не превышает n~ai~l\.

Применение До недавних пор наибольшее внимание в контексте LP-декодирования уделялось LDPC-кодам. Применение линейных программ для этого семейства кодов не только служит интересной альтернативой более традиционным итерационным методам [ ], но и дает полезный инструмент для анализа этих методов; эта идея впервые была рассмотрена в работах [8, 10, 14]. Итеративные методы, такие как распространение доверия, используют локальные вычисления на графе Таннера для обновления аппроксимаций предельных вероятностей каждого бита кода. В этом типе анализа вершины политопа P называются псевдокодовыми словами и, как правило, совпадают с неподвижными точками этого итеративного процесса. Другие понятия структур, подобных псевдокодовым словам, такие как множества остановки, также совпадают с вершинами политопа. Понимание этих структур вдохновило разработчиков на создание новых кодов для итеративного и LP-декодирования. (Более полную библиографию этой работы см. в [3]).

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

Открытые вопросы Метод LP-декодирования предлагает простой, эффективный и поддающийся анализу подход к декодированию кодов с исправлением ошибок. Известные на данный момент результаты служат доказательством того, что сильные границы возможны, но пока еще остаются без ответа важные вопросы. Хотя LP-декодеры могут достигать максимальной пропускной способности со временем декодирования, полиномиальным от длины кода, сложность декодера все еще экспоненциально зависит от разрыва между скоростью и пропускной способностью (как и для всех других известных доказуемо эффективных декодеров, также достигающих пропускной способности). Уменьшение этой зависимости было бы большим достижением, и теоретически LP-декодирование могло бы помочь в этом. Также важным направлением дальнейших исследований является повышение доли ошибок, исправляемых LP-декодированием.

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

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

LP-декодирование исследовалось большей частью для LDPC-кодов в симметричных каналах без запоминания данных. Линейные программы для турбокодов были определены, но доказанные до сих пор границы ошибок не являются удовлетворительным объяснением превосходной производительности, наблюдаемой на практике. Другие типы кодов и каналов были удостоены гораздо меньшего внимания или вообще остались вне поля зрения.

См. также ► Декодирование кодов Рида–Соломона ► Изучение высоких коэффициентов Фурье булевых функций ► Проверка линейности / тестирование кодов Адамара ► Списочное декодирование в приближении к максимальной пропускной способности: свернутые коды Рида–Соломона

Литература 1. Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24,384-386(1978) 2. Berrou, C., Glavieux, A., Thitimajshima, P.: Near Shannon limit error-correcting coding and decoding: turbo-codes. In: Proc. IEEE Int. Conf. Comm. (ICC), pp. 1064-1070. Geneva, 23-26 May 1993 3. Boston, N., Ganesan, A., Koetter, R., Pazos, S., Vontobel, P.: Papers on pseudocodewords. HP Labs, Palo Alto. http://www.pseudocodewords.info. 4. Feldman, J.: Decoding Error-Correcting Codes via Linear Programming. Ph.D. thesis, Massachusetts Institute of Technology (2003) 5. Feldman, J., Karger, D.R.: Decoding turbo-like codes via linear programming. In: Proc. 43rd annual IEEE Symposium on Foundations of Computer Science (FOCS), Vancouver, 16-19 November 2002 6. Feldman, J., Malkin, T., Servedio, R.A., Stein, C., Wainwright, M.J.: LP decoding corrects a constant fraction of errors. In: Proc. IEEE International Symposium on Information Theory, Chicago, 27 June - 2 July 2004 7. Feldman, J., Stein, C.: LP decoding achieves capacity. In: Symposium on Discrete Algorithms (SODA '05), Vancouver, January (2005) 8. Feldman, J., Wainwright, M.J., Karger, D.R.: Using linear programming to decode linear codes. In: 37th annual Conf. on Information Sciences and Systems (CISS '03), Baltimore, 12-14 March 2003 9. Gallager, R.: Low-density parity-check codes. IRE Trans. Inform. Theory, IT-8 , pp. 21 -28 (1962)

10. Koetter, R., Vontobel, P.: Graph covers and iterative decoding of finite-length codes. In: Proc. 3rd International Symposium on Turbo Codes and Related Topics, pp. 75-82, September 2003. Brest, France (2003) 11. MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. North-Holland, Amsterdam (1981) 12. Sipser, M., Spielman, D.: Expander codes. IEEE Trans. Inf. Theory 42,1710-1722(1996) 13. Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2003) 14. Wainwright, M., Jordan, M.: Variational inference in graphical models: the view from the marginal polytope. In: Proc. 41st Allerton Conf. on Communications, Control, and Computing, Monticello, October (2003) 15. Wiberg, N.: Codes and Decoding on General Graphs, Ph. D. thesis, Linkoping University, Sweden (1996)