А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 14
Текст из файла (страница 14)
ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙборы независимы, так что надо возвести ещё в степень . Полученныйрезультат просуммируем по всем возможным и и получим оценку !(1−).∑ · − ·(1)=0Нам нужно, чтобы это выражение было меньше 1.
Воспользуемся оценкой для числа сочетаний: не превосходит (/ ) . (В самом деле,что ! > (/ ) , поскольку интегралR 6 / !, и остаётся заметить,ln , равный ( ln − )| , не превосходит своей верхней интегральной суммы ln 1 + ln 2 + . . . + ln = ln( !).)Оценивая сверху биномиальные коэффициенты, получаем − !(1−).·∑ (/ ) · (1 − )Если из второй скобки вынести наружу , то она станет обратной к третьей, и можно привести подобные члены, получится==11(1)=0"∑ (/ ) · (1−)·(1 − ) #=0(мы заодно вынесли общую степень ).
Заменяя (1 − ) на единицу, мылишь увеличим сумму:∑"(/ ) · ·=0 #.Мы хотим оценить эту сумму как геометрическую прогрессию, но покав основание входит . Его мы заменим на верхнюю оценку . Но дляэтого нужно, чтобы выражение в квадратных скобках росло с ростом ,то есть чтобы было больше 1. В этом предположении мы получаем(напомним, что / = ):"∑ (/) · ·=0 #.Теперь видно, как надо действовать: прежде всего мы выбираем так,чтобы было больше 1. При таком знаменатель геометрической прогрессии стремится к нулю при → 0, и при достаточно малых он будетменьше 1/2, что и требуется.28. ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙ67Однородные справа экспандерыУдобно иметь дело с экспандером, который регулярен не только слева, но и справа (все вершины справа имеют одинаковую степень). Этоможно использовать при оценке времени работы алгоритма.Снова зафиксируем произвольное рациональное < 1 (отношение числа вершин в правой и левой долях) и произвольное > 0.
Далее мыподберём такое целые и вещественное > 0, что для всех достаточно больших целых и с отношением существует двудольныйграф с вершинами слева (степени ) и вершинами справа (степени ′ = / ), для которого выполнено нужное нам свойство расширения(с параметрами и ).Итак, пусть фиксированы количества вершин в левой и правой долях:числа и , для которых / = .
Будем выбирать двудольный графс вершинами слева и вершинами справа случайно по следующемураспределению. Для каждой вершины слева возьмём копий, а для каждой вершины справа | ′ копий (это будут концы рёбер). Тогда слеваи справа будет одно и то же число = = ′ копий, и мы возьмёмслучайное взаимно однозначное соответствие между правыми и левымиконцами (каждое из паросочетаний между левыми и правыми концами выбирается с вероятностью 1/ !).
Это ещё не окончательная конструкция,т.к. построенный нами граф может содержать кратные (параллельные)рёбра. Временно мы разрешим кратные рёбра и покажем, что в определённом выше графе свойство расширения выполнено с положительной(и даже большей 1/2) вероятностью. Действительно, если нужное намсвойство не выполнено, то в левой доле графа найдётся такое множество из 6 вершин, что все соседи его вершин (в правой доле) лежатв некотором множестве размера (1 − ) . Оценим вероятность этогособытия для данных и .На наше распределение вероятностей можно смотреть следующимобразом. Можно считать, что сначала мы случайно выбираем правыхконцов, куда будут «отправлены» рёбра из (всего имеется вариантов), затем распределяем все ребра, выходящие из , между выбранными позициями (для этого имеется ( )! вариантов), после чего дополняем выбранные рёбер до полного паросочетания (для этого есть( − )! способов).
Всего, как и положено, получается · ( )! · ( − )! = !способов. (Хотя это представление зависит от множества , получающееся в результате распределение одно и то же для всех .)6828. ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙТеперь ограничим свой выбор на первом шаге: будем выбирать множество соседей не среди всех потенциальных правых концов рёбер,а лишь среди (экземпляров) вершин множества (таких экземпляроввсего ′ | | = (1 − ) ′ ). При этом число вариантов сокращается с до | | = − .
Теперь понятно, что вероятность события«все соседи лежат в множестве » равна отношению биномиальныхкоэффициентов:′(1′) − / .(1′)Просуммируем эту оценку по всем возможным и . Получается, чтовероятность того, что выбранный нами граф не является экспандером, непревосходит∑ · − · − / .Дальше рассуждаем почти также, как мы действовали при независимомвыборе соседей каждой вершины. Мы хотим подобрать такие значенияпараметров, чтобы данная сумма была меньше 1/2.
Для начала воспользуемся оценкой для числа сочетаний: не превосходит (/ )и не меньше (/ ) . (Нижняя оценка получается, если в произведении = · −− · . . . · − все дроби заменить на / .) Оценивая биномиальные коэффициенты и вынося общую степень , получаем(1)(1′)=01+11∑=01 ·(1 − )(1−)·(1 − ) ′ !.Вспоминая, что = ′ , мы видим, что по сравнению с предыдущимвычислением у нас появился множитель в последней скобке, в результате чего (1 − ) в показателе экспоненты заменяется на (2 − ):∑ (/ ) · (2−)·(1 − ) =0!.Дальше всё происходит по прежней схеме. Мы хотим, чтобы выражениев скобках росло с ростом . Для этого нужно, чтобы было больше 1.Выбрав (при заданном ) такое , можно заменить внутри скобок на , от чего сумма только увеличится. Также огрубим (2 − ) и (1 − )до 2 и 1 соответственно:∑ (/) · =0·2 !.6928.
ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙТеперь ряд превратился в геометрическую прогрессию, причём её знаменатель стремится к нулю при → 0. Следовательно, при достаточномалых он будет меньше 1/4, и тогда сумма ряда не превосходит 1/2.Подведём промежуточный итог: с вероятностью не меньше 1/2 случайновыбранное паросочетание даёт нам регулярный двудольный граф, возможно, с кратными рёбрами, обладающий свойством расширения.Устранение кратных рёбер потребует некоторого запаса в свойстверасширения. Для этого мы заменяем в приведённом выше вероятностномрассуждении параметр на ′ = /2. (Также запомним, что в этом случаестепень мы выбираем не меньше 1/′ = 2/.)Как устранить кратные рёбра? Из каждой вершины в левой доле графавыходит по рёбер.
Будем считать, что рёбра занумерованы по их левым концам (от 1 до = ). Нетрудно проверить, что для любых двухразличных , (в частности, соответствующих одной левой вершине |в этом случае возможно образование кратных рёбер) вероятность того,что их правые концы попадут в одну и ту же вершину справа, не превосходит 1/ . Суммируя эту вероятность по всем вершинам левой доли ипо всем парам рёбер, выходящим из одной вершины, получаем, что математическое ожидание числа пар кратных рёбер в графе не превосходит · (/ ) = ( / ). Вероятность того, что положительная величинаболее чем в два раза превышает своё математическое ожидание, должнабыть меньше 1/2 (неравенство Маркова).
Следовательно, с вероятностьюбольше 1/2 в случайно выбранном графе будет не больше ( / ) паркратных рёбер.Итак, с вероятностью не меньше 1/2 случайное паросочетание даётнам экспандер (с нужными параметрами), и в то же время с вероятностью больше 1/2 в случайно выбранном графе число кратных рёберограничено ( / ). Это значит, что с положительной вероятностьюдля случайного графа выполняются оба свойства. Таким образом, существует регулярный (слева и справа) экспандер, в котором не больше ( / ) пар кратных рёбер. Заметим, что величина ( / ) не зависит от числа вершин в графе.
Если число вершин достаточно велико посравнению с , в таком графе можно «распараллелить» кратные рёбра,лишь незначительно ухудшив свойство расширения.Опишем более подробно процедуру «распараллеливания». Назовём«запрещёнными» сами кратные рёбра, а также рёбра, имеющие с нимиобщую вершину (слева или справа). Пока в графе остаются кратные рёбра, будем производить операцию переклейки: берём одно из имеющихсякратных рёбер и обмениваем его правый конец с правым концом какого2222227028. ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙнибудь незапрещенного ребра. При этом мы позаботимся, чтобы все незапрещённые рёбра, использованные в переклейках, не имели общих концов(это можно обеспечить, если много больше числа кратных рёбер).Понятно, что после этой процедуры граф остался регулярным, и внём не осталось кратных рёбер.
Посмотрим, насколько могло изменитьсясвойство расширения графа. Раньше для всякого множества левых вершин множество соседей состояло не менее чем из (1 − ′ ) || правыхвершин. После переклейки рёбер множество () могло стать меньшеза счёт незапрещённых рёбер (выходящих из ), использованных в процедуре распараллеливания. Таких рёбер заведомо не больше || (левыеконцы всех этих рёбер различны).
Это значит, что в новом графе числососедей не меньше(1 − ′ ) || − || > (1 − ′ − ) ||.Таким образом, для нового графа свойство расширения выполняется сослегка ухудшенными параметрами: ′ заменяется на (′ + ). За счёт предусмотренного запаса (′ = /2) мы получаем экспандер с параметромрасширения .Таким образом, мы доказали, что при определённых значениях параметров (при любом > 0, при фиксированном отношении / , достаточно больших и достаточно малых ) экспандеры существуют (и, болеетого, существуют экспандеры с одинаковой степенью всех вершин в правой доле). Однако наше доказательство неявное | оно не даёт возможности построить экспандер с заданными параметрами достаточно быстро (аэто необходимо, чтобы организовать быстрое кодирование и декодирование для соответствующего кода равномерно по длинам кодовых слов). В2002 году Вадхан, Вигдерсон, Капалбо и Рейнголд [M. Capalbo, O. Reingold, S.
Vadhan, A. Wigderson, Randomness conductors and constant-degreelossless expanders, Proceedings of 34th Annual ACM Symposium on Theory of Computing, pp. 659{668, 2002] придумали явную конструкцию,которая для сколь угодно малого параметра расширения > 0 позволяетстроить экспандеры с нужным свойством за полиномиальное (от числавершин) время.11Параметры экспандерных кодовМы доказали существование экспандерных кодов и объяснили, чтодля них есть быстрые алгоритмы декодирования.
Однако до сих пор мыне обсуждали качество таких кодов | как соотносятся их коэффициент28. ìÉÎÅÊÎÙÅ ËÏÄÙ ÎÉÚËÏÊ ÐÌÏÔÎÏÓÔÉ É ÜËÓÐÁÎÄÅÒÙ71полезного действия (скорость) и кодовое расстояние (а значит, и числоисправляемых ошибок). Сейчас мы оценим скорость экспандерного кода,исправляющего заданную долю ошибок.Прежде всего нужно понять, как связаны параметры экспандера ихарактеристики соответствующего ему кода. Напомним, какие параметрыесть у экспандера:∙ число вершин слева и справа ( и соответственно; мы считаем,что < , и обозначаем отношение этих чисел = / );∙степень вершин слева (обозначается );параметры расширения и : всякое множество , состоящее изне более чем вершин левой доли, должно иметь не менее (1 −) | | соседей (в правой доле).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
