Лекция Құпиялау теориясы Кодталу теориясының негізгі ұғымдары және анықтамалары Алфавиттік кодтталу. Оптимал кодталу. Қателерді табу және өңдеу кодттары
Кодталу теориясының негізгі ұғымдары
жүктеу/скачать 198,4 Kb.
|
15-лекция
| 1. Кодталу теориясының негізгі ұғымдары
және анықтамалары Математикада құпиялау (кодталу) теориясы үлкен жұмыс атқарады. Құпиялау бір нысанды үйрену арқылы екінші нысанды үйретуге алып келеді. Сандарды ондық санау жүйесінде көрсету қандай маңызды болғандығы бізге белгілі. Математика пәні ары қарай өркендеуі, дамуы барысында координаталар әдісі үлкен маңызға ие болды, өйткені ол яғни координаталар жүйесінде геометриялық нысандарды аналитикалық көрініс арқылы кодтау мүмкіндігін берді. Хабарландыру хабарлардың Желі Хабарлардың көзі Хабарлар коды байланысы шығу коды Кодтау өзгерту, декодтау Хабарлардың кедіргі шығуы көзі Бастапқыда кодталу құралы көмекші құрылғы-аспап болып, ол зерттелетін - оқытылатын пән емес еді. Басқару жүйесін үйренуде кодтау сөзін мүлдем басқа мағынада қолданылған. Кодталу теориясында жүйелер облысы негізінде ізденістер, зерттеулер алып баруды қажет етеді. Осыған байланысты жоғарыдағы сызбада көрсетілген сұлба арқылы негізгі мәселелерді көруге болады. Айталық белгілі бір әріптерден құралған Ω = {a1…,ar} алфавит берілген болсын. Ω символдарынан құралатын A = ai1 ai2 … ain шекті тізбекті Ω алфавитіндегі «сөз» деп айтамыз, бұл жерде n – A сөзінің ұзындығы. А сөзінің ұзындығын L(A) арқылы белгілеуге келісеміз. Айталық, SΩ алфавиттдегі кез келген әріптерден құралған барлық сөздер жиыны және S1 – S көпмүшеліктен келіп шығатын ішкі сөз болсын. S сөзі келіп шығатын нысан ( обект) «хабарлар көзі» деп аталады. Ал, S-тен құралған сөздерді «хабар» деп атаймыз. Хабарлардың көзі болып автомат, табиғат, адам жәнеде басқалар болуы мүмкін. Әдетте кодталу теориясында есептерді көру кезінде «хабар көзі» тұралы қосымша ақпаратпен ауысады. Оларды қандай көріністерде сипаттау мүмкіндігін бір неше жолдар арқылы төмендегідей көру мүмкін : а) теоретикалық жиында сипаттау қуаттылық характеристикаларын белгілеп бару жолымен орындалады, мысалы S¢ – берілген m ұзындықтағы барлық сөздер жиыны. б) статистикалық бейнелеу - мұнда S¢ ықтималдық характеристикаларының берілу жолымен орындалады, мысалы, S¢ = S және а1, а2,..., аr әріптерінің пайда болу ықтималдықтары P1,..., Pr берілген ( ∑ рі = 1) . в) логикалық бейнелеу – S¢ жиынының сипатталуын кейбір “Тілдер ” ретінде береді. Ол S¢ жиынды құрастыру тәсілдерін көрсетеді, мысалы, S¢ кез – келген автомат арқылы түрленуі мүмкін. Айталық, Ψ алфавиті берілген болсын, бұл жерде Ψ = {b1,…,bq } . В арқылы Ψ алфавитіндегі сөздерді және S(Ψ) арқылы Ψ алфавитіндегі барлық сөздер жиынын белгілейміз. Айталық әр бір А, А Î S (Ψ) сөзге В = F(A), B Î S(Ψ) сөзді сәйкес қоятын F кескіндеу берілген болсын, B сөзін А – ның «хабарлар коды» деп, ал А сөзінен оның кодына өтуді кодталу деп айтамыз. Кодталу теориясында F кескіндеу кейбір алгоритмдер түрінде беріледі. а) Алфавиттік кодталу. Ω алфавитіндегі әріптер және Ψ алфавитіндегі кейбір сөздер арасындағы сәйкестікті қарастырамыз: а1 – В1, а2 – В 2, ( ∑ ) ........... аn = Bn Бұл қатынасты «сұлба» деп айтамыз және ∑ арқылы белгілейміз. Ол алфавиттік кодталуды кезектегідей анықтайды: S1 (Ω) = S(Ω) жиынынан, алынған әрбір А = ai1…ain сөзге А сөздің коды деп аталатын В=Bi1... Bin сөз сәйкес қойылады, мұнда Bi1, Bin қарапайым(элементар) кодтар деп айтылады. б) теңбе – тең кодталу. Айталық {A1,…,As} Ω алфавитіндегі ұзындығы m ге тең болған жұбымен әртүрлі сөздердің жиыны болсын. Бұл жерде әрбір А сөз А = Ai1…Ain көрінісіндегі жіктеуге келетін жалғыз жіктелуге ие. Айталық S¢(Ω) жоғарыда көрсетілген типтегі жіктелуге мүмкіндік беретін Ω алфавитіндегі сөздердің кейбір ішкі жиыны болсын. Кезектегі сұлбаны қарастырамыз. A1 – B1, ………. As – Bs, бұл жерде А жиынының элементтері В жиынының элементтер кодына сәйкесінше ұзындақтары тең. ∑ сұлбасы теңбе-тең кодталуды кезектегідей анықтайды: S¢(Ω) жиындағы әрбір A = Ai1…Ain сөзге А ның «кодтық сөзі» деп аталатын B = Bi1…Bin сөз сәйкес қойылады. Кодты таңдау әр түрлі жағдайларға байланысты, атап айтқанда: - кодты жіберу ыңғайлығымен (мәселен, техникада екіленген кодты қолдану өте оңай); - қабылдаудың ыңғайлығын қамтамасыз етумен (мәселен, машиналық кодтар процессордың жұмыс істеуіне ыңғайлы); - желінің максимал өткізу қабілетін қамтамасыз етумен; - кедергілерге төзімділігін қамтамасыз етумен; - кодталу алгоритімінің белгілі бір қасиеттеріне жетумен (мәселен, кодталудың қарапайымдылығы, бірмәнді кодталудың мүмкіндіктері) және т.б. Байланыс желісін бір «кіріс» және бір «шығыс» нүктесі бар құрылғы ретінде қарастыруға болады ( төмендегі сұлба). В В¢
B¢ = f(B). Қарапайым жағдайда (кедергісіз желіге теңдес), яғни байланыс желісі идеал болған жағдайда B¢ º B (немесе f(B)=B) болады, ал ол Ψ¢ = Ψ екендігін білдіреді. Жалпы жағдайда Ψ¢ ≠ Ψ байланыс желісі кодтардың түрленулерін өз ішіне алуы , яғни болуыда мүмкін (мәселен, электрон есептеу машиналарында ). «Кедергі көзі» (центрі) «шығыста» кодтардың айнығанын ескере отырып байланыс желісіне қателіктер еңгізеді. «Кедергі көзін» сипаттау үшін екі тәсіл қолданылады: логикалық – комбинаторикалық бейнелеу, статистикалық бейнелеу. жүктеу/скачать 198,4 Kb. Достарыңызбен бөлісу:
|