Построение и реализация эффективных кодов

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

ПОСТРОЕНИЕ И РЕАЛИЗАЦИЯ ЭФФЕКТИВНЫХ КОДОВ

Целью работы является усвоение принципов построения и технической реа­лиза­ции кодирующих и декодирующих устройств эффективных кодов.

1.1. Указания к построению кодов

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

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

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

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

Код строится следующим образом: буквы алфавита сообщений выписыва­ются в таблицу в порядке убывания вероятностей их встречаемости. Затем их разделяют на две группы так, чтобы суммы вероятностей встречаемости букв в каждой из групп были бы по воз­можности одинаковыми. Всем буквам верхней половины в качестве первого сим­вола записывается ­– 1, а всем нижним – 0. Каждая из полученных групп, в свою очередь, разбивается на две под­группы с одинаковыми суммарными веро­ятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе не останется по одной букве.

Все буквы будут закодированы различными последовательностями символов из “0” и ”1” так, что ни одна более длинная кодовая комбинация не будет начинаться с более короткой, соответствующей другой букве. Код, обладающий этим свойством, называется префиксным. Это позволяет вести запись текста без разделительных символов и обеспечивает однозначность декодирования.

Рассмотрим алфавит из 8 букв. Ясно, что при обычном (не учитывающем вероятностей встречаемости их в сообщениях) кодировании для представления каждой бу­квы требу­ется 3 символа (), где M – количество букв в алфавите.

Наибольший эффект "сжатия" получается в случае, когда вероятности встречаемости букв представляют собой целочисленные отрицательные степени двойки. Среднее число символов на букву в этом случае точно равно энтропии. В более общем слу­чае для алфавита из 8 букв среднее число символов на букву будет меньше трех, но больше энтропии алфавита H(M).

Для алфавита, приведенного в табл.1.1, энтропия H(M) равна 2.76, а среднее число символов на букву:

,

где li – количество символов для обозначения i-ой буквы.

Таблица 1.1

Буква	Вероятности	Кодовая ком­бинация	№ деления
A1 A2 A3 A4 A5 A6 A7 A8	0.22 0.20 0.16 0.16 0.10 0.10 0.04 0.02	11 101 100 01 001 0001 00001 00000	II III I IV V VI VII

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

Рассмотрим сообщения, образованные с помощью алфавита, состоящего всего из двух букв А1 и А2 с вероятностями появления соответственно

Р1 (А1)=0,9 и Р2(А2)=0,1.

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

Действительно, на передачу каждой буквы требуется символ либо 1, либо 0, в то время как энтропия равна 0,47. При кодировании блоками, вклю­чающими по две буквы, получим табл. 1.2. Так как буквы статистически не свя­заны, вероятности встречаемости бло­ков определяют как произведение вероятностей состав­ляющих их букв.

Таблица 1.2

Буква	Вероятности	Кодовая ком­би­нация	№ деления
А1А1 А1А2 А2А1 А2А2	0.81 0.09 0.09 0.01	1 01 001 000	I II III

Среднее число символов на блок получается равным 1.29, а на букву – 0.645.

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

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

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

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

Вероятности, приведенные в табл.1.1, можно было бы разбить иначе (табл. 1.3):

Таблица 1.3

Буква	Вероятности	Кодовая ком­бинация	№ разбиения
A1 A2 A3 A4 A5 A6 A7 A8	0.22 0.20 0.16 0.16 0.10 0.10 0.04 0.02	11 10 011 010 001 0001 00001 00000	II I IV III V VI VII

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

Буквы алфавита сообщений выписываются в первый столбец в порядке убывания вероятностей. Две последние вероятности объединяются в одну вспомога­тельную, которой приписывается суммарная вероятность. Вероятности букв, не участ­вующих в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние вероятности снова объе­диняются. Процесс продолжается до тех пор, пока не получим единственную вспо­могательную вероятность равную единице. Поясним методику на примере (табл. 1.4). Значения вероятностей примем те же, что и в табл. 1.1.

Для получения кодовой комбинации, соответствующей данной букве, необходимо проследить путь перехода ее вероятности по строкам и столбцам табл. 1.4. Для наглядности построим кодовое дерево. Из точки, соответствую­щей вероятно­сти 1, направим две ветви, причем ветви с большей вероят­ностью присвоим символ 1, а с меньшей – 0. Такое последовательное ветвление продолжим до тех пор, пока не дойдем до вероятности каждой буквы. Кодовое дерево для алфа­вита букв, рассматриваемого в нашем примере, приведено на рис. 1.1.

Таблица 1.4

Буква	Вероятности	Вспомогательные столбцы
A1 A2 A3 A4 A5 A6 A7 A8	0.22 0.20 0.16 0.16 0.10 0.10 0.04 0.02	1	2	3	4	5	6	7
0.22 0.20 0.16 0.16 0.10 0.10 0.06	0.22 0.20 0.16 0.16 0.16 0.10	0.26 0.22 0.10 0.16 0.16	0.32 0.26 0.22 0.20	0.42 0.32 0.26	0.58 0.42	1

Теперь, двигаясь по кодовому дереву от единицы через промежуточные вероятности к вероятностям каждой буквы, можно записать соответствующую ей кодовую комбинацию: А1 - 01, А2 - 00, А, А, А, А6-1011, А, АПри этом получим lср =2,80 символа на букву.

Рис. 1.1. Кодовое дерево

Отметим в заключение особенности систем эффективного кодирования.

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

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

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

1.2. Программные и технические средства реализации

Лабораторная работа выполняется на ПЭВМ, подключенных к локальной сети кафедры. При проведении занятий на кафедре ВМСС необходимо при по­мощи опре­деленных команд войти в кафедральную сеть. Затем запустить на выполнение про­грамм Effectcoding. exe и HUFFMAN. EXE. В HUFFMAN. EXE строится кодирующее устройство по методу Шеннона-Фено, потом – по ме­тоду Хаффмена, а наконец, строится дерево Хаффмена.

1.3. Описание сборки устройств для реализации эффективных кодов

Работу ре­ко­мендуется начать со сборки кодирующего устройства – кодера (рис.1.2).

Рис. 1.2. Пример схемы кодирующего устройства

Устройство включает схему получения моментов считывания очередной буквы (матричный шифратор 1 с регистром сдвига 1) и шифратор букв (матрич­ный шифратор 2 с регистром сдвига 2). Число горизонтальных шин шифраторов равно числу кодируемых букв, а число вертикальных шин в каждом из них равно числу символов в самой длинной комбинации исполь­зуемого кода. Схема рассчитана на использование алфавита из 6-8 букв (сооб­щений). Источник информации удовлетворяет требованиям идеального источ­ника по Хартли, т. е. в каждый данный момент он воз­буждает шину только од­ной буквы, выставляя на нее сигнал "1". В регистре 1 появля­ется сигнал "1" в разряде соответствующем длине кодовой комбинации буквы, что обеспечивается диодным переходом. В регистре 2 появляется код со­ответствующий букве, шина которой возбуждена. Что тоже обеспечивается соответ­ствующими диодными переходами с возбужденной шины на триггеры регистра 2. Сдвигающими импульсами код буквы последовательно выталкивается в канал связи, а единица "вы­толкнутая" из регистра 1 разрешает источнику выдать очередную букву.

При выполнении домашней подготовки студент должен построить эффектив­ный код, используя методики Шеннона-Фено и Хаффмена. В первой части лабо­раторной работы применяется кодирование по Шеннону - Фено. На экране представ­лена заготовка схемы кодера. Необходимо правильно расставить диоды шифраторов. Теку­щее соединение отображается красной пунктирной линией, которую можно переме­щать кнопками управления ←↑→↓. Фиксируется соединение кнопкой +. В случае ошибки снять соединения можно с помощью все той же кнопки. Переключение между схемами осуществляется на главной форме.

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

Сборка декодирующего устройства – декодера производится аналогично сборке кодера рис 1.3.

Информация поступает из канала связи в приемный регистр 3. Регистр 3 состоит из триггеров, количество которых на один больше, чем самая длинная кодовая комбинация одной из букв алфавита. В начальном состоянии в регистре 3 в триггере T6 записана “1”. Перемещаясь по регистру сдвигающими импульсами по мере приема информации из линии связи, она информирует о приеме очередной буквы. Когда кодовая комби­нация буквы разместится в регистре 3 полностью, в этот момент должна схема совпадения “И”, соответствующая принятой букве.

