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

Түзетуші кодтар деп акпараттарды тарату жане сактау кезінде богеуілдердін асерінен пайда болатын кателіктерді табуга немесе түзеуге арналган кодтарды айтады. Түзетуші кодтар блоктык жане үздіксіз кодтарга болінеді. Блоктык кодтар – бул таралатын малімет блоктарга болініп жане арбір блокка озінін кодтык комбинациясы сайкес келетін кодтар. Кодтау жане декодтау операциялары арбір блокта жеке жүргізіледі.Блоктык кодалардан үзіліссіз кодалардын айырмашылыгы — үзіліссіз кодалардагы кодалау жане кодадан шыгару үзіліссіз берілетін символдар тізбегімен жүргізіледі. Үзіліссіз кодалардагы тексеруші символдар акпараттык символдарды тікелей байланысты түрлендіру аркылы алынады.Кодтау жане декодтау элементтердін блоктарга болінбей, олардын бірізділігімен үздіксіз жүреді. Блоктык кодтар болінетін жане болінбейтін кодтарга болінеді. Салыстырмалы түрде барлык түзетуші кодтар кобіне болінетін кодтарга жатады, себебі болінетін кодтарта кодтык комбинациялар екі болімнен турады: акпараттык жане тексеру. Олар үнемі белгіленген орындарда турады. Бул кодтарда алгашкы символдар акпараттык, одан кейінгілері тексеру символдары болады. Болінбейтін кодтарда акпараттык жане тексеру символдарына боліну болмайды. Мундай кодтарга туракты салмагы бар тепе-тен кодтар жатады. Болінетін кодтар жүйелік жане жүйелік емес болып екіге болінеді. Жүйелік кодтар – бул тексеру симаолдары акпараттык символдардын сызыктык комбинациясы ретінде аныкталатын кодтар. Мундай комбинацияларды алудын негізі сызыктык алгебранын математикалык аппараты болгандыктан, кодтар сызыктык деп, ал тексеру символдары белгілі жүйемен калыптасатындыктан блоктык болінетін сызыктык кодтар жүйелік деп аталады. Бул кодтар дискретті акпараттарды тарату жүйесінде колданылады. Жүйелік емес кодтарда жүйелік емес кодтардагы касиеттер колданылмайды. Мундай кодтарга болінбейтін тепе-тен кодтар жатады. Мундай кодтар кобіне симметриялык емес байланыс каналдарында пайдаланылады. Жүйелік кодтардын ішіндегі белгілі кодтардын бірі Хемминг коды. Хемминг байланыс каналдарындагы, сонымен катар компьютерлердегі акпараттарды беру магистральдарында, ен бастысы жад пен процессор арасындагы кателерді түзете алатын кодты усынды. Хемминг коды Шеннон теоремасында корсетілген мүмкіндіктерді практикалык түрде калай іске асыруга болатындыгын корсетеді. Хемминг кодымен кодтау алгоритмі: Хемминг кодынын курылуы бірлік символдар санынын жуптылыкка тексерілу принципін тексеруге негізделген. белгісі 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 * х4 + 0 * х3 + 1 * х2 + 0 * х1 + 1 * х0 = х4 + х2 + 1 деп жазуга болады.



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

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

Мысалы, 001101...0011010 орнына (х3 + х2 + 1)х = х4 + х3 + х.

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

(х3 + х2 + 1) • (х + 1) = х4 + х2 + х + 1.

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

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

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


6096771555136792.html
6096807291963663.html
    PR.RU™