Теория информации и кодирования

Министерство образования и науки РФ

Сочинский государственный университет

туризма и курортного дела

Факультет информационных технологий и математики

Кафедра информационных технологий

 

 

Мацканюк А.А.

Теория информации и кодирования

 

Учебное пособие для студентов специальности

080801 Прикладная информатика (по областям применения)

 

Рекомендовано учебно-методическим объединением в области прикладной информатики как учебное пособие для студентов вузов, обучающихся по специальности 080801 Прикладная информатика (по областям применения)

 

Сочи, 2010 г.

УДК 007:681.3; 519.72

ББК 24.1

М

 

Мацканюк А.А. Основы теории информации и кодирования: учебное пособие для вузов. Сочи:РИО СГУТКД, 2010. -165 с., ил.

ISBN 5-

 

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

Пособие предназначено для студентов информационных специальностей и рекомендовано учебно-методическим объединением в области прикладной информатики для студентов специальности 080801 Прикладная информатика (по областям применения).

 

Оглавление

Введение. 7

Курс лекций.. 8

Определение понятия информация. 10

Фазы обращения информации. 11

Некоторые определения. 13

1. Меры информации. 17

1.1. Структурные меры количества информации. 17

1.1.1. Геометрическая мера. 18

1.1.2. Комбинаторная мера. 18

1.1.3. Аддитивная мера (мера Хартли) 19

1.2. Статистические меры.. 20

1.2.1. Энтропия и ее свойства. 20

1.2.1.1. Энтропия и средняя энтропия простого события. 21

1.2.1.2. Энтропия сложного события, состоящего из нескольких независимых событий 24

1.2.1.3. Вывод формулы среднего значения энтропии на букву сообщения. 24

1.2.1.4. Энтропия сложного события, состоящего из нескольких зависимых событий 25

1.2.2. Некоторые выводы, касающиеся статистической меры количества информации Шеннона 27

1.2.3. Литература. 28

1.2.4. Избыточность сообщения. 28

1.2.5. Пример оценки количества информации при помощи статистической меры Шеннона 29

1.3. Семантические меры информации. 30

1.3.1. Содержательность информации. 30

1.3.2. Целесообразность информации. 31

1.3.3. Динамическая энтропия. 31

1.4. Общие замечания об измерении информации. 32

1.5. Энтропия непрерывных сообщений. 33

1.5.1. Экстремальные свойства энтропии непрерывных сообщений. 36

1.5.1.1. Первый случай (значения сл. величины ограничены интервалом) 36

1.5.1.2. Второй случай (заданы дисперсия и математическое ожидание сл. величины) 37

1.5.1.3. Третий случай (сл. величина принимает только положительные значения) 39

1.5.2. Информативность (ε-энтропия) случайных величин, распределенных по некоторым наиболее известным законам распределения. 39

1.5.2.1. Нормальный закон распределения. 39

1.5.2.2. Равномерный закон распределения. 40

1.5.2.3. Экспоненциальный закон распределения. 40

1.5.3. Энтропия дискретного сообщения, получаемого из непрерывного путем его квантования по уровню.. 40

2. Квантование сигналов. 41

2.1. Виды дискретизации (квантования) 42

2.2. Критерии точности представления квантованного сигнала. 43

2.3. Элементы обобщенной спектральной теории сигналов. 45

2.4. Дискретизация по времени. 47

2.4.1. Разложение в ряд Котельникова (Теорема Котельникова) 47

2.4.1.1. Свойства функции отсчетов. 49

2.4.1.2. О практическом использовании теоремы Котельникова. 49

2.4.2. Выбор периода дискретизации (квантования по времени) по критерию наибольшего отклонения. 51

2.4.2.1. Интерполяция при помощи полиномов Лагранжа. 52

2.4.2.2. Оценка максимального значения ошибки при получении воспроизводящей функции на основе полинома Лагранжа. 53

2.4.2.3. Схема дискретизации-передачи-восстановления сигнала. 54

2.4.2.4. Расчет периода дискретизации при использовании для получения воспроизводящей функции полинома Лагранжа нулевого порядка. 56

2.4.2.5. Расчет периода дискретизации при использовании для получения воспроизводящей функции полинома Лагранжа первого порядка. 56

2.4.2.6. Расчет периода дискретизации при использовании для получения воспроизводящей функции полинома Лагранжа второго порядка. 57

2.4.2.7. Обобщение на случай использования полиномов Лагранжа произвольного порядка 58

2.4.3. Выбор интервала дискретизации по критерию среднеквадратического отклонения 58

2.5. Квантование по уровню.. 60

2.5.1. Оптимальное квантование по уровню.. 60

2.5.2. Дисперсия ошибки в случае использования равномерной шкалы квантования по уровню 63

2.5.3. Расчет неравномерной оптимальной в смысле минимума дисперсии ошибки шкалы квантования. 63

2.5.4. Расчет неравномерной оптимальной в смысле максимума количества информации в квантованном сигнале шкалы квантования. 66

2.5.5. Закон компандирования при условии равномерного закона распределения квантуемого сигнала 67

3. Кодирование информации.. 67

3.1. Общие понятия и определения. Цели кодирования. 67

3.2. Элементы теории кодирования. 70

3.3. Неравенство Крафта. 72

3.4. Теорема об обобщении некоторых результатов, полученных для префиксных кодов, на все однозначно декодируемые коды.. 73

3.5. Основная теорема кодирования для канала связи без шума (теорема 3) 74

3.6. Теорема о минимальной средней длине кодового слова при поблочном кодировании (теорема 4) 76

3.7. Оптимальные неравномерные коды.. 77

3.7.1. Лемма 1. О существовании оптимального кода с одинаковой длиной кодовых слов двух наименее вероятных кодируемых букв. 77

3.7.2. Лемма 2. Об оптимальности префиксного кода нередуцированного ансамбля, если префиксный код редуцированного ансамбля оптимален. 80

3.7.3. Коды Хаффмена. 81

3.7.4. Коды Шеннона−Фэно. 82

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

3.7.6. Особенности эффективных кодов. 87

3.8. Помехоустойчивое кодирование. 88

3.8.1. Классификация кодов. 89

3.8.2. Простейшие модели цифровых каналов связи с помехами. 91

3.8.3. Расчет вероятности искажения кодового слова в ДСМК. 92

3.8.4. Общие принципы использования избыточности. 92

3.8.5. Граница Хэмминга. 96

3.8.6. Избыточность помехоустойчивых кодов. 97

3.8.7. Математическое введение к алгебраическим кодам.. 97

3.8.8. Линейные коды.. 99

3.8.9. Упрощённый способ построения линейного кода. 100

3.8.10. Двоичные циклические коды.. 105

3.8.11. Некоторые свойства циклических кодов. 109

3.8.12. Построение кода с заданной корректирующей способностью.. 111

3.8.13. Матричное описание циклических кодов. 111

3.8.14. Выбор образующего полинома. 112

4. Передача информации.. 113

4.1. Виды каналов передачи информации. 114

4.2. Разделение каналов связи. 115

4.2.1. Частотное разделение. 115

4.2.2. Временное разделение. 116

4.2.3. Кодовое разделение. 116

4.2.4. Разделение по уровню.. 116

4.2.5. Корреляционное разделение. 118

4.2.6. Комбинированные методы разделения. 119

4.3. Пропускная способность каналов связи. 119

4.4. Пропускная способность дискретного канала связи с шумом.. 121

4.4.1. Типичные последовательности и их свойства. 125

4.4.2. Основная теорема Шеннона для дискретного канала с шумом.. 125

4.4.3. Обсуждение основной теоремы Шеннона для канала с шумом.. 129

4.5. Пропускная способность непрерывного канала при наличии аддитивного шума 130

Литература. 133

Приложение 1. Таблица неприводимых полиномов. 134

Учебно-лабораторный практикум.. 137

Лабораторная работа 1: Исследование информативности источников дискретных сообщений. 137

Теоретическое введение. 137

Возможный план выполнения работы с использованием табличного процессора Excel 140

Шаг 1. Поиск в Интернете текстов с суммарным объемом от около 10 тысяч символов на каждом из двух языках согласно варианту задания. 140

Шаг 2. Ввод текстовых файлов в Excel-таблицу с разбиением каждой строки текста на отдельные символы. 142

Шаг 3. Используя инструмент «гистограмма» пакета анализа надстройки Анализ данных, находим частоты появления каждого символа в текстах и по ним находим вероятности их появления в данном языке. 144

Шаг 4. Находим среднюю энтропию, приходящуюся на 1 букву сообщения. 149

Шаг 5. Находим абсолютную и относительную избыточности источника сообщений на заданных языках, сравнить эти языки по степени избыточности написанных на них текстов без учета и с учетом статистических связей между соседними буквами если размер алфавита языка позволил его произвести. 153

Шаг 6. Возьмем короткий отрезок текста на одном из заданных языков и найдем количество заключенной в нем информации. 153

Шаг 7. Проделаем те же операции с учетом зависимости двух соседних букв того же текста. 154

Шаг 8. Напишем отчет о выполненной работе с описанием всех вычислений и о том, как они выполнялись. Прокомментируйте результаты. 154

Шаг 9. Сдайте или отослать по электронной почте (alexm5@fromru.com) отчет на проверку преподавателю. 154

Шаг 10. Защитите лабораторную работу у преподавателя. 154

Варианты задания. 154

Результаты работы.. 156

Сдача работы.. 156

Вопросы для самопроверки. 156

Литература. 156

Приложение 1: Пример оформления титульного листа. 157

Приложение 2: Порядок создания нестандартных функций при использовании табличного процессора Excel 158

Введение. 158

Подключение возможности использования нестандартных функций. 158

Создание нестандартной функции. 160

Приложение 3: Описание функции ВПР. 164

Лабораторная работа 2. Исследование методов дискретизации непрерывных сообщений по времени. 166

Теоретическое введение. 166

Последовательность выполнения практической части работы.. 167

1. Знакомство с программой Wavosaur для записи и обработки звука. 168

2. Подключите к компьютеру головную гарнитуру (головной телефон и микрофон, рис. 2, слева) и нажмите кнопку Monitor input with vu meter, указанную на рис. 2 справа синей стрелкой. 169

3. Запись голоса и подготовка сигнала. 170

4. Импорт текстовых данных в Excel 179

Результаты работы.. 192

Литература. 192

Вопросы для самопроверки. 192

Иллюстрация к порядку вычисления ряда Найквиста-Котельникова. 193

Лабораторная работа 3. Исследование оптимального квантования непрерывных сообщений по уровню. 194

Теоретическое введение. 194

Возможный вариант выполнения работы.. 200

Результаты работы.. 208

Литература. 208

Вопросы для самопроверки. 208

Лабораторная работа 4. Исследование оптимальных (в смысле минимальной средней длины кодового слова) кодов на примере кодов Шеннона-Фэно и Хаффмена. 209

Теоретическое введение. 209

Коды Хаффмена. 209

Коды Шеннона−Фэно. 210

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

Особенности эффективных кодов. 214

Выполнение работы.. 215

Результаты работы.. 220

Литература. 220

Вопросы для самопроверки. 221

Лабораторная работа 5. Исследование кодов, обнаруживающих и исправляющих ошибки на примере линейного кода, исправляющего однократные ошибки. 221

Теоретическое введение. 221

Выполнение работы.. 229

Результаты работы.. 237

Литература. 237

Вопросы для самопроверки. 237

Введение

Курс лекций

Развитие науки и техники привело к появлению в 1948 г. работы Клода Шеннона (рис. 0.1) Рис. 0.1. Клод Элвуд Шеннон

Определение понятия информация

Информация наряду с материей и энергией является первичным понятием нашего мира и поэтому в строгом смысле не может быть определена. Можно лишь… · информация приносит сведения об окружающем мире, которых в рассматриваемой… · информация не материальна, но ее передача возможна только при помощи сообщений, представленных на материальных…

Фазы обращения информации

В процессе обращения информации можно выделить несколько фаз (рис. 0.2). 1 фаза ─ восприятие информации - выполняется автоматически или с…  

Некоторые определения

Информация, основанная на однозначной связи знаков или сигналов с объектами реального мира, называется семантической или смысловой. Информация, заключенная в характере (порядке и взаимосвязи) следования знаков… Также в общей науке о знаках (семиотике), кроме перечисленных, выделяют сигматический и прагматический аспекты…

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

Дискретный источник за конечное время создает конечное множество сообщений. Типичным дискретным сообщением являются текст, записанный с помощью… Непрерывные сообщения отражаются какой-либо физической величиной, изменяющейся…

Структурные меры количества информации

В структурных мерах во внимание принимается только дискретное строение носителя информации - количество содержащихся в нем информационных элементов, связей между ними или комбинаций из них.

Под информационными элементами понимаются неделимые части ─ кванты ─ информации в дискретных моделях реальных носителей информации, а также элементы алфавитов в числовых системах. В структурной теории различают геометрическую, комбинаторную и аддитивную меры информации.

Наибольшее распространение получила аддитивная мера Хартли - двоичная аддитивная мера, измеряющая количество информации в двоичных единицах ─ битах (binary digit).

Геометрическая мера

  Рис. 1.1. Внешний вид перфокарты. В случае сообщения, его можно записать (если это текст) в строчку и длину получившейся строки разделить на длину одной…

Комбинаторная мера

Этот вид меры информации используют тогда, когда требуется оценить возможность передачи информации при помощи различных комбинаций букв. Образование комбинаций - одна из форм кодирования информации.

Количество информации в комбинаторной мере равно количеству разрешенных комбинаций букв.

Можно договориться (условиться) о различных правилах образования комбинаций. Различные комбинации могут, например, отличатся буквами или порядком их следования или и тем и другим одновременно.

Подсчитаем количество информации, которое можно передавать в комбинаторном смысле перфокартами.

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

Буквы могут располагаться в 80х10 = 800 позициях в виде всевозможных соединений. Таких соединений может быть 2⁸⁰⁰. Таким образом, одна перфокарта несет на себе 2⁸⁰⁰ комбинаторных единиц информации (примерно 10²⁴⁰)

Аддитивная мера (мера Хартли)

В 1929 году Хартли была предложена аддитивная мера. Словом аддитивность (суммируемость) здесь подчеркивается важное свойство этой меры,… Количество информации по Хартли измеряется в битах (binary digit) и… Вернемся к нашему примеру с перфокартой. Каждая позиция на поверхности перфокарты может находиться в двух состояниях…

Статистические меры

Энтропия и ее свойства.

Если произошло событие (например вы получили сообщение), в результате чего неопределенность была полностью снята, априорная вероятность… I = - log2 P Если же событие не произошло, но вам известна вероятность его появления, вы имеете дело с неопределенностью в…

Энтропия и средняя энтропия простого события

Вероятности событий ─ положительные числа со значениями, принадлежащими интервалу [0,1], а их сумма равна 1. Выборочное пространство и его… Обозначим вероятности появления сообщений: P1, P2, ..., Pm. В этом случае энтропия конкретного k-го сообщения равна:

Метод множителей Лагранжа

Значения аргументов, при которых достигается экстремум, находится путём решения системы из n+k уравнений:   Для определения того, какой из эстремумов найден (максимум, минимум или седловая точка) проверяются знаки вторых…

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

Согласно теории вероятностей вероятность P такого события равна произведению вероятностей событий, его составляющих:

,

где k ─ количество событий, составляющих сложное событие.

Легко доказать, что энтропия Н этого события находится по формуле:

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

Вывод формулы среднего значения энтропии на букву сообщения

Если буквы в сообщении статистически независимы друг от друга, то вероятность P получения этого сложного многобуквенного сообщения вычисляется через… Энтропия всего сообщения по определению находятся по формуле: (1.1)

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

Как и в предыдущий раз, предположим, имеется сообщение, состоящее из n букв: , где j=1, 2, …, n – номера букв в сообщении по порядку, а i1, i2, …… С учетом взаимозависимости между буквами вероятность его получения теперь… (3)

Некоторые выводы, касающиеся статистической меры количества информации Шеннона

1. После получения сообщения получатель приобретает такое количество информации, которое равно энтропии полученного сообщения.

2. Если известно, что данное событие наверняка произойдет или не произойдет, его энтропия минимальна и равна 0.

3. Энтропия максимальна, если ожидаемые события могут произойти с равной вероятностью.

4. Количество информации, получаемое при приеме равновероятных сообщений, максимально и равно количеству информации по Хартли.

5. Энтропия сложного события, состоящего из нескольких независимых событий, равна сумме энтропий этих событий.

6. Энтропия сложного события, состоящего из нескольких зависимых событий, равна не сумме энтропий этих событий и может быть найдена с использованием матрицы взаимных вероятностей получения всевозможных комбинаций этих сообщений.

Литература

1. Nyquist H. Certain factors affecting telegraph speed, Bell system technical journal. 1924. v.3. p. 324.

2. Hartley R.V. Transmition of information, Bell system technical journal, 1928. v.7. p. 535.

3. Котельников. О пропускной способности "эфира" и проволоки в электросвязи. Материалы к I Всесоюзному съезду по вопросам технической реконструкции дела связи и развития слаботочной промышленности. Всесоюзный энергетический комитет, 1933.

Избыточность сообщения

Различают 2 вида избыточности – абсолютную и относительную. Абсолютная избыточность Dabs находится в виде разности между максимально… Dabs = Hmax ─ H .

Пример оценки количества информации при помощи статистической меры Шеннона

Рассмотрим оцифрованное телевизионное изображение с параметрами:

· количество строк в кадре Nстр=400;

· количество столбцов в кадре Nстолб=600;

· число градаций яркости Ярк = 2⁷=128;

· число градаций цвета Цвет =2¹⁴=16384;

· количество кадров за 1 сек Кадр = 25.

При таких параметрах количество информации по Хартли I_h равно:

I_h = N_стр* N_столб * Кадр * log₂(Ярк*Цвет) = 126 000 000 бит/сек.

Таким образом, за 1 сек. через телеэкран может быть передано максимум 126 миллионов бит. Но на самом деле передается намного меньше. Оценка количества информации с использованием меры Хартли соответствует оценке мерой Шеннона только в случае равных вероятностей передачи в каждой точке изображения значения любой яркости и любого цвета. Причем яркость и цвет каждой точки должны быть статистически независимыми друг от друга. Внешне это выглядит как экран с зернистым изображением. Такое изображение мы видим, когда телеприемник настроен на канал, по которому не ведется вещание, например поздней ночью или ранним утром.

Известно, что через зрение человек не может воспринимать более 50-100 бит/сек. Следовательно, реальное изображение несет в себе намного меньше информации. Действительно, точки реального изображения сильно связаны между собой и составленное из них изображение совсем не похоже на случайную смесь разноцветных и разноярких точек. Следовательно, телесигнал обладает очень большой избыточностью.

Кроме того, в человеческом мозгу хранится много моделей изображений, полученных на основании опыта прожитой жизни. Он обладает развитой способностью к интерполяции и логическому мышлению. Поэтому человек может распознавать и понимать передаваемое на экран изображение по малому числу элементов. Он может сжимать данные, выделяя из них главное ─ смысловое содержание. Все это, однако, находится за пределами шенноновской меры информации.

Семантические меры информации

Семантика[4] отражает смысл сообщения. Семантические меры количества информации ближе к человеческому представлению об информации. Они отражают смысл, полезность, целесообразность, содержательность и другие стороны информации. Общим же недостатком семантических мер является слабость математического обоснования, трудность в определении исходных данных и вследствие этого малая распространенность.

Содержательность информации

Содержательность события I выражается через функцию меры содержательности его отрицания: Cont(I) = M(~I) = 1-M(I), где I – рассматриваемое событие, M – функция меры содержательности, ~ – знак отрицания.

Целесообразность информации

Полученная информация может быть пустой, т.е. не изменять вероятности достижения цели, и в этом случае ее мера равна 0. В некоторых других случаях она может уменьшить вероятность достижения цели. В… Полученная информация может увеличить вероятность достижения цели. В этом случае количество полученной информации…

Динамическая энтропия

Количество информации в этом случае рассчитывается как разность энтропии в предыдущий момент времени (до получения новых сведений в результате… Обычно во всех вышеперечисленных задачах существует 2 набора объектов –… Здесь существует зависимость этих вероятностей от времени. Энтропия , где n(t) и m(t) – меняющиеся количества…

Общие замечания об измерении информации

1. Возможно большое количество определения и способов измерения информации.

2. Во всех определениях имеет место оценка неопределенности, неожиданности, многообразия, характеризуемая либо вероятностью, либо какой-либо другой мерой сложности.

3. Современные меры информации в значительной мере опираются на субъективные предпосылки.

4. После формализации понятия информации появляется возможность ее использования в ситуациях, для которых понятие информации по человеческим понятиям неприменимо. Это объясняется тем, что теория информации – математическая дисциплина и, например, физическое содержание вероятности в теории Шеннона в принципе может быть любым.

5. Вводимые определения информации могут быть беднее по смыслу того, что имеет в виду человек.

Энтропия непрерывных сообщений

Как было сообщено выше, средняя энтропия дискретного сообщения, входящего в полную группу из m независимых сообщений, находится по формуле: . Эта формула справедлива, в частности, для сообщений, состоящих из конечного… Если рассматривать попадание значения непрерывного сообщения в определенный интервал, как появление определенной…

Экстремальные свойства энтропии непрерывных сообщений

Представляет интерес решение следующей задачи. Заданы некоторые ограничения на параметры закона распределения непрерывного сообщения. Требуется с учетом этих ограничений найти такой закон распределения, при котором дифференциальная энтропия максимальна.

Решение подобных задач имеет практическое значение. Знание таких законов полезно при исследование космоса на предмет поиска в нем сигналов, имеющих искусственное происхождения, при постановке максимально эффективных помех в заданной полосе частот с помощью передатчика с ограниченной мощностью (например, при подавлении сотовой связи) и т.д.

Первый случай (значения сл. величины ограничены интервалом)

Найдем аналитическое выражение для закона f(a), который дает максимум дифференциальной энтропии . Эту задачу можно интерпретировать как предельный случай задачи на поиск условного экстремума функции бесконечного…

Второй случай (заданы дисперсия и математическое ожидание сл. величины)

Из этого следуют следующие условия, накладывающие ограничения на искомый закон распределения: ; ;

Третий случай (сл. величина принимает только положительные значения)

Аналогичным образом можно показать, что если случайная величина может принимать только положительные значения, т.е. , то максимальная дифференциальная энтропия получается при распределению сигнала по экспоненциальному закону:

, где M – математическое ожидание.

Ни рис. 1.7. изображены графики экспоненциального закона распределения при М=1 и М=2.

 

Рис. 1.7. Графики экспоненциального закона распределения.

1.5.2. Информативность (ε-энтропия) случайных величин, распределенных по некоторым наиболее известным законам распределения

Нормальный закон распределения

;

 

. (1.6)

Учтем, что константа может быть вынесена из под знака интеграла в первом слагаемом (1.6), а сам интеграл в этом случае равен 1.

Константу можно вынести из-под знака второго интеграла (5), а сам интеграл представляет собой дисперсию D.

Учитывая все это, получаем:

.

Равномерный закон распределения.

;

.

Экспоненциальный закон распределения

;

 

.

После преобразований и взятия интегралов (там, где нужно при помощи таблиц интегралов) получим: .

Энтропия дискретного сообщения, получаемого из непрерывного путем его квантования по уровню

Для всех трех случаев несложно получить энтропию дискретного сообщения, получаемого из непрерывного путем его квантования по уровню с шагом ∆a. Вспомним, то энтропия непрерывной величины равна:

.

При небольших шагах квантования ∆a энтропию квантованного сообщения можно находить по формуле:

.

Поэтому выражения энтропии квантованного сообщения при различных законах распределения будут иметь вид:

1) нормальный закон ;

2) равномерный закон: ;

3) экспоненциальный закон: .

Квантование сигналов

Предположим следует передать на расстояние информацию о форме некоторого непрерывного сигнала. Причем, как можно точнее. Для этого выполняются… 1. преобразование непрерывного сигнала в непрерывно-дискретную или дискретную… 2. кодирование эффективным кодом с целью устранения избыточности;

Виды дискретизации (квантования)

· квантование по уровню (будем говорить просто квантование); · квантование по времени (будем называть дискретизацией); · их сочетание.

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

Способы дискретизации и воспроизведения влияют на ошибку и ее параметры. Обычно, чем шире шаг квантования по уровню или по времени или чем меньше… Ошибка является функцией времени и потому неудобна для использования в… Поэтому в качестве такого критерия обычно используют какой-либо функционал ошибки.

Элементы обобщенной спектральной теории сигналов

Сигналы в обобщенной спектральной теории описываются в виде: , (2.1) где x(t) – описываемый сигнал;

Дискретизация по времени

Разложение в ряд Котельникова (Теорема Котельникова)

Описанный здесь результат Котельниковым был получен 1933 г., но ранее подобные результаты были получены в 1915 г. Виттакером и в 1928 г. Найквистом.

Котельников доказал, что, если некоторый сигнал x(t) имеет ограниченный сверху частотой f_m спектр, то его можно проквантовать по времени с периодом и затем с абсолютной точность восстановить по формуле:

(2.6)

Ряд (2.6) называется рядом Котельникова, а вышеуказанное утверждение – теоремой Котельникова.

По определению сигнал x(t) и его спектр S(jω) находятся в следующих отношениях:

; (2.7)

. (2.8)

