Бөгеттерге тұрақты кодтаудың әр түрін қолданатын кателерден қорғау

 Кіріспе

 

 

Кодтау теориясы —  компьютингтің дамуына өз үлесін қосқан математиканың бір облысы болып табылады. Оның таралу облысы мәліметтерді нақты каналдар бойынша  беру, ал оның пәні берілген ақпараттың нақтылығын қамтамасыз ету болып  табылады. Кейбірде кодтау теориясын шифрлеумен шатастырады, бірақ ол дұрыс емес: криптография кері есепті шешеді, оның мақсаты - мәліметтерден ақпаратты алуды қиындату.

Кодтау (кодирование; coding; кодировать; encode) — мәліметтерді олардың  алдын ала тағайындаған кодтық комбинацияларымен бейнелеу немесе мәліметтер элементін (символдар жиынын) олардың кодтық комбинацияларымен сәйкес келтіру; программалау процесі; 2) ақпараттың 8 биттік (байттық) кодтауын 7 биттік кодтауға түрлендіру. Мұндай түрлендірудің қажеттілігі кейбір желілік программалардың мәліметтерді тек 7 биттік кодтауда жеткізе алатындығынан туындайды. Байттық мәліметтерді осындай арналармен тікелей жеткізу ақпараттың бұрмалануына жол береді; 3) белгілі бір ереже бойынша дискреттік хабарды дискреттік сигнал түріне түрлендіру (аудармалау), яғни шарт таңбаларды қолдану.

.Хаффмен алгоритмі кодтай айнымалы ұзындықтағы кодтық қабаттардың көмегімен болатын кодтау жүйесі. Онда анықталған әріптер мүмкіндігінше қысқа кодтық сөздермен көрсетіледі. Бұл кезде кодтық сөздер қабылдау кезінде декодирленеді.

ECC жаңа кодтардың бірі  ретінде LDPC (Low-Density Parity-check Code) кодын  айтуымызға болады. Негізінде олар  отыз жыл бұрын танымал болған, бірақта қазіргі уақытта оларға ерекше көңіл бөлінуде. LDPC коды 100-пайыздық анықтылығы бомағанмен, ол қатенің мүмкіндігін керекті нәтижеге дейін жеткізуімізге мүмкіндік береді және сонымен қатар каналдың жіберу мүмкіндігі максимальді толық түрде қолданылады. Оларға  «турбокодтар» (Turbo Code) өте жақын келеді, олар алыс космостағы объектілермен жұмыс жасағанда өте қолайлы.

Қабылданған хабардағы  қатені анықтау мүмкін болу үшін, қате кодты дұрыс кодтан дұрыс ажыратуға  мүмкіндік беретін, бұл хабардың кейбір артық ақпараты болуы тиіс. Мысалы, егер берілген хабар үш абсалютті  бірдей бөліктерден тұрса, онда қабылданған хабарлардағы дұрыс символдарды қате символдардан бөліп алу жөнелтпенің бір түрінің (мысалы, 0 немесе 1) жинақталу нәтижелері бойынша жүзеге асырылуы мүмкін.

Қабылданған хабар сондай-ақ кодтан және оның инверсиялырынан тұруы  мүмкін. Инверсиялар коды, біртұтас ретінде байланыс арнасына жіберіледі. Қабылдау ұшындағы қате код пен оның инверсияларын салыстыру кезінде шығады. Хабар символдарының кез келгенін бұрмалау тыйым салынған комбинацияларға әкелмес үшін, кодта символдар қатарында бір-бірінен өзгешеленетін комбинацияларды бөліктеу, осы комбинациялардың бір бөлігіне тыйым салу және сол арқылы кодқа артықтық енгізу қажет.

1 Кодтау 

 

 

Кодтау (кодирование; coding; кодировать; encode) — мәліметтерді олардың  алдын ала тағайындаған кодтық комбинацияларымен бейнелеу немесе мәліметтер элементін (символдар жиынын) олардың кодтық комбинацияларымен сәйкес келтіру; программалау процесі; 2) ақпараттың 8 биттік (байттық) кодтауын 7 биттік кодтауға түрлендіру. Мұндай түрлендірудің қажеттілігі кейбір желілік программалардың мәліметтерді тек 7 биттік кодтауда жеткізе алатындығынан туындайды. Байттық мәліметтерді осындай арналармен тікелей жеткізу ақпараттың бұрмалануына жол береді; 3) белгілі бір ереже бойынша дискреттік хабарды дискреттік сигнал түріне түрлендіру (аудармалау), яғни шарт таңбаларды қолдану.

