Лекция Құпиялау теориясы Кодталу теориясының негізгі ұғымдары және анықтамалары Алфавиттік кодтталу. Оптимал кодталу. Қателерді табу және өңдеу кодттары
жүктеу/скачать 198,4 Kb.
|
15-лекция
- Бұл бет үшін навигация:
- 3. Оптимал кодталу.
| 1–теорема. Айталық ℓ0,ℓ1,…,ℓm-1 – кез келген натурал сандар (m≥2) жиналымы болсын.
λ (ui) = ℓi, i = 0,1,…,m-1 ұзындықтағы бөлінетін V = {u0,u1,…,um-1} код бар болуы үшін «Бөлінетін кодтар үшін Крафт – Макмиллан теңсіздігі» орындалуы қажет және жеткілікті: i=0Σm-1 (1/2ℓі ) ≤ 1. 3.2 кестедегі код үшін: 3(½)3 + 4(½)4 = 3/8 + 4/16 = 5/8 < 1. Салдар. Кез келген бөлінетін V = {u0,u1,…,um-1} код үшін V кодта болғандағыдай кодталу сөздерінің жиналымдар ұзындығында болған префикстік код бар болады. 3. Оптимал кодталу. Енді біз кейбір қарапайым болжамдарға ақпараттар көзінің салыстырмалы статистикалық қасиеттерінде тиімді өзара бірмәнді кодталудың құрылуын қарастырамыз. Мұнда, кодталуды күштірек тиімді деп есептейміз, егер ақпараттың бір әрпіне орташа алғанда аз сандағы екілік цифрлар тұра келсе. Кездейсоқ түрде (яғни, кездейсоқ ретте) A = {a0,a1,…,am-1} алфавиттің әріптерін біртіндеп келтіріп шығаратын ақпарат көзін қарастырамыз. Мұнда А алфавит әріптерінің біртіндеп пайда болуы статистикалық жағынан тәуелсіз және төмендегідей ықтималдықтар үлестіруіне бағынады деп есептейміз: P = P{p0,p1,…,pm-1}, (pi³0, i=0Σm-1 pi = 1). Β = {0,1} алфавиттегі әр бір V = {u0,u1,…,um-1} код Ku0ao, Kuiai,…,Kum-1am-1 әріп бойынша кодталуда А алфавиттің бір әрпіне тұра келетін LV(p) = i=0Σm-1 piλ(ui) екілік цифрлардың орташа санымен сипатталады. Lv(p) шама Р үлестірімнің V кодтағы бағасы деп айтылады. Айталық L(p) = inf Lv(p) болсын, бұл жерде төменгі деңгей m сөзден құралған V префиксті кодтар жиыны бойынша алынады. V = {u0,u1,…,um-1} префиксті кодты P={P0,P,..., Рm-1 } үлестірімде оптимал деп айтамыз, егер Lv( Р)=L( Р) болса. Бұл жерде тұындайтын негізгі мәселе L(p) шаманың бағасын анықтауда өте тиімді әдістерді табу немесе кодталудың бағасы бойынша соған жақын болған тәсіл іздеу болып есептеледі. Осындай кодталулар құрудың оптимал әдістеріне жақын К. Шеннон және Р. Фаноларға тиісті екі әдіс бар. Құрылымы бойынша өте қарапайым болған Фано әдісі кезектегідей сипатталады. Реттелген (ықтималдықтардың кему ретімен) әріптер тізімі оларға кіретін әріптер мүмкін болғанша бір-бірінен кем айырмашылықта болатындай етіп ықтималдықтар қосындысы екі бөлікке (тізбекті) бөлінеді. Бірінші бөліктің әріптеріне 0 символы, ал екінші бөлігіне 1 символы жазылады. Осыған жалғаса отырып, егер олар кемінде екі әріптен құралатын болса, онда әрбір алынған бөліктерменде дәл осындай жұмыс орындалады. Бұл процесс барлық тізім бір әріптен тұратын бөліктерге бөлінбейтіндей болғанша жалғаса береді. Әрбір әріпке осы процесс нәтижесінде жазылған символдар тізбегі сәйкес қойылады. Мұнда алынған код префиксті болатынын көру қиын емес. Фано әдісі бойынша құрылған кодқа мысал 3- кестеде келтірілген. 3- кесте Мұнда кодталу бағасы: 2·(0.30+0.18)+3·(0.14+0.14+0.11)+4·0.06+5·(0.05+0.02) = 2.72 болады. Бұл жерде мынаған мән берген жөн, яғни әріптер тізімін тең екіге бөлу белгілі бір қатынастарда бір мәнді орындалмауы мүмкін. Алдынғы телеграфтарда танымал болған Морзе кодында әр бір әріпке немесе цифрға, сонымен бірге тыныс белгілері және басқада белгілерге қысқа уақыттағы үзілістермен бөлінген 3 мәрте ұзындау ток сигналынан (“сызықша” - аз аралықтағы қысқа сигналдар) тұратын тізбек сәйкестендіріледі. Әріптер арасындағы бос орын ұзындығы “сызықша”ның ұзындығына, ал бос орын сөздер арасындағы еселік үзіліске тең болған үзіліс бөлгіштерді (3 бірлік уақыттағы токтың қосылуы) сипаттайды. Морзе коды европа тілдеріндегі әр түрлі латын алфавитіндегі әріптердің жиілік қасиетін есепке алып қолданудан құралған. 4-кестеде латын әріптерінің коды және олардың ағылшын мәтіндеріндегі жиілігі келтірілген. Негізінен көптеу қолданылатын әріптер мүмкін болғанша қысқа сөздермен кодталады. Егер ағылшын мәтіндері көрсетілген жиіліктерді (бос орынның жиілігін де) есепке алмастан әріптер бойынша кодталса, онда бір әріпке орташа log226 ≈ 4.70 екілік белгілер (немесе бос орынды есепке алғанда 4.75 ≈ log227) талап етіледі. Морзе кодын қолданғанда 4.14 белгі болып, шамамен 13% үнемделеді. 4-кесте
Орыс әріптері үшін Морзе коды бір түрлі дыбыстарды сипаттайтын (мысалы: Б және Н орыс әріптерін В және N латын әріптерімен ) әріптер үшін латын әріптерінің сәйкестігін еске ала отырып құрастырылған. Сондықтан кодтар орыс тілді мәтінде әріптердің жиілікпен қатынасу сәйкестігі анағұрлым тұра келмейді. 5- кестеде орыс тілді әріптер үшін кодтар және оларға сәйкес жиілігі келтірілген (мұнда ь және ъ, сонымен тағыда Е және Ё бір түрлі кодталады). 5-кесте
Әр түрлі әріптердін жиілігін есепке алмағанда 32-әріптік алфавитте бір әріп үшін орташа log232 = 5.00 екілік белгілер талап етіледі (31 әріп үшін - log231 ≈ 4.95). Шын мәндегі жиілікті есепке алғанда – 4.45 (тиімділік шамасы – 10%), ал Морзе кодын қолданғанда – біраз көптеу болады. Бір қызық жағдай, танымал жазушы Л. Толстойдың “Война и мир” романының мәтінінде, әріптер жиілігі үшін осы секілді есеп біразғана төмен мәнді береді: 4.35. Осы жерде мән берген жөн, яғни түрлі өлшемді Морзе коды бөлгіштермен бірге кейіндеу әріп басатын құрылғылардың кейде жарамсыз болып қалуынан телеграфтарға тең өлшемді бес разрядты Бодо екілік кодымен ауыстырылған (регистрларды ауыстыру жолымен, мұнда, кейде бес разрядты сан екі немесе үш түрлі символдарды кодтаған). Бодо кодында бөлгіштер талап етілмейді, себебі қабылдау сандарының соңы белгілі, яғни әрбір 5 элементар сигналдан соң бір әріп бітеді және кейінгі әріп басталады. жүктеу/скачать 198,4 Kb. Достарыңызбен бөлісу:
|