АҚПАРАТТЫ БЕРУ ЖЫЛДАМДЫҒЫ ЖӘНЕ ШУСЫЗ ДИСКРЕТТІ КАНАЛДЫҢ ӨТУ ҚАБІЛЕТТІЛІГІ

Берілістің дискретті каналы деп дискретті сигналдарды беруге арналған ақпараттар жиынтығын айтады. 
Хабар көзі x1, x2, ...., xn элементтерінен Х хабарлама каналына берілсін, ал хабарламаны алушы y1, y2, ...., yn элементінен кейбір хабарламаны Y қабылдасын. Егер каналды шусыз қарастыратын болсақ, онда берілген және алынған хабарлама бір-біріне сәйкес келеді.
Келесі құрылымдық сұлбаны қарастырайық
 
Суретте
Hи – бір символ көзінің орташа энтропиясы;
Vи - бір қор көзінмен беретін  символдың орташа жылдамдығы;
Hк- кодер шығысындағы бір символдың орташа энтропиясы;
Vк- кодермен бір символды берудің орташа жылдамдығы.
Шеннон бойынша келесі сипаттаманы қарастырамыз:
Хабарлама көзінің өнімділігі P = Vи Hи [бит/сек].
Канал бойынша ақпаратты беру жылдамдығы R = Vк Hк [бит/сек].
Каналдың өткізу қабілеттілігі- берілгени канал бойынша ақпаратты беру жылдамдығының максималды мүмкіншілігі C = max R [бит/сек] – тек канал сипаттамасы болып табылады және көз қасиетіне тәуелді емес.
 
Шусыз каналдың өткізгіштік қасиеті жөнінде Шеннон теоремасы
Егер Р хабарлама көзінің өнімділігі С каналының өткізгіштік каналынан аспайтын болса, онда әрдайым ақпаратты беру жылдамдығы R қанша қажет болса соншалықты С-ға жақындайды, яғни С - R =  - аз шама 
Кері тұжырымдау 
Егер өнімділігі P  С, онда дискретті канал бойынша хабарламаны беруді қамтамасыз ететін кодттау әдісі болмайды.
Теоремадан сипаттаманың фундаментальды рольі- каналдың өткізгіштік қабілеттілігі. Ол бұл сипаттама канал бойынша  (R  C) ақпаратты беру жылдамдығының мүмкін және мүмкін емемс шектерін анықтайды. 
Теоремада кодттау әдісі келтірілмеген, бірақ R-дің С–ға жақындау мүмкіндігі көрсетілген. 
 R-ді С–ға жақындататын хабарламаның кодттау әдісі оптималды кодттау деп аталады.

Шеннону – Фано бойынша дискретті хабарламаны оптималды кодттау
x1, x2, ...., xn элементтерінен Х хабараламасы кодттауға ұшырайды. Бұл операция келесі ретпен іске асырылады:
1. Бастарқы хабарлама элементтері Х ықтималдылықтың кему шегі бойынша реттеледі, яғни p(x1у)  p(x2у)  ....  p(xnу), нәтижесінде мынаны аламыз Xу  x1у, x2у, ...., xnу .
2. Элементтер реттелген тізбегімен екі топқа бөлініледі, ол топтардың суммалық ықтималдылығы мүмкіншілігінше тең болуы керек. Бір топқа 0 символы, ал екінші топқа 1 символы беріледі.
3. Әр топта бір элемент қалмайынша екі топқа бөлу жалғаса береді.
Мысал.

X    p(xi)    Xу    pу(xi)    Бөлу    Коды
a    0,3    D    0,4     0        0
b    0,1    A    0,3     1     0         10
c    0,2    C    0,2     1     1     0    110
d    0,4    B    0,1     1     1     1    111

    Шеннон-Фано коды тең өлшемді болып саналмайды, яғни әр-түрлі символға әр-түрлі ұзындықтағы кодттық комбинация сәйкескеледі.
    Қабылданағн хабарлама мысалы 110 0 111 10 111 0 0 0 10 10
                                             c   d   b   a    b  d d d  a   a
Хабарламаны кодттауға мысалды үш түрде қарастырайық

X с элементами x1,x2,x3 элементтерімен Х үштік хабарлама көзі болсын

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

Хабарлама екілік канал бойынша беріледі, яғни xi элементі тек 1 немесе 0 шамаларын ғана қабылдайды.
Vи = 1000 дв.симв./сек; 
Vк = 1000 дв.симв./сек;  
С = Vк Hmax = 1000 дв.симв./сек • 1 бит/ дв.симв. = 1000 бит/сек .
Ескерте кетсек, кодттаудың кез-келген әдіс тиімділігі С каналының өткізгіштік қабілеті бойынша және R каналы бойынша ақпараттың берілу жылдамдығын салыстыру негізінде анықталады. R неғұрлдым С-ға жақын болса, соғұрлым ақпартты кодттау жақсы.

1. Хабарламаны тең өлшемді екілік кодпен кодттаймыз.
Код маңыздылығын анықтаймыз n = ] lb 3 [ = 2
x1 = 00, x2 = 01 x3 = 10 болсын делік;
 = 10-3 с-бір элементке сәйкес, кодттық комбинация ұзақтығы. Rр.обд  анықтаймыз
V1 = 1/* = 500 элем./сек;  
 
Rр.обд = V1 H = 500 элем./c • 1,16 бит/элем. = 580 бит/c .
 Rр.обд <  C болғандықтан кодттаудың мұндай әдісі тиімсіз
2. Шеннона – Фано әдісімен бекітусіз хабарламаны кодттаймыз.

Эл-ты 
(xi)у    p(xi)у    Бөлу    Кодттыкомбин
    
i, c
x2    0,7    0        0    10-3
x1    0,2    1    0    10    2•10-3
x3    0,1    1    1    11    2•10-3

RШФБ  анықтаймыз
 
RШФБ =V2 H = H/2* = (1,16 бит/элем.)/1,3•10-3 c. = 890 бит/c, 
мұндағыV2 = 1/2*.
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ШФУ анықтаймыз
 

RШФУ =V3 H = H/3* = (1,16 бит/элем.)/1,165•10-3 c. = 995 бит/c,

мұндағы  V3 = 1/3*.

Хаффман әдісі бойынша дискретті хабарламаны оптималды кодттау
Әдіс келесілермен қорытындыланылады.
Қор көзі алфовитінің элементтері олардың ықтималдылықтарының кему реті бойынша орналасады.
Одан кейін екі төменгі элемент біріктіріліп жаңа іріктендірілген элемент шығады, ол алфовитте қосындылық ықтималдылығына сәйкес орналасады. 
Соңғы екі ықтималдылық қосындысы бірге тең болмайынша 2 п. Орындау жалғаса береді.
Әр біріктіру кезінде элементке  0 санын береміз, біріктірілген қос элементтің жоғарғы жағында орналасқан және 1 санын егер ол төменгі жақта орналасса. 
Алынылып отырған элементтің біріктірілген саны оның сәйкес келетін кодттық комбинациясына тең. Мұндай түрде салынған код Хаффман коды деп аталады.

Хаффмена кодының құрылуына мысал қарастырамыз.

Эл-нт    Ықт-ық    Біріктірілген символдар ықтималдылығы    Код
xi    p(xi)    1    2    3    4    5    6    7    8    
                                    1    
                                0,57        
                            0,43            
x1    0,29                                    00
                        0,28                
x2    0,23                                    10
                    0,20                    
                0,15                        
x3    0,13                                    011
x4    0,11                                    110
x5    0,09                                    111
x6    0,08                                    0100
            0,07                            
x7    0,04                                    01010
        0,03                                
x8    0,02                                    010110
x9    0,01                                    010111