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

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

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

Двоичный код с исправлением ошибок представляет собой подмножество 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.