Файл: прикладная теория информации.pdf

Министерство образования Республики Беларусь
Учреждение образования
«Белорусский государственный университет информатики и радиоэлектроники»
Институт информационных технологий
Кафедра физико-математических дисциплин
А. И. Митюхин
«ПРИКЛАДНАЯ ТЕОРИЯ ИНФОРМАЦИИ»
Рекомендовано УМО по образованию в области информатики
и радиоэлектроники в качестве учебно-методического пособия
Минск БГУИР 2023

УДК [621.391.7+004.056](076)
ББК 32.811.4 я73+32.972.5я73
М67
Рецензенты : кафедра полиграфического оборудования и систем обработки информации учреждения образования
«Белорусский государственный технологический университет»
(протокол № от); заведующий лабораторией идентификации систем государственного учреждения «Объединенный институт проблем информатики Национальной академии наук Беларуси»,
ОИПИ НАН Беларуси, доктор технических наук, профессор А. А. Дудкин
Митюхин, А. И.
М67 Прикладная теория информации : учеб.-метод. пособие / А. И. Митюхин.
– Минск : БГУИР, 2023. – 199 с. : ил.
ISBN 978-985-543-356-0.
Рассмотрены понятия теории информации – эффективное и помехоустойчивое кодиро- вание, защита информации. Дано описание алгоритмов, позволяющих уменьшать объем передаваемых, хранимых или распределяемых данных. Представлены основные методы кодирования и декодирования линейных кодов, корректирующих ошибки. Ме- тоды и алгоритмы теории информации изложены с учетом их практической направлен- ности. Учебный материал содержит примеры решения задач на основе практического использования доступного математического аппарата. Изложение тем сопровождается иллюстрациями и заданиями для самостоятельного выполнения.
УДК [621.391.7 + 004.056](076)
ББК 32.811.4 я73+32.972.5я73
ISBN 978-985-543-356-0 ©Митюхин А. И., 2023
© УО «Белорусский государственный университет информатики и радиоэлектроники», 2023

3
Содержание
ВВЕДЕНИЕ ………………………………………………………………………….6
ЧАСТЬ 1. ИНФОРМАЦИЯ. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ ......................... 9 1. МОДЕЛЬ КАНАЛА ПЕРЕДАЧИ, ХРАНЕНИЯ, ОБРАБОТКИ И
РАСПРЕДЕЛЕНИЯ ИНФОРМАЦИИ .......................................................................9 1.1. Обобщенная модель канала передачи, хранения, обработки и распределения информации . ......................................................................................9 1.2. Эталонная модель взаимосвязи открытых систем. . ..............................11 1.3. Первичное кодирование информации ……………………………........11 2. КАЧЕСТВЕННАЯ И КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ .......15 2.1. Дискретный источник информации без памяти ………………............15 2.2. Канал передачи информации .………………………………………......17 2.3. Дискретный канал без памяти …………………………………….........17 2.4. Характеристики дискретного канала без памяти ..................................19 2.5. Модель связанных источников ...............................................................23 2.6. Количественная оценка информации ……………………………….....26 2.7. Энтропия …………………………………………………………….......31 2.8. Относительная избыточность источника ………………………….......35 2.9. Задания для самостоятельного выполнения …………………………..36 3. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ ДЛЯ ДИСКРЕТНОГО
ИСТОЧНИКА БЕЗ ПАМЯТИ …………………………………………………......38 3.1. Условия взаимной однозначности алфавитного кодирования ……....38 3.2. Эффективное кодирование …………………………………………......40 3.3.Неравенство Крафта . ...............................................................................42 3.4. Средняя длина кодового слова . ...............................................................44 3.5. Задания для самостоятельного выполнения …………………………..46 4. ТЕОРЕМА ШЕННОНА О КОДИРОВАНИИ ДЛЯ КАНАЛА БЕЗ ШУМА
(первая теорема Шеннона) …………………………………………………….......48 4.1. Энтропия блокового источника ……………………………………......48 4.2. Первая теорема Шеннона ……………………………………………....49 4.3. Cжатие данных ……………………………………………………….....52 4.4.Энтропийное кодирование методом Хаффмена ....................................55 4.5. Универсальный алгоритм сжатия ...........................................................68 4.6. Задания для самостоятельного выполнения …………………………..75 5. КАНАЛЫ БЕЗ ПАМЯТИ И ПЕРЕДАЧА ИНФОРМАЦИИ .............................78 5.1. Комбинирование источников ......................... .........................................78 5.2. Взаимная информация .. .... .....................................................................79 5.3. Совместная энтропия ……………………………………………….......81 5.4. Условная энтропия . .................................................................................83 5.5. Соотношение между совместной и условной энтропией ....................91 5.6. Пропускная способность канала .............................................................92 5.7. Дифференциальная энтропия ..................................................................99 5.8. Пропускная способность непрерывного канала...……………………100

