Часть III. ПРИЛОЖЕНИЯ И СОВРЕМЕННЫЕ МЕТОДЫ

Эта часть книги посвящена приложениям материала, изложенного в ч. I и II, и современным методам. В ней рассматриваются следующие темы:

Глава 4. Коды, исправляющие ошибки, и криптография.

Глава 5. Наибольшие общие делители полиномов над целыми числами и последовательности полиномиальных остатков.

Глава 6. Разложение на множители полиномов над целыми числами.

Глава 7. Отделение и аппроксимация вещественных корней полиномиальных уравнений.

Читателю следует помнить, что разд. 7.2 зависит от разд. 5.2.

Глава 4. Коды, исправляющие ошибки, и криптография

Кодирование и декодирование информации для поддержания секретности называется криптологией. Однако имеется много других типов кодов, где секретность не представляет интереса. Примерами могут служить zip-коды, используемые почтовыми учреждениями, коды ASCII или EBCDIC, используемые для преобразования символов алфавита в двоичную форму для представления в ЭВМ, и Универсальный промышленный код, ряд черных вертикальных линий, содержащих информацию об изделии, который можно обнаружить на многих товарах.

В этой главе мы будем рассматривать коды, предназначенные защищать передаваемую информацию как от искажения этой информации, так и от несанкционированных получателей.

4.1. Коды, исправляющие ошибки, — основные понятия

Ошибки при передаче данных по каналу могут возникать по самым разным причинам, например из-за отказа аппаратуры, «шумов», или «сбоев», которым подвержено чувствительное и сложное электронное оборудование. Для защиты от ошибок мы можем кодировать посылаемую информацию и декодировать ее на другом конце таким образом, чтобы максимизировать вероятность исправления или по крайней мере обнаружения таких ошибок. Удачные схемы кодирования часто опираются на абстрактную алгебру.

Алгебраическая теория кодирования насчитывает к настоящему времени более 30 лет. Изначально она возникла в ответ на знаменитую теорему Шеннона о кодировании (Shannon, 1948, 1949), которая ограничивала эффективность ошибки, которая мажет получиться на дискретном канале, но почти не давала указаний, как эта эффективность может получиться. То есть теорема Шеннона гарантирует существование кодон, которые могут передавать

информацию со скоростью, близкой к пропускной способности, с произвольно малой вероятностью ошибки.

В этом разделе мы описываем два семейства кодов: первый — способный обнаруживать и исправлять одну ошибку, был разработан в 1950 г. Хэммингом, в то время как второй, который может обнаруживать и исправлять две ошибки, был разработан на 10 лет позже Боузом, Чоудхури и Хоквингемом (БЧХ для краткости) (Bose, Chaudhuri, I960; Hocquenghem,1959). Главным инструментом в коде Хэмминга служат линейная алгебра (читатель мажет просмотреть приложение в конце книги) и язык смежных классов, в то время как в БЧХ-кодах важную роль играют конечные поля. (В изложении мы следуем работе (Afrati, 1985); см. также (Berlekamp, 1968; Blake, 1979; Levinston, 1970; MacWilliams, 1977; Peterson и др., 1972 и Wakery, 1978).)

На рис. 4.1.1 мы описываем нашу модель системы связи. Сообщения проходят по системе от отправителя (называемого также источником, или передатчиком). Каналом могут служить воздух или провода.

Рис. 4.1.1. Модель системы связи.

В противоположность непрерывным источникам, таким, как радио, мы рассматриваем только источники с конечным числом дискретных сигналов. Более точно, мы имеем дело с двоичными кодами, предполагая, что любая передаваемая нами информация мажет быть представлена в виде последовательности двоичных цифр; это — сообщение. Более того, мы предполагаем, что наш канал — это двоичный симметричный канал приведенного на рис. 4.1.2 вида.

Это значит, что если — вероятность правильного получения двоичного сигнала, то вероятность приема с ошибкой. Мы

Рис. 4.1.2. Два вида двоичных симметричных каналов.

