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

үш еселі қателерді анықтайтын кодтар үшін,

 

                                                                                           (10)

 

Немесе

 

                                                                  (11)

 

 бір немесе екі қатені  түзететін ұзындығы n символдардағы  кодтар үшін,

                                                                                         (12)

 

тәжірибеде есептеулер үшін мына өрнекті пайдалану кажет

 

                                                                                       (13)

 

(d₀=7) 3 қатені түзететін кодтар үшін,

 

                                                                       (14)

 

(d₀=2s+1) s қателерді түзейтін кодтар үшін,

 

                                               (15)

 

Сол жақтағы өрнек  Хэммингтің төменгі шекарасы ретінде  белгілі, ал оң жақтағы өрнек Варшамов – Гильбеттің жоғары шекарасы ретінде белгілі.

Жуық есептеулер үшін мына өрнекті қолдануға болады.

 

                                                                              (16)

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6 Сызықтық кодтар

 

 

Тексерілетін символдар  ақпараттық символдардың сызықтық конбинациялары болып көрсетілетін кодтар сызықтық деп аталады.

Екілік кодтар үшін сызықтық операциялар ретінде 2 модуль бойынша қосылғыш пайдаланылады.

2 модуль бойынша қосылғыш  ережесі мына теңдіктермен анықталады:

Осы кодқа жататын  нөлдер мен бірліктердің тізбектілігін  кодтық вектор деп атаймыз.

Сызықтық кодтар қасиеті: сызықтық кодтың кодтық векторларының жиыны (айырымы), аталған кодқа жататын векторды береді.

Сызықтық кодтар 2 модуль бойынша қосу операциясына қатнасы  бойынша алгебралық топ құрады және бұл мағынасында олар топтық кодтар болып саналады.

Топтық кодтың қасиеті: топтық кодтың кодтық векторлары арасындағы ең аз кодтық қашықтық нөлдік емес кодтық векторлардың ең аз салмағына тең болады.

Кодтық вектордың аймағы (кодтық комбинациялар) оның нөлдік емес компоненттерінің санына тең.

Екілік кодтық векторлар арасындағы қашықтық 2 модуль бойынша алғашқы векторларды қосу нәтижесінде алынған векторларды қосу нәтижесінде алынған вектор салмағына  тең. Осылайша, осы топтық код үшін W_min=d₀.

Топтық кодтарды, өлшемдегі n_м және n_к кодтың параметірімен анықталған матрицалармен берген ыңғайлы болады. Матрицадағы жолдар саны n_м – ге тең, матрицалар бағаналарының саны n_м+ n_к + n_-ге тең:

 

.                                                        (17)

 

Осы матрицалар туғызатын  кодтар (n;k)- кодтар ретінде белгілі, мұндағы k=n_м, ал оған сәйкес келетін матрицалар туғызатын, өндіруші, құрушы деп аталады.

С туғызушы матрица А  және Т ( ақпараттық және тексерілетін) екі матрицалармен көрсетілуі мүмкін. Т матрицалары бағаналарының  саны  n_к –ға, ал А матрицалары бағаналарының саны n_м –ге тең;

 

                                    (18)

 

Теорияда және тәжірбиеде дәлелдегендей, канондық формулағдағы бірлік матрицаны матрицалар ретінде  алған ыңғайлы болады:

 

_.                                                                                                           (19)

 

Т матрицаны таңдау кезінде  мынадай тұжырымдардан шығарады: Т тексерілетін матрицалардың разрядтарында  бірліктер неғұрлым көп болса, оңтайлы  кодқа оңтайлы 1-ге тиісті туындалатын код соғұрлым жақын болады, екіншіден, Т матрицалар бірліктерінің саны шифраторда және дешифраторда 2 модуль бойынша суматорлар саның анықтайды. Т матрицада бірліктер саны неғұрлым көп болса, аппаратура соғұрлым көп болады. Т матрицасының әрбір жолдарының салмағы - ден аз болмауы тиіс, мұндағы -А матрицасының тиісті жолдарының тиісті  жолдарының салмағы. Егер А матрицасы – жалғыз болса , онда =1 (А матрицасы санында бірлік матрицаны тандау ыңғайлы болатыны анық: >1 кезінде кодтарды құру да, технологиялық жүзеге асыру да күрделі боларп еді). Айтылған шарттарды сақтау кезінде топтық кодтың кез келген туындататын матрицасын мынадай түрге келтіруге болады:

a₁a₂a₃…a_nAp₁p₂…p_nA

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

Артық разрядтардың саны ең аз болатын түзетуші кодтар тығыз  қапталған немесе жетілдірілген  кодтар деп аталады.

= үшін n және n₀ арақатынас мынадай: (3;1), (7;4), (15;11), (31;26), (63;57) және т.б.

Тығыз қапталған кодтар, r+1, r+2 еселік қателер нұсқаларының ең көп мүмкін саны анықтайтын және 6 және n 40 қа ие болатын Д слепян зерттеген болатын. Осы кодтарды алу үшін Т матрица салмағы ең жоғары комбинацияларға ие болуы тиіс. Бұл  үшін ³3 кодтарын құру кезінде ұзындығы n-n_U, салмағы W_T=n_K, n_k-1, …,d₀-1 векторлар тізбекпе пайдаланады. Слепян аз тығыздықпен жұптылыққа тығыз емес қапталған кодтарды зерттеді. Бұл кодтар апаратуралардың қарапайымдылығы тұрғысынан үнемді және туындататын матрицалардың түзетуші разрядтарында бірліктердің ең аз санынан тұрады. Аса қарапайым шифратормен және дешифратормен кодтарды құру кезінде салмағы  W_T=2,3,... n_k векторлар тізбекпен тандалады, кодтың түзетуші разрядтарын көрсететін комбинациялар санын W_T³d₀-1 және көбірек n_u  комбинацияларын көрсетеді. Кодтың қалған комбинациялары мына ереже бойынша пайда болатын матрицалардың көмегімен құрылады: кодтың ақпараттық бөлігінде қателерді анықтау немесе түзетуге арналған түзетуші символдар, нөмірі разрядтар нөмірлерімен дәл келетін, кодтың ақпараттық бөлігін көрсететін кодтық векторда бірліктерден тұратын, Т матрицаның сол жолдарындағы 2 модуль бойынша қосындылау жолымен табылады. Алынған комбинацияны оң жақтан кодтың ақпараттық бөлігіне қосып векторын алады. Алғашқы алфовиттегі бүкіл символдарды беру үшін түзетуші код құрылғанғадейін, екінші, үшінші және одан кейінгі ақпараттық кодтық комбинациялармен осыған ұқсас рәсім созыла беретін болады.

Кодтың белгілі бір  ақпараттық бөлігі бойынша тексерілетін символдар құру алгоритмі мына түрде  жазылуы мүмін:

 

,

,

.........................

,

Немесе                                                (20)

Декодтау үдерісінде, жалпы түрде оның идеясы мына түрде  көрсетілуі мүмкін тексерулер жүргізеді:

,                                      (21)

 

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

Тексерулерді жүзеге асыру нәтижесінде синдром деп аталатын, S1,S2,…Sn_k тексерілетін вектор пайда болады. Егер синдром салмағы нөлге тең болса, онда қабылданған комбинация қателіксіз болып саналады. Егер тексерілетін вектордың, ең болмағанда бір разряды бірліктен тұрса, онда қабылданған комбинацияда қате болады. Қателерді түзейту синдром түрі бойынша жүргізіледі, өйткені әрбір қате разрядқа бір жалғыз тексерілетін вектор сәйкес келеді.

Синдром түрі әрбір нақты  матрица үшін Т транспонирленген матрица болып көрсетілген бағаналар  саны; кодтың тексерілген разряд санына тең,I_nk  бірлік матрицаларымен толықтырылған,Н тексерілетін матрица көмегімен анықталған болуы мүмкін.

Осындай матрицаның бағаналарымен  Н матрица бағанасының нөміріне сәйкес келетін разряд үшін синдром мәні болып көрсетіледі,

Топтық кодтарды декодтау үдірісінде қателерді түзету рәсімі мыналарға саяды:

Кодтық кесте кұрылады,Кестенің бірінші жолына А_і бүкіл кодтық векторлары орналасады.Екінші жолдың бірінші бағанасыда,салмағы 1-ге тең е₁ вектор орналасады.