Кодтау теориясы —  компьютингтің дамуына өз үлесін қосқан математиканың бір облысы болып табылады. Оның таралу облысы мәліметтерді нақты каналдар бойынша  беру, ал оның пәні берілген ақпараттың нақтылығын қамтамасыз ету болып табылады. Кейбірде кодтау теориясын шифрлеумен шатастырады, бірақ ол дұрыс емес: криптография кері есепті шешеді, оның мақсаты - мәліметтерден ақпаратты алуды қиындату.

Мәліметтерді кодтаудың  қажеттілігімен алғашқы рет жүз  елу жыл бұрын тап болды. Каналдар өте қымбат және сенімсіз болғандықтан телеграммаларды жіберудің өте  тиімді жолдары қарастырылды.1845 жылы пайдалануға арнайы кодтау кітаптары  шықты; олардың көмегімен телеграфистер қолмен мәліметтердегі ұзақ сөйлемдерді қысқа кодтармен алмастырды. Сол кездері мәліметтердің жіберілуінің дұрыстығын тексеру үшін жұптық бақылау әдісі қолданылды, бұл әдісті перфокарталардың дұрыстығын тексеру үшін компьютердің бірінші және екінші буындарында да қолданылды. Ол үшін ең соңғы мәліметтер колодасына арнайы дайындалған бақылау сомасы бар картаны салған. Егер енгізу құрылғысы сенімсіз болса (немесе колода тым ұзын болған жағдайда), онда қате тууы мүмкін. Оны жөндеу үшін картадағы сомамен сәйкес келмегенше процедураны қайталай беретін. Бұл сұлбаның ыңғайсыз болғанымен қатар, ол екі есе қателер жіберетін. Байланыс каналдарының дамуымен қатар бақылаудың өте тиімді механизмі керек болды.

Бұл мәселенің теориялық  шешімін алғашқы болып ақпараттың статистикалық теориясынының негізін  қалаушы Клод Шеннон ұсынды. Шеннон өз заманының жұлдызы болды,ол АҚШ-тың академиялық элитасынынң мүшесі болған. Ванневар Буштың аспиранты болып, ол 1940 жылы жасы 30 жетпеген оқымыстыларға берілетін Нобель атындағы сыйлыққа ие болды (Нобель премиясымен шатастырмаңыздар). Bell Labs жұмыс істеп жүріп Шеннон «Мәліметтерді жіберудің математикалық теориясы» (1948) атты жұмыс жазды, ол жұмыста Шеннон  каналдың жіберу мүмкіндігі мәліметтердің энтропия бастауынан жоғары болса, онда мәліметтерді ешқандай ақаусыз жіберілетіндей етіп кодтап қоюға болатынын дәлелдеді.Бұл түйіндеме Шеннонның көптеген дәлелдеген теоремалардың біреуінде бар. Сонымен қатар, ол каналда шудың бар болуына қарамастан мәліметтің жіберілу мүмкіндігінің теориялы түрде дәлелдеп берді.Шеннонның Мичиган штатында өзінің туып өскен қаласында орнатылған ескерткішінде ойып жазылған формуланы C = W log ((P+N)/N) Альберт Эйнштейннің E = mc2 формуласының мәнімен салыстырады.

Шеннонның еңбектері  ақпараттар теория облысындағы ары  қарай  зерттеулерінде өз ықпалын  тигізді, бірақта оларда инженерлік практикалық  қосымшасы бар болмады. Теориядан  практикаға алмасу Ричарда Хэммингтің жұмысынан байланысты болды. Ол Шеннонның Bell Labs бойынша әріптесі болды және кодтар класын ашқандығы үшін әйгілі болды, оларды «Хэмминг коды» деп атады. Өзінің жаңалығын Хемминг 40 жылдардың ортасында Bell Model V есептеуіш машинасының перфокарталармен жұмыс жасау қолайсыздығынан ашты деген аңыз бар. Оған операторлар жоқ болғанда, яғни демалыс күндерде машинамен жұмыс жасауға мүмкіндік берді және ол өзі енгізулермен жұмыс жасады. Хемминг байланыс каналдарындағы, сонымен қатар компьютерлердегі ақпараттарды беру магистральдарында, ең бастысы жад пен процессор арасындағы қателерді түзете алатын кодты ұсынды. Хемминг коды Шеннон теоремасында көрсетілген мүмкіндіктерді практикалық түрде қалай іске асыруға болатындығын көрсетеді.

