Сызықты кодтарға математикалық кіріспе

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

Кейбір алгебралық операциялары анықталған көбейткіштерді алгебралық жүйелер деп атайды. Алгебралық жүйе деп анықталған ережелермен екі элементті үшінші элементпен салыстыру. Әдетте негізгі операцияны қосу деп атайды (a+b=c көрсетіледі) немесе көбейту (a*b=c көрсетіледі), ал оған қарсы – алу немесе бөлу,тіпті, егер осы операциялар сандармен орындалмаса және сәйкес арифметикалық операцияларға ұқсамайтын болса да.

Түзейтін кодтар теориясында көп пайдаланылатын негізгі алгебралық жүйелер теориясын кысқаша қарастырамыз.

Элементтер жиынтық тобында Бір негізгі операция анықталған және келесі аксиомалар орындалады:

1. Операцияларды топтың кез-келген екі элементіне қолданса, онда сол топтың элементі пайда болады (тұйықтар талабы) .

2. a,b,c тобының кез-келген үш элементін мына теңдік қанағаттандырады (a+b)+c=a+(b+c), егер негізгі операция – қосу, және a(bc)=(ab)c теңдігі,егер негізге операция - көбейту.

3. Кез-келген G_n тобында G_n барлық а мәндерінде а+0=0+а шартын, егер негізгі операция – қосу, немесе а*1=1*а=а шартын, егер негізгі операция – көбейтуді қанағаттандыратын анықталған элемент болады. Бірінші жағдайда ол элементті нөл деп атайды және 0 символымен белгілейді, ал екінші жағдайда – бірлік және 1 символымен белгілейді.

4. а тобындағы кез-келген элемент а+(-а)=-а+а=0 теңдігімен анықталған, егер негізгі операция – қосу, егер негізгі операция – көбейту, онда а*а^-1= а^-1*а=1 теңдігімен анықталатын элементі болады.

Бірінші жағдайда ол элементті қарама-қарсы деп атайды және (-а) белгілейді, ал екінші жағдайда – кері және а^-1белгілейді.

Егер топта анықталған операция коммутативтік болса, онда a+b=b+a теңдігі дұрыс (қосу тобына) немесе a*b=b*a теңдігі (көбейту тобына), онда топты коммутативтік деп атаймыз.

Соңғы элементтер санынан тұратын топты топтың реті деп атайды.

Бізбен каралатын көп n-разрядты кодалық комбинациялар соңғы топ болуы үшін, негізгі операцияны орындау кезінде нәтижелік кодалық комбинациялардағы разрядтар саны артпауы қажет. Бұл шартты берілген модуль бойынша q (q – жәй сан) символдық разрядасты қосу операциясы қанағаттандырғандықтан, топ элементтерінің бірдей разрядты сандары жәй түрде қосылады, ал қосындының нәтижесі болып алынған санның q модуль бойынша бөлгендегі қалдық саналады.

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



Бізбен таңдалған операция коммутативті, сондықтан қаралатын топтар абелевті болады.

Нөлдерден тек тұратын комбинация нөлдік болады. 2 модуль бойынша қосынды кезінде берілген элемент өзі қарама-қарсы элемент болады. Демек, 2 модуль бойынша алу операциясы қосу операциясына парапар.

24 мысал. Келесі берілген кодалық комбинациялар топтар ма екендігін анықтау:

1. 0001, 0110, 0111, 0011;

2. 0000, 1101, 1110, 0111;

3. 000, 001, 010, 011, 100, 101, 110, 111.

Шешімі: Бірінші көпмүше топ емес, себебі нөлдік элементі жоқ.

Екінші көпмүше де топ емес, себебі тұйыталу шарты орындалмай тұр, мысалы, 2 модул бойынша 1101 мен 1110 комбинацияларының соммасы алғашқы көпмүшеге жатпайтын 0011 комбинациясын береді.

Үшінші көпмүше барлық шарттарды қанағаттандырады және топ болып табылады.

Көпмүшеасты топтар, операцияға қатысты өздері топ болып табылатын, топта анықталғандарды – тобастылар деп атайды. Мысалы, үшразрядты кодалық комбинациялар: 000, 001, 010, 011 көрсетілген үшразрядты кодалық комбинациялар тобы мысалында тобасты құрайды.

G_n тобында белгілі бір А тобы берілсін. Егер В- А элементіндегі G_n –ға жатпайтын, онда В элементінің суммасы G_n тобындағы А тобын құрсын.

Кез келген топ нолдік элементті құрайтындай, көршілес кластар В элемеентінен тұрады. Құрылған көршілес класқа кірмейтін дәйекті түрде В элементін алып, барлық топты А тобына ажыратуға болады.

B_j элементі деп топ бойынша көршілес класты құрайтын элементтерді атайды.

Топтық таблица деп аталатын ажырату таблицасында, құратын элементтер бағанның сол жағында орналасады, топтағы сол жақ элемент нолдік элемент болып табылады.

25 мысал: Үш разрядты екілік кодты комбинацияны, екі разрядты кодты комбинациялы топқа ажырату.

Шешімі: Ажырату таблицаға сай орындалады:

Таблица 4.4.

A1=0	A2	A3	A4
000	001	010	011
B1	A2B1	A3B1	A4B1
100	101	110	111

26 мысал:Төрт разрядты екілік кодты комбинацияны, екі разрядты кодты комбинациялы топқа ажырату.

Шешеімі: Көптеген ажырату нұсқалары , көршілес кластардан тұратын элементтерді құрайтынына тәуелді

Нұсқалардың бірі:

Таблица 4.5.

A1=0	A2	A3	A4
0000	0001	0110	0111
B1 0100	A2B1 0101	A3B1 0110	A4B1 0111
B2 1010	A2B2 1011	A3B2 1000	A4B2 1001
B3 1100	A2B3 1101	A3B3 1110	A4B3 1111

Сақина дегеніміз R-дің көп элементтері,онда екі операция анықталған (қосу және көбейту)олар:

1)қатынас бойынша R элементінің топтық коммутациясы;

2)элементтер туындысы аR және bR,сосын R элементі бар(қатынас және көбейту бойынша тұйықталуы);

3) R-ғы кез келген а,b,c үш элементі үшін мына теңдік дұрыс болады a(bc)=(ab)c (көбейту үшін ассоциациялық заң);

4) R-ғы кез келген а,b,c үш элементі үшін мына қатынас дұрыс боладыa(b+c)=ab+ac и (b+c)a=ba+ca (дистрибутивті заң);

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

Сақинада көбейту және кері элементтер үшін бірлік элемент болмау мүмкін.

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

F аймағы дегеніміз-көптеген,соның ішінде екі элемент арасында екі операция-қосу және көбейту, және келесі аксиомалар орындалады:

1)қосу бойынша көптеген элементтер коммутациялық топ құрады;

2)көбейту бойынша көптеген нөл емес элементтер коммутациялық топ құрады;

3)кез келген үш a,b,c элементі үшін келесі қатынас орындалады (b+c)=ab+ac (дистрибутивті заң).

1. F аймағы, сәйкесінше ,әрбір нольдік емес элементте кері элементі бар болып келетін, көбейту бойынша бірлік элементі бар коммутативті сақина болып табылады, Мысал аймағына көптеген оң сандарды жатқызумызға болады.

2. GF(P) аймағы P элементтерден тұратын соңғы сандарды соңғы аймақ немесе Галуа аймағы деп аталады. Р сандарының әрқайсысына жай сандардың деңгейі болып келетін q аймағы бар,ол р элементтерін санайды.

3. Аймақта екі элементтен кем емес болуы керек, ең болмағанда оның құрамында қосу операциясына(0) қатысты бірлік элемент және алу операциясына қатысты бірлік элемент болуы керек(1).. 0 және 1 қамтитын аймақты GF(2) деп белгілейміз. Екі элемент аймағында орындалатын қосу және алу ережелері мынадай:

4. +	0	1		×	0	1
   0	0	1		0	0	0
   1	1	0		1	0	1

5. 4.5 сурет Екі элемент аймағында орындалатын қосу және алу ережесі

