Лекция Құпиялау теориясы Кодталу теориясының негізгі ұғымдары және анықтамалары Алфавиттік кодтталу. Оптимал кодталу. Қателерді табу және өңдеу кодттары
Логикалық – комбинаторикалық бейнелеу
жүктеу/скачать 198,4 Kb.
|
15-лекция
- Бұл бет үшін навигация:
- «Шығыс»тағы ақпараттар кодының коррекциясы
- 2. Алфавиттік кодталу Анықтама.
| Логикалық – комбинаторикалық бейнелеу – әдетте {0,1} жиындағы қателіктердің санын шектеулермен көрсетуге байланысты.
Статистикалық бейнелеу – қайнар көздердің ықтималдық сипаттамаларының берілуімен орындалады. «Шығыс» тағы ақпараттар коды желінің теңбе-тең жағдайында Ψ¢ = Ψ алфавитінде өздігінен кейбір сөздер жиынын білдіреді. Бірақта кедергі көзі В¢ ¹ В болуына алып келуі мүмкін. ²Шығыс²тағы ақпараттар өздігінен кейбір G алфавитіндегі сөзді білдіреді. Желінің тепе-теңдік жағдайында, яғни ақпаратты жеткізу кезінде G = W болады. «Кірісте»гі ақпараттар кодынан «шығыстағы» ақпараттарға өту екі ауыстыру арқылы орындалады. «Шығыс»тағы ақпараттар кодының коррекциясы. Бұл ауыстыру тек арнайы ақпарат кодтары үшін ғана мүмкін. Ал, егер біз ақпараттарды жеткізу жағдайындағы жұмысқағана ие болсақ, онда өту В¢ тан В ға орындалады. Декодталу. Ол коррекциядан кейінгі шығыстағы ақпараттар кодынан алынған кодтан «шығыс»тағы ақпараттарға өздігінен өтуді бейнелейді. Тағыда, декодталу барлық кодтарғада мүмкін бола бермейді, ал ол тек арнайы ақпараттар коды үшін орындалуы мүмкін. 2. Алфавиттік кодталу Анықтама. Әр түрлі ақпараттарды жіберу, қайта істеу және сақтауға арналған шартты белгілер жүйесі құпия (код) деп айтылады. Құпиялау теориясының зерттеуі болып 0,1,2,...,r – 1 (мұнда r кейбір бүтін оң сандар, дербес түрде r = 2) сандар тізбектеріндегі жиындардың шекті немесе ерікті нысандар жиынындағы санаулы кескіндеулер есептеледі. Осындай кескіндеулер құпияластыру (кодталу) деп айтылады. Құпиялау теориясының көп мәселелері кезектегідей тұжырымдар арқылы сипатталады. Мұнда, берілген нысандар объектісі үшін белгілі бір қасиеттерге ие болған құпиялау класы қарастырылады. Қарастырылып жатқан кластан алдынала берілгендік мағынасында оптимал болған құпиялау жүйесін құру талап етіледі. Әдетте құпиялаудың оптималдық критерисі кодтардың ұзындығын минимизациялауға байланысты. Сонымен бірге талап етілетін құпиялаудың қасиеттері жеткілікті дәрежеде әр түрлі болуы мүмкін. Осындай қасиеттерге: бірмәнді кері кескіндеудің бар екендігі, құпияны ашу (декодталу) мүмкіндігі, декотдалу кезіндегі әр түрлі типтегі қателіктерді өңдеу мүмкіндіктері, қарапайым іске асыру (қарапайым алгоритм мүмкіндігі) және т.б. кіреді. Айталық А – еркін алфавит берілген болсын. Алфавиттің элементтерін әріптер, ал осы әріптерден құралған шекті тізбекті А жиындағы «сөз» деп айтамыз. α сөздің ұзындығын (әріптер саны) φ(α) арқылы белгілейміз, ал 0 ұзындықтағы сөзді (бос сөз) λ ретінде белгілеуге келісеміз. α1 және α2 сөздердің бірлігін α1α2 арқылы және бір түрлі n әріптен біріккен α сөзді αn(α0=λ) арқылы белгілейміз. Айталық U A дағы кез келген сөздер жиыны болсын. Un (n = 0,1,…,) арқылы Аn дегі U дан алынған n сөздің бірігуі ретінде сипатталатын барлық сөздер жиынын белгілейміз. Дербес ретінде An (n = 0,1,…) арқылы А алфавитіндегі барлық n ұзындықтағы сөздер жиынын белгілейміз. А* арқылы А дағы кез келген ұзындықтағы барлық сөздер жиынын түсінеміз. Ал, U* = n=0U¥Un – А алфавитіндегі мүмкін болған барлық сөздер жиыны. Мұнда ол U жиынның таңдауына өте байланысты болады. Егер U жиын 00 және 11 сөздерден құралған болса, онда оның кез келген бірігуі жұп ұзындыққа ие болады, екіншіден нөльдермен бірлер жұбымен жайғасады. Мысалы 0110 сөзі U2 жиынға тиісті болмайды. Егер α = α1α2 болатын сондай бір α2 сөз бар болса, онда α1 сөзді α сөздің басы деп атауға келісеміз, сонымен бірге, егер α2 ≠ λ болса, онда α1 сөз α сөздің өзіндік бастамасы деп айтылады. Егер α = α1α2 болатын α1 сөз бар болса, онда α2 сөзді α сөздің соңы деп айтамыз және сонымен бірге, егер α1 ≠ λ болса, онда α2 сөзді α сөздің өзіңдік соңы деп атауға келісеміз. Дербес ретінде, бос сөз кез келген α ≠ λ сөздің өзіндік басы және өзіндік соңы бола алады. Тағыда U жиыннан алынған барлық сөздер басын →U, ал сөздер соңының жиынын U¬ арқылы белгілейміз Енді B(r)={0,1,…,r-1} алфавиттік және еркін алынған G жиынды қарастырамыз, мұнда r >2. Дербес түрде G жиын шекті алфавит натурал сандар жиыны , белгілі типтегі сұлбалар немесе формулалар, белгілі бір алфавиттегі сөздер және т.б. лар болуы мүмкін. В алфавитіндегі G жиынның кез келген кескінделуі сөздер жиынында G жиынның r – дік кодталуы деп айтылады. Ал біз қолайлық үшін r = 2 болған жағдайды, яғни екілік кодталуды қарастырамыз. Сонымен байланысты logx өрнекті log2x ретінде түсінеміз. Кодталуға мысалдар келтірейік. Е кодталу арқылы натурал сандардың екілік жазылуын белгілейміз. Мұнда n = 0 санына ℓ(o) = 0 сөзі, ал n > 0 санға j=1∑ℓ(n) bj(n) 2ℓ(n)-j = n шартты қанағатандыратын ең қысқа ұзындықтағы е(n) = b1(n)b2(n)…bℓ(n)(n) eкілік сөз сәйкес қойылады. Мұнда n санның жазуы 1 цифрасымен жазылуы айқын, яғни b1(n) = 1 , ал ℓ(n) – белгілер саны 2ℓ(n)-1 ≤ n < 2ℓ(n) теңсіздікті қанағаттандыруы қажет, сондықтан ℓ(n) = [log n]+ 1 = ] log (n+1)[ болады, (мұнда [x] – x санның бүтін бөлігін , ал ]x[ - х тен кіші болмаған ең кіші бүтін санды білдіреді). Е кодталу n1 ≠ n2 болғанда e(n1) және e(n2) әр түрлі сөздер өзара бір мәнділікті қалыптастырады. Бірінші 2к натурал сандардың Ек кодталуы. Мұнда әр бір n (0 ≤ n < 2k) санға ek(n) = 0k-ℓ(n) e(n) сөз сәйкес қойылады. ek(n) сөзі n санның к цифрлық екілік жазуы деп айтылады. Еk кодталу кезінде бірінші 2к натурал сандар k ұзынықтағы екілік сөздер жиынында кескінделеді. 1 кестеде Е және Е4 кодталу кезіндегі 0 ден 15 ке дейінгі сандарға сәйкес келетін сөздер келтірілген. 1-кесте
Почта индекісінің цифрасын жазу негізіндегі қолданылатын кескіндеу ( 1- сызба). 1-сызба Хат жіберуші жағынан бір қалыптағы он бөліктен белгіленген әр бір ондық сан В алфавитіндегі 9 ұзындықтағы сөз ретінде автоматикалық танып-білу үшін кодталады. Мұнда, 1 белгісімен қолданылған сызықтар нөмірі белгіленеді. Мысалы, 2 санына 100100101 сөзі, ал 5 санына 110010011 сөзі сәйкес келеді. Кейде шекті жиынның кейбір екілік сөздердің ішкі жиынына кескінделуі осы жиын элементтерінің санын есептеу және бағалау үшін өте қолайлы қолданыс құралы болып есептеледі. Мысал үшін n санын m бүтін оң қосындыларының реттелген жіктеулерінен тұратын Fn1,m жиынды қарастырамыз. Мұндағы әр бір n = n1 + n2 +…+ nm жіктеуге сәйкес ретінде 0n110n21…10nm сөз қойылады. Ол n нөльдерден және (m-1) бірлерден құрылғандықтан (n+m-1) ұзындыққа ие. Мысал үшін 11 санның 4 қосындыға, яғни 11 = 5+0+2+4 бөлінуі 00000110010000 сөз арқылы, ал 11 = 1+1+6+3 бөліну 01010000001000 сөзімен кодталады. Мұндай кодталу дәл (m-1) бірлерге ие болған, ұзындығы (n+m-1) ге тең екілік сандар жиынындағы Fn,m жиынның өзара бір мәнді кескіні болады. Сондықтан Fn,m жиын элементтерінің саны Cm-1n+m-1 ге тең. Құпиялау теориясында белгілі бір А алфавиттегі барлық сөздерден (немесе дербес ретінде айырып алынған бір бөлігінен) тұратын G жиынды құпиялау жеке орын иелейді. Мұнда кодталатын жиын элементтерін ескере отырып, оларды хабарлар деп айтамыз. Жалпы жағдайда оған сәйкес екілік сөздерді хабарлау үшін есептеу процесінде (алгоритмнің өзі, оның тиімділігі) еш қандай шарт қойылмайды. Бірақта көп мәселелер үшін сөздерді кодтаудың - әріп бойынша кодталуы деп аталатын айтарлықтай тар класстарды қарастыруымен шектелу жеткілікті. Айталық, А = {aj} әріптері натурал сандармен нөмірленген шекті алфавит болсын. Бұл жағдайда А алфавит әріптерінің кодталуын V = {ui} екілік сөздермен беру мүмкін, мұнда ui ai әріптің басқаша сипаты. V = {ui} сөздерді А алфавиттен алынған кодтар деп айтамыз. Егер ai1,ai2,…,aik сөздердің (ақпараттың) әр біріне ui1,ui2,…,uik сөздер сәйкес қойылған болса, онда А алфавиттегі сөздердің кодталуын әріп бойынша кодталу деп атаймыз және Kuiai немесе KuA арқылы белгілейміз. Мысал үшін, A = {a,b,c,d} және оның әріптерінің екілік кодталуын a→01, b→100, c→101, d→0 ретінде алсақ,онда 0100 сөзді бір уақытта db немесе add ретінде декодтау мүмкін, ал сол секілді 0010100 сөзді ddcdd, daadd немесе dadb ретінде қарауға болады. Осы жерде, барлығымызға жақсы таныс болған Морзе телеграфтар коды латын немесе орыс алфавитінің әріптерін кодтау болып есептелуін білеміз. Мұнда барлық цифрлар және белгілер сипаты екілік сан болмаған екі әріпті алфавит – “нүкте”, “сызықша” арқылы жазылған сөздерден тұрады. Морзе кодтары қосымша белгі – бос орын(пробел) арқылы бөлінгендіктен байланыс жүйесі бойынша ақпаратты ұзату негізінде – уақыты өте аз мерзімде сақтау, ал жазбада бос орын қалдыруымен шектеледі. (3.4 және 3.5 кестелер) Кейбір кездерде алфавит әріптерін өзара бірмәнді кодталудан әріптер бойынша сөздерді кодталуға өтүде өзара бірмәнділік қаситтері сақталмауы мүмкін. Мысалы, Kеn(n)-натурал сандардың әріптер бойынша кодталуында (5,6,1) , (11,2,1) және (5,13) натурал сандар тізбегі бірдей 1011101 (101*110*1, 1011*10*1, 101*1101) сөздеріне сәйкес келеді. Сонымен, натурал сандардың көрсетілген әріптер бойынша кодталуы өзара бірмәнді болмайды. Егер алфавиттің барлық әріптер коды бірдей ұзындыққа ие болса , онда бұл код тең өлшемді деп айтылады ( мысал үшін Еn код Е кодтан айрықшалықта). Бұдан былай V = {ui} кодта (сөздер жиынында) тек қана әр түрлі сөздер болады деп есептейміз. жүктеу/скачать 198,4 Kb. Достарыңызбен бөлісу:
|