close

Вход

Забыли?

вход по аккаунту

?

D5

код для вставкиСкачать
Лабораторная работа № 2
ЭФФЕКТИВНЫЕ
КОДЫ
ЦЕЛЬ РАБОТЫ. Изучение основных понятий теории информации, информационных характеристик систем передачи сообщений и методов эффективного
статистического кодирования на примере эффективного кода Хафмена.
1. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ К ЛАБОРАТОРНОЙ
РАБОТЕ.
Для выполнения лабораторной работы студенты должны предварительно
изучить раздел 1 настоящего методического руководства и получить у преподавателя допуск к работе.
1.1
Информация, сообщение, кодирование, сигнал.
Под информацией понимают совокупность сведений о каких-либо сообщениях, явлениях или предметах, которые получает потребитель. Академия Наук
СССР рекомендовала следующее определение: информация - это сведения, являющиеся объектом хранения, передачи и преобразования. Информацию, представленную в форме, которая позволяет осуществлять ее преобразование с целью передачи, обработки и практического использования, называют сообщением.
Всякое сообщение является совокупностью сведений о состоянии какой-либо
материальной системы, которые передаются человеком (или устройством), наблюдающим эту систему, другому человеку, (или устройству), не имеющему возможностей получить эти сведения из непосредственных наблюдений. Наблюдаемая материальная система вместе с наблюдателем представляет собой источник
информации (корреспондент), а человек или устройство, которому предназначаются результаты наблюдения - получатель информации (абонент).
Источник информации может вырабатывать непрерывное или дискретное
сообщения. Передача сообщений на расстояние осуществляется с помощью какого-либо материального носителя (бумага, магнитная лента и т.п.) или физического процесса (звуковых или электромагнитных волн, тока и.т.п.).
Физический процесс, отображающий (несущий) передаваемое сообщение,
называется сигналом. Сигналы формируются путём изменения тех или иных параметров физического носителя по закону передаваемых сообщений. Этот процесс изменения параметров сигнала в соответствии с передаваемым сообщением
называется модуляцией и осуществляется в системах связи с помощью модулятора. Любое преобразование сообщения в определённый сигнал путём установления между ними однозначного соответствия называют в широком смысле кодированием. Кодирование может включать в себя процессы преобразования и дискретизации непрерывных сообщений (аналого - цифровое преобразование), модуляцию (манипуляцию в цифровых системах связи) и непосредственно кодирование в узком смысле слова. Обратная операция называется декодированием.
Рассмотрим передачу дискретных сообщений. Последовательный процесс
преобразования сообщения в кодирующем устройстве (кодере) может быть представлен структурной схемой, показанной на рис.2.1.
2
Источник дискретных сообщений в общем случае характеризуется ансамблем X = { x1,...,xi,...,xmi} сообщений, представляющих собой конечное число символов xi. Совокупность символов x1,...,xi,..., xmi называется алфавитом источника
сообщений, а число различных символов m i - является объёмом алфавита источника сообщений. Для полного описания источника сообщений необходимо задать вероятности появления символов p(x1),...,p(xi),...,p(xm), причём их сумма равна 1. В частном случае символами алфавита источника могут быть буквы. Наиболее часто повторяющаяся буква русского языка - "О". Её вероятность появления p(x) = 0.09 означает, что на 1000 букв русского текста приходится в среднем
90 букв "О". Наиболее редко встречающаяся в тексте - буква "Ф", для которой
p(x) = 0.002. Вероятность появления промежутка между словами в тексте (пробел) наибольшая и равна 0.175. Отметим, что по этой причине на клавиатуре пишущих машинок клавиша "пробел", которой наиболее часто пользуются, выполнена не в виде кнопки, как для других букв, а в виде протяжённой планки, размещаемой ниже всей клавиатуры.
Кодер источника, который иногда может и отсутствовать, служит для представления сообщений в более удобной для передачи и компактной форме без потери информации. Кодер источника имеет свой алфавит G = { gk }, k = 1,2,...,mk,
где mk - объём алфавита кодера источника. Например, русские буквы алфавита
источника могут в кодере источника перекодироваться в цифры десятичной системы счисления с символами (буквами) алфавита (0,1,2,. . ., 9) с объёмом m= 10,
или в двоичный код с алфавитом 0 и 1 и, следовательно, с объёмом алфавита
m = 2 (например первичный код МТК - 2, см. [2] ). С помощью кодера источника
возможно устранение избыточности источника сообщений путём применения эффективного статистического кодирования.
Кодер канала может иметь свой алфавит θ = { θs }, s = 1, 2, . . ., ms. С помощью кодера канала может вводиться избыточность при применении корректирующих кодов, в целях повышения помехозащищённости системы связи. Таким
образом, в процессе преобразования сообщения в сигнал операция кодирования
позволяет в итоге уменьшить влияние различных помех и искажений на передачу
сообщений.
Итак, в процессе кодирования сообщений могут выполняться следующие
операции:
- преобразование сообщений из одной формы в другую, например, непрерывных в дискретные (натуральное, первичное кодирование);
- устранение естественной избыточности источника сообщений (эффективное или статистическое кодирование);
- введение специально рассчитанной искусственной избыточности в сообщение (помехоустойчивое кодирование).
Соответствующие кодеры (рис. 2.1) можно построить либо для каждой из указанных выше операций отдельно, либо объединить их в единое устройство.
3
1.2
Информационные характеристики системы передачи сообщений.
Такие понятия теории информации, как количество информации, передаваемое по каналу связи, энтропия, избыточность, пропускная способность канала являются интегральными оценками эффективности системы связи. Теория
указывает потенциальные возможности системы связи, которые надо стремиться
реализовать на практике.
Мера количества информации.
Мера количества информации должна отражать сущность работы систем передачи сообщений и служит основой для сравнения их между собой. Для систем
связи в большинстве случаев не имеет значение конкретное содержание сообщений, их ценность, важность, истинность или ложность. Системы передачи информации можно уподобить почте, для которой важен только сам факт отправления
письма, а содержание пересылаемых писем никак не учитывается. Поэтому понятие количества информации, применяемое для характеристики технических систем, значительно беднее, чем используемое нами в повседневной жизни.
Тем не менее мера количества информации должна согласовываться с интуитивными представлениями о существенных сторонах сообщений. При этом разумно руководствоваться следующими соображениями:
1) чем длиннее сообщение, тем большее количество информации оно должно содержать;
2) количество информации в сообщении тем больше, чем больше число возможных сообщений;
3) количество информации должно обладать свойством аддитивности, т.е.
количество информации, содержащееся, например, в двух независимых сообщениях, должно равняться сумме количества информации, переносимой каждым
сообщением;
4) большее количество информации несут маловероятные сообщения (сенсации, которые трудно угадать).
Понятие количества информации прошло следующие этапы эволюции:
1. Сообщение состоит не из одного, а из многих символов (букв, знаков,
элементов). Число возможных элементов определяется объёмом m соответствующего алфавита (mi , mk , ms - i - источник, К - кодер, s - сигнал), а число
элементов в сообщении - n. При выборе первого элемента сообщения производится выбор из m возможных элементов. При выборе второго делается выбор из
того же числа m элементов, но число возможных комбинаций выбора двух элементов составляет уже m2
(при m = 2, например, "0" и "1", возможных комбинаций - 4: "00", "01", "10" и "11"). Если же сообщение содержит n элементов, то число различных сочетаний этих элементов равно:
(2.1)
N = mn .
Значение N определяет число возможных сообщений. Оно и может служить
мерой количества информации. Однако мера N не обладает свойством аддитивности. Действительно, количество информации в сообщении из n символов не
равно сумме количеств информации из n1 и n2 символов, так как
mn # mn1 + mn2 , если n1 + n2 = n .
2. Для удовлетворения условию аддитивности можно выбрать в качестве
меры количества информации не само число N, а некоторую его функцию J = f(N).
Р. Хартли в 1928 году предложил логарифмическую меру количества информации:
J = log(N) = nlog(m).
(2.2)
4
Эта мера обладает свойством аддитивности, а именно:
nlog(m) = n1log(m) + n2log(m), если n1 + n2 = n.
Основание логарифма в (2.2) не имеет существенного значения. Широко
пользуются логарифмом по основанию 2 (причём обозначение "2" опускается). В
этом случае количество информации измеряется в двоичных единицах (дв.ед.)
или битах. Однако мера (2.2) не удовлетворяет четвёртому интуитивному требованию, так как не учитывается зависимость количества информации, содержащейся в сообщении, от вероятности появления сообщения. В то же время эта вероятность характеризует неожиданность данного сообщения для получателя.
3. К. Шеннон учёл требуемую зависимость и предложил определять количество информации, содержащееся в сообщении xi (i = 1, 2, . . . , mi) и относящееся к
выбору данной буквы xi алфавита источника, в виде:
J(xi) = log [1/p(xi)] = -log[p(xi)] ,
(2.3)
где p(xi) - вероятность появления сообщения xi, причём сумма всех p(xi)=1.
Как следует из (2.3), количество информации, содержащееся в сообщении,
тем больше, чем меньше вероятность этого сообщения. Такая зависимость соответствует интуитивным представлениям об информации. Действительно, сообщения, ожидаемые с большей вероятностью, легко угадываются получателем, а достоверные сообщения, вероятность которых равна 1, вообще не содержат информации,так как всегда могут быть предсказаны точно (очевидно,если p(xi)=1, то
J(xi)=0). Наоборот, сообщения, являющиеся сенсациями, имеют малую вероятность появления и их трудно предсказать, поэтому они содержат больше информации.
Количество информации, определяемое (2.3), является случайной величиной, принимающей значение J(xi) с вероятностью p(xi) в зависимости от появления буквы xi в сообщении источника. Однако при передаче больших массивов
сообщений важно не количество информации в одном конкретном символе J(xi), а
количество информации, усреднённое по всем возможным сообщениям, содержащим n символов. Такой мерой количества информации является математическое ожидание (среднее значение) случайной величины J(xi), содержащей n символов (букв), усреднённое по всему ансамблю X:
mi
mi
i =1
i =1
J ( Χ ) = n∑ p( xi )J ( xi ) = − n∑ p( xi ) log p( xi ) .
(2.4)
Это соотношение носит название формулы Шеннона. Для равновероятных
сообщений (p(xi) = 1/mi) меры информации по Хартли (2.2) и по Шеннону (2.4)
совпадают:
m
J ( Χ ) = − n∑1 / m log( 1 / m ) = n log m .
i =1
Поэтому меру Шеннона (2.4) можно рассматривать как обобщение меры
Хартли на ансамбль сообщений с распределением вероятностей, отличающимся
от равномерного.
Энтропия источника дискретных сообщений.
Для характеристики источника сообщений более удобной величиной является средняя величина (математическое ожидание) количества информации, содержащегося в одном символе (букве) сообщения. Эта величина называется энтропией источника сообщений. В случае отсутствия статистической связи между
символами, энтропия источника равна:
5
m
H ( Χ ) = J ( Χ ) / n = −∑ p( xi ) log p( xi ) .
(2.5)
i =1
Понятие энтропии (от греческого "эн-тропе" - обращение) распространилось
на ряд областей знания. Энтропия характеризует неопределённость каждой ситуации. Энтропия в термодинамике определяет вероятность теплового состояния
вещества (закон Больцмана), в математике - степень неопределённости ситуации
или задачи, в теории информации она характеризует способность источника "отдавать" информацию. Приобретение информации сопровождается уменьшением
неопределённости, поэтому количество информации можно измерять количеством
исчезнувшей неопределённости, т.е. энтропией. Энтропию называют также информационной содержательностью сообщения.
Анализируя выражение (2.5), можно отметить некоторые свойства энтропии
дискретной случайной величины.
1. Энтропия источника является величиной вещественной и положительнойH(x) ≥0. Энтропия равна 0 в случае, когда отсутствует возможность выбора, т.е.
когда величина X может принимать только одно значение с вероятностью p(x) = 1.
В передаче такого сообщения нет смысла, поскольку результат заранее известен
получателю. Источники с малой энтропией не являются информативными. Они
выдают знаки, которые с большой вероятностью известны получателю. В этом
смысле энтропия источника характеризует его информационную ёмкость.
2. Энтропия случайной величины, имеющей всего два значения x1 и x2, не
превышает 1. При объёме алфавита источника mi=2 и одинаковой вероятности
сообщений p(x1)=p(x2)=0.5 энтропия достигает максимального значения Hmax(x)=
1 дв.ед. Следовательно, в качестве единицы измерения информации (дв.ед., бит)
взята информация, содержащаяся в одном из двух равновероятных сообщений.
3. Максимальная энтропия источника Hmax(x) достигается лишь в случае равных вероятностей выбора букв алфавита, т.е. когда p(xi) = 1/m, (i= 1,2,...,m), тогда:
m
H max ( x ) = −∑1 / m log( 1 / m ) = log m .
(2.6)
i =1
Такой источник называют идеальным (оптимальным), так как каждый его
символ несет максимальное количество информации. Для конкретизации этих
свойств энтропии приведем два примера.
Пример 1. Определить энтропию источника сообщений, если он может
выдавать m = 5 знаков с вероятностями p(x1) = 0.4; p(x2) = 0.1; p(x3) = 0.2;
p(x4) = 0.1; p(x5) = 0.3. (Сумма всех p(xi) = 1).
Решение:
m
H ( x ) = −∑ p( xi ) log 2 p( xi ) = − ( 0.4 log 2 0.4 + 0.1log 2 0.1 +
i =1
+ 0.2 log 2 0.2 + 0.1log 2 0.1 + 0.2 log 2 0.2 ) = 2.12бит / знак .
Пример 2. Решить предыдущий пример при условии одинаковой вероятности появления каждого из пяти знаков: p(xi) = 1/m = 0.2.
Решение:
m
H ( x ) = −∑ p( xi ) log 2 p( xi ) = −5 ∗ 0.2 log 2 0.2 = 2.32бит / знак .
i =1
Отметим, что это значение H(x) соответствует Hmax(x).
6
При наличии кодера источника, в свою очередь, представляющего каждую из
m букв алфавита источника кодовой группой из nk символов (разрядов), определяют удельную энтропию H1(x), приходящуюся на один разряд кодовой группы:
H( x )
H1( x ) =
,
(2.7)
nk
где nk - длина кодовой группы (слова), а в обозначении удельной энтропии H1(x)
индексом 1 подчеркивается, что энтропия отнесена к одному разряду кодовой
группы, а не к знаку источника сообщения.
Пример 3.
Определить максимальные значения энтропии Hmax(x),
H1max(x), H1(x) для первичного пятиразрядного (nК = 5) кода МТК-2 (см. [2]), если
известно, что с учётом неравновероятности появления m = 32 буквенных знаков
текста энтропия источника сообщений H(x) = 4.36 бит/знак.
Решение.
В соответствии с (2.6) и (2.7) Hmax(x) =log32 = 5 бит/знак;
H (x)
H 1 max ( x ) = max
= 5 / 5 = 1 бит / разряд;
H1(x)=4.36/5=0.87бит/разряд.
nk
Это означает, что кодер источника (рис.2.1) выдаёт разряды сообщения при
кодировании буквенного алфавита источника первичным кодом МТК-2 с "недогрузкой" в информационном смысле на 13% по сравнению с потенциальными
возможностями.
В теории информации доказывается, что энтропия источника зависимых сообщений всегда меньше энтропии источника независимых сообщений при том же
объёме алфавита и тех же безусловных вероятностях сообщений.
Если источник выдаёт последовательность букв из алфавита объёмом m =32
и буквы выбираются равновероятно и независимо друг от друга, то энтропия источника (2.6) Hmax(x)=logm =5 бит. Однако таким источником могла бы быть обезьяна, нажимающая в хаотическом порядке клавиши пишущей машинки (идеальный
источник!).
Если буквы передаются не хаотически, а составляют связный, например,
русский текст, то появление их неравновероятно (см. выше - вероятность появления буквы "О" в 45 раз больше, чем буквы "Ф"), и, главное, буквы в тексте зависимы. Так, после гласных не может появиться "Ь", мала вероятность сочетания более трёх согласных подряд, вероятность последовательности, не образующей осмысленных слов (идеальный источник), практически равна нулю. Расчёты показывают [5], что для текстов русской художественной прозы энтропия оказывается
менее 1.5 бит на букву. Еще меньше, около 1 бита на букву, энтропия поэтических
произведений, так как в них имеются дополнительные вероятностные связи, обусловленные ритмом и рифмами. Слово, рифмуемое с окончанием предыдущей
стихотворной строки, легко угадывается без произнесения или чтения его, и поэтому информации не несет (H(x) = 0). Энтропия телеграмм обычно не превышает
0.8 бит на букву, поскольку их тексты довольно однообразны (особенно поздравительных).
Количественно эта характеристика источника оценивается его избыточностью.
Избыточность источника сообщений.
Абсолютная избыточность источника определяется формулой
χa = Hmax(x) - H(x) .
(2.8)
Чаще используется понятие относительной избыточности, которую и называют избыточностью источника:
7
H max ( x) − H ( x)
H ( x)
= 1−
= 1 − µ,
(2.9)
H max ( x)
H max ( x)
где µ = H(x) / Hmax(x) - относительная энтропия.
Избыточность 0 ≤ χ ≤ 1 и учитывает как взаимосвязь (корреляцию) символов
в передаваемой последовательности, так и неопределённость каждого символа.
Она является важной характеристикой источника, так как указывает, насколько
можно сократить число символов и довести его до минимального nmin в последовательности данного источника, если то же количество информации будет передаваться последовательностью, составленной из равновероятных и независимых
символов, т.е. при H(x) = Hmax(x). Действительно, для данного (реального) источника количество информации, содержащееся в последовательности из n символов, равно (2.5) J = nH(x), а для идеального J=nmin*Hmax. Приравнивая
количества информации этих источников, получим
n
H ( x) / H max ( x) = min
или
избыточность
кода
источника
n
n − nmin
n
χ=
= 1 − min = 1 − µ ,
(2.10)
n
n
где отношение
µ=nmin /n получило название коэффициента сжатия, равного
относительной энтропии.
Таким образом, источник с избыточностью χ # 0 формирует последовательности сообщений, число n символов в которых больше минимально необходимого
nmin для передачи данного количества информации.
Установлено, что избыточность текстов на русском и английском языках χ ≅ 0.7,
т.е. объём книги и другой печатной продукции примерно в 3.3 раза больше, чем
это необходимо для отображения содержащейся в ней информации (при χ=0.7
значение nmin/n = 0.3 = 1/3.3).
Однако это не даёт повод утверждать, что такая избыточность бесполезна.
Избыточность текста обеспечивает высокую достоверность передачи информации, позволяет легко находить опечатки и исправлять ошибки. В частности, получатель телеграммы догадывается о её подлинном содержании даже при нескольких ошибочно переданных буквах. Отметим, что именно необходимость разговаривать при воздействии акустических помех явилась причиной того, что все национальные языки в процессе своего возникновения и развития оказались избыточными, и значение избыточности для всех языков близко к χ = 0.7 - 0.9 [ 5].
В технических приложениях естественную избыточность источников трудно
использовать для повышения помехоустойчивости систем связи. Лишние символы в последовательности сообщений часто нежелательны, так как увеличивают
время передачи информации, а при её хранении требуют дополнительной памяти
в запоминающих устройствах. Вопросам устранения избыточности сообщений
уделяется большое внимание и с этой целью осуществляют статистическое (эффективное) кодирование дискретных сообщений, в частности, применяют коды
Шеннона - Фано и Хафмена.
Отметим, что для повышения помехозащищенности канала связи целесообразно вводить избыточность снова, что делается при помехоустойчивом кодировании.
χ=
Производительность источника.
Производительность источника H'(x) есть среднее количество информации,
создаваемое источником в единицу времени:
8
H ′( X ) = lim
H( X T )
,
T
(2.11)
T →∞
где H(XT) - энтропия случайной последовательности, заданной на интервале T.
При наличии кодера источника, с учётом определения удельной энтропии
(2.7), выражение (2.11) преобразуется к виду:
H (X )
H ′( X ) = 1
= Vx H 1 ( X ) ,
(2.12)
τx
где τх - средняя длительность одного символа (разряда) кодового слова,
Vx = 1/τx - скорость формирования символов кодером источника.
Из (2.12) следует весьма важный вывод о том, что источник может генерировать сообщения с большой скоростью, но, тем не менее, его производительность с
информационной точки зрения будет чрезвычайно низкой, если H1(X) << 1. Причиной этого является избыточность источника.
Различие понятий производительности и скорости формирования символов
объясняется тем, что количество информации характеризует не сам факт появления сообщения, а определённое его свойство - степень его неожиданности, нетривиальность выбора этого сообщения из множества других.
Призводительностью источника можно управлять, изменяя длительность
символов τx. Поэтому различают неуправляемые и управляемые источники. Для
неуправляемых источников производительность - постоянная величина. Так, телеметрические датчики обычно выдают информацию с постоянной скоростью и
могут служить примером неуправляемых источников с фиксированной скоростью
создания сообщений. Для управляемых источников формирование символов сообщений происходит по внешним командам и, следовательно, длительность символа может изменяться. Например, чтение чисел из запоминающего устройства
осуществляется импульсами, интервал между которыми определяется возможностями и быстродействием периферийных устройств. Очевидно, что производительность управляемого источника может меняться в широких пределах.
Производительность источника является основной характеристикой при решении задач согласования источника с каналом связи.
1.3 Эффективное кодирование дискретных сообщений.
Цели эффективного кодирования
Основной целью эффективного (статистического) кодирования является преобразование сообщения в сигнал с меньшей, чем у сообщения, избыточностью (в
пределе - без избыточности). Сигналы без избыточности имеют максимальную
удельную энтропию. Для передачи информации с помощью таких сигналов требуется минимальное количество символов. Поэтому такие коды называют эффективными, а также экономными и оптимальными. В результате эффективного кодирования скорость передачи информации по дискретному каналу связи может быть
приближена к его пропускной способности. В этом случае говорят о согласовании
источника с каналом.
Скорость передачи информации и пропускная способность
дискретного канала без помех.
Вопросы статистического кодирования сообщений рассмотрим в предположении, что передача ведётся по каналу связи в отсутствии помех. В этом случае
9
принятый за время T сигнал YT совпадает с переданным ST, равны их энтропии
H(ST) = H(YT) и скорость передачи информации
H ( ST ) H1( S )
R = lim
,
=
(2.13)
T
τ
T →∞
где H1(S) - удельная энтропия сигнала; τ - длительность символов сигналов неуправляемого источника (τ = const).
и
При однозначном преобразовании сообщения в сигнал H(XT) = H(ST)
скорость передачи может быть выражена через удельную энтропию H1(X) сообщения:
H ( ST )
H ( X T ) H1( X )
= lim
=
= H ′( X ) ,
R = lim
(2.14)
τ
T
T
T →∞
T →∞
т.е. скорость равняется производительности источника - (2.12).
Пропускная способность канала C, характеризующая его потенциальные
возможности, определяется как верхняя граница (или максимум) скорости передачи информации R. Для дискретного канала без помех максимальное значение
скорости достигается при равновероятных и независимых символах сигнала (2.6):
H ( S ) H 1 ( S )max log m S
C = max R = max 1
=
=
,
(2.15)
p( x )
τ
τ
τ
где ms - алфавит кодера канала (сигнала).
В частности, для двоичного канала ms = 2 и C = 1/τ численно совпадает со
скоростью манипуляции символов в канале [2]. Полное согласование источника с
каналом достигается при R / C = 1, а качество согласования определяется отношением:
R H1( S )
=
=1 − χ S ,
(2.16)
C log m S
где χs = 1 - H1(S) / log ms - избыточность сигнала по аналогии с ( 9).
При заданном канале отношение R/C полностью определяется избыточностью сигнала и его удельной энтропией H1(S).
Чтобы R / C → 1, следует выбирать такой способ кодирования сообщений
источника, при котором H1(S) → log ms, т.е. в результате кодирования должна получаться последовательность, составленная из равновероятных и независимых
символов.
Основная теорема кодирования.
Вопрос о возможности передачи информации со скоростью, равной пропускной способности канала без помех, решается положительно при применении безизбыточного кодирования (см. (2.16) - при χs = 0). Это утверждение доказывается
одной из основных теорем теории информации, которая называется теоремой кодирования для источника. Поскольку при этом предполагается, что последовательность кодовых символов принимается без ошибок, то эту теорему называют
также теоремой кодирования для канала без помех.
Одна из возможных формулировок этой теоремы следующая.
Если производительность источника H'(X) = C - ε, где С - пропускная способность
канала связи, а ε > 0 - сколь угодно малая величина, то существует способ кодирования, обеспечивающий передачу всех сообщений, вырабатываемых источником, со скоростью R = H'(X) = C - ε. Если H'(X) > C, то длительная передача всех
10
сообщений невозможна. Доказательство этой теоремы можно найти в [3]. Другая
формулировка этой теоремы приведена в [1].
Избыточность источника возникает за счёт:
- неравной вероятности набора символов, составляющих алфавит источника;
- зависимости выбора последующего символа от предыдущего (так, в связном
русском тексте после гласных не может появиться "ъ", мала вероятность сочетания более трёх согласных подряд и т.п.).
Устранение избыточности достигается следующим образом.
1-й этап - применяется укрупнение алфавита источника для устранения статистической связи между соседними символами (кодируются не отдельные буквы,
а целые слова текста), при этом уменьшается неравновероятность букв укрупнённого алфавита.
2-й этап - при последующем кодировании используются неравномерные коды; при этом наиболее вероятные буквы ранее укрупнённого алфавита источника
передаются меньшим количеством символов.
Теорема кодирования является теоремой существования, т.е. она доказывает, что оптимальные (эффективные) коды существуют, но не даёт указаний о том,
как построить такие коды.
В настоящее время разработано большое количество эвристических приёмов, позволяющих осуществить статистическое кодирование и найти код, близкий
к оптимальному. Однако основные свойства и особенности, которыми должны обладать такие эффективные коды, следуют из теоремы кодирования.
1. Для обеспечения минимальной средней длины кодового слова избыточность должна быть сведена к минимуму (желательно к нулю). Для этого эффективный код должен состоять из кодовых слов, в которых все символы равновероятны и статистически независимы. Это позволяет уравнять скорость передачи с
пропускной способностью канала связи, что и является целью безизбыточного кодирования.
2. Ни одна из кодовых комбинаций не должна получаться из другой, более
короткой, путём добавления новых символов. Эффективные коды не требуют разделительных символов (маркеров) и при этом должно выполняться их однозначное декодирование. Коды, удовлетворяющие этому условию, называются префиксными кодами, так как ни одно кодовое слово не является передней частью
("префиксом" - приставкой) другого кодового слова.
3. Эффективные коды являются неравномерными, т.е. для передачи разных
символов сообщения mi используются кодовые комбинации разной длины. Наиболее вероятные сообщения кодируются самыми короткими кодовыми словами,
вследствие чего средняя длина кодового слова в сообщении уменьшается, что и
позволяет решить задачу равенства скорости передачи и пропускной способности
канала.
При неравномерном эффективном кодировании средняя длина кодового слова n определяется выражением:
mi
n = ∑ n k p( x k ) ,
(2.17)
k =1
где p(xк) - вероятность появления сообщения (кодового слова), причём их сумма
равна 1; nк - длина кодовых слов xк (к = 1, 2, . . ., mi).
По аналогии с выражением (2.10), где предполагалось применение равномерных кодов с постоянной длиной кодовых слов (n = const), при использовании
эффективных неравномерных кодов (n = var) избыточность кода источника
11
n min
n − n min
= 1−
.
(2.18)
n
n
Очевидно, когда n = nmin, что эквивалентно равенству Hmax(X) = H(X), избыточность кода χк равна нулю и при применении эффективных кодов обеспечивается полное согласование источника сообщений с каналом (2.16). При этом энтропия источника H(X) является оценкой среднего числаn двоичных символов,
требуемых для кодирования сообщений.
Процедуру построения эффективного кода, близкого к оптимальному, предложили практически одновременно Шеннон и Фано (код Шеннона - Фано). Эта
процедура рассмотрена подробно в [1], раздел 3.3.
В данной лабораторной работе студенты знакомятся с процедурой построения эффективных кодов, предложенной Хафменом. При малом алфавите
источника и неравновероятных символах xi выгодно кодировать не отдельные
символы, а целые блоки из нескольких символов (букв). В этом студенты убеждаются, исследуя в лабораторной работе метод кодирования Хафмена.
χk =
Код Хафмена.
Д. А. Хафменом был предложен систематический метод кодирования, который всегда приводит к получению оптимального множества кодовых слов для кодирования данного множества сообщений.
Для дискретных систем с двоичным алфавитом кодера (m=2) методика построения кода Хафмена сводится к следующей процедуре.
1. Все mi = M сообщений (буквы алфавита источника) выписываются в порядке убывания вероятностей p(xi) (см. таблицу).
2. Две последние буквы алфавита, имеющие наименьшие вероятности p(xМ-1)
и p(xM), группируются вместе и объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность pΣ = p(xM-1 ) + p(xM).
3. Вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей ( в
следующем столбце таблицы). Объём нового алфавита таким образом уменьшается на единицу: М-1.
4. Производят второе укрупнение алфавита, состоящего уже из М-1 символов, путём объединения двух символов с наименьшими вероятностями и вычисляют их общую вероятность. Получают новый алфавит объёмом М-2.
5. Упорядочивают по вероятности символы этого нового алфавита.
6. Образуют последовательность укрупнённых алфавитов путём последовательного повторения операций пунктов 4 и 5, пока в ансамбле не останется единственное сообщение с вероятностью, равной 1 (шаговая процедура, записываемая в столбцах таблицы).
7. Проведя линии, соединяющие символы при последовательном укрупнении
алфавита, получают так называемое кодовое дерево, концы ветвей которого являются символами исходного алфавита источника сообщений. Приписывая ветвям дерева, исходящим из каждого промежуточного узла, различные символы
алфавита кодера (0 или 1), получают кодовые слова, соответствующие кодируемым сообщениям источника.
Методика поясняется примером, представленным в таблице, где для алфавита источника с объёмом М = 8 приняты произвольные значения вероятностей
p(xi) , но
M
∑ p( x
i =1
i
) = 1.
12
Для составления кодовой комбинации, соответствующей данному сообщению xi , необходимо проследить путь перехода сообщения по строкам и столбцам таблицы. Для наглядности кодовое дерево построено в поле таблицы. Целесообразно строить кодовое дерево, начиная с первого столбца таблицы, располагая ветви против группируемых попарно вероятностей p(xi) и соединяя их со значением суммарной вероятности pΣ, располагаемой в следующем столбце. Ветвям с большей вероятностью присваивается символ 1, а с меньшей – 0 (или наоборот). Такое последовательное ветвление продолжается до тех пор, пока ветвь
не закончится узлом с вероятностью p(xi) каждой буквы алфавита источника. Отдельно кодовое дерево для алфавита источника, рассматриваемого в примере,
приведено на рис.2.2.
Перемещаясь по кодовому дереву сверху вниз, можно записать для каждой
буквы алфавита xi соответствующую ей кодовую комбинацию
x1
x2
x3
x4
x5
x6
x7
x8
1
011
010
001
00011 00010 00001 00000
Рис.2.2. Кодовое дерево по данным таблицы
13
Код Хафмена при любом распределении вероятностей p(xi ) даёт однозначный ансамбль набора кодовых слов, в то время как при коде Шеннона – Фано на
выходной ансамбль кодовых слов влияет субъективный выбор границ последовательного разбиения алфавита на две группы [ 1 ].
Существенное преимущество кода Хафмена по сравнению с кодом Шеннона
- Фано проявляется при применении кодов с основанием большим 2 (М>2) и заключается в том, что методика Хафмена гарантирует однозначное построение
кода с наименьшим для данного распределения вероятностей средним количеством символов на букву, что показано в [1], стр. 43 - 46.
Достоинства и недостатки эффективных кодов.
Кратко сформулируем перечисленные выше достоинства оптимальных эффективных кодов.
1. При эффективном кодировании, учитывающим вероятности появления
букв алфавита источника сообщений, удаётся построить коды с максимальной
удельной энтропией на символ.
2. Обеспечивается преобразование сообщения в сигнал с меньшей, чем у
сообщения избыточностью (в пределе - без избыточности).
3. На передачу сообщения затрачивается минимальное количество символов.
4. Решается задача согласования источника сообщений с каналом связи, в
результате чего скорость передачи информации может быть приближена к пропускной способности канала.
5. Не требуется введения специальных разделительных символов (маркеров), как, например, в коде Морзе, для отделения одной кодовой комбинации от
другой, так как ни одна комбинация эффективного кода не совпадает с началом
другой, более длинной. Такое свойство кода называется "неприводимостью", и коды называются префиксными или кодами без запятой.
К недостаткам эффективных кодов можно отнести следующее.
1. Эффективные коды являются неравномерными, т.е. кодовые комбинации
имеют различное количество символов. Если линия связи работает с постоянной
скоростью передачи, то на выходе кодера необходимо буферное запоминающее
устройство (" упругая задержка" ) для записи в него "пульсирующих" по длительности кодовых групп и последующего считывания в канал символов с постоянной
скоростью. Аналогичная "упругая задержка" должна быть и на стороне приёма.
2. Наибольший эффект оптимальные коды дают при кодировании исходного
сообщения длинными блоками, поскольку при этом достигается равновероятность
и статистическая независимость блоков. Однако блочное кодирование вызывает
необходимость накапливать слова алфавита источника, прежде чем поставить им
в соответствие определённую кодовую группу эффективного кода. Это приводит к
большим задержкам при передаче и приёме сообщений, что затрудняет (или исключает) применение эффективных кодов в системах, работающих в реальном
масштабе времени. Эффективное кодирование (кодом Хафмена) применяется при
записи информации на магнитные носители (системы архивации) и в системах
факсимильной связи.
3. Существенным недостатком эффективных кодов является то, что они непомехозащищённые. Любая одиночная ошибка при приёме переводит передаваемую комбинацию в другую, не равную ей по длительности, что влечёт за собой неправильное декодирование целого ряда последующих кодовых групп. Такое спе-
14
цифическое влияние помех называется "треком ошибок" или пакетом ошибок. В
чистом виде эффективное кодирование можно применять только для каналов без
помех.
Таким образом, непосредственная передача сообщений при применении
эффективных кодов по каналу связи с шумами приводит к недопустимо большим
искажениям (потере информации). Однако, эффективное кодирование, устраняющее статистическую избыточность в передаваемом сообщении, наилучшим образом подготавливает непрерывную кодовую последовательность, полученную после первичного кодирования сообщений источника, к последующему помехоустойчивому кодированию с помощью корректирующих кодов в кодере канала
(рис.2.1). Целенаправленное введение избыточности при помехоустойчивом кодировании путём добавления дополнительных проверочных символов в кодовые
информативные группы позволяет при декодировании обнаруживать и исправлять
ошибки, вызванные помехами.
2. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ.
Описание работы:
Лабораторная работа выполняется в диалоговом режиме. Ввод данных осуществляется с клавиатуры, выходная информация отображается на экране.
После введения заданных студентами вероятностей p(x1) и p(x2) появления
2-х сообщений x1 и x2 осуществляется последовательное группирование символов алфавита источника сообщений в блоки с длиной ℓ =2, 3 и 4 символа. Каждой
новой комбинации источника сообщений присваивается обозначение, соответственно, Yi , Zi ,Qi и рассчитывается вероятность появления этой комбинации. Далее выполняется операция упорядочения вероятностей по величине от большего
значения к меньшему.
На экран выводятся расчётные значения вероятностей появления блоков источника сообщений Xi , Yi , Zi , Qi и присвоенные им кодовые слова эффективного кода Хафмена.
Выполнение работы:
Перед выполнением лабораторной работы целесообразно подготовить следующие таблицы:
Таблица 1
Алфавит
Обозначения
Вероятность
Код Хафмена
Число симисточника
кодовых слов
p(SI)
волов
x1
X1
x2
X2
Группировка по 2
Алфавит
Обозначения
источника
кодовых слов
x1 x1
Y1
x1 x2
Y2
x2 x1
Y3
x2 x2
Y4
Вероятность
p(SI)
Таблица 2
Код Хафмена
Число символов
15
Группировка по 3
Алфавит
Обозначения
источника
кодовых слов
x1 x1 x1
Z1
Z2
x1 x1x2
x1x2 x1
Z3
……
........
x2 x2 x2
Z8
Группировка по 4
Алфавит
Обозначения
источника
кодовых слов
x1 x1 x1 x1
Q1
Q2
x1x1 x1x2
x1x1x2 x1
Q3
…..
........
x2 x2 x2 x2
Q16
Вероятность
p(SI)
Таблица 3
Код Хафмена Число символов
Вероятность
p(SI)
Таблица 4
Код Хафмена Число символов
Таблица 5
ℓ
1
2
3
4
p(xk)
H(S)
H1(S)
nminc
χи
n
nc
nminc/nc χк
Таблицы 1 – 4 и большая часть таблицы 5 будут заполнены в ходе
лабораторной работы.
R/C
выполнения
2.1 Для выполнения лабораторной работы необходимо выбрать соответствующую позицию в основном меню и нажать клавишу « ENTER». После появления
подсказки : «Введите вероятность» ввести заданную вероятность (число, меньшее 1, например :0.765).
2.2 В случае некорректного ввода в правом нижнем углу экрана появится окно
с диагностическим сообщением. Окно исчезнет после нажатия любой клавиши, а
подсказка 2.1 появится вновь.
2.3 В случае корректного ввода вероятности на экране появится следующая
таблица:
N п/п
1
2
Алфавит источника
x1
x2
Вероятность
Код Хафмена
и окно результатов, характеризующее правильность вводимых ответов.
nK
16
Студентам необходимо построить и ввести кодовые слова кода Хафмена
для каждой из букв алфавита источника данного ансамбля. В случае правильного
ввода в окне результатов в соответствующей позиции появится сообщение
«ВЕРНО». Если кодовое слово введено неправильно, то появится сообщение
«НЕВЕРНО». В любом случае следует продолжить ввод кодовых слов кода
Хафмена до конца, после чего будет предоставлена возможность исправить допущенные ошибки. Нажатие клавиши « ESC» во время ввода приведёт к прекращению выполнения работы и выходу в основное меню. Правильно построенные
кодовые слова кода Хафмена необходимо занести в таблицу 1 протокола выполняемой работы.
2.4 По завершению построения и ввода кода Хафмена в колонку nK необходимо ввести длины кодовых слов построенного кода Хафмена. Ввод длин кодовых
слов происходит аналогично п. 2.3.
2.5 После корректного ввода длин кодовых слов построенного кода Хафмена в
нижней строке экрана появится запрос: "Желаете получить справочную информацию Y/N?". В случае ввода символа "Y" на экране будет предъявлено окно, содержащее справочную информацию о вычислении энтропии, средней длины кодового
слова и т.п. Окно справочной информации исчезнет после нажатия любой клавиши. В случае ввода "N" окно справочной информации не предъявляется.
2.6 После предъявления или непредъявления окна справочной информации
таблица на экране будет сдвинута на две колонки влево и примет вид:
Вероятности
Код Хафмена
nK
В правом нижнем углу экрана будет предъявлено окно, в котором будут последовательно задаваться вопросы, в ответ на которые необходимо определить и
ввести следующие теоретико-информационные характеристики построенного кода
Хафмена:
− среднюю длину кодового слова n,
− среднюю длину на символ
n c,
− энтропию источника
H(S),
− удельную энтропию
H1(S),
− избыточность источника
χ и,
− избыточность кода
χк,
− качество согласования источника с каналом R/C.
2.7 При выполнении пункта 2.6 для получения значений двоичных логарифмов
следует пользоваться встроенной программой, которая активизируется одновременным нажатием комбинации клавиш <ALT>\<ShiftLeft>\<L>. Правила пользования этой программой приведены в Приложении 2.
2.8 При выполнении вычислений согласно п.2.6. может возникнуть необходимость использования калькулятора. В ходе выполнения лабораторной работы
можно использовать встроенный программный калькулятор, который активизируется одновременным нажатием комбинации клавиш <CTRL>\<ShiftRight>\<C>.
Правила пользования этой программой приведены в Приложении 3.
17
2.9 Результаты вычислений по п.2.6 необходимо занести в соответствующие
столбцы первой строки таблицы 5 (ℓ = 1).
2.10 В случае неверного определения характеристик п.2.6 или некорректного их
ввода в правом нижнем углу экрана будет появляться окно с диагностическим сообщением, которое следует проанализировать. Окно исчезнет после нажатия любой клавиши, после чего необходимо ввести правильный ответ.
2.11 Нажатие клавиши <ESC> в любом из пунктов 2.6 приведёт к прекращению
выполнения лабораторной работы и появлению на экране основного меню.
2.12 После корректного определения и ввода характеристик п. 2.6 на экране будет предъявлено дерево кода Хафмена, которое необходимо зафиксировать в
протоколе. Оно исчезнет при нажатии любой клавиши.
2.13 Из исходных вероятностей p(x1) и p(x2) будет автоматически построен алфавит с вероятностями, значения которых являются результатом объединения
символов x1 и x2 по два (группирование по 2). На экране будет предъявлена таблица как в п. 2.3, но с другим алфавитом источника Y1 - Y4 и с вышеопределёнными вероятностями. Необходимо повторить действия, рассмотренные в п.п. 2.3 2.12. Результаты заносятся в протокол работы в таблицу 2 и вторую строку таблицы 5 (ℓ = 2).
2.14 Повторить п. 2.13 для группировки исходных символов х1 и х2 по три (Z1 Z8) и четыре (алфавит источника Q1 - Q16), причём для случая Q1 - Q16 код
Хафмена строится автоматически, поэтому для данного случая выполнение работы будет продолжено с п. 2.4. Кодовое дерево для алфавита (Q1 - Q16) не
предъявляется. Результаты заносятся в таблицы 3 и 4 и в третью и в четвёртую
строки (ℓ = 3 и ℓ = 4) таблицы 5 соответственно.
2.15 Далее в лабораторной работе исследуется влияние ошибок на результат
декодирования информации, закодированной кодом Хафмена.
На экране предъявляется окно, в котором представлены:
− двоичный эквивалент последовательности букв источника Z1 - Z8 (см. п. 2.14),
т.е. эталонная последовательность,
− эта же последовательность со случайным образом искажённым одним разрядом.
Необходимо, пользуясь таблицей 3, декодировать искажённую последовательность и определить количество символов, не совпадающих с эталонной последовательностью, т.е. определить длину трека ошибки.
Предыдущий пункт повторяется для последовательности Z8 - Z1.
2.16 Результаты, полученные в п. 2.15, следует зафиксировать в протоколе работы. На этом выполнение лабораторной работы заканчивается и на экране появится основное меню.
Рассмотрим пример.
Пусть введена вероятность p(x1) = 0.366. Вероятности для данного случая:
0.634
0.366
Строим очевидный код:
18
и заносим его в таблицу 1. Определяем длины кодовых слов. На экране будет:
Алфавит источника
N п/п
1
2
Вероятность
x1
x2
Проверка
Код Хафмена
nK
0
1
1
1
0.634
0.366
∑ p(S ) = 1
i
Определяем характеристики и заносим их в таблицу 5:
ℓ
1
2
3
4
p(xk)
0.634
0.366
H(S)
0.951
H1(S)
0.951
χи
0.049
nminc
n
1
nc
1
nminc/nc χк
0.049
R/C
0.951
Автоматически формируются следующие вероятности при группировке x1 и x2
по два символа: 0.4019, 0.232, 0.232, 0.134.
Строим код Хафмена:
0 .4 0 2
0
0 .2 3 2
0
0 .2 3 2
0
0 .1 3 4
1
0 .5 9 8
1
1
0 .3 6 6
и заносим его в таблицу 2. Определяем длины кодовых слов. На экране будет:
N% п/п
Алфавит
источника
Вероятности
Код Хафмена
nK
1
Y1
0.40196
0
1
2
Y2
0.23204
10
2
3
Y3
0.23204
110
3
4
Y4
0.13396
111
3
Проверка
∑ p(S ) = 1
i
Определяем характеристики и заносим их в таблицу 5:
19
ℓ p(xk)
1 0.634
2 0.366
3
4
H(S)
0.951
1.903
H1(S)
0.951
0.951
χи
0.049
0.951 0.049
nminc
n
1
1.964
nс
1
0.982
nminc/nc
0.951
0.969
χK
0.049
0.031
R/C
0.951
0.969
Автоматически формируются следующие вероятности при группировке x1 и x2 по
три символа: 0.255, 0.147, 0.147, 0.147, 0.085, 0.085, 0.085, 0.049.
Строим код Хафмена:
и заносим его в таблицу 3. Определяем длины кодовых слов.
На экране будет:
N% п/п
Алфавит
источника
Вероятности
1
Z1
0.255
00
1
2
Z2
0.147
100
3
3
Z3
0.147
101
3
4
Z4
0.147
110
3
5
Z5
0.085
010
3
6
Z6
0.085
011
3
7
Z7
0.085
1110
4
8
Z8
0.049
1111
4
Проверка
Код Хафмена
∑ p(S ) = 1
i
Определяем характеристики и заносим их в таблицу 5:
nK
20
ℓ p(xk)
1 0.634
2 0.366
3
4
H(S)
0.951
1.902
2.853
3.807
H1(S)
0.951
0.951
0.951
0.951
χи
0.049
0.951 0.049
0.049
0.049
nminc
n
1
1.964
2.880
3.843
nс
1
0.982
0.960
0.958
nminc/nc
0.951
0.969
0.990
0.992
χK
0.049
0.031
0.010
0.008
R/C
0.951
0.969
0.990
0.992
Для следующего случая при группировке по 4 (Q1 - Q16) код Хафмена строится
автоматически, поэтому сразу переходим к определению характеристик и занесению их в таблицу 5.
Теперь переходим к исследованию влияния ошибок на декодирование кода
Хафмена.
Эталонная последовательность для Z1 – Z8:
0010010111001001111101111
Последовательность с ошибкой:
0010110111001001111101111
Видно, что в данном случае второй символ декодируется неверно ( Z3 вместо
Z2). Трек ошибки равен 2.
Аналогично для последовательности Z8 – Z1:
1111111001101011010110000
Последовательность с ошибкой :
1111111001001011010110000
Здесь тоже трек ошибки равен 2.
На этом выполнение лабораторной работы закончено. Преподавателю
предъявляется протокол выполненной работы.
3.
ПОРЯДОК ОФОРМЛЕНИЯ И СОДЕРЖАНИЕ ОТЧЁТА.
При оформлении отчёта и подготовке к зачёту необходимо пользоваться методической разработкой «Эффективные коды», а также литературой [1-5].
3.1 Поместить в отчёте рис. 1 из методической разработки.
3.2 Привести в отчёте заполненные в ходе выполнения работы таблицы 1 - 5.
3.3 Под таблицами 1, 2, 3 привести деревья кода Хафмена и процедуры их построения.
3.4 Для двоичного источника с алфавитом М = х1,х2 и соответствующих значений p(х1) и p(х2) определить значение энтропии источника. Построить график
зависимости энтропии двоичного источника от вероятности p(x) во всём диапазоне
0≤ p(x) ≤ 1.
3.5 Определить максимальное значение энтропии источников X,Y,Z и Q и максимальное значение удельной энтропии (на символ). Построить на одном графике
зависимости Hmax(S) = f(ℓ ) и H1max (S)= f(ℓ ), где ℓ - количество объединяемых в
блок исходных символов х1 и х2, (ℓ = 1, 2, 3, 4).
3.6 На основании данных таблицы 5 построить следующие зависимости:
21
 n = f(ℓ ) и nc = f(ℓ ) на одном графике; χ и = f(ℓ ) и χк = f(ℓ ) на одном
графике;
R / C = f(ℓ ).
Сделать оценку качества согласования источника с каналом по отношению скорости передачи R к пропускной способности канала C.
3.7 Исследовать влияние помех на правильность декодирования кодов Хафмена
путём определения трека ошибки в последовательности кодовых комбинаций
Z1-Z8. С этой целью записать последовательно, друг за другом, без пропусков
между кодовыми комбинациями все 8 кодов Хафмена для алфавита источника Z
(от Z1 до Z8), взятых из таблицы 3. Наметить пунктиром границы кодовых комбинаций и над каждым кодовым словом разместить соответствующее значение Zi.
В полученной непрерывной последовательности набора «1»и «0», имитируя одиночную ошибку, изменить на противоположный символ с номером, равным номеру бригады по списку в лабораторном журнале.
Произвести декодирование искажённой последовательности, зафиксированной в
черновике, пользуясь таблицей 3, столбцом "Код Хафмена". Под каждой вновь полученной комбинацией записать декодированное значение Zi. Отметить полученный трек ошибки.
Эти же действия проделать для последовательности кодовых комбинаций Z8 - Z1.
3.8 По всем пунктам в отчёте привести расчётные формулы с пояснением входящих в них обозначений, дать объяснения полученных результатов и сделать выводы по каждому пункту отчёта.
4. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАЧИ.
4.1 Дайте определения понятий "информация", "сигнал", модуляция", "кодирование", "объём алфавита".
4.2 Сравните три вида определения меры количества информации. Достоинства
определения меры по Шеннону.
4.3 Поясните определение "энтропия". Перечислите свойства энтропии.
4.4 Дайте определение избыточности источника сообщений, коэффициента сжатия и коэффициента избыточности.
4.5 Поясните различие понятий производительности и скорости формирования
символов источника сообщений.
4.6 Объясните, зачем нужно производить эффективное (статистическое) кодирование и в чём его суть.
4.7 Поясните связь между скоростью передачи информации и пропускной способностью дискретного канала.
4.8 Дайте определение теоремы кодирования для канала без помех. Какие свойства оптимальных кодов являются следствием этой теоремы?
4.9 Почему оптимальные коды называются "префиксными"? Какой факт подчёркивается этим названием?
4.10 Поясните преимущества блочного кодирования и его особенности.
4.11 Поясните процедуру кодирования по методу Хафмена. Назовите достоинства
процедуры Хафмена.
4.12 Перечислите достоинства эффективных кодов и возможности их применения.
4.13 Что такое "неприводимость" кода?
4.14 Что понимается под термином "упругая задержка"?
4.15 Как влияют помехи на декодирование сообщений при зффективном кодировании?
4.16 Что такое "трек ошибок"?
22
4.17 Перечислите операции, которые необходимо выполнить при максимально
эффективной и помехоустойчивой передаче бинарных последовательностей.
4.18 Определите избыточность алфавита двоичного источника, выдающего независимые сообщения "0" и "1", на выходе которого вероятность появления символа
"0" равна p(0) = 0.2.
4.19 Сравните пропускные способности двух дискретных каналов без помех, если
в первом канале используются сигналы с основанием кода ms= 2 при технической
скорости передачи В = 100 Бод, а во втором канале основание кода ms = 8 и
В = 40 Бод.
4.20 Оцените производительность источника сообщений в виде телеграфного
аппарата, если он работает со скоростью передачи 300 знаков в минуту, передавая: 1) последовательность произвольного набора независимых и равновероятных букв; 2) осмысленный русский текст; 3) только поздравительные телеграммы;
4) цифры в случайной последовательности.
4.21 При переводе русского текста на английский число букв в среднем уменьшается в 1.3 раза. При переводе того же текста на финский язык число букв возрастает примерно в 1.4 раза. Найдите соотношение энтропий данных иностранных
языков к русскому и английского к финскому.
4.22 Определите относительную энтропию двух сообщений: 1) аббревиатуры ЛИАП; 2) полного развёрнутого наименования института без сокращений. Оцените
избыточность второго сообщения.
4.23 Фокусник в присутствии зрителей распечатывает новую колоду игральных
карт, содержащую 32 листа. Перемешав карты, он вынимает из колоды одну карту. Какое количество информации (по п.п. 1 - 7) получает зритель, если: 1) вынутая карта предъявляется зрителям и оказывается "пиковой дамой"; 2) вынутая
карта не предъявляется зрителям, но по достоверному утверждению фокусника
является "дамой"; 3) вслед за этим (п.2) карта показывается зрителям и оказывается "дамой пик"; 4) после предъявления зрителям (п.3) карта возвращается
в колоду, которая перемешивается, после чего из неё вновь извлекается "дама
пик"; 5) предъявленная "дама пик" не возвращается в колоду, а откладывается, и
из колоды снова достаётся "пиковая дама"; 6) отложенная ранее карта (п.5) показывается зрителям и действительно оказывается "пиковой дамой"; 7) отложенная
карта (п.5) оказывается "тройкой".
Поясните с позиции зрителя, знакомого с основами теории информации, в чём
суть фокусов.
4.24 Закодировать двоичным кодом Шеннона - Фано множество из пяти сообщений с вероятностями p1 = 0.4; p2 = p3 = p4 = p5 = 0.15. Оценить среднюю длину кодовых слов n .
Закодировать сообщения этого же источника кодом Хафмена, определить среднюю длину кодовых слов n. Сравнить результаты кодирования по этим двум методам и сделать выводы.
23
ПРИЛОЖЕНИЕ 1
Таблица двоичных логарифмов. Энтропия двоичного ансамбля.
p
-log p
-p logp
H(p)
-(1-p)⋅log(1-p)
-log(1-p)
1-p
0,01
0,02
0,03
0,04
0,05
0,06
0,07
0,08
0,09
0,10
0,11
0,12
0,13
0,14
0,15
0,16
0,17
0,18
0,19
0,20
0,21
0,22
0,23
0,24
0,25
0,26
0,27
0,28
0,29
0,30
0,31
0,32
0,33
0,34
0,35
0,36
0,37
0,38
0,39
0,40
0,41
0,42
0,43
0,44
0,45
0,46
0,47
0,48
0,49
0,50
6,643
5,644
5,059
4,644
4,322
4,059
3,936
3,644
3,474
3,322
3,184
3,059
2,943
2,836
2,737
2,644
2,556
2,474
2,396
2,322
2,252
2,184
2,120
2,059
2,000
1,943
1,889
1,836
1,786
1,737
1,690
1,644
1,599
1,556
1,514
1,474
1,434
1,396
1,358
1,322
1,286
1,252
1,217
1,184
1,152
1,120
1,089
1,059
1,029
1,000
0,066
0,113
0,152
0,186
0,216
0,243
0,268
0,291
0,313
0,332
0,350
0,367
0,383
0,397
0,411
0,423
0,434
0,445
0,455
0,464
0,473
0,481
0,488
0,494
0,500
0,505
0,510
0,514
0,518
0,521
0,524
0,526
0,528
0,529
0,530
0,531
0,531
0,530
0,529
0,529
0,527
0,526
0,523
0,521
0,518
0,515
0,512
0,508
0,504
0,500
0,081
0,141
0,194
0,242
0,286
0,327
0,366
0,402
0,436
0,469
0,499
0,529
0,557
0,584
0,610
0,634
0,658
0,680
0,701
0,722
0,741
0,760
0,778
0,795
0,811
0,827
0,841
0,855
0,869
0,881
0,893
0,904
0,915
0,925
0,934
0,943
0,951
0,958
0,965
0,971
0,976
0,981
0,986
0,989
0,993
0,995
0,997
0,999
0,999
1,000
0,014
0,028
0,042
0,056
0,070
0,084
0,097
0,111
0,124
0,137
0,150
0,162
0,175
0,187
0,199
0,211
0,223
0,235
0,246
0,257
0,269
0,279
0,290
0,301
0,311
0,321
0,331
0,341
0,351
0,360
0,369
0,378
0,387
0,396
0,404
0,412
0,420
0,428
0,435
0,442
0,449
0,455
0,462
0,468
0,474
0,480
0,485
0,491
0,495
0,500
0,014
0,029
0,044
0,059
0,074
0,089
0,105
0,120
0,136
0,152
0,168
0,184
0,201
0,217
0,234
0,252
0,269
0,286
0,304
0,322
0,340
0,358
0,377
0,396
0,415
0,434
0,454
0,474
0,494
0,514
0,535
0,556
0,578
0,599
0,621
0,644
0,667
0,690
0,713
0,737
0,761
0,786
0,811
0,836
0,852
0,889
0,916
0,943
0,971
1,000
0,99
0,98
0,97
0,96
0,95
0,94
0,93
0,92
0,91
0,90
0,89
0,88
0,87
0,86
0,85
0,84
0,83
0,82
0,81
0,80
0,79
0,78
0,77
0,76
0,75
0,74
0,73
0,72
0,71
0,70
0,69
0,68
0,67
0,66
0,65
0,64
0,63
0,62
0,61
0,60
0,59
0,58
0,57
0,56
0,55
0,54
0,53
0,52
0,51
0,50
24
ПРИЛОЖЕНИЕ 2
Инструкция по использованию встроенной программы вычисления двоичных
логарифмов.
Для вызова программы вычисления двоичных логарифмов необходимо на
клавиатуре
одновременно
нажать
следующую
комбинацию
клавиш:
<ALT>\<ShiftLeft>\<L>.
В левом верхнем углу экрана терминала будет предъявлено окно :
Введите x или -1
X=
Необходимо ввести число, двоичный логарифм которого необходимо определить, или -1. В первом случае в окне появится искомое значение двоичного
логарифма и указание о нажатии любой клавиши для продолжения работы. После выполнения указания окно вернется в исходное состояние. Во втором случае
сеанс работы с программой завершится и окно исчезнет с экрана.
ПРИЛОЖЕНИЕ 3
Инструкция по использованию встроенного калькулятора.
Для вызова калькулятора необходимо нажать одновременно следующую
комбинацию клавиш: <CTRL>\<ShiftRight>\<C>.
В правом верхнем углу терминала будет предъявлено окно калькулятора следующего вида
PCALC Programm ers Calculator 5.0
Clr …………
Save ……….
Верхняя часть окна используется для ввода чисел и вывода результатов. В
нижней части представлены список команд и режимы работы.
Вычисления производятся в следующей последовательности:
1. На цифровой клавиатуре набирается первое число, которое записывается в
верхнем углу окна калькулятора.
2.Нажатием клавиш +,-,*,/ выбирается нужное действие сложение, вычитание,
умножение или деление.
3. Набирается второе число, следующее за знаком операции (высвечивается в
окне).
4. Для получения результата необходимо нажать клавишу = или <ENTER>.
В окне высветится результат.
25
Команды калькулятора:
<C> (очистка) - стереть содержимое окна калькулятора
<E> (сбросить ввод) - стереть текущий ввод.
<I> (вставить запомненное значение) - число из памяти
используется в качестве операнда.
<S> (сохранить) - записать результат в память.
ПРИМЕР: Необходимо вычислить выражение:
0,1⋅5 + 0,2⋅3 – 0,3⋅2
АЛГОРИТМ РЕШЕНИЯ
Действие
1. Очистить калькулятор, нажав
клавишу <C>.
2. Ввести первое число, 0.1
3. Нажать клавишу <*>
4. Ввести второе число, 5
5. Нажать клавишу <=>
6. Нажать клавишу <S>
7. Нажать клавишу <C>
8. Ввести третье число, 0.2
9. Нажать клавишу <*>
10. Ввести четвертое число, 3
11. Нажать клавишу <+>
12. Нажать клавишу <I>
13. Нажать клавишу <=>
14. Нажать клавишу <S>
15. Нажать клавишу <C>
16. Ввести пятое число, -0.3
17. Нажать клавишу <*>
18. Ввести шестое число, 2
19. Нажать клавишу <+>
20. Нажать клавишу <I>
21. Нажать клавишу <=>
22. Нажать клавишу <C>
Комментарий
Очистка окна и памяти калькулятора, если
там не 0
Ввод на цифровой клавиатуре.
Действие умножения.
Ввод на цифровой клавиатуре.
Результат первого умножения.
Запоминание в памяти.
Очистка окна калькулятора.
Ввод на цифровой клавиатуре.
Очередное действие умножения.
См. п.2
Результат * п.9 становится
Значением 1.
Запомненный итог п.5 становится
Значением 2.
Результат сложения п.5 и п.11
См. п.6
Cм. п.7
Со знаком!! - см. п.2
См. п.3
См. п.2
Cм. п.11
См. п.12
В третьей строке окна калькулятора
будет результат, число 0.5
См. п.1
Для завершения сеанса работы с калькулятором нажать клавишу <ESC>.
Замечание: Калькулятор сохранит состояние предыдущего сеанса, если не
произвести его очистку.
26
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.
1. Журавлев А.К., Никитин Г.И. Радиотехнические системы передачи информации: Учебное пособие /ЛИАП. Л., 1984. 86 с.
2. Первичные коды: Методические указания /Сост. Г.И. Никитин; ЛИАП.
Л.; 1984. 28 с.
3. Шеннон К. Связь при наличии шума / Теория информации и ее приложения: Сб. переводов / Под ред. А.А. Харкевича. М.; Физматгиз, 1969. 328 с.
(С. 82 - 112).
4. Новик Д.А. Эффективное кодирование. М.; Энергия, 1965. 236 с.
(С. 33 -63).
5. Теория передачи сигналов: Учебник для вузов / А.Г. Зюко, Д.Д. Кловский,
М.В. Назаров, Л.М. Финк. М.: Радио и Связь, 1986. 304 с. (С. 101 -112, 135 -137).
Оглавление
1. Методические указания по подготовке к работе ………………..…………... 1
1.1 Информация, сообщение, кодирование, сигнал ……………………..…... 1
1.2 Информационные характеристики системы передачи сообщений …….. 3
Мера количества информации ………………………..……………………... 3
Энтропия источника дискретных сообщений ………………….………….. 4
Избыточность источника сообщений ……………………………………….. 6
Производительность источника …………………………………..…………. 7
1.3 Эффективное кодирование дискретных сообщений …………………….. 8
Цели эффективного кодирования ……………………………………………. 8
Скорость передачи информации и пропускная способность
дискретного канала без помех ……………………………………………….. 8
Основная теорема кодирования ………….………….. …………………….. 9
Код Хафмена ……………………..……………………..………..…………….. 11
Достоинства и недостатки эффективных кодов ……………….………….. 13
2. Порядок выполнения лабораторной работы …………………………..…….. 14
Описание работы ………………………………………….……………..…….. 14
Выполнение работы ……………………………………………………..…….. 14
3. Порядок оформления и содержание отчёта ………………………..…..……. 20
4. Контрольные вопросы и задачи …………………………………………..….... 21
Приложение 1. Таблица двоичных логарифмов. Энтропия двоичного
ансамбля
……………………………………………………………….….…….. 23
Приложение 2. Инструкция по использованию встроенной программы
27
вычисления двоичных логарифмов …………………………………….….…. 24
Приложение 3. Инструкция по использованию встроенного
калькулятора …………………………..…….. ………………………..…..……. 24
Библиографический список ………………………………………………..…... 26
Графика и компьютерная вёрстка
Романова М.Я. 2002 г.
Документ
Категория
Без категории
Просмотров
0
Размер файла
309 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа