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

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

Кейбір алгебралық операциялары анықталған көбейткіштерді алгебралық жүйелер деп атайды. Алгебралық жүйе деп анықталған ережелермен екі элементті үшінші элементпен салыстыру. Әдетте негізгі операцияны қосу деп атайды (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
B1	A2ÅB1	A3ÅB1	A4ÅB1

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

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

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

Таблица 4.5.

A1=0	A2	A3	A4
B1	A2ÅB1	A3ÅB1	A4ÅB1
B2	A2ÅB2	A3ÅB2	A4ÅB2
B3	A2ÅB3	A3ÅB3	A4ÅB3

Сақина дегеніміз 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)

+				×

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 және W) екі класын біріктіретін модельдер кеңінен қолданылады. Композицияның ішкі заңдарында элементтер композициясының сыртқы заңдары еңгізіледі, wÎW және аÎ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. Жұптыққа тексеріс қалай жүргізіледі?

Дата добавления: 2015-10-23