Макеты страниц Часть 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. Два вида двоичных симметричных каналов. предполагаем, что возникающие при передаче ошибки независимы и что изменилась только одна двоичная цифра, в то время как соседние цифры остались нетронутыми. (В действительности это не так, и внимание уделяется кодам, имеющим дело с каналами, в которых ошибки встречаются пакетами, или кластерами.) Наконец, мы предполагаем, что вероятность того, что Хотя мы не в состоянии помешать каналу допускать такие ошибки, мы можем принять некоторые меры, чтобы защититься от них. Идея состоит в том, чтобы к к информационным цифрам, которые мы хотим передать, добавить Определение 4.1.1. Любая последовательность из в каждом кодовом слове полностью определяются к информационными цифрами; мы будем называть кодом множество этих 2 векторов длины п. Для любого передаваемого кодового слова, учитывая тот факт, что мы имеем дело с зашумленным каналом, может быть получен любой из Определение 4.1.2. Если и — переданное кодовое слово, Получив v, пользователь должен решить, какое кодовое слово было передано, определив наиболее вероятную ошибку. Если все кодовые слова длины Определение 4.1.3. Расстояние Хэмминга Например, если
Аналогично можно показать, что вес Хэмминга — это норма на векторном пространстве
Для понимания следующей теоремы требуется некоторое знакомство с теорией вероятностей. Теорема 4.1.4. Пусть С — код для двоичного симметричного канала, и предположим, что С содержит s равновероятных кодовых слов длины п. Тогда декодирование в ближайшее кодовое слово является декодированием по максимуму правдоподобия, если вероятность Локазательство. Пусть
где
а поскольку мы всегда предполагаем, что
Поэтому вероятность Пример. Предположим, что код состоит из четырех следующих кодовых слов:
Если получен вектор Поскольку любой вектор v, поступивший к получателю, декодируется в ближайшее кодовое слово (ближайшее относительно расстояния Хэмминга), то естественно предположить, что хороший код — это код, в котором кодовые слова находятся «далеко» друг от друга. Это действительно так, потому что если расстояние между кодовыми словами велико, то чтобы кодовое и преобразовалось в (полученный) вектор v, который ближе к другому кодовому слову и, чем к и, должно встретиться много ошибок. Имеет место следующая Лемма 4.1.5. Пусть С — двоичный код с s кодовыми словами
Локазательство. Мы докажем лемму только в одном направлении, оставив остальное читателю. Предположим, что расстояние между любыми двумя кодовыми словами не меньше, чем
т.е. всегда больше, чем Определение 4.1.6. Кодовое расстояние Если положить Теорема 4.1.7. Кодовое расстояние двоичного кода С равно наименьшему весу ненулевых кодовых слов. Локазательство. Доказательство непосредственно следует из того, что Определение 4.1.8. Пусть Лемма 4.1.9. Двоичный код С с кодовым расстоянием Доказательство. Первая часть доказана в лемме 4.1.5. Оставляем читателю в качестве упражнения доказательство того, что может быть обнаружена любая комбинация
Рис. 4.1.3. Связь между расстоянием и корректирующей способностью кода. Геометрическая интерпретация лемм 4.1.5 и 4.1.9 дана на рис. 4.1.3. Например, если Другое геометрическое представление двоичного кода — рассматривать векторы длины
Рис. 4.1.4. Двоичные кодовые слова как вершины гиперкуба. рис. 4.1.4 код, состоящий из кодовых слов (0,0,1), (0,1,0) и (1,1,1), имеет 2. Интересно узнать, сколько кодовых слов может иметь код, если он способен исправлять все комбинации t или менее ошибок. Верхнюю границу числа кодовых слов дает следующая Теорема 4.1.10 (верхняя граница Хэмминга числа кодовых слов). Если двоичный код С, имеющий s кодовых слов длины
Локазательство. Пусть
Поэтому во всех s шарах содержится
векторов, и доказательство завершается, если мы заметим, что общее число векторов внутри всех шаров не может превосходить Если в теореме 4.1.10 имеет место равенство, то код называется совершенным. Отметим также, что не для всех троек
|
Оглавление
|