Хемминг өзінің мақаласын 1950 жылы жарыққа шығарды, бірақта  ішкі жазбаларда кодтау теориясы 1947 жылмен белгіленген. Сондықтанда кейбіреулер  кодтау теориясының атасы ретінде  Шеннонды емес, Хеммингті атау керек деп ойлайды. Бірақта, техника тарихында алғашқыны іздеу пайдасыз нәрсе.

Хемминг бірінші болып  «қателерді түзейтін кодтарды» (Error-Correcting Code, ECC) ұсынғандығы анық екенін білеміз. Бұл кодтардың қазіргі заманғы  модификациялары барлық ақпараттарды сақтау жүйелерінде және жад пен процессор арасындағы алмасулар үшін қолданатыны белгілі. Олардың бір нұсқасы Рид-Соломонның коды компакт-дискілерде қолданылады.  Хэмминг тәсілі бойынша жасалынған көптеген кодтар нұсқалары бар, олар кодтау алгоритмдері бойынша және тексеретін биттер саны бойынша айырмашылықтары бар. Мұндай кодтарға планетааралық станциялармен космостық байланыс жасау үшін ерекше көңіл беріле бастады, мысалы, Рид-Мюллердің кодтарын 7 ақпараттық битке 32 тексеруші бит немесе 6 ақпараттық битқа – 26 тексеруші биттар келетін болды.

ECC жаңа кодтардың бірі  ретінде LDPC (Low-Density Parity-check Code) кодын  айтуымызға болады. Негізінде олар  отыз жыл бұрын танымал блған,  бірақта қазіргі уақытта оларға  ерекше көңіл бөлінуде. LDPC коды 100-пайыздық анықтылығы бомағанмен, ол қатенің мүмкіндігін керекті нәтижеге дейін жеткізуімізге мүмкіндік береді және сонымен қатар каналдың жіберу мүмкіндігі максимальді толық түрде қолданылады. Оларға  «турбокодтар» (Turbo Code) өте жақын келеді, олар алыс космостағы объектілермен жұмыс жасағанда өте қолайлы.

 

2 Хабарламаны кодтау  көздері

 

 

Кодтау теориясының  тарихына Владимир Александрович Котельниковтың аты нық жазылған. 1933 году  «Материалах  по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи»-да ол өзінің «О пропускной способности ‘эфира’ и ‘проволоки’» атты жұмысын жариялады. Бұл теоремада жіберілген сигнал ақпараттың жоғалтуынсыз қайтадан қалпына келетін шарттарды анықтайды.

Сандық байланыс каналы кодтаушысы мен хабарлама көзі арасында хабарламаны кодтаушы көздері қосылған. Хабарлама көздері сандық (компьютер, магнитті немесе оптикалық диск) немесе аналогты (телефонды, телевизиялық, телеметрикалық) сигналдар болып бөлінеді.  Хабарламаны кодтау көздерінің міндеті болып, экономды түрде байланыс каналына хабарламаны сандық түрде көрсетуді жеткізу болып табылады. Хабарламаны кодтау көздерін тағы да хабарламаларды сығу құрылғысы деп те атайды. Егер сандық хабарлама көзі Rи жылдамдықпен екілік символдардың ағынын құрса, онда хабарлама кодтаушысының шығысында R<Rи жылдамдықты ақпараттық бит ағыны пайда болады. Бұл жылдамдықтардың қатынасы сығу коэффициенті болып табылады:

Ксғ= Rи  / R,

мысалы,  V.34 модемі үшін мәтіндік ақпараты бар сығу құрылғысы  Ксғ=4 сығу коэффициентімен жасалған. Өйткені V.34 модемінің шығысында Rи=128кбит/с болған кезде R  = 32 кбит/с мәніне ие.