предполагаем, что возникающие при передаче ошибки независимы и что изменилась только одна двоичная цифра, в то время как соседние цифры остались нетронутыми. (В действительности это не так, и внимание уделяется кодам, имеющим дело с каналами, в которых ошибки встречаются пакетами, или кластерами.) Наконец, мы предполагаем, что вероятность того, что преобразуется в «1», равна вероятности того, что «1» преобразуется в и что вероятность любого такого события относительно мала, скажем 0.01. (В действительности единицы преобразуются чаще, чем нули.)

Хотя мы не в состоянии помешать каналу допускать такие ошибки, мы можем принять некоторые меры, чтобы защититься от них. Идея состоит в том, чтобы к к информационным цифрам, которые мы хотим передать, добавить проверочных цифр, а затем передавать весь блок из цифр. Предполагается, естественно, что канал изменит относительно немного из этих передаваемых цифр, так что пользователь на основе проверочных цифр будет иметь достаточно информации, чтобы обнаружить и исправить ошибки канала. (Это — пример избыточности, т.е. передачи более чем к информационных цифр, чтобы улучшить надежность процесса передачи.) Конечно, должно существовать правило выбора проверочных цифр, и этот процесс носит название кодирования. Мы назовем скоростью передачи информации кода.

Определение 4.1.1. -мерное подпространство С векторного пространства всех двоичных -кортежей над GF(2) называется -кодом.

Любая последовательность из цифр, которая может быть передана, называется кодовым словом. Очевидно, имеется последовательностей, или векторов, длины , но только 2 из них являются кодовыми словами, потому что проверочных цифр

в каждом кодовом слове полностью определяются к информационными цифрами; мы будем называть кодом множество этих 2 векторов длины п. Для любого передаваемого кодового слова, учитывая тот факт, что мы имеем дело с зашумленным каналом, может быть получен любой из векторов длины ; тогда пользователь должен решить, какое из 2 возможных кодовых слов передавалось.

Определение 4.1.2. Если и — переданное кодовое слово, полученный вектор, то называется вектором ошибок.

Получив v, пользователь должен решить, какое кодовое слово было передано, определив наиболее вероятную ошибку. Если все кодовые слова длины равновероятны, то эта процедура минимизирует вероятность некорректного декодирования. Декодирование по максимуму правдоподобия просто предполагает наиболее вероятную ситуацию, а именно что встречается наименьшее число ошибок.

Определение 4.1.3. Расстояние Хэмминга между двумя векторами длины — это число координат, в которых и и v различаются. Вес Хэмминга вектора длины п — это число отличных от нуля координат и очевидно, что

Например, если то Можно показать, что расстояние Хэмминга — это метрика на векторном пространстве над GF(2) (см. упр. 1 к этому разделу), т.е. для любых из выполнены следующие условия:

Аналогично можно показать, что вес Хэмминга — это норма на векторном пространстве над GF(2), т.е. для любых u, v из и А из в R имеют место следующие утверждения:

Для понимания следующей теоремы требуется некоторое знакомство с теорией вероятностей.

Теорема 4.1.4. Пусть С — код для двоичного симметричного канала, и предположим, что С содержит s равновероятных кодовых слов длины п. Тогда декодирование в ближайшее кодовое слово является декодированием по максимуму правдоподобия, если вероятность правильной передачи

Локазательство. Пусть — расстояние между кодовым словом и и полученным вектором v. Для того чтобы пользователь мог получить вектор v, если передавался и, должны встретиться ошибок. Вероятность этого события равна

где — вероятность правильной передачи. Положим и сравним вероятности для двух кодовых слов Очевидно, что

а поскольку мы всегда предполагаем, что , то

Поэтому вероятность максимальна, когда и — ближайшее к v кодовое слово. Если имеется несколько кодовых слов с таким свойством, то мы мажем выбирать одно из них произвольным образом.

Пример. Предположим, что код состоит из четырех следующих кодовых слов:

Если получен вектор , то он будет декодирован как потому что для . Аналогично принятый вектор может быть декодирован как или потому что

Поскольку любой вектор v, поступивший к получателю, декодируется в ближайшее кодовое слово (ближайшее относительно расстояния Хэмминга), то естественно предположить, что хороший код — это код, в котором кодовые слова находятся «далеко» друг от друга. Это действительно так, потому что если расстояние между кодовыми словами велико, то чтобы кодовое и преобразовалось в (полученный) вектор v, который ближе к другому кодовому слову и, чем к и, должно встретиться много ошибок. Имеет место следующая

