Кедергіден сақталған (түзеуші) кодтар

1) қателерді табушы кодтар;

2) қателерді табушы және түзетуші кодтар.

Код арқылы қателерді табу және түзету принципі геометриялық модельдер бойынша көрсетіледі. Кез-келген n-элементті екілік кодты n-реттік куб арқылы бейнелейді, оның әрбір төбесі кодтық комбинация деп есептеледі, ал қырларының ұзындығы бір бірлікке тең. Ондай кубта төбелердің ара-қашықтығы төбелердің арасында орналасқан қырлардың ең аз санымен өлшенеді, d деп белгіленеді де Хэммингтің кодтық ара-қашықтығы деп аталады.

Осылайша, кодтық ара-қашықтық бұл - құрамында кез-келген кодтық комбинация басқасынан өзгешеленетін (барлық кодтық сөздер жұбы бойынша) элементтердің ең аз саны. Мысалы, код 1011,1101,1000 және 1100 комбинациясынан тұрсын. Алғашқы екі комбинацияны салыстыра отырып, оларды 2 модулі бойынша қосу арқылы d=2 екенін табамыз. Бірінші және үшінші комбинацияларды салыстыру бұл жағдайда да d=2 екенін көрсетеді. Ең үлкен d=3 мәні бірінші және төртінші комбинацияларды салыстыру кезінде байқалады, ал ең кіші d =1 екінші мен төртіншіні, үшінші мен төртіншіні салыстырғанда байқалады. Осылайша, берілген код үшін ең кіші ара-қашықтық d_min =1.

Екілік кодының екі комбинациялары арасындағы кодтық ара-қашықтық осы комбинацияларды 2 модулі бойынша қосу кезінде алынған бірліктер санына тең. Мысалы, 10+01=11 және 00+11=11. Осындай кодтық ара-қашықтықты анықтау жолы кодтардың үлкен разрядтылығында ыңғайлы.

+

10000000010

00110101111

Осы комбинацияларды қосу арқылы арасындағы кодтық қашықтықтың d=7 екенін көре аламыз.

Кодтық комбинацияның і-ші орнына 0 қойылады, егер сол төбенің і-ші оське проекциясы нөлге тең болса, және 1 қойылады, егер проекция бірге тең болса. Мысалы, А₆ төбесіне қандай комбинацияны жазу керек екенін табу керек. Осы төбені Х₁ осіне проекциялай отыра бірді аламыз. Комбинацияның екінші орнында дәл солай бір жазылады (Х₂ осіне проекция бірге тең).

Х₃ осіне проекция нөлге тең болғандықтан (проекция координат басында), комбинацияның үшінші орнында нөл жазылады. Осылайша бүкіл комбинация А₆ төбесіне 110 түрінде жазылады.

000,110,011,101. келтірілген комбинациялар белгілі ереже бойынша құралған, ал нақтырақ айтсақ, бірліктердің жұп санынан тұрады, ал қабылданған комбинайия 100-тақ. 100 комбинациясы рұқсат етілген комбинациялардың біреуінің разрядының бұрмалануынан пайда болды деп ұйғаруға болады, алайда нақты қай комбинация екенін анықтау мүмкін емес. Сондықтан сондай немес соған ұқсас кодтарды қателерді табушы кодтар деп атайды.

Дәл сол үш өлшемді кубтағы көрсетілген комбинациялар тобынан басқа тағы да бір кодтық ара-қашықтығы d=2 болатын комбинациялар тобын алуға болады(111,001,010,100). Бұл кодтық комбинацияларда бірліктедің тақ саны мен комбинациялардың әрқайсысы тасымалдау кезіндегі қателерді табу үшін қолданыла алады, себебі бір рет бұрмалану кезінде комбинацияда бірліктердің жұп саны болады. Бірақ егер жалғыз қатені табушы код қажет болса, онда тасымалдауға тек бір топ қатыса алады, яғни мүмкін болатын сегіз комбинацияның ішінен төртеуі. Кері жағдайда кедергіге шыдамсыз құрамында d=1-ден басталатын комбинациялары кезігетін код шығады.

Осылайша, кедергіден сақталған кодтарда рұқсат етілген, белгілі бір ереже бойынша құралған, және өзіне сәйкес ереже бойынша тыйым салынған комбинациялар бар.

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

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

Кодтың жөндеуші қасиеті кодтық ара-қашықтыққа тәуелді:

А) d=1 болғанда қате табылмайды;

Б) d=2 болғанда жалғыз қателер табылады;

В) d=3 болғанда жалғыз қателер табылады немесе екі еселі қателер табылады. Жалпы жағдайда

d=r+s+1

мұндағы d- ең кіші кодтық ара-қашықтық, r- табылатын қателер саны, s- жөнднлнтін қателер саны.

Сонымен қатар міндетті шарт болып r>>s табылады.

Мысалға d=3, және егер r=s=1, онда код бір қатені тауып, соны жөндей алады. Егер r=2, s=0, онда код екі қатені тек таба ғана алады. 1 теңдігіне қарағанда бір қатені жөндеу және екі қатені табу үшін d=2+1+1=4 қажет. d=4 болғанда r=3,s=0 деген нұсқалар болуы мүмкін. Егер d=5, онда үш нұсқа болуы мүмкін: r=s=2; r=3, s=1;r=4, s=0.

Егер код қателерді тек табатын болса, онда

d=r+1, яғни r=d-1.

Егер код қателерді тек жөндейтін болса, онда

d=2s+1, яғни s=(d-1)/2.

Хэмминг кодтары. Бұл кодтар барлық жалғыз қателерді түзетуге (d=3 болғанда), сонымен қатар барлық жалғыз(дара) қателерді түзетіп, барлық екі еселі қателерді табуға мүмкіндік береді, бірақ түзетусіз. Барлық дара қателерді түзететін Хэмминг кодын қарастырайық.

