Лекция Құпиялау теориясы Кодталу теориясының негізгі ұғымдары және анықтамалары Алфавиттік кодтталу. Оптимал кодталу. Қателерді табу және өңдеу кодттары
жүктеу/скачать 198,4 Kb.
|
15-лекция
| 1-теорема. Егер Σ сұлба префикстік қасиетіне ие болса, онда алфавиттік кодталу өзара бір мәнді болады.
Дәлелдеу. Айталық SΣ (B) жиыннан алынған кез-келген В сөз екі ашиалауға ( декодталуға) мүмкіндік берсін, ал ол екі қарапайым кодтарға бөлінеді деген сөз: B=Bi … Bis B=Bj … Bjt . Айталық Вi1 =Bj1,…, Bin-1=Bjn-1, Bin ≠ Bjn болсын. Мұндай жағдайда Bin, Bjn сөздерінің біреуі екіншісінің префиксі болып табылады. Теорема дәлелденді. Қарастырылған мысалдар көрсетіп отырғандай көп жағдайларда префикстік қажетті шарт болып табыла бермейді. Σ сұлба префикстік қасиетіне ие болмауы мүмкін, ал бірақта Σ-ны анықтайтын алфавиттік кодталу өзара бір мәнді болып табылады. Айталық, B=bi1 … bin, S(B) жиыннан алынған сөз болсын. В* арқылы В-дан кезектегідей ауыстыру жолымен алынған сөзді белгілейміз: B*=bin … bi1. Ал, Σ арқылы a1−−−−В1* .............. ar−−−−Вr* типтегі сұлбаны белгілейміз. Мысал. Σ ретінде жоғарыдағы мысалда көрсетілген сұлбаны алсақ, онда Σ* мынадай көрініске ие болады: a1−−−b1 a2−−b1b2 . Мұнда, Σ префикстік қасиетіне ие болады, ал 1-теорема бойынша Σ* - ретінде берілген алфавиттік кодталу өзара бір мәнді болады. Ескерту: Σ сұлба арқылы анықталған алфавиттік кодталу және Σ* схема арқылы анықталған алфавиттік кодталулар бір уақытта өзара бір мәнділікке ие болуыда, болмауыда мүмкін. 2-теорема: Егерки не Σ сұлба , не Σ* сұлба префикстік қасиетке ие болса, онда Σ (Σ*) ретінде берілген алфавттік кодталу өзара бірмәнді болады. Бұл жерде сұлбаны алфавиттік кодталуға Σ да, Σ* да префикстік қасиетіне ие болмайтын, бірақта алфавиттік кодталу бірмәнді болатын мысал келтіру мүмкін. Оның үшін жоғарыдағы мысал тура келмейді, бірақ ол мысалды кішкентай жетілдіреміз. Мысал: Айталық A={a1, a2, a3} және B={ b1,b2,b3} берілген болсын. Σ сұлбаны қарастырамыз: a1−−−b1 a2−−b1b2 (Σ) a3−−b3b1. Σ және Σ* сұлбалар префикстік қасиетке ие емес екендігі айқын, бірақта сонымен бір уақытта алфавиттік кодталу өзара бірмәнді болады. Шындығында, егер BÎ SΣ (B) болса, онда бұл сөз бірмәнді түрде қарапайым кодтарға бөлінеді: − b2 әріптің сол жағында міндетті түрде b1 табылады, оны (b1b2) жұптық ретінде айырып қоямыз; −b3 әріпінің оң жағында міндетті түрде b1 болады, оны (b3b1) жұптық ретінде айырып қоямыз; −барлық (b1b2) және (b3b1) жұптарды айырып болғаннан соң сөзде тек b1 символдар ғана қалады. Алға қарай қарастырмас бұрын мынадай белгілулер енгіземіз: ℓ(B) арқыла сөздегі әріптер санын білдіретін В сөзінің ұзындығын белгілейміз. Дербес ретінде Bi (i=1…r) қарапайым кодтар ұзындығы үшін ℓ(Bi)=ℓi ретінде қабылдаймыз. L арқылы Σ сулба “ұзындығы” ретінде ℓ(B1 … Br ) шаманы белгілейміз. Айталық Bi = β′ Bi1 … Bik β′′ (1) қарапайым Вi кодтың нөлдік болмаған жіктеуі, яғни Bi =Bi (β′ =β′′ =λ) жіктеуден айрықша болған жіктеу болсын. Бұл жіктеуде төмендегілерді ескереміз: a) β¢ қарапайым кодпен аяқталуы мүмкін емес; б) β² бастау ретінде ( префикс ретінде ) қарапайым кодтарға ие болмайды. (1) теңдікте k параметр нөльге тең немесе үлкен болған бүтін сан болуы мүмкін. Сонымен бірге (1) қатынас қарапайым Bi кодта β′ басталуын және β′′ соңын сондай тастап жіберу мүмкін, ал қалған бөлігі қарапайым кодтарға бөлінеді (төмендегі сызба ): → Bi ← ׀−−׀−−׀−−׀−−׀−−׀−−| β′ βi1 βi2 ........βik β′′ Шыныменде, әр бір Bi үшін (1) типтегі жіктеулер шекті. W арқылы Bi-дің барлық жіктеулер бойынша және барлық i-лер бойынша алынған k санның максимумын белгілейміз, яғни W=max k. Мысал: A={a1, a2, a3, a4, a5}, B={ b1,b2,b3} алфавиттік кодталу және a1−−−b1b2 a2−−−b1b3b2 a3−−−−−−b2b3 a4−−−−−b1b2b1b3 a5−−−−−−b2b1b2b3 сұлбаны қарастырамыз. Мұнда 6 > ℓi ≥ 2 болғандықтан W< 3 болады. Басқа жағынан B5=b2b1b2b2b3 = b2B1B3, сондықтан W=2. Енді SN(A) арқылы А алфавитіндегі ұзындықтары N-нен аспайтын барлық сөздер жиынын белгілейміз. Бұл жерде SN(A) шекті жиын, ал оның қуаты і=1ΣNri - ге тең екендігі түсінікті. Осы жерде алфавиттік кодталудың өзара бірмәнділік критериін қарастырамыз. жүктеу/скачать 198,4 Kb. Достарыңызбен бөлісу:
|