Лекция Құпиялау теориясы Кодталу теориясының негізгі ұғымдары және анықтамалары Алфавиттік кодтталу. Оптимал кодталу. Қателерді табу және өңдеу кодттары
жүктеу/скачать 198,4 Kb.
|
15-лекция
- Бұл бет үшін навигация:
- 4. Декодталудың бірмәнділік критериі
| Теорема. H(x) = (0,0,…,0) (*)
болатын барлық X = x1x2…xn Î Bn сөздерден құралған Hn – Хемминг коды бір орнын ауыстырып өңдеудің коды болады. Жоғарыда қарастырылған мысалда XÎ H6, YÏ H6. Мысал: Айталық , Х = 010101 Î H6 сөздің бесінші белгісінде орын ауысқан болсын, нәтижеде T = 010111 сөз алынады. Себебі H(T) – (0,1,0)+(1,0,0)+(1,0,1)+(1,1,0) = (1,0,1) болғандықтан H(Y) сөздің сандық мәні 5 ке тең және ол орны ауысқан белгінің нөмірін анықтайды. Бұл жерде |Hn| - Hn кодтың элементтер саны 2n-1 ге тең екендігін көреміз. Бұл, нөмірлері 20,21,...,2ℓ-1 сандардан (ақпараттық позициялар) айрықша болған (n-ℓ) компонентті мәндердің кез келген еркін берілуінен келіп шығады, ал 20,21,...,2ℓ-1 нөмірлеріндегі компоненттер мәні (*) шарттан бірмәнді анықталады. ℓ = [log n]+1 = ]log(n+1)[ болғандықтан 2n-1/n £ |H÷=2n-]log(n+1)[ £ 2n/(n+1) болады. Дербес ретінде |H6| = 26-]log7[ = 26-3 = 23 = 8. Осы H6 код төменде келтірілген. H6 000000 111000 110011 001011 101101 010101 011110 100110 Мұндай кодталу жиынымен 3 ұзындықтағы барлық сөздерді кодтау мүмкін, ал олар 8. Р. Хэмминг декодталудың өте қарапайым және қолай орындалатын кодталу әдісін ұсынған. Оның үшін m ұзындықтағы Х кодталу сөзі кодталу кезінде білгілі бір тәсілмен санақталатын ℓ тексерілген разрядтарымен ( ℓ = ]log(m+1)[ ) қосымша толтырылады. Ал, алынған Х хабарлар m ақпараттық және ℓ тексерілген позициялардан құралады. Тексерілген разрядтар үшін нөмірлері 2 санның бүтін дәрежелеріне келетін 1-ші, 2-ші, 4-ші, 8-ші және т.б. нөмірлер ажратылады. Олардың екілік сан құрамында дәл біреуғана ғана бір саны болады. Басқа орындарға (3,5,6,7,9,10,...) кодталатын Х сөзінің белгілері жайғастырылады. Енді, екі мысал арқылы Хемминг бойынша кодталудың қалай өткізілетіндігін көрсетеміз. Айталық X = 1100 кодталу сөзі берілген болсын, мұнда m = 4, ℓ = ]log 5[ = 3. m + l = 7 ұзындықтағы құпияланған хабар P1 P21 P4100 көрінісінде болады. Тексерілетін P1,P2,P4 белгілер кезектегідей есептелінеді. Р ның мәні нөмірлері Рі дің нөмірлеріне сәйкес екілік бейнедегі бірлерден құралған сондай ақпараттық белгілердің модул 2 бойынша қосындыларына тең, яғни оң жақтан і-ші разрядта: Р1 – 1 – ші разрядта, Р2 – 2 – ші, Р4 – 3 – шіде ( 7-кесте). P1 = P3 Å P5 = 0; P2 = P3 = 1; P4 = P5 = 1. Нәтижеде Х¢ = 0111100 ді аламыз 7-кесте
Мысал. Ұзындығы m = 10; 1001110110; ℓ = 4 болған Х кодталатын сөздің тексерілетін разрядтарының есептелінуі 8-кестеде келтірілген, Х= 01110010110110. 8 – кесте
Енді кез келген әр түрлі Х,У сөздер үшін олардың Хэмминг бойынша құпияланған Х¢,Y¢ бейнелері кемінде үш разрядта айрықшылықта болатын және жеке қателерді өңдеуді қамтамасыз ететінін дәлелдейміз. 1) ρ(Х,Y)>3, яғни Х,Y үш немесе оданда көп разрядта айырмашылыққа ие болады: мұнда кодталу негізінде бұл айырықшалықтар сақталады; тексеретін разрядтарда айырмашылық қосылуы мүмкін, яғни ρ(X¢,Y¢) ³ 3. 2) ρ(X,Y) = 2 , яғни Х,Y екі разрядта айырықшалыққа ие болады. Айталық, құпияланған сөздерде бұл орындар α≠β болған α, β сандардың екілік жазылуы еш болмағанда бір і-ші разрядта (α=0, β=1 немесе α=1, β=0) айырықшалықта болсын. і-ші разрядқа сәйкес келетін тексерілетін белгіні есептеуде, яғни 2і орында тек Х¢,Y¢ сөздердің біреуі үшін модуль 2 бойынша қосындыда бір қатысады, ал α, β дан басқа қалған орындарда Х және Yсөздер сәйкес келеді. Демек, 2і-ші тексерілетін орындарда Х¢ және Y¢ сөздерде айрықшалыққа ие болады: нәтижеде Ρ(Х¢,Y¢)≥3 екені айқын. 3) ρ(X,Y) = 1, яғни Х,Y дәл бір разрядта айырықшалыққа ие. Х және Y сөздеріндегі сол ақпараттық разряд нөмірі 2 санның бүтін дәрежесіне тең емес, яғни оның екілік жазылуы кемінде екі бірлерге ие болады. Онда сәйкес екі тексеретін разрядтарда Х және Y сөздері әр түрлі болады, мұнда тағыда ρ(X¢,Y¢)≥3 болуын көреміз. Егер Х кодталу сөзін жеткізу кезінде бір қателік табылса, онда декодталу кезіндегі Т сөзден алынған екілік жазу ретінде қолданған H(T) вектор бұзылған разрядтық нөмірді көрсетеді. 4. Декодталудың бірмәнділік критериі Бұл жерде біз А және В алфавиттер үшін Σ сұлба арқылы берілген алфавиттік кодталуларды қарастырамыз: a1 ——— b1 a2 ——— b2 (Σ) .............. ar ——— br және S′(A)=S(A), яғни хабарландыру дерек көздері А алфавитіндегі барлық сөздер жиынын келтіріп шығарады деп есептейміз. Ал, алфавиттік кодталу S(B) жиынында S(A) жиын кескінін келтіріп шығаратындығы айқын. SΣ(B) арқылы S(A) кескіндеулер өзара бірмәнді болған жағдайда декодталу мүмкін, яғни В кодталу бойынша бастапқы А ақпаратты бірмәнді түрде тіктеу мүмкін болады. Оның бұл кездегі басты қызмет атқарушы коды В коды болып табылады. Мұндай жағдайларда былайша айтылады, яғни алфавиттік кодталу өзара бірмәнді болып табылады екен. Мысал үшін А={a1, a2}, B={ b1, b2} алфавиттік кодталуды қарастырсақ, оларды схема түрінде былай жазу мүмкін: a1 ——— b1 a2——— b1b2 . Айталық В¢ және В², А¢ және А² сөздердің сәйкес ретіндегі коды болсын. Егер А′ ≠ А" болса, онда В′ ≠ В" болары айқын. Декодталу процесі төмендегідей амалға асырылады. В, ВÎSΣ(B) сөздерді қарапайым кодтарға бөлеміз. Оның үшін мынадай болатындығын байқаймыз. В сөзге b2 әріп әр бір енуден алдын міндетті түрде b1 әріп тұрады. Бұл барлық (b1b2) жұптықтарды айырып алуға мүмкіндік береді. В сөзінің қалған бөлігі b1 әріптерінен құралады. Егер әрбір (b1b2) жұптықты а2 мен, ал қалған әрбір b1 әріпті а1- ге ауыстырсақ В сөзге ұқсас А сөзді аламыз. Айталық B= b1b1b2b1b2b1b1b1b2 сөз берілген болсын, мұнда жұптықтар айырып алынғаннан соң олардың қарапайым кодтар бейнеленген түрін аламыз: B= b1(b1b2) (b1b2) b1b1 (b1b2), бұл жерде мына сөз алынады: A=a1a2a2a1a1a2 . Сол секілді өзара бірмәнді қасиетке ие болмайтын алфавиттік кодталуларға көптеген мысалдар келтіру мүмкін. Осыған байланысты сұрақ туындайды: Осы алфавиттік кодталудың Σ сұлбасы бойынша алфавиттік кодталудың өзара бірмәнділік қасиетін білуге болама? Бұл мәселенің шешімін табу қиындығы мынада, яғни өзара бір мәнділікті тікелей тексеру үшін шексіз көп сөздер тізбегін міндетті түрде қарастыру қажет. Алфавиттік кодталу бір мәнділігінің жалпы критериін келтіруден алдын өзара бірмәнділіктің өте қарапайым жеткіліктік белгісін қарастырайық. Анықтама. Айталық В сөзі төмендегідей көрініске ие болсын: B=B′B" . Онда В′ сөзі В сөзінің бастаушысы немесе сөздің префиксі, ал В" В сөзінің соңы деп айтылады. Анықтама. Егер кез-келген i және j (1≤ i, j ≤ r, i ≠ j ) үшін Вi сөзі Вj сөзінің префиксі болмаса Σ сұлба префиксті қасиетке ие болады. жүктеу/скачать 198,4 Kb. Достарыңызбен бөлісу:
|