Духин А.А. Теория информации

Подождите немного. Документ загружается.

А. А. ДУХИН

ТЕОРИЯ

ИНФОРМАЦИИ

Допущено Учебно-методическим объединением ВУЗов

по образованию в области информационной безопасности

в качестве учебного пособия для студентов высших

учебных заведений, обучающихся по специальностям

090102 «Компьютерная безопасность»,

090 105 «Комплексное обеспечение информационной

безопасности автоматизированных систем» и

090106 «Информационная безопасность

телекоммуникационных систем».

МОСКВА

«Гелиос АРВ»

2007

УДК 355.01:510.21

ББК 68+22.16

Д32

Рецензенты:

доктор физ.-мат. наук, проф. А.А.Грушо

(Российский государственный

гуманитарный университет);

доктор тех. наук, проф. Ю.Н.Мельников

(Московский государственный

энергетический институт).

Духин, Александр Александрович.

Д32 Теория информации: Учебное пособие/А.А.Духин. - М.: Гелиос АРВ, 2007.

248 с, ил.

ISBN 978-5-85438-168-0

Изложены фундаментальные понятия энтропии и информации вероятностных

схем и их свойств. С использованием этих понятий рассмотрена математическая

теория передачи информации по каналам связи, включающая такие принципиальные

вопросы, как сжатие информации, построение корректирующих кодов, теоремы

кодирования.

Пособие рекомендуется для студентов и аспирантов, обучающихся по спе-

циальностям 090102 «Компьютерная безопасность», 090105 «Комплексное обеспе-

чение информационной безопасности автоматизированных систем» и 090106 «Инфор-

мационная безопасность телекоммуникационных систем», а также для специалистов,

работающих в области компьютерных технологий и технологий связи.

ББК 68+22.16

ISBN 978-5-85438-168-0

ОГЛАВЛЕНИЕ

Предисловие

Список обозначений

сокращений

Глава

ЭНТРОПИЯ

ИНФОРМАЦИЯ ВЕРОЯТНОСТНЫХ

СХЕМ

Аксиоматическое введение

теорию энтропии

вероятностных схем

Энтропия объединенной вероятностной схемы.

Условная энтропия

и ее

свойства

Взаимная собственная, условная информация

вероятностных схем

Выпуклость средней взаимной информации

вероятностных схем

Энтропия

взаимная информация непрерывных

вероятностных схем

Задачи

Глава

II.

Источники

СООБЩЕНИЙ

Математическая модель дискретного источника

сообщений, энтропия стационарных источников

.... 52

Теоремы Шеннона

для

источников

без

памяти

Марковские источники

Эргодические источники. Теорема Мак-Миллана

.... 75

Задачи

Глава

III.

ОПТИМАЛЬНОЕ КОДИРОВАНИЕ

Основные понятия

определения

Простейшие методы построения префиксных кодов

. . 99

Построение оптимальных кодов методом Хаффмана.

. 103

Теоремы

кодировании источников сообщений

111

Задачи

119

Глава

IV.

ЛИНЕЙНЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ

ОШИБКИ

123

Задачи помехоустойчивого кодирования. Основные

определения

понятия

124

Границы для параметров кодов

135

Методы декодирования при применении линейных

кодов

147

Код Хемминга

152

Методы построения новых кодов

156

Тождества Мак-Уильяме

162

Циклические коды

168

Коды Боуза-Чоудхури-Хоквингема, исправляющие

заданное число ошибок

174

Задачи

180

Глава

ДИСКРЕТНЫЕ (БЕЗ ПАМЯТИ) КАНАЛЫ ПЕРЕДАЧИ

ИНФОРМАЦИИ

СВЯЗАННЫЕ

НИМИ

ТЕОРЕМЫ

КОДИРОВАНИЯ

191

Классификация каналов связи. Пропускная

способность

192

Вычисление пропускной способности для

дискретного канала без памяти

197

Прямая

обратная теоремы Шеннона для двоичного

симметричного канала

206