Екінші жолдың қалған позициялары, бірінші жолдың тиісті бағанасында орналасқан А_і вектормен е₁ вектордың 2 модулі бойынша қосындылу нәтижесінде алынған векторлармен толтырылды,Үшінші жолдың бірінші бағанасында,салмағы сондай-ақ 1-ге тең,бірақ,егер е₁ вектор бірінші разрядтағы бірліктен тұрса, онда е_2-екінші разрядтағы бірліктен тұратын, е₂ вектор жазылады.Үшінші жолдың қалған позициялары А₁ және е₂ жиындарын жазады.

Салмағы 1 e₁ бүкіл векторлары A_i векторлармен, n разрядтардың әрбіріндегі бірліктермен қысыландыланған дейін, осыған ұқсас түсе беретін болады. Содан кейін, бүкіл мүмкін разрядтардың тізбекпен жаба отырып, салмағы 2, e_i векторлардың 2 модулі бойынша қосындыланады.  e_i  векторлар саны қайталанбайтын синдромдардың мүмкін санымен анықталады және -1 ге тең (нөлдік комбинация қателердің жоқтығын растайды). Синдромның қайталанбайтындық шарты, оның түрі бойынша оған жалғыз сәйкес келетін e_i векторын анықтайды. e_i векторлары берілген топтық кодпен түзетілуі мүмкін қателер векторы болып табылады.

Синдром түрі бойынша  қабылданған комбинация, e_i қателер векторымен  A_i кодтық комбинациялармен 2 модуль бойынша қосумен пайда болған сол немесе өзге шектес класқа, яғни кодтық 1 кестенің белгілі бір жолына жатқызылуы мүмкін.

 

A              e	A1	A2	...
e1			…
e2			…
…	…	…	...	…
			…

                               

                        1-кесте. Қабылданған кодтық комбинация

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

e₁, e₂, …, e_2nk-1 векторлар A₁, A₂, …, A_2nk-1 векторлардың бірде біреуіне тең болмауы тиіс, оған керісінше жағдайда кестеде нөлдік векторлар пайда болады.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7 Травиальді жүйелік кодтар

 

 

Травиальді Жүйелік кодтар- ақпараттық және түзетуші разрядтар қатаң белгіленген жүйе бойынша орналасатын және кодтық комбинацияларда әрқашанда қатаң белгіленген орынға ие болатын кодтар. Жүйелік кодтар бірқалыпты кодтар болып саналады және берілген түзетушілік қабілеттерімен бүкіл комбинациялар бірдей ұзындыққа ие болады. Топтық кодтар сондай-ақ жүйелік топтық бола алмайды. Травильді жүйелік кодтар, туындатушы матрица негізінде, топтық сияқты құрылуы мүмкін. Әдетте туындатушы матрица, рангі ақпараттық разрядтар санымен және бағаналар саны кодтың бақылау разрядтарының санымен анықталатын қосымша санымен анықталатын бірлік матрица көмегімен құрылады. Қосымша матрицаның әрбір жолы аз дегенде d₀-1 бірліктен тұруы, ал кез келген жолдар үшін модуль бойынша жиыны аз дегенде d₀-2 бірлік болуы тиіс (мұндағы d₀ –ең аз кодтық қашықтық). Туындатушы матрица, барлық мүмкін тіркестерде туындатушы матрица жолдары үшін модуль бойынша қосындылаумен бүкіл қалған кодтық комбинацияларды табуға мүмкіндік береді.

Хәмминг коды жүйелік  кодтың типтік мысалы болып саналады. Бірақ оның құру кезінде әдетте матрицаларға жүгірмейді. Кодтың негізгі параметрлерін  есептеу үшін, я ақпараттық символдар  саны, я N=2^nk ақпараттық комбинациялар саны беріледі. (5) және (6) көмегімен n_A және n_k есептеледі. Хэминг үшін  n, n_A және  n_k арасындағы арақатынас 8-қосымшаның 1-кестесінде берілген. Түзетуші кодтың негізгі параметрлерін біле отырып, дабылдардың қандай позициялары жұмысшы, қандай позициялары бақылаушы болатынын анықтайды. Тәжірбие көрсеткендей, бақылау символының нөмірлерін 2ⁱ заңы бойынша таңдаған ыңғайлы болады, мұндағы i=0, 1, 2 және т.б.-сандардың натурал қатары. Осы жағдайдағы бақылау символдарының нөмірі тиісінше: 1, 2, 4, 8, 16, 32 және т.б. болады.