А.В. Чашкин - Задачи с некоторых семинаров по дискретной математике, страница 2

С другой стороныi=1P (Γi ) > 3 ⇒ 2k > 3m. Подставляя это неравенство в формулу Эйлера, получим k 6 3n − 6.Нетрудно заметить, что отсюда следует непланарность K5 . А вспоминая, что каждому ребрупринадлежат две вершины, получаем2k =nXi=1P (Bi ) 6 6n − 12,(1)откуда и следует, что найдется хотя бы одна вершина (обозначим ее Bn ), из которой выходитне более 5 ребер. Если их меньше пяти, то все доказано: убирая эту вершину, раскрасим (этоможно сделать по предположению индукции) оставшийся граф 5ю красками, а саму Bn —раскрасим в тот цвет, который не встречается среди 4х смежных с ним вершин. Пусть теперьтаких вершин ровно пять. Среди них найдутся две, которые не соединены друг с другом (этоследует из непланарности K5 ).

Возьмем эти две вершины и склеим их с Bn , получившийся графраскрасим. Т. о. мы получили раскраску графа без Bn , причем для раскраски вершин, смежныхс Bn было использовано только 4 цвета. Раскрасим Bn в оставшийся цвет — все доказано. Задача 6.

Пусть A ⊆ Bn , α ∈ Bn , (α ⊕ A) := {a + α|a ∈ A}. Найтитакое n, при которомTдля любого A с условием |A| < n найдется такое α, что (α ⊕ A) A = ∅.TРешение. ∃α : (α ⊕ A) A = ∅ тогда и только тогда, когда ∃α : ∀ai , aj ∈ A : α + ai 6= aj . Всвою очередь, это возможно в том и только в том случае, если|{ai + aj |ai , aj ∈ A}| 6 |Bn r {0} | = 2n − 1.Отсюда получаем следующее условие на A:|A|(|A| − 1)6 2n − 1,24(2)откуда|A| 61+√2n+3 − 7.2(3)3. Коды ХеммингаОпределение. Линейным [n, k, d]q -кодом будем называть линейное подпространство размерности k n-мерного пространства над полем Fq , расстояние (т.

е. число различных координат)между векторами которого не меньше d. Проверочной матрицей H этого кода будем называтьтакую (n − k) × n матрицу, после умножения на которую все вектора данного подпространства(кодовые слова) обращаются в нуль. Порождающей матрицей G — такую k × n матрицу, чтолинейная оболочка ее столбцов совпадает с пространством кодовых слов.Определение. Будем говорить, что проверочная матрица приведена к систематическомувиду, если H = (EH ′ ), где E — единичная n − k × n − k матрица, а H ′ — некоторая матрицаразмера (n − k) × k.

Нетрудно заметить, что в этом случае порождающая матрица будет иметьвид ′ HTG =(1)E, где E — уже k × k единичная матрица.Определение. Пусть r — целое положительное и H — матрица размера r ×(2r −1), столбцыкоторой — все различные ненулевые векторы пространства Zr2 . Код с проверочной матрицей Hбудем называть (двоичным) кодом Хемминга.Такой код является линейным [2r − 1, 2r − r − 1, 3]2 -кодом, т.

е. он исправляет 1 ошибку.Пример 1. Пусть r = 3, тогдаили, в систематическом виде:и, соответственно0 0 0 1 1 1 1H =  0 1 1 0 0 1 1 ,1 0 1 0 1 0 1(2)(3)1 0 0 0 1 1 1H =  0 1 0 1 0 1 1 ,0 0 1 1 1 0 11 0G= 000100001000010111101111 .0 1Определение. Кодом Хемминга над Fq называют линейныйЗадача 1. Построить код Хемминга над Z3 .(4)hq r −1 q r −1,q−1 q−1i− r, 3 -код.qРешение. Любые два столбца проверочной матрицы кода с минимальным расстоянием 3должны быть линейно независимы.

В частном случае кода над полем Z2 для этого было достаточно, чтобы все они были различны. В общем случае никакие два столбца не должны бытькратны друг другу. Т. е. матрица H должна состоять из максимального числа столбцов, не5r−1кратных друг другу над Z3 — это число равно как раз qq−1− r (высоту столбцов предполагаемравной r). В частности, для r = 3 эта матрица будет выглядеть так:0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 2 2 2 .(5)1 0 1 2 0 1 2 0 1 2 0 1 2Задача 2. Доказать, что выполняется условие границы Варшамова-Гилберта: еслиC1n + . . .

+ Cd−2< 2r − 1,n(6)то существует n × r матрица H, в которой любые d − 1 столбцов линейно независимы.Решение. Докажем это утверждение по индукции. Для n = 1 оно очевидно. Пусть оновыполнено для n = i. Заметим, что сумма в левой части неравенства (6) есть число всех нетривиальных линейных комбинаций из d − 2-х столбцов.

Если неравенство выполнено, то такиелинейные комбинации не исчерпывают всех столбцов высоты r, т. е. найдется еще один, неявляющийся линейной комбинацией никаких (d − 2)-х из уже имеющихся. Значит, можно егодобавить, не испортив линейной независимости системы. Задача 3. Имеются 2000 символов русского алфавита (страница текста) и битовый канал связи с вероятностью ошибки при передаче 1го символа perr = 10−3.