4 5.9. Статистические характеристики каналов.............................................104 5.10. Задания для самостоятельного выполнения.………………………..105 6. ВВЕДЕНИЕ В ЗАЩИТУ ИНФОРМАЦИИ.......................................................107 6.1. Составляющие информационной безопасности ..................................108 6.2. Информационные угрозы и атаки ......................................................... 108 6.3. Модели разграничения доступа к информации ...................................109 6.4. Обеспечение целостности данных в инфокоммуникационных системах и сетях .......... ............................................................................................112 6.5. Общие сведения по классической криптографии ...............................113 6.6.Алгоритмы блочного шифрования .......................................................116 6.7. Ассиметричные алгоритмы шифрования ............................................117 6.10. Задания для самостоятельного выполнения.………………………..123
ЧАСТЬ 2. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ .....................................124 7. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО
КОДИРОВАНИЯ ……………………………………………………………….....124 7.1. Основная теорема Шеннона кодирования для канала с шумом
(вторая теорема Шеннона) ……………………………………………………......124 7.2. Возможность исправления ошибок помехоустойчивым кодом ........125 8. АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ ..................................................................134 8.1. Группы .. ..................................................................................................134 8.2.Разложение группы на смежные классы ..............................................143 8.3. Определение смежного класса кода .....................................................144 8.4. Кольцо. .. ..................................................................................................146 8.5. Конечные поля . ......................................................................................149 8.6. Представление элементов конечного поля Галуа
????????(????
????
) ............ ....150 8.7. Векторные пространства и подпространства ......................................154 8.8. Задания для самостоятельного выполнения.…………………………155 9. ЛИНЕЙНЫЕ КОДЫ ……………………………………………………………157 9.1. Линейные коды, исправляющие ошибки: построение и основные свой- ства ....... ……………………………………………………………………………155 9.2. Вектор ошибок ... ....................................................................................159 9.3. Порождающая и проверочная матрица систематического линейного кода........................................................................................................................... 160 9.4. Кодирование линейным кодом .............................................................163 9.5. Линейный код Рида-Маллера ................................................................165 9.6. Линейный код Хэмминга ……………………………………………...167 9.7. Совершенные и квазисовершенные коды ............................................169 9.8. Вычисление минимального веса по проверочной матрице кода .......170 9.9. Задания для самостоятельного выполнения.…………………………170 10. МЕТОДЫ ДЕКОДИРОВАНИЯ ЛИНЕЙНЫХ КОДОВ...…………………..171 10.1. Декодирование кода на основе принципа максимального правдоподобия .. ......................................................................................................171 10.2. Декодирование по синдрому ...............................................................172

5 10.3. Декодирование кода Хэмминга ...........................................................177 10.4. Вычисление вероятности ошибки декодирования............................ 178 10.5. Задания для самостоятельного выполнения.………………………..181 11. КОНСТРУКЦИИ ЦИКЛИЧЕСКИХ КОДОВ…………....…………………..182 11.1. Алгебраическое описание циклических кодов.……………………..182 11.2. Порождающий многочлен циклического кода .…………………….184 11.3. Проверочный многочлен циклического кода .……………………...186 11.4. Минимальные многочлены..............................……………………...186 11.5. Низкоскоростные циклические коды..............................……………188 11.6. Корреляционный метод декодирования низкоскоростных кодов ..191 11.7. Коды максимальной длины..............................…................…………194 11.8. Задание для самостоятельного выполнения………………………...197
Список используемых источников ........................................................................199

6
ВВЕДЕНИЕ
Теория информации – это раздел науки, возникший в средине прошлого века. Умение применять на практике результаты теории информации стало важ- ным для специалиста, создающего современные инфокоммуникационные си- стемы. Теория информации возникла из статистической теории связи. Лишь ча- стично отвечая на вопросы о путях и способах технической реализации аппара- туры, эта теория позволяет вычислить эффективность системы передачи, хране- ния, обработки и перераспределения информации, определить максимально воз- можную эффективность системы. Для широкого класса информационных задач при определенных знаниях или допущениях относительно статистики шумов стало возможным построение аппаратуры, работающей на основе оптимального приема кодированных сигналов. Такие сигналы строятся на основе трех состав- ляющих теории информации – теории эффективного кодирования, теории поме- хоустойчивого кодирования и теории криптографического кодирования.
После того, как выбрана и обоснована конкретная схема оптимального приемника, фильтра, обнаружителя и т. п. возникают вопросы выбора метода ко- дирования, класса кода, способа защиты информации от несанкционированного доступа к ней.
Большая часть передаваемых, хранимых, распределяемых, преобразуемых данных соответствует звуковой, графической, специальной (военной), видеоин- формации. Увеличиваются технические затраты на хранение данных, предъяв- ляются более высокие требования по экономии канального частотного ресурса.
Алгоритмы теории информации позволяют уменьшить объем данных, использу- емых для представления информации и ее передачи по физическому каналу.
Задача теории информации – при известной статистике шумов выбрать та- кое множество передаваемых сигналов, чтобы правдоподобие правильного деко- дирования принимаемых сообщений было максимальным. При этом важно найти не только хороший код, но и эффективный алгоритм декодирования.
Теория эффективных и помехоустойчивых кодов (кодов сжатия и кодов, контролирующих ошибки) является одной из ветвей теории цифровой обработки сигналов (ЦОС). Существует тесная связь теории информации – кодирования и теории ЦОС. Но данные дисциплины развивались различными путями: одна раз- рабатывалась в основном инженерами совместно с математиками (алгебраи- стами), а другая – инженерами и прикладными математиками. Первые резуль- таты по теории информации появились в конце 40-х годов в работах американ- ских ученых К. Шеннона (Shannon Claude), М. Голея (M. J. E. Golay) и Р. Хэм- минга (R. Hamming). Можно определить следующие основные исторические этапы развития теории информации:
– 1948 г., К. Шеннон сформулировал и доказал теоремы кодирования для дискретного канала. К. Шеннон показал, что с каждым каналом передачи инфор- мации связано число ????. Это число определяет пропускную способность канала и измеряется в битах в секунду. Если требуемая от информационной системы cко-

7 рость передачи информации ????
????
(измеряемая в битах в секунду) меньше ????, то, ис- пользуя коды, контролирующие ошибки, для данного канала можно построить такую информационную систему, что вероятность ошибки на выходе декодера будет сколь угодно мала;
– 1950 г., Р. Хэмминг описал класс кодов, исправляющих независимые оди- ночные ошибки;
– 1952 г., Д. А. Хаффмен (D. A. Huffman, амер. ученый) показал, что, раз- работанный им алгоритм эффективного кодирования позволяет строить класс оптимальных префиксных кодов, позволяющий сжимать данные источника ин- формации.
– 1960 г., Р. К. Боуз (R. C. Bose, инд.-амер. ученый), Д. К. Рой-Чоудхури
(D. K. R-Chaudhari, инд.-амер. ученый) и независимо Р. К. Хоквингем, 1959 (R.
C. Hochquenghem, фран. ученый) открыли двоичные коды, исправляющие крат- ные независимые ошибки (коды Боуза – Чоудхури – Хоквингема (БЧХ-коды));
– 1963 г., И. С. Рид (I. C. Reed, амер. ученый) и Г. Соломон (G. Solomon, амер. ученый) предложили модификацию БЧХ-кодов для недвоичных каналов
(коды Рида – Соломона (PC-коды)). Эти коды нашли применение для исправле- ния пакетов и модулей ошибок;
– (1960 – 1970) г., с появлением микросхем средней степени интеграции началось практическое воплощение методов теории информации в каналах с большим уровнем помех. Применялись низкоскоростные коды максимальной длины (М-последовательности), коды Рида-Маллера (РМ-коды) и др. Кроме того, были разработаны новые эффективные алгоритмы декодирования (Питер- сон, Берлекэмп, Мэсси и др.).
–1977 г., разработан метод сжатия на основе словаря А. Лемпелем
(Abraham Lempel, изр. ученый) и Я. Зивом (Jacob Ziv, изр. ученый). Метод явля- ется основой алгоритмов сжатия ZIP, ARJ, gzip и др.
Кодирование применяется для защиты специальных радиоэлектронных си- стем гражданского и военного назначения, например, радиолокационных и ра- дионавигационных систем, систем видеографии от воздействия:
– непреднамеренных помех типа белого шума;
– преднамеренных помех специального типа, (например, сосредоточенных в спектре сигнала – узкополосных или широкополосных с кодовыми видами мо- дуляции).
Алгоритмы теории информации используются для защиты информацион- ных комплексов от случайного и несанкционированного доступа к информации; повышения надежности радиоэлектронных и вычислительных систем, делая их нечувствительными к отказам и сбоям.
Теория информация уже относится к классической науке, непрерывно раз- вивающаяся как в теоретическом, так и прикладном направлении.
Методы теории информации используются:
– для защиты данных в памяти вычислительных устройств, для передачи данных в вычислительных системах (такие системы очень чувствительны к

8 очень малой доле ошибок, т. к. даже одиночная ошибка может нарушить всю программу вычислений);
– в цифровых оптических дисках (компакт-дисках);
– в системах со сжатием данных;
– в системах связи с ограничением на передаваемую мощность, например, в системах ретрансляции через спутник, где увеличение мощности обходится очень дорого;
– в системах цифрового телевидения; обработки изображения;
– в системах передачи информации разного назначения, например, в систе- мах с пакетной коммутацией и разделением во времени, где длинные двоичные сообщения разделяются на пакеты, и пакет передается в отведенное временное окно. Из-за нарушения синхронизации пакеты могут быть утеряны. Кодирование позволяет обеспечить надежную синхронизацию в такой системе.
– в индустрии «Industrie 4.0» (4-я промышленная революция). Термин предложен федеральным правительством Германии и означает автоматизиро- ванное производство, реализуемое на основе использования современных ин- формационно-коммуникационных технологий и точной механики
(роботов)
Замечание.
«Industrie 1.0» – это механизация производства с помощью энергии воды и пара
. Вторая промышленная революция «Industrie 2.0» – это мас- совое производство на основе электрической энергии (сборочные линии и пр.).
«Industrie 3.0» –это производство на основе использованием электроники (станки с ЧПУ и пр.).
Рассмотрение вопросов теории информации начнем с представления об- щей модели информационного канала.

9
ЧАСТЬ 1. ИНФОРМАЦИЯ. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ
1. МОДЕЛЬ КАНАЛА ПЕРЕДАЧИ, ХРАНЕНИЯ, ОБРАБОТКИ
И РАСПРЕДЕЛЕНИЯ ИНФОРМАЦИИ
1.1. Обобщенная модель канала передачи, хранения, обработки
и распределения информации
Обобщенная модель канала имеет вид, представленный на рис. 1.1.
Рис. 1.1. Обобщенная модель канала передачи информации
Источник сообщений формирует поток непрерывных или дискретных со- общений.
Кодер первичного кода представляет информацию в форме, позволяющей упростить дальнейшую обработку.
Кодер источника сообщения предназначен для устранения информацион- ной избыточности. Он позволяет:
– более эффективно использовать частотный, временной и энергетический ресурсы;
– повысить скорость передачи информации.
Криптокодер преобразует информацию с целью защиты от случайного и несанкционированного доступа к ней.
Корректирующий кодер вводит информационную избыточность в переда- ваемое сообщение с целью обнаружения и (или) исправления ошибок сравни- тельно небольшой кратности (число ошибок ???? = 1, 2, 3, 4).