Теоремы кодирования для дискретных каналов без

памяти

218

Задачи

228

Приложение

235

Библиография

241

ПРЕДИСЛОВИЕ

Пособие подготовлено на основе годовых лекционных курсов, прочитанных

на протяжении ряда лет на факультете Прикладной математики МГИЭМ, фа-

культете Спецдокументоведения РГГУ, факультете Вычислительной матема-

тики и кибернетики МГУ и других вузах для студентов старших курсов.

В предлагаемом пособии дано систематическое изложение Теории инфор-

мации и основ кодирования, обусловленных проблематикой передачи инфор-

мации. Изучение процесса порождения информации источником, её дальней-

шей передачи потребителю-адресату с последующим декодированием диктует

естественную логику организации изложения материала.

В связи с этим в Первой главе введены базовые понятия дисциплины:

"аксиоматически введенная энтропия вероятностной схемы", "условная

энтропия", "средняя взаимная информация" и др., а также связи и соотно-

шения между ними. Вторая глава посвящена математическому описанию

различных типов источников сообщений. В ней для ряда источников доказы-

ваются теоремы об информационной устойчивости вероятностных характе-

ристик порождённых последовательностей. В Третьей главе изложены ре-

зультаты, касающиеся построения оптимальных сжимающих информацию ко-

дов,

при фиксированном вероятностном распределении на символах алфавита

источника. В Четвёртой главе изложены вопросы построения линейных ко-

дов,

исправляющих заданное число ошибок. В завершающей Пятой главе

даётся описание дискретных каналов связи и их пропускных способностей. В

прямых и обратных теоремах кодирования обосновываются верхняя и нижняя

границы вероятности ошибки при передаче информации по дискретным кана-

лам связи без памяти. Именно для доказательства этих фундаментальных тео-

рем кодирования автором избрана данная последовательность общего изложе-

ния материала.

Вместе с тем, алгоритм построения оптимальных кодов, изложенный в

Главе 3, может быть рассмотрен самостоятельно как отправной, начальный

материал при изучении вопросов компрессии (архивирования) дискретной ин-

формации с помощью арифметического кодирования, адаптивных динамичес-

ких методов и словарных методов сжатия информации.

ПРЕДИСЛОВИЕ

Совершенно аналогично излагаемый в Главе 4 материал по линейным

кодам можно рассматривать как введение в Теорию корректирующих кодов.

В конце каждой главы помещены задачи, от тривиальных до проблемных,

решение которых будет способствовать углублённому освоению предлагаемого

курса.

Для изучения математической дисциплины "Теория информации" по пред-

лагаемой книге от читателя требуется знание фундаментальных математичес-

ких дисциплин: Математического анализа, Теории вероятностей, Теории слу-

чайных процессов, Линейной алгебры и Теории конечных полей.

Материал представлен согласно общеупотребимым формам: тройная нуме-

рация определений, теорем, лемм, формул, где первое число - номер текущей

главы, второе число - номер параграфа, третье число - собственный порядко-

вый номер. Доказательства наиболее употребимых в тексте оценок и нера-

венств вынесены в "Приложение". Пособие снабжено разделом «Список

обозначений», распределённым по главам. Предлагаемая библиография

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

так и те, к которым можно прибегнуть для расширения и углубления знаний

по Теории информации и кодированию.

Автор искренне благодарит С. В. Королёва, оказавшего активную дея-

тельную помощь в подготовке и редактировании пособия.

А.

А. Духин

СПИСОК

ОБОЗНАЧЕНИЙ

И СОКРАЩЕНИЙ

ОБЩЕУПОТРЕБИМЫЕ

ОБОЗНАЧЕНИЯ:

{l,2,3,...}~

множество натуральных чисел;

|А|-

число элементов в конечном множестве;

[а]-

ближайшее целое слева к заданному веществен-

