Вопрос №6 Теория кодирования информации. Первая теорема Шеннона.

1) разработка методов экономичного кодирования;

2) разработка методов надёжной передачи информации при наличии помех.

Код – правило, описывающее соответствие знаков (или их сочетания) первичного алфавита знакам вторичного алфавита;

Код – набор знаков вторичного алфавита (т.е. результат кодирования). Кодирование бывает обратимым и необратимым. Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких либо потерь.

Теория Шеннона: ( теория о кодировании при отсутствии помех).

I – исходная информация (первичный алфавит), n – количество символов в первом алфавите (длинна сообщения), - информация, которую содержит один в сообщении первом; и соответственно для вторичного алфавита, в который превращается первичный II, m, ; ; ; ;

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

Вопрос №7 Виды кодирования. Коды Фано-Шеннона и Хаффмана.

Виды кодирования:

1. Неравномерное кодирование. Идея н.к. заключается в том, что наиболее короткие коды соответствуют чаще употребляемым символам. Можно выделить специальный набор 0 и 1 для разделения. Код первого символа

_

P

____

P

_

P

____

Но он не экономичный. Коды которые можно однозначно разделить без разделителей – Префиксные коды (Фено).

Префиксный код – строится по следующему требованию. Никакой из кодов не совпадает с началом (префиксом) какого-либо иного длинного кода. ЕХ:

а	л	м	р	у	ы
10	010	00	11	0110	0111

00100010000111010101110000110, где

00	01	00	10	00	0111	010	10	11	10	00	0110
м	а	м	а	м	ы	л	а	р	а	м	у

Префиксный код Шеннона Фано.

Основная идея построения кода заключается: символы все время делятся на 2 группы, так чтобы их были ≈

ЕХ:

Знак	Pi
а1	0,30	0 0	00
а2	0,20	0 1	01
а3	0,20	1 0	10
а4	0,15	1 1 0	110
а5	0,10	1 1 1 0	1110
а6	0,05	1 1 1 1	1111

Посчитаем экономичность кода: I=-ΣP_i log₂P_i, где i=1…6. Если посчитать I=2,390 бита.

Для нашего кода: 2,45/2,39-1=2,5% Префиксный код Хаффмана.

Строится несколько промежуточных алфавитов, каждый раз исключается 2 последних символа с наименьшей вероятностьюP_i

М// Хаффмана имеет такую же избыточность, что и метод Шеннона, но он лучше тем, что и у него > вероятность 0 и 1.

М// Хаффмана является наилучшим с точки зрения экономичности и это можно математьически доказать.

М. рассчитать, что избыточность при применении М// Хаффмана к русскому тексту ≈1%.

2. Равномерное кодирование. Для всех символов количество битов одинаково →не нужны разделители. Для информации каждого символа применима ф-ла Хартли: I=log₂N₁, где N – количество символов. ЕХ: Код Бодо: Для русского алфавита вводят 32 символа, где пренебрегают разницей между «е» и «ё» и «ъ»; + пробел включительно. →надо 5 бит информации. ЕХ: ASCII принято 8 битов. Недостаток единовременно может существовать только 2 языка. Для решения этой проблемы вводят другую кодировку. ЕХ: Unicode Каждый символ занимает 2 бита: 1-ый – номер алфавита (для России №4) , 2-ой бит – номер символа в алфавите.

3. Блочное кодирование. ЕХ: Возъмем слов. Запас в 160000 слов. Воспользуемся формулой Хартли: I=log₂16000<14 бит. Т.е. 14 бит достаточно, чтобы закодировать эти слова. В русском слове ≈5,3 символов (в среднем + пробел). 14/6,3=2,2 бита для одного слова. Когда кодируем слова, можно использовать тот же принцип: чем чаще встречается, тем меньше цифр. Что надо сделать, чтобы уменьшить избыточность? – увеличить размер блока, - применить метод Хаффмана. Это удовлетворяет Т//Шеннона. ЕХ: Пусть алфавит состоит всего из 2-х букв А и В. (Р(А)=0,75, а Р(В)=0,25) – вероятность появления. Сравнить избыточность кодов Хаффмана при алфавитном и при блочном кодировании.

	Р
А	0,75	0
В	0,25	1

1 символ=1 бит. Определим избыточность из формулы Шеннона: I=-0,75 log₂0,75 – 0,25 log₂0,25=0,811 Избыточность : 1/0,811-1=0,233.

Двубуквенное кодирование:

аа	Р(а)∙Р(а)	0,562	0
ав	Р(а)∙Р(в)	0,188	1 10
ва	Р(в)∙Р(а)	0,188	1 11 110
вв	Р(в)∙Р(в)	0,062	1 11 111

Воспользуемся лит. Фано-Шеннона. I=-0,562 log₂0,562-2∙0,188 log₂0,188-0,062 log₂0,062≈1,688

1,688/1,623=1,04 Избыточность мала. Блочное кодирование экономичнее и выгоднее.

4. Кодирование с неравной длительностью неравных сигналов. (Азбука Морзе в 1838). τ – единица длительности. τ-точка, 3 τ – тире. Пауза между точкой и тире – τ. Пауза между буквами - 3 τ. Пауза между символами - 6 τ.

Алфавит из 3 символов: - точка; - тире; - пауза слов.

Постараемся как-нибудь более экономично расположить «∙» и «-»