Информация, язык, общество. Измерение информации. Энтропия и её свойства. Определение информационных потерь в каналах связи. Передача информации по дискретным каналам связи. Код Хэминга, страница 7

 бит

 бит/символ

Коэффициент статического сжатия

Коэффициент общей эффективности

К_СС и К_ОЭ характеризуют оптимальность алфавита

Пример: Построить оптимальный код Шеннона-Фана.

Буква	Вер-ть	1	2	3	4
а1	0.25	1	1
а2	0.25	1	0
а3	0.25	0	1
а4	0.1	0	0	1
а5	0.1	0	0	0	1
а6	0.5	0	0	0	0

l_ср  = 2.4 бит

 бит/символ – т.к. разделили неравномерно три столбца, лучше не получиться.

            

Блочное кодирование

Пусть первичный алфавит содержит 2-е буквы: а и б. p(A) = 0.7; p(B) = 0.3

H = - 0.7*log 0.7 – 0.3 log 0.3 = 0.881 бит/символ

Составим новый алфавит из 2-х буквенных комбинаций

АА	0.49	1
АВ	0.21	0	1
ВА	0.21	0	0	1
ВВ	0.09	0	0	0

L_ср = 1 * 0.49 + 2 * 0.21 + 3 * 0.21 + 4 * 0.09 = 1.81 бит

На одну букву

бит < 1                                    l_ср > H                       3%

Пример: Составим алфавит из трёх буквенных комбинаций.

Буква	Вероят.	1	2	3	4
ААА	0.343	1	1
ААВ	0.147	1	0
АВА	0.147	0	1	1
ВАА	0.147	0	1	0
АВВ	0.063	0	0	1	1
ВАВ	0.063	0	0	1	0
ВВА	0.063	0	0	0	1
ВВВ	0.027	0	0	0	0

l_ср = 2.686 бит

.895 бит  - это больше 1,5% и H, следовательно, можно делить по четыре группы.

Избыточность  от округления

Пример: Кодируются цифры от 0 до 10.  Чтобы их представить в виде двоичных, надо

2³<10<2⁴

4 бита   

1 символ – 4 бита

Кодируем блоки по 2 цифры

   00

   01

   …

   99

Для передачи информации с помощью двоичной системы 2⁶<99<2⁷

                                                   7 бит

На 1 символ:  7/ 2 = 3,5 бита

Кодируются блоки по 3 цифры

   000

210 = 1024, 10 бит информации, следовательно, на один символ: 10/3 = 3,3 бита

   001

   …

   999

Подсчитаем энтропию

Н = log n = log 10 = 3,32 бит

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

где m1 – число символов первичного алфавита; m2 – число символов вторичного алфавита; L – длина кодовой комбинации.

,

Пример: Передается алфавит из 5 символов: 1, 2, 3, 4, 5, следовательно, m₁=5  с помощью двоичных символов 0,1 , следовательно,  m₂=2.

Для передачи сообщения потребуется:

D₀ – избыточность от округления

                                    m - коэффициент;

                                                                                                  К – большее целое число.

Пример:

Пример:  Определить избыточность сообщений от округления при побуквенном и поблочном кодировании, если кодируются цифровые сообщения и передаются в двоичном коде. Кодирование осуществляется блоками по 4, 5, 6 цифр.

Первичный алфавит m₁=10

Вторичный алфавит m₂ = 2

Первичный алфавит из 2-х букв                      m₁=10000         m₂=2

Первичный алфавит из блоков по пять             m₁=100000

Кодируются символы по шесть букв                          m₁=10⁶

 , следовательно, этот алфавит наиболее близок к оптимальному.

Код Хафмана