О.Б. Лупанов - Курс лекций по дискретной математике, страница 7

Коды ХеммингаОпределим схему кодирования для (двоичного) кода Хемминга, исправляющего одну ошибку. Поскольку мыоперируем с двоичными разрядами, суммирование везде будет предполагаться по модулю два.Пусть требуется закодировать некоторое сообщение a1 a2 . . . al , где ai ∈ B.Через Vk обозначим набор индексов, имеющих в двоичной записи единицу в k-м разряде.Теперь будем строить кодовое слово b1 b2 . .

. bn по следующему правилу. Вначале все разряды с номерами,не являющимися степенями двойки, заполним символам кодируемого сообщения и назовём информационными.Разряды с номерами, являющимися степенью двойки, заполним так:Xbm .(19)b2k :=m6=2k ,m∈VkТакие разряды называют контрольными. Таким образом, мы выбираем их так, чтобы сумма всех разрядов синдексами из каждой последовательности Vi была равна нулю, потому что в каждом множестве Vk находитсяровно один контрольный разряд. Несложно заметить, что число контрольных разрядов в кодовом слове длины nбудет равно m, где 2m−1 6 n < 2m .

Следовательно, число информационных разрядов равно n−m, а общее числонаборов длины n в коде Хемминга равно 2n−m , потому что мы имеем право заполнять только информационныеразряды, а контрольные уже однозначно определяются.Пусть произошла ошибка в разряде bi . Посколькукод двоичный, то, чтобы исправить эту ошибку, достаточноPзнать только номер i. Найдём числа εk =bm .

Заметим, что εk = 0 тогда и только тогда, когда i ∈ Vk . Инымиm∈Vkсловами, это означает, что последовательность εt . . . ε0 есть не что иное, как двоичная запись числа i. Если мыполучили нулевое число, то ошибок нет.2.2.3. Свойства кодов, исправляющих ошибкиОпределение. Расстоянием Хемминга между двумя кодовыми словами будем называть число различныхразрядов в них. Минимальным расстоянием кода C будем называть, соответственно, минимум таких расстоянийпо всем парам слов из C.Определение. Весом Хемминга кодового слова будем называть число ненулевых символов в нём.Замечание. Это определение работает не только для двоичных кодов, но и для кодов над Zq .Сейчас мы выясним, что такое вообще двоичный код C, который исправляет одну ошибку.

Пусть α, β ∈ C.Введём на булевом кубе, в который вложен наш код C, метрику, задаваемую расстоянием Хемминга. Шарырадиуса 1 с центрами в точках α и β не должны пересекаться, иначе возможна ситуация, когда искажённоеслово попадёт в «сферу влияния» двух кодовых слов, и будет неясно, к какому из двух слов его относить.22Пусть кодовые слова имеют длину n. Тогда шар радиуса 1 содержит n + 1 точку.

Пусть M = |C|. Тогда2n.получаем оценку M (n + 1) 6 2n , откуда M 6 n+1nПусть 2m−1 6 n < 2m . Тогда 2m 6 2n, и, как мы знаем, код Хемминга имеет мощность M = 2n−m = 22m .n2Отсюда M > 2n.Рассмотрим случай, когда 2m −1 = n, то есть 2m = n+1. Тогда верхняя и нижняя оценки для числа M простосовпадают, то есть код является плотным. Это означает, что имеется плотная упаковка M шаров радиуса 1 вбулев куб Bn .2.2.4. Коды с исправлением нескольких ошибокТеперь представим себе, что может происходить не одна, а r ошибок, то есть какие-то r разрядов портятся.Тогда нужно рассматривать шары радиуса r с центрами в кодовых словах, и они тоже не должны пересекаться.Пусть Sr — объём шара радиуса r.

Ясно, чтоSr = C0n + C1n + C2n + . . . + Crn .(20)nСледствие 2.2. Мощность кода, исправляющего r ошибок, не превосходит величины S2 r .Оценим снизу мощность кода Cr , исправляющего r ошибок. Ясно, что если α, β ∈ Bn , и ρ(α, β) > 2r + 1, тошары с центрами в точках α и β не пересекаются.

Поэтому эти слова можно взять в качестве кодовых. Тогдарассмотрим (тупой) алгоритм построения кода: берём произвольную точку в Bn , объявляем её кодовым словоми описываем вокруг неё шар радиуса 2r. Точки этого шара уже брать нельзя, а все остальные — можно.

Находимnточку в кубе, которая не попала в этот шар и повторяем процедуру. Ясно, что так заведомо можно сделать S22rраз, поэтому нам гарантирована мощность кодаM>2n.S2r(21)Имеется очевидная асимптотика Sr ∼ nr при n → ∞, поэтому получаем оценки, верные для всех достаточнобольших n при фиксированном r:2n2nС1 · 2r 6 Mr (n) 6 C2 · r .(22)nnПусть мы хотим передавать сообщения из t-битных слов.

Тогда нам нужен код мощности Mr > 2t . Отсюда(и из оценки выше) получаем асимптотическое неравенство2t 6 C1 ·2n.n2r(23)Положим n := t + 2r log2 t + C, где C = const. Тогда неравенство перепишется в виде:1 6 C1 ·2t+2r log2 t+Ct2r · 2C=C·∼ C1 · 2C .1n2r · 2tn2r(24)Отсюда ясно, как подбирать константу C. Это нужно делать так, чтобы асимптотически неравенство быловыполнено.Таким образом, мы видим, что «прирост» количества контрольных разрядов сравнительно мал, а именно,линейно растёт по r и логарифмически — по t.2.2.5.

