7 тақырып
Ақпаратты беру жылдамдығы және шусыз дискретті каналдың өту қабілеттілігі
Берілістің дискретті каналы деп дискретті сигналдарды беруге арналған ақпараттар жиынтығын айтады.
Хабар көзі 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
|
210-3
|
x3
|
0,1
|
1
|
1
|
11
|
210-3
|
RШФБ анықтаймыз
RШФБ =V2 H = H/2* = (1,16 бит/элем.)/1,310-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
|
310-3
|
x2,x1
|
0,14
|
1
|
0
|
1
|
|
|
|
101
|
310-3
|
x2,x3
|
0,07
|
1
|
1
|
0
|
0
|
|
|
1100
|
410-3
|
x3,x2
|
0,07
|
1
|
1
|
0
|
1
|
|
|
1101
|
410-3
|
x1,x1
|
0,04
|
1
|
1
|
1
|
0
|
|
|
1110
|
410-3
|
x1,x3
|
0,02
|
1
|
1
|
1
|
1
|
0
|
|
11110
|
510-3
|
x3,x1
|
0,02
|
1
|
1
|
1
|
1
|
1
|
0
|
111110
|
610-3
|
x3,x3
|
0,01
|
1
|
1
|
1
|
1
|
1
|
1
|
111111
|
610-3
|
RШФУ анықтаймыз
RШФУ =V3 H = H/3* = (1,16 бит/элем.)/1,16510-3 c. = 995 бит/c,
мұндағы V3 = 1/3*.
Достарыңызбен бөлісу: |