Телефондық  сигналдарды  берген кезде Rи=64кбит/с жылдамдықты  да қоюға болады. Бұл беру жылдамдығы кезінде аналогты телефонды сигналдың  телефон сигналының сапасын жоғалтпай сандық түрге айналуы жүреді. Бригадалық эксперттің тыңдауы көрсеткендей, жеткен сигналдың қайтадан аналогтыға ауысуы, яғни оны қайтадан кері аударып тыңдау  кезінде ол сигналдың бастапқы кезінде шыққан сигналдан еш айырмасы жоқ екендігі анықталған.

Қазіргі кездегі түрлі-түсті  телевизиялық сигналдар үшін оның сапасы жоғалмастан Rи= 256кбит/с жылдамдыққа  дейін жетеді. Бұл кезде телевизиялық сигналдың коммерциялық сапасында  сығу коэффициенті Ксғ=50-100 мәніне жетеді.

 

 

 

 

 

 

 

 

 

 

3 Хаффмен алгоритмінің кодтаушысы

 

 

 Хаффмен алгоритмі  кодтай айнымалы ұзындықтағы  кодтық қабаттардың көмегімен  болатын кодтау жүйесі. Онда анықталған әріптер мүмкіндігінше қысқа кодтық сөздермен көрсетіледі. Бұл кезде кодтық сөздер қабылдау кезінде декодирленеді.

Хаффмен әдісі бойынша әріптер баған бойына жоғарыдан төмен қарай жазылады. Ол Р (хі) ықтималдығы бойынша кему ретімен орналасып, кодтық ағаш сұлбасын түзеді (1-сурет).

Кодтық ағаш құруды ықтималдырақ х8   және х7 символдарынан бастаймыз. Бұл екеуін жоғарғы бұтаққа біріктіріп, жоғарғысына «0», ал төменгісіне «1» саламыз. Бұл екі бұтақтың ықтималдығы бірігіп ортақ суммалық ықтималдық құрайды. Ары қарай келесі ықтималдықты бұтақтарды біріктіреміз және солай жалғаса береді. Кодтық сөздер қозғалыс кезінде оң жақ шетінен бастап шеткі сол жаққа дейінге жерден алынады. Ағаш бойымен жоғары қозғалғанда «0» символы, төмен қозғалғанда «1» сиволы алынады.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 Кодтау теориясының жалпы ұғымдары

 

 

Біз, қателердің туындау ықтималдығы  нөлге жақын ( идеалда = 0) дискретті арнаға ие боламыз деп жорамалдайық. Осындай арна мінсіз арна немесе шуылсыз арна деп аталады. Бұған сәйкес арнаның өткізу қаблеті C=u_k * logM мен анықталады. Мінсіз арнаның болуы кезінде ақпараттарды ол бойынша H’(U) сенімділікпен сипатталатын U еркін дискреттік көзден арнаның өткізу қаблетіне тең жылдамдықпен, жоғалтусыз хабар беру мүмкіндігі туралы мәселені қою заңды.

Арнадағы ақпараттарды беру жылдамдығы оның өткізу қабілетіне тең болуы үшін арнадан шығарда I(Z,Z*) шаманы арттыратын, белгілі бір статистикалық қасиеттермен дискретті көз қолданылуы тиіс. Жекелей алғанда, біздің қызығушылығымызды туғызатын мұндағы кедергілерсіз мінсіз арна жағдайында осындай көз ең үлкен энтропияға немесе нөлдік артықшылыққа ие болуы тиіс, яғни тәуелсіз тең ықтималды хабарлар беруі қажет. Есептердің қойылымы көзінде еркін дереккөзінен кез келген статистикалық қасиеттермен, яғни нөлдік емес артықшылыққа ие хабарлар беру мүмкіндігін қажет етеміз. Осылайша, кодер атқарымдары статистикалық мағынада көз хабарларының арнаға кіруімен келісуі болып саналады.  Осы келісім есептері түпкі қорытындысында хабарлардың артықтығын жоюға әкеледі. Кодер хабарларды кодтауды жүзеге асырады, яғни белгілі бір ереже бойынша әрбір дискреттік хабарға көлемі М алфавиттен символдардың тізбектілігін  сәйкестікке қояды. Бұл ретте арнаға кіруге қатнасы бойынша кодермен берілетін символдардың өзі статикалық қасиеттері алғашқы көз хабарларының дискреттік элементтері болып саналады. Хабарлардың еркін алғашқы көзінің артықтығынтолық жоятын кодер құру мүмкіндігі арнаның өткізу қаблетіне тең жылдамдықпен ақпараттарды қатесізберудің алға қойған тесептерін шешу мүмкіндігін анықтайды. Оны толық шешу кезінде төмендегі тендік дұрыс болып шығады.