Формулы (2.7) и (2.8) образуют пару преобразований Фурье (прямое и обратное. Ограниченный интервал интегрирования в (2.8) – следствие ограниченности спектра, поскольку . Здесь ω – круговая частота, а .

Образуем новый спектр S_п(jω) путем периодического (с периодом 2ω_m) продолжения спектра S(jω) вдоль оси ω.

Тогда его, как периодическую функцию можно разложить в ряд Фурье:

, (2.9)

где . (2.10)

В формулах (2.8) и (2.10) можно подставлять как S(jω), так и S_п(jω), так как на участке интегрирования они равны.

Сравним (2.8) и (2.10). Интегралы совпадают, если в (2.8) положить:

 

Домножим, кроме того, правую и левую части (2.8) на . Тогда правая часть (2.8) совпадет с левой частью (2.10). Следовательно, можно приравнять и левые части:

.

Подставим выражение для с_k в (2.9):

. (2.11)

Подставим (2.11) в (2.8), так как S(jω) = S_п(jω) при –ω_m<=ω<=ω_m :

 

(2.12)

Возьмем интеграл .

Введем обозначение z=t-kΔt, тогда определенный интеграл берется:

.

Учитывая, что получаем:

. (2.13)

Подставим (2.13) в (2.12):

, что и требовалось доказать.

Обозначим .

Функция называется функцией отсчетов.

Тогда формула восстановления принимает вид:

 

На рис. 2.4 изображена форма двух разных функций отсчетов:

 

Рис. 2.4. Графики функций отсчетов.

Свойства функции отсчетов

1. Функция отсчетов имеет максимальное значение = 1 при .

2. симметрична относительно точки .

3. Функция отсчетов =0 при .

4. Система функций ортогональна: .

О практическом использовании теоремы Котельникова

  Рис. 2.5. Возможная схема квантования-передачи-восстановления непрерывного… Технически восстановитель исходной функции может быть реализован при помощи электронного устройства, называемого…

Выбор периода дискретизации (квантования по времени) по критерию наибольшего отклонения

Если функция x(t) имеет ограниченный максимальной частотой спектр, время ее воспроизведения и сложность воспроизводящего устройства не имеют… Чаще, однако, одно или несколько из вышеуказанных условий не выполняется и… При воспроизведении исходной функции широко используют хорошо проработанные в математике методы интерполяции,…

Интерполяция при помощи полиномов Лагранжа

. (2.14) В этом случае , т.е. значения воспроизводящей и исходной функций совпадают… Функции, обладающие этим качеством, нашел выдающийся французский математик и механик Жозеф Луи Лагранж (1736-1813). …

Оценка максимального значения ошибки при получении воспроизводящей функции на основе полинома Лагранжа

, (2.16) где K(t) – вспомогательная функция, которую надо найти. Для произвольного t* имеем:

Схема дискретизации-передачи-восстановления сигнала

Предположим, что для дискретизации-передачи-восстановления сигнала используется схема, изображенная на рис. 2.7.

 

Рис. 2.7. Схема дискретизации-передачи-восстановления сигнала X(t).

Верхняя граница максимальной ошибки , как показано выше, задается формулой .

Графики на интервале дискретизации при разном порядке n полинома Лагранжа изображены на рис. 2.8.

 

Рис. 2.8. График сомножителя при разных n.

Ясно, что наименьших значений достигает на серединных шагах . Следовательно, и восстанавливать сигнал лучше всего именно на этих серединных отрезках. Это позволит уменьшить .

Для этого предлагается использовать порядок восстановления, иллюстрируемый графиками, приведенными на рис. 2.9.

 

Рис. 2.9. Порядок восстановления исходной функции при использовании для этого полиномов Лагранжа 4 степени.

 

.

Рассмотрим несколько вариантов, отличающихся порядком n используемых полиномов Лагранжа.

Расчет периода дискретизации при использовании для получения воспроизводящей функции полинома Лагранжа нулевого порядка

Интерполяция полиномами нулевого порядка n=0.

Таких полиномов всего 1:

, отсюда при

Воспроизводящая функция при использовании полиномов Лагранжа нулевого порядка имеет вид ступенчатой кривой (рис. 2.10).

 

Рис. 2.10. Воспроизводящая функция при использовании для восстановления полиномов Лагранжа нулевого порядка.

Подставив n=0 в формулу максимальной погрешности, по заданной погрешности найдем максимальный шаг квантования:

, отсюда и .

Расчет периода дискретизации при использовании для получения воспроизводящей функции полинома Лагранжа первого порядка

Интерполяция полиномами первого порядка n=1.

Таких полиномов оказывается всего 2:

;

.

Видно, что последнее уравнение – уравнение прямой.

В графической форме такая интерполяция выглядит в виде ломаной линии (рис. 2.11).

 

Рис. 2.11. Воспроизводящая функция при использовании для восстановления полиномов Лагранжа первого порядка.

 

Найдем .

 

Для этого приравняем производную этой величины по t к нулю:

=0. Отсюда .

Вторая производная отрицательна. Это означает, что найден именно максимум.

Теперь подставим найденное t в формулу максимальной погрешности:

;

и найдем шаг дискретизации:

.

Расчет периода дискретизации при использовании для получения воспроизводящей функции полинома Лагранжа второго порядка

Интерполяция полиномами второго порядка n=3

 

− парабола.

Обобщение на случай использования полиномов Лагранжа произвольного порядка

− некоторая функция n. Кроме того, для Mn+1 выведена оценка сверху: Таблица 2.1. n   89,5 …

Выбор интервала дискретизации по критерию среднеквадратического отклонения

Начнем с полинома нулевого порядка. Ошибка, как известно, вычисляется по формуле: Дисперсия ошибки в случае стационарных эргодических процессов может быть вычислена по формуле:

Квантование по уровню

Оптимальное квантование по уровню

  Рис. 2.13. Квантование по уровню. Это квантование сводится к замене значения исходного сигнала уровнем того шага, в пределы которого оно (это значение)…

Дисперсия ошибки в случае использования равномерной шкалы квантования по уровню

Найдем дисперсию ошибки в случае использования равномерной шкалы квантования, т.е. равенства всех шагов квантования.

В этом случае:

и

Следовательно при постоянном шаге квантования дисперсия ошибки квантования находится по формуле (2.21)

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

Введем вспомогательную переменную . Тогда, учитывая (2.19), дисперсия ошибки квантования: (2.22) Заметим, что

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

Другим, заслуживающим интерес критерием, является информационное содержание квантованного сигнала. Оно будет максимальным, если вероятности пребывания сигнала на всех уровнях будут равны, т.е.:

; отсюда ;

;

;

;

;

.

Нелинейное квантование нашло применение, в частности, в цифровой телефонной связи и позволяет качественно передавать как слабые, так и мощные сигналы, уменьшить загрузку каналов связи.

 

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

Закон распределения задается формулой:

.

 

1. Критерий минимума дисперсии:

,

.

После подстановки получаем:

.

Таким образом, оптимальной в случае квантования равномерно распределенного сигнала является равномерная шкала квантования.

2. Критерий максимальной информативности:

.

Таким образом, и в случае использование критерия максимальной информативности, оптимальной также является равномерная шкала квантования.

Кодирование информации

Общие понятия и определения. Цели кодирования

Код (франц. code), совокупность знаков (символов) и система определенных правил, при помощи которых информация может быть представлена… Рассмотрим обобщенную схему передачи цифровой информации (рис. 3.1).  

Элементы теории кодирования

Рассмотрим на примерах. Предположим, что дискретный источник без памяти, т.е. дающий независимые сообщения – буквы – на выходе, имеет алфавит из k… Каждая буква кодируется с использованием вторичного алфавита из m букв.… .

Неравенство Крафта

, (3.1) существует префиксный код с алфавитом объемом m, длины кодовых слов которого… Доказательство

Теорема об обобщении некоторых результатов, полученных для префиксных кодов, на все однозначно декодируемые коды

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

Теорема 2.

Доказательство. Пусть z – произвольное положительное число. Рассмотрим тождество:

Основная теорема кодирования для канала связи без шума (теорема 3)

Теорема 3.

. (3.3) Доказательство Докажем сначала левую часть неравенства (3.3), для чего перепишем его в виде: .

Теорема о минимальной средней длине кодового слова при поблочном кодировании (теорема 4)

Теорема 4. Формулировка. Для данного дискретного источника без памяти (с независимыми… .

Оптимальные неравномерные коды

Неравномерными называют коды, кодовые слова которых имеют различную длину. Оптимальность можно понимать по-разному, в зависимости от критерия. В данном… Дальнейшие выводы будем делать при следующих условиях:

Лемма 1. О существовании оптимального кода с одинаковой длиной кодовых слов двух наименее вероятных кодируемых букв

Пример: если существует кодовое слово xk = 0 1 1 0 0 0 1 0, то существует и кодовое слово xk-1 = 0 1 1 0 0 0 1 1 Доказательство.

Лемма 2. Об оптимальности префиксного кода нередуцированного ансамбля, если префиксный код редуцированного ансамбля оптимален

Доказательство Заметим, что нередуцированный код от редуцированного отличается только заменой… Для доказательства запишем выражения для средней длины кодовых слов редуцированного и нередуцированного кода.

Буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей;

Затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы;

Всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним 0;

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

Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.

Наибольший эффект сжатия получается в случае, когда вероятности букв представляют собой целочисленные отрицательные степени двойки. Среднее число… Таблица 3.4. Буквы Вероятности Ступени разбиения …  

Таблица 3.5

Буквы	Вероят-ности	Ступени разбиения	Кодовые комбинации
Z1	0,22
Z2	0,20
Z3	0,16
Z4	0,16
Z5	0,10
Z6	0,10
Z7	0,04
Z8	0,02

Следовательно, некоторая избыточность в последовательностях символов осталась. Из теоремы Шеннона следует, что эту избыточность также можно уменьшить, если перейти к кодированию достаточно большими блоками.

Рассмотрим сообщения, образованные с помощью алфавита, состоящего всего из двух букв Z₁ и Z₂, с вероятностями появления соответственно p(Z_i)=0,9 и р(Z₂) =0,1.

Поскольку вероятности не равны, то последовательность из таких букв будет обладать избыточностью. Однако при побуквенном кодировании никакого эффекта не получается.

Действительно, на передачу каждой буквы требуется символ либо 1, либо 0, в то время как энтропия равна 0,47.

При кодировании блоков, содержащих по две буквы, получим коды, показанные в табл. 3.6.

Таблица 3.6

Буквы	Вероятности	Ступени разбиения	кодовые комбинации
Z1 Z1	0,81
Z2 Z1	0,09
Z3 Z1	0,09
Z4 Z1	0,01

Так как буквы статистически не связаны, вероятности блоков определяются как произведение вероятностей составляющих букв.

Среднее число символов на блок получается равным 1,29; а на букву − 0,645.

Кодирование блоков, содержащих по три буквы, дает еще больший эффект. Соответствующий ансамбль и коды приведены в табл. 3.7.

Таблица 3.7.

Буквы	Вероят ности	Ступени разбиения	кодовые комбинации
Z1 Z1 Z1	0,729
Z2 Z1 Z1	0,081
Z1 Z2 Z1	0,081
Z2 Z2 Z1	0,081
Z1 Z1 Z2	0,009
Z2 Z1 Z2	0,009
Z1 Z2 Z2	0,009

Среднее число символов на блок равно 1,59; а на букву − 0,53; что всего на 12% больше энтропии. Теоретический минимум Н(Z) = 0,47 может быть достигнут при кодировании блоков, включающих бесконечное число букв: .

Следует подчеркнуть, что увеличение эффективности кодирования при укрупнении блоков, не связано с учетом все более далеких статистических связей, так как нами рассматривались алфавиты с некоррелированными буквами. Повышение эффективности определяется лишь тем, что набор вероятностей, получающийся при укрупнении блоков, можно делить на более близкие по суммарным вероятностям подгруппы.

Рассмотренная нами методика Шеннона—Фэно не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу.

Множество вероятностей, приведенных в таблице 3.5, можно было бы разбить иначе, например, так, как это показано в табл. 3.8.

Таблица 3.8.

Буквы	Вероятности	Ступени разбиения	кодовые комбинации
Z1	0,22
Z2	0,20
Z3	0,16
Z4	0,16
Z5	0,10
Z6	0,10
Z7	0,04
Z8	0,02

При этом среднее число символов на букву оказывается равным 2,80. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием m>2 неопределенность становится еще большей.

От указанного недостатка свободна методика Хаффмена. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

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

1. Коэффициент статистического сжатия Kcc:   Здесь k и m – объемы первичного и вторичного алфавитов. log2m учитывает объем вторичного алфавита. Для двоичных кодов…

Особенности эффективных кодов.

2. Вторая особенность связана с временными задержками в передаче информации, возникающими при использовании кодирования блоков букв первичного… 3. Третья особенность заключается в том, что, как оказывается, эффективные… 4. Если , то H=nсрlog2m. В этом случае энтропия, приходящаяся на 1 букву вторичного алфавита H1букву=log2m,…

Помехоустойчивое кодирование

Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных К. Шенноном и сформулированных им в виде основной теоремы… Здесь под скоростью передачи информации понимается количество информации,… Подробнее эти вопросы будут рассмотрены ниже в разделе Передача информации.

Классификация кодов

1. В зависимости от способности обнаруживать и исправлять ошибки, различают коды, обнаруживающие ошибки, и коды, исправляющие ошибки. Первые позволяют только обнаруживать, но не исправлять ошибки. Вторые – не только обнаруживать, но и исправлять большую или меньшую долю обнаруженных ошибок.

2. По форме внесения избыточности различают разделимые и неразделимые коды.

В разделимых кодах кодовые слова четко разделены на две части. Одна часть состоит из исходных (кодируемых) разрядов, а другая из дополнительных разрядов, благодаря которым собственно и обеспечивается возможность обнаружения и/или исправления ошибок.

Ясно, что эти дополнительные разряды создают в сообщении избыточность (вспомним, что предполагается нулевая избыточность исходного (кодируемого) сообщения).

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

3. В зависимости от способа образования дополнительных разрядов разделимые коды подразделяются на систематические и несистематические. В систематических кодах дополнительные разряды символы образуются с помощью различных линейных операций над информационными. Систематические коды - самая обширная и наиболее применяемая группа корректирующих кодов.

4. По способу кодирования различают блочные и непрерывные коды.

При блочном кодировании входное кодируемое сообщение разбивается на блоки фиксированной длины k. Этим блокам ставятся в соответствие кодовые слова длиной n (n>k).

При непрерывном кодировании каждый символ b выходной последовательности (закодированного сообщения) определяется рекуррентным соотношением, связывающим его с соответствующими символами a входной последовательности (кодируемого сообщения), например: ,

где: a – символы входной последовательности (кодируемого сообщения);

b – символы выходной последовательности (закодированного сообщения);

c_kj и s – константы, зависящие от кода;

i – номер символа входной последовательности (кодируемого сообщения);

j – номер символа в группе символов выходной последовательности (закодированного сообщения), создаваемой в результате поступления нового символа входной последовательности.

L – количество символов выходной последовательности, создаваемых в результате кодирования в ответ на поступления на вход кодера одного символа входной последовательности.

Следующим рисунком иллюстрируется кодирование непрерывным кодом:

 

Рис. 3.4. Образование непрерывного кода.

Таким образом, на каждый символ входной последовательности приходится L символов выходной.

Существуют и другие варианты формулы кодирования.

5. По способу описания выделяют алгебраические коды, т.е. коды, описываемые с помощью аппарата высшей алгебры.

6. В зависимости от длины кодового слова различают равномерные и неравномерные коды. Если длина кодовых слов постоянна, код равномерный. В противном случае – неравномерный.

7. Рассмотрим блочный равномерный код. Если произвольная линейная комбинация кодовых слов – также кодовое слово, такой код называется линейным.

Одни и тот же код может одновременно принадлежать нескольким классам, например, может существовать алгебраический разделимый неравномерный код.

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

1) двоичный симметричный канал (ДСМК); 2) двоичный стирающий канал (ДСТК). При передаче информации через ДСМК помеха способна с некоторой вероятностью Р превратить 0 в 1 или 1 в 0. Передачу…

Расчет вероятности искажения кодового слова в ДСМК

. Вероятность искажения одного символа (однократная ошибка):  

Общие принципы использования избыточности

Однако возможное число n-разрядных комбинаций равно 2n. Если из этого числа исключить все разрешенные кодовые слова, то останутся запрещенные… Кодер посылает в линию связи только разрешенные кодовые слова, однако под… Возможность исправления ошибки связана со свойством кода, называемого кодовым расстоянием.

Граница Хэмминга

Найдем связь между максимально возможной корректирующей способностью КСК, длиной n кодового слова и максимальным числом Q разрешенных кодовых слов в… В круг (шар) диаметром КСК поместится кодовых слов. Поскольку подмножества не пересекаются, то

Избыточность помехоустойчивых кодов

Различают абсолютную и относительную избыточность. Абсолютная избыточность Иабс равномерных помехоустойчивых кодов находится по… Иабс=n-k.

Математическое введение к алгебраическим кодам

В настоящее время наиболее изучены, многочисленны, исследованы и широко используются корректирующие коды, описываемые при помощи аппарата высшей алгебры. Поэтому, прежде чем приступить к рассмотрению конкретных корректирующих кодов ознакомимся с используемой при этом частью высшей алгебры.

Предметом высшей алгебры являются так называемые алгебраические системы, являющиеся совокупностью некоторых множеств и определенных на элементах этих множеств операций.

Под двухместной операцией здесь понимается однозначное сопоставление двум элементам множества с третьим по определенным правилам.

Под одноместной операцией понимается однозначное сопоставление одному элементу множества с другим по определенным правилам.

Обычно основные операции называются сложением (a+b=c) и умножением (ab=d), а обратные им вычитанием и делением, даже если этим операции производятся не над числами (например, над оттенками цветов или геометрическими фигурами) и не идентичны соответствующим арифметическим операциям. С точки зрения высшей алгебры элементарная школьная алгебра − одна из бесконечного множества других возможных алгебраических систем.

