 |
Тақырып №4. Фано-коды. Тақырып №5 Префикстіқ қасиет. Бірмәнділік. Тақырып №6. Ауыстыру тәсілдері
|
|
|
|
Тақ ырып №4. Фано-коды.
Екі алфавиттен тұ ратын символдар арқ ылы кез-келген хабарды кодтауғ а болады. Бірақ, біз хабарлардағ ы символдарды ұ зындығ ы бірдей символдармен кодтадық. Ал мұ ндай тә сіл ә рқ ашан дұ рыс бола бермейді.
Мыслы: информацияда бір хабарлар ө те жиі, ал екінші бір хабарлар ө те сирек кездесуі мү мкін. Сондық тан, бірінші хабарды қ ысқ а, ал екінші хабарды ұ зын кодтармен берген тиімді болып табылады. Шығ ынды кодтық мә тіннің ұ зындығ ы орта есеппен қ ысқ а болады жә не оны беруге аз уақ ыт жұ мсалады.
Бізге кездесу ық тималдығ ы 
болатын бір символдар жиыны берілсін. 
болсын. Осы информацияны ұ зындығ ы 2-ге тең болатын кодтар арқ ылы ө рнектейік. А1 =00, А2 =01, А3 =10, А4 =11 Бұ лай кодтағ анда ә рбір информацияның ұ зындығ ы 2-ге тең болады. Осы кодтауды, ө згеше, тө мендегідей ұ йымдастыруды қ арастырайық. Ық тималдық кездесуге байланысты элементтерді шамамен 2-топқ а бө леміз. Бө луді осы ережемен ә рі қ арай жалғ астырамыз. Осығ ан сә йкес тө мендегідей кодтау шығ ады.
| 0 | ||
| 1 | 0 | |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
Мә ліметтерді бұ лай кодтауды алғ аш рет америка математигі Фано ұ сынғ ан. Осылай кодтау ө те тиімді болып таабылады екен. Мысалы: бізге бір мың белгіден тұ ратын хабарламаны жіберуіміз қ ажет. Мұ ны І тә сілмен шығ арсақ, ә рбір символғ а екі бит сә йкес келегендіктен жалпы 2000 символ қ ажет болады.
|
|
|
L= 
кодтардың ұ зындығ ы, 
- ық тималдығ ы.
L=1*1/2+2*1/4+3*1/8+3*1/8=1/2+1/2+3/8+3/8=4+4+3+3/8=
14/8=7/8=1, 75
Екінші жағ дайда ә рбір кодтың орташа салмағ ы 1, 75 –ке тең болғ андық тан барлығ ы 1750 символ колданылады.
Негізгі ә дебиеттер: [1, 2, 10]
Қ осымша ә дебиеттер: [11, 12]
Тақ ырып №5 Префикстіқ қ асиет. Бірмә нділік
Алдың ғ ы тақ ырыпта қ арастырылғ ан мысалғ а екі тү рлі кодтау жү ргізейік. Осы жазуларда жә не -те соң ғ ы 0-ді алып тастайық та, олардың орнына 1 саныны орналастырайық. Осылай жасау мү мкін тиімдірек болатын шығ ар.
0 10 110 111 1 - тү р
0 1 11 111 2 - тү р
Мұ нда ә рбір хабар бұ рынғ ысынша ә р тү рлі тізбектермен кодталады. Енді бізге осы сө зді робот немесе машина орындау керек болсын. Егер робот ү шін А1 –алғ а, А2 –артқ а, А3 –солғ а, А4 –оң ғ а жү ру болса, онда ол тө мендегі команданы қ алай тү сініп орындау тиіс: 0 1 1 0 1 1 1 0 1. . . Алғ ашқ ы мә н 0-ге тең болғ андық тан робот алғ а жү реді, бірақ келесі жү ретін жолы анық талмағ ан. Себебі робот 1 немесе 11 мә нінің қ айсысын алу керегін нақ ты анық тай алмайды. Біздің кодтауымызда оның екеуі де кездеседі.
Яғ ни ә рбір кодталғ ан символдан кейін оны екінші символдан ажырататын белгі болуы тиіс. Бұ л белгі бос орын немесе басқ а арнайы алынғ ан белгі болса, онда біздің кодтық мә тініміздің кө лемі ұ лғ айып кетеді.
Сондық тан кодтық мә тінде жеке кодтық сө здерді тағ айындап алады. Кодтық символдардың тізбегі тек бір ғ ана тә сіл арқ ылы кодтық сө здерге бө лінеді. Бұ л кодтаудың ең қ арапайым жә не жиі қ олданылатын тү рі префиксті кодтау деп аталады. Мұ нда кез келген кодтық сө з екінші кодтық сө здің жазылуының бастапқ ы жерінде кездеспейді. Егер код префиксты болса, олар арқ ылы жазылғ ан кез келген сө зді оқ ығ анда бір кодтық сө здің қ ай жерден басталып, қ ай жерде аяқ талатынын білеміз. Фано тә сілі бойынша алынғ ан код префикстік код болып табылады. Онда ә рбір код ө зге кодтың бас жағ ында ешқ ашанда кездеспейді.
|
|
|
Префикстік кодтың негізгі қ асиеті оның бір мә нділігі. Осы қ асиет арқ ылы кез келген кодталғ ан тізбекті шешуге болады.
Негізгі ә дебиеттер: [1, 2, 6, 9]
Қ осымша ә дебиеттер: [11, 12]
Тақ ырып №6. Ауыстыру тә сілдері
Ауыстыру тә сілі ө те ертеден белгілі жә не жиі қ олданылатын шифр болып табылады. Оларда хабарламаның (ә ріптер, сө здер, …) жеке бө ліктері басқ а бір ә ріпке, символғ а, санғ а жә не т. б. ауыстырылады. Сонымен қ атар ауыстыру шифрленген хабарлама бойынша жіберілетін хабарламаны қ алпына келтіруге болатындай орындалады.
Айталық, мысалы, хабарлама орыс тілінде шифрленсін жә не сонымен қ атар ауыстыруғ а хабарламаның ә рбір ә ріпі жатады деп есептелінсін. Бұ л жағ дайда, формальды тү рде, ауыстыру шифрын келесі тү рде беруге болады. Алғ ашқ ы алфавиттің ә рбір 
ә ріпі ү шін 
символымен белгіленетін сә йкес жиын қ ұ рылады. Егер 
болғ анда жә не 
жиындары қ иылыспайтын болса, онда кез келген екі ә ртү рлі жиын бірдей элементке ие болмайды. жиыны ә ріпі ү шін шифр белгіленген жиын деп аталады.
| а | Б | В | … | Я |
|
| 
| 
| … | 
|
(1)
кестесі ауыстыру шифрының кілті болып табылады. Осыны біле отырып, шифрлеу сияқ ты шифрді қ айта шешуді орындауғ а болады.
Шифрлеу кезінде ашық хабарламаның біріншіден бастап ә рбір ә ріпі жиынының кез келген символымен ауытырылады. Егер хабарлама бірнеше ә ріпінен тұ ратын болса, онда оның ә рбіреуі -дан алынғ ан кез келген символмен ауыстырылады. Осыны есепке ала отырып (1) кілтінің кө мегімен бір ашық хабарлама ү шін шифрлеудің ә р тү рлі варианттарын алуғ а болады.
|
|
|
Негізгі ә дебиеттер: [3, 6, 9, 10]
Қ осымша ә дебиеттер: [11, 12]
|
|
|