Требуется закодировать текст с помощью кода Хемминга и передать, так что бы вероятность неправильногораскодирования не превышала 1) 10−2, 2) 10−3 , 3) 10−4 .Решение. Сначала поставим в соответствие каждой букве некоторую последовательностьиз 0 и 1 (это разумно делать, учитывая частоту появления различных букв — данная процедура предоставляется читателю).

В результате получим некоторую битовую последовательностьдлины N ∼ 104 . Разделим нашу последовательность на k слов длины n, каждое из которых закодируем с помощью кода Хемминга. размерность r кода подбирается так, чтобы n 6 2r − r − 1,а длина закодированных слов будет равна m = 2r − 1.

Вероятность того, что отдельное словобудет передано правильно (т. е. вероятность того, что при передаче n символов будет допущеноне более 1 ошибки) такова:p = (1 − pe )m + mpe (1 − pe )m−1 ,(7)m(m − 1) 2pe + O(m3 p3e ).2Следовательно, вероятность того, что все сообщение будет передано правильно равнаp=1−pk = 1 −km(m − 1) 2pe + O(k 2 m3 p3e ).2(8)(9)Отсюда для случая 1) получаемkm(m − 1) 2pe + O(k 2 m3 p3e ) < 10−2 .2(10)Вспоминаем, что pe = 10−3 , km ∼ N:104 ∗ (m − 1) −610 + O(10−1 m) < 10−2 ,2m−1+ O(10m) < 1.2Т.

е. такого m не существует даже для случая 1). 6(11)(12)4. Коды БЧХОпределение. Пусть α1 , . . . , α2m −1 — все элементы поляα1α2 . . . αn3 α3α. . . αn312A =  ........ ....2t−12t−12t−1α1α2. . . αnGF ∗ (2m ). Построим матрицу:.(1)Теперь заметим, что каждый элемент αi можно рассматривать как столбец γi высоты m изэлементов Z2 . Подставляя эти столбцы в A на место αi , получим n×mt матрицу H с элементамииз поля Z2 .

Код с такой проверочной матрицей будем называть кодом БЧХ.Теорема 1. Такой код является кодом, исправляющим t ошибок. Нам нужно доказать, что в построенной матрице любые t столбцов линейно независимы.Предположим обратное, т. е. что нашлось t линейно зависимых столбцов. Без ограниченияобщности можно считать, что это первые t столбцов. Тогда будет равен нулю определительтакой матрицы:α1α2 . .

. αt α3α23 . . . αt3 1(2) ....  ..... .. ..α12t−1 α22t−1 . . . αt2t−1Т. к. αi есть столбцы элементов из Z2 , квадрат их суммы будет равен сумме квадратов, а значитзамена в этой матрице строк, соответствующих степеням вида 2k − 1 на строки со степенямиk не испортит линейной зависимости. Т. о. мы получаем, что равен нулю так называемыйопределитель Вандермонда:α1 α2 . . .

αt α2 α3 . . . α2 2t  1(3)det  ....  ,.... .. ..α1t α2t . . . αttчто неверно. Следовательно, исходное предположение было ошибочным и любые t столбцовматрицы H линейно независимы. Пример 1. Построим проверочнуюGF ∗ (16). Заметим, что GF ∗ (16) = Z/[x4элементом. Т. о. получаемx x2 x3 x4 x5 x6A=x3 x6 x9 x12 x15 x3H=0100000100100011000101011100111101101000матрицу кода БЧХ, исправляющего 2 ошибки для+ x + 1], причем x в этом поле будет примитивнымx7 x8 x9 x10 x11 x12 x13 x14 x15x6 x9 x12 x15 x3 x6 x9 x12 x15001100011101001171010010101011111111010000111000111110011101101011001111110001000.,Теперь выясним, как будет выглядеть процесс декодирования для кода, задаваемого этой матS1рицей. Синдром S = Hy T =, где S1 , S3 — столбцы высоты (в данном случае) 4.

ТеперьS3рассмотрим следующие случаи:1. S1 = S3 = 0: ошибок нет.2. S1 = αi 6= 0,S3 = S13 : 1 ошибка в i-м разряде.3. S1 = αi 6= 0,S3 6= S13 : см. ниже.Разберем случай 3). Пусть ошибки произошли в разрядах i, j, тогда S1 = αi + αj , S3 = αi3 + αj3 ,откуда получаем, что αi , αj являются корнями следующего квадратного уравненияt2 + S1 t + S12 +S3= 0.S1(4)Т.

е. требуется решить это уравнение и таким образом найти разряды, в которых произошлиошибки.5. Алгоритм ПитерсонаБолее подробно теория написана в лекциях Лупанова/Угольникова (см. http://dmvn.mexmat.net).Было передано сообщение x, закодированное с помощью кода БЧХ. Получено сообщениеy = x + e, где e — вектор ошибок. Требуется восстановить исходный вектор x.1◦ Первый шаг очевиден — посчитаем синдром полученного вектора.S1 S3 TTS = Hy = He =  .. (1) .

S2t−12◦ Теперь вспомним, что означает синдром. Если ошибки произошли в разрядах i1 , . . . , it ,выполняются следующие соотношения:αi1 + . . . + αit = S1 α 3 + . . . + α 3 = S3i1it(2)... α2t−1 + . . . + α2t−1 = S.i1it2t−13◦ Отсюда хорошо бы найти αi1 , . . .