Методичка по лабам (Лабораторные 101-104)

Посмотреть архив целиком

41



621.398

M 545




МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

_________________



МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

__________________________________


Ю.Н. Кушелев , Г.В. Рыженков, П.М. Сорокин, Н.В. Якушин










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


ЛАБОРАТОРНЫЕ РАБОТЫ № 101 – 104


Методическое пособие


по курсу

Передача информации”



для студентов, обучающихся по направлению

Информатика и вычислительная техника”

и по специальности

Вычислительные машины, комплексы, системы и сети”







621.398

M 545

УДК: 621.398.725.3 (076.5)


Москва Издательство МЭИ 2001

Утверждено учебным управлением МЭИ

Подготовлено на кафедре вычислительных машин, систем и сетей


Рецензент д-р техн. Наук, проф. А.Б. Фролов


Кушелев Ю.Н. , Рыженков Г.В., Сорокин П.М., Якушин Н.В.

Методы кодирования информации в каналах связи: лабораторные работы 101–104. – М.: Издательство МЭИ, 2001.– 41 с.

Цикл рабораторных работ включает четыре работы: построение и реализация эффективных кодов, построение и реализация групповых кодов, построение и реализация циклических кодов, построение и реализация рекуррентных кодов.

Для студентов специальности “Вычислительные машины, комплексы, системы и сети”, изучающих курс “Передача информации”.

­­­­­­­­­­­­­­­­­­­­­­––––––––––––––––––––––––––––––––––––––

Учебное издание


Кушелев Юрий Николаевич , Рыженков Геннадий Васильевич,

Сорокин Павел Михайлович, Якушин Николай Владимирович


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

ЛАБОРАТОРНЫЕ РАБОТЫ № 101 – 104

Методическое пособие


по курсу

Передача информации”


Редактор А.И. Евсеев

Редактор издательства


Темплан издания МЭИ 2001г., метод. Подписано к печати

Формат 60x84/16 физ. леч. л. 2,5

Тираж 300 Изд. # Заказ


Издательство МЭИ, 111250, Москва, ул. Красноказарменная, д.14


Московский энергетический институт, 2001


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


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


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


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 с вероятностями появления соответственно

Р11)=0,9 и Р22)=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, А3 - 111, А4 - 110, А5 - 100, А6-1011, А7 - 10101, А8 - 10100. При этом получим lср =2,80 символа на букву.











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

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

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

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

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


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


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


1.3. Описание программного обеспечения и технической

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


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





















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

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


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

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

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

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

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

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

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

После проверки работы кодера и декодера в отдельности проверим их совместную работу. В начале предлагается выбрать последовательность кодируемых букв. Это осуществляется с помощью клавиш управления курсором и . Ошибки исправляются через . Выбрав нужную последовательность, переведите курсор на <кодировать>. Схема кодера ра­ботает потактно. Причем процессы кодирования и передачи сигналов разделены, что позволяет четко проследить прохождение каждого сигнала по схеме. Переданные сигналы высвечиваются темно-зеленым цветом, полученные – ярко-зеленым. Номер такта отображается в правом верхнем углу. Закодированная последовательность вы­ходит из схемы в "перевернутом" виде (справа-налево). Для выполнения схемой сле­дующего такта нажмите любую клавишу.

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

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

регистр 3





















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

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


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

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


Случайные файлы

Файл
diplom.doc
32348.rtf
140755.doc
73406.rtf
10103.rtf