Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
b + c + d = 0, b σ+1 + c σ+1 + d σ+1 = 0. Тогда, выражая из первого равенства d и подставляя во второе, с учетом леммы 10 получаем b σ+1 + c σ+1 + (b + c) σ+1 = b σ c + bc σ = bc(b σ−1 + c σ−1 ) = 0. В силу условия (9.2), отображение x → x σ−1 взаимно однозначно, поэтому b = c. Противоречие с выбором b, c. Покажем теперь, что код P (σ) содержит слово веса 6. Рассмотрим попарно раз- личные элементы a, b, c поля GF (2 m ). Определим d и e из системы уравнений 9.3. Коды Препараты 113 ½ a σ+1 + b σ+1 + c σ+1 = d σ+1 , a + b + c + d = e. Несложно убедиться, что вектор ({0, e}, {a, b, c, d}) удовлетворяет условиям (9.3) и, следовательно, является кодовым. N Утверждение 19. Мощность кода P (σ) длины N = 2 m+1 равна 2 N /N 2 . Доказательство. Определим число пар (X, Y ), удовлетворяющих условиям (9.3). Выберем множество X так, чтобы мощность |X| была четной. Это можно сделать 2 2 m −1 способами. Выберем множество Y из ненулевых элементов поля так, чтобы вы- полнялись пункты 2 и 3 условия (9.3). Затем, если необходимо, добавим в множество Y элемент 0, чтобы мощность |Y | была четной. Пусть X = ∅. Тогда для Y выполняется система равенств P y∈Y y = 0, P y∈Y y σ+1 = 0, (9.5) см. пункты 2 и 3 в условии (9.3). Эту систему над GF (2 m ) можно рассматривать как систему из 2m уравнений над полем GF (2), заменив каждый элемент поля GF (2 m ) на вектор-столбец длины m над GF (2). Пусть α — примитивный элемент поля GF (2 m ). Поскольку σ удовлетворяет усло- виям (9.2), элемент α σ+1 имеет порядок 2 m −1, и следовательно, также является при- митивным элементом поля GF (2 m ). Минимальные многочлены M (1) (x), M (σ+1) (x), согласно свойствам 1 и 6 из разд. 7.6., неприводимы и имеют степень m. Тогда множе- ство Y , удовлетворяющее системе (9.5), соответствует кодовому слову циклического кода длины n = 2 m − 1 с порождающим многочленом M (1) (x) · M (σ+1) (x). Мощность такого циклического кода равна 2 n−2m Выберем другое множество X четной мощности. Тогда всевозможным множе- ствам Y таким, чтобы выполнялись условия (9.3), будут соответствовать векторы некоторого смежного класса циклического кода длины n = 2 m − 1 с порождающим многочленом M (1) (x) · M (σ+1) (x). Значит для фиксированного множества X число способов выбора подходящего множества Y равно 2 2 m −1−2m Таким образом, число различных пар (X, Y ), удовлетворяющих условиям (9.3), а значит принадлежащих коду P (σ), равно 2 2 m −1 | {z } выбор X · 2 2 m −1−2m | {z } выбор Y для X = 2 2 m+1 −2(m+1) = 2 N /N 2 . Утверждение доказано. N Из утверждений 18 и 19 немедленно вытекает теорема 64. В литературе кодом Препараты иногда называют максимальный двоичный код длины n − 1 с кодовым расстоянием 5. Очевидно, что каждый такой код получается 114 Глава 9. Другие коды выкалыванием одной координаты некоторого кода Препараты. Заметим, что опера- ция расширения кода с помощью добавления проверки на четность, вообще говоря, не является взаимно обратной для операции выкалывания. Однако, можно показать, что в случае совершенных кодов и кодов Препараты эти операции всегда взаимно обратны. Заключение Безусловно, представленный вниманию читателя материал не претендует на пол- ноту освещения всех областей теории кодов, корректирующих ошибки в каналах связи с шумами. Цель настоящих лекций — познакомить читателя с математиче- скими основами современной теории кодирования, подготовить его к чтению специ- альной литературы по теории кодирования, а также таких смежных дисциплин, как криптография и сжатие данных. Для понимания изложенного материала достаточно знаний линейной алгебры, основ теории чисел, комбинаторики и теории вероятно- стей. Впрочем, все необходимые для понимания основного материала определения и утверждения приведены в тексте. Практически все главы и разделы сопровождаются упражнениями, решение которых позволит читателю глубже понять теорию. Пособие предназначено для студентов математических факультетов и факульте- тов информационных технологий университетов, а также может быть полезно сту- дентам физических факультетов, интересующимся математическими основами про- блем передачи данных по каналам связи с помехами. Следует отметить, что выбор материала, представленного в настоящем пособии, отвечает в некотором смысле вкусам автора. В частности, больше внимания уделено различным методам построения известных кодов, нежели процедурам декодирова- ния. Автор со всей ответственностью осознает это и в дальнейших переизданиях дан- ного пособия возможно восполнение этих пробелов. Кроме того, следует отметить, что имеются также другие классические интересные и красивые темы по теории кодирования, не затронутые в пособии, такие, как преобразование Адамара, теоре- мы Мак-Вильямс, теория равновесных кодов, глубокие связи теории кодирования с теорией блок-схем, теорией групп, теорией графов, а также не рассмотрены схемы отношений, сверточные коды и др. Изложенный материал опробирован при чтении лекций в течение ряда лет в Но- восибирском государственном университете. Автор выражает признательность всем студентам, которые помогали шлифовать в дискуссиях презентации многих тем, тео- рем, лемм, а также своим детям Ване Могильных и Маше Соловьевой за постоянную моральную поддержку в период написания этого пособия и помощь в напечатании лекций. Глубокая благодарность моим коллегам Валентину Афанасьеву, Алексею Пережогину, Владимиру Потапову, Денису Кротову за тщательное чтение пособия и полезные замечания, позволившие улучшить текст; моим рецензентам В. В. Зяблову, С. А. Малюгину, Ю. Л. Сагаловичу; моему ученику аспиранту Института матема- тики СО РАН Антону Лосю за помощь в напечатании текста, сопровождение текста красивыми рисунками, считывание глав, оригинальную обложку; Н. Н. Токаревой, оказавшей всестороннюю техническую помощь при подготовке настоящего пособия — в формировании буклета, в печатании текста, подготовке рисунков, основательной и творческой считке текста, в написании раздела 9.3, посвященного кодам Препараты; О. Г. Заварзиной за подготовку верстки к печати. 115 Библиографический список основной литературы [1] Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. М.: Связь, 1979. 744 с. [2] Берлекэмп Е. Р. Алгебраическая теория кодирования: Пер. с англ. М.: Мир, 1971. 477 с. [3] Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. М.: Мир, 1986. 576 с. [4] Галлагер Р. Г. Теория информации и надежная связь: М.: Сов. радио, 1974. [5] Касами Т., Токура Н., Ивадари Е., Инагаки Я. Теория кодирования: Пер. с яп. М.: Мир, 1978. 576 с. [6] Колесник В. Д., Полтырев Г. Ш. Курс теории информации. М.: Наука, 1982. 416 с. [7] Конвей Дж. Н. , Слоэн Н. Дж. А. Упаковки шаров, решетки и группы: Пер. с англ. М.: Мир, 1990. Т. 1, 2. [8] Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976. 594 с. [9] Фано Р. М. Передача информации. Статистическая теория связи. М.: Мир, 1965. [10] Шеннон К. Е. Работы по теории информации и кибернетике. М.: Иностр. лит., 1963. [11] Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. 399 с. [12] Handbook on coding theory, Amsterdam: North-Holland, 1998. [13] Solov’eva F. I. "On perfect codes and related topics" Com 2 Mac Lecture Note Series 13, Pohang 2004. 80 p. (доступна по адресу http://www.codingtheory.gorodok.net/literature/lecture-notes.pdf) 116 Библиографический список основной литературы 117 Библиографический список дополнительной литературы [14] Аршинов М. Н., Садовский Л. Е. Коды и математика (рассказы о кодировании). М.: Наука, 1983. 144 c. [15] Васильев Ю. Л. О негрупповых плотно упакованных кодах. Проблемы киберне- тики. М: Физматгиз, 1962. Вып. 8. С. 337–339. [16] Гоппа В. Д. Введение в алгебраическую теорию информации. М.: Наука: Физ- матлит, 1995. [17] Calderbank A. R. The Art of Signaling: Fifty Years of Coding Theory. IEEE Trans. Inform. Theory. 1998. Vol. 44, № 6. P. 2561–2595. (доступна по адресу http://citeseer.ist.psu.edu/calderbank98art.html) [18] Камерон П., Ван Линт Дж. Х. Графы. Коды и схемы: Пер. с англ. М.: Наука, 1980. 140 с. [19] Cohen G., Honkala I., Litsyn S., Lobstein A. Covering codes. Netherlands: Elsevier, 1997. 542 p. [20] Колмогоров А. Н. Теория информации и теория алгоритмов. М.: Наука, 1987. 304 с. [21] van Lint J. H. Introduction to Coding Theory. Springer; Verlag; Berlin; Heidelberg, 1999. [22] Марков А. А. Введение в теорию кодирования. М.: Наука: Физматлит, 1982. [23] Реньи А. Дневник: Записки студента по теории информации: Пер. с венг. М.: Мир, 1980. [24] van Tillborg H. Error correcting codes – a first course. Sweden, Chartwell Bratt Ltd., 1997. [25] Яглом А. М., Яглом И. М. Вероятность и информация. М.: Наука, 1973. [26] Сайт "Теория кодирования в Новосибирском государственном университете" по адресу http://www.codingtheory.gorodok.net. [27] Сайт "Math Tree" : каталог математических интернет ресурсов (раздел "Теория кодирования") по адресу http://www.mathtree.ru. Предметный указатель α-компонента кода, 41 i-компонента кода, 41 асимптотически хорошее семейство кодов, 92 базовое множество, 18 вектор антиподальный, 43 вероятность на выходе, 29 вероятность ошибки декодирования, 26, 29 на символ, 28 на слово, 26, 29 вес Хэмминга, 5 весовой спектр совершенного кода, 43 граница БЧХ, 84 Варшамова-Гилберта, 13 Плоткина, 12 Синглтона, 12 Синглтона для нелинейных кодов, 12 Хэмминга, 11 группа автоморфизмов кода, 6 симметрий кода, 6 двоичный симметричный канал связи, 7 декодирование двоичных кодов, 21 по максимуму правдоподобия, 22 циклического кода, 77 идеал, 61, 70 квадратичный вычет, 96 невычет, 96 код Z 4 -линейный, 107 Адамара, 99 БЧХ, 86 в узком смысле, 86 двоичный, 87 примитивный, 86 Васильева, 38 Препараты, 107 Рида – Маллера, 103 Рида – Соломона, 88 Романова, 53 Соловьевой, 50 РМ, 107 Хэмминга, 14 q-значный, 53 Хямяляйнена, 55 Юстесена, 91 внешний, 49 внутренний, 49 двоичный, 5 дистанционно инвариантный, 42, 109 дуальный, 100 каскадный, 49 квазисовершенный, 27 линейный, 6, 9 ортогональный, 100 плотноупакованный, 11 равномерно-упакованный, 107 систематический, 73 совершенный, 11, 27 циклический, 6, 69, 70 эквивалентный, 6 кодер второй систематический, 74 несистематический, 75 первый систематический, 73 кодовые слова, 7 118 Предметный указатель 119 конструкция X4, 52 Васильева, 37, 38 Думера–Бакера, 108 Зиновьева, 56 Моллара, 39 Плоткина, 18, 38 Пулатова, 106 Фелпса, 57 обобщенная каскадная, 59 критерий Эйлера, 96 лемма Зигеля, 45 матрица Адамара, 93 нормализованная, 94 типа Пэйли, 96 типа Сильвестра, 95 Джекобстола, 98 Сильвестра, 96 кодовая, 9 кронекерово произведение, 95 мономиальная, 93 порождающая, 9 циклического кода, 73 проверочная, 9 канонический вид, 10 циклического кода, 75 метод каскадный, 49 свитчинга, 41 многочлен минимальный, 77 неприводимый, 62 нормированный, 71 порождающий, 71 приведенный, 71 примитивный, 63 проверочный, 75 неравенство Йенсена, 31 Чебышева, 33 нули кода, 81 окрестность множества, 41 определитель Вандермонда, 83 оценка верхняя числа совершенных кодов, 47 нижняя числа кодов Васильева, 38 ошибка вероятность, 26 несимметричная, 8 стирания, 8 поле, 61 порядок, 61 характеристика, 61 поле Галуа, 63 полином Жегалкина, 102 полная система функций, 102 порядок элемента, 63 проверка на четность обобщенная, 39 пропускная способность, 29 расстояние Хэмминга, 5 расширенный код, 16 свитчинг, 41 свойства квадратичных вычетов, 96 минимального многочлена, 77 полей Галуа, 64 символ Лежандра, 97 символы информационные, 9 проверочные, 9 синдром, 15 свойства, 24 скорость кода, 29 смежный класс, 22 лидер, 22 совершенная дизъюнктивная нормальная форма, 102 120 Предметный указатель стандартное расположение, 23 теорема Васильева, 37, 38 Глаголева, 18 Моллара, 39 Пулатова, 106 Ферма, 64 Шапиро и Злотника, 42 Шеннона, 29 о границе БЧХ, 84 о связи проверочной и порождающей матриц, 10 о существовании совершенных кодов, 44 о циклическом представлении кода Хэм- минга, 82 формула Стирлинга, 39 функция Мебиуса, 68 характеристика поля, 61 циклотомический класс, 78 число неприводимых многочленов, 68 циклических кодов, 79 энтропия, 29 свойства, 30 Оглавление Введение 3 Основные понятия и определения . . . . . . . . . . . . . . . . . . . . . . . . 5 Двоичный симметричный канал связи . . . . . . . . . . . . . . . . . . . . . 7 1 Линейные коды 9 1.1. Линейные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2. Границы объемов кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3. Код Хэмминга и его свойства . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.1. Определение кода Хэмминга . . . . . . . . . . . . . . . . . . . . 14 1.3.2. Примеры кодов Хэмминга длины 7 . . . . . . . . . . . . . . . . . 15 1.3.3. Декодирование кода Хэмминга . . . . . . . . . . . . . . . . . . . 15 1.4. Способы построения новых кодов . . . . . . . . . . . . . . . . . . . . . 16 1.5. Теорема Глаголева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Декодирование 20 2.1. Декодирование двоичных кодов . . . . . . . . . . . . . . . . . . . . . . 20 2.2. Декодирование линейных кодов . . . . . . . . . . . . . . . . . . . . . . 21 2.2.1. Стандартное расположение. Синдром . . . . . . . . . . . . . . . 21 2.2.2. Свойства синдрома . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3. Вероятность ошибки декодирования . . . . . . . . . . . . . . . . . . . . 25 3 Теорема Шеннона 28 3.1. Необходимые понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2. Свойства энтропии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3. Необходимые комбинаторно-вероятностные утверждения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.4. Доказательство теоремы Шеннона . . . . . . . . . . . . . . . . . . . . 33 4 Свитчинговые методы 36 4.1. Коды Васильева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2. Конструкция Моллара . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.3. Общая идея метода свитчинга . . . . . . . . . . . . . . . . . . . . . . . 40 4.4. Некоторые свойства совершенных кодов . . . . . . . . . . . . . . . . . 41 4.4.1. Дистанционная инвариантность . . . . . . . . . . . . . . . . . . 41 4.4.2. О существовании совершенных кодов . . . . . . . . . . . . . . . 43 4.4.3. Верхняя оценка числа совершенных кодов . . . . . . . . . . . . 45 121 122 Оглавление 5 Каскадные методы 48 5.1. Основная идея каскадного способа построения . . . . . . . . . . . . . 48 5.2. Коды Соловьевой (1981) . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.3. Коды Романова . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.4. Коды Хямяляйнена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.4.1. Код Хэмминга над GF (q) . . . . . . . . . . . . . . . . . . . . . . 53 5.4.2. Конструкция Хямяляйнена . . . . . . . . . . . . . . . . . . . . . 54 5.5. Каскадная конструкция Зиновьева (1988) . . . . . . . . . . . . . . . . 55 5.6. Каскадная конструкция Фелпса (1984) . . . . . . . . . . . . . . . . . . 56 5.7. Обобщенная каскадная конструкция . . . . . . . . . . . . . . . . . . . 57 6 Поля Галуа 60 6.1. Основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.2. Строение конечных полей . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.3. Примеры конечных полей . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.4. Число неприводимых многочленов . . . . . . . . . . . . . . . . . . . . 67 7 Циклические коды 69 7.1. Определение и свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.2. Порождающий многочлен . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.3. Кодирование циклических кодов . . . . . . . . . . . . . . . . . . . . . . 73 7.4. Проверочный многочлен . . . . . . . . . . . . . . . . . . . . . . . . . . 75 7.5. Декодирование циклического кода . . . . . . . . . . . . . . . . . . . . . 77 7.6. Минимальный многочлен и его свойства . . . . . . . . . . . . . . . . . 77 7.7. Число циклических кодов . . . . . . . . . . . . . . . . . . . . . . . . . . 79 8 Коды БЧХ 81 8.1. Нули кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 8.2. Циклическое представление кода Хэмминга . . . . . . . . . . . . . . . 82 8.3. Определитель Вандермонда . . . . . . . . . . . . . . . . . . . . . . . . 83 8.4. Граница БЧХ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8.5. Коды БЧХ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 8.6. Двоичные коды БЧХ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 8.7. Коды Рида-Соломона . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 8.7.1. Определение и свойства . . . . . . . . . . . . . . . . . . . . . . . 88 8.7.2. Использование кодов Рида-Соломона для получения двоичных кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 8.8. Коды Юстесена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 9 Другие коды 93 9.1. Матрицы Адамара, коды Адамара . . . . . . . . . . . . . . . . . . . . 93 9.1.1. Матрицы Адамара . . . . . . . . . . . . . . . . . . . . . . . . . . 93 9.1.2. Матрица Сильвестра . . . . . . . . . . . . . . . . . . . . . . . . . 95 9.1.3. Матрица Адамара по типу Пэйли . . . . . . . . . . . . . . . . . 96 9.1.4. Коды Адамара . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 9.1.5. Связь кодов Адамара с кодом Хэмминга . . . . . . . . . . . . . 100 9.2. Коды Рида-Маллера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.2.1. Коды с параметрами кодов Рида-Маллера . . . . . . . . . . . . 106 Оглавление 123 9.3. Коды Препараты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Заключение 115 Ф. И. Соловьева ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ Учебное пособие Редактор С. Д. Андреева Подписано в печать 14.06.2006 г. Формат 84×120 / 8. Офсетная печать. Уч.-изд. л. 17,7. Усл. печ. л. 14,4. Тираж 200 экз. Заказ № Редакционно-издательский центр НГУ. 630090, Новосибирск-90, ул. Пирогова, 2. |