П.Г. Демидова
Составитель: М.В. Краснов
К 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. Коды, исправляющие ошибки
В этом разделе рассматриваются способы исправления ошибок
(помех) при передаче информации. Наиболее действенный способ
борьбы с помехами – введение избыточности, то есть, кроме
информационных символов, сообщение должно содержать некоторое
число контрольных символов, служащих для обнаружения и
исправления ошибок.
Пусть имеется сообщение {},
символов алфавита {},1,
=
0 ,
,
A −
= 0,
же алфавита {},1,
A −
= 0,
= c0 ,
q
q
,cn−1
1.1. Основные определения
i u uk −1
состоящее из
которое должно быть передано
по каналу связи. Из-за существования помех передача сообщения в
чистом виде исключается. Поэтому сообщение i кодируется другой
последовательностью {},
c состоящей из символов того
по которой можно восстановить i.
Последовательность с называется в этом случае кодовым словом, а
i – информационным словом.
Определение 1.1 Блоковым кодом
над алфавитом из q
символов называется множество q-ичных последовательностей
длины .n Мощность кода M – число этих последовательностей.
Определение 1.2. Блоковый код
мощности k
q называется
(n,k)-кодом.
При кодировании произвольной q-ичной последовательности
(n,k)-кодом она разбивается на части из k-символов, и каждая часть
кодируется элементом кода .
3
ξ
ξ
ξ
Стр.3
О блоковом коде судят по трем параметрам: длине блока ,n
информационной длине k и минимальному расстоянию
d* .
Минимальное расстояние
вводится
двумя следующими
определениями.
Определение 1.3. Расстоянием по Хэммингу между двумя q-ичными
последовательностями x и y длины n называется число
d( , ).yx
Определение 1.4. Пусть {}−−
минимальное расстояние кода
= c i = ,M 1
i ,
d =
*
ci ,c ∈ ≠i j
min
,
j
Если
d
* 2 1 ,+≥ t
d ci c ).
( ,
j
0,
позиций, в которых они различны. Это расстояние обозначается
через
код. Тогда
равно наименьшему из всех
расстояний по Хэммингу между различными парами кодовых слов,
то есть
то код может исправлять t ошибок.
Исправление ошибок в этом случае заключается в замене
принятого слова на ближайшее кодовое слово.
1.2. Некоторые сведения из алгебры
Определение 1.5. Бинарной операцией на множестве M
называется произвольная функция f M M M→×
:
( * )* =
a b c a b c
a e e a a=
что a b b a e= .
любых a, Gb∈ .
* = *
*
*
– существует единичный элемент
для любого a G ;∈
e G∈
.
называется группой, если выполнены следующие аксиомы:
– ассоциативность.
Определение 1.6. Множество G с бинарной операцией ∗
*( * ) для любых a, , Gcb ∈ ;
такой, что
– для любого Ga∈ существует обратный элемент b G ,∈ такой,
=
Группа G называется абелевой группой, если a b b a*
Группа G называется циклической (с образующим элементом
* =
для
a), если существует такой элемент a G ,∈ что любой элемент Gb∈
является некоторой степенью .a
Определение 1.7. Кольцом R называется множество с двумя
определенными на нем бинарными операциями; первая называется
сложением (обозначается +), вторая называется умножением
(обозначается ∗), причем имеют место следующие аксиомы:
4
ξ ξ
ξ
Стр.4
– относительно сложения (+) R является абелевой группой
(0 – единичный элемент);
a, Rb∈
–
– замкнутость: произведение a b* принадлежит R для любых
;
( * )* =
a b c a b c
любого элемента a R ;∈
– существует элемент
– a b c a c + b c
*( * ) для любых a, , Rcb ∈ ;
1∈ R такой, что
a*1= *1 a a
=
( + )* = ( * ) ( * ) для любых a, , Rcb ∈ .
Определение 1.8. Полем называется множество с двумя
определенными на нем операциями – сложением и умножением,
причем имеют место следующие аксиомы:
– множество образует абелеву группу по сложению
(0 – единичный элемент);
элементов (0
любых a b c,,
– поле замкнуто относительно умножения, и множество
≠ ) образует абелеву группу по умножению
(1 – единичный элемент);
– закон дистрибутивности:
из поля.
Определение 1.9. Пусть F – некоторое поле. Подмножество
S F⊂ называется подполем, если оно само является полем
относительно операций поля .F В этом случае поле F называется
расширением поля .S
Определение 1.10. Множество V называется векторным
пространством над полем F если
1) для пар элементов из V (векторов) определена операция
векторного сложения;
2) для элемента из V и скаляра (элемент поля F) определена
операция умножения на скаляр,
то результат выполнения операций дает элемент из V и
выполняются следующие аксиомы:
– V является абелевой группой относительно векторного
сложения;
– где
∀ a F∈ и ∀ v v V∈ ;
1, 2
– a b v av bv+=
( + )
,
, где ∀ a b F∈,
– (ab)v a bv= ( ), где ∀ a b F∈,
– 1 vv = где ∀ v V .∈
и ∀ v V ;∈
и ∀ v V ;∈
5
( +a b c a c + b c
)* = ( * ) ( * )
для
для
Стр.5