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

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-кодами, это достигается ценой увеличения сложности декодирования, так как размер линейной программы экспоненциально зависит от разницы между скоростью и пропускной способностью.