Түзетуші кодтардын жіктемесі. Хэмминг коды, циклдік кодтар.

Тү зетуші кодтар деп акпараттарды тарату жане сактау кезінде богеуілдердін асерінен пайда болатын кателіктерді табуга немесе тү зеуге арналган кодтарды айтады. Тү зетуші кодтар блоктык жане ү здіксіз кодтарга болінеді. Блоктык кодтар – бул таралатын малімет блоктарга болініп жане арбір блокка озінін кодтык комбинациясы сайкес келетін кодтар. Кодтау жане декодтау операциялары арбір блокта жеке жү ргізіледі.Блоктык кодалардан ү зіліссіз кодалардын айырмашылыгы — ү зіліссіз кодалардагы кодалау жане кодадан шыгару ү зіліссіз берілетін символдар тізбегімен жү ргізіледі. Ү зіліссіз кодалардагы тексеруші символдар акпараттык символдарды тікелей байланысты тү рлендіру аркылы алынады.Кодтау жане декодтау элементтердін блоктарга болінбей, олардын бірізділігімен ү здіксіз жү реді. Блоктык кодтар болінетін жане болінбейтін кодтарга болінеді. Салыстырмалы тү рде барлык тү зетуші кодтар кобіне болінетін кодтарга жатады, себебі болінетін кодтарта кодтык комбинациялар екі болімнен турады: акпараттык жане тексеру. Олар ү немі белгіленген орындарда турады. Бул кодтарда алгашкы символдар акпараттык, одан кейінгілері тексеру символдары болады. Болінбейтін кодтарда акпараттык жане тексеру символдарына боліну болмайды. Мундай кодтарга туракты салмагы бар тепе-тен кодтар жатады. Болінетін кодтар жү йелік жане жү йелік емес болып екіге болінеді. Жү йелік кодтар – бул тексеру симаолдары акпараттык символдардын сызыктык комбинациясы ретінде аныкталатын кодтар. Мундай комбинацияларды алудын негізі сызыктык алгебранын математикалык аппараты болгандыктан, кодтар сызыктык деп, ал тексеру символдары белгілі жү йемен калыптасатындыктан блоктык болінетін сызыктык кодтар жү йелік деп аталады. Бул кодтар дискретті акпараттарды тарату жү йесінде колданылады. Жү йелік емес кодтарда жү йелік емес кодтардагы касиеттер колданылмайды. Мундай кодтарга болінбейтін тепе-тен кодтар жатады. Мундай кодтар кобіне симметриялык емес байланыс каналдарында пайдаланылады. Жү йелік кодтардын ішіндегі белгілі кодтардын бірі Хемминг коды. Хемминг байланыс каналдарындагы, сонымен катар компьютерлердегі акпараттарды беру магистральдарында, ен бастысы жад пен процессор арасындагы кателерді тү зете алатын кодты усынды. Хемминг коды Шеннон теоремасында корсетілген мү мкіндіктерді практикалык тү рде калай іске асыруга болатындыгын корсетеді. Хемминг кодымен кодтау алгоритмі: Хемминг кодынын курылуы бірлік символдар санынын жуптылыкка тексерілу принципін тексеруге негізделген. белгісі 2 модуль бойынша косуды білдіреді. S=0 кате жок, S=1 кате бар дегенді білдіреді. Мундай код (к+1, к) немесе (n, n-1)деп аталады. Бірінші сан – бірізділік элементінін саны, екіншісі – акпараттык символдар саны. Арбір тексеру символдарынын саны ү шін r=3, 4, 5... , ягни (7, 4), (15, 11), (31, 26) маркировкасы бар классикалык Хемминг коды бар. Мысал ү шін Хеммингтін классикалык кодын карастырайык: тексеру символдарын келесі тү рде топтастырайык: ; ; . 2 модуль бойынша косуды білдіреді. Кодтык созді алу келесі тү рде беріледі:

=

Декодердін кірісіне кодтык созі келеді, штрихпен берілген символдар – богеуіл асерінен жогалып кетуі мү мкін символдар. Декодерде кателерді тү зету болімінде синдромдар бірізділігі куралады:

; ; . - бірізділік синдромы деп аталады. Синдромды алу келесі тү рде корсетіледі:

=

Хемминг кодынын (7, 4) кодтык созі:

(0, 0, 0) синдромы бірізділікте кателік жок дегенді білдіреді. (7.4) коды ү шін кестеде нолдік емес синдромдар жане оларга сайкес келетін кателер конфигурациясы корсетілген.

Циклді кодалар. Кез келген екілік жү йедегі топталган кодаларды ар тү рлі m жолдан туратын n баганалы матрицамен жазуга болады. Немесе оган керісінше кез келген п орынды кодалык комбинациядан туратын m жолдын жиынтыгынан топталган кодаларды курушы матрица деп карауга болады.

Мундай матрицанын барлык жолдарынын ішінен косымша циклдік касиеті бар матрица куратын жолдарды боліп шыгаруга болады.

Мундай матрицанын барлык жолдарын осы коданын курушы деп аталатын бір комбинациясын циклдік ыгыстыру аркылы алуга болады. Осындай шартты канагаттандыратын кодаларды циклдік кодалар деп атайды.

Ыгыстыру, негізінен, оннан солга карай жү ргізіледі. Мысалы: 0100101, 1001010, 0010101, 0101010, 1010100, т.е.с. Топталган ар тү рлі кодалардын ішінде циклдіге жататындары коп болмайды. Сондыктан олармен берілетін маліметтер колемі жалпы топталган кодалармен берілетін маліметтер колемінен аз.

Циклді кодаларды жазганда, оларды n дарежесіндегі копмү ше тү рінде жазу ынгайлы.

Мысалы,

10101 -ді G(x) = 1 * х⁴ + 0 * х³ + 1 * х² + 0 * х¹ + 1 * х⁰ = х⁴ + х² + 1 деп жазуга болады.

Сойтіп кодалык комбинациямен жасалатын жумыс копмү шемен жасалатын жумыска акелінеді.

Кодалык комбинацияны куратын копмү шені бір орынга ыгыстырудын орнына оны х-ке кобейтеді.

Мысалы, 001101...0011010 орнына (х³ + х² + 1)х = х⁴ + х³ + х.

Осы екі комбинацияны " екілік модульмен" косканда алынатын комбинацияны х³ + х² + 1 копмү шеcін (х + 1)-ге кобейтіп алуга болады.

(х³ + х² + 1) • (х + 1) = х⁴ + х² + х + 1.

Сонымен, кода курушы копмү шені белгілеп алганнан кейін циклді коданын кез келген руксат етілген комбинациясын курушы копмү шені баска бір копмү шеге кобейту аркылы алуга болады.

Циклді коданын кез келген копмү шесі курушы копмү шеге калдыксыз болінуі керек. Циклді коданын осы касиеті катені табуга, ал егер калдыксыз болінбесе, сол калдыктын тү ріне карап, катенін орнын тауып тү зетуге болады.

Копмү шелерді кобейту мен болу кері байланысты ыгыстырушы тіркегіштерде онай орындалатын болгандыктан, циклді кодаларды колдану оте кен тараган. Циклді кода тугызушы немесе ондіруші деп аталатын мү шелерімен беріледі. Барлык маліметті таратуга арналган копмү шелер осы ондіруші немесе тугызушы копмү шеге калдыксыз болінуі керек.