4551
правка
Декодирование при помощи линейных программ: различия между версиями
Материал из WEGA
Декодирование при помощи линейных программ (посмотреть исходный код)
Версия от 16:53, 12 апреля 2023
, 12 апреля 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 91: | Строка 91: | ||
'''Коды с малой плотностью проверок на четность''' | '''Коды с малой плотностью проверок на четность''' | ||
Политоп <math>\mathcal{P}</math> для LDPC-кодов, впервые определенный в [4, 8, 10], основан на лежащем в основе кода ''графе Таннера'' и имеет линейное число переменных и ограничений. Если граф Таннера достаточным образом расширен, то известно, что LP-декодирование способно исправить постоянную долю ошибок в канале и, таким образом, имеет обратный экспоненциальному коэффициент ошибок. Это было доказано с помощью двойного свидетельства: | Политоп <math>\mathcal{P}</math> для LDPC-кодов, впервые определенный в [4, 8, 10], основан на лежащем в основе кода ''графе Таннера'' и имеет линейное число переменных и ограничений. Если граф Таннера достаточным образом расширен, то известно, что LP-декодирование способно исправить постоянную долю ошибок в канале и, таким образом, имеет обратный экспоненциальному коэффициент ошибок. Это было доказано с помощью двойного свидетельства: | ||
| Строка 98: | Строка 99: | ||
'''Коды расширителей''' | '''Коды расширителей''' | ||
''Пропускная способность'' канала связи ограничивает сверху коэффициент, которого можно достичь для семейства кодов и при этом получить вероятность ошибок в кодовых словах, стремящуюся к нулю по мере увеличения длины кода. Пропускная способность <math>BSC_p</math> обозначается как <math>\mathcal{C}_p</math>. Используя семейство кодов, основанных на расширителях [12], LP-декодирование может достичь скорости, приближающейся к пропускной способности. Однако, по сравнению с LDPC-кодами, это достигается ценой увеличения сложности декодирования, так как размер линейной программы экспоненциально зависит от разницы между скоростью и пропускной способностью. | |||
Теорема 2 [ ]. Для любого p > 0 и любой скорости r < | |||
Теорема 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-кодов, однако известно следующее: | |||
Преимуществом турбокодов [2] является то, что они могут быть кодироваться за линейное время, даже в потоковом режиме. Простой формой турбокода являются ''коды повторного накопления''. LP-декодер для турбокодов и их разновидностей был впервые определен в [4, 5] и основан на ''решетчатой'' структуре компонентных ''сверточных'' кодов. Из-за некоторых свойств турбокодов невозможно доказать для них столь же сильные границы, как для LDPC-кодов, однако известно следующее: | |||