H’(U)=u_c*H(U)=u_k*logM=C                                                                           (1)

Одан мынаны аламыз

                                                                                   (2)

Мұндағы, Н(U) – берілетін хабарлар көзінің энтропиясы, u_к және u_с – уақыт бірлігінде берілетін хабармен кодқа сәйкес символдардың орташа саны, - бір хабарға келетін код символдарының орташа саны.

(1) және (2)тендіктерін дәл орындауға  жуықтау дәрежесі хабарлар көзінің  артықтығын азайту дәрежесіне  байланысты болады. Хабарлар көздерінің артықтығын жоюға мүмкіндік беретін кодтау тиімді немесе статистикалық деп аталады. Осындай кодтау нәтижесінде алынатын кодтар, тиімді немесе статистикалық деп аталады. Тиімді кодтау негізі болып қалануы мүмкін негізгі идеяларды қарастырамыз. Дискреттік көздердің артықшылығы екі себептермен:

Деректер көзінің жадысымен;

Хабардың бір қалыпты еместігімен  шарттасылады.

Қарапайым (элементар) хабарды ірілендіру көз жадысымен шарттасылған артықшылықты азайтудың әмбебап  тәсілі болып  саналады. Бұл ретте кодтау ұзын блоктармен жүзеге асырылады. Блоктар арнасындағы ықтималдылық байланыстары хабарлардың жекелеген элементтері арасындағы қарағанда аздау болады және блоктар неғұрлым ұзынырақ болса, олардың арасындағы тәуелділік соғұрлым аз болады. Ірілендіру мағнасын әріптік мәтін мысалымен түсіндіреміз: егер кез келген тілдегі әріптер арасындағы ықтималдылықбайланыстар салыстырмалы түрде күшті болса, онда олар сөздер арасында айтарлықтай аздау, абзацтар арасындағы тіпті оданда аздау болады. Сондықтан сөздерді, сөз тіркестерін, абзацтарды кодтауды қолдана отырып, біз ықтималдық байланыстарымен шарттасылған артықшылықты толықтай жоя аламыз. Бірақ бұл ретте хабарларды беруді кешіктіру көбейеді, өйткені алдымен хабарлардың бүкіл ұзын блогын қалыптастыруды күтіп, содан кейін ғана барып оны кодтау және беру қажет. Хабардың бір қалыпты еместігінен шарттасылған артықшылықты азайтуға бірқалыпты емес кодтарды қолданумен жетуге болады. Осындай кодтарды құрудың негізгі идеясы: неғұрлым ықтимал хабарлаға кодтық символдардың (кодтық комбинациялардың) неғұрлым қысқа блоктарын, ал ең кіші ықтимал блоктарға неғұрлым ұзын блоктарды сәйкестікке қою болып табылады. Осындай кодтардың бірқалыпты еместігінен және U хабардың кездейсоқ сипатынан, u_к  кодтық символдардың тұрақты жылдамдығымен ақпараттарды жоғалтусыз беру, үлкен жадысы бар буферлік жинақтағыштың болуы кезінде, демек үлкен кешіктірулердің ұйғарымдылығы кезінде ғана қамтамасыз етіледі.

Статистикалық кодтаудың шекті  мүмкіндіктері ақпараттарды беру теориясының  негізгі ережелерінің бірі болып саналытын шуылсыз арна үшін Шеннон теоремасында ашып көрсетіледі. Бұл теорема мына түрде тұжырымдалуы мүмкін:

Хабарлар көзі H’(U)=u_c*H(U) өнімділікке ие, ал арна C=u_k*logM өткізу қаблетіне ие болады. Сол уақытта,

                                                                            (3)

Хабар элементіне келетін  кодтық символдардың орташа санын алатындай  түрде көзден шығатын хабарды  кодтауды болады, мұндағы е –  керек болса, сонша аз (тура теорема).

- нен кіші мәнді алу мүмкін  емес (кері теорема).

                                                                                   (4)

