А.Е. Ромащенко, А.Ю. Румянцев , А. Шень - Заметки по теории кодирования (1127104), страница 3
Текст из файла (страница 3)
Эта матрица называется проверочной, поскольку умножением на неё проверяется принадлежность множеству кодовыхслов. Код с проверочной матрицей имеет расстояние тогда и толькотогда, когда любые − 1 столбцов матрицы линейно независимы. Всамом деле, кодовое слово, в котором лишь − 1 позиций отличны отнуля, как раз и выражает линейную зависимость между − 1 столбцамипроверочной матрицы.5. Код ХэммингаСейчас мы рассмотрим случай, когда удаётся указать простой код снаилучшими возможными параметрами (шары плотно заполняют всё пространство, достигая границы Хэмминга).
Этот код называется кодом Хэмминга и позволяет исправлять одну ошибку, то есть имеет минимальноерасстояние 3.Рассмотрим алфавит из двух букв B = {0, 1}. Мы будем рассматривать его как поле из двух элементов со сложением (⊕) и умножением помодулю 2.В пространстве B шар радиуса 1 состоит из +1 элементов (центр иещё слов, отличающихся от центрального в одной из позиций). Всегослов 2 , поэтому шансы на укладку шаров без пробелов и перекрытийесть, лишь если 2 кратно + 1, то есть если + 1 есть степень двойки: = 2 − 1 для некоторого целого (при = 3, 7, 15, 31, . . .; случай = 1 тривиален).При = 3 есть 8 вершин куба, которые разбиваются на два шара сцентрами в противоположных вершинах.
Каждый из шаров содержит 4элемента, так что плотная упаковка действительно возможна.Оказывается, что она возможна и при остальных значениях из указанной серии. Чтобы убедиться в этом, рассмотрим произвольное =2 − 1 и запишем все числа от 1 до в двоичной системе по столбцам матрицы (от 1 в первом столбце до в последнем; каждое числозаписывается сверху вниз, так что младший разряд оказывается внизу).135. ëÏÄ èÜÍÍÉÎÇÁНапример, при = 7 получится матрица0 0 0 1 1 1 10 1 1 0 0 1 11 0 1 0 1 0 1Строки этой матрицы будем рассматривать как способы вычисления контрольных сумм. (Другими словами, мы используем эту матрицу как проверочную). А именно, пусть дано произвольное слово1234567из B . Для него мы вычислим три контрольных суммы, складывая помодулю 2 те биты, против которых в матрице стоит единица: ⊕ ⊕ ⊕ (для первой строки), ⊕ ⊕ ⊕ (для второй строки) и ⊕ ⊕ ⊕ (для третьей строки).Можно сказать, что мы умножаем матрицу на столбец с элементами( , .
. . , ), получая столбец из трёх контрольных сумм.Кодовые слова (центры шаров) | это те слова длины 7, для которыхвсе три контрольные суммы равны нулю. Линейная алгебра говорит, чтоони образуют подпространство размерности 4 (три уравнения на семьпеременных; легко проверить, что уравнения независимы, посмотрев напервый, второй и четвёртый столбцы), состоящее из 2 = 16 кодовыхслов.Что случится с контрольными суммами, если мы отойдём от центрашара на единицу, то есть изменим какой-либо из битов ? Это изменениесоответствует прибавлению столбца с одной единицей в -ой строке, изначения контрольных сумм (из нулевых) станут равными -му столбцупроверочной матрицы, то есть образуют двоичную запись числа .
Таким образом, по этим контрольным суммам мы восстановим, какой битизменился, и сможем изменить его обратно.Мы описали алгоритм декодирования, исправляющий ошибку в любом (но только одном) бите. Отсюда автоматически следует, что шарыне пересекаются. Тем самым у нас есть 16 шаров, каждый из которыхсостоит из 8 элементов, и вместе они покрывают все 128 элементов семимерного булева куба B .Точно так же для произвольных и = 2 − 1 строится проверочнаяматрица из столбцов высоты (двоичные записи чисел 1, . . . , ). Еёстроки указывают контрольных сумм для векторов из B . Кодовых слов2 − , в каждом шаре +1 = 2 элементов и они покрывают B полностью.74671231536777475145. ëÏÄ èÜÍÍÉÎÇÁЗаметим, что этот код не только совершенный (всё пространство занято шарами без пробелов), но и имеет простые алгоритмы кодирования идекодирования. (Про декодирование мы уже говорили; при кодированииможно считать биты , , контрольными, а остальные значащими, ивыбирать контрольные биты так, чтобы получить кодовое слово.) Единственный недостаток кода Хэмминга | что он исправляет только однуошибку..1.
Можно вычеркнуть из матрицы часть столбцов. При этом мы получим код с тем же числом контрольных сумм, но с меньшим числом битов. Он уже не будет совершенным, но будет достаточно эффективным.(Больше половины столбцов выкидывать нет смысла, поскольку тогдауж лучше уменьшить высоту матрицы. А если мы выбрасываем меньшеполовины столбцов, то теряем не больше половины места.)2. Аналогичное построение возможно и при > 2, если существуетполе F из элементов (это бывает, напомним, когда есть степень простого числа).
Для этого напишем в столбцах матрицы ненулевые векторыиз F , причём из каждого класса пропорциональных друг другу векторовоставим только один. Всего ненулевых векторов − 1, в каждом классе − 1 пропорциональных друг другу векторов, так что классов (и столбцов матрицы) будет = ( − 1)/( − 1).
Ясно, что ранг полученнойматрицы равен .Изменение одной позиции в кодовом слове изменит контрольные суммы на вектор, пропорциональный одному из столбцов матрицы, и по построению этот столбец (и тем самым номер изменённого символа) определится однозначно.Кодовых слов будет − , размер шара 1 + ( − 1) (в каждой из позиций можно заменить букву на ( − 1) других, да ещё центр шара),что равно1 + −−11 ( − 1) = .124ЗамечанияТаким образом, шары заполняют всё пространство.3. Для доказательства того, что код Хэмминга имеет расстояние неменьше 3, достаточно было бы сослаться на то, что любые две строки внашей матрице (=любые два столбца в проверочной матрице из предыдущего раздела) линейно независимы.
Но нам важен и простой алгоритмдекодирования.156. îÅÒÁ×ÅÎÓÔ×Ï óÉÎÇÌÔÏÎÁ1 /1/2кода нет?кодесть1 /1/2Рис. 2. Для двухбуквенного алфавита оценка Синглтона слабее оценкиХэмминга.6. Неравенство СинглтонаДля любого кода : ˚венство Синглтона→˚ с расстоянием выполняется нера6 −+1(называемое также оценкой или границей Синглтона ).В самом деле, пусть имеется кодовых слов в ˚ . Выделим в этихсловах первые − 1 позиций. Для некоторой пары кодовых слов эти − 1позиций совпадают по принципу Дирихле (число слов больше числавариантов − ).
Расстояние между такими словами не больше − ( −1) = − + 1, что и требовалось доказать.Для кодов в двухбуквенном алфавите эта оценка уступает оценке Хэмминга. А именно, для кода с расстоянием она оценивает сверху коэффициент полезного действия (скорость) кода величиной 1 − / , чтосоответствует прямой, соединяющей точки (0, 1) и (1, 0) (рис. 2). Видно,что эта прямая соединяет концы кривой Хэмминга и лежит выше неё.Для большего размера алфавита это уже не так. Дело в том, что оценка Хэмминга не даёт ничего хорошего при ≈ . Рассмотрим, например,случай = 3 и шар радиуса /2 или чуть меньше.
Сколько элементовв этом шаре? Позиций несовпадения примерно /2 среди ; вариантоввыбора не более 2 . После такого выбора останется выбрать в каждойпозиции несовпадения один из двух несовпадающих символов, получится1168. äÅËÏÄÉÒÏ×ÁÎÉÅ ËÏÄÏ× òÉÄÁ { óÏÌÏÍÏÎÁне более 2/ . √Таким образом, шар радиуса не более /2 содержит не более 2 / = (2 2) элементов. А всего в пространстве√ 3 точек, поэтомуоценка на число шаров будет всего лишь (3/2 2) и кривая Хэмминга не стремится к нулю при приближении к (в отличие от прямойСинглтона).2327. Код Рида { СоломонаРассмотрим конечное поле F из элементов (как мы говорили, этовозможно, когда есть степень простого числа; для начала можно ограничиться случаем, когда само простое, и рассматривать поле вычетовпо модулю ).Кодируемое слово . . .
− (где ∈ ˚ = F ) будем рассматривать как последовательность коэффициентов многочлена ( ) = + + . . . + − −степени меньше . Ему соответствует кодовое слово, состоящее из значений многочлена в заранее выбранных точках поля F (естественно, что для этого надо, чтобы 6 ). Из курса алгебры известно, чтодва различных многочлена степени меньше могут совпадать максимумв −1 точках. Поэтому для различных многочленов имеется как минимум − +1 точек (среди выбранных нами ) несовпадения, то есть кодовоерасстояние построенного кода Рида { Соломона не меньше − +1. Темсамым для этих кодов неравенство Синглтона обращается в равенство.Кодирование выполняется просто. Некоторая проблема тут с декодированием: как восстановить многочлен по таблице значений, где некоторые значения испорчены? Оказывается, что это можно сделать заполиномиальное время (чего с первого взгляда не скажешь).01110118.
Декодирование кодов Рида { СоломонаИтак, пусть имеется таблица значений многочлена степени меньше в некоторых точках, причём = ⌊( − )/2⌋ значений в неймогут быть неверными. (Такое значение соответствует числу исправляемых ошибок при кодовом расстоянии = − + 1.) Другими словами,нам дана искажённая функция ~, определённая в точках и отличающаяся от неизвестного нам многочлена не более чем в точках. Какнайти ?8. äÅËÏÄÉÒÏ×ÁÎÉÅ ËÏÄÏ× òÉÄÁ { óÏÌÏÍÏÎÁ17Поскольку число ошибок не больше , существует (пока что неизвестный нам) многочлен ( ) степени , который обращается в нуль вместах ошибок. (Достаточно перемножить одночлены ( − ) для всех, где есть ошибки; если таких мест меньше , домножим результат ещёна что-нибудь, чтобы поднять степень до .)Тогда ( ) ( ) равно ~( ) ( ) во всех точках, поскольку разницамежду ( ) и ~( ) приходится на те , где ( ) = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