Свойства и наименования систем зависят от законов, которые в них определены.

Пусть S – множество некоторых элементов, а а и b - элементы, принадлежащие множеству S (последнее записывается в виде ).

В таблице 3.9 определены некоторые важные для нас законы (Элементы теории передачи дискретной информации. –М.:Связь, 1972):

Таблица 3.9.

Законы композиции	Операция
Сложение	Умножение
Обозн.	Формула	Обозн.	Формула
Замкнутость (если , то ).	А1	a+b=c	M1	ab=c
Ассоциативность	А2	(a+b)+c= a+(b+c)	M2	(ab)c=a(bc)
Коммутативность	А3	a+b=b+a	M3	ab=ba
Наличие нулевого для операции сложения и единичного для операции умножения элемента е.	А4	a+e=e+a=a	M4	ae=ea=a
Наличие для обратного элемента .	А5		M5
Дистрибутивность	D1	a(b=c) = ab=ac
D2	(b+c)a = ba+bc

Система, в которой определены две основные операции (сложение и умножение) и которая соответствует всем отмеченным в таблице свойствам, называется полем.

Система, в которой определены обе основные операции и выполняются законы А1−А5, М1, М2, D1 и D2, называется кольцом.

Если дополнительно в некотором кольце выполняется закон М3, то это кольцо – коммутативное.

Система, в которой задана лишь одна операция (сложение или умножение) и выполняются законы А1, А2, А4, А5 или М1, М2, М4, М5 называется группой.

Если в группе определена операция сложения, то такая группа называется аддитивной, если умножения, то мультипликативной.

Группа называется коммутативной или абелевой, если в ней выполняется закон коммутативности (А3 или М3) в зависимости от введенной операции.

Группы, имеющие конечное число элементов, называются конечными.

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

Предположим, что кодовые комбинации образуют множество S. Определим теперь операцию суммирования, обладающую свойствами А1, А2, А4, А5 и образуем таким образом группу. Операцию суммирования определим таким образом, чтобы удовлетворялось условие замкнутости А1. Следовательно, число разрядов при выполнении этой операции меняться не должно. Этому условию отвечает операция поразрядного сложения кодовых слов по модулю 2 (обозначается знаком ). Результатом такого сложения будет 1, если число единиц в разряде слагаемых четно, и 0 − если нечетно.

Пример:

1 0 1 1 1 0 1

0 1 1 1 1 0 1

0 0 0 1 1 1 0

1 1 0 1 1 1 0

Выбранная операция коммутативна, поэтому группа будет абелевой.

Нулевым элементом является комбинация, состоящая из одних нулей (это легко проверить).

Противоположным элементом является сама кодовая комбинация, а обратная операция – вычитание – тождественна основной операции суммирования.

Линейные коды

Определение: Линейными называют блоковые коды, дополнительные разряды которых образуются путем линейных операций над определенными информационными… Здесь используется понятие линейная операция. Линейной операцией называется операция над объектами, описываемая выражением: С0 + С1Х1 + С2Х2 + … , где Сi –…

Определение числа добавочных разрядов m.

. При этом можно получить плотноупакованный код, т.е. код с минимальной при… К задаваемым параметрам кода относятся: длина информационной последовательности k и корректирующая способность кода…

Построение образующей матрицы

Линейная независимость означает, что никакое из слов, входящих в подмножество линейно-независимых кодовых слов, нельзя получить путем суммирования… В то же время любое другое из разрешенных кодовых слов можно получить путем… Таким образом, построение кодовых комбинаций линейного кода связано с линейными операциями. Для выполнения таких…

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

||KC1*n|| = ||X1*k|| * ||OMk*n|| . Умножение выполняется по правилам матричного умножения:  

Порядок декодирования

Искажение можно описать с помощью следующей формулы: ||ПКС|| = ||KC|| + ||BO||, где ||BO|| − вектор ошибки – матрица-строка размерностью 1*n, с 1 в тех разрядах, в которых произошли…

Двоичные циклические коды

Циклическими называют линейные (n,k)-коды, обладающие следующим свойством: для любого кодового слова: ; существует другое кодовое слово:

Некоторые свойства циклических кодов

1. Циклический код, образующий полином которого содержит более одного слагаемого, обнаруживает все одиночные ошибки. Строго доказывать это не будем. Покажем это на примере простейшего образующего…  

Построение кода с заданной корректирующей способностью

1. По заданному размеру информационной составляющей кодового слова длиной k определяется количество m дополнительных (избыточных) разрядов,… 2. Рассматривая кодовые слова построенного (n,k)-кода как новую… В результате получаем новый (n1,k1)-код, способный также способный исправлять однократные ошибки.

Матричное описание циклических кодов

Вспомним, что KC(X) = gm(X)*И(Х) . Вспомним также на примере порядок умножения полиномов: gm(X) = 1 0 1 0 1 1

Выбор образующего полинома

Напомним, что сдвигу влево соответствует умножение кодового слова на Х с вычитанием, если в результате умножения получается полином порядка n, из… gi(X) = g(X)Хi – B(Xn+1), где коэффициент В=1, если степень g(X)*Xi < n

Виды каналов передачи информации

1. Механические, в которых для передачи информации используется перемещение каких-либо твердых, жидких или газообразных тел. В первом случае могут… 2. Акустические. Используют механические колебания звуковой и ультразвуковой… 3. Оптические. Используют оптические линии связи. Являются перспективными, т.к. обладают в настоящее время…

Разделение каналов связи

Свойства канала передачи информации сильно зависят от используемой линии передачи информации. По разным причинам этих линий не может быть много. Например, в радиоканале она всегда одна – «эфир». Поэтому приходится каким-то образом выделять сигналы разных каналов, использующих одну и ту же линию передачи информации. Различные способы такого выделения принято называть разделением каналов.

Частотное разделение

Весь спектр, пропускаемых линией связи частот делится на участки по количеству каналов. В каждом из каналов используются сигналы со спектром, лежащим в пределах своего участка. Через линию передачи информации передается сумма сигналов, каждый из которых имеет свой, не перекрывающийся с другими спектр. Это и позволяет на приемном конце выделить каждый из сигналов и воспринять переносимую им информацию. Для разделения сигналов используются так называемые полосовые фильтры.

 

Рис. 4.1. Схема системы передачи информации, основанной на частотном разделении каналов.

Так работает радио- и телевещание, когда одновременно одна радиолиния связи (эфир) одновременно используется тысячами радиостанциями для организации доставки информации миллионам жителей Земли (рис. 4.1).

Подобным же образом передача может вестись и по оптической линии передачи информации. Так по одному оптоволоконному кабелю одновременно может передаваться несколько миллионов телефонных разговоров, сотни телепрограмм и цифровых данных.

Временное разделение

При таком виде разделения сигналы от источников передаются только в отведенные для них непересекающиеся отрезки времени длительностью (рис. 4.2).

 

Рис. 4.2. Схема системы передачи информации, основанной на временном разделении каналов.

Такое использование линии связи в компьютерной технике называют режимом разделения времени.

Кодовое разделение

Кодовое разделение похоже на временное. Отличие заключается в способе управления коммутатором или все чаще коммутаторами (на пути от источника к приемнику может оказаться множество коммутаторов). Передаваемые данные содержат адрес приемника. На основании его специальные компьютеры − коммутаторы − направляют сообщение к нужному приемнику. Это наиболее распространенный в настоящее время способ разделения каналов.

Разделение по уровню

Предположим, что источники выдают сообщения, закодированные одноразрядным двоичным кодом. Эти сообщения можно использовать как разряды многоразрядного двоичного числа и подавать это число на вход цифроаналогового преобразователя. Сигнал с выхода этого преобразователя подается в линию связи для передачи на нужное расстояние. На приемном конце устанавливается аналого-цифровой преобразователь. На его выходе образуются сигналы, соответствующие передаваемым (рис. 4.3).

 

Рис. 4.3. Схема многоканальной системы передачи двоичной информации, основанной на разделении по уровню.

В таблице 4.1 приведен пример исходных данных для 4 источников И1-И4 двоичных данных, а справа те же данные в графический форме. Здесь Х – сигнал с выхода 4-хразрядного аналого-цифрового преобразователя (АЦП).

Рис.4.2. Графики сигналов на входе и выходе АЦП.

Таблица 4.1. № И1 И2 И3 И4 Х

.

 

Х и И1 −И4 связаны характерной для АЦП зависимостью:

Х = И1+2*И2+4*И3+8*И4.

Ясно, что разрядность АЦП и ЦАП совпадает с числом разделяемых каналов. При наличии помех она не должна быть слишком большой.

Для безошибочной передачи разделяемых по уровню каналов нужно чтобы помеха не превосходила половины минимального шага уровня напряжения на выходе АЦП.

 

Корреляционное разделение

В основу такого разделения положено использование системы ортогональных нормированных функций на интервале (0;Т).

В канал связи подается сумма: .

Информация с i-го канала здесь передается амплитудой сигнала а_i.

На приемном конце получают сигнал b_i:

,

так как .

За отрезок времени Т можно таким образом одновременно передать n величин a_i (1<=i<=n). Следующая порция n величин a_i передается за следующий отрезок времени длиной Т.

На рис. 4.3 изображена блок-схема системы корреляционного разделения каналов.

 

Рис. 4.3. Схема многоканальной системы передачи информации, основанной на корреляционном разделении каналов.

Видно, что эта схема во многом подобна схеме частотного разделения. Это не случайно. Действительно, здесь есть сходство. Частотное разделение основано на использовании одного из видов ортонормированных функций – набора синусоидальных функций. Но они образуют лишь одну из множества возможных систем ортонормированных функций. Существуют еще системы функций Радемахера, Хара, Уолша, Лежандра и другие, которые также можно использовать для разделения каналов и которые при определенных условиях обладают преимуществами по сравнению с остальными.

Комбинированные методы разделения

Комбинированные методы разделения каналов позволяют увеличить число каналов и уменьшить их взаимное влияние.

Можно, например, сочетать временное или кодовое разделение с частотным, амплитудным или корреляционным.

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

Пропускная способность каналов связи

Определения: 1. Скорость передачи информации – среднее количество информации, передаваемой… В случае канала без шума эта скорость равна Vк*Hк, где Vк – количество символов, передаваемых через канал в единицу…

Пропускная способность дискретного канала связи с шумом

Существует большое количество математических моделей таких каналов. Простейшей из них является канал с независимой от передаваемой информации… Если в канале без помех среднее количество информации, получаемой с выхода… Помехи нарушают взаимно-однозначное соответствие между символами на входе и выходе канала, что приводит к появлению на…

Типичные последовательности и их свойства

Последовательности, для которых выполняется равенство Ni=pi*n, называются типичными. Согласно закону больших чисел при росте n все большее число… Вероятность появления любой типичной последовательности вычисляется по одной и той же формуле:

Основная теорема Шеннона для дискретного канала с шумом

Для дискретного канала в шумом существует такой способ кодирования, при котором может быть обеспечена безошибочная передача все информации,… Vк max [ log2m – H(B/B’)] > Vи * H(A),(4.1) где H(A) – энтропия источника.

Обсуждение основной теоремы Шеннона для канала с шумом

Кроме того, анализируя выведенную выше формулу вероятности ошибки , приходим к выводу: чем выше запас по пропускной способности Ck-VиH(A) имеет канал связи, тем вероятность ошибки…

Пропускная способность непрерывного канала при наличии аддитивного шума

1. Канал способен пропускать колебания с частотами ниже Fm. 2. В канале действует помеха n(t), имеющая нормальный (гаусcовский) закон… 3. Помеха n(t) статистически не связана с полезным сигналом x(t).

Литература

1. Темников Ф. Е. и др. Теоретические основы информационной техники: Учеб. пособие для вузов. Ф. Е. Темников, В.А. Афонин, В.И. Дмитриев. – 2-е изд., перераб. и доп. –М.: Энергия, 1979. –512 с., ил.

2. Кузин Л. Т. Математические основы кибернетики. Том 1. Учеб. пособие. –М.: Энергия, 1973. –504 с.

3. Цымбал В.П. Теория информации и кодирования. −Киев: Вища школа; 1977. −288 с.

4. Кэтермоул К.В. Принципы импульсно-кодовой модуляции. −М.:Связь, 1974. −408 с.

5. Советов Б.Я. Теория ин формации. −Л.:Из-во ЛГУ, 1977. −184 с.

6. Яглом Л. М., Яглом И. М. Вероятность и информация. −М.:Наука, 1973. −512 с.

7. Шляпоберский В. И. Основы техники передачи дискретных сообщений. −М.: Связь, 1973. −480 с.

8. Липкин И. А. Основы статистической радиотехники, теории информации и кодирования. –М.:Советское радио. 1978. –240 с.

9. Галлагер Р. Теория информации и надежная связь. Пер с англ., под ред. М. С. Пинскера и Б. С. Цыбакова. –М.:Советское радио, 1974. −720 с.

10. Элементы теории передачи дискретной информации. Под ред. Л. П. Пуртова. −М.:Связь, 1972. −232 с.

Приложение 1. Таблица неприводимых полиномов

(По книге Темников Ф.Е. и др. Теоретические основы информационной техники. 3-е изд. –М.:Энергия, 1979. –512 с.)

№ п/п	Сте-пень	Полином	Двоичная последовательность
		Х+1
		х2+х+1
		Х3+Х+1
	Х3+Х2+1
		Х4+Х+1
	Х4+Х8+1