ному а;

]а [- ближайшее целое справа к заданному веществен-

ному а;

l°g

~ логарифм числа х по основанию а > 1;

log

JnJg- двоичный, натуральный, десятичный логарифмы;

0~ пустое множество;

V- квантор всеобщности;

квантор существования;

^ ~ импликация.

ОБОЗНАЧЕНИЯ,

ИСПОЛЬЗУЕМЫЕ в

ГЛАВЕ

А - окончание доказательства утверждения;

А,

В,С,

АВ,... - вероятностные схемы;

aj,bj,ajbj,...-

исходы вероятностных схем;

р(Я|)

= Pi - вероятность исхода &

{

;

вероятность правильного декодирования;

Ре'РОО

~ вероятность ошибочного декодирования;

Н(А)-

энтропия вероятностной схемы А;

Н(А/В)-

условная энтропия вероятностной схемы А относи-

тельно вероятностной схемы В;

1(А;В)-

средняя взаимная информация вероятностных схем

А и В;

Ifai)-

собственная информация исхода а^

СПИСОК

ОБОЗНАЧЕНИЙ

I(aj /bj) - условная собственная информация, содержащаяся

в исходе а

(

, при условии реализации исхода bj;

l((A;B)/c)- средняя взаимная информация между схемами А и

В относительно вероятностной схемы С;

- операция сложения по модулю 2.

ОБОЗНАЧЕНИЯ,

ИСПОЛЬЗУЕМЫЕ

ГЛАВЕ

II:

[A;p(s)]-

источник сообщений с алфавитом А и вероятност-

ной мерой p(s);

С( -

lpt,„.,t+M(

itv*»»ai

^j))--

множество ^-членных последовательностей, порож-

дённых источником;

Т - оператор сдвига;

- к - кратное применение оператора сдвига;

шаговая энтропия марковского либо эргодического

источника;

- энтропия на знак, марковского либо эргодического

источника;

энтропия источника;

I(aj;bj)-

средняя взаимная информация между исходом

исходом bj вероятностных схем А и В, соответст-

венно.

ОБОЗНАЧЕНИЯ,

ИСПОЛЬЗУЕМЫЕ

ГЛАВЕ

ill:

р ~ средняя длина кодового слова неравномерного

кода;

Ц- коэффициент сжатия кода.

СПИСОК

ОБОЗНАЧЕНИЙ

ОБОЗНАЧЕНИЯ,

ИСПОЛЬЗУЕМЫЕ в

ГЛАВЕ

IV:

GF(q)

GF(p

)- конечное поле Галуа;

(GF(^))- n-мерное векторное пространство над GF(q);

g- вектор-строка;

_ вектор-столбец;

- единичная матрица (kxk);

dimG- размерность пространства кода;

F[X]-

кольцо многочленов над полем F;

F[x]/

-1- фактор-кольцо;

deg g(x) - степень многочлена g(x);

[f(

)]~

класс вычетов многочленов;

g(x)~-

порождающий многочлен;

h(x)-

проверочный многочлен;

(g(

)}~

главный идеал с порождающим многочленом

g(x);

G- линейный код;

(n,k,d)-

линейный код с длиной блока n, к-

информационными символами и кодовым

расстоянием d;

d(g,h)-

расстояние Хемминга между векторами;

W(g)-

вес Хемминга вектора g;

d- кодовое расстояние;

- порождающая матрица;

- проверочная матрица;

s(h)-

синдром вектора h;

R =

—

- скорость передачи информации;

..,A

)- весовой спектр кода;

Н - код Хемминга с параметрами

-l,

-г-1,

з);

- проверочная матрица кода Хемминга;

~ код, двойственный к коду Хемминга И

симплексный код.

СПИСОК

ОБОЗНАЧЕНИЙ

ОБОЗНАЧЕНИЯ,

ИСПОЛЬЗУЕМЫЕ

ГЛАВЕ

ДСК

двоичный симметричный канал;

ДКБП

дискретный канал

без

памяти;

С*

пропускная способность канала;

[А,В;Р]~

канал связи

вероятностными схемами

на

входе

выходе

А и В,

соответственно,

матрицей переходных вероятностей

Р.