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

Введение

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

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

 

Лабораторная работа № 1

Кодирование источника

 

Цель работы

Научиться отображать данные в наиболее эффективной для передачи форме.

 

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

Для определения количества информации используется формула Хартли , где P(S) – вероятностное появление одного символа, а все символы равновероятны. Но в большинстве случаев информация зависит от вероятности и поэтому для уточнения этого определения необходимо использовать концепцию вероятности. Говорят, что информация – это уменьшение (снятие) неопределенности. Т.е. чем больше вероятность события, тем меньшее количество информации содержится в результате. Этот подход был использован Шенноном. Он определил неопределенность, как энтропию случайного события (величины) X, которое может иметь n возможных результатов (значений), получаемых в результате экспериментов с вероятностями , как .

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

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

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

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

Близко связанным понятием является эффективность кода (обозначается как ), которая определяется как и обычно выражается в процентах. Избыточность кода равна , и если код имеет эффективность 100%, то у него нет никакой избыточности. Для случая двоичного кода , так что можно упростить эти уравнения: избыточность = .

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

 

Кодирование Шеннона-Фано

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

 

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

Процесс кодирования Хаффмана выполняется следующим образом. Символы сообщения, которые нужно закодировать, перечисляются в порядке убывания вероятности (Т.е. символы с самой высокой вероятностью должны быть в верхней части этого списка). Если используется двоичный кодовый алфавит, то две ветви с самыми низкими вероятностями объединяются (со сложением их вероятностей), но перед этим одна из них маркируется как 0, а другая – как 1. Затем эти ветви вновь упорядочиваются по вероятности и процесс повторяется. Процесс продолжается до тех пор, пока не останется только одна ветвь. Затем считываются кодовые слова, причем чтение выполняется в обратном порядке от последнего элемента с добавлением в кодовое слово встречающихся по пути нулей и единиц.

Например, возьмем систему со следующими вероятностями: A 0,25; B 0,3; C 0,35; D 0,1. Ранжируем их. Самые маленькие вероятности у элементов А и D (0,25 и 0,1). Они объединяются в одну AD ветвь, ветвь А маркируется как 0, а ветвь D как 1, и выполняется новое упорядочивание по убыванию вероятности:

С – 0,35; AD – 0,35; B – 0,3.

Относительно упорядочивания компонента AD имеется свобода выбора: располагать его можно либо выше, либо ниже компонента C. В каждом случае будут получены разные, но эквивалентные коды.

Затем объединяются компоненты AD и B, причем AD помечается как 0, а B – как 1. Это приводит к следующему списку:

ADB – 0,65; C – 0,35.

в котором компонента ADB маркируется как 0, а С – как 1, что дает только одну ветвь, на этом процесс заканчивается.

Извлечение кодовых слов выполняется следующим образом (начиная с последнего столбца, в обратном порядке):

А: 0 – от ветви ADB (последний столбец), 0 – от ветви AD (средний столбец) и 0 – от ветви А (первый столбец), что дает первое кодовое слово: 000;

В: 0 – от ветви ADB, 1 – от ветви В (средний столбец), что дает второе кодовое слово: 01 и т.д.

Рис. 1 Пример построения кода Хаффмана

 

Чтобы использовать кодирование Хаффмана для кодовых алфавитов, состоящих из большего количества символов, нужно выполнить небольшую модификацию этапа группировки: вместо объединения двух самых маловероятных компонентов перед переходом к следующему этапу нужно объединять n таких компонентов, где n – число символов кодового алфавита. Эти символы следует использовать для нумерации последних ветвей дерева на различных этапах процесса построения кодов Хаффмана. Следовательно, на каждом этапе этого процесса удаляются (n-1) входов (элементов) списка. Поскольку, в конце концов, остается элемент помеченный как 1, то в предыдущем списке должно быть 1+(n-1) элементов, а в его предшественнике – 1+2(n-1) элементов и т.д.

 

Задания

1. Информационный источник без памяти генерирует 8 различных символов с вероятностями 1/2, 1/4, 1/8, 1/16, 1/32, 1/64, 1/128 и 1/128. Эти символы кодируются как 000, 001, 010, 011, 100, 101, 110 и 111 соответственно:

1.1. Определить, чему равна энтропия на символ данного источника;

1.2. Какова эффективность данного кода;

1.3. Построить код, используя алгоритм Шеннона-Фанно, и вычислить его эффективность;

1.4. Построить код, используя алгоритм Хаффмана, и вычислить его эффективность;

2. Постройте код для источника без памяти с шестью символами, используя трехзначный кодовый алфавит {0, 1, 2}. Пусть выборка вывода такого источника выглядит так: ACAAABEBCDAEABDCAEFAABDF. Определите эффективность этого кода. Сравните ее с эффективностью кода {A:00, B:01, C:02, D:10, E:11, F:12}.

3. Удаленные датчики могут иметь два состояния – SET (Установлен) и CLEAR (Сброшен). В среднем 99% датчиков находятся в состоянии CLEAR:

3.1. Используйте одноразрядный код: 0 – CLEAR, 1 – SET. Определите его эффективность.

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

3.3. Повторите процедуру предыдущего пункта для групп, состоящих из 3 символов.

 

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

1. Что такое энтропия?

2. Дайте определение источника информации?

3. Какие типы сжатия используются для кодирования источника?

4. Как выполняется процесс кодирования Хаффмана?

Лабораторная работа № 2