Аноним

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

Материал из WEGA
Строка 95: Строка 95:




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




'''Турбокоды'''
'''Турбокоды'''


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


== Применение ==
== Применение ==
4551

правка