А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 16
Текст из файла (страница 16)
Максимальный разрез тут пересекает все рёбер.Любой другой разрез проигрывает ему по крайней мере рёбер.(Проще всего в этом убедиться с помощью такого трюка. Разрез |это разделение всех вершин на «белые» и «чёрные», величина разреза |это число рёбер с концами разных цветов. Рассмотрим произведение( + . . . + )( + . . . + ), в котором все и равны ±1. Значения соответствуют цветам вершин в одной группе, значения | вдругой.
При этом для знак «+» соответствует вершинам белого цвета,а для | наоборот. Раскрывая скобки, убеждаемся, что это произведение равно числу разноцветных рёбер минус число одноцветных. Когдавсе и равны 1, это произведение максимально и состоит из членов , равных единице и соответствующих рёбрам между долями.Замена единицы на минус единицу соответствует перекрашиванию вершины, при этом пропавшее ребро даёт уменьшение суммы на 2. Посколькувсе варианты, кроме = = 1 и = = −1, дают произведение небольше ( − 2) , видно, что пропадают по крайней мере рёбер.)Теперь соединим копий такого графа.
В этом графе есть 2 максимальных разрезов: в каждой группе надо разрезать все рёбра, но какую изполовин поместить по одну сторону разреза, а какую по другую, можновыбирать. Выбор одного из таких разрезов естественно кодируется последовательностью из битов. Пока что все 2 вариантов разреза одинаковохороши (разрезают все рёбра).Это уже не так, если мы добавим дополнительные рёбра. Пусть, ска211227629. óÌÏÖÎÏÓÔØ ÄÅËÏÄÉÒÏ×ÁÎÉÑ...12nжем, добавлен треугольник, соединяющий три вершины из разных копий.Из них разрезаны либо 0 (если все три вершины треугольника оказались содной стороны разреза), либо 2 ребра. Таким образом, такой треугольникдаёт премию в +2 ребра, если не все вершины с одной стороны (что какраз и соответствует соответствует NotAllEqual для битов из кода разреза)....Таким образом, вопрос о выполнимости набора NAESAT-ограниченийсводится к вопросу о наличии разреза из + 2 рёбер, где | количество ограничений.
Надо только выбрать больше 3 , чтобы никакойвыигрыш за счёт раз дополнительных рёбер не перевесил проигрыш, еслиразрез не разделит группы в одной из копий. (На самом деле достаточно потребовать > , поскольку в каждом треугольнике мы можемвыиграть только один разрез, получив 3 вместо 2.)2ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ77Предметный указатель3-SAT, задача, 74Берлекэмп (Berlekamp, Elwyn), 23, 73Бертран (Bertrand, Joseph Louis Francois), 24Бессель (Bessel, Friedrich Wilhelm), 56Боуз (Bose, Raj Chandra), 35, 40Капалбо (Capalbo, Michael R.), 70Чоудхури (Ray-Chaudhuri, Dwijendra Kumar), 35, 40Элайес [Элиас, Элайс] (Elias, Peter), 42, 47,48Форни (Forney, G. David), 22, 24, 31, 32Галлагер (Gallager, Robert G.), 61Гаусс (Gauss, Johann Carl Friedrich), 73Гилберт (Gilbert, Edgar N.), 7{9, 11, 22, 26,32Голдрайх (Goldreich, Oded), 57Адамар (Hadamard, Jacques Solomon), 29{33,45, 46, 54, 56, 57Хэмминг [Хемминг] (Hamming, Richard Wesley), 5, 6, 8, 12, 26, 29, 35, 37,40{42, 47Джонсон (Johnson, Selmer M.), 46, 47, 55,57Юстесен (Justesen, Jfirn), 24, 31Лагранж (Lagrange, Joseph-Louis), 41LDPC, low density parity-check code, 61MAX-CUT, 73Маллер (Muller, D.E.), 33NAESAT, задача, 74Ньютон (Newton, Sir Isaac), 41NP-полнота, 73задачи 3-SAT, 74задачи MAX-CUT, 74задачи NAESAT, 74Парсеваль(Parseval des Ch^enes, MarcAntoine), 46Паскаль (Pascal, Blaise), 41Плоткин (Plotkin, Morris), 26, 28, 29, 31, 47Рид (Reed, Irwing Stoy), 16, 22, 25, 31{33,36, 49, 54Рейнголд (Reingold, Omer), 70Шеннон (Shannon, Claude Elwood), 8Синглтон [Синглетон] (Singleton, RichardC.), 15, 16, 29, 31Сипсер (Sipser, Michael), 61Соломон (Solomon, Gustave), 16, 22, 25, 31{33, 36, 49, 54Спилман (Spielman, Daniel A.), 61Стирлинг (Stirling, James), 7Судан (Sudan, Madhu), 4Вадхан (Vadhan, Salil Vadhan), 70ван Тилборг (van Tilborg, Henk C.A.), 73volume bound, 6Вигдерсон (Wigderson, Avi), 70Возенкрафт (Wozencraft, John M.), 24, 31Адамар (Hadamard, Jacques Solomon), 29{33,45, 46, 54, 56, 57Адамара код, 29{33, 45, 46, 54, 56, 57алгоритм Берлекэмпа, 23алфавит, 5Бассалыго, Леонид Александрович, 47, 48Берлекэмп (Berlekamp, Elwyn), 23, 73Берлекэмпа алгоритм, 23Бертран (Bertrand, Joseph Louis Francois), 24Бертрана постулат, 24Бессель (Bessel, Friedrich Wilhelm), 56Бесселя неравенство, 56бином Ньютона, 41Бозе { Чоудхури { Хоквингема код, 35, 40Боуз (Bose, Raj Chandra), 35, 40буква, 5Вадхан (Vadhan, Salil Vadhan), 70ван Тилборг (van Tilborg, Henk C.A.), 73Варшамов, Ром Рубенович, 11, 22, 32Варшамова { Гилберта граница, 11, 22, 32Варшамова { Гилберта оценка, 11вероятностное декодирование, 32вероятностное декодирование спискомкода Адамара, 57взвешенная степень многочлена, 50Вигдерсон (Wigderson, Avi), 7078внешний код, 19внутренний код, 19Возенкрафт (Wozencraft, John M.), 24, 31Возенкрафта лемма, 24выполнимость, задача, 74Галлагер (Gallager, Robert G.), 61Гаусс (Gauss, Johann Carl Friedrich), 73Гаусса метод, 73Гилберт (Gilbert, Edgar N.), 7{9, 11, 22, 26,32Гилберта граница, 7{9, 26Голдрайх (Goldreich, Oded), 57Голдрайха { Левина теорема, 57границаВаршамова { Гилберта, 11, 22, 32Гилберта, 7{9, 26Джонсона, 46, 47, 55, 57Плоткина, 26, 28, 29, 31, 47Синглтона, 15, 16, 29, 31Хэмминга, 6, 8, 26, 29, 40, 42, 47Элайеса { Бассалыго, 47, 48декодер, 3, 6декодированиевероятностное, 32каскадного кода, 19кода Рида { Соломона, 16, 25полиномиальное, 32, 73списком, 42, 44декодирование спискомкаскадного кода, 54кода Адамара, 45, 46, 57кода Рида { Соломона, 49, 54Джонсон (Johnson, Selmer M.), 46, 47, 55,57Джонсона оценка (граница), 46, 47, 55, 57Еханин, Сергей Михайлович, 4задача 3-SAT, NP-полнота, 74задача NAESAT, NP-полнота, 74задача о максимальном разрезе, 73закон больших чисел для попарно независимых событий, 59избыточность, 5избыточность кода, 3интерполяционная формула Лагранжа, 41Кабатянский, Григорий Анатольевич, 4канал связи, 3, 5Капалбо (Capalbo, Michael R.), 70ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØкаскадный код, 18, 22декодирование списком, 54каскадный код, декодирование, 19код, 5Адамара, 29{33, 45, 46, 54, 56, 57Адамара, вероятностное декодирование списком, 57Адамара, декодирование списком, 45,46, 57БЧХ (Бозе { Чоудхури { Хоквингема),35, 40внешний, 19внутренний, 19избыточность, 3каскадный, 18, 22, 25каскадный, декодирование, 19коэффициент полезного действия, 6линейный, 10, 73линейный низкой плотности (LDPC),61линейный, проверочная матрица, 12минимальное расстояние, 5, 44Рида { Маллера, 33Рида { Соломона, 16, 22, 25, 31{33,36, 49, 54Рида { Соломона, декодирование списком, 49скорость, 6случайный, 9совершенный, 14Форни { Возенкрафта { Юстесена, 24,25, 31, 32Хэмминга, 12, 35, 37, 40, 41кодер, 3, 6кодовое слово, 5ближайшее, 73конкатенация кодов, 19контрольная сумма, 12коэффициент полезного действия кода, 6Лагранж (Lagrange, Joseph-Louis), 41Лагранжа интерполяционная формула, 41Левин, Леонид Анатольевич, 57леммаВозенкрафта, 24линейный код, 10, 73низкой плотности, 61максимальный разрез, 73МакЭлис (McEliece, Robert James), 73Маллер (Muller, D.E.), 33Марков Андрей Андреевич (старший, 1856{1922), 69Маркова неравенство, 6979ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØметод Гаусса, 73минимальное расстояние, 5, 44Монте-Карло метод, 59МакЭлис (McEliece, Robert James), 73неравенствоСинглтона, 15, 16, 29, 31неравенство Бесселя, 56неравенство Маркова, 69неравенство Чебышёва, 59Ньютон (Newton, Sir Isaac), 41Ньютона бином, 41оценкаВаршамова { Гилберта, 11Джонсона, 46, 47, 55, 57Плоткина, 26, 28, 29, 31, 47Синглтона, 15, 16, 29, 31Хэмминга, 6, 8, 47Элайеса { Бассалыго, 47, 48ошибки, исправление, 3, 5Парсеваль(Parseval des Ch^enes, MarcAntoine), 46Парсеваля равенство, 46Паскаль (Pascal, Blaise), 41Паскаля треугольник, 41Пифагор Самосский, 46Пифагора теорема, 46Плоткин (Plotkin, Morris), 26, 28, 29, 31, 47Плоткина оценка (граница), 26, 28, 29, 31,47полиномиальное декодирование, 32попарно независимые события, 59проверочная матрица линейного кода, 12пропуск, 18расстояние Хэмминга, 5, 26, 47расстояние, минимальное кода, 5Рейнголд (Reingold, Omer), 70Рид (Reed, Irwing Stoy), 16, 22, 25, 31{33,36, 49, 54Рида { Маллера код, 33Рида { Соломона код, 16, 22, 25, 31{33, 36,49, 54декодирование списком, 49Синглтон [Синглетон] (Singleton, RichardC.), 15, 16, 29, 31Синглтона неравенство (граница, оценка),15, 16, 29, 31Сипсер (Sipser, Michael), 61скорость кода, 6слово, 5случайные коды, 9совершенный код, 14Соломон (Solomon, Gustave), 16, 22, 25, 31{33, 36, 49, 54Спилман (Spielman, Daniel A.), 61степень взвешенная, 50стирание, 18Стирлинг (Stirling, James), 7Судан (Sudan, Madhu), 4теоремаГолдрайха { Левина, 57Пифагора, 46Форни, 22Чебышёва, 24Элайеса, 42треугольник Паскаля, 41Форни (Forney, G.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
