ОТИ практическая 3

«Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева» (СибГАУ)

Аэрокосмический колледж

Преподаватель: Пятков Антон Геннадьевич, СибГАУ

Основы теории информации

Практическая работа № 3

«Кодирование информации при передачи по дискретному каналу без помех»

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

Теоретическая часть

КОДИРОВАНИЕ МЕТОДОМ ШЕННОНА-ФАНО

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

1. Алфавит из n букв (или комбинации букв) располагается в порядке убывания вероятностей их появления в сообшениях.

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

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

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

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

КОДИРОВАНИЕ МЕТОДОМ ХАФФМАНА

Метод Хаффмана также относится к группе неравномерных кодов. Методика построения кода следующая.

Пусть имеется алфавит А, содержащий буквы а₁, а₂, ... а_n, вероятности появления которых p₁, p₂, ... p_n.

1. Расположим буквы в порядке убывания их вероятностей.

2. Две буквы алфавита А₁, объединяем в новую букву (в случае кодирования двоичным алфавитом). Получаем новый алфавит А₁.

3. Буквы алфавита А₁ также располагаем в порядке убывания их вероятностей.

4. Две последние буквы алфавита А₁ объединяются в новую букву. Получаем алфавит А₂. Процедура сжатия (образование новых алфавитов) продолжается до тех пор, пока в последнем алфавите не останется две буквы.

Кодирование:

1. Две буквы последнего алфавита кодируются нулем и единицей.

2. Затем кодируется предыдущий алфавит. При этом буквы алфавита имеют те же кодовые комбинации, а к двум последним буквам добавляется ноль или единица.

Практическая часть

1. Преобразовать весь указанный текст в 16-ричный вид в кодировку Unicode.

2. Преобразовать 2 первые строчки текста в 2-ичный вид в кодировку Unicode.

Текст:

В темнице там царевна тужит, А бурый волк ей верно служит; Там русский дух... там Русью пахнет! И там я был, и мёд я пил; У моря видел дуб зелёный; Под ним сидел, и кот учёный Свои мне сказки говорил.

3. (не обязательно, на дополнительную оценку) Построить код 1 и 2 строк исходного текста методом Шеннона-Фано или методом Хаффмана.

3