Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
M{n,2t + \)^~. (2)
Оценки, аналогичные (1) и (2), справедливы и для недвоичных кодов. В случае произвольного основания q они имеют вид:
vH V1
при этом число слов в шаре радиуса г вычисляется по формуле:
Vr= 1 +Oniq- 1) + C2n (q-I)2+.. . +CJ1 (?-1)'.
На примерах можно убедиться, что указанные границы далеко отстоят одна от другой, т. е. являются весьма грубыми. Имеется много их уточнений, а также оценок другого рода, но это вопросы более специальные.
Скажем теперь несколько слов о совершенных кодах, с которыми связана целая эпоха в теории кодирования. Мы отмечали уже, что число кодовых слов M совершенного кода, исправляющего t ошибок, достигает наибольшей возможной величины (верхней границы Хемминга). В случае двоичного кода имеем, следовательно,
t
M =2»/ 2 Cin. (3)
I= о
Тривиальным примером совершенного кода является код с повторением нечетной длины и=2t+\. В этом случае верхняя граница (1) равна
221 + 1/ 2 C^+i = 22t+1/22i = 2, i=0
что совпадает с числом кодовых слов кода с повторением.
Более интересный класс совершенных кодов являют собой хорошо известные нам коды Хемминга длины 2т—1 с исправлением одиночных ошибок. Граница сферической упаковки для этих параметров (п=2т—1, i=l) равна
2"/(1 +п) = 2п/2т S= 2п~т.
,79 Столько же кодовых слов имеет двоичный код Хемминга.
Из равенства (3) вытекает, что совершенные двоичные коды могут существовать лишь для таких параметров п и t
t, для которых 2 C1n является степенью двойки (так
- I = о
именно и было в рассмотренных выше примерах).
Понятие плотно упакованного кода появилось уже в первых работах по теории кодирования, тогда же возникла проблема описания всех совершенных кодов. Поиск плотно упакованных кодов казался весьма заманчивой задачей, но лишь однажды он увенчался успехом. Новый совершенный двоичный код был открыт в 1949 г. американским ученым Голеем. Этим кодом (его так и называют — код Голея) оказался (23, 12)-код, исправляющий три ошибки. Как впоследствии выяснилось, этот код является циклическим с порождающим многочленом g(X) = Xn+X9+X7+X5+X+! (мы уже знаем, что этот многочлен служит делителем многочлена X23-I).
Дальнейшие поиски совершенных кодов к удаче не привели. Это не значит, однако, что не появлялось интересных работ о совершенных кодах. Самой значительной и глубокой из них была опубликованная в 1957 г. статья Ллойда, в которой на изучение проблемы были брошены мощные средства теории функций комплексного переменного и дифференциальных уравнений. В результате вопрос существования совершенного кода с теми или иными параметрами был сведен к чисто алгебраической задаче, связанной со свойствами корней некоторого многочлена.
Под влиянием этой и ряда других работ стало складываться впечатление, что иных двоичных линейных совершенных кодов, кроме перечисленных, и не существует. Это предположение оказалось справедливым, но доказано оно было лишь в начале семидесятых годов финскими учеными А. Тиетявяйненом и А. Перко и независимо от них советскими учеными В. А. Зиновьевым и В. К. Леонтьевым. Решению проблемы предшествовала многотрудная подготовка, в которую внесли вклад многие специалисты, и немалую роль здесь сыграли результаты и методы упоминавшейся выше работы Ллойда.
Что касается кода Голея, то он является во многих отношениях важным и замечательным кодом и остается источником многих идей и исследований в теории кодиоования (см. [12J).
,80 Задачи и дополнения
1. Убедиться, что не существует кода длины 20, содержащего 1000 кодовых слов и исправляющего любые комбинации из трех и менее ошибок.
2. Использовать верхнюю оценку Хемминга для доказательства следующего утверждения:
Для всякого q-ичного линейного (п, к)-кода с кодовым расстоянием d =2І+1 величина Iogl7Vf служит нижней границей для числа т проверочных символов:
т log, Vt.
3. Для оценки «качества» линейного кода можно пользоваться так называемой границей Варшамова — Гильберта. Применительно к двоичным кодам указанная оценка основывается на следующем утверждении:
Если выполняется неравенство
1 +"С,U + С2п-г +...+ СІ2\ < 2» (4)
то существует линейный (п, k)-Kod с кодовым расстоянием, не меньшим d, имеющий не более т проверочных символов.
Для доказательства достаточно построить матрицу H порядка тХп, в которой любые d—1 столбцов линейно независимы; она и будет служить проверочной матрицей искомого кода (см. § 11, дополнение 4). В качестве первого столбца H можно взять любой ненулевой вектор длины т. Пусть уже выбрано i<n столбцов, любые d—1 из которых линейно независимы. Всевозможных линейных комбинаций этих і столбцов, содержащих ровно / слагаемых, имеется не более С\, и, следовательно, число всех линейных комбинаций, содержащих d—2 или меньше столбцов, не превосходит числа
С] +Cf+... +Cf-2.
Но в силу (4) это число меньше величины 2т—1, т. е. общего количества ненулевых столбцов. Поэтому мы можем добавить по крайней мере еще один столбец, не равный ни одной из указанных линейных комбинаций. В получившейся при этом системе из i+1 векторов любые d—1 векторов по-прежнему будут линейно независимы. Продолжая эту процедуру присоединения столбцов, мы и построим искомую матрицу Н.
