Есептеу техникасы және программалық қамсыздандыру мамандығы үшiн

Хабар көзі x₁, x₂, ...., x_n элементтерінен Х хабарлама каналына берілсін, ал хабарламаны алушы y₁, y₂, ...., y_n элементінен кейбір хабарламаны Y қабылдасын. Егер каналды шусыз қарастыратын болсақ, онда берілген және алынған хабарлама бір-біріне сәйкес келеді.

Суретте

V_и - бір қор көзінмен беретін символдың орташа жылдамдығы;

H_к- кодер шығысындағы бір символдың орташа энтропиясы;

V_к- кодермен бір символды берудің орташа жылдамдығы.

Шеннон бойынша келесі сипаттаманы қарастырамыз:

Хабарлама көзінің өнімділігі P = V_и H_и [бит/сек].

Канал бойынша ақпаратты беру жылдамдығы R = V_к H_к [бит/сек].

Каналдың өткізу қабілеттілігі- берілгени канал бойынша ақпаратты беру жылдамдығының максималды мүмкіншілігі C = max R [бит/сек] – тек канал сипаттамасы болып табылады және көз қасиетіне тәуелді емес.

Егер Р хабарлама көзінің өнімділігі С каналының өткізгіштік каналынан аспайтын болса, онда әрдайым ақпаратты беру жылдамдығы R қанша қажет болса соншалықты С-ға жақындайды, яғни С - R =  - аз шама

Кері тұжырымдау

Егер өнімділігі P  С, онда дискретті канал бойынша хабарламаны беруді қамтамасыз ететін кодттау әдісі болмайды.

Теоремадан сипаттаманың фундаментальды рольі- каналдың өткізгіштік қабілеттілігі. Ол бұл сипаттама канал бойынша (R  C) ақпаратты беру жылдамдығының мүмкін және мүмкін емемс шектерін анықтайды.

Теоремада кодттау әдісі келтірілмеген, бірақ R-дің С–ға жақындау мүмкіндігі көрсетілген.

R-ді С–ға жақындататын хабарламаның кодттау әдісі оптималды кодттау деп аталады.
Шеннону – Фано бойынша дискретті хабарламаны оптималды кодттау

x₁, x₂, ...., x_n элементтерінен Х хабараламасы кодттауға ұшырайды. Бұл операция келесі ретпен іске асырылады:

1. Бастарқы хабарлама элементтері Х ықтималдылықтың кему шегі бойынша реттеледі, яғни p(x₁^у)  p(x₂^у)  ....  p(x_n^у), нәтижесінде мынаны аламыз X_у  x₁^у, x₂^у, ...., x_n^у .

2. Элементтер реттелген тізбегімен екі топқа бөлініледі, ол топтардың суммалық ықтималдылығы мүмкіншілігінше тең болуы керек. Бір топқа 0 символы, ал екінші топқа 1 символы беріледі.

3. Әр топта бір элемент қалмайынша екі топқа бөлу жалғаса береді.

Мысал.

Шеннон-Фано коды тең өлшемді болып саналмайды, яғни әр-түрлі символға әр-түрлі ұзындықтағы кодттық комбинация сәйкескеледі.

Қабылданағн хабарлама мысалы 110 0 111 10 111 0 0 0 10 10

c d b a b d d d a a

Хабарламаны кодттауға мысалды үш түрде қарастырайық
X с элементами x₁,x₂,x₃ элементтерімен Х үштік хабарлама көзі болсын

Элементте	x1	x2	x3
p(xi)	0,2	0,7	0,1

Хабарлама екілік канал бойынша беріледі, яғни x_i элементі тек 1 немесе 0 шамаларын ғана қабылдайды.

V_и = 1000 дв.симв./сек;

V_к = 1000 дв.симв./сек;

С = V_к H_max = 1000 дв.симв./сек  1 бит/ дв.симв. = 1000 бит/сек .

Ескерте кетсек, кодттаудың кез-келген әдіс тиімділігі С каналының өткізгіштік қабілеті бойынша және R каналы бойынша ақпараттың берілу жылдамдығын салыстыру негізінде анықталады. R неғұрлдым С-ға жақын болса, соғұрлым ақпартты кодттау жақсы.

Код маңыздылығын анықтаймыз n = ] lb 3 [ = 2

x₁ = 00, x₂ = 01 x₃ = 10 болсын делік;

 = 10^-3 с-бір элементке сәйкес, кодттық комбинация ұзақтығы. R_р.обд анықтаймыз

R_р.обд = V₁ H = 500 элем./c  1,16 бит/элем. = 580 бит/c .

R_р.обд < C болғандықтан кодттаудың мұндай әдісі тиімсіз

2. Шеннона – Фано әдісімен бекітусіз хабарламаны кодттаймыз.

R_ШФБ анықтаймыз

R_ШФБ =V₂ H = H/₂^* = (1,16 бит/элем.)/1,310^-3 c. = 890 бит/c,

мұндағыV₂ = 1/₂^*.

3. Шеннона – Фано әдісімен бекітумен хабарламаны кодттаймыз, яғни кодттау жеке элементтер бойынша емес, көрші элементтер тобымен жүргізіледі (2 элементтік, 3 элементтік топтардан)

Көрші екі элементтерден тұратын топты қарастырамыз

Топтар xi,xj	Ықти-ық p(xi,xj)	Бөлу						Кодттық комбинация	i, c
x2,x2	0,49	0						0	10-3
x1,x2	0,14	1	0	0				100	310-3
x2,x1	0,14	1	0	1				101	310-3
x2,x3	0,07	1	1	0	0			1100	410-3
x3,x2	0,07	1	1	0	1			1101	410-3
x1,x1	0,04	1	1	1	0			1110	410-3
x1,x3	0,02	1	1	1	1	0		11110	510-3
x3,x1	0,02	1	1	1	1	1	0	111110	610-3
x3,x3	0,01	1	1	1	1	1	1	111111	610-3

R_ШФУ анықтаймыз