7	Х4+Х3+Х2+Х+1
		Х5+Х2+1
	Х5+Х3+1
	Х5+Х3+Х2+Х+1
	Х5+Х4+Х2+Х+1
	Х5+Х4+Х3+Х+1
	Х5+ Х4+Х3+Х2+l
		х6+X1+1
	X6+X3+1
	X6+х4+х2+х+1
	х6+х4+X3+х+1
	х6+х5+1
	х6+х5+х2+х+1
	х6+х5+х3+х2+1
	X6+х5+х4+х+1
	х6+х5+х4+х2+1
		х7+х+1
	х7+х3+1
	х7+х3+х2+х+1
	X7+Х4+1
	X7+х4+х3+х2+1
	X7+X5+X2+X+1
	х7+х5+х3+х+1
	X7+X5+X4+X3+1
	X7+X5+X4+X3+X2+X+1
	X7+X6+11
	X7+X6+X3+X+1
	х7+х6+х4+х+1
	X7+X6+X5+X4+X2+1
	X7+X6+X5 +X2+1
	X7+X6+X5+X3+X2+X+1
	X7+X6+X5+X4+1
	X7+X6+X5+X4+X2+X+1
	X7+X6+X5+X4+X3+X2+1
		х8+х4+X3+х + 1
	X8+X4+X3+X2+1
	х8+х8+х3+х+1
	X8+X5+X3+X2+1
	Х8+Х5+Х4+Х3+1
	Х8+Х5+ х4+х3+х2+х+1
	X8+X6 +X3+X2+1
	X8+X6+X4+X3+X2+X+1
	X8+X6+X5 +X+1
	X8+X6+X5 +X2+1
	X8+X6+X5+X3+1
	X8+X6+X5+X4+1
	X8+X6+X5+X4+X2+X+1
	X8+X6+X5+X4+X3+X+1
	X8+X7 +X2+X+1
	х8+х7+х3+х+1
	х8+х7+х3+х2+1
	X8+X7+X4+X3+X2+X+1
	X8+X7+X5+X+1
	X8+X7+X5+X3+1
	х8+х7+х5+х4+1
	х8+х7+х5+х4+х3+х2+1
	х8+х7+х6+х+1
	X8+X7+X6+X3+X2+X+1
	х8+х7+х6+х4+х2+х+1
	X8+X7+X6+X4+X3+X2+1
	X8+X7+X6+X5+X2+X+1
	X8+X7+X6+X5+X4+X+1
	X8+X7+X6+X5+X4+X2+1
	X8+X7+X6+X5+X4+X3+1
		х9+х+1
	X9+ X4+1
	X9+X4+X2+X+1
	X9+X4+X3+X+1
	Х9+Х5+1
	X9+X5+X3+X2+1
	X9+X5+X4+X+1
	X9+X6+X3+X+1
	X9+X6+X4+X3+1
	х9+х6+х4+х3+х2+X+1
	X9+X6+X5+X2+1
	X9+X6+X5+X3+1
	X9+X6+X5+X3+X2+X+1
	X9+X6+X5+X4+X2+X+1
	X9+X6+X5+X4+X3+Х2+1
	X9+X7+X2+X+1
	Х9+Х7+Х4+Х2+1
	х9+х7+х4+х3+1
	Х9+Х7+Х5+Х+1
	х9+х7+х5+х2+1
	х9+х7+х5+х3+х2+х+1
	х9+х7+X5+х4+х2+х+1
	х9+х7+х5+х4+х3+х2+1
	х9+х7+х6+ х3+х2+х+1
	X9+X7+X6+X4+1
	X9+X7+X6+X4+X3+X+1
	х9+х7+х6+х5+х4+х2+1
	х9+х7+х6+х5+х4+х3+1	101111100J
	х9+х8+1
	х9+х8+х4+х+1
	X9+X8+X4+X2+1
	X9+X8+X4+X3+X2+X+1
	х9+х8+х5+х+1
	X9+X8+X5+X4+1
	X9+X8+X5+X4+X3+X+1
	X9+X5+X6+X3+1
	Х9+х8+х6+Х3+х2+х+1
	X9+X8+X6+X4+X3+X+1
	х9+х8+х6+х5+1
	X9+X8+X6+X5+X3+X+1
	X9+X8+X6+X5+X3+Х2+1
	X9+X8+X6+X5+X4+X+1

 

Учебно-лабораторный практикум

Лабораторная работа 1: Исследование информативности источников дискретных сообщений.

 

 

Задание – сравнить текстовые сообщения, написанные на двух языках (выбираются в зависимости от варианта) по количеству информации, приходящейся на одну букву, используя меру Шеннона без учета статистической связи между буквами и с учетом этой связи между двумя соседними буквами.

Цель работы – приобретение навыков измерения количества информации, заключенной в дискретных сообщениях, с использованием меры Шеннона.

Теоретическое введение

К. Шеннон предложил измерять количество информации I в сообщениипо формуле:

I = Н _{априорная} – Н _{апостериорная} ,

где

Н _{априорная} – неопределенность знания истинного состояния объекта до получения сообщения, в котором это состояние описывается;

Н _{апостериорная}– неопределенность знания истинного состояния объекта после получения сообщения, в котором это состояние описывается.

Численно неопределенность состояния объекта, называемая также энтропией, рассчитывается по формуле Н = -log₂P , где Р – вероятность нахождения объекта в этом состоянии.

Если считать объектом полученный текст (что в реальности мало интересно, однако кардинально упрощает задачу), то неопределенность после его получения полностью снимается, т.е. апостериорная энтропия после получения текста = 0.

Следовательно, в этом случае количество информации (мера Шеннона) в полученном тексте I = Н _{априорная}

Если в качестве дискретных сообщения принять, как это определено в задании, тексты, написанные на разных языках, то степень информативности таких сообщений целесообразно измерять и сравнивать, измеряя среднее количество информации, приходящейся на одинаковый по длине отрезок текста, например на 1 букву текста.

Средняя энтропия, как известно из теории информации, рассчитывается по формуле:

, (1)

где Р_k – вероятность реализации k-го события в полной группе независимых событий, в которую всего входят m событий.

Эту формулу можно использовать для расчета средней энтропии, приходящейся на 1 букву текста, если считать их независимыми. Здесь m - объем (количество букв) используемого при написании текста алфавита. Конечно, предположение о независимости букв в тексте достаточной искусственно, поскольку интуитивно ясно, что на самом деле буквы в тексте взаимозависимы (мы ведь, как правило, можем восстановить утерянную или искаженную или утерянную букву в тексте, что свидетельствует об их взаимозависимости).

Более точно рассчитать среднюю неопределенность одной буквы сообщения можно, учитывая связи (зависимость) между двумя соседними буквами. Формула средней энтропии двухбуквенной комбинации в этом случае принимает следующий вид:

, (2)

где P(i,j) – вероятность появления в тексте комбинации из i-ой и j-ой букв алфавита.

Заметим, что количество слагаемых в формуле (2) возросло в квадрате (m²) по сравнению с количеством слагаемых в формуле (1) (m).

Конечно, и в этом случае расчет дает неточный, приблизительный результат, поскольку связи между буквы распространяются далее, чем на одну соседнюю букву. Однако дальнейшее увеличение точности, основанное на учете более дальних связей между буквами, резко увеличивает сложность расчетов из-за резкого (по экспоненциальному закону) роста количество слагаемых.

Поэтому в данной работе ограничимся только двумя вариантами – без учета связей между буквами и учетом связей только между соседними буквами. Для сравнения полученных результатов среднюю энтропию двухбуквенной комбинации для приведения к неопределенности, приходящейся на 1 букву, следует поделить на 2.

Оба расчета опираются на знание вероятностей: в первом случае – отдельных букв алфавита, во втором случае – всевозможных сочетаний из двух букв алфавита.

Согласно положениям теории вероятностей, эти вероятности можно найти только приближенно – путем подсчета частот появления букв и двухбуквенных комбинаций в реальных текстах и деления найденных частот на общее число букв и двухбуквенных комбинаций в исходном тексте. Результаты таких вычислений согласно закону больших чисел будут тем точнее, чем большие по объему тексты были взяты в качестве исходных.

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

Наиболее удобным источником разноязычных текстов в настоящее время является Интернет. Обработку текстов можно вести разными средствами. Это может быть какой-либо язык программирования или табличный процессор.

При подсчете частот появления отдельных букв текста или двухбуквенных комбинаций надо иметь в виду способы их кодирования. Во всех современных вариантах ОС Windows для кодирования символов используется кодовая таблица Unicode. В отличие от ранее доминировавшей кодовой таблицы ASCII , символы в которой кодировались 1-байтовым числом, сейчас символы в ОС Windows кодируются 2-байтовыми числами. Такая 2-байтовая кодировка позволяет различать 2¹⁶=65536 символов в отличие от 2⁸=256, различаемых в таблице ASCII. Таким образом, появилась возможность обрабатывать тексты, написанные на большинстве языков народов мира. Со временем проявились недостатки кодовой таблицы Unicode (Уникод). Предпринимаются усилия, направленные на их устранение. Это отражается в разработке новых усовершенствованных версий кодовой таблицы Unicode.

Сайт консорциума по разработке кодовой таблицы Unicode находится по адресу www.unicode.org. Согласно информации, опубликованной на этом сайте к осени 2008 года уже разработано 5 версий этой кодовой таблицы. На сайте в виде PDF-документов представлены участки кодовой таблицы, закрепленные за различными алфавитами с подробным описанием входящих в них символов.

Описание стандарта Unicode на русском языке можно найти по адресу http://allo.usaaa.ru/wdh/unicode.htm. С критикой Unicode можно ознакомиться по адресу http://cie.ase.md/~sereda/kod.htm#top

Ряд алфавитов отображаются также и при помощи модификаций однобайтовой кодовой таблицы ASCII. Различные программные средства, в том числе языки Visual Basic, тестовый процессор Excel могут работать с текстами так, как будто они закодированы при помощи этой однобайтовой кодовой таблицы. Надо думать, что этот искусственный прием предусмотрен как временная мера на период полного перехода от ASCII к Unicode. Поэтому с точки зрения перспективы рекомендуется обработку текстов выполнять средствами, работающими с кодовой таблицей Unicode.

Приводим примерный план выполнения данной лабораторной работы для случая применения для обработки текстов табличного процессора Excel. Это не значит, что выполнять работу нужно только так, как описано в этом плане. Наоборот, приветствуются и поощряются другие оригинальные способы исследования информативности заданных вариантом языков основанные на использовании статистической меры К. Шеннона.

Возможный план выполнения работы с использованием табличного процессора Excel

Шаг 1. Поиск в Интернете текстов с суммарным объемом от около 10 тысяч символов на каждом из двух языках согласно варианту задания.

Вообще, источник текстов может быть любым – газеты, книги, радио, телевидение и т.д. В настоящее время удобнее всего использовать Интернет, т.к. в этой сети можно найти тексты на практически любом языке и ввиду удобства его представления в электронной форме, готовой для компьютерной обработки.

Объем текста должен быть достаточным для расчета с достаточной точностью вероятностей появления в нем букв или других символов, составляющих письмо (например, иероглифов). Почему вероятностей? Потому, что именно на основе вероятностей на основе меры Шеннона находится количество информации в сообщении (см. формула 1 и 2). Из теории вероятностей (раздел математики) следует, что приближенно вероятность (оценку вероятности) какого-либо события можно вычислить, проведя множество экспериментов. Затем подсчитывается и количество случаев возникновения нужного события. Это количество делится на число проведенных экспериментов. В результате получается оценка вероятности возникновения нужного события. Эта оценка будет тем точнее, чем больше экспериментов будет проведено. Если пользоваться терминами нашей задачи, событиями являются факты появления нужной буквы в тексте, а экспериментами – появления букв текста. Число экспериментов – количество букв в тексте. Поэтому для увеличения точности расчета вероятностей появления отдельных букв (формула 1) и комбинаций из двух букв (формула 2) следует максимально увеличить длину текста. Однако возможности компьютеров небезграничны. Поэтому опытным путем была установлена верхняя граница количества букв – около 10000 букв.

Найденные в сети Интернет тексты через буфер промежуточного хранения передаются в текстовый процессор Word. По мере передачи текстов просматривается информация об объеме накопленного текста. Для этого выбирается меню Сервис ->Статистика (рис. 1).

 

Рис.1. Окно Статистика

После накопления нужного объема (около 10 тыс. символов без пробелов) для удобства дальнейшей обработки абзацы на экране целесообразно сузить приблизительно на 0,5 ширины страницы. Для этого можно, например, значительно увеличить правое поле страницы (рис. 2).

 

Рис. 2. Изменение размера правого поля.

Затем информация сохраняется в файле типа Обычный текст (*.txt). В процессе сохранения на экран выводится диалоговое окно Преобразование файла (рис. 3).

 

Рис. 3. Окно Преобразование файла

В этом окне нужно выбрать опции Другая, Уникод, Вставлять разрывы строк. Надо проверить также, что весь текст (прокрутить его сверху вниз) в нижней части окна не содержит символов, помеченных красным цветом. В противном случае следует подобрать другую кодировку. Окончательно текст сохраняется после нажатий кнопки ОК.

Шаг 2. Ввод текстовых файлов в Excel-таблицу с разбиением каждой строки текста на отдельные символы.

  Рис. 4. Окно Мастер текстов (импорт) – шаг 1. Здесь для размещения букв в отдельных клетках следует указать формат данных фиксированной длины и выбрать подходящий…

Шаг 4. Находим среднюю энтропию, приходящуюся на 1 букву сообщения.

Вероятности можно найти приближенно, исследуя частоты. Для получения по этим частотам приближенных значений (оценок) вероятностей… До расчета средней энтропии появления букв без учета статистических связей между ними нужно найти слагаемые в формуле…

Шаг 5. Находим абсолютную и относительную избыточности источника сообщений на заданных языках, сравнить эти языки по степени избыточности написанных на них текстов без учета и с учетом статистических связей между соседними буквами если размер алфавита языка позволил его произвести.

Согласно [1], различают 2 вида избыточности – абсолютную и относительную.

Абсолютная избыточность D_abs находится в виде разности между максимально возможной H_max и действительной энтропией H сообщения:

D_abs = H_max - H

Относительная избыточность D находится как отношение абсолютной избыточности D_abs к максимальной энтропии H_max:

 

Максимального значения энтропия достигает при равной вероятности всех букв сообщения.

Максимальная энтропия находится по формуле:

H_max = log₂m

Здесь m - количество учитываемых букв или двухбуквенных комбинаций.

Таблица с результатами вычисления должна содержать от 2 до 4 значений энтропий. Вам необходимо сравнить значения энтропий и по 2 значения избыточности для каждой энтропии. Нужно также по сведенным в таблицу данным сделать заключение о степени информативности исследованных языков, сравнивая их энтропии разных языков между собой и с учетом влияния статистической связи между буквами.

Шаг 6. Возьмем короткий отрезок текста на одном из заданных языков и найдем количество заключенной в нем информации

Поскольку речь идет о конкретном отрезке текста, его энтропия находится по формуле

Н = -log₂P, (4)

где Р – вероятность получения именно этого конкретного отрезка текста. Если не учитывать связи между буквами, то вероятность получения данного конкретного отрезка текста равна произведению вероятностей появления букв, из которых он состоит. Далее для расчета количества информации в этом тексте используют формулу 4.

Шаг 7. Проделаем те же операции с учетом зависимости двух соседних букв того же текста.

