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

                        

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

p(β)=0

β⁵+β²+1.

β⁵=-β²-1                                                      (4.9)

β⁵=β²+1

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

β⁶=β⁵β=β³+β

β⁷=β⁶β=β⁴+β²

β⁸=β⁷β=β³+β²+1

β⁹=β⁸β=β(β³+β²+1)=β⁴+β³+β

β¹⁰=β⁹β=β(β⁴+β³+β)=β⁴+1

β¹¹=β¹⁰β=β(β⁴+1)=β²+β+1

β¹²=β¹¹β=β(β²+β+1)=β³+β²+β

β¹³=β¹²β=β(β³+β²+β)=β⁴+β³+β²

β¹⁴=β¹³β=β(β⁴+β³+β²)=β⁴+β³+β²+1

β¹⁵=β¹⁴β=β(β⁴+β³+β²+1)=β⁴+β³+β²+β+1

β¹⁶=β¹⁵β=β(β⁴+β³+β²+β+1)=β⁴+β³+β+1

β¹⁷=β¹⁶β=β(β⁴+β³+β+1)=β⁴+β+1

β¹⁸=β¹⁷β=β(β⁴+β+1)=β+1

β¹⁹=β¹⁸β=β(β+1)=β²+β

     β²⁰=β¹⁹β=β(β²+β)=β³+β²                               (5)

β²¹=β²⁰β=β(β³+β²)=β⁴+β³

β²²=β²¹β=β(β⁴+β³)=β⁴+β²+1

β²³=β²²β=β(β⁴+β²+1)=β³+β²+β+1

β²⁴=β²³β=β(β³+β²+β+1)=β⁴+β³+β²+β

β²⁵=β²⁴β=β(β⁴+β³+β²+β)=β⁴+β³+1

β²⁶=β²⁵β=β(β⁴+β³+1)=β⁴+β²+β+1

β²⁷=β²⁶β=β(β⁴+β²+β+1)=β³+β+1

β²⁸=β²⁷β=β(β³+β+1)=β⁴+β²+β

β²⁹=β²⁸β=β(β⁴+β²+β)=β³+1

β³⁰=β²⁹β=β(β³+1)=β⁴+β

β³¹=β³⁰β=β(β⁴+β)=β²+β²+1=1=β⁰

 

                        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+β²)(x+β³)(x+β⁴)(x+β⁵)(x+β⁶)=[x²+βx+β²x+β³]ּ[x²+β³x+β⁴x+β⁷][x²+β⁵x+β⁶x+β¹¹]=x⁶+β¹⁰x⁵+β⁹x⁴+β²⁴x³+β¹⁶x²+β²⁴x+β²¹       (5.1)

 

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

 

           2.2 Кодтау

 

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

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

J(x)=m₀+m₁x+m₂x²+…+m_k-1x^k-1

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

                                                                                                        (5.2)

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

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

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

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

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

U(x)=r(x)+x^n-kJ(x)

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

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

J(x)=β³х³ +β⁷х²+β²⁰x+β¹⁷.

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

Х⁶J(x)=β³x⁹+β⁷x⁸+β²⁰x⁷+β¹⁷x⁶.

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

 

b⁷х¹⁶+β³х¹⁵+β⁷х¹⁴+β⁸х¹³+β²⁰х¹²+β¹¹x¹¹+β²⁰x¹⁰+b⁸х⁹+b²х⁷+b³⁰х⁶

b⁷х¹⁶+β¹⁷х¹⁵+β¹⁶х¹⁴+β¹⁰х¹³+β²³х¹²+β⁰x¹¹+β²⁸x¹⁰

       β¹⁶х¹⁵+β²³х¹⁴+β²⁰х¹³+β¹⁸х¹²+β¹⁹x¹¹+β⁹x¹⁰+b⁸х⁹+b²х⁷+b³⁰х⁶                                           b¹⁶х¹⁵+β²⁶х¹⁴+β²⁵х¹³+β⁹х¹²+βх¹¹+β⁹x¹⁰+β⁶x⁹

β²¹х¹⁴+β²²х¹³+β²⁵х¹²+β²x¹¹+0+b¹¹х⁹+b²х⁷+b³⁰х⁶                                                                                                 β²¹х¹⁴+β⁰х¹³+β³⁰х¹²+β¹⁴х¹¹+β⁶x¹⁰+β¹⁴x⁹+β¹¹x⁸

        β⁷х¹³+β²⁷х¹²+β²⁵x¹¹+b⁶х¹⁰+b⁹х⁹+b¹¹х⁸+b²х⁷+b³⁰х⁶                                                  β⁷х¹³+β¹⁷х¹²+β¹⁶х¹¹+β⁰х¹⁰+β²³x⁹+β⁰x⁸+β²⁸х⁷

                   β²¹х¹²+βx¹¹+b²⁷х¹⁰+b²²х⁹+b¹⁹х⁸+b³⁰х⁷+b³⁰х⁶                                                            β²¹х¹²+β⁰х¹¹+β³⁰х¹⁰+β¹⁴x⁹+β⁶x⁸+β¹⁴х⁷+b¹¹х⁶

β¹⁸ x¹¹+b²⁵х¹⁰+b³х⁹+b²⁰х⁸+b²³х⁷+b²²х⁶                         β¹⁸х¹¹+β²⁸х¹⁰+β²⁷x⁹+β¹¹x⁸+β³х⁷+b¹¹х⁶+b⁸х⁵

b²³х¹⁰+b¹⁸х⁹+b²⁷х⁸+b¹¹х⁷+b³⁰х⁶+b⁸х⁵              β²³х¹⁰+β²х⁹+β¹x⁸+β¹⁶x⁷+β⁸х⁶+b¹⁶х⁵+b¹⁵х⁴

                              b¹¹х⁹+b²⁹х⁸+b¹³х⁷+b¹⁵х⁶+b²⁸х⁵+b¹⁵х⁴     

β¹¹х⁹+β²¹х⁸+β²⁰x⁷+β⁴x⁶+β²⁷х⁵+b⁴х⁴+b¹х³

b¹⁰х⁸+b⁴х⁷+b²³х⁶+b¹⁴х⁵+b²³х⁴+b¹х³

 β¹⁰х⁸+β²⁰х⁷+β¹⁹x⁶+β³x⁵+β²⁶х⁴+b³х³+b⁰х²

           b¹³х⁷+b²⁹х⁶+b²²х⁵+b²¹х⁴+b⁶х³+b⁰х²                                                                   (5.3)

         β¹³х⁷+β²³х⁶+β²²x⁵+β⁶x⁴+β²⁹х³+b⁶х²+b³х

              

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

r(x)= β²⁹х⁵+β²x⁴+β⁸x³+β¹⁶х²+b¹⁹х+b⁹

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

U(x)= b⁷х¹⁶+β³х¹⁵+β⁷х¹⁴+β⁸х¹³+β²⁰х¹²+β¹¹x¹¹+β²⁰x¹⁰+b⁸х⁹+b²х⁷+b³⁰х⁶ +β²⁹х⁵+β²x⁴                     +β⁸x³+β¹⁶х² +b¹⁹х+b⁹

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

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

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

U(β)=U(β²)=U(β³)=U(β⁴)=0

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

U(β)= β⁷+β³+β⁷+β⁸+β²⁰+β¹¹+β²⁰+β⁸+β²+ β³⁰+β²⁹+β²+β⁸+β¹⁶+β¹⁹+β⁹=0

U(β²)= β¹⁴+β⁶+β¹⁴+β¹⁶+β⁹+β²²+β⁹+β¹⁶+β⁴+ β²⁹+β²⁹+β⁴+β¹⁶+β¹+β⁷+β¹⁸=0  

U(β³)= β²¹+β⁹+β²¹+β²⁴+β²⁹+β²+β²⁹+β²⁴+β⁶+ β²⁸+β²⁷+β⁶+β²⁴+β¹⁷+β²⁶+β²⁷=0

U(β⁴)= β²⁸+β¹²+β²⁸+β¹+β¹⁸+β¹³+β¹⁸+β¹+β⁸+ β²⁷+β²⁹+β⁸+β¹+β²+β¹⁴+β⁵=0

                                                                                                                            (5.4)

 

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

 

2.3 Декодтау

 

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

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

                          (5.5)

 

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

 

e(x)=0+β⁷x+βx²+0x³+β¹¹ x⁴+0x⁵+0x⁶+0x⁷+0x⁸+0x⁹+0х¹⁰+0х¹¹+0х¹²

+0х¹³+0х¹⁴+0х¹⁵+0х¹⁶==(00000)+(10100)х+(00010)х²+(00000)х³+(00111)х⁴

+(00000)х⁵+(00000)х⁶+(00000)x⁷+ (00000)x⁸+(00000)x⁹

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

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

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

r(x)= b⁷х¹⁶+β³х¹⁵+β⁷х¹⁴+β⁸х¹³+β²⁰х¹²+β¹¹x¹¹+β²⁰x¹⁰+b⁸х⁹+b²х⁷+b³⁰х⁶ +β²⁹х⁵+β¹⁸x⁴

                +β⁸x³+β²⁵х² +b³⁰х+b⁹                                                      (5.6)

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

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

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

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

 

 

 

 

 

 

 

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

 

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