Контрольная работа по информатике : Кодирование

i P i (вероятность) - Pi log 2 P i

A 0.35 0.5301

B 0.28 0.5142

C 0.10 0.3322

D 0.09 0.3127

E 0.08 0.2915

I 0.06 0.2435

K 0.04 0.1857

Кодирование по методу Шеннона :

1) Передаваемый алфавит записывается в столбик, причем в верхней строке записывается символ алфавита, который чаще всего передается.

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

3) Затем выделенные раньше половины продолжать надо дальше делить, до тех пор , пока в каждой группе будет только по одному символу (символы будут обособлены)

4) Записываются коды символов. Наиболее часто встречающимся символам ставят в соответствие короткие коды (битовые комбинации), а редко встречающимся – длинные. В целом мы получим более короткое представление всего текста, чем при использовании обычного кода, подобного Unicode или ASCII.

i P i (вероятность)

A 0.35 0 0

63

B 0.28 0 1

C 0.10 1 0 0

19

D 0.09 1 0 1

E 0.08 1 37 1 0

I 0.06 1 1 18 1 0

K 0.04 1 1 1 1

А – 00

В – 01

С – 100

D – 101

E – 110

I – 1110

K – 1111

5) Вычисляем эффективность кодирования:

L двоичное = 3

L среднее = 1*( 0.35 + 0.28) + 2*(0.10 + 0.9) + 3* (0.08 +0.06 +0.04) =1.55

3 – 1.55

۵= 3 = 1.45

H = 0.5301 +0.5142 +0.3322 + 0.3127 + 0.2915 +0.2435 + 0.1857 =2.4099 ≈ 2.41

H max =log 2 7 = 2.81

۵ H = 2.81- 2.41 = 0.14

2.81

Кодирование по методу Хаффмана :

A – 00

B – 01

C – 100

D – 101

E – 110

I – 1110

K – 1111