Лекция Құпиялау теориясы Кодталу теориясының негізгі ұғымдары және анықтамалары Алфавиттік кодтталу. Оптимал кодталу. Қателерді табу және өңдеу кодттары
жүктеу/скачать 198,4 Kb.
|
15-лекция
| Анықтама: V = {ui} код бөлінетін деп айтылады, егер B = {0,1} алфавитінде ui1ui2…uik = uj1uj2…ujℓ көрінісіндегі әр бір теңдіктен k = ℓ және it = jt,t = 1,2,…,k келіп шықса.
Анықтама. Әріп бойынша кодталу сонда тек сондағана өзара бірмәнді болады, қашан ол бөлінетін кодтар көмегімен берілетін болса. Осы анықтамадан тағыда бөлінетін кодтардың барлық сөздері әр түрлі және бос болмастығы келіп шығады. Анықтама. V = {ui} кодты префиксті деп айтамыз, егер еш қандай uk сөз, басқа ешқандай uj(j ≠ k) сөздің басы болмаса. Бұл жерден префикс кодтың бөлінетін екендігі, яғни префикстілік бөлінетінділік үшін жеткілікті шарт екендігі келіп шығады. Егер префиксті кодтың әрбір сөзін басқа кодталған сөздердің басы болмаған ең кіші оның басталуымен ауыстырылса, онда алынған код тағыда префиксті болады. Мұндай амалдарды префикс кодтың кесімі деп айтамыз. Префикс кодқа өте қарапайым мысал – тең өлшемді кодтар. Олардың әр бір жіберілетін сөз кодының анықталуы және әр бір басталатын кодтың саны кодталған символдардың белгіленген бір түрлі сандары арқылы жазылғандықтан бөлгіштер қажет болмайды. Мысалы: қалалардағы 7 санды телефон нөмірлерінің префикстілігі (демек, бөлінетіндігі) тең өлшемділігімен қамтамасыз етіледі. Нөльден басталатын: 01,02,03 және т.с. нөмірлер үшін бөлінетінділік талаптары сондай басталуға ие болған басқа нөмірлерге мүмкіншілік бермейді. Кодтардың префикстілігін және басқада әдістермен қолдау мүмкін. Алдын қарастырылған Морзе кодында кез келген код сөзінің соңы ретінде арнайы белгі – бөлгішті еңгізу мүмкін. Сол секілді, компьютерлерге файлдың аты, берілгендердің аты, көпмәнді сандар және т.с. ақпараттарды еңгізу бөлгіштермен аяқталуы қажет, дербес түрде Шыныменақ, егер кейбір хабарларда 0 символынан кейін 0 келсе, онда бірінші 0 «а» әрпін кодтайды, себебі, 00 ешбір кодталу сөзінің басталуы емес, ал егер 0 ден кейін 1 келсе, онда 01 жұп символ «в» әріптің коды болады. Мұнда 0 «а» әріпті кодтай алмайды, себебі кезектегі 1 еш бір кодталу сөзінің басталуы бола алмайды. Әр түрлі сөздерден құралған V еркін код үшін V® төбелер жиынынан құралған бағытталған графты қарастырамыз, мұнда βÎ V® төбе β¢Î V® төбемен (β,β¢) доға арқылы қосылған болады сонда тек сондағана, қашан β¢ = β0 немесе β¢ = β1 болса. Бұл граф циклдарға ие емес және ол V кодтың кодталу ағашы деп айтылады. Префиксті кодтар үшін (текқана солар үшін) кодты сөздер жиыны кодталу ағашының соңғы төбелер жиынымен сәйкес келеді (яғни, қабырғалар шықпайтын төбелер). 2-сызбада (ℓi = λ(uj)) 2- кестеде келтірілген кодтың кодталу ағашы бейнеленген. 2- кесте 2-сызба
Бұдан былай шекті V = {u0,u1,…,um-1} код үшін m ≥ 2 деп есептейміз және
жүктеу/скачать 198,4 Kb. Достарыңызбен бөлісу:
|