6. Екілік кодтау комбинациясы GF(2), аймағындағы n элементтердің біркелкілік дәйектілігі болып табылады,олар жеке оқиғаға байланысты GF(P) аймағындаn элементтердің кодтай теориясында қарастыралыды.Жай сандарды бірдей деңгейде ұстап, Мұндай тәсіл кодтарды негізге ала отырып құруға және сараптауға болады.Жалпы жағдайда A_jжәне A_i кодтық комбинациясының қосындысын A_f = A_i + A_j деп атайды, A_k (k=1,2,…,n) символының қосындысы k-х символдар комбинацисын ұсынады.және де қосындыны іске асыру GF(P) аймағынын ережесімен орындалады.

7. Жеке жағдайда , код негізгісі q жай сан болып келсе, GF(q) аймағындағы қосу ережесі q модуліне сәйкес келетін қосу ережесімен тұспа-тұс келеді

Сызықтық векторлық кеңістіктегі сызықтық код

Көрсетілген алгебралық жүйелерге (топ, шар, өріс) операциялар математикалық объектілердің бір класына жатты. Мұндай операцияларды элементтер композициясының ішкі заңдары деп атайды.

Кодалау теориясында математикалық объектілердің (мысалы, L және ) екі класын біріктіретін модельдер кеңінен қолданылады. Композицияның ішкі заңдарында элементтер композициясының сыртқы заңдары еңгізіледі,  және аL бойынша сL болуы керек.

F элементі өрісіндегі сызықтық векторлық кеңістік деп (скалярлі) көптеген элементтерді айтады V (векторлар), егер келесі аксиомалар орындалса:

1. көптеген V бірігу операциялары жөніндегі коммутативті топ болып саналады;

2. кез-келген вектор үшін v -V-дан және кез-келген с -F-тан V –да тіркелген cv көбейтіндісі болып табылады;

3. егер u және v -V векторынан, ал с және d -F скалярынан, онда

с(с+v)=cu+cv; (c+d)v=cv+dv (дистрибутивті заңдар);

4. егер v-вектор, ал с және d-скалярлар, онда (cd)v=c(dv) және 1*v=v

(скалярлар үщін көбейтілген ассоциативті заң).

Жоғарыда көрсетілген кодалық комбинациялардың разрядты көбейту ережелері анықталған болатын. Енді n тізбегінен GF(P) өрісіндегі элементтің a_i GF(P) тұратын көбейтіндінің операциясын анықтаймыз, ол келесідей көбейтіледі: a_i(a₁, a₂, … , a_n)= (a_ia₁, a_ia₂, … , a_ia_n)

(элементтер көбейтіндісі GF(P) өрісінің ережелері бойынша анықталады).

Берілген операциялар бойынша дистрибутивті заңдар және ассоциативті заңдар (п.п.3.4) орындалады, n-разрядті кодалық комбинациялардағы барлық біріктірулерді GF(2)өрісіндегі векторлық сызықтық кеңістік деп қарастыруымызға болады (т.е. 0 и 1). Біріктірулер разряд бойынша 2 модуль арқылы өрнектеледі. Векторларды өрістегі (1) бір элементке көбейту барысында, ол өзгермейді, ал басқасына көбейту (0) 0=(0 0…0) символымен аталатын векторлық кеңістіктегі бірлік элементке айналдырылады.

Егер сызықты кеңістікте n элементтің қайталануынан GF(P) алаңы анықталған шартты қанағаттандыратын(қауымдастық,тұйықталған бейсызықтының скаляр кобейтіндіге қатынасы)векторлық көбейтіндінің қосыша операциясын береді, онда n-разрядты кодалық комбинацияның барлық қосындысы GF(P) коэффициентінің алаңындағы сызықты коммутативтік алгебраға айналады.

Векторлық кеңістіктегі аксиоманы қанағаттандыратын векторлық кеңістіктегі көптеген элементтер кеңістікішілік деп аталады.

GF(P) алаңындағы барлық n-разрядты кодалық комбинациялар векторлық кеңістіктегі кеңістікішілік тудырушы көптеген векторлар сызықтық кода деп аталады.

Екілік кодалық жағдайда мұндай кеңістікішілік комбинациялар GF(2) алаңында барлық n-разрядты екілік кодалық комбинациялар топтарының топішілігі болып табылатын екілік кодалық комбинацияның кез келген қосындысын тудырады.

Екілік топтық коданы құрастыру

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

Векторлық қателік деп разряд бірліктеріне ие болатын, қателікке әкелетін n-разрядты екілік қайталануды айтамыз. Кез келген қате кодалық комбинацияны енді қосынды( немесе айырма) деп қарастыруға болады.

2^к-1≥Q теңсіздігінен шыға отырып(0-дік комбинация байланыс арнасы күйін өзгертпейтіндіктен жиі қолданылмайды) қарапайым екілік кодалық команданың берілісіне қажетті берілген сан, яғни к ақпараттық разрядты санын анықтаймыз.

k –разрядты қалдықсыз кодтың әр 2^k - 1 нөлдік емес комбинациялары үшін сәйкес п символдар комбинациясын қою керек. Түртіндінің мағыналарының ара п - k мынадай әрекеттің тексерістің дәрежелерінің арада нәтижеде жинақта- ша 2 мағынаның модулю түртінді тағайынды ақпараттық дәрежелерде бекиді.

Ақпараттық түртіндінің(нөлдік емес қоса) 2k әрекетінің көпшілігін дәрежелі әрекеттің барлық n- тобының топшасын тәрбиелейді, сол және көрсетілген ережеге алған дәрежелі әрекеттің 2k n- көпшілігі де дәрежелі кодтық әрекеттің n- топ топша болып табылады. Рұқсат етідген кодтық әрекеттің сол көпшілігі топтық код болады.

Бізге тексерістің дәрежесінің және абатшылықтардан түртіндінің ұйғарымі үшін тексерістің дәрежелерінде бас-басыға деген кіріс ақпараттық дәреженің нөмірінің санын анықтау қажет.

2n топты дәрежелі әрекеттің барлық n- шектес сыныптарға 2k рұқсат етілген топшаға дәрежелі n- разрядты кодтық әрекеттің тексеріс дәрежелері мұнда тағы толтырылмаған. Басқа кода өзінің топшасының бөлінуінде 2n - k - 1 шектес сыныптар саналады. Бас-басы сыныптың элементтері өздігінен сомаларды кода және айтылмыш сыныптың тәрбиеле- элементінің 2 әрекетінің модулю ұсынады. Егер бас-басы сыныптың құрушы элементтерін қабылдау үшін тапсырынды арна үшін қатенің векторын, нешінші жөндеулі болуға керек ең ықтимал байланыстарын, сол ара бас-басы шектес сыныпта, арада нәтижеде әсердің тағайынды векторға барлық адал әрекеттеріне қате кодты әрекет топталады. Кодты әрекеттің көрінген байланысын түзетуі үшін арнаның шыға берісінде енді анықтау баршылық, қанаттастықтың қандай сыныбына ол қарайды. Оны кейін(модуль 2 б/а) осы шектес сыныптың құрушы элементімен қаттап сала, кода ақиқаттық әрекетін аламыз.

Ортақ саннан 2n - 1 ықтимал қателердің топты код небәрі 2n - k - 1 қатенің айырмашылығы б/а шектес сыныптың санына жөндеу білетіні анық.

Қандай шектес сыныпқа алынған әрекет қарайтынын туралы ақпаратты алу мүмкіндігі болу үшің әр шектес сыныпқа сәйкес бір символдар бақылау тізбегі опознаватель(синдром) деп аталатын қойылу керек.

Егер тек қана барлық бірлік қателіктер емес,сонымен қатар, екілік тәуелсіз қателіктерді өңдеу керек болса, онда теңсіздіктің түрі мынадай болады:

2^n-k-l+

Жалпы жағдайда барлық тәуелсіз қателіктерді s дәрежесіне дейін өңдеп қоысмша теңсіздік аламыз:

2^n-k-l++…+

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

Әрбір бастауыш қателікті өңдеудің анықтаушысын салыстыру процесін қарастырғанда бір себебі анықталады.

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

1. Желілік кодтар.

2. Желілік топтық кодтар қалай құрылады?

3. Екілік желілік кодтар дегеніміз не?

4. Оларды қалай құрады?

