П.Г. Демидова
Составитель: М.В. Краснов
К 78
Теория кодирования : метод. указания / сост. <...> Основные определения
Пусть имеется сообщение i = {u0 , , uk −1}, состоящее из
символов алфавита A = {0,, q − 1}, которое должно быть передано
по каналу связи. <...> Последовательность с называется в этом случае кодовым словом, а
i – информационным словом. <...> Определение 1.1 Блоковым кодом ξ над алфавитом из q
символов называется множество q-ичных последовательностей
длины n. <...> Блоковый код ξ мощности q k называется
(n,k)-кодом. <...> 3
О блоковом коде судят по трем параметрам: длине блока n,
информационной длине k и минимальному расстоянию d * . <...> Расстоянием по Хэммингу между двумя q-ичными последовательностями x и y длины n называется число
позиций, в которых они различны. <...> Тогда
минимальное расстояние кода ξ равно наименьшему из всех
расстояний по Хэммингу между различными парами кодовых слов,
то есть d * = min d (ci , c j ).
ci ,c j ∈ξ ,i ≠ j
Если d * ≥ 2t + 1, то код может исправлять t ошибок. <...> Кольцом R называется множество с двумя
определенными на нем бинарными операциями; первая называется
сложением (обозначается +), вторая называется умножением
(обозначается ∗), причем имеют место следующие аксиомы:
4
– относительно сложения (+) R является абелевой группой
(0 – единичный элемент);
– замкнутость: произведение a * b принадлежит R для любых
a, b ∈ R;
– (a * b) * c = a * (b * c) для любых a, b, c ∈ R;
– существует элемент 1∈ R такой, что a *1 = 1* a = a для
любого элемента a ∈ R;
– (a + b) * c = (a * c) + (b * c) для любых a, b, c ∈ R. <...> Полем называется множество с двумя
определенными на нем операциями – сложением и умножением,
причем имеют место следующие аксиомы:
– множество образует абелеву группу по сложению
(0 – единичный элемент);
– поле замкнуто относительно умножения, и множество
элементов ( ≠ 0 ) образует абелеву группу по умножению
(1 – единичный элемент);
– закон дистрибутивности: (a + b) * c = (a * c <...>
Теория_кодирования_.pdf
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П.Г. Демидова
Кафедра компьютерных сетей
Теория кодирования
Методические указания
Рекомендовано
Научно-методическим советом университета
для студентов, обучающихся по специальности
Прикладная математика и информатика
Ярославль 2006
Стр.1
УДК 007
ББК 181я73
К 78
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2006 года
Рецензент
кафедра компьютерных сетей Ярославского государственного
университета им. П.Г. Демидова
Составитель: М.В. Краснов
Теория кодирования : метод. указания / сост.
К 78
М.В. Краснов; Яросл. гос. ун-т. – Ярославль : ЯрГУ, 2006. –
48 с.
Основное использование вычислительной техники связано
с хранением и передачей информации. При хранении
информации возникает задача экономного метода записи.
При передаче информации возникает задача ее защиты от
случайных помех. Описанию некоторых математических
понятий и приемов, используемых при решении этих задач,
и посвящена данная работа.
Предназначено для студентов, обучающихся по специальности
010501 Прикладная математика и информатика
(дисциплина «Теория информации и кодирование», блок
ДС), очной формы обучения.
УДК 007
ББК 181я73
© Ярославский государственный университет, 2006
© М.В. Краснов, 2006
2
Стр.2
Оглавление
1. Коды, исправляющие ошибки ...................................................... 3
1.1. Основные определения ............................................................ 3
1.2. Некоторые сведения из алгебры ............................................ 4
1.3. Поля Галуа ................................................................................ 6
1.4. Минимальные многочлены ...................................................... 9
1.5. Линейные блоковые коды ...................................................... 10
1.5.1. Стандартное расположение .......................................... 11
1.5.2. Описание алгоритма декодирования по синдрому ..... 12
1.5.3. Коды Хэмминга ............................................................. 13
1.6. Циклические коды .................................................................. 14
1.7. БЧХ-коды ................................................................................ 16
1.7.1 Построение примитивного БЧХ-кода ........................... 16
1.7.2. Построение общего БЧХ кода максимальной длины . 18
1.7.3. Декодер БЧХ-кодов ....................................................... 19
Задачи ............................................................................................ 24
2. Методы сжатия информации ...................................................... 25
2.1. Статистические методы .................................................... 26
2.1.1. Алгоритм Хаффмана ..................................................... 26
2.1.2. Арифметическое кодирование ..................................... 30
2.2. Преобразующие методы ....................................................... 35
2.2.1. Словарные методы ........................................................ 35
2.2.1.1. Алгоритм LZ77 .................................................... 35
2.2.1.2 Алгоритм LZSS .................................................... 38
2.2.1.3. Алгоритм LZ78 .................................................... 39
2.2.1.4. Алгоритм LZW .................................................... 41
2.2.2. Алгоритм RLE ................................................................ 43
Задачи ............................................................................................ 45
Литература ......................................................................................... 46
47
Стр.47
Теория
Кодирования
50
Стр.50