Лемма 4.1.5. Пусть С — двоичный код с s кодовыми словами и, длины . Этот код может исправлять все комбинации не более чем t ошибок тогда и только тогда, когда

Локазательство. Мы докажем лемму только в одном направлении, оставив остальное читателю. Предположим, что расстояние между любыми двумя кодовыми словами не меньше, чем . Если и — переданное кодовое слово, полученный вектор с ошибками, т.е. то по неравенству треугольника расстояние от v до любого другого кодового слова и удовлетворяет соотношению

т.е. всегда больше, чем если t, то вектор v будет декодирован в правильное кодовое слово .

Определение 4.1.6. Кодовое расстояние двоичного кода С дается формулой где минимум берется по всем векторам

Если положить , то получаем другую характеристику кода, аналогичную приведенной в определении 4.1.1, а именно Более того, имеет место следующая

Теорема 4.1.7. Кодовое расстояние двоичного кода С равно наименьшему весу ненулевых кодовых слов.

Локазательство. Доказательство непосредственно следует из того, что

Определение 4.1.8. Пусть векторное пространство всех двоичных -кортежей над . Тогда множество называется шаром радиуса с центром в

Лемма 4.1.9. Двоичный код С с кодовым расстоянием может исправлять все комбинации от 1 до t ошибок и может обнаруживать все комбинации от до ошибок тогда и только тогда, когда

Доказательство. Первая часть доказана в лемме 4.1.5. Оставляем читателю в качестве упражнения доказательство того, что может быть обнаружена любая комбинация ошибок.

Рис. 4.1.3. Связь между расстоянием и корректирующей способностью кода.

Геометрическая интерпретация лемм 4.1.5 и 4.1.9 дана на рис. 4.1.3. Например, если как на рис. то изменение четырех или менее цифр в кодовом слове приведет к тому, что полученный вектор будет ближе к чем к . Если как на рис. то ошибки в трех или менее цифрах будут исправлены, но четыре ошибки могут привести к тому, что полученный вектор будет равноудален как от так и ОТ и т.д.

Другое геометрическое представление двоичного кода — рассматривать векторы длины как вершины -мерного гиперкуба (см. рис. 4.1.4). Изменение цифры в двоичном векторе соответствует переходу к соседней вершине, при этом движение выполняется вдоль ребра, параллельного направлению, соответствующему позиции изменившейся цифры. Чтобы получить код с кодовым расстоянием d, выбираем те вершины гиперкуба, которые не могут быть соединены путем, состоящим менее чем из d ребер. На

Рис. 4.1.4. Двоичные кодовые слова как вершины гиперкуба.

рис. 4.1.4 код, состоящий из кодовых слов (0,0,1), (0,1,0) и (1,1,1), имеет 2.

Интересно узнать, сколько кодовых слов может иметь код, если он способен исправлять все комбинации t или менее ошибок. Верхнюю границу числа кодовых слов дает следующая

Теорема 4.1.10 (верхняя граница Хэмминга числа кодовых слов). Если двоичный код С, имеющий s кодовых слов длины , мажет исправлять все комбинации t или менее ошибок, то

Локазательство. Пусть — кодовые слова длины в С. Для каждого кодового слова рассмотрим шар радиуса t с центром - (определение 4.1.8). Поскольку код исправляет до t ошибок, шары не пересекаются. Поскольку шар с центром ; содержит все векторы, которые отличаются от - в позициях, мы видам, что число этих векторов равно

Поэтому во всех s шарах содержится

векторов, и доказательство завершается, если мы заметим, что общее число векторов внутри всех шаров не может превосходить — общее число двоичных векторов длины

Если в теореме 4.1.10 имеет место равенство, то код называется совершенным. Отметим также, что не для всех троек и s, определенных этой теоремой, непременно существует код с s кодовыми словами длины и, который может исправлять t ошибок. Например, положим тогда по теореме но кода с такими параметрами не существует. (Проверьте это.) Когда такие коды существуют, другой их характеристикой является