Задания на практическую работу

Санкт-Петербургский колледж телекоммуникаций

«УТВЕРЖДАЮ»

ЗАМ. Директора по Э и Р

____________________________

«» ____________2015 г.

 

Практическое занятие 8

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

 

 

по дисциплине: «Основы теории информации»

для специальностей:

 

230111 «Компьютерные сети»

 

среднего профессионального образования

(базовый уровень)

 

 

Каждая работа рассчитана

на 2 часа

 

Санкт-Петербург

Описание практического занятия составлено в соответствии с рабочей программой по учебной дисциплине «Основы теории информации»

 

 

Составитель: К.В. Лебедева, К.Д. Волкова

 

 

Рассмотрено и одобрено на заседании цикловой комиссии № (цикловая комиссия общепрофессиональных дисциплин электросвязи)

 

 

Утверждено на заседании методического совета

 

_______________ 2015 г. Протокол №_

 

Председатель цикловой (предметной) комиссии:

______________________

 

 

Практическое занятие №8

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

 

Цель занятия:

В соответствии с рабочей программой по дисциплине «Основы теории информации», в результате выполнения заданий ПЗ, студент должен:

 

уметь:

- кодировать информацию (символьную, числовую, графическую, звуковую);

 

знать:

- принципы кодирования и декодирования;

 

 

Таким образом, студент во время проведения ПЗ и самостоятельной работы по теме должен:

- научиться использовать оптимальное кодирование информации

 

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

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

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

Оптимальные коды — коды с практически нулевой избыточнос­тью. Оптимальные коды имеют минимальную среднюю длину кодовых слов — L. Верхняя и нижняя границы L определяются из неравен­ства

 

где Н — энтропия первичного алфавита, т — число качественных признаков вторичного алфавита.

При построении оптимальных кодов наибольшее распространение нашли методики Шеннона — Фано и Хаффмена

Согласно методике Шеннона — Фано построение оптимального кода ансамбля из сообщений сводится к следующему:

1-й шаг. Множество из сообщений располагается в порядке убывания вероятностей.

2-й шаг. Первоначальный ансамбль кодируемых сигналов разбивается на две группы таким образом, чтобы суммарные веро­ятности сообщений обеих групп были по возможности равны. Если равной вероятности в подгруппах нельзя достичь, то их делят так, чтобы в верхней части (верхней подгруппе) оставались символы, суммарная вероятность которых меньше суммарной вероятности символов в нижней части (в нижней подгруппе).

3-й шаг. Первой группе присваивается символ 0, второй» группе — символ 1.

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

5-й шаг. Первым группам каждой из подгрупп вновь присваивается 0, а вторым—1. Таким образом, мы получаем вторые цифры кода. Затем каждая из четырех групп вновь делится на равные (с точки зрения суммарной вероятности) части до тех пор, пока в каждой из подгрупп не останется по одной букве.

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

Методические указания

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

Решение. Так как вероятности данного ансамбля сообщений равны р₁ = р₂ =... = р₆ = 2^-3 и порядок их размещения не играет роли, то располагаем сообщения в порядке возрастания порядковых номеров. Затем разбиваем данное множество сообщений на две равновероятные группы. Первой группе в качестве первого символа кодовых слов присваиваем 0, второй группе — 1. В колонке «ко­довые слова» записываем 4 нуля и 4 единицы. После этого согласно методике Шеннона — Фано, разбиваем каждую из подгрупп еще на две равновероятные подгруппы. Затем каждой первой подгруппе в качестве второго символа присваиваем 0, а второй —1 и записываем в колонку «кодовые слова». Далее каждую из четырех подгрупп разбиваем на две равновероятные части и первой из них присваиваем 0, а второй —1, таким образом, в колонке «кодовые слова» появятся значения третьего символа кодовых слов.

Для исходного алфавита оптимальный код будет иметь вид: А₁₌=000; А₂=001; А₃ = 010; А₄ = 011; А₅ = 100; А₆ = 101; А₇=110; А₈=111.

Проверка.

Н = log_a N= log_a 8 = 3 бит/символ,

 

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

 

Задания на практическую работу

Номер варианта определяет преподаватель.

Работа выполняется в тетради для практических работ и сдается преподавателю.

Задача 1. Построить оптимальный код для передачи сообщений при помощи 32-буквенного равновероятного алфавита. Чему равна средняя длина кодового слова в полученных кодах?

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

 

 

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

Задача 3. Чему равна длина кодовых комбинаций оптимального кода для передачи сообщений, составленных из 16, 32 и 28 равно­вероятных двоичных символов?

Задача 4. Напишите первые три кодовые комбинации опти­мального кода для передачи сообщений» составленных из первичного алфавита, содержащего 64 равновероятных символа.

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

Задача 6. Составьте ОНК для фразы «озорной подросток».

Задача 7. Составьте ОНК для фразы «нехороший продавец».

Задача 8 Вероятности появления символов на выходе источника сообщения следующие:

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

Задача 9. Построить ОНК для передачи сообщений, в которых вероятности появления букв первичного алфавита равны: А₁ = 0,5; А₂ = 0,25; А₃ = 0,098; А₄ = 0,052; А₅ = 0,04; А₆ = 0,03; А₇ = 0,019; А₈ = 0,011. Определить коэффициент статистического сжатия и коэффициент относительной эффективности.

Задача 10. Составьте ОНК для фразы «холодное сердце».