А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 13
Текст из файла (страница 13)
. . , . Чтобы получить малую вероятность ошибки, достаточно взять полиномиальное число попарно независимых векторов, тоесть 2 − 1 = poly( ), а тогда = (log ). (Это | для фиксированных и , оценку для общего случая см. ниже.)Теперь главное: все значения —( ) в силу линейности — определяются значениями —( ), .
. . , —( ), то есть битами. Возможных вариантовэтих значений 2 , то есть полиномиальное от количество. Вспомним,что нам разрешалось отгадывать с нескольких попыток: алгоритм B выдаёт не один набор коэффициентов, а полиномиальный (от ) списоквариантов. Так что нам позволено перепробовать эти варианты, и всёсходится.Оценим возникающие вероятности более подробно. Нам нужно восстановить значения в +1 точках.
Мы начинаем с того, что выбираемнезависимые векторы , . . . , и получаем из них попарно независимые векторы , . . . , − . Затем для каждой из + 1 точек мы проводим голосование с 2 − 1 участниками и получаем набор из + 1предполагаемых значений. Эта процедура предполагает известными значения —( ), . . . , —( ) и проводится 2 раз, для всех возможных вариантов.
Подчеркнём, что выбор случайных векторов , . . . , производитсятолько один раз: одни и те же векторы используются для всех +1 точеки во всех 2 попытках.111121116128. ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙДля данной точки события ( + ) ̸= ( + ) (всего 2 − 1событий при = 1, 2, .
. . , 2 − 1) являются попарно независимыми. Вероятность каждого из них не больше −. Поэтому вероятность того, чтовыборка окажется «плохой» (не меньше половины попаданий в ошибки,где ̸= ), не превосходит11 · 2 − 1 .Это | для данной точки ; вероятность того, что выборка окажетсяплохой хотя бы для одной из + 1 точек, не больше1 · 1 · ( + 1) 2 − 1и потому меньше , если2 > + 1 + 1 .1222А если выборка хороша для всех + 1 точек, то в список, выдава2емый алгоритмом B (и содержащий 2 вариантов), войдёт и правильный ответ (коэффициенты аффинной функции ). Длина списка и времяработы алгоритма B при этом полиномиальны от ( + 1)/ + 1 =poly(, 1/, 1/).228.
Линейные коды низкой плотностии экспандерыВ этом разделе мы вернёмся к линейным кодам и покажем, как можнопостроить линейный код (над полем F ), для которого не только кодирование, но и декодирование выполняется быстро. Идея построения такихкодов (LDPC, low density parity-check codes) была предложена Галлагером ещё в 1963 году, но потом эти коды были почти что забыты. Сипсери Спилман вернулись к ним в середине 1990-х годов и обнаружили ихсвязь с некоторым классом графов | экспандерами.2Линейные коды и графыЛинейный код над полем из двух элементов состоит из двоичных слов .
. . , биты которых удовлетворяют некоторым проверочным урав-нениям. Поскольку в поле только два элемента, достаточно указать, какие126228. ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙбиты входят в уравнение, и код задаётся двудольным графом (рис. 5). Влевой доле вершин , . . . , . Каждая вершина правой доли задаётуравнение: сумма тех битов, с которыми она соединена, равна нулю (каждое ребро соответствует вхождению бита в уравнение; кратные рёбране разрешены). Низкая плотность означает, что рёбер мало. Мы будемпредполагать, что все вершины слева имеют одинаковую степень (каждый бит входит в контрольных сумм), и что уравнений меньше, чемпеременных (и тем самым есть более одного кодового слова).1123...1 + 3 = 0nРис.
5. Проверочная матрица как граф.Пусть | некоторое множество вершин левой доли (переменных).Из них выходят || рёбер, и поэтому множество соседей () содержит не более || элементов. Если эта оценка близка к точной длямножеств небольшого размера, граф называют экспандером. Точнее,мы фиксируем некоторое > 0 и некоторое > 0 и требуем, чтобы| ( )| > (1 − ) | | при | | 6 .Это определение имеет смысл при достаточно малых ; в дальнейшем нампонадобятся значения < 1/4. Оно говорит, что соседи левых вершинсравнительно мало пересекаются друг с другом, и если взять не слишкоммного таких вершин, то за счёт пересечений множество соседей уменьшится не более чем в (1 − ) раз.
Слова «не слишком много» важны, таккак для больших множеств в правой доле просто не хватит вершин.(Отметим, что при малом необходимо брать достаточно большое ;при малых уже один общий сосед справа у двух вершин левой долиприводит к уменьшению более чем в (1 − ) раз | а вершины с общимсоседом точно будут, так как справа меньше вершин, чем слева.)6328. ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙ ( )| | ≤ | ( )| ≥ (1 − ) | |степень Рис. 6. К определению экспандера.Исправление ошибок и экспандерыМы отложим вопрос о существовании экспандеров с данными параметрами (число вершин слева , их степень , число вершин справа ,границы и ) и сначала посмотрим на параметры получающегося кода. Прежде всего отметим, что имеется 2 − кодовых слов (или дажебольше, если уравнений оказались линейно зависимыми).Мы уже говорили, что из || вершин левой доли исходит || рёбер;они приходят в (1 − ) || вершин.
Значит, имеется не более ||вершин, в которые входит более одного ребра (каждая такая вершинауменьшает число соседей по крайней мере на 1), и остаётся не менее(1 − 2) || вершин, в которые входит только одно ребро.Отсюда следует, что минимальное расстояние кода больше . Всамом деле, пусть два кодовых слова различны, и | те позиции (переменные), в которых они отличаются. Поскольку код линейный, будемсчитать, что есть кодовое слово, которое содержит единицы в позицияхиз (а второе слово нулевое). Мы видим, что если единиц не более ,то найдётся не менее (1 − 2) || «критических» контрольных сумм, которые содержат ровно одну единицу (и остальные нули). Если < 1/2,получаем противоречие: для кодовых слов все контрольные суммы должны быть равны нулю.
(Заметим, что некритические контрольные суммы6428. ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙтоже могут быть ненулевыми, если содержат нечётное число переменныхиз .)Раз минимальное расстояние больше , то можно корректировать до(/2) ошибок. Покажем, что при < 1/4 это можно делать с помощьюпростого алгоритма: пока есть ненулевые контрольные суммы, найдёмпеременную, изменение которой уменьшит их количество, и изменим. Нужно только убедиться, что такая переменная всегда найдётся (тоесть что мы не окажемся в «локальном минимуме»): после этого ясно,что число ненулевых сумм убывает, пока не достигнет нуля.Итак, пусть нам дано некоторое слово , которое отличается от кодового слова в некоторых позициях.
(Как и раньше, в силу линейности можно считать, что слово нулевое.) Пусть | соответствующеемножество позиций. Мы уже видели, что из выходит || рёбер, изкоторых в критические вершины ведёт не менее (1 − 2) ||, то естьбольше половины, если < 1/4. Значит, в найдётся переменная, изкоторой большинство рёбер ведут в критические контрольные суммы, ипотому её изменение (которое исправит по крайней мере эти суммы засчёт возможной порчи других соседей) уменьшит число плохих сумм.Всё? Не совсем. Дело в том, что и другие переменные, в том числе ивне , могут обладать тем же свойством (их изменение уменьшает числонарушений), и изменение этих переменных удалит текущее слово от искомого, увеличив множество ошибок .
(Предотвратить это, не зная, гдеошибки, мы не можем.) При этом число ненулевых контрольных суммвсё равно уменьшается, но если при таких изменениях множество превысит размер , то с этого момента все наши рассуждения потеряютсилу (может не найтись переменной, изменение которой уменьшает числоплохих сумм; кроме того, при || > все контрольные суммы могутоказаться хорошими, хотя и непусто).Почему размер не превысит ? Вспомним, что в начале у насбыло не более (/2) ошибок. Надо убедиться, что их число в ходеработы алгоритма увеличивается не более чем вдвое.
Дело в том, чторазмер связан с числом неверных сумм. Это число, как мы видели, неменьше (1 − 2) || > || и не больше || (общего числа соседей).Раз число неверных сумм убывает, а люфт в этом соотношении менеечем двукратный, размер может возрасти не более чем вдвое. (Строгоговоря, оценка (1 − 2) || для числа ненулевых контрольных суммверна, лишь если доля ошибок не превзошла . Но если до некоторогомомента число ошибок оставалось меньше , то и на следующем шагеэто неравенство не нарушится. По индукции получаем, что число ошибокеё1228.
ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙ65никогда не достигнет .)Ясно, что алгоритм этот полиномиальный (число шагов не большечисла уравнений и тем самым числа переменных, и каждый шаг тоже полиномиальный). При дополнительном предположении о том, что степеньвсех вершин справа не превосходит (1) (см. ниже о том, почему такиеэкспандеры существуют) и достаточно умелой реализации алгоритм декодирования получается почти линейным. Действительно, можно хранитьдля каждой переменной число содержащих её ненулевых контрольныхсумм; на каждом шаге надо выбирать наибольшее из этих чисел и затем корректировать соседей его соседей, что удобно делать с помощьюочереди с приоритетами.Известны также быстрые параллельные алгоритмы коррекции ошибок,но мы ограничимся уже сказанным.Существование экспандеровИтак, мы доказали, что на основе графа с вершинами в левой долеи вершинами в правой доле, в котором степень каждой вершины слеваравна и выполнено свойство экспандера с параметрами и < 1/4,можно кодировать слова из − битов словами из битов и быстроисправлять до (/2) ошибок.Остаётся доказать существование такого графа (при подходящем соотношении параметров).
Зафиксируем произвольное рациональное < 1(отношение числа вершин в правой и левой долях) и произвольное > 0.Мы подберём подходящие и , при которых существует экспандер любого размера с такими параметрами (для любых целых и с отношением ). Пусть фиксированы количества вершин в левой и правой долях:числа и , для которых / = . Будем выбирать двудольный графс вершинами слева и вершинами справа случайно: из каждой левойвершины выпускаем рёбер в правую долю (для каждой вершины случайно выбирается разных соседей; при этом для разных вершин выборделается независимо).Мы хотим доказать, что свойство расширения выполнено с положительной вероятностью. Если оно не выполнено, то в левой доле графанайдётся такое множество из 6 вершин, что все соседи его вершин (в правой доле) лежат в некотором множестве размера (1 − ) .Для одного ребра вероятность попасть в такое равна | |/ , для рёбер она не превосходит (| |/ ) (даже немного меньше за счёт того,что все соседей должны быть различными), и для разных вершин вы-6628.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