При учете статистической связи между буквами буквы текста разбиваются на пары. Вероятности появления этих пар перемножаются и полученное произведение опять же подставляется в формулу 4.

Шаг 8. Напишем отчет о выполненной работе с описанием всех вычислений и о том, как они выполнялись. Прокомментируйте результаты.

Результаты вычислений представьте в виде таблицы:       <Язык 1> <Язык 2> … По данным, внесенным в таблицу сделайте выводы – объясните характер изменения… Шаг 9. Сдайте или отослать по электронной почте (alexm5@fromru.com) отчет на проверку преподавателю.

Шаг 10. Защитите лабораторную работу у преподавателя.

Варианты задания

№ вар	Язык 1	Язык 2	№ вар	Язык 1	Язык 2
	Корейский	Финский		Голландский	Венгерский
	Сирийский	Русский		Венгерский	Бенгальский (Индия)
	Татарский	Латышский		Болгарский	Узбекский
	Калмыцкий	Тайский (Тайланд)		Эстонский	Болгарский
	Ирландский	Бенгальский (Индия)		Чешский	Китайский
	Эсперанто	Датский		Французский	Чешский
	Китайский	Голландский		Фломандский (Бельгия)	Чешский
	Грузинский	Корейский		Финский	Эстонский
	Хинди (Индия)	Русский		Украинский	Фломандский (Бельгия)
	Тамильский (Индия)	Норвежский		Турецкий	Французский
	Бенгальский (Индия)	Португальский		Словенский	Украинский
	Тайский (Тайланд)	Греческий		Словацкий	Арабский
	Кхмерский (Камбоджа)	Латышский		Сербский	Эсперанто
	Турецкий	Иврит (hibrew, Израиль)		Итальянский	Сербский
	Иврит (hibrew, Израиль)	Японский (айны)		Румынский	Финский
	Корейский	Польский		Португальский	Чешский
	Греческий	Норвежский		Польский	Сербский
	Японский (айны)	Венгерский		Норвежский	Финский
	Арабский	Норвежский		Немецкий	Датский
	Албанский	Испанский		Монгольский	Фломандский (Бельгия)
	Португальский	Болгарский		Македонский	Французский
	Норвежский	Вьетнамский		Литовский	Македонский
	Монгольский	Итальянский		Итальянский	Финский
	Македонский	Датский		Испанский	Французский
	Эсперанто	Болгарский		Голландский	Венгерский
	Литовский	Арабский		Болгарский	Немецкий
	Итальянский	Португальский		Африкаанс (ЮАР)	Шведский
	Испанский	Болгарский		Албанский	Голландский
	Датский	Венгерский		Чешский	Армянский

Результаты работы

В результате выполнения работы должен быть представлен doc-файл отчета и файлы с исходными данными и программами (возможно файл в формате Excel).

Сдача работы

Сдача работы преподавателю происходит в форме собеседования.

Вопросы для самопроверки

1) Дайте определение меры количества информации по Шеннону.

2) Напишите выражение энтропии источника независимых дискретных сообщений.

3) Как изменяется энтропия источника при учете зависимости между буквами, составляющих сообщение?

4) В каком случае количество информации, приходящееся на букву сообщения, и энтропия источника совпадают?

5) Как связаны энтропия сложного сообщения с энтропиями составляющих его сообщений в случае их статистической независимости?

6) В каком случае энтропия максимальна?

Литература

1. Мацканюк А.А. Теория информации и кодирования. Учебное пособие. СГУТКД,. 2003. -165 с. илл.

3. Темников Ф. Е. и др. Теоретические основы информационной техники. Учебн. пособие для вузов - 2-е изд., перераб. и доп. -М.:Энергия, 1979.-512с.

4. Кузин Л. Т. Основы кибернетики. Том 1. Математические основы кибернетики. Учебное пособие для втузов. -М.:Энергия, 1973. -504 с.

5. Цымбал В. П. Теория информации и кодирование. -Киев:Вища школа; 1977. -288 с.

 

Приложение 1: Пример оформления титульного листа

Министерство образования и науки РФ

Сочинский государственный университет туризма и курортного дела

Факультет информационных технологий и математики

Кафедра информационных технологий

 

 

Пояснительная записка

к лабораторной работе №1

по дисциплине

Теория информации и кодирования

Тема: Исследование источников дискретных сообщений.

 

 

Выполнена студентом

группы 08ПИ

Сидоровым Иваном Петровичем

“…….”………………2010

 

Сочи, 2010 г.

Приложение 2: Порядок создания нестандартных функций при использовании табличного процессора Excel

Введение

Не смотря на наличие в составе табличного процессора Excel обширного набора встроенных (стандартных) функций, при решении некоторых задач его бывает недостаточно. Примером может служить обработка текстов, написанных на восточных языках, когда необходимо обращаться к кодировке Unicode (двухбайтовая кодировка). Стандартные функции Excel расчитаны на обработку в стандарте ASCII (однобайтовая кодировка). Не смотря на то, что в памяти компьютера тексты хранятся в стандарте Unicode с помощью стандартных функций возможна их обработка так, как будто они хранятся в стандарте ASCII. С другой стороны работа в стандарте Unicode на уровне операционной системы возможна. Поэтому возникает необходимость создания собственных, нестандартных или, что то же самое, пользовательских функций, а иногда и дополнительных программ, использующих расширенные возможности.

Для этих целей в табличный процессор Excel, как впрочем и в другие составляющие пакета Microsoft Office, встроена система программирования на языке высокого уровня Visual Basic. Некоторых людей, причастных к программированию, но не знакомых со свойствами последних версий этого языка, следует наверно предостеречь от снисходительного к нему отношения. Версии системы программирования, основанные на Visual Basic не уступают, а во многих случаях превосходят по своим возможностям системы программирования на основе языков Object Pascal (Delphi) или C++. Несомненным преимуществом Visual Basic является его встроенность в основные приложения популярного пакета программ Microsoft Office, что делает его использование максимально доступным.

Подключение возможности использования нестандартных функций.

Слово Макрос – греческого происхождения. В переводе с греческого оно означает большой, длинный. В Кратком оксфордском словаре английского языка… Однако у всякой пользы есть своя теневая сторона. Возможностью применения… Для этого нужно выбрать пункты меню Сервис -> Параметры (рис. 15).

Создание нестандартной функции

  Рис. 17. Окно управления подключением макросов. Для того, чтобы иметь возможность и дальше пользоваться ранее созданными нестандартными функциями – макросами,…

Лабораторная работа 2. Исследование методов дискретизации непрерывных сообщений по времени

Цель работы -: Закрепление теоретических знаний и приобретение практических навыков применения методов дискретизации непрерывных сигналов по времени.

Теоретическое введение.

Теория дискретизации непрерывных сигналов по времени изложена в главе 2 учебного пособия по дисциплине Теория информации и кодирование [1].

В данной лабораторной работе предлагается экспериментально подтвердить:

1) высокую экономичность представления и точность восстановления исходного сигнала с помощью ряда Котельникова;

2) соответствие максимального значения ошибки восстановления расчетному при использовании для восстановления полиномов Лагранжа разных степеней.

В качестве квантуемого непрерывного сигнала берется звук вашего голоса, пропущенный через фильтр, ограничивающий спектр сигнала сверху. Современные операционные системы, в частности Windows, имеют в своем составе средства записи и воспроизведения звука. Необходимо только, чтобы компьютер был оснащен звуковой картой. Индивидуальность голоса обеспечивает различие получаемых результатов.

Для решения первой задачи используется теорема Найквиста-Котельникова, согласно которой для абсолютно точного восстановления непрерывного сигнала по отсчетам, взятым с постоянным шагом , нужно, чтобы этот шаг был взят в соответствии с неравенством: , где f_m – частота, выше которой спектр квантуемого сигнала равен 0.

Если шаг дискретизации отвечает этому условию, то согласно теореме Найквиста-Котельникова исходный сигнал x(t) можно восстановить при всех значениях времени (аргумента t) по формуле (ряд Котельникова):

(1)

Здесь:

x(t) – исходная дискретизируемая функция;

- отсчеты функции x(t), взятые в моменты времени

- круговая частота.

Проблема, однако, заключается в том, что, как доказано математически, поскольку все реальные сигналы конечны во времени, их спектры не ограничены по частоте. Следовательно, на самом деле для всех реальных сигналов . Поэтому в чистом виде теорему Найквиста-Котельникова применить невозможно. Тем не менее, ее используют, пренебрегая малыми значениями спектра. Это и предлагается сделать в этой работе. Платой за такое пренебрежение будет неточное выполнение равенства (1).

Решение второй задачиосновано на использовании формулы максимального значения ошибки (отклонения восстановленного значения функции от исходного):

(2)

Здесь - абсолютное значение ошибки;

n – порядок полиномов Лагранжа, используемых для восстановления исходной функции;

- максимальное значение абсолютной величины производной (n+1)–го порядка исходного сигнала x(t);

t – текущее время;

t_i – время взятия i-го отсчета.

Используя эту формулу, задавшись максимально допустимым значением ошибки восстановления исходной функции по периодически взятыми отсчетам, и порядком используемых в воспроизводящей функции полиномов Лагранжа, можно найти максимально возможный шаг квантования (чем шаг квантования больше, тем лучше, поскольку тем меньше приходится брать отсчетов).

В следующей ниже таблице приведены формулы расчета максимального шага дискретизации по времени в зависимости от порядка n полинома Лагранжа и максимально допустимого значения ошибки

n – порядок используемых для восстановления исходного процесса полиномов Лагранжа

Эти формулы и предлагается использовать в данной работе. Их вывод приводится в методическом пособии [1].

Последовательность выполнения практической части работы

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

В качестве дискретизируемого процесса в данной лабораторной работе берется сигнал, получаемый из голоса студента-исполнителя работы.

Практическая часть работы начинается с записи в память компьютера в цифровой форме голоса студента-исполнителя лабораторной работы. Студент должен будет произнести примерно следующий текст:

Лабораторная работа номер два по дисциплине Теория информации студента(тки) группы 08ПИ Иванова Петра Сидоровича (называются своя группа и ФИО).

В результате каждый студент получит свой индивидуальный вариант дискретизируемого сигнала.

Знакомство с программой Wavosaur для записи и обработки звука.

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

ОС Windows XP имеет в своем программу Звукозапись, которую можно использовать для записи голоса, однако в следующих версиях ОС (Vista, Windows 7) она заменена другой программой и, кроме того, ее возможности невелики. Поэтому в данной лабораторной работе предлагается использовать бесплатную программу Wavosaur, лучше подходящую для решения задач данной работы.

Программу устанавливать на компьютер не нужно. Ее файл Wavosaur.exe размером 556 кбайт находится в папке 2 второй лаб. работы в rar-архиве Wavosaur.rar. Распакуйте все файлы этого архива на свою флэшку и запустите файл программы Wavosaur.exe.

В результате на экране появится окно, изображенное на рис. 1.

 

Рис. 1. Окно программы Wavosaur

Подключите к компьютеру головную гарнитуру (головной телефон и микрофон, рис. 2, слева) и нажмите кнопку Monitor input with vu meter, указанную на рис. 2 справа синей стрелкой.

 

Рис. 2. Головная гарнитура и кнопка Monitor input with vu meter включения/выключения индикатор силы звука, фиксируемого микрофоном

Кнопкой Monitor input with vu meter включается/выключается индикатор силы звука, фиксируемого микрофоном. Этот индикатор имеет вид двух вертикальных полос, расположенных вдоль правой стороны окна программы Wavosaur (рис 3.).

Рис. 3. Включенный индикатор силы звука, фиксируемого микрофоном

После пуска программы полосы индикатора закрашены черным, но после нажатия кнопки Monitor input with vu meter нижняя часть индикатора закрашивается усиливающимся кверху зеленым цветом. Размер закрашенной части должен меняться пропорционально силе звука, фиксируемого микрофоном. Если этого не происходит нужно проверить подключение микрофона и настройки ОС Windоws.

Установите в настройках Windows максимальную чувствительность микрофона (рис. 4).

 

Рис. 4. Окна установки максимальной чувствительности микрофона, вызываемые через кнопку Пуск->Панель управления->Звуки и аудиоустройства->Запись звука->Громкость…

Запись голоса и подготовка сигнала.

  Рис. 5. Кнопка Record для запуска и прекращения записи Используя кнопку Record запишите в память компьютера фразу:

Импорт текстовых данных в Excel

  Рис. 23. Примерный вид данных Видно, что экспортированные данные представляют собой дробные числа со знаком точка, отделяющим целую часть числа от…

Результаты работы

В результате выполнения работы должен быть представлен архивный файл следующего содержания:

1. Wav-файл с записью голоса автора работы;

2. txt-файлы.

3. Еxcel-файл с расчетами;

4. Word-документ с титульным листом (см. образец титульного листа), теоретически обоснованным описанием хода выполнения работы, ее результатами и выводами.

Все файлы нужно упаковать при помощи архиватора WinZip или WinRar в один архивный файл и сдать преподавателю на проверку.

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

Защита заключается в обсуждении теории по теме работы и хода ее выполнения.

Литература

1. Мацканюк А. А. Теория информации и кодирования: Учеб. пособие для студентов вузов спец. 351400 «Прикладная информатика (по областям)». – Сочи: РИО СГУТиКД, 2003. – 198 с.: 51 рис., 11 табл. – библиогр: 13 назв.

2. Кэтермоул К. В. Принципы импульсно-кодовой модуляции. –М.:Связь, 1974. – 408 с.

3. Советов Б. Я. Теория информации. –Л.: Из-во ЛГУ, 1977. – 184 с.

Вопросы для самопроверки

1. Что понимается под дискретизацией непрерывного сигнала по времени? Какой вид представления (непрерывный, непрерывно-дискретный или дискретный) в итоге получается и почему?

2. Сформулируйте теорему Котельникова-Найквиста.

3. Расскажите о трудностях ее практического использования.

4. Как на результаты дискретизации влияет размер шага дискретизации?

5. Перечислите критерии точности восстановления исходного сигнала.

6. Опишите функции Лагранжа.

7. Опишите форму сигнала, восстановленного при помощи полиномов Лагранжа нулевого, первого и второго порядков.

8. Опишите связь размера шага квантования по времени с порядком полиномов Лагранжа и ошибкой восстановления исходной функции?

Иллюстрация к порядку вычисления ряда Найквиста-Котельникова

Рисунком П1 иллюстрируется тот факт, что для вычисления слагаемых ряда Найквиста-Котельникова функция отсчетов нужна в интервале значений аргумента от –k_max до k_max . В данной лабораторной работе k_max = 64, на рисунке k_max = 9.

Учтите, что графики на рис. П1 в Excel в варианте, описанном в данном методическом пособии, представлены столбцами чисел: x(t) столбцом А, слагаемое с k=0 – столбцом Z, слагаемое с k=1 – столбцом АА, …, слагаемое с k=64 – столбцом CL.

 

Рис. П1. Иллюстрация, поясняющая порядок вычисления ряда Найквиста-Котельникова

Лабораторная работа 3. Исследование оптимального квантования непрерывных сообщений по уровню.

Цель работы -: Закрепление теоретических знаний и приобретение практических навыков построения оптимальной шкалы квантования непрерывных сигналов по уровню.

Теоретическое введение.

Теория дискретизации непрерывных сигналов по времени изложена в главе 2 учебного пособия по дисциплине Теория информации и кодирование [1].

В данной лабораторной работе предлагается экспериментально подтвердить уменьшение дисперсии ошибки квантования по уровню при использовании оптимальной шкалы квантования.

В качестве квантуемого непрерывного сигнала берется звук вашего голоса. Программная поддержка работы со звуком имеется во всех современных операционных системах, в том числе и в Windows. Аппаратная же поддержка заключается в использовании звуковой карты или в наличии на материнской плате звукового чипа. Такими чипам сейчас оснащаются все новые материнские платы. Индивидуальность голоса обеспечивает различие получаемых результатов.

Квантование по уровню невозможно без наличия шкалы квантования. Шкала квантования представляет собой совокупность шагов квантования и соответствующих этим шагам уровней:

 

Здесь:

· вертикальная ось – ось значений квантуемого сигнала,

· горизонтальная ось – ось времени (на этом рисунке не изображена),

· х_max и х_min – максимальное и минимальное значения сигнала,

· штриховыми линиями показаны границы шагов квантования,

· δ_i размер i-го шага квантования,

· сплошными горизонтальными линиями показаны уровни квантования.

Квантование по уровню сводится к замене значения исходного сигнала уровнем того шага, в пределы которого это значение попадает.

В результате квантования восстановленный сигнал приобретает ступенчатую форму:   Можно использовать разные критерии точности представления исходного сигнала квантованным. В данной работе будем…

Возможный вариант выполнения работы

Используя программу Wavosaur запишите в память компьютера примерно следующую фразу:

Лабораторная работа номер 3 по дисциплине «Теория информации и кодирования» студента(тки) группы 07ПИ Иванова Петра Сидоровича (называются свои ФИО). Тема работы: «Исследование оптимального квантования непрерывных сообщений по уровню».

Преобразуйте стереосигнал в моно и нормализуйте его амплитуду. Измените частоту дискретизации с 44100 на 8000 герц. Фильтровать голосовой сигнал, как это было сделано во второй лабораторной работе, не следует. Спектр сигнала в этой работе нас не интересует.

Сохраните сигнал в текстовом формате в файле под своей фамилией и при помощи текстового процессора Word замените точки в дробных числах запятыми.

Откройте текстовый файл в Excel (файл будет прочитан не полностью). Данные введутся в столбец А. Для удобства последующихрасчетов увеличим масштаб сигнала путем умножения его на 500. Для этого ведите заголовки столбцов А и В и заполните формулы в столбец В (см. рис. 1 и 2).

 

Рис. 1. Данные. Рис. 2. Формулы.

Данные в столбце А находятся в интервале от -1 до +1. Умноженные на 500 (столбец В) - в интервале от -500 до +500.

Из теории следует, что для построения оптимальной шкалы нужно знать диференциальный закон распределения f(x) квантуемого по уровню сигнала. Этот закон используется при вычислении закона компандирования:

 

Согласно определению, точки f(x) дифференциального закона распределения равны:

,

где - вероятность попадания значения случайного процесса в интервал .

Практически, конечно, невозможно устремить к нулю, но можно выбрать достаточно малым. Таким образом можно вычислить с достаточной точностью значения дифференциального закона f(x). В нашем случае можно выбрать =1, что является достаточной малой величиной относительно сигнала, значения которого меняются в интервале от -500 до +500. Осталось найти вероятности попадания зачений сигнала в интервалы единичной ширины. Этот расчет можно выполнить при помощи инструмента Гистограмма табличного процессора Excel.

Исходные данные находятся в столбце В. Для использования инструмента Гистограмма нужны Карманыс единичными интервалами (рис. 3).

 

Рис. 3. Интервал Карманов.

Интервал карманов протягивается от -500 до +500.

Запустите инструмент Гистограмма и укажите в его окне положение исходных данных (столбец В) и интервала карманов в столбце К (рис. 4).

 

Рис. 4. Содержимое окна Гистограмма.

В результате создается новая страница с результатами работы инструмента Гистограма в столбцах А и В.

На этой странице будет выполнено много вычислений. Добавьте в ее верхнюю часть примерно 22 пустые строки и вставьте в освободившееся пространство формулу закона компандирования (рис. 5).

 

Рис. 5. Изображение нового листа

Замените имя Лист1 нового листа на Шкалы.

Для качественного квантования целесообразно отбросить несколько процентов очень больших и очень малых отсчетов. Для этого образуем в столбце С нарастающую сумму частот, отображаемых в столбце В. Кроме того, скопируйте содержимое столбца А в столбец D и введите заголовки так, как изображено на рис. 6.

 

Рис. 6. Столбцы С и D.

Теперь найдем х_min, отсекающее 2% самых малых значений сигнала и x_max, отсекающее 2% самых больших значений сигнала, а также размера шага квантования по уровню равномерной шкалы квантования при 100 шагах (рис.7).

 

 

Рис. 7. Формулы расчета х_min, x_max и размера шага квантования по уровню равномерной шкалы квантования.

 

Для удобства сместим часть данных столбцов А и В вверх так, чтобы данные столбца А измнялись от х_min до x_max. Для этого создадим вспомогательный столбец E и столбцы F и G со смещенными данными из столбцов А и В так, как показано на рис. 8 и 9.

 

Рис. 8. Столбцы E-G

 

Рис. 9. Формулы в столбцах E-G.

Формулы в столбцах С, E-G копируются до строки 1024.

Теперь можно приступить к вычислению точек диференциального закона распределения f(x) голосового сигнала x(t).

Выше уже сообщалось, что значения этого закона приближенно совпадают с отношением вероятности попадания значения сигнала в некий интервал к ширине этого интервала. Возьмем интервал шириной, равной единице. Тогда приближенное значение закона распределения станет равным вероятности попадания в единичный интервал.

Для нахождения вероятности делим количество попаданий значений сигнала в единичный интервал на общее количество отсчетов. Общее количество отсчетов, значения которых больше х_min и меньше x_max находим в клетке G1025 по формуле =сумм(G24:G1024).

В клетках столбца H находим вероятности – точки закона распределения f(x). По ним в столбце I вычисляем . Затем в столбце J - интеграл (рис. 10, 11).

 

Рис. 10. Вид столбцов H-J

 

Рис. 11. Формулы в столбцах H-J

Формулы в столбцах H-K следует копировать до строки с номером 24+(x_max - х_min).

Для расчета закона компандирования в клетке К21 подготовим вычисление , а затем по формуле

 

вычислим значения точек закона компандирования (рис. 12, 13).

 

Рис. 12.

 

 

Рис. 13. Формулы.

В столбец L скопируйте столбец F и постройте график закона компандирования (рис. 14).

 

Рис. 14. График закона компандирования

 

Далее строим равномерную и неравномерную оптимальную шкалы квантования (рис. 15, 16).

Изучите формулы. Необходимо понять их смысл! В случае неудачи – проконсультируйтесь у преподавателя.

 

Рис. 15. Результат построения шкал квантования.

 

Рис. 16. Формулы, используемые при построении равномерной и неравномерной шкал квантования.

Согласно теории начальные значения шкал должны равняться х_min, а конечные – x_max. Из-за особенностей работы функции ВПР конечное значение оптимальной шкалы окажется несколько меньше. Поэтому вам нужно принудительно приравнять конечное значение оптимальной шкалы x_max.

Теперь оптимальная неравномерная и неоптимальная равномерная шкалы квантования найдены. Используем их для квантования вашего голосового сигнала, рассчитаем дисперсии ошибки в случае квантования при помощи оптимальной неравномерной и неоптимальной равномерной шкал и сравним эти экспериментально найденные дисперсии с их теоретическими значениями.

Все эти вычисления будем делать на листе, названном по имени файла с записью голосового сигнала (в данном примере это лист Иванов П.С.). Перейдите на этот лист.

Сначала пометим строчки с отсчетами, выходящими за границы интервала (x_min, x_max). Для этого заполним столбец С так, как показано на рис. 17, 18.

 

Рис. 17. Значения.

 

 

Рис. 18. Формулы.

Теперь строчки со значениями голосового сигнала, попадающими в интервал (x_min,x_max), помечены значением ИСТИНА в клетке столбца С, а строчки со значениями голосового сигнала, не попадающими в этот интервал, значением ЛОЖЬ. Это сделано для того, чтобы исключить крайние значения голосового сигнала.

Теперь все готово для использования ранее найденных шкал для квантования голосового сигнала по уровню. Процес такого квантования и расчет ошибок представлены на рис. 19, 20 (столбцы D-G).

 

Рис. 19. Результаты применения шкал и расчет ошибок квантования

 

Рис. 20. Формулы квантования и расчета ошибок

Теперь следует рассчитать теоретические дисперсии ошибок квантования для двух видов шкал (равномерной неоптимальной и неравномерной оптимальной), рассчитать экспериментальные дисперсии ошибок квантования для тех же шкал и сравнить их между собой.

В описываемом примере это сделано на листе Шкалы (рис. 21, 22).

 

Рис. 21. Результаты расчета теоретических и экспериментальных дисперсий ошибки квантования при использовании равномерной и оптимальной шкал квантования.

 

Рис. 22. Расчетные формулы для дисперсий ошибки.

Видно хорошее – в пределах нескольких процентов – совпадение теории и практики. Если и в вашем варианте такое совпадение наблюдается – вы справились с заданием, с чем вас и поздравляю!

Результаты работы

На защиту работы должен быть представлены следующие файлы:

5. Wav-файл с записью голоса автора работы;

6. Еxcel-файл с расчетами;

7. Word-документ с титульным листом (см. приложение), теоретически обоснованным описанием хода выполнения работы, ее результатами и выводами.

Литература

1. Мацканюк А.А. Теория информации и кодирования: Учеб. пособие для студентов вузов спец. 351400 «Прикладная информатика (по областям)». –Сочи: РИО СГУТиКД, 2003. -198 с.: 51 рис., 11 табл. –Библиогр: 13 назв.

1. Кэтермоул К.В. Принципы импульсно-кодовой модуляции. -М.:Связь, 1974. -408 с.

2. Советов Б.Я. Теория информации. -Л.: Из-во ЛГУ, 1977. -184 с.

Вопросы для самопроверки

1. Чем задается шкала квантования по уровню?

2. По каким параметрам при построении оптимальной шкалы квантования выполняется оптимизация квантования?

3. Каким образом находится диапазон значений, в который случайная величина попадает с заданной вероятностью?

4. Какую информацию о квантуемом сигнале нужно иметь, чтобы построить оптимальную шкалу его квантования по уровню?

5. Объясните назначение закона компандирования.

6. Как используется формула, описывающая закон компандирования, при построении оптимальной шкалы квантования в данной работе?

7. Как при построении оптимальной шкалы квантования располагаются уровни квантования по отношению к границам интервалов квантования?

Лабораторная работа 4. Исследование оптимальных (в смысле минимальной средней длины кодового слова) кодов на примере кодов Шеннона-Фэно и Хаффмена.

Цель работы -: Закрепление теоретических знаний и приобретение практических навыков построения и использования эффективных (оптимальных) кодов на примере кодов Шеннона-Фэно и Хаффмена.

Теоретическое введение.

Обоснование и алгоритмы построения оптимальных кодов Хаффмена и Шеннона-Фэно изложены в п.п. 3.1 - 3.7 главы 3 учебного пособия по дисциплине Теория информации и кодирование [1].

В данной лабораторной работе предлагается на практике построить и использовать оптимальные коды Хаффмена и Шеннона-Фэно для кодирования и декодирования дискретных сообщений.

Коды Хаффмена

5) буквы первичного алфавита выписываются в основной столбец в порядке убывания вероятностей; 6) две последние буквы объединяются в одну вспомогательную букву, которой… 7) вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке…

Буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей;

Затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы;

Всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним 0;

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

Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.

Наибольший эффект сжатия получается в случае, когда вероятности букв представляют собой целочисленные отрицательные степени двойки. Среднее число… Таблица 3.4. Буквы Вероятности Ступени разбиения … В более общем случае для алфавита из восьми букв среднее число символов на букву будет меньше трех, но больше энтропии…

Таблица 3.5

Буквы	Вероят-ности	Ступени разбиения	Кодовые комбинации
Z1	0,22
Z2	0,20
Z3	0,16
Z4	0,16
Z5	0,10
Z6	0,10
Z7	0,04
Z8	0,02

Следовательно, некоторая избыточность в последовательностях символов осталась. Из теоремы Шеннона следует, что эту избыточность также можно уменьшить, если перейти к кодированию достаточно большими блоками.

Рассмотрим сообщения, образованные с помощью алфавита, состоящего всего из двух букв Z₁ и Z₂, с вероятностями появления соответственно p(Z_i)==0,9 и р(Z₂) =0,1.

Поскольку вероятности не равны, то последовательность из таких букв будет обладать избыточностью. Однако при побуквенном кодировании никакого эффекта не получается.

Действительно, на передачу каждой буквы требуется символ либо 1, либо 0, в то время как энтропия равна 0,47.

 

 

При кодировании блоков, содержащих по две буквы, получим коды, показанные в табл. 3.6.

Таблица 3.6

Буквы	Вероятности	Ступени разбиения	кодовые комбинации
Z1 Z1	0,81
Z2 Z1	0,09
Z3 Z1	0,09
Z4 Z1	0,01

Так как буквы статистически не связаны, вероятности блоков определяются как произведение вероятностей составляющих букв.

Среднее число символов на блок получается равным 1,29; а на букву − 0,645.

Кодирование блоков, содержащих по три буквы, дает еще больший эффект. Соответствующий ансамбль и коды приведены в табл. 3.7.

Таблица 3.7.

