Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану
жүктеу/скачать 1,12 Mb.
|
Лекция дискретка каз
| 2.Алфавиттік кодтау
Жалпы жағдайда кодтауды келесі түрде беруге болады. Ақырлы символдар тізбегінен тұратын А және В алфавиттері берілсін: a1, a2,..., anиB b1,b2,...,bm. Алфавит элементтері әріптер деп аталады. А алфавитіндегі реттелген жиынды сөз деп атайық a1, a2,..., ai,..., an мұндағы i1,n ,п саны сөздегі әріптер санын көрсетеді және сөзінің ұзындығы деп аталады,мына түрде белгіленеді:п=l( )=| |. Бос сөз былай белгіленеді: :l 0 a1, a2,..., ai,..., an сөзі үшін a1 әрпі сөзінің басы немесе префиксі деп аталады, ал anәрпі—сөзінің соңы немесе постфиксі деп аталады. Сөздерді біріктіруге болады. Ол үшін екінші сөздің префиксі бірінші сөздің постфиксінен кейін бірден жалғануы керек және олар жаңа сөзде өз статустарын жоғалтады, егер сөздердің бірі бос болмаса. 1 және 2 сөздерін біріктіру 1, 2 түрінде белгіленеді, п бірдей сөздерді біріктіру n түрінде белгіленеді,және де0 . А алфавитінің бос емес сөздер жиынын А* деп белгілейміз: A* | l( ) 0 жиынын хабарламалар алфавиті, ал В жиынын кодтаушы алфавит деп атайды. В алфавитінде құрылған сөздер жиынын В* деп белгілейміз. F арқылы А алфавитінің сөздерінің В алфавитіне кескінделуін бейнелейміз. Онда F сөзін сөзінің коды деп атаймыз. Кодтау деп ақпараттың оны сақтау,беру және өңдеу кезінде хабарламаэлементтері мен сигналдар арасындағы сәйкестіктер жүйесі түрінде кескінделуінің әмбебап тәсілін айтады, олардың көмегімен бұл элементтерді тіркеуге болады. Осылайша, код – хабарламаны бір символдық берілу формасынан (бастапқы А алфавитінен) басқа бір формаға(В объектілі алфавитіне) ақпарат шығынынсыз бірмәнді түрлендіру ережесі (яғни, функция). А бастапқы алфавитінің сөздерін В алфавитіне F:А*→В* түрлендіру процесі ақпаратты кодтау деп аталады. B* сөзін A* сөзіне кері түрлендіру процесі декодтау деп аталады. Осылайша, декодтау F – кері функция, яғни . Кез-келген кодтау үшін декодтау орындалатын болғандықтан түрлендіру қайтымды болуы керек (биекция). Егер |B|= m, онда F m-ншы кодтау деп аталады, ең көп тараған түрі = {0, 1}-екілік кодтау.Осы түрі әріқарай қарастырылатын болады. Егер барлық кодтық сөздердің ұзындықтары бірдей болатын болса, онда код бірдейөлшемді немесе блокты деп аталады. Алфавиттік кодтауды (немесе әріптеп кодтауды) кодтар кестесі түрінде беруге болады. Ко д немесе кодтаушы функция қызметін қандай да бір орналастыруы атқарады. Онда 1 2... n 1 2... n,
жүктеу/скачать 1,12 Mb. Достарыңызбен бөлісу:
|