Для этого на все входы схемы "И" этой буквы должны быть поданы сигналы "1" через диоды, подключенные к триггерам регистра 3, состояния которых соответствуют кодовой комбинации принятой буквы. Если триггер находится в состоянии "1", то диод подключается к правому или единичному выходу, а если в состоянии "0", то к левому или нулевому вы­ходу. Срабатывание схемы "И" принятой буквы индицирует ее и через схему “ИЛИ” сбрасывает в ноль все разряды ре­гистра 3, кроме первого, в котором снова выставляется "1". После этого схема декодера готова к приему очередной буквы.

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

Схема кодера ра­ботает потактно. Причем процессы кодирования и передачи сигналов разделены, что позволяет четко проследить прохождение каждого сигнала по схеме. Закодированная последовательность вы­ходит из схемы в "перевернутом" виде (справа-налево).

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

Рис. 1.3. Пример декодирующего устройства

Во второй части лабораторной работы применяется кодирование по Хаф­фмену. Порядок действий аналогичен выполнению первой части лабораторной работы.

Заключительной частью лабораторной работы является построение дерева Хаффмена для кодирования небольшого текста с помощью программы HUFFMAN. EXE. Эта часть является чисто демонстрационной. В ней шаг за шагом рассматривается процесс кодирования и построения дерева Хаффмена.

В окно с надписью "Текст для кодирования" вводится подготовленный текст. Во всех случаях для продолжения работы нажимается F10, для возврата назад – F9, подсказка – F1. Рядом в окне показывается частота появления букв в тексте. Для удобства можно передвигаться по тексту и выбрав любую букву клавишей <ENTER>, наглядно посмотреть эту букву в тексте. Она будет выделена другим цве­том.

На следующем этапе строится дерево Хаффмена. Дерево расшифровывается следующим образом. Красный прямоугольник – узел дерева, соответствующий букве. В нижней половине прямоугольника выводится сама буква, а в верхней – количество вхожде­ний этой буквы в текст. Серые узлы дерева – узлы, которые получились в про­цессе свертки. Число внутри такого узла показывает общую сумму вхождений. Ка­ждому ребру дерева присваивается “0” или “1”. Чтобы определить код конкретной буквы, входящей в текст, необходимо пройти путь от начала дерева до этой буквы в его конце, накапливая символы (“0” или “1”) при перемещении по ребрам дерева.

1.4. Описание программы Effectcoding. exe

рис.1

На рис.1 представлен общий вид программы. Работа с ней состоит из 5 возможных этапов: 1 – Выборка размерности, 2 – Пример (автоматическое кодирование и запуск устройств по заданным пользователем буквам), 3 – Сборка схем, 4 – Генерация ошибки в сообщении при прохождении его через канал связи, 5 – Запуск модели кодер-канал связи-декодер.

рис.2

На рис.2 показан путь Меню→Файл – здесь: первые четыре опции – открытие и сохранение файлов, хранящих кодеры и декодеры соответственно. Пятая и шестая опции – сохранение картинок кодера и декодера, седьмая и восьмая – открытие и сохранение файлов с сообщениями.

рис.3

На рис.3 показан путь Меню→Вид – здесь: первые три опции скрывают/показывают соответствующие окна, четвёртая – сворачивает главное окно (если не хватает места на экране), пятая – меняет язык интерфейса (в случае отсутствия настроек русского).

Этап Выбора размерности.

рис.4

На рис.3 показано окно Проверки, вызываемое кнопкой Ввод букв. В данное окно можно вводить слова вашего сообщения, причём: 1) если ваше исходное слово 0010, то ввести следует 0100 (“обернуть”) – именно в таком виде ваше исходное слово должно кодироваться на схеме кодера и подаваться в канал связи; 2) синий цвет то, что данное слово не сохранено, красный – наоборот.

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

Этап Примера.

рис.5

Если хоть одна буква введена и сохранена в окне Проверки, то появляется возможность перейти на этап Примера, на котором в поле ввода можно записать любое из сохранённых в окне Проверки слов (на рис.5 – a1a2 {принимаются буквы A и a латинского алфавита}).

Если введённые слова доступны – цвет становится синим (в противном случае - красным) и можно запустить пример – либо автоматический, либо потактовый(рис.6).

рис.6

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

Перезагрузка процесса производится нажатием появившейся жёлтой точки (см. рис.6), либо переходом обратно на Этап Выбора размерности.