Мәнін алу мүмкін еместігін  растайтын теореманың кері бөлігі, егер (4) теңсіздік u_c*H(U) >u_k*logM, H’(U)>c теңсіздіке эквиволентті екенін ескеретін болсақ, дәлелденуі мүмкін. Соңғы теңсіздік орындалмайды, өйткені қарастырылып отырған кодтау қайтымды түрлендіру (яғни ақпараттарды жоғалтусыз). Арнаға кірердегі бір секундтағы энтропия немесе кодердің өнімділігі арнаның өткізу қаблетінен артып кетпейді.

Тура теораеманы екі әр түрлі  тәсілдермен дәлелдейміз, бұл ретте  хабарлар көзін жадысыз көз деп  жорамалдайық, егер хабар элементтері  блоктарының аса үлкен К₁ ұзындығын, алфавит көлемі N_u  қарапайым хабар ретінде қарастыратын болсақ, оған керек болса, сонша жоғары дәлдік дәрежесімен кез келген көз келтірілуі мүмкін деп түсіну керек.   

Дәлелдеудің бірінші  тәсілі көзбен құралатын К символдардан хабарлардың жиынын қарастырулан тұрады. Көлемі N_u   алфавит тен таңдалатын U_i қарапайым хабарлардың К мазмұның осындай әрбір тізбектілігін a=(U_k-1U_k-2 U₁U₀) хабар деп санайтын боламыз. Жадыларсыз көздер үшін осы хабарлардың ықтималдылығы P(a)=P(U_k-1)*P(U_k-2)…P(U₀). Бұл ретте бір-бірінен жақсы а хабарларының L саны L= . К хабарының ұзындығы аса үлкен болған кезде мүмкін хабарлардың L бүкіл жиыны 2 ішкі жиынға бөлінуі мүмкін, олардың бірі, ықтималдылықтар қосындысы 1-d бірлікке жақын неғұрлым ықтимал хабардың К₁ нен тұрады(оны жоғары ықтимал немесе типтік деп атайтын боламыз), екінші, хабарлар қосындысының ықтималдылығы d нөлге жақын хабарлардан ( аз ықтимал немесе типтік емес) тұрады. К ны ұлғайта отырып, d ны кішірейтуге болады. Осы айтылғандар ықтималдылықтар теориясы заңынан шығарылады және соған сәйкес сынақтардың аса үлкен саны кезінде мүмкін нәтижелерінің әрбір саны өзінің математикалық үмітіне (үлкен саңдар заңы) жақын келеді. Аталған жағдайларда хабарладрдың К элементтерінің саны сынақтар саны болып, u_i элементтердің мәні алғашқы болып саналады және u_i нәтижелер саның математикалық үміті K*P(U_i)-ге тең. Сондықтан хабарлардың аса үлкен ұзындығы 0 элементтер санының K*P(0)- на жақын N_u-1 элементтер саны  K*P(N_u-1)- ға жақын, 1, элементтер саны K*P(1)- ға жақын. Осындай хабар жоғары ықтимал ішкі жиынды құрайды. Хабардың К Р кезінде элементтердің өзге санынан тұру ықтималдылығы өте аз болады. өйткені хабардың әртүрлі элементтерінің қандайда бір ұштасуының (сочетание) ықтималдылық көзінде жадының жоқ болуы кезінде олдардың санына ғана тәуелді болады, сондықтан жоғары ықтималдылық ішкі жыйынына жататын, яғни әртүрлі элементтердің шамамен алғанда сондай бір санынан тұратын және осы әлементтердің тізбектіліктерінде орналасумен ғана өзгешеленетін бүкіл хабар,  -ға жақын бір ықтималдыққа ие болады. Алынған тендікті логарифм дейміз:

 

К₁>1/Р жоғары ықтималдылық ішкі жиындағы хабарлар санының тең ықтималдылығынан, Р, К₁  логарифм үшін алынған  өрнекті ескеріп, дерек көз энтропиясы арқылы жазуға болады.

Р=2^-k*H(U), K₁=1/P=2^K*H(U)                                                                                (5)

 

өйткені L=

 

                                                           (6)

 

