Лекция Құпиялау теориясы Кодталу теориясының негізгі ұғымдары және анықтамалары Алфавиттік кодтталу. Оптимал кодталу. Қателерді табу және өңдеу кодттары
жүктеу/скачать 198,4 Kb.
|
15-лекция
| Теорема ( Марков А.А.): Σ сұлбалы кез-келген алфавиттік кодталу үшін сондай бір N0 табу мүмкін, ал бұл жерде алфавиттік кодталудың бірмәнділік мәселесі осыған іспеттес SN0(A) шекті жиынның кодталу мәселесіне алып келеді және ол
N0 ≤ [(W+1)(L-r+2)]2 болады. Дәлелдеуі [4]. Декодталудың бір мәнділік критериін Σ сұлба бойынша қалыптастыруда алфавиттік кодталудың өзара бірмәнділік қасиеттерінің бар немесе жоқ қасиеттеріне ие болудың қарапайым алгоритімін береді. Оның үшін А алфавитінде ұзындығы N0-ден аспайтын, яғни SN0(A) сөздер жиынын қарастыру және осы шекті жиындағы кодталудың өзара бірмәнді болатындығын анықтау жеткілікті. Бұл алгаритмнің қиындық көлемін rN0 ретінде тұрпайы бағалау мүмкін. Мысал. Жоғарыда көрілген мысалдағы алфавиттік кодталуды қарастырамыз. Бұл жерде r=5, W=2, L=16. Теоремадағы теңдікті қолдансақ N0=[(W+1)(L-r+2)2=[3·13]2 =19, rN0 = 519 болады. Ал, бұл біразғана үлкен сан. Декодталудың бірмәнділігін танып-білу. Декодталудың бірмәнділігін танып-білу үшін графтар теориясы көмегінен пайдалануды жөн көрдік. Айталық алфавиттік кодталу Σ сұлбасы берілген болсын: a1−−−−В1 ............ (Σ) ar−−−−Вr . Әр бір қарапайым Ві код үшін Bi = β′ Bi1 … Bik β′′ (*) көрінісіндегі барлық жағдайларды қарастырамыз. В0 арқылы λ “бос” сөзді және (*) көрінісіндегі жіктеулерде префикстер формуласында немесе соңында β сөздер қатысатындарды өз ішіне алатын жиынды белгілейміз. Бұдан бұлай В0 –ден алынған әр бір сөзге жазықтықта нүктелер сәйкес қоямыз. Айталық β′, β"ÎВ0 болсын. Мұнда, Bi = β′ Bi1 … Bik β′′ көрінісіндегі барлық жіктеулерді қарастырамыз. Олардың әр біреуі үшін β′ және β" сөздерге сәйкес келетін Bi1 … Bik сөздер жазылған бағытталған кесінділерді төбелермен жалғастырамыз (β′ тан β"ге қарата). Алынған графты Г (Σ) арқылы белгілейміз. жүктеу/скачать 198,4 Kb. Достарыңызбен бөлісу:
|