А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 15
Текст из файла (страница 15)
При построении кодов мы предполагали, что < 1/4.Вспомним, какой код соответствует такому графу. Поскольку длина кодового слова равна , а число контрольных сумм равно , то числокодовых слов не меньше 2 − . Таким образом, коэффициент полезногодействия кода заведомо не меньше − = 1 − . Далее, мы доказали, чторасстояние экспандерного кода будет не меньше . Мы хотим, чтобыкодовое расстояние кода (при данной скорости) было как можно больше. Это значит, что при каждом значении мы хотим максимизироватьсоответствующее ему .Теперь можно точно сформулировать задачу в терминах параметровэкспандера. Мы фиксируем (некоторое число меньше 1/4) и (некоторое число меньше 1).
Требуется найти максимальное = (, )(а также подходящее значение = (, )), для которого существуетэкспандер с указанными параметрами.Ранее мы доказали, что для существования экспандеров достаточно,чтобы выполнялись условия > 1 и∙(/) · · < 1/2.Это значит, что нам нужно найти максимальное = (, ) такое, чтодля некоторого = (, ) эти неравенства верны. Точное решение этойзадачи на поиск максимума довольно громоздко. Однако нетрудно подобрать значение , которое будет достаточно близко к макисмуму (длянашего исследования экспандерного кода этого приближения окажется7229. óÌÏÖÎÏÓÔØ ÄÅËÏÄÉÒÏ×ÁÎÉÑвполне достаточно).
Достаточно взять, например, = / (для некоторого достаточно малого коэффициента = ()). Прямая подстановка показывает, что при данном и при = log(3/ ) оба нужные намнеравенства выполняются. В самом деле, при выбранном неравенство > 1 очевидно. Чтобы убедиться, что и второе неравенство верное,его удобно прологарифмировать (по основанию 2).
При выбранных и получаем( )log(3)1log / + log(3/ ) log + log ()/ · log(3/ ) < −1,что можно переписать в видеlog / () + log + log log + log log + log < −1.После сделанных преобразований видно, что нужное нам неравенствовыполнено при достаточно малом () (для всех < 1).Для дальнейшего нам нужно запомнить только асимптотику полученного ответа: при фиксированном существует экспандер с параметромрасширения = (/ log ).Таким образом, мы выразили достижимое кодовое расстояние через : для произвольного > 0 можно построить экспандерный код со скоростью не менее (1 − ), исправляющий долю ошибок ( ) = ˙(/ log ).Полезно переписать это соотношение, выразив наоборот через .
Получается, что мы можем исправлять долю ошибок с помощью кода,скорость которого меньше (1 − ), где () = ( log ).Сравним полученную оценку на скорость экспандерного кода с оценкой Хэмминга. Напомним границу Хэмминга: всякий двоичный код, который позволяет исправлять ошибки в доле позиций , имеет скорость небольше (1 − ()), где () = log +(1 − ) − . При → 0 мы имеем ( ) = log + ( ). Таким образом, для малых экспандерный кодтребует не более чем в константу раз большей потери скорости по сравнению с (теоретически возможными) оптимальными кодами. Отметим, чтоэкспандерные коды дают один из лучших известных компромиссов междускоростью кода, кодовым расстоянием и быстротой декодирования.( )log(31)133( )1111111129.
Сложность декодированияВ предыдущем разделе был указан полиномиальный алгоритм декодирования для линейных кодов специального вида (LDPC). Возникает7329. óÌÏÖÎÏÓÔØ ÄÅËÏÄÉÒÏ×ÁÎÉÑвопрос: а возможен ли полиномиальный алгоритм декодирования (работающий полиномиальное время от длины кодового слова) для произвольных линейных кодов? (Мы ограничиваемся линейными кодами, так какв общем случае уже задание кода как множества кодовых слов имеетэкспоненциальный размер.)В наиболее естественной постановке этот вопрос остаётся открытым,но имеется следующий частичный отрицательный результат: задача онахождении ближайшего кодового слова является NP-трудной. (В этомразделе мы предполагаем знакомство читателя с начальными сведениямио классе NP.)Множество кодовых слов линейного кода над полем из двух элементов (подпространство в B ) можно задавать как базисом в нём, так иуравнениями, выделяющими его из всего пространства, и от одного задания можно перейти к другому за полиномиальное время (метод Гаусса).Поэтому, говоря о подпространстве, можно не уточнять, каким из двухспособов оно задано.Рассмотрим такую задачу:: -битовое слово = .
. . , подпространство ⊂ B ичисло .: узнать, можно ли так изменить не более битов в слове , чтобы оно после этого попало в .Эта задача очевидно принадлежит классу NP: если ответ положительный, то для доказательства этого достаточно указать изменяемые биты.. Эта задача является NP-полной.Из этой теоремы (её доказали Берлекэмп, МакЭлиес и ван Тилборг в1978 году, вскоре после появления понятия NP-полноты) следует, что иболее общая задача нахождения ближайшего элемента подпространства(кодового слова) является NP-трудной и вряд ли можно ожидать появления полиномиального алгоритма, её решающего.
(Впрочем, как мы ужеговорили, с точки зрения теории кодирования это мало что значит: насинтересуют не все подпространства, а только с достаточно большим расстоянием между точками, и декодировать мы хотим лишь слова, близкиек одной из точек.)Для доказательства заметим, что к этой задаче сводится задача омаксимальном разрезе (MAX-CUT): разбить вершины данного графа надва класса, чтобы число рёбер между вершинами разных классов быломаксимально.
Точнее, поскольку мы говорим о задачах разрешения, надосказать так: дан граф и число ; выяснить, можно ли разбить вершиныДаны1НадоТеоремаграфа на два класса так, чтобы рёбер с концами из разных классов7429. óÌÏÖÎÏÓÔØ ÄÅËÏÄÉÒÏ×ÁÎÉÑ.Сведение совсем простое. Сопоставим графу такой код: биты кодовогослова сопоставляются рёбрам графа; всякой раскраске вершин графа вдва цвета (одни вершины красятся в чёрный цвет, другие | в белый)соответствует такое кодовое слово: пишем единицы на тех рёбрах, концыкоторых покрашены в разные цвета, и нули на рёбрах с одноцветнымиконцами. Нетрудно проверить, что получился линейный код.
При этомнаибольший разрез в графе соответствет кодовому слову, которое ближевсего к слову из одних единиц. (Более формально, разрез с или болееразноцветными рёбрами существует тогда и только тогда, когда в словеиз одних единиц можно изменить не более − битов, получив кодовоеслово; здесь | число рёбер графа.)Остаётся установить, что задача MAX-CUT (в описанном варианте сответом «да/нет») является NP-полной. Покажем, как к ней свести задачу 3-SAT (стандартную при доказательствах NP-полноты; SAT означаетSATis˛ablility, выполнимость).В задаче 3-SAT требуется найти набор булевских значений , .
. . , ,удовлетворяющий некоторым условиям. Каждое условие относится к каким-то трём переменных и запрещает одну комбинацию их значений. Этообычно записывают в виде «дизъюнкта»: запрет комбинации (к примеру) = 1, = 0, = 1 записывается как ¬ ∨ ∨ ¬ . Задача в целомтогда становится конъюнкцией (логическим И) этих дизъюнктов. Будемпредполагать NP-полноту этой задачи известной.В качестве леммы докажем NP-полноту частного случая этой задачи,в котором запрещения должны быть симметричными: запрещая какую-тотройку значений (скажем, 1, 0, 1), мы должны запретить и противоположную тройку (0, 1, 0) для тех же переменных. Если ввести обозначениеNotAllEqual(, , ), означающее, что не все три бита , , одинаковы,то можно переформулировать этот частный случай так: вместо дизъюнкций ∨ ∨ трёх литералов (переменных или их отрицаний) мы пишемNotAllEqual(, , ).
При этом запрещается не только случай, когда онивсе ложны (как в дизъюнкции), но и случай, когда они все истинны. Этотчастный случай иногда называют NAESAT (Not All Equal SATis˛ablity).. Общая задача 3-SAT сводится к NAESAT.Прежде всего заметим, что решения задачи NAESAT выдерживаютсимметрию (замену всех значений на противоположные). Поэтому можновыбрать какую-то одну «спецпеременную» и наложить дополнительноеусловие: мы рассматриваем только наборы значений, где спецпеременнаяложна (равна нулю).было не меньше157Лемма1157117529.
óÌÏÖÎÏÓÔØ ÄÅËÏÄÉÒÏ×ÁÎÉÑЗаметим, что NotAllEqual(0, , ) = ∨ , так что дизъюнкцию двух(обычных) переменных и можно выразить как NotAllEqual(, , ),где | спецпеременная. Условие ∨ ∨ (запрещение всем литералам, , быть ложными) можно заменить двумя условиями ∨ = и ∨ , где | вспомогательная новая переменная (своя для каждой дизъюнкции): новая система условий выполнима тогда и только тогда, когдавыполнима старая. Остаётся выразить условие ∨ = , то есть запретитьвариант = 1, = 0, вариант = 1, = 0 и вариант = 0, = 0, = 1.Первые два соответствуют дизъюнкциям ¬ ∨ и ¬ ∨ , в которых толькодве переменные (и это мы выражать умеем).
В последнем случае беды небудет, если мы запретим и противоположный вариант = 1, = 1, = 0(он тоже не подходит и уже запрещён), написав NotAllEqual(, , ¬ ).Лемма доказана.Осталось свести задачу NAESAT к MAX-CUT. Для этого нам надопредставить значения переменных как варианты разбиений вершин графа.Для начала рассмотрим граф из двух групп по вершин и всех рёбермежду группами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
