Желі қателерді табу жане дұрыстау алгоритмдері

Курсовая работа, 24 Ноября 2013, автор: пользователь скрыл имя

Краткое описание


Өзектілігі:Циклдық артық код бойынша таралған қатерлердің келесідей категорияларын табуды оңайлатады. Біріншіден, аппаратураның ақаулығы кейде bit-тердің белгілі бір топтарын зақымдауды тудырады. Мысалы, ақауға ұшыраған символ бойынша кіріс-шығыс құрылғысы әр символдың екі бірінші мәні 0 мәніне теңестіріп тастауы мүмкін. Мұндай қатерлерді кейде тік деп атайды, өйткені олар тік бағанда жол түріндегі символ bit-терінің ауыстыруы кезіңде оңай байқалады. Циклдық артық кодтар тік қатерлерді бақылау сомасына қарағанда жақсы байқайды.

Прикрепленные файлы: 1 файл

Курстық жұмыс Бостанов Бекбосын Аж 442 (Восстановлен).doc

— 1.39 Мб (Скачать документ)

                        

Дәл осы жолмен бес  разрядты Рид-Соломон кодының алфавитін  құрамыз:

p(β)=0

β5+β2+1.

β5=-β2-1                                                      (4.9)

β5=β2+1

Көрініп тұрғандай, β5 барлық төменгі ретті β-мүшелерінің қосындысы ретінде келтірілген. Сондықтан β-ның барлық дәрежелерін көрсетуге болады:

β6=β5β=β3+β

β7=β6β=β4+β2

β8=β7β=β3+β2+1

β9=β8β=β(β3+β2+1)=β4+β3+β

β10=β9β=β(β4+β3+β)=β4+1

β11=β10β=β(β4+1)=β2+β+1

β12=β11β=β(β2+β+1)=β3+β2+β

β13=β12β=β(β3+β2+β)=β4+β3+β2

β14=β13β=β(β4+β3+β2)=β4+β3+β2+1

β15=β14β=β(β4+β3+β2+1)=β4+β3+β2+β+1

β16=β15β=β(β4+β3+β2+β+1)=β4+β3+β+1

β17=β16β=β(β4+β3+β+1)=β4+β+1

β18=β17β=β(β4+β+1)=β+1

β19=β18β=β(β+1)=β2+β

     β20=β19β=β(β2+β)=β3+β2                               (5)

β21=β20β=β(β3+β2)=β4+β3

β22=β21β=β(β4+β3)=β4+β2+1

β23=β22β=β(β4+β2+1)=β3+β2+β+1

β24=β23β=β(β3+β2+β+1)=β4+β3+β2+β

β25=β24β=β(β4+β3+β2+β)=β4+β3+1

β26=β25β=β(β4+β3+1)=β4+β2+β+1

β27=β26β=β(β4+β2+β+1)=β3+β+1

β28=β27β=β(β3+β+1)=β4+β2+β

β29=β28β=β(β4+β2+β)=β3+1

β30=β29β=β(β3+1)=β4+β

β31=β30β=β(β4+β)=β2+β2+1=1=β0

 

                        3-Кесте  Кодты алфавиттің символдары

 

Топ элементтері

Көпмүшелік түрінде

Вектор түрінде

0

-

00000

1

1

00001

Β

Х

00010

β2

Х2

00100

β3

Х3

01000

β4

Х4

10000

β5

Х2+1

00101

β6

Х3+Х

01010

β7

Х4+Х2

10100

β8

Х3+Х2+1

01101

β9

Х4+Х3+Х

11010

β10

Х4+1

10001

β11

Х2+Х+1

00111

β12

Х3+Х2+Х

01110

β13

Х4+Х3+Х2

11100

β14

Х4+Х3+Х2+1

11101

β15

Х4+Х3+Х2+Х+1

11111

β16

Х4+Х3+Х+1

11011

β17

Х4+Х+1

10011

β18

Х+1

00011

β19

Х2+Х

00110

β20

Х3+Х2

01100

β21

Х4+Х3

11000

β22

Х4+Х2+1

10101

β23

Х3+Х2+Х+1

01111

β24

Х4+Х3+Х2+Х

11110

β25

Х4+Х3+1

11001

β26

Х4+Х2+Х+1

10111

β27

Х3+Х+1

01011

β28

Х4+Х2+Х

10110

β29

Х3+1

01001

β30

Х4+Х

10010


                          

 

Енді жасаушы көпмүшелікті табайық. Бұл көпмүшелік Рид- Соломон кодын  туғызады:

g(x)=(x+β)(x+β2)(x+β3)(x+β4)(x+β5)(x+β6)=[x2+βx+β2x+β3]ּ[x2+β3x+β4x+β7][x2+β5x+β6x+β11]=x6+β10x5+β9x4+β24x3+β16x2+β24x+β21       (5.1)

 

Жасаушы көпмүшелік 2t=6 дәрежелі болғандықтан, бізде β-ның 2t тізбекті дәрежесі болуы керек. Олар көпмүшеліктің  түбірлері болып табылады.

 

           2.2 Кодтау

 

Рид- Соломон коды айналмалы болғандықтан, жүйелік түрдегі кодерлеу  екілік кодерлеу процедурасы сияқты.

Сонымен, хабар векторын полиноминалды  түрде келесідей жазуға болады:

J(x)=m0+m1x+m2x2+…+mk-1xk-1

Жүйелік түрде хабар символдары кодты сөздің бөлшегі ретінде  пайдаланылады. Біз хабар полиномын  кодты сөздің k шеткі оң разрядына  ығыстыра аламыз, содан кейін жұп биттерді n-k шеткі сол разрядтарына орналастырып қоса аламыз. Сондықтан біз J(x)-ны xn-k көбейткен кезде J(x)  оңға n-k позицияға ығысады. Ары қарай біз J(x)xn-k жасаушы көпмүшелікке g(x) бөлеміз:

                                                                                                        (5.2)

мұндағы q(x)- көпмүшелікті бөлудің  бүтін бөлігі,

      r(x)- көпмүшелікті  бөлудің қалдығы, қалдық жұп  болады.

r(x)- ті (2.3) теңдеудің екі жағына  да қосқан кезде және модуль  екі бойынша қосқанда:

U(x)=q(x)g(x)=r(x)+xk-1J(x)

Кодты сөздің нәтижелік полиномын  келесі түрде жазуға болады:

U(x)=r(x)+xn-kJ(x)

Осы айтылғандарды ескеріп, кез-келген хабар көпмүшелігін кодтайық.

Хабар келесі көпмүшелік түрінде берілсін

J(x)=β3х3 +β7х2+β20x+β17.

Оны х6- ке көбейту арқылы комбинациямызды n-k=6 оңға ығыстырамыз.

Х6J(x)=β3x9+β7x8+β20x7+β17x6.

Шыққан нәтижені g(x) модулі бойынша  бөлеміз. Қосу және көбейту амалдары 2.2- ші кесте мен 2.3- ші кесте көмегімен  орындалады.

 

b7х16+β3х15+β7х14+β8х13+β20х12+β11x11+β20x10+b8х9+b2х7+b30х6

b7х16+β17х15+β16х14+β10х13+β23х12+β0x11+β28x10

       β16х15+β23х14+β20х13+β18х12+β19x11+β9x10+b8х9+b2х7+b30х6                                           b16х15+β26х14+β25х13+β9х12+βх11+β9x10+β6x9

β21х14+β22х13+β25х12+β2x11+0+b11х9+b2х7+b30х6                                                                                                 β21х14+β0х13+β30х12+β14х11+β6x10+β14x9+β11x8

        β7х13+β27х12+β25x11+b6х10+b9х9+b11х8+b2х7+b30х6                                                  β7х13+β17х12+β16х11+β0х10+β23x9+β0x8+β28х7

                   β21х12+βx11+b27х10+b22х9+b19х8+b30х7+b30х6                                                            β21х12+β0х11+β30х10+β14x9+β6x8+β14х7+b11х6

β18 x11+b25х10+b3х9+b20х8+b23х7+b22х6                         β18х11+β28х10+β27x9+β11x8+β3х7+b11х6+b8х5

b23х10+b18х9+b27х8+b11х7+b30х6+b8х5              β23х10+β2х9+β1x8+β16x7+β8х6+b16х5+b15х4

                              b11х9+b29х8+b13х7+b15х6+b28х5+b15х4     

β11х9+β21х8+β20x7+β4x6+β27х5+b4х4+b1х3

b10х8+b4х7+b23х6+b14х5+b23х4+b1х3

 β10х8+β20х7+β19x6+β3x5+β26х4+b3х3+b0х2

           b13х7+b29х6+b22х5+b21х4+b6х3+b0х2                                                                   (5.3)

         β13х7+β23х6+β22x5+β6x4+β29х3+b6х2+b3х

              

Нәтижеде көпмүшелікті бөлу- келесідей  қалдық береді:

r(x)= β29х5+β2x4+β8x3+β16х2+b19х+b9

Осыдан код сөзінің  көпмүшелігін келесідей жазуға болады:

U(x)= b7х16+β3х15+β7х14+β8х13+β20х12+β11x11+β20x10+b8х9+b2х7+b30х6 +β29х5+β2x4                     +β8x3+β16х2 +b19х+b9

Жасаушы көпмүшелік g(x) түбірлері- g(x) өндіретін код сөзінің де түбірлері  болуы керек. Өйткені:

U(β)=J(x)g(x)

Осыдан, жасаушы көпмүшеліктің  түбірлері арқылы өрнектелетін код  сөзі нәтижеде нуль болуы тиіс. Яғни:

U(β)=U(β2)=U(β3)=U(β4)=0

Осыны есептеп көрсек:

U(β)= β7+β3+β7+β8+β20+β11+β20+β8+β2+ β30+β29+β2+β8+β16+β19+β9=0

U(β2)= β14+β6+β14+β16+β9+β22+β9+β16+β4+ β29+β29+β4+β16+β1+β7+β18=0  

U(β3)= β21+β9+β21+β24+β29+β2+β29+β24+β6+ β28+β27+β6+β24+β17+β26+β27=0

U(β4)= β28+β12+β28+β1+β18+β13+β18+β1+β8+ β27+β29+β8+β1+β2+β14+β5=0

                                                                                                                            (5.4)

 

Яғни жоғарыда айтылғандай жасаушы  көпмүшеліктің кез- келген түбірі арқылы өрнектелген код сөзі нуль болады.

 

2.3 Декодтау

 

Рид- Соломон кодын декодерлеу айналмалы  кодтарды декодерлеу сияқты жүргізіледі.

Жоғарыда біз хабарды жүйелік  түрде кодерлеп, нәтижесінде U(x) код  сөзі көпмүшелігін алғанбыз. Енді кодерлеу кезінде бұл хабар бұрмаланып, үш символ қате болып қабылданды делік. Қате комбинацияны келесі түрде жазуға болады:

                          (5.5)

 

Үш символды қате мына түрде берілсін:

 

e(x)=0+β7x+βx2+0x3+β11 x4+0x5+0x6+0x7+0x8+0x9+0х10+0х11+0х12

+0х13+0х14+0х15+0х16==(00000)+(10100)х+(00010)х2+(00000)х3+(00111)х4

+(00000)х5+(00000)х6+(00000)x7+ (00000)x8+(00000)x9

Бұл жағдайда бұрмаланған  код сөзінің қабылданған көпмүшелігі r(x)- жіберілген код сөзі көпмүшелігі U(x) және қате комбинация көпмүшелігінің  e(x) қосындысы түрінде беріледі:

                              r(x)=U(x)+e(x).

       яғни қабылданған комбинация келесідей болады:

r(x)= b7х16+β3х15+β7х14+β8х13+β20х12+β11x11+β20x10+b8х9+b2х7+b30х6 +β29х5+β18x4

                +β8x3+β25х2 +b30х+b9                                                      (5.6)

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

2.4 Программа интерфейсі

 

Delphi 7 ортасында құрылған  программанының жұмыс істеу принципі  келесідей. Программада көрсетілгендей  берілген бір мәтіннің бір блогының шифрлауын қарастырайық. Берілген блок 16 символдан тұрады. Олар төрт-төрттен әр сублокқа бөлінеді. Әр субблок бір сөзге w тең.

«Devide» батырмасын басып, алгоритмде қарастырылатын амалдардың барлығы дерлік екілік санау жүейсінде орындалатын болғандықтан, біз берілген блокты екілік санау жүйесіндегі субблоктарға бөлеміз.  Келесі әрекет «KEYS» батырмасымен жүзеге асады. Бұл батырма RC6 алгоритмінде қолданылатын барлық 43 ішкікілттердің мәнін есептеп шығарады. 3-суретте программаның интерфейсі көрсетілген.


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                   3-сурет Программаның интерфейсі

 

«Қадам 1» батырмасы  бастапқы субблоктардың мәнін кіріс  әрекеттерін орындап өзгертеді. Олар төмендегі тұрған жолдарға жазылады. Кіріс әрекеттеріне B = B + K0 mod 232, D = D + K1 mod 232 формулалары жатады.

Одан кейін, кіріс әрекеттері орындалып болғаннан кейін 1- раундта орындалатын амалдардың жүзеге асырылуы басталады. Бұны біз «Қадам 2» батырмасын басу арқылы орындаймыз. Бұл батырма бірден 20 раундтың әрекеттерін орындап, сублоктардың мәндерін есептейді де одан төмен тұрған жолдарға түсіреді. 

«Қадам 3» батырмасы 20 раундтың нәтижесінде шыққан субблокттардың мәндеріне шығыс әрекеттерін  орындайды. Шығыс әрекеттеріне A = A + K42 mod 232, C = C + K43 mod 232 формулалары жатады. 4-суретте программадағы субблоктардың ағымды мәндері көрсетілген.

 


 

 

 

 

 

 

4-сурет Программадағы субблоктардың ағымды мәндері

 

Программаның орындалуының соңғы қадамы «Нәтижесі» батырмасымен аяқталады. Шығыс әрекеттерімен  орындалған қадамның нәтижесінде шыққан 4 субблок соңғы нәтиже болып табылады. «Нәтижесі» батырмасын басу арқылы біз осы мәндердің екілік санау жүйесіндегі өлшемдерін ASCII кодасына ауыстыру арқылы шифрланған блоктың символдар тізбегін немесе сөздерін аламыз.

 

 

 

Информация о работе Желі қателерді табу жане дұрыстау алгоритмдері

Похожие темы