Линейные кодыПри рассмотрении линейных кодов мы будем рассматривать в качестве выходного и выходного алфавитовполе Fq , где q — простое число. Это поле обозначим для краткости буквой K.Зафиксируем натуральные числа n и k < n. Рассмотрим линейный оператор H : K n → K n−k . Матрицу этогооператора будем называть проверочной.Определение. Линейным кодом V с проверочной матрицей H называется ядро оператора H, то естьV := {x ∈ K n : Hx = 0} .(25)Как мы знаем, ядро линейного оператора является линейным подпространством.

Поскольку dim Ker H ++ dim Im H = dim K n = n, получаем, что dim V > k.Мы будем использовать расстояние Хемминга, а под нормой вектора, соответственно, понимать количествоненулевых координат в нём.23Число n называется длиной кода V , число k(V ) := dim V — размерностью кода, а через d(V ) будем обозначатьминимальное расстояние между элементами кода, то есть(26)d(V ) := min ρ(x, y) = min kxk .x,y∈Vx6=0x∈Vx6=0Такой код мы будем называть [n, k, d]-кодом.Замечание. Вообще говоря, не следует путать числа k и k(V ). Однако, если нам повезло, и оператор Hимеет полный ранг (то есть n − k), то k = k(V ), и его матрицу можно привести к виду H = (A|In−k ), где In−k —единичная матрица.ошибок, потомуЗаметим, что если минимальное расстояние кода равно d, то он умеет исправлять t := d−12что шары радиуса t с центрами в кодовых словах не пересекаются.ttРассмотрим матрицу G = (Ik |−A ), тогда простая проверка показывает, что HG = 0.

Это тем более видноIkиз того, что Gt = −A.Определение. Матрица G называется порождающей матрицей кода V .Суть порождающей матрицы проста: Im G = Ker H = V .Схема кодирования устроена следующим образом:кодпомехидекодu = (u1 , . . . , uk ) −−→ x = (x1 , . . . , xn ) −−−−→ y = (y1 , . . .

, yn ) −−−−→ue = (eu1 , . . . , uek ).(27)xi1 hi1 + . . . + xid hid = 0.(28)Из-за возможных помех в канале связи, вообще говоря, x 6= y. Кодирование происходит по схеме x = Gt u.Проверка того, произошли ли ошибки, проводится с помощью матрицы H, применяемой к полученному изканала связи вектору y.Теорема 2.10. Пусть H — проверочная матрица кода V . Минимальное расстояние d(V ) кода V равно dтогда и только тогда, когда любые d − 1 столбцов матрицы H линейно независимы, и существует d линейнозависимых столбцов. Пусть d(V ) = d. Тогда существует x ∈ V , такой что kxk = d.

Пусть в векторе x ненулевые числа стоятна местах i1 , . . . , id . Пусть матрица H состоит из столбцов h1 , . . . , hn . Поскольку Hx = 0, получаем, чтоЭто есть искомая нулевая линейная комбинация для столбцов hi1 , . . . , hid , значит, они линейно зависимы. Теперь,если бы нашлись d − 1 линейно зависимых столбцов, то коэффициенты линейно зависимости образовали бывектор веса d − 1, зануляющийся матрицей H, что невозможно.

Все наши рассуждения обратимы, поэтомуобратное тоже верно. Следствие 2.3. Если в проверочной матрице любые d − 1 столбцов линейно независимы, то d(V ) > d.Следствие 2.4 (Граница Синглтона). Имеет место неравенство d(V ) 6 n − k + 1. Так как максимальное число линейно независимых столбцов равно рангу матрицы H, а ранг матрицы Hникак не больше n − k, поэтому d(V ) − 1 6 rk H 6 n − k. Отсюда сразу получаем доказываемое неравенство.

Определение. Синдром — это вектор S := Hy.Если представить y в виде y = x + e, где e — вектор ошибок, то получаем Hy = Hx + He = He, поскольку x ∈∈ V = Ker H. Таким образом, ненулевые элементы синдрома — это в точности те разряды, в которых произошлиошибки.2.2.6. Код Хемминга как пример линейного кодаТеперь, наконец, можно дать определение кода Хемминга в терминах линейных кодов.Определение.

Пусть H есть матрица над полем F2 , в которой r строк и 2r −1 столбцов, причём её столбцы —все различные ненулевые вектора из Fr2 . Линейный код, для которого эта матрица является проверочной, и естьдвоичный код Хемминга.Стоит объяснить, почему та схема кодирования, которую мы описали вначале, задаёт именно этот код. Этостановится ясно, если заметить, что столбцы в матрице H можно расставить таким образом, чтобы номерастолбцов, в которых стоят единицы на i-й строке, были элементами последовательности Vi−1 . Это означает, чтовектор Hx состоит из всех сумм видаXxk(29)k∈Vi−1и равен нулю тогда и только тогда, когда все эти суммы равны нулю.Утверждение 2.11. Код Хемминга есть двоичный [n, k, d]-код, где n = 2r − 1, k = 2r − 1 − r, d = 3.24 В доказательстве нуждается лишь тот факт, что этот код имеет минимальное расстояние 3.

Покажем,что он не содержит векторов, вес которых меньше 3. Предположим противное. Пусть, например, в нём нашелсявектор x, содержащий только одну единицу в разряде с номером i. Тогда из равенства Hx = 0 следует, что i-йстолбец матрицы H должен быть нулевым, а это противоречит определению.