Қаттау әдісімен сығу коэффициенті:
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.СЫЗЫҚТЫҚ КОДТАРҒА МАТЕМАТИКАЛЫҚ КІРІСПЕ. ХЭММИНГ ШЕКАРАЛАРЫН КӨРСЕТІҢІЗ. ХЭММИНГ КОДЫНА МЫСАЛ КЕЛТІРІҢІЗ.
Каналдағы қателік
Ақпарат көзі
Қабылдағыш
x
Кей жағдайларда 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 – алатын санымыз
|
25. ЦИКЛДІК КОДТАР. ЦИКЛДІК КОДТАРҒА МАТЕМАТИКАЛЫҚ КІРІСПЕ.
Циклді кодтар. Кез келген екілік жүйедегі топталған кодтарды әр түрлі m жолдан тұратын n бағаналы матрицамен жазуға болады. Немесе оған керісінше кез келген п орынды кодтық қомбинациядан тұратын m жолдың жиынтығынан топталған кодтарды құрушы матрица деп қарауға болады.
Мұндай матрицаның барлык жолдарының ішінен қосымша циклдік қасиеті бар матрица құратын жолдарды бөліп шығаруға болады.
Мұндай матрицаның барлық жолдарын осы кодтың құрушы деп аталатын бір комбинациясын циклдік ығыстыру арқылы алуға болады. Осындай шартты қанағаттандыратын кодтарды циклдік кодтар деп атайды.
Ығыстыру, негізінен, оңнан солға қарай жүргізіледі. Мысалы: 0100101, 1001010,0010101, 0101010,1010100, т. с.с. Топталған әр түрлі кодтардың ішінде циклдіге жататындары көп болмайды. Сондықтан олармен берілетін мәліметтер көлемі жалпы топталған кодтармен берілетін мәліметтер көлемінен аз.
Циклді кодтарды жазғанда, оларды n дәрежесіндегі көпмүше түрінде жазу ыңғайлы.
Мысалы,
10101 -ді G(x) = 1 * х4 + 0 * х3 + 1 * х2 + 0 * х1 + 1 * х0 = х4 + х2 + 1 деп жазуға болады.
Сөйтіп кодтық комбинациямен жасалатын жұмыс көпмүшемен жасалатын жұмысқа әкелінеді.
Кодтық комбинацияны құратын көпмүшені бір орынға ығыстырудың орнына оны х-ке көбейтеді.
Мысалы, 001101...0011010 орнына (х3 + х2 + 1)х = х4 + х3 + х.
Осы екі комбинацияны "екілік модульмен" қосқанда алынатын комбинацияны х3 + х2 + 1 көпмүшеcін (х + 1)-ге көбейтіп алуға болады.
(х3 + х2 + 1) • (х + 1) = х4 + х2 + х + 1.
Сонымен, кода құрушы көпмүшені белгілеп алғаннан кейін циклді коданың кез келген рұқсат етілген комбинациясын құрушы көпмүшені басқа бір көпмүшеге көбейту арқылы алуга болады.
Циклді кодтың кез келген көпмүшесі құрушы көпмүшеге қалдықсыз бөлінуі керек. Циклді кодтың осы қасиеті қатені табуға, ал егер қалдықсыз бөлінбесе, сол қалдықтың түріне қарап, қатенің орнын тауып түзетуге болады.
Көпмүшелерді көбейту мен бөлу кері байланысты ығыстырушы тіркегіштерде оңай орындалатын болғандықтан, циклді кодаларды қолдану өте кең тараған. Циклді код туғызушы немесе өндіруші деп аталатын мүшелерімен беріледі. Барлық мәліметті таратуға арналған көпмүшелер осы өндіруші немесе туғызушы көпмүшеге қалдықсыз бөлінуі керек.
МЫСАЛ
Циклдік кодтың тексеру матрицасы
Есеп. Циклдік кодтың кодтық комбинациясын жазу керек, егер туынды полином P(x) = x³+x²+1
Ақпарат көзінен түскен кодтық комбинация – парольдің соңғы екі цифры.
шешімі:
N = 23;
2310 = 101112
Бұл санды полином ретінде жазсақ:
A(x) = 1*x4+0*x3+1*x2+1*x1+1*x0 = x4+x2+x+1
1) r=3 болсын, онда:
Екілік кодта:
A(x)*x3 = (x4+x2+x+1)*x3 = x7+x5+x4+x3
A(x) = 10111000
2) Бөлу операциясы
3) Кодерден өткеннен кейін сигнал мынаған тең:
|
26. БӨГЕУІЛГЕ ТӨЗІМДІ КОДТАР ЖӘНЕ ОЛАРҒА ҚОЙЫЛАТЫН ТАЛАПТАРДЫ АТАҢЫЗ. МЫСАЛ КЕЛТІРІҢІЗ.
Ақпаратты беру
Ақпаратты беру оны кеңістікте тарату үшін қажет.
Ақпаратты берудің ақпараттық үдерістерінің сұлбасы
e
Канал
Ақпарат көзі
Кодтау құрылғысы
Қабылдағыш
Декодтау құрылғысы
Бөгеуіл
Байланыс каналы ешқашан мінсіз болмайды, себебі бөгеуілдер әрқашан кедергі жасайды. Байланыс каналдарындағы бөгеуілдер әр түрлі себептерге байланысты пайда болады, бірақ олардың берілетін ақпаратқа әсерінің нәтижесі біреу - ақпаратты бұрмалау.
Бөгеуілге орнықтылық дегеніміз байланыс каналдарындағы бөгеуілдерге қарамай ақпаратты қабылдауды жүзеге асыратын жүйенің қабілеттілігі.
Ақпараттық жүйелерді талдау кезінде жүйенің бөгеуілге орнықтылығының екі түрі ажыратылып көрсетіледі: статикалық және динамикалық. Статикалық бөгеуілге орнықтылық жалған сигналдардың орта санымен бағаланады, ал динамикалық бөгеуілге орнықтылық жалған командалардың орташа санымен бағаланады.
Қазіргі кезде дискретті байланыс каналдарына қызығушылық танытылуда. Бұл жүйелердегі берілетін дискретті хабарламалар кодтауға келеді.
Бөгеуілге орнықты кодтың қарапайым кодтан айырмашылығы, байланыс каналдарында рұқсат етілген разрядтар санынын тұратын кодтық комбинациялар беріледі, ал қолданылмаған кодтық комбинациялар рұқсат етілмеген деп аталады.
Байланыс арналарында қосымша элементтерді пайдалану
арқылы берілетін ақпараттың дәлдігін жоғарылату үшін қолданы
латын коданы kедергіге төзімді кодтар деп атайды. Бөгеуілге төзімді кодтар бірінші ретті кодтарға қосымша разрядтар косу арқылы жасалады. Қосымша разрядтар байланыс арналарындағы бөгеуіл
дердің пайда болу зандылығына байланысты қосылып, сол бөгеуілдердің әсерінен пайда болатын қателерді жою үшін пайдаланылады. Қосымша разрядтар кодтарды күрделендіреді. Дәлдікті жоғарылату дәрежесі бөгеуілге төзімді кодтар күрделілігіне байланысты. Дәлдікті неғұрлым жоғары дөрежеге көтеру үшін бөгеуілге төзімді кодтар соғұрлым күрделі болу керек. Сөйтіп акпаратты тарату дәлдігін жоғарылату әдістерінің әсері байланыс арналарындағы қателердің жалпы саны мен олардың таратылу заңдылығына байланысты болады.Егер байланыс арналарындағы қателер біріне-бірі байланыссыз, яғни корреляцияланбаған болса және бір элемент қатесінің ықтималдығы берілсе, онда қалған қателер мәліметтерін анықтау қиын емес. Тәжірибеде кездесетін байланыс арналарында кателер корреляцияланған болады. Қателердің бір түрі
— қателердің топталып келуі. Мұндай топталып келетін қателерді "пакеттеліп келеді" деп те айтады. Қателер тобы немесе пакеті деп бірінші бұзылған элементтен бастап соңғы бұзылған элементке
дейінгі элементтер тізбегін айтады. Осы элементтер санын пакет ұзындығы
деп атайды. Екі пакет арасындағы бұзылмаған элементтер санынқорғаныс аралығы дейді. Қорғаныс аралығындағы элементтер саны пакет ұзындығынан бірнеше есе артық болу керек.
Бөгеуілге төзімді кодтар қолданылуына жөне құрылуына байланысты бірнеше түрге бөлінеді.
Екі топқа бөлінеді: Жүйеленген түзетуші кодалық топта кез келген екі кодалық комбинацияны "екілік модульмен" қосса, сол коданың үшіпші комбинациясы шығады. Жүйеленген топта ақпараттық орындарға ақпараттық символдар орналасады да, олардың белгілі бір комбинациясын "екілік модульмен" қоскан тексеруші символдар тексеруші орындарға орналасады.Жүйеленген кодалар циклденген жөне циклденбеген хэмминг кодаларына бөлінеді. Циклденген кодада символдарды белгілі бір циклмен ауыстыру арқылы келесі
комбинация алынады.
Жүйеленбеген топта "екілік модульмен" қосқанда үшінші
комбинация шығатын қасиет болмайды. Жүйеленбеген топта символдардың тексеру қосындылары пайдаланылады. Яғни,
тексеруші символ белгілі бір ақпараттық символдардың қосындысы болады.
үзіліссіз тізбекті кодалар
Үзіліссіз немесе тізбекті кодалау кезінде кодалау және кодадан
шығару үзіліссіз жүргізіледі. Мұнда түзетуші элементтер ақпараттық элементтерге тәуелді болып, сол ақпараттық элементтердің
араларында орналасады.
топталған немесе блокталған кодалар
Топталған немесе блокталған кодалау кезінде ақпараттық тізбек кодалык комбинацияларға (блоктарға немесе топтарға) бөлініп, сол топтар бөлек-бөлек кодаланып, кабылдау орнында бөлек-бөлек
кодадан шығарылады.
Топталған кода екі түрде кездеседі:
бөлінетін (ақпараттық және текесеруші символдардың әрқайсысының бөлек орындары болады)
бөлінбейтін. (аралас орналасады)
|
27. ШЕННОН-ФАНО КОДЫН ҚҰРУ ҚАҒИДАЛАРЫНА ШОЛУ ЖАСАҢЫЗ. ШЕННОН-ФАНО КОДЫНА МЫСАЛ КЕЛТІРІҢІЗ.
Шеннон-Фано алгоритмі— американдық ғалымдар Шеннон және Р.Фано алғаш рет жасаған сығу алгоритмі. Шеннон-Фано алгоритмі хабарламалардың артықтығын қолданады.
Шеннон-Фано алгоритмі әдісі Хаффман алгоритміне өте ұқсас. Алгоритм ұзын айнымалы кодын қолданады: жиі кездесетін символ қысқа кодпен кодталады, сирек кездесетін символ ұзын кодпен кодталады. Шеннон-Фано коды префиксті болып табылады, ешбір кодтық сөз басқа кодтық сөздің префиксі болып табылмайды. Бұл қасиет кез-келген кодтық сөзді декодтауға мүмкіндік береді.
Шеннон-Фано коды ағаш түрінде тұрғызылады. Ағаштың тұрғызылуы түбірінен басталады.
Шеннона-Фано әдісі
a, b, c и d төрт символдан тұратын әліпби берілсін.
Әр символды кодтау үшін 2 бит жеткілікті. Мысал: a – 00, b – 01, c – 10, d – 11.
Сонымен ababcaacdbхабарламасы 20 битпен кодталады.
ababcaacdb хабарламасы бойынша әр символдың үлесін анықтайық және оларды үлестің кемуі бойынша кестеге орналастыру керек.
Символ
|
a
|
b
|
c
|
d
| |
|
Мәтіндегі үлесі
|
4/10
|
3/10
|
2/10
|
1/10
|
Үлестердің қосындысы әр бөлікте аз ерекшеленетіндей етіп, кестені екіге бөлеміз. Бірінші бөліктегі символдар коды 0-ден, ал екіншісі 1-ден басталсын:
Символ
|
a
|
b
|
c
|
d
| |
|
Мәтіндегі үлесі
|
4/10
|
3/10
|
2/10
|
1/10
|
Үлестер қосындысы
|
4/10
|
6/10
|
Кодтың бірінші цифры
|
0
|
1
| |
Скачать 2.19 Mb.