Определение избыточности сообщений. Оптимальное кодирование

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

 

∆D=(Н_макс-Н) бит/символ

 

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

 

,

 

где = μ - коэффициент сжатия (относительная энтропия). Н и Н_макс берутся относительно одного и того же алфавита.

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

Избыточность, которая заложена в природе данного кода, получается в результате неравномерного распределения в сообщениях качественных признаков этого кода и не может быть задана одной цифрой на основании статистических испытаний. Так при передаче десятичных цифр двоичным кодом максимально загруженными бывают только те символы вторичного алфавита, которые передают значения, являющиеся целочисленными степенями двойки. В остальных случаях тем же количеством символов может быть передано большее количество цифр (сообщений). Например, тремя двоичными разрядами мы можем передать и цифру 5, и цифру 8. Фактически для передачи сообщения достаточно иметь длину кодовой комбинации.

Фактически для передачи сообщения достаточно иметь длину кодовой комбинации

 

где N - общее количество передаваемых сообщений.

L можно представить и как

 

 

где  и  - соответственно качественные признаки первичного и вторичного алфавитов. Поэтому для цифры 5 в двоичном коде можно записать

 

 дв. симв.

 

Однако эту цифру необходимо округлить до ближайшего целого числа (в большую сторону), так как длина кода не может быть выражена дробным числом.

В общем случае, избыточность от округления:

 

 

где , k - округленное до ближайшего целого числа значение . Для нашего примера

 

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

Для уменьшения избыточности используют оптимальные коды. При построении оптимальных кодов наибольшее распространение получили методики Шеннона-Фано и Хаффмена. Согласно методике Шеннона-Фано построение оптимального кода ансамбля из сообщений сводится к следующему:

1) множество из сообщений располагается в порядке убывания вероятностей;

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

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

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

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

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

Построенный код называют оптимальным неравномерным кодом (ОНК).

ПРАКТИЧЕСКАЯ ЧАСТЬ

A) Расчеты

 

1) рассчитывается первоначальные вероятности для неравновероятных символов алфавита.

2) выполняет нормирование указанных вероятностей.

3) рассчитывается энтропия алфавита из равновероятных символов.

4) производится расчет энтропии алфавита с неравновероятными символами и недогруженность в этом случае.

5) с учетом заданных длительностей символов вычисляется скорость передачи и избыточность.

6) строится оптимальный код по методу Шеннона-Фано.

 

Расчет вероятностей.

Промежуточные значения:  k-1  ...pk = S pn /(m - k + 1).  n-1	Окончательный результат:  рi = pi/( pi)
p1 = 0,1500 p2 = 0,0065 p3 = 0,0071 p4 = 0,0078 p5 = 0,0086 p6 = 0,0095 p7 = 0,0105 p8 = 0,0118 p9 = 0,0132 p10 = 0,0150 p11 = 0,0171 p12 = 0,0198 p13 = 0,0231 p14 = 0,0273 p15 = 0,0327 p16 = 0,0400 p17 = 0,0500 p18 = 0,0643 p19 = 0,0857 p20 = 0,1200 p21 = 0,1800 p22 = 0,3000 p23 = 0,6000 p24 = 1,8000   рi = 3,6	p1=0,0417 p2=0,0018 p3=0,0020 p4=0,0022 p5=0,0024 p6=0,0026 p7=0,0029 p8=0,0033 p9=0,0037 p10=0,0042 p11=0,0048 p12=0,0055 p13=0,0064 p14=0,0076 p15=0,0091 p16=0,0111 p17=0,0139 p18=0,0179 p19=0,0238 p20=0,0333 p21=0,0500 p22=0,0833 p23=0,1667 p24=0,5000   рi = 1

 

 

Определение количества информации на символ сообщения, составленного из данного алфавита.

Количество информации на символ сообщения для символов данного алфавита, встречающихся с равными вероятностями:

 

H_max = log₂ 24 = ln 24/ln 2 = 4,5850 бит/символ

 

Количество информации на символ сообщения для символов данного алфавита, встречающихся в сообщении с разными вероятностями:

 

H = – (0,0417*log₂0,0417 + 0,0018*log₂0,0018 + 0,020*log₂ 0,0020 + 0,0022*log₂0,0022 + 0,0024*log₂0,0024 + 0,0026*log₂0,0026 + 0,0029*log₂0,0029 + 0,0033*log₂0,0033 + 0,0037*log₂0,0037 + 0,0042*log₂0,0042 + 0,0048*log₂0,0048 + 0,0055*log₂0,0055 + 0,0064*log₂0,0064 + 0,0076*log₂0,0076 + 0,0091*log₂0,0091 + 0,0111*log₂0,0111 + 0,0139*log₂0,0139 + 0,0179*log₂0,0179 + 0,0238*log₂0,0238 + 0,0333*log₂0,0333 + 0,0500*log₂0,0500 + 0,0833*log₂0,0833 + 0,1667*log₂0,1667 + 0,5000*log₂0,5000) =

= 2,6409 бит/символ

Недогруженность символов в данном случае:

 

N = Н_max – Н = 4,5850 – 2,6409 = 1,9441 бит/символ

 

Вычисление скорости передачи информации.

 