5. Жұптыққа тексеріс қалай жүргізіледі?

Тақырып 15. Жөндеуші топтық кодтар. Циклдық код.

Дәрістің мақсаты: Циклдық кодтардың құрылуы

Сұрақтар:

1. Циклдық кодтар қалай құрылады?

2. Циклдық кодтарға математикалықкіріспе.

3. Туындатушы көпмүшелікке қойылатын талап.

Циклдық кодтардың құрылуы

Жалпы түсініктер және анықтамасы

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

Бір комбинацияны циклдық қозғалу арқылы туындатушы матрицалардың барлық жолдарын алуға болады, бұл кодты туындатушы деп аталады. Бұл шартты қанағаттандыратын кодтар циклдық кодтар деген атқа ие болған.

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

Циклдық мүмкін (n,k)-кодтардың саны әртүрлі топтық (n,k)-кодтар санынан көп есе аз болады.

Циклдық кодтарды суреттегенде n-разрядты комбинациялық кодтар көпмүшелі фиктивті х-айнымалы түрінде көрсетіледі. у және х дәрежелері разрядтар нөмірлеріне сәйкес келеді (нөлден бастап),ал жалпы жағдайда коэффиценті х деп GF(q) өрісінің элементі болып табылады. х⁰ = 1 фиктивті айнымалысы ең төменгі санның разрядына сәйкес келеді. GF(q) өрісінің көпмүше коэффицентін GF(q) өрісінің үстіндегі көрмүшесі деп атайды. Екілік кодтарды қарастырмауымызға байланысты, х-тің коэффиценті тек 0 және 1 сандары болады. Басқаша айтқанда,GF(2) өріс үстінде көпмүшені оперировать етеміз. Жазып алайық, мысал, 01011 кодтық комбинацияны құраушы көпмүше түрінде:

G(x) = 0·x⁴ + 1·x³ + 0·x² + 1·x + 1

Нөлдік коэффицентті жазғанда көпмүшелік түседі, туындатушы көпмүшелік:

G(x) = x³ + x + 1

Нөлдік коэффицентпен қосылатын х-тің үлкен дәрежесін көпмүшеліктің дәрежесі деп атаймыз. Енді кодтық комбинацияларға жасалған әрекеттер көпмүшеліктерге әрекетке өтеді. Көпмүшеліктерді қосу коэффиценттерді екінші модуль арқылы жүзеге асырады.

Көрсетілген циклдық қозғалыс кейбір туындатушы көпмүшенің дәрежесін n – k деп бірлікті кодтық комбинацияның соңына ауыстырмай х-ке көбейту сияқты қарапайым орындайды. Көбейтеміз, мысал, матрицаның бірінші жолы (001011) , g₀(х) = x³ + x + 1 сәйкес көпмүшені, х-ке, матрицаның екінші жолын (010110) , сәйкесінше көпмүшені х • g₀(x) аламыз.

Мына екі комбинацияның қосындысы x³ + x + 1 және х+1арқылы табылған мәні кодтық комбинацияның шыққан мәніне тең екеніне көз жеткіземіз. Шынымен де,

Циклдық қозғалыс жолдар матрица бірлігімен үлкен (n-м) разрядында (солдан) тең болады көпмүшенің х жолына сәйкес болатын , біруақытты алыну көпмүшенің нәтижесіне теңхⁿ + 1= хⁿ– 1 модуль бойынша хⁿ + 1.

Бұл жерде циклдық кодтың кез келген рұқсат етілген комбинациясы модуль xⁿ + l бойынша құралатын көпмүшенің басқа бір көпмүшеге көбейтілуінің нәтижесінен алынады.Басқаша айтсақ,дәл келетін таңдауда құралатын көпмүше және циклдық кодтың кез келген көпмүшесі қалдықсыз бөлінетін болады.Рұқсат етілмеген кодтық комбинациясына сәйкес келетін,бірде бір көпмүше,құралатын көпмүше қалдықсыз бөлінбейді.Бұл қасиет қатені табуға мүмкіндік береді.Көпмүшенің көбеюі және бөлінуі кері байланыс бар жылжу регистрында оңай орындалады.