Үзіліссіз аргументтің үзіліссіз функ 2. Үзіліссіз аргументтің дискретті функ
3.Дискретті аргументтің үзіліссіз функ 4. Дискретті аргументтің дискретті функ
|
Дискретті каналдар дегеніміз дискретті сигналдарды ұзатудың құрылымдар жиыны.
Стационарлы дискретті канал төрт шартты ықтималдықтармен анықталады:
p(0/0), p(1/0), p(0/1), p(1/1).
0 0
1 1
p(0/0), p(1/1) – символдардың бұзылмай өту ықтималдықтары,
p(1/0), p(0/1) - символдардың бұзылып өту ықтималдықтары.
Егер шартты ықтималдықтары p(0/1)≈p(1/0)=q тең болса, онда канал екілік симметриялы болады. Басқа жағдайда, канал симметриялы емес болады.
Дискретті каналдағы жылдамдықтар екіге бөлінеді: техникалық және ақпараттық.
23. ХАФФМАН АҒАШЫ МЕН ХАФФМАН КОДЫН ТҮСІНДІРІҢІЗ. МЫСАЛ КЕЛТІРІҢІЗ. СЫҒУ КОЭФФИЦИЕНТІН ЕСЕПТЕУ ЖОЛЫН КӨРСЕТІҢІЗ.
Хаффман алгоритмі
Сығу дәрежесін жақсарту үшін жиі қайталанатын символдарды қысқа кодпен, ал сирек кездесетіндерді ұзын кодпен алмастыру керек. Бүл әдіс идеясын ұсынған - Д. Хаффман (1952 жыл).
Хаффман алгоритмінің көмегімен деректерді сығу: кездесетін символдар жиілігі есептелінеді, содан кейін Хаффман кодтау ағашы тұрғызылады. Кодтау ағашы бойынша символар коды жасалынады.
Хаффман ағашын тұрғызу алгоритмі
Алғашқы символдар бос түйіндер тізімін құрайды. Әр түйіннің алғашқы хабарламадағы символдар санына тең салмағы бар.
Тізімнен ең кіші салмағы бар екі бос түйін таңдалады.
Олардың салмақтарының қосындысына тең салмағы бар «ата-ана» түйіні құрылады, ол «ұрпақтарымен» доға арқылы байланысады.
«Ата-анадан» шығатын бір доғаға 1, екіншісіне 0 қойылады.
«Ата-ана» бос түйінді тізімге қосылады, ал оның «ұрпақтары» тізімнен жойылады.
Тізімдегі қадам тек бір бос түйін қалғанша қайталана береді. Ол ағаштың басы (тамыры) болып есептелінеді.
Мысалы. «КОЛ_ОКОЛО_КОЛОКОЛА» мәтіні үшін Хаффман ағашын тұрғызу және префикстік кодты алу:
Төбелерін қоссақ, шығатыны: 3+7+11+18=39
Мәтін коды 39/бит немесе 5 байт.
Сығу коэффициенті
18/5 = 3,6.
Сығылған деректерді қалпына келтіру үшін Хаффман ағашын қолданамыз.
Хаффман коды префиксті болып табылады, себебі әр символ коды басқа символдың кодының басы болып саналмайды.
Хаффман ағашын тұрғызу: «на_дворе_трава,_на_ траве_дрова»
|
а
|
в
|
д
|
,
|
е
|
н
|
р
|
о
|
т
|
_
|
6
|
4
|
2
|
1
|
2
|
2
|
4
|
2
|
2
|
5
|
3 4 4
0 1 0 1 0 1
а
|
в
|
д
|
,
|
е
|
н
|
р
|
о
|
т
|
_
|
6
|
4
|
2
|
1
|
2
|
2
|
4
|
2
|
2
|
5
|
7 8
0 1 0 1 4
3 4
0 1 0 1 0 1
а
|
в
|
д
|
,
|
е
|
н
|
р
|
о
|
т
|
_
|
6
|
4
|
2
|
1
|
2
|
2
|
4
|
2
|
2
|
5
|
7 8 9
0 1 0 1 0 1
3 4 4
0 1 0 1 0 1
а
|
в
|
д
|
,
|
е
|
н
|
р
|
о
|
т
|
_
|
6
|
4
|
2
|
1
|
2
|
2
|
4
|
2
|
2
|
5
|
13 17
1 0 1
7 8 9
0 0 1 0 1 0 1
3 4 4
0 1 0 1 0 1
а
|
в
|
д
|
,
|
е
|
н
|
р
|
о
|
т
|
_
|
6
|
4
|
2
|
1
|
2
|
2
|
4
|
2
|
2
|
5
|
30
0 1
13 17
1 0 1
7 8 9
0 0 1 0 1 0 1
3 4 4
0 1 0 1 0 1
а
|
в
|
д
|
,
|
е
|
н
|
р
|
о
|
т
|
_
|
6
|
4
|
2
|
1
|
2
|
2
|
4
|
2
|
2
|
5
|
а
|
в
|
д
|
,
|
е
|
н
|
р
|
о
|
т
|
_
|
6
|
4
|
2
|
1
|
2
|
2
|
4
|
2
|
2
|
5
|
00
|
010
|
0110
|
0111
|
1000
|
1001
|
101
|
1100
|
1101
|
111
|
Қаттау әдісімен сығу коэффициенті:
10 символ - 4 бит. Бүкіл мәтін– 120 бит.
Хаффман алгоритмі бойынша: 2*6+3*4+4*2+4*1+4*2+4*2+3*4+4*2+4*2+3*5=95 бит
120/95=1,26
|
24.СЫЗЫҚТЫҚ КОДТАРҒА МАТЕМАТИКАЛЫҚ КІРІСПЕ. ХЭММИНГ ШЕКАРАЛАРЫН КӨРСЕТІҢІЗ. ХЭММИНГ КОДЫНА МЫСАЛ КЕЛТІРІҢІЗ.
Каналдағы қателік
Кей жағдайларда 1 мен 0 орны ауысып кетуі мүмкін.
Хэмминг коды
- (n, k) – код
- n = 2m – 1
- m тексеру разряды
k=n - m = 2m – 1-m ақпараттық разряд
жүйелік код
dmin= 3, t = 1
(7,4), (15, 11), (31,26) және т.б.
Мысал
v
Кодталған хабарламаны алайық:
b28 b27 b26 b25 b24 b23 b22
B21 b20 b19 b18 b17 b16 b15
B14 b13 b12 b11 b10 b9 b8
b7 b6 b5 b4 b3 b2 b1
b1, b2, b4, b8, b16 тексеру разряды, ал қалғандары ақпараттық разрядтар
Ақпараттық разрядқа берілген кодты ретімен орналастырамыз:
b3 =1, b5 = 0, b6 = 0, b7=1,
b9=0, b10 =0, b11=0, b12=1,
b13= 1, b14=1, b15=0, b17=1,
b18=1, b19=1, b20=1, b21=0,
b22=0, b23=0, b24=0, b25=0,
b26=0, b27=0, b28=0.
Тексеру разрядының мәндері:
Ол үшін мына жиындарды енгіземіз:
V1 = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27… - бірінші разряд
тары 1-ге тең
V2 = 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27… - екінші разрядтары 1-ге тең
V3 = 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28… - үшінші разрядтары 1-ге тең
V4 = 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28… - төртінші разрядтары 1-ге тең
V5 = 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 … бесінші разрядтары 1-ге тең
b3 =1, b5 = 0, b6 = 0, b7=1,
b9=0, b10 =0, b11=0, b12=1,
b13= 1, b14=1, b15=0, b17=1,
b18=1, b19=1, b20=1, b21=0,
b22=0, b23=0, b24=0, b25=0,
b26=0, b27=0, b28=0.
Онда mod2 бойынша
b1 = b3+b5+b7+b9+b11+b13+b15+b17+b19+b21+b23+b25+b27 = 1
b2 = b3+b6+b7+b10+b11+b14+ b15+ b18+ b19+ b22+ b23+ b26+ b27 = 1
b4 = b5+b6+b7 +b12+b13+ b14+ b15+ b20 +b21+b22+b23+b28 = 1
b8 = b9+b10+b11+b12+b13+b14+b15+b24+b25+b26+b27+b28 = 1
b16 = b17+b18+b19+b20+b21+b22+b23+b24+b25+b26+b27+b28 = 0
Енді тексерк коды мен ақпараттық кодтарды біріктіреміз:
Жауабы: 1111 0011 0001 1100 1111 0000 0000.
Мысал2: Хэмминг кодын қолданып, хабарламадағы қатені табу.
1) 1111 1011 0010 1100 1101 1100 110
Шешілуі. Хабарлама 27 символдан тұрады, 22 ақпараттық, ал 5 тексеру разрядтары.
Бұл разрядтар b1 = 1, b2 = 1, b4 = 1, b8 = 1, b16=0.
Ол үшін мына жиындарды енгіземіз:
V1 = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27… - бірінші разряд
тары 1-ге тең
V2 = 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27… - екінші разрядтары 1-ге тең
V3 = = 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23 - үшінші разрядтары
1-ге тең
V4 = 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27 - төртінші разрядтары
1-ге тең
V5 = 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27 … бесінші разряд
тары 1-ге тең
Қатені табатын J есептейміз:
J санының разрядтарын анықтаймыз:
j1 = b1 + b3+b5+b7+b9+b11+b13+b15+b17+b19+b21+b23+b25+b27 = 1
j2 = b2+ b3+b6+b7+b10+b11+b14+ b15+ b18+ b19+ b22+ b23+ b26+ b27= 0
j3 = b4+ b5+b6+b7 +b12+b13+ b14+ b15+ b20 +b21+b22+b23 = 0
j4 = b9+b10+b11+b12+b13+b14+b15+b24+b25+b26+b27 = 0,
j5 = b16+ 17+b18+b19+b20+b21+b22+b23+b24+b25+b26+b27 = 1
Яғни
J=10001 = 17 (ондық санау жүйесіндегі)
17 разрядта қате бар, 1-ді 0 –ге ауыстырамыз.
1111 1011 0010 1100 1101 1100 110
Аламыз:
1111 1011 0010 1100 0101 1100 110
Тексеру разрятарын алып тастасақ
1101 0010 1100 1011 1001 10 – алатын санымыз
|
Достарыңызбен бөлісу: |