С= – (0,0417*log₂0,0417 + 0,0018*log₂0,0018 + 0,020*log₂ 0,0020 + 0,0022*log₂0,0022 + 0,0024*log₂0,0024 + 0,0026*log₂0,0026 + 0,0029*log₂0,0029 + 0,0033*log₂0,0033 + 0,0037*log₂0,0037 + 0,0042*log₂0,0042 + 0,0048*log₂0,0048 + 0,0055*log₂0,0055 + 0,0064*log₂0,0064 + 0,0076*log₂0,0076 + 0,0091*log₂0,0091 + 0,0111*log₂0,0111 + 0,0139*log₂0,0139 + 0,0179*log₂0,0179 + 0,0238*log₂0,0238 + 0,0333*log₂0,0333 + 0,0500*log₂0,0500 + 0,0833*log₂0,0833 + 0,1667*log₂0,1667 + 0,5000*log₂0,5000) /

(1*0,0417 + 2*0,0018 + 3*0,020 + 4*0,0022 + 5*0,0024 + 6*0,0026 + 7*0,0029 + 8*0,0033 + 9*0,0037 + 10*0,0042 + 11*0,0048 + 12*0,0055 + 13*0,0064 + 14*0,0076 + 15*0,0091 + 16*0,0111 + 17*0,0139 + 18*0,0179 + 19*0,0238 + 20*0,0333 + 21*0,0500 + 22*0,0833 + 23*0,1667 + 24*0,5000) = 0,1244 бит/сек

 

Избыточность сообщений, составленных из данного алфавита.

 

D = 1 – (Н/Н_max) = 1 – (2,6409 / 4,5850) = 0,4240

 

Построение оптимального кода

1	p24=0,5000	0,5	0																	0
2	p23=0,1667	0,5	1	0,25	1	0,1666	1													111
3	p22=0,0833		1		1	0,0833	0													110
4	p21=0,0500		1	0,25	0		0	0,05	1 0											1000
5	p1=0,0417		1		0		0	0,0690	1	0,0357	1									10011
6	p20=0,0333		1		0	0,1190	0		1	0,0333	0									10010
7	p19=0,0238		1		0		1		1	0,0428	1	0,0178	1							101111
8	p18=0,0179		1		0		1		1		1	0,025	0	0,0138	0					1011100
9	p17=0,0139		1		0		1		1		0	0,025	1							101101
10	p16=0,0111		1		0		1	0,0666	1		1		0							101110
11	p15=0,0091		1		0		1	0,0642	0		0		1	0,0090	1					1010011
12	p14=0,0076		1		0		1		0		0		1	0,0102	0	0,0054	0			10100100
13	p13=0,0064		1		0		1		0		0	0,0166	0	0,0064	1					1010001
14	p12=0,0055		1		0		1		0		0	0,0166	1	0,0064	1					1010011
15	p11=0,0048		1		0		1		0	0,0333	1		1		1	0,0047	1			10101111
16	p10=0,0042		1		0		1		0		1		1	0,0088	1		0	0,0032	0	101011100
17	p9=0,0037		1		0		1		0		1		1	0,0078	0	0,0036	1			10101101
18	p8=0,0033		1		0		1		0		1		1	0,0078	1	0,0036	0			10101110
19	p7=0,0029		1		0		1		0		1		0		1		0			10101010
20	p6=0,0026		1		0		1		0		1	0,0167	0		1	0,0026	1	0,0026	1	101010111
21	p5=0,0024		1		0		1		0		1	0,0147	0		1		1	0,0024	0	101010110
22	p4=0,0022		1		0		1		0		1		0		0	0,0022	0			10101000
23	p3=0,0020		1		0		1		0		1		0		0	0,0038	1	0,0020	1	101010011
24	p2=0,0018		1		0		1		0		1		0	0,0083	0		1	0,0018	0	101010010

Буква	Вероятность появления буквы	Кодовые слова	Число знаков в кодовом слове	Pi· li
A[1] (p24)	0,5000	0	1	0,5
A[2] (p23)	0,1667	111	3	0,50001
A[3] (p22)	0,0833	110	3	0,2500
A[4] (p21)	0,0500	1000	4	0,2000
A[5] (p 1)	0,0417	10011	5	0,2083
A[6] (p20)	0,0333	10010	5	0,1667
A[7] (p19)	0,0238	101111	6	0,1429
A[8] (p18)	0,0179	1011100	7	0,1250
A[9] (p17)	0,0139	101101	6	0,0833
A[10] (p16)	0,0111	101110	6	0,0667
A[11] (p15)	0,0091	1010011	7	0,0636
A[12] (p14)	0,0076	10100100	8	0,0606
A[13] (p13)	0,0064	1010001	7	0,0449
A[14] (p12)	0,0055	1010011	7	0,0385
A[15] (p11)	0,0048	10101111	8	0,0381
A[16] (p10)	0,0042	101011100	9	0,0375
A[17] (p9)	0,0037	10101101	8	0,0294
A[18] (p8)	0,0033	10101110	8	0,0261
A[19] (p7)	0,0029	10101010	8	0,0234
A[20] (p6)	0,0026	101010111	9	0,0237
A[21] (p5)	0,0024	101010110	9	0,0214
A[22] (p4)	0,0022	10101000	8	0,0173
A[23] (p3)	0,0020	101010011	9	0,0178
A[24] (p2)	0,0018	101010010	9	0,0163

 

123	Поделиться:

Воспользуйтесь поиском по сайту: