Лекции по теории передачи информации

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

b=2

000 0 01111 0 1100

00 0000111111

Рис. 7.4. Схема построения рекуррентного кода

Кодирование и декодирование производятся с помощью регистров сдвига

и сумматоров по модулю два.

На выходе кодирующего устройства (рис. 7.5) получим последователь-

ность символов

1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1 . (7.20)

Эта последовательность поступает в дискретный канал связи.

Структурная схема декодера приведена на рис. 7.6. Процесс декодирова-

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

ступивших на декодер, и

их сравнении с контрольными символами, пришед-

шими из канала связи. В результате сравнения вырабатывается корректирую-

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

последовательности. Рассмотрим этот процесс более подробно. Пусть из дис-

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

ность (искаженные символы обозначены сверху чертой)

.1100100111110111010001

(7.21)

Устройство разделения (рис. 7.4) разделяет последовательность (7.21) на

информационные последовательности:

100111111010000

(7.22)

и контрольные символы:

10101101000

. (7.23)

111

Сумматор по модулю 2

Устройство задержки

на b тактов

Устройство задержки

на b тактов

Ключ

Вход

10110111001

Выход

1000111000111110010011

112

Устройство

разделения на

информационные и

контрольные символы

Устройство задержки

на b тактов

Устройство задержки

на b тактов

Устройство задержки

на b тактов

Устройство задержки

на b тактов

Сумматор

по модулю 2

Сумматор

по модулю 2

Инвертор

Схема совпадений

Устройство коррекции

Устройство задержки

на b тактов

Синдром

Ввод

Информационные

символы

Контрольные

символы

Формирователь

контрольных

символов

113

Последовательности символов (7.22) и (7.23) содержат ошибочные симво-

лы, которые подчеркнуты сверху. Формирователь контрольных символов из

(7.22) выдает последовательность символов

0 0 1 0 0 1 0 0 0 0 1, (7.24)

которая в сумме по модулю два с последовательностью (7.23) дает исправляю-

щую последовательность

0 0 1 1 0 0 1 0 1 0 0. (7.25)

Исправляющая последовательность (7.25) подается на инвертор, который

выдает последовательность (7.26) и одновременно поступает на устройство за-

держки на b и 2b тактов.

На выходе устройств задержки появляются последова-

тельности (7.27) и (7.28) соответственно. На выходе схемы совпадения получа-

ем последовательность (7.29)

1 1 0 0 1 1 0 1 0 1 1 … (7.26)

. 0 0 1 1 0 0 1 0 1 … (7.27)

. . . 0 0 1 1 0 0 1 … (7.28)

0 0 0 0

1 … (7.29)

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

ответствующее число тактов. Единица на выходе схемы совпадения возникает

только в тех случаях, когда на все его три входа подаются единицы. Она пред-

ставляет собой команду исправить ошибку. Исправленная последовательность

вырабатывается устройством коррекции в виде суммы по модулю два последо-

вательности (7.29)

и (7.22), задержанной на b тактов:

10011101101

10011111101.......

00000010000000000

. (7.30)

Точки в последовательности слева означают задержку на шесть тактов от-

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

символы.

После автоматического исправления последовательность (7.30) совпадает с

последовательностью на рис. 7.4 (верхняя строка). Как следует из (7.29), на пу-

ти информационных символов включено 3b = 6 ячеек регистра сдвига. При

этом для вывода всех ошибочных

символов необходим защитный интервал

1 = 13 символов.

Рассмотренный код позволяет исправлять пакет ошибок длиной l = 2b = 4.

В заключение следует отметить, что рекуррентный код находит примене-

ние в системах связи.

114

Контрольные вопросы

1. Сформулируйте теорему Шеннона о кодировании в каналах связи с по-

мехами.

Перечислите основные задачи, решаемые кодированием.

При каких предположениях решают задачи корректирующего кодиро-

вания?

Приведите классификацию корректирующих кодов.

Дайте определение блочным кодам.

Назовите основные характеристики корректирующих кодов

Покажите принцип обнаружения ошибок на геометрической модели ко-

дов.

Приведите выражение для определения числа контрольных символов.

Какие коды называются систематическими?

10.

Как строится образующая и проверочная матрицы систематического ко-

да?

11.

Как получается алгоритм кодирования и декодирования в систематиче-

ском коде?

12.

Какой принцип кодирования кодовых комбинаций в рекуррентном коде?

13.

Какое минимальное расстояние должно быть между пакетами искаже-

ний, чтобы принятая кодовая комбинация была однозначно декодируемой?

[1 с.197–219, с.288-296; 11 с. 120-126].

115

ЗАКЛЮЧЕНИЕ

Изложенные в конспекте лекций идеи и методы теории информации

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

и хранением информации. Теоретико-информационный подход приобрел зна-

чение метода исследования, позволяющего качественно и количественно со-

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

зависимо от их физической сущности.

Трудами

ученых и инженеров созданы и продолжают создаваться фунда-

ментальные методы анализа, синтеза и оптимизации информационных систем.

Развивается математическое моделирование процессов передачи сообщений,

разрабатываются и внедряются новые методы анализа нестационарных непре-

рывных каналов, неоднородных асимметричных дискретных каналов, помехо-

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

ненадежность аппаратуры и отклонение характеристик

устройств от идеаль-

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

но развивается корректирующее кодирование.

Методы теории информации все шире применяются для решения практи-

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

тем и сетей связи, радионавигационных и радиолокационных систем, автомати-

зированных систем управления воздушным движением, вычислительных сис-

тем,

измерительных комплексов и многих других.

Основные тенденции и перспективы теории информации следующие:

широкое внедрение цифровых методов передачи сообщений;

рост удельного веса алгоритмических и программных методов управле-

ния процессами передачи информации;

широкое использование корректирующего кодирования;

разработка методов оценки эффективности передачи информации с пози-

ции системного подхода;

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

пе-

редачи сообщения для анализа и синтеза информационных систем.

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

практическими потребностями информационной техники.

Следует ожидать, что идеи и методы теории информации будут успешно

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

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

116

ЛИТЕРАТУРА

Дмитриев В. И. Прикладная теория информации.-М.:Высш.шк.,1989.-

320 с.

Темников Ф.Е. и др. Теоретические основы информационной техники.-

М.: Энергия, 1979.-512 с.

Герасименко В.А., Мясников В.А. Защита информации от несанкцио-

нированного доступа.-М.: МЭИ, 1984.

Шеннон К. Работа по теории информации и кибернетике.-М.: ИЛ, 1963.

Питерсон У.,Уэлдон Э. Коды, исправляющие ошибки.-М.: Мир, 1976.

Игнатов В.А. Теория информации и передачи сигналов: Учебник для

вузов.-М.:Сов.радио,1979.-280с.

Пенин П.И., Филиппов Л.И. Радиотехнические системы передачи ин-

формации: Учеб. пособие для вузов.-М.:Радио и связь, 1984.-256 с

Фельдбаум А.А. и др. Теоретические основы связи и управления.-М.:

Физматгиз, 1963.-932 с.

Шувалов В.П. и др. Передача дискретных сообщений: Учебник для ву-

зов.-М.: Радио и связь, 1990.-464 с.

10. Бовбель Е.И. и др. Элементы теории информации.-Мн.: БГУ, 1974.–

111 с.

11. Ильин В.А. Телеуправление и телеизмерение: Учеб. пособие для ву-

зов.-3-е изд.-М.: Энергоиздат, 1982.-560 с.

12. Брюс Шнайер. Прикладная криптография. Протоколы

, алгоритмы, ис-

ходные тексты на языке Си.-М.: Изд-во ТРИУМФ, 2002.-816 с.

13. Столлингс Вильям. Криптография и защита сетей.-М., 2002.

14. Молдовен и др. Криптография. Скоростные шифры. –М., 2003.

15. Маслянников М. Практическая криптография.-М., 2003.