Мұндағы, - көздің артықтығы. (6) өрнекті талдау, көздің кез келген нөлдік емес артықтығы кезінде жоғары ықтимал ішкі жиын хабарлар саны, егер К хабар ұзындығы аса үлкен болса (қанша болмасын аз ықтималдылық аса ұзын хабарлардың үлкен бөлігіне ие болады) бүкіл мүмкін хабарлардың қандай да бір аз бөлігін құрайтындығын көрсетеді. Бұл басым көпшілік сан хабарлар элементіне кодтық символдардың ең аз санына жетуге мүмкіндік береді. Хабарлардың жоғары ықтималдылық тобына бөлетін дабыл ретінде пайдалану үшін біреуін қалдырып, n₁ ұзындықтардың бірқалыпты кодының әр түрлі қысқа (олар аз) кодтық комбинацияларын сәкестікке келтіреміз. Аз ықтималды ішкі жыйындарды құрайтын хабарлардың қалғандары үшін K₂=L-K₁>L. Жоғарыда айтылған ұзындықтары n_1, бөлінетін комбинациялардан басталатын (декодтау кезінде қабылданатын хабарды шектейтіндей болу үшін) n₂ символдардан тұратын неғұрлым ұзын кодтық комбинацияларды пайдаланамыз. n₁ және n₂ кодтардың ұзындықтарын (7) шартынан анықтаймыз, мұндағы, S- бірқалыпты кодтың әртүрлі кодтары комбинациялардың әртүрлі кодтары комбинацияларының саны, m- кодтық символдар алфавитінің көлемі, n- символдар саны (кодтық комбинациялар ұзындығы).

 

                                                                                             (7)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5 Криптографиялық кодтау

 

 

5.1 Кедергіге төзімді  кодтау

 

Қабылданған хабардағы қатені анықтау мүмкін болу үшін, қате кодты дұрыс кодтан дұрыс ажыратуға мүмкіндік беретін, бұл хабардың кейбір артық ақпараты болуы тиіс. Мысалы, егер берілген хабар үш абсалютті бірдей бөліктерден тұрса, онда қабылданған хабарлардағы дұрыс символдарды қате символдардан бөліп алу жөнелтпенің бір түрінің (мысалы, 0 немесе 1) жинақталу нәтижелері бойынша жүзеге асырылуы мүмкін. Екілік кодтар үшін бұл әдісті мынадай мысалмен көрсетуге болады:

10110-берілген кодтық  комбинация;

10010-1-ші қабылданған  комбинация;

10100-2-ші қабылданған  комбинация;

00110-3-ші қабылданған  комбинация;

10110-жинақталған комбинация. Байқағанымыздай, бүкіл қабылданған  үш комбинацияларда қателер болғандығына  қарамастан, жинақталған комбинацияда  қателер болмайды.

Қабылданған хабар сондай-ақ кодтан және оның инверсиялырынан тұруы мүмкін. Инверсиялар коды, біртұтас ретінде байланыс арнасына жіберіледі. Қабылдау ұшындағы қате код пен оның инверсияларын салыстыру кезінде шығады. Хабар символдарының кез келгенін бұрмалау тыйым салынған комбинацияларға әкелмес үшін, кодта символдар қатарында бір-бірінен өзгешеленетін комбинацияларды бөліктеу, осы комбинациялардың бір бөлігіне тыйым салу және сол арқылы кодқа артықтық енгізу қажет. Мысалы, бірқалыпты блоктық кодта, әрбір кодтық комбинацияларға нөлдер мен бірліктердің тұрақты арақатынасымен кодтық комбинацияларды шешілген (рұқсат етілген) деп санау керек. Осындай кодтар деген атауға ие болады. Екілік кодтар үшін салмағы тұрақты, кодтық комбинациялар санының n символдардағы ұзындығы мынаған тең:

 

                                                                                                  (1)

 

Мұндағы -кодтық сөздегі бірліктер саны. Егер тұрақты салмақ шарты қолданылмаған болса, онда код комбинацияларының саны анағұрлым үлкен, атап айтқанда 2ⁿ болар еді. Стандартты телеграфтық код №3, салмағы тұрақты кодтың мысалы болып пайдаланылуы мүмкін.Осы кодтың комбинациялары ,7 тактыға, сол уакыт ішінде бір комбинация қабылдануы тиіс түрде құрылады, яғни әрқашанда үш осындай және төрт осындай емес жөнелтпелер қажет болады. Осындай жөнелпелердің санын үлкейту немесе азайту , қателердің бар болуын растайды.

