Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану
жүктеу/скачать 0,66 Mb.
|
darismatlogidm
| 2.Алфавиттік кодтау
Жалпы жағдайда кодтауды келесі түрде беруге болады. Ақырлы символдар тізбегінен тұратын А және В алфавиттері берілсін: A a1, a2,..., an B b1, b2 ,..., bm Алфавит элементтері әріптер деп аталады. А алфавитіндегі реттелген жиынды сөз деп атайық. a1, a2 ,..., ai ,..., an Мұндағы i[1, n] n саны сөздегі әріптер санын көрсетеді және α сөзінің ұзындығы деп аталады, мына түрде белгіленеді: п =l(α)=|α|. Бос сөз былай белгіленеді: α= a1, a2 ,..., ai ,..., an сөзі үшін a1 әрпi α сөзінің басы немесе префиксі деп аталады, ал an әрпі – α сөзінің соңы немесе постфиксі деп аталады. Сөздерді біріктіруге болады. Ол үшін екінші сөздің префиксі бірінші сөздің постфиксінен кейін бірден жалғануы керек және олар жаңа сөзде өз статустарын жоғалтады, егер сөздердің бірі бос болмаса. α 1 және α2 сөздерін біріктіру a1 , a2 түрінде белгіленеді, п бірдей сөздерді біріктіру an түрінде белгіленеді, және де a0=Λ . А алфавитінің бос емес сөздер жиынын А* деп белгілейміз: А* = { α |l(α )>0} А жиынын хабарламалар алфавиті, ал В жиынын кодтаушы алфавит деп атайды. В алфавитінде құрылған сөздер жиынын В* деп белгілейміз. F арқылы А алфавитінің сөздерінің В алфавитіне кескінделуін бейнелейміз. Онда β=F(α) сөзін α сөзінің коды деп атаймыз. Кодтау деп ақпараттың оны сақтау, беру және өңдеу кезінде хабарлама элементтері мен сигналдар арасындағы сәйкестіктер жүйесі түрінде кескінделуінің әмбебап тәсілін айтады, олардың көмегімен бұл элементтерді тіркеуге болады. Осылайша, код дегеніміз хабарламаны бір символдық берілу формасынан (бастапқы А алфавитінен) басқа бір формаға(В объектілі алфавитіне) ақпарат шығынынсыз бірмәнді түрлендіру ережесі (яғни, функция). А бастапқы алфавитінің сөздерін В алфавитіне F: А*→В* түрлендіру процесі ақпаратты кодтау деп аталады. β B* сөзін α A* сөзіне кері түрлендіру процесі декодтау деп аталады. Осылайша, декодтау F – кері функция, яғни F-1. Кез-келген кодтау үшін декодтау орындалатын болғандықтан түрлендіру қайтымды болуы керек (биекция). Егер |B|= m, онда F m-ншы кодтау деп аталады, ең көп тараған түрі В = {0, 1}- екілік кодтау. Осы түрі әріқарай қарастырылатын болады. Егер барлық кодтық сөздердің ұзындықтары бірдей болатын болса, онда код бірдей өлшемді немесе блокты деп аталады. Алфавиттік кодтауды (немесе әріптеп кодтауды) кодтар кестесі түрінде беруге болады. Код немесе кодтаушы функция қызметін қандай да бір σ орналастыруы атқарады. Онда σ=, мұндағы Мұндай әріптеп кодтау түрінде белгіленеді. {βi} әріптерінің кодтарының жиыны элементер кодтар жиыны деп аталады. Алфавиттік кодтауды кез-келген хабарламалар жиыны үшін қолдануға болады. Осылайша, алфавиттік кодтау ең қарапайым кодтау болып табылады, оны әрқашан бос емес алфавитте қолдануға болады. Мысал. Төмендегі алфавиттер берілсін делік: А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} В = {0, 1}. Онда кодтау кестесі орналастыру түрінде бола алады: Бұл екілік-ондық кодтау, ол өзара бірмәнді болып табылады, сондықтан декодтау орындала алады. Дегенмен схема өзара бірмәнді болып табылмайды. Мысалы, алты бірліктен 111111тұратын жиын 333, 77, сонымен қатар 111111, 137, 3311 немесе 7111сөздеріне сәйкес келуі мүмкін, онымен қоса кез-келген орыналмастыру. Алфавиттік кодтау схемасы префиксті деп аталады, егер бір әріптің элементар коды басқа әріптің элементар кодының префиксі болып табылмаса. жүктеу/скачать 0,66 Mb. Достарыңызбен бөлісу:
|