Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 31
Текст из файла (страница 31)
Кодовое расстояние d кодов Q и N удовлетворяет неравенству d2 > p. Если p = 8m − 1, то выполняетсяболее сильное неравенство d2 − d + 1 > p.Доказательство. Прежде всего убедимся, что кодовые расстояния кодов Q и N одинаковы. Пусть c(x) ∈ Q, а a — квадратичный невычет по модулю p. Тогда c̄(x) = c(xa ) будет принадлежать N .
Верно и обратное. Чтобы проверить эти утверждения, достаточно проверить, что возведение в степень a меняетместами корни уравнений f (x) = 0 и g(x) = 0. Действительно, квадратичные вычеты образуют группу по умножению.Поэтому произведение квадратичного невычета на квадратичный вычет является квадратичным невычетом, а произведениеквадратичного невычета на квадратичный невычет являетсяквадратичным вычетом.Рассмотрим произведение c(x)c̄(x).
Оно делится на взаимнопростые многочлены f (x) и g(x), а значит, и на их произведениеf (x)g(x) =xp − 1= 1 + x + x2 + · · · + xp−1 .x−1Если многочлен c(x) содержит d ненулевых коэффициентов,то столько же ненулевых коэффициентов содержит c̄(x), а ихпроизведение содержит не более d2 ненулевых коэффициентов.Значит, p 6 d2 .В случае p = 8m − 1 оценку можно усилить, если выбратьa = −1. Это действительно невычет, так как (−1)(8m−1−1)/2 == −1 (см.
задачу 3.8). При таком выборе c̄(x) = c(x−1 ). Тогда из d2 произведений, в сумме дающих c(x)c̄(x), d штукдают вклад в свободный член. Поэтому количество возможныхненулевых коэффициентов в c(x)c̄(x) не больше d2 − d + 1. 4.5.Совершенный код Голея1814.5. Совершенный код ГолеяВ этом разделе мы построим совершенный код Голея, т. е.код, содержащий 212 слов длины 23, который исправляет 3ошибки (кодовое расстояние равно 7).
Вычислением можнонайти объем 23-мерного шара радиуса 3 в E 23 : 2323231+++= 211 .123Поэтому в булев куб E 23 можно вложить не более 212 шароврадиуса 3. Так что построенный код будет разбивать булев кубE 23 на шары радиуса 3. (Поэтому он и называется совершенным.)Фактически мы уже построили такой код. Обозначим черезG23 квадратично-вычетный код при p = 23, который в обозначениях предыдущего раздела порожден многочленом f (x).Теорема 4.15. Количество кодовых слов в G23 равно 212 , акодовое расстояние равно 7.Доказательство. Квадратичных вычетов, которые образуют подгруппу индекса 2 мультипликативной группы поля вычетов GF (23) столько же, сколько и квадратичных невычетов(смежный класс по этой подгруппе), степень многочлена f (x)при p = 23 равна 11.
Значит, размерность идеала (f (x)) равна 12 и он содержит 212 элементов.Из теоремы 4.14 следует, что d > 6, так как 23 = 8 · 3 − 1.Теперь докажем, что если вес многочлена из кода Голеячетен, то он делится на 4. Это означает, в частности, что вкоде Голея нет слов веса 6. Поэтому d > 7. Но из границыХэмминга следует, что d 6 7. Таким образом d = 7.Пусть c(x) — многочлен четного веса w.
Тогда c(1) = 0, т. е.(x−1) | c(x), откуда следует, что c(x)c̄(x) = 0 в GF (2)/(x23 −1),где c̄(x) = c(x−1 ).Из равенства c(x)c̄(x) = 0 получаем равенства для коэффициентов ci многочлена c(x), рассматриваемых как целыечисла: для r = 0, . . . , 22 имеемXci cj = 2ar , ai — целые числа.i−j≡r mod 23182Глава 4.Коды, исправляющие ошибкиМеняя местами i и j, получаем равенства ar = a23−r при r 6= 0.Поэтому22 X2211XXXw(w − 1) =ci cj = 2ar = 4ar ,r=1i=0 j6=ir=1т.
е. из четности w следует, что w делится на 4.Мы доказали существование кода Голея, но не предъявилиего явно. Напомним, что конструкция квадратично-вычетногокода включает в себя произведение мономов вида x−ω i по всемквадратичным невычетам, где ω — примитивный корень степени 23.
Вычисление коэффициентов многочлена f (x) непосредственно из этого определения весьма мучительно. Но проверить полученный ответ довольно легко. Оказывается, чтонад полем GF (2)x23 − 1 = (x − 1)(x11 + x9 + x7 + x6 + x5 + x + 1)×× (x11 + x10 + x6 + x5 + x4 + x2 + 1). (4.6)Проверить это равенство можно прямым вычислением. В приводимой ниже таблице мы перемножаем два последних множителя, указывая только показатели мономов многочленов иих коэффициенты и опуская обозначение переменной2200000011210000010120000000111900000101180000001117000011111600010111150010110114000100011301101001120001101111111111111000110101911100001801000001711001001610011001510110001400100001301000001201000001110000001010000001Из равенства (4.6) и примера 3.56 следует, что множители11-й степени, которые входят в (4.6), и есть многочлены f (x)и g(x) из предыдущего раздела.
Как было показано выше втеореме 4.14, идеалы (f (x)) и (q(x)) имеют одинаковое кодовое расстояние. Поэтому любой из них можно выбрать дляпостроения совершенного кода размерности 12 длины 23, исправляющего 3 ошибки.4.6.183Коды Рида – СоломонаИтак, код Голея образуют линейные комбинации строк, которые получаются циклическими сдвигами из строки0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1.4.6. Коды Рида – СоломонаДо сих пор мы рассматривали двоичные коды: сообщениякодировались последовательностями 0 и 1. Этот случай наиболее интересен в практических приложениях, так как двоичнаясистема широко применяется в компьютерах.
Но в принципеничто не мешает рассматривать коды, которые используютдля кодирования большее количество символов. Если используется q символов, то говорят о q-ичном коде.На множестве q-ичных слов длины n можно ввести метрикуХэмминга: расстояние между двумя q-ичными словами равноколичеству позиций, в которых слова содержат разные символы. Основная задача теории кодирования переформулируетсядля q-ичных кодов дословно.Если q — степень простого числа, то понятие линейногокода и все с ним связанные определения можно переформулировать и для q-ичных кодов, если считать, что символыпринадлежат полю из q элементов. Общие результаты, которые приведены выше для двоичных кодов, сохраняются и вслучае q-ичных кодов, иногда с небольшими изменениями.Например, теорема Хэмминга имеет естественный аналогдля q-ичных кодов.
Нужно только правильно сосчитать объемn-мерного шара радиуса r.Теорема 4.16 (q-ичная теорема Хэмминга). При 2r < nмаксимальное число сообщений k для q-ичных кодов длины nнаходится в следующих пределахqnP2ri=0 (q− 1)iqn.i ni=0 (q − 1) i 6 k 6 PrniДоказательство аналогично доказательству теоремы 4.6.Нужно только заметить, что количество точек на расстоянии iот данной равно (q−1)i ni (выбираем i позиций из n, в которых184Глава 4.Коды, исправляющие ошибкисимволы различаются, для каждой такой позиции есть q − 1вариант выбора символа).Мы уже упоминали, что значения несовпадающих многочленов небольшой степени должны различаться во многихточках. Но это и есть условие исправления ошибок! Коды Рида – Соломона строятся следующим образом.
Пусть q — степень простого числа, F = GF (q) — поле из q элементов. неотрицательное число. Кодом Рида – Соломона Rq (X, r) назовемq-ичный код длины n, который состоит из наборов значениймногочленов степени не выше g в точках множестваX = {x1 , . . . , xn } ⊆ F.Другими словами, каждому многочлену f ∈ F [x], deg f 6 g,сопоставлено кодовое слово(f (x1 ), . . . , f (xn )).Во всех дальнейших рассмотрениях мы предполагаем, чтоn > g.Многочлены степени не выше g образуют векторное пространство над полем F размерности g + 1.
Поэтому в кодеРида – Соломона q g+1 точек.Теорема 4.17. Кодовое расстояние для кода Рида – Соломонаравноd = n − g.(4.7)Доказательство. Поскольку многочлены степени не выше g,совпадающие в g + 1 точке, задают одну и ту же функцию,получаем оценку d > n − g. Построим многочлен степени g,имеющий g корней:(x − x1 ) · . . . · (x − x2 ) · . . . · (x − xg ).Значит, кодовое расстояние не превосходит n − g.Для линейных кодов справедлива следующая простая оценка кодового расстояния.Теорема 4.18 (граница Синглтона). Пусть q — степеньпростого числа, а C — линейный q-ичный код длины n с кодовым расстоянием d, содержащий q k слов. Тогдаn − k > d − 1.4.6.Коды Рида – Соломона185Доказательство. C является векторным пространством размерности k над полем F из q элементов.
Пространство размерности k имеет базис (b1 , . . . , bk ) из k элементов, поэтому можнозадать F -линейное отображение пространства ϕ : F k → F n ,образом которого будет C:ϕ : (0, . . . , 0, 1, 0 . . . , 0) 7→ bi .|{z}i − 1 нулей слева от 1Матрица отображения ϕ имеет размер n × k и полный ранг.Покажем, что можно найти такое ненулевое кодовое слово,у которого k − 1 нулей. Выберем для этого невырожденнуюподматрицу размера k × k, пусть ее строки соответствуют позициям в слове с номерами i1 , i2 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