Олардың сомасы әрқашанда  жұп немесе тақ болатындай алғашқы  кодтарға нөлдерді , я бірліктерді  қосу әдісі кодтқа артықшылықты енгізудің тағы бір мысалы болып табылады. Кез келген бір символдың тоқтап қалуы әрқашанда жұптылық (тақтылық) шартын бұзады және қате анықталатын болады.Бұл жағдайда комбинациялар бір-бірінен , аз дегенде екі символдармен өзгешеленуі тиіс, яғни код комбинацияларының тура жартысы тыйым салынған болып саналады (жұптылыққа немесе керісінше тексеру кезінде букіл тақ ткомбинациялар тыйым салынған болып саналады).

Ілгеріде айтылған барлық жағдайларда хабар артық ақпаратқа ие болады.Хабардың артықтығы, егер сол , бір кодты көп рет қайталамаса, кодқа оның инверсиясын қоспаса, егер код комбинацияларының бір бөлігіне жасанды тыйым салмаса ,оның одан да көп ақпараттар санынан тұратындығын растайды. Бірақ бүкіл айтылған артықшылықтың түрлерін, қате комбинациясы дұрыс комбинациядан ажырата білу ушін енгізуге тіра келеді.

Кодтың кез келген екі комбинациялары бір-бірінен  өзгешеленетін символдардың ең аз санының, артықсыздық кодтарны а нықтай алмайтыны, оның үстіне қателерді түзей алмайтыны кодтық қашықтық деп аталады. Кодтың бүкіл комбинациялары бір-бірінен өзгешеленетін символдардың ең аз саны ең аз кодтық қашықтық деп аталады. Ең аз кодтық қашықтық –кодтың кедергіге төзімділігін анықтайтын және код артықтылығының параметрі. Ең аз кодтық қашықтық пен кодтың тузетуші қасиеті анықталады.

Жалпы жағдайда r  қателерді  анықтау үшін ең тазкодтық қашықтық

 

d₀=r+1                                                                                                               (2)

 

бір мезгілде анықтау және қателерді түзету үшін қажет ең аз кодтық қашықтық,

 

d₀=r+s+1                                                                                                           (3)

 

мұндағы, s- түзетілетін қателер  саны.

Қателерді түзететін  ғана кодтар үшін,

 

d₀=2s+1                                                                                                            (4)

 

екілік кодтың екі  конбинациялары арасындағы кодтық қашықтықты анықтау үшін, 2 модуль бойынша осы конбинацияларды қосындылау және алынған конбинациялардағы бірліктер санын санау жеткілікті болады.

Кодтық қашықтық ұғымы  кодтардың геометриялық модельдерін  құру мысалында жақсы игеріледі. Геометриялық модельдердегі n төбелердегі  – бұрыштар, мұндағы, n- кодтың мәнділігі кодтық комбинациялар орналасқан, ал бір конбинацияны екіншісінен бөліп тұратын n бұрыш қабарғаларының саны кодтық қашықтыққа тең.

Егер А екілік кодтың кодтық конбинациясы В кодтық конбинациядан d қашықтықта болса, онда бұл А кодында d символдарды, В кодын алу үшін кері символдарға ауыстыруы қажет, бірақ бұл кодтың түзетушілік қасиеттерге ие болуы үшін, d қосымша символдар қажет дегенді білдірмейді. Екілік кодтар бір қатені анықтау үшін кодтың ақпараттық разрядтарының санына тәуелсіз 1 қосымша символға ие болуы жеткілікті, ал ең аз кодтың қашықтық d₀=2.

Бір қатені анықтау және түзету үшін n_м ақпараттық разрядтар саны мен n_к түзетуші разрябтар саны арасындағы арақатынас мына шарттарды қанағаттандыруы тиіс:

 

                                                                                                          (5)

 

                                                                                                           (6)

 

Бұл ретте,кодтық комбинациялардың жалпы ұзындығы

 

                                                                                                         (7)

 

Тәжірибеде есептеу  үшін ең аз кодтық қашықтық пен кодтардың бақылау разрядтарының санын анықтау кезінде мына өрнекткрді пайдаланған ыңғайлы болады:

 

                                                                                               (8)

 

Егер n толық кодтық комбинациялардың ұзындығы белгілі болса және

 

                                                                     (9)

 

Егер есептеулер кезінде  берілген сандардан  ақпараттық символдарды табу ыңғайлы болса.