4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 65: | Строка 65: | ||
Заметим, что <math>N_{\dot{y}}(\mathcal{P})</math> соответствует множеству векторов | Заметим, что <math>N_{\dot{y}}(\mathcal{P})</math> соответствует множеству векторов стоимости <math>\gamma</math>, таких, что <math>\dot{y}</math> является оптимальным решением (2). Множество <math>N_{\dot{y}}(\mathcal{C})</math> имеет аналогичную интерпретацию как множество векторов стоимости <math>\gamma</math>, для которых <math>\dot{y}</math> является кодовым словом при декодировании по принципу максимального правдоподобия (ML). Поскольку <math>\mathcal{P} \subset \mathcal{C}</math>, из определения следует, что <math>N_y(\mathcal{C}) \supset N_y(\mathcal{P})</math> для всех <math>y \in C</math>. На рис. 1 показаны эти два конуса и их взаимосвязь. | ||
Вероятность успеха LP-декодера равна общей вероятностной мере <math>N_{\dot{y}}(\mathcal{P})</math> при распределении на векторах | Вероятность успеха LP-декодера равна общей вероятностной мере <math>N_{\dot{y}}(\mathcal{P})</math> при распределении на векторах стоимости, определяемом каналом. Вероятность успеха ML-декодирования аналогичным образом связана с вероятностной мерой в нормальном конусе <math>N_y(\mathcal{C})</math>. Таким образом, расхождение между нормальными конусами <math>\mathcal{P}</math> и <math>\mathcal{C}</math> является мерой разрыва между точным ML- и расслабленным LP-декодированием. | ||
Строка 79: | Строка 79: | ||
'''Использование двойственной задачи для доказательства границ ошибок''' | '''Использование двойственной задачи для доказательства границ ошибок''' | ||
Для доказательства успешности LP-декодирования необходимо показать, что <math>\dot{y}</math> является оптимальным решением линейной программы (2). Если код C линейный, а релаксация – правильная и C-симметричная, то можно предположить, что <math>\dot{y} = 0^n</math>, а затем показать, что <math>0^n</math> является оптимальным. Рассмотрим ''двойственную задачу'' LP-декодирования в (2). Если существует | Для доказательства успешности LP-декодирования необходимо показать, что <math>\dot{y}</math> является оптимальным решением линейной программы (2). Если код C линейный, а релаксация – правильная и C-симметричная, то можно предположить, что <math>\dot{y} = 0^n</math>, а затем показать, что <math>0^n</math> является оптимальным. Рассмотрим ''двойственную задачу'' LP-декодирования в (2). Если существует допустимая точка двойственной линейной программы, имеющая ту же (т. е. нулевую) стоимость, что и точка <math>0^n</math> прямой линейной программы, то <math>0^n</math> должна быть оптимальной точкой в задаче LP-декодирования. Поэтому, чтобы доказать успешность LP-декодера, достаточно показать точку с нулевой стоимостью двойственной задачи. | ||
''(На самом деле, поскольку существование двойственной | ''(На самом деле, поскольку существование точки двойственной задачи с нулевой стоимостью доказывает только то, что <math>0^n</math> является одной из возможно многих оптимальных точек решения прямой задачи, необходимо проявить несколько большую осторожность; в данной статье рассмотрение этого вопроса не предусматривается).'' | ||
== Основные результаты == | == Основные результаты == | ||
Строка 87: | Строка 87: | ||
Для LP-декодирования и смежных понятий были получены другие важные результаты, которые здесь не упоминаются. Некоторые из этих общих областей рассматриваются в следующем разделе; подробную библиографию можно найти в работе [3]. | Для LP-декодирования и смежных понятий были получены многие другие важные результаты, которые здесь не упоминаются. Некоторые из этих общих областей рассматриваются в следующем разделе; подробную библиографию можно найти в работе [3]. | ||
'''Коды с малой плотностью проверок на четность''' | '''Коды с малой плотностью проверок на четность''' | ||
Политоп <math>\mathcal{P}</math> для LDPC-кодов, впервые определенный в [4, 8, 10], основан на лежащем в основе кода ''графе Таннера'' и имеет линейное число переменных и ограничений. Если граф Таннера достаточным образом | Политоп <math>\mathcal{P}</math> для LDPC-кодов, впервые определенный в [4, 8, 10], основан на лежащем в основе кода ''графе Таннера'' и имеет линейное число переменных и ограничений. Если граф Таннера достаточным образом расширяется, то известно, что LP-декодирование способно исправить постоянную долю ошибок в канале и, таким образом, имеет обратный экспоненциальному коэффициент ошибок. Это было доказано с помощью двойственной задачи: | ||
'''Теорема 1 [6]. Для | '''Теорема 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>\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] является то, что они могут | Преимуществом турбокодов [2] является то, что они могут кодироваться за линейное время, даже в потоковом режиме. Простой формой турбокода являются ''коды с повторением и накоплением''. LP-декодер для турбокодов и их разновидностей был впервые определен в работах [4, 5] и основывался на ''решетчатой'' структуре компонентных ''сверточных'' кодов. Из-за некоторых свойств турбокодов невозможно доказать для них столь же сильные границы, как для LDPC-кодов, однако известно следующее: | ||
'''Теорема 3 [5]. | '''Теорема 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>.''' | ||
== Применение == | == Применение == | ||
Строка 124: | Строка 123: | ||
Еще один интересный вопрос – существуют ли семейства кодов с линейным расстоянием и постоянной скоростью, для точного декодирования которых можно разработать линейные программы полиномиального размера. Другими словами, есть ли семейства кодов с описанными характеристиками, выпуклые | Еще один интересный вопрос – существуют ли семейства кодов с линейным расстоянием и постоянной скоростью, для точного декодирования которых можно разработать линейные программы полиномиального размера. Другими словами, есть ли семейства кодов с описанными характеристиками, выпуклые оболочки которых имеют полиномиальное число граней? Если да, то для такого семейства LP-декодирование будет эквивалентно ML-декодированию. Если нет, то это служит убедительным доказательством распространенного мнения, заключающегося в том, что субоптимальное декодирование при использовании хороших кодов неизбежно. | ||
правок