Этап Сборки схем.

рис.7

Сборка (рис.7) производится на этом этапе в ручную: либо на главной форме, либо на формах кодера или декодера (переключатель Местное управление) .

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

рис.8

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

Замечание: при проверке отмечаются регистры и триггеры, которых не хватает до правильной схемы (соответствующей введённым в окно Проверки словам), и не отмечаются те триггеры, что отмечены неверно.

Этап Генерации ошибки.

рис.9

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

Этап Запуск модели.

рис.10

рис.11

В поле ввода этого этапа(рис.10,рис.11) можно ввести либо последовательность из {A1,A2…}, либо из {0,1} – смешивать их нельзя. Необходимым условием возможности моделирования является в первом случае наличие полностью собранных слов кодера и декодера (полностью означает, что цифры напротив соответствующего слова кодера или декодера не должны содержать “?”) с теми номерами, которые были введены в поле ввода данного этапа (например, при вводе a1a3a6a7 – первое, третье, шестое и седьмое слова кодера и декодера, считая сверху вниз, не должны содержать “?”); во втором случае необходима лишь полная сборка хотя бы одного слова декодера.

рис.12

На рис.11 показан момент моделирования (управление им аналогично управлению Примером с той лишь разницей, что возможно управлять не с главной формы (переключатель Местное управление) – например, для того, чтобы, скрыв основную форму, увеличить пространство для визуальной среды модели кодер-канал связи-декодер(рис.12)). На кодере загораются слова, которые в данный момент кодируются и передаются в канал связи (со сдвигом по регистрам 1 и 2), на декодере с тактовой задержкой равной 6 тактам происходит распознавание сигнала/кода (со сдвигом по регистру 3) {использование в качестве слов не префиксных кодов приведёт к неверному декодированию}: красные штрихи у сумматоров означают соответствие сигнала с триггера и схемы, их отсутствие означает обратное; цветом выделяются сумматоры, в которых распознано слово, и триггеры, нашедшие хотя бы одно вышеуказанное соответствие.

ПРИМЕЧАНИЕ: предположим, имеются слова 000101 и 01111. Тогда кодировать необходимо последовательность (если смотреть на схеме кодера слева направо по регистру 2) 101000 и 11110. На декодере (регистр 3 слева направо) – 1010001 и 1111010. В окно Проверки следует ввести 101000 и 111010. При моделировании (если вводить последовательность из {0,1}) – 1000101 и 101111.

Примечание 2: учтите, программа плохо переносит “общение” с Microsoft Word!

Примечание 3: программа нестабильна.

Примечание 4: программу нельзя запустить дважды

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

ЗАДАНИЕ

Выполняется при домашней подготовке

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

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

3. Вычислить энтропию источника и среднюю длину комбинации полученного кода.

4. Подготовить небольшой текст на 150–200 букв для построения дерева кодирования демонстраци­онной программой.

Выполняется в лаборатории

1. Используя построенный код по методу Шеннона-Фено и Хаффмена пра­вильно расставить диоды в схемах кодирующего и декодирующего устройства.

2. Проверить работоспособность системы передачи.

3. Ввести текст для построения дерева кодирования.

4. Зарисовать таблицу и дерево Хаффмена.

5. Подсчитать выигрыш от записи текста эффективным кодом.

Требования к отчету

Отчет должен включать:

1. таблицу построения эффективного кода по методике Шеннона-Фено;

2. схемы шифратора и дешифратора для построенного кода;

3. таблицу и кодовое дерево, иллюстрирующие построение эффективного кода по методике Хаффмена.

4. Результаты расчетов энтропии источника и среднюю длину кода для буквы, отдельно для заданного Вами алфавита из 8 букв и текста.

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

1. Когда целесообразно использовать эффективное кодирование?

2. Каковы сложности в реализации систем передачи с применением эффективных кодов?

3. До какого предела может быть сокращена средняя длина кодовой комбинации?

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

5. Какой код называется префиксным?

6. Как учесть взаимосвязь букв в тексте? Что произойдет с энтропией, если учесть взаимосвязь букв?

ЛИТЕРАТУРА

1. Прикладная теория информации. – M.: Высш. шк., 1989. – 320 с. (С. 184–196).

2. , , Теоретические основы информационной техники. М.: Энергия, 1979.– 512с. (С. 119-131).