Бастапқы ретінде барлық үйлесімдегі ақпараттық символдардың k саны бар екілік кодты алады, оған m бақылау символдарын қосады. Осылайша кодталған комбинацияның жалпы ұзындығы n=k+m.

Хэмминг бойынша кодтау мен декодтау ретін қарастырайық.

Кодтау. Бақылау символдарының санын анықтау. Ол үшін төмендегі тұжырымдарды пайдалануға болады. Шуы бар канал бойынша тасымалдауда кодтың n символының кез-келгені бұрмалануы мүмкін, егер сөз бұрмаланусыз берілсе. Сондықтан, бұрмаланудың n+1 нұсқасы болуы мүмкін (бұрмаланусыз тасымалдауды бірге санағанда). Бақылау символдарын пайдалана отырып, барлық n+1 нұсқаны айра білу керек. m бақылау символдарының көмегімен 2^m жағдайды сипаттауға болады. Яғни, мына шарт орындалуы керек: 2^m≥ n+1= k+m+1

1 кестесінде олардың арасындағы тәуелділік келтірілген.
Кесте 3.1 – Хэмминг кодындағы m бақылау символдар санының k ақпараттық символдар санына тәуелділігі

k	1	2	3	4	5	6	7	8	9	10	11	12	13
m	2	3	3	3	4	4	4	4	4	4	4	5	5

Бақылау символдарын орналастыру. Негізінде бақылау символдарының орналасқан орны маңызды емес: оларды ақпараттық символдарға дейін де, кейін де, және оларды аралас жазуға да болады. Алайда бақылау символдарының қалауынша қойылғаны берілген кодтың тексерілуін қиындатады. Бұрмаланған символдарды табу ыңғайлы болу үшін оларды 2-нің дәрежесіне еселі орындарға орналастыру жөн, яғни 1,2,4,8 т.с.с. позицияларға. Ақпараттық символдар қалған орындарға орналасады. Сондықтан, мысалы, жеті злементті кодталған комбинация үшін төмендегідей жазуға болады:

m₁, m₂, k_4, m₃,k₃,k_2,k_1,

k₄ – кодталуға жататын екілік кодтың бастапқы комбинациясының үлкен (төртінші) разряды;

k₁ – кіші (бірінші) разряд.

Бақылау символдарының құрамын анықтау.

Элементтердің қайсысы бақылау позициясында тұру қажет екендігін (1 немесе 0) жұптылыққа тексеру арқылы тексереді. Оны мына комбинация мысалында қарастырайық: m₁, m₂, k_4, m₃,k₃,k_2,k₁ .

3.2 кестесінде барлық үйлесімдегі үш разрядты екілік кодқа арналған барлық кодтық комбинациялары жазылған, және жанында оң жағынан, жоғарыдан төмен қарай (2) жүйелі тізбектелген Хэмминг кодының комбинациясының символдары қойылған. 3.2 кестесінен төмендегідей заңдылық бойынша символдар үш бағанаға жазылған 3.3 кестесі құралады. Бірінші бағанаға қарам-қарсысына 3.2 кестесіндегі екілік кодтың комбинациясының кіші разрядындағы бірліктер қойылған символдар жазылады.

Кесте 3.3 –Хэмминг коды үшін бақылау кестесі

Тексеруші коэффициенттердің екінші бағанасына қарама-қарсысында екілік кодтың екінші разрядындағы бірліктер жазылған символдар қойылады.

Үшінші бағанаға қарам-қарсысында екілік кодтың үшінші разрядының бірліктері қойылған символдар жазылады (m₃,k₃,k_2,k_1,).

Декодтау.

Комбинацияның дұрыстығын тексеру үшін тағы да жұптылыққа тексеру тәсілін пайдаланады. Егер комбинация қателерсіз қабылданса, онда 2 модулі бойынша бірліктер қосындысы нөлді береді. Кез-келген символдың бұрмалануы кезінде тексеру барысындағы қосу бірді беруі мүмкін. Әрбір тексерудің қосу нәтижесі бойынша бұрмалану орнын көрсететін екілік сан құрылады. Мысалға бірінші және екінші тексерулер қатенің бар екенін көрсетеді, ал үшінші тексері барысындағы қосу нөлді береді. 011=3 санын жазайық, бұл сан құрамына бақылау символдары да кіретін кодтық комбинацияның үшінші символында бұрмалану пайда болғанын білдіреді, сондықтан бұл санды өзіне кері санға түзеті керек, яғни 1-ді 0-ге және 0-ді 1-ге.

Бақалау сұрақтары

1. Ақпаратты сақтау, тасымалдау және өңдеуде екілік кодты пайдалану артықшылығы неде?

2.Грей коды қандай мақсатпен қолданылады?

3.Разрядтап теңестіру тәсілінің мәні неде?

4.Аналогты-сандық түрлендіргіштердің түрлі типтерін жылдамдығы мен дәлдігі бойынша салыстырыңыз.

5.Нәтижелі тұрақты (эффективное статическое) кодтаудың мәні неде?

6.Шеннонның кедергісіз каналдар үшін кодтауы туралы негізгі теоремасын құрып, оны түсіндіріңіз.

7.Ұзын тізбектелген белгілерді кодтаудың нәтижелілігі қандай?

8.Нәтижелі кодтау кезінде ненің арқасында кодтық комбинацияның орташа ұзындығы қысқарады?

9.Шеннон-Фано әдісімен салыстырғанда Хаффмен ұчынған нәтижелі кодты құрау әдісінің артықшылығы неде?

10.Нәтижелі кодтарды пайдалану кезінде пайда болатын қиындықтарды атап өтіңіз.