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

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

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

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

 

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