Буквы	Вероят ности	Ступени разбиения	кодовые комбинации
Z1 Z1 Z1	0,729
Z2 Z1 Z1	0,081
Z1 Z2 Z1	0,081
Z2 Z2 Z1	0,081
Z1 Z1 Z2	0,009
Z2 Z1 Z2	0,009
Z1 Z2 Z2	0,009

Среднее число символов на блок равно 1,59; а на букву − 0,53; что всего на 12% больше энтропии. Теоретический минимум Н(Z) = 0,47 может быть достигнут при кодировании блоков, включающих бесконечное число букв: .

Следует подчеркнуть, что увеличение эффективности кодирования при укрупнении блоков, не связано с учетом все более далеких статистических связей, так как нами рассматривались алфавиты с некоррелированными буквами. Повышение эффективности определяется лишь тем, что набор вероятностей, получающийся при укрупнении блоков, можно делить на более близкие по суммарным вероятностям подгруппы.

Рассмотренная нами методика Шеннона—Фэно не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу.

Множество вероятностей, приведенных в таблице 3.5, можно было бы разбить иначе, например, так, как это показано в табл. 3.8.

Таблица 3.8.

Буквы	Вероятности	Ступени разбиения	кодовые комбинации
Z1	0,22
Z2	0,20
Z3	0,16
Z4	0,16
Z5	0,10
Z6	0,10
Z7	0,04
Z8	0,02

При этом среднее число символов на букву оказывается равным 2,80. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием m>2 неопределенность становится еще большей.

От указанного недостатка свободна методика Хаффмена. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

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

3. Коэффициент статистического сжатия Kcc:   Здесь k и m – объемы первичного и вторичного алфавитов. log2m учитывает объем вторичного алфавита. Для двоичных кодов…

Особенности эффективных кодов.

1. Вторая особенность связана с временными задержками в передаче информации, возникающими при использовании кодирования блоков букв первичного… 2. Третья особенность заключается в том, что, как оказывается, эффективные… 3. Если , то H=nсрlog2m. В этом случае энтропия, приходящаяся на 1 букву вторичного алфавита H1букву=log2m,…

Выполнение работы

Запустите программу Эффективное кодирование. На экран будет выведено окно Форма 1. Регистрация (рис. 1):  

Результаты работы

На защиту работы должен быть представлены отчет, выполненный в виде Word-документа с титульным листом (см. приложение), теоретически обоснованным описанием хода выполнения работы и скриншотами (фотографиями с экрана). К отчету можно приложить Еxcel-файл с расчетами;

 

Литература

1. Мацканюк А.А. Теория информации и кодирования: Учеб. пособие для студентов вузов спец. 351400 «Прикладная информатика (по областям)». –Сочи: РИО СГУТиКД, 2003. -198 с.: 51 рис., 11 табл. –Библиогр: 13 назв.

3. Кэтермоул К.В. Принципы импульсно-кодовой модуляции. -М.:Связь, 1974. -408 с.

4. Советов Б.Я. Теория информации. -Л.: Из-во ЛГУ, 1977. -184 с.

5. Материалы из интернета, например ru.wikipedia.org.

Вопросы для самопроверки

8. В каком смысле понимается оптимальность эффективных кодов?

9. Какие коды называются префиксными?

10. Как отражается принадлежность кода к классу префиксных на виде его кодового дерева?

11. Являются ли коды Хаффмена и Шеннона-Фэно префиксными?

12. Сформулируйте основную теорему кодирования для каналов связи без шума.

13. В каких условия целесообразно использовать оптимальные (эффективные) коды?

14. Какими параметрами оценивается качество эффективных кодов и как каждый из них характеризует код?

15. Какие затруднения возникают при практическом использовании эффективных кодов?

Лабораторная работа 5. Исследование кодов, обнаруживающих и исправляющих ошибки на примере линейного кода, исправляющего однократные ошибки.

Цель работы: Закрепление теоретических знаний и приобретение практических навыков построения и использования кодов, обнаруживающих и исправляющих ошибки.

Теоретическое введение.

Алгоритм построения и использования линейного кода, обнаруживающего и исправляющего ошибки изложены в п.п. 3.8.9 главы 3 учебного пособия по дисциплине Теория информации и кодирование [1].

Упрощённый способ построения линейного кода

Существует большое количество кодов, обнаруживающих и корректирующих искажения (ошибки), возникающие в результате действия помех в канале связи.

Коррекция (исправление) ошибок – операция более сложная и не всегда нужная. Коррекция ошибок подразумевает сначала обнаружение ошибок. Коррекция не предполагает повторное обращение к источнику сообщения и осуществляется на основании свойств самого искаженного сообщения. Если же возможен повторный запрос сообщения выгоднее, поскольку требуется меньше ресурсов, запрашивать повторную передачу сообщения до тех пор, пока в нем не перестанут обнаруживаться искажения. В этом случае используются более простые коды только обнаруживающие, но не исправляющие ошибки. Такие коды используются при передаче информации в компьютерных сетях, т.е. при передаче информации на расстоянии.

Корректирующие коды распространены при передаче информации во времени, например при записи ее на носители с целью последующего хранения. Во время хранения информация может быть искажена, но повторное ее получение не всегда возможно.

В данной лабораторной работе рассматривается один из видов кода – блоковый код – код при использовании которого во время кодирования некоторому числу информационных (кодируемых) разрядов ставится соответствие блок символов вторичного алфавита, называемый кодовым словом.

Код рассматриваемый в данной работе относится также к классу разделимых. Это означает, что в кодовых словах этого коды можно выделить информационные и дополнительные разряды.

Еще важно отметить, что рассматриваемый код относится к классу линейных. Принадлежность кода к классу линейных означает, что все кодовые слова такого кода получаются в результате линейных операций над небольшим количеством особых кодовых слов, которые называются линейно-независимыми [1].

Ниже следует описание операций, которые выполняются чтобы построить и использовать линейный код.

4. Определение числа добавочных разрядов m.

Добавочные (дополнительные) разряды в кодовом слове присоединяются к информационным и служат для борьбы с искажениями кодовых слов, которые возникают вследстве действия помех.

Одновременно дополнительные разряды увеличивают длину кодового слова, что является платой за помехоустойчивость. Поэтому количество этих разрядок должно быть минимально необходимым, для обеспечения заданной помехоустойчивости.

Для определения числа добавочных разрядов можно воспользоваться формулой границы Хэмминга [1]:

.

При этом можно получить плотноупакованный код, т.е. код с минимальной при заданных параметрах кода длиной n кодового слова и, следовательно, избыточностью.

К задаваемым параметрам кода относятся: длина информационной последовательности k и корректирующая способность кода КСК[19].

При k информационных двоичных разрядах может передаваться 2^k кодовых слов. Если приравнять Q=2^k, то с учетом границы Хэмминга получаем: .

Если КСК=1, т.е. строится код, исправляющий максимум однократные ошибки, то ,

так как и .

С учетом последней формулы ищется (обычно путем простого переборв) наименьшее m при котором удовлетворяется это неравенство. Наименьшее потому, что при этом достигается наименьшая избыточность.

Пример: k=7, тогда путем простого перебора легко найти, что m=4.

Построение образующей матрицы

Линейная независимость означает, что никакое из слов, входящих в подмножество линейно-независимых кодовых слов, нельзя получить путем суммирования… В то же время любое другое из разрешенных кодовых слов можно получить путем… Таким образом, построение кодовых комбинаций линейного кода связано с линейными операциями. Для выполнения таких…

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

||KC1*n|| = ||X1*k|| * ||OMk*n|| . Умножение выполняется по правилам умножения матриц:  

Порядок декодирования

Искажение можно описать с помощью следующей формулы: ||ПКС|| = ||KC|| + ||BO||, где ||BO|| − вектор ошибки – матрица-строка размерностью 1*n, с единицами в тех разрядах, в которых произошли…

Выполнение работы

Запустите программу Помехоустойчивое кодирование. На экран будет выведено окно Форма 1. Регистрация (рис. 1):  

Результаты работы

На защиту работы должен быть представлены отчет, выполненный в виде Word-документа с титульным листом (см. приложение), теоретически обоснованным описанием хода выполнения работы и скриншотами (фотографиями с экрана). К отчету можно приложить Еxcel-файл с расчетами;

Литература

1. Мацканюк А.А. Теория информации и кодирования: Учеб. пособие для студентов вузов спец. 351400 «Прикладная информатика (по областям)». –Сочи: РИО СГУТиКД, 2003. -198 с.: 51 рис., 11 табл. –Библиогр: 13 назв.

2. Кэтермоул К.В. Принципы импульсно-кодовой модуляции. -М.:Связь, 1974. -408 с.

3. Советов Б.Я. Теория информации. -Л.: Из-во ЛГУ, 1977. -184 с.

4. Материалы из интернета, например ru.wikipedia.org.

Вопросы для самопроверки

1. Какие коды называются линейными?

2. По каким правилам выполняется суммирование кодовых слов?

3. Как связаны кодовое расстояние и корректирующая способность?

4. По какому признаку обнаруживается ошибка в кодовом слове?

5. Для чего предназначена и их каких частей состоит образующая матрица?

6. Каким образом выполняется кодирование с помощью образующей матрицы?

7. Как выполняется декодирование?

8. Какими свойствами и почему должна обладать матрица дополнительных разрядов (МДР)?

9. Как составляется и почему именно так составляется транспонированная проверочная матрица?

10. Сформулируйте основную теорему Шеннона для дискретного канала с шумом.

11. В каких случаях ошибка в кодом слове не обнаруживается и в каких исправляется неверно?

 

Всего 14 п.л.

[1] ЭНТРОПИЯ (от греч. entropia − поворот, превращение) (обычно обозначается S), функция состояния термодинамической системы, изменение которой dS в равновесном процессе равно отношению количества теплоты dQ, сообщенного системе или отведенного от нее, к термодинамической температуре Т системы. Неравновесные процессы в изолированной системе сопровождаются ростом энтропии, они приближают систему к состоянию равновесия, в котором S максимальна. Понятие «энтропии» введено в 1865 г. Клаузиусом. Статистическая физика рассматривает энтропию как меру вероятности пребывания системы в данном состоянии (принцип Больцмана). Понятием энтропии широко пользуются в физике, химии, биологии и теории информации (описание взято из сети Интернет - адрес http://mega.km.ru/bes_98/encyclop.asp?topicnumber=75073&search=%FD%ED%F2%F0%EE%EF%E8%FF#srch0)

[2] .

[3] Доказательство можно найти, например, в книге: Кузин Л.Т. Математические основы кибернетики. Учеб. пособие для втузов. М.: Энергия, 1973. 504 с., стр.260-262.

[4] Семантика (от греч. semantikos − обозначающий):

1) значения единиц языка;

2) то же, что семасиология, раздел языкознания, изучающий значение единиц языка, прежде всего слов;

3) Один из основных разделов семиотики. (www.km.ru).

[5] Мера впервые была предложена в 1953 г. Карнапом и Бар-Хиллелом.

^[6] Харкевич Александр Александрович (1904 − 1965). Специалист в области радиотехники, электроники, акустики и приборостроения. Член-корреспондент по отделению технических наук (радиотехника и электроника). Академик по отделению механики и процессов управления (механика и процессы управления).

[7] По монографии Кэтермоула Принципы импульсно-кодовой модуляции.

[8] По книге: Галлагер Р. Теория информации и надежная связь. США, 1968 г. Пер. с англ. –М.: Советское радио. 1974, 720 с.

[9] Лемма - вспомогательная теорема, необходимая для доказательства других теорем.

^[10] Постулат (от лат. postulatum − требование) − утверждение (суждение), принимаемое в рамках какой-либо научной теории за истинное, хотя и недоказуемое ее средствами, и поэтому играющее в ней роль аксиомы.

^[11] Редукция (от лат. reductio − возвращение, приведение обратно) − упрощение, сведение сложного к более простому, обозримому, понимаемому, более доступному для анализа или решения; уменьшение, ослабление чего-либо.

[12] Дэвид Хаффман (р. 9 августа 1925, Альянс, Огайо — 7 октября 1999, Санта Круз, Калифорния) — первопроходец в сфере информатики.

В 1952 году создал алгоритм префиксного кодирования с минимальной избыточностью (известный как алгоритм или код Хаффмана)

В 1999 году получил медаль Ричарда Хэмминга за исключительный вклад в Теорию информации

[13] Роберт Марио Фано, родился в 1917 году в Италии в Турине. Он поступил в туринский колледж School of Engineering, но в 1939 году эмигрировал в США. Здесь он продолжил обучение в Массачусетском технологическом институте (МИТ), получив степень бакалавра в 1941 году. После этого он проработал шесть лет в лаборатории Radiation Laborator МИТ, а в 1947 году защитил диссертацию на звание доктора. В период с 1950 по 1953 год он возглавлял группу изучения радиолокационных технологий в Лаборатории им. Линкольна, но в основном его работа была связана с МИТ. В начале 60-х он занимался разработкой компьютеров, работающих по принципу разделения времени. В 1963 году он возглавил проект MAC и оставался на этой должности до 1968 года. Интересы Фано не ограничивались информационными системами. Он опубликовал ряд статей по микроволновым системам, электромагнетизму, теории сетей, а также по вопросам обучения специалистов технологической сферы. Фано является действительным членом Американской академии искусств и науки и института Institute of Electrical and Electronics Engineers. В 1976 году Фано получил премию Клода Шеннона за вклад в развитие теории информации.

 

[14] Число разрядов в кодовой комбинации здесь и в дальнейшем обозначено через n для того, чтобы избежать расхождения с общепринятой терминологией в области эффективного и помехоустойчивого кодирования.

[15] Ряд Тэйлора для функции y(x) одной переменной х, непрерывной и имеющей все производные при x=a, имеет следующий вид:

[16] Формальное имя аргумента – имя указываемое в тексте процедуры. При вызове процедуры формальное имя заменяется фактическим.

[17] Дэвид Хаффман (р. 9 августа 1925, Альянс, Огайо — 7 октября 1999, Санта Круз, Калифорния) — первопроходец в сфере теории информации.

В 1952 году создал алгоритм префиксного кодирования с минимальной избыточностью (известный как алгоритм или код Хаффмана)

В 1999 году получил медаль Ричарда Хэмминга за исключительный вклад в Теорию информации

 

[18] Число разрядов в кодовой комбинации здесь и в дальнейшем обозначено через n для того, чтобы избежать расхождения с общепринятой терминологией в области эффективного и помехоустойчивого кодирования.

[19] КСК – корректирующая способность кода – максимальная кратность правильно исправляемых кодов ошибки.