16. Петраков А.В., Лагутин В.С. Телеохрана.-М.: Энергоатомиздат, 1998.-

376 с.

117

СОДЕРЖАНИЕ

Введение.......................................................................................................................2

В.1. Определение информации...............................................................................2

В.2. Этапы обращения информации ......................................................................4

В.3. Система передачи информации......................................................................5

В.4. Уровни проблем передачи информации........................................................7

Контрольные вопросы.............................................................................................8

1. КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ .......................................9

1.1. Количество информации при равновероятности состояний источника

сообщений

................................................................................................................9

1.2. Энтропия ансамбля.........................................................................................11

1.3. Энтропия объединения...................................................................................12

1.4. Свойства энтропии .........................................................................................15

1.5. Количество информации от опыта в общем случае....................................18

1.6. Основные свойства количества информации ..............................................20

Контрольные вопросы...........................................................................................20

2. ИСТОЧНИКИ ДИСКРЕТНЫХ СООБЩЕНИЙ...........................................21

2.1. Энтропия эргодического источника .............................................................21

2.2. Свойство энтропии эргодических источников............................................24

2.3. Избыточность источника сообщений...........................................................25

2.4. Поток информации источника сообщений ..................................................26

Контрольные вопросы...........................................................................................27

3. ИСТОЧНИКИ НЕПРЕРЫВНЫХ СООБЩЕНИЙ .......................................27

3.1. Дифференциальная энтропия ........................................................................27

3.2. Свойства дифференциальной энтропии.......................................................30

3.3. Эпсилон - энтропия источника сообщений .................................................31

3.4. Эпсилон-производительность источника.....................................................32

3.5. Избыточность источника непрерывных сигналов ......................................33

3.6. Количество информации................................................................................34

Контрольные вопросы...........................................................................................34

4. ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ НЕПРЕРЫВНЫХ

КАНАЛОВ

.................................................................................................................35

4.1 Скорость передачи информации и пропускная способность......................35

4.2. Согласование источников с каналами..........................................................38

Контрольные вопросы...........................................................................................39

5. ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ ДИСКРЕТНЫХ

КАНАЛОВ СВЯЗИ

..................................................................................................40

5.1. Информационная модель канала и основные характеристики..................40

5.2. Энтропия источника и энтропия сообщения ...............................................44

5.3. Дискретный канал без помех.........................................................................45

5.4. Дискретный канал с помехами......................................................................46

5.5. Согласование характеристик сигнала и канала...........................................48

Контрольные вопросы...........................................................................................49

118

6. КОДИРОВАНИЕ ИНФОРМАЦИИ ПРИ ПЕРЕДАЧЕ ПО

ДИСКРЕТНОМУ КАНАЛУ БЕЗ ПОМЕХ

.........................................................50

6.1. Эффективное кодирование ............................................................................50

6.2. Префиксные коды...........................................................................................57

6.3. Недостатки системы эффективного кодирования.......................................58

6.4. Эффективное кодирование при неизвестной статистике сообщений.......59

Построение префиксного кода .................................................................................60

6.5. Кодирование как средство криптографического закрытия информации .62

6.6. Электронная цифровая подпись....................................................................80

6.7. Построение и использование хеш-функций ................................................85

6.8. Закрытие речевых сигналов в телефонных каналах ...................................88

Контрольные вопросы...........................................................................................98

7. КОДИРОВАНИЕ ИНФОРМАЦИИ ПРИ ПЕРЕДАЧЕ ПО

ДИСКРЕТНОМУ КАНАЛУ С ПОМЕХАМИ

....................................................99

7.1. Постановка задачи ..........................................................................................99

7.2. Классификация корректирующих кодов....................................................100

7.3. Основные характеристики корректирующих кодов .................................102

7.4. Способы введения избыточности в сигнал................................................106

7.5. Систематические коды.................................................................................107

7.6. Рекуррентные коды ......................................................................................110

Контрольные вопросы.........................................................................................115

ЗАКЛЮЧЕНИЕ......................................................................................................116

ЛИТЕРАТУРА........................................................................................................117

119