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

σ(β)= β⁰+β²⁹+β¹³+β¹⁰ 0

 σ(β²)= β⁰+β³⁰+β¹⁵+β¹³ 0

σ(β³)= β⁰+β⁰+β¹⁷+β¹⁶ 0

σ(β⁴)= β⁰+β¹+β¹⁹+β¹⁹ 0                                  

σ(β⁵)= β⁰+β²+β²¹+β²² 0

σ(β⁶)= β⁰+β³+β²³+β²⁵ 0

σ(β⁷)= β⁰+β⁴+β²⁵+β²⁸ 0

σ(β⁸)= β⁰+β⁵+β²⁷+β⁰ 0

σ(β⁹)= β⁰+β6+β²⁹+β³ 0

σ(β¹⁰)= β⁰+β7+β⁰+β⁶ 0

σ(β¹¹)= β⁰+β⁸+β²+β⁹ 0

 σ(β¹²)= β⁰+β⁹+β⁴+β¹² 0

  σ(β¹³)= β⁰+β¹⁰+β⁶+β¹⁵ 0

  σ(β¹⁴)= β⁰+β¹¹+β⁸+β¹⁸ 0

  σ(β¹⁵)= β⁰+β¹²+β¹⁰+β²¹ 0

   σ(β¹⁶)= β⁰+β¹³+β¹²+β²⁴ 0

   σ(β¹⁷)= β⁰+β¹⁴+β¹⁴+β²⁷ 0

   σ(β¹⁸)= β⁰+β¹⁵+β¹⁶+β³⁰ 0

  σ(β¹⁹)= β⁰+β¹⁶+β¹⁸+β² 0

  σ(β²⁰)= β⁰+β¹⁷+β²⁰+β⁵ 0

  σ(β²¹)= β⁰+β¹⁸+β²²+β⁸ 0

  σ(β²²)= β⁰+β¹⁹+β²⁴+β¹¹ 0

   σ(β²³)= β⁰+β²⁰+β²⁶+β¹⁴ 0

  σ(β²⁴)= β⁰+β²¹+β²⁸+β¹⁷ 0                                                      (3.7)

    σ(β²⁵)= β⁰+β²²+β³⁰+β²⁰ 0

  σ(β²⁶)= β⁰+β²³+β¹+β²³ 0

       σ(β²⁷)= β⁰+β²⁴+β³+β²⁶®қате

  σ(β²⁸)= β⁰+β²⁵+β⁵+β²⁹ 0

                      σ(β²⁹)= β⁰+β²⁶+β⁷+β¹®қате

                      σ(β³⁰)= β⁰+β²⁷+β⁹+β⁴®қате                      

 

Қателердің орналасуы  көпмүшелік түбірлеріне кері шама болып  табылады. Сондықтан, σ(β²⁷)=0 бір түбірдің 1/α₁=β²⁷, бұдан α₁=1/β²⁶=β⁴. Осылай σ(β²⁹)=0 екінші түбірдің  1/α₁=β²⁹, бұдан α₁=1/β²⁹=β² . Үшінші түбірдің 1/α₁=β²⁹, бұдан α₁=1/β³⁰=β¹. Бізде қате үш символдық болғандықтан, қате көпмүшелігін былай жазады:

                   e(x)=e_j1x^j1+e_j2x^j2+e_i3xⁱ³

Бұл жерде β¹,β², β⁴ позицияларында үш қате табылады. Синдромды есептеу. R сигналының синдромы келесі түрде анықталады:

S=rH^T 

Синдром- берілген код  сөздерінің жиынына тиістілігін  анықтау үшін, сигналға жасалатын  жұптыққа тексерудің нәтижесі. Оң нәтиже берген кезде синдром нольге тең.S-тің  кез-келген нульдік емес мәні қатенің бар болуын білдіреді. Синдром S n-k символдардан тұрады. Біздің (30,5)-кодымыз үшін синдромның әрбір векторында бес символдан бар. Олардың мәндерін r(x) қабылданған көпмүшелігінен есептеп шығаруға болады. () өрнекпен анықталатын код құрылымының арқасында есептеулеріміз жеңілденеді:

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

Бұл құрылымнан код сөзінің U(x) әрбір  дұрыс көпмүшелігі жасаушы көпмүшелікке g(x) еселі екенін көруге болады. Яғни, g(x) түбірлері U(x)-тің де түбірлері  болуы тиіс. r(x)=U(x)+e(x) болғандықтан, онда g(x) әрбір түбірімен есептелетін r(x) дұрыс код сөзі болып табылған жағдайда ғана нуль беруі керек. Ақырында кез-келген қате нульдік емес нәтижеге әкеледі.

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

  i=1,…,n-k.

()-те көрсетіліп кеткендей r(x)-те екі символдық қате бар. Егер r(x) дұрыс код сөзі болып табылса, онда синдром символдары S_i нульге тең болып шығады. Берілген жағдайда синдромның алты символы келесі түрде болады:

 

S₁=r(β)= b⁷+β³+β⁷+β⁸+β²⁰+β¹¹+β²⁰+b⁸+b²+b³⁰ +β²⁹+β¹⁸+β⁸+β²⁵ +b³⁰+b⁹ =β⁹

 

S₂=r(β²)= b⁷+β³+β⁷+β⁸+β²⁰+β¹¹+β²⁰+b⁸+b²+b³⁰ +β²⁹+β¹⁸+β⁸+β²⁵ +b³⁰+b=β²⁵

 

S₃=r(β³)= b⁷+β³+β⁷+β⁸+β²⁰+β¹¹+β²⁰+b⁸+b²+b³⁰ +β²⁹+β¹⁸+β⁸+β²⁵ +b³⁰+b =β⁶

 

S₄=r(β⁴)= b⁷+β³+β⁷+β⁸+β²⁰+β¹¹+β²⁰+b⁸+b²+b³⁰ +β²⁹+β¹⁸+β⁸+β²⁵ +b³⁰+b=β²⁸

 

S₅=r(β⁵)= b⁷+β³+β⁷+β⁸+β²⁰+β¹¹+β²⁰+b⁸+b²+b³⁰ +β²⁹+β¹⁸+β⁸+β²⁵ +b³⁰+b=β³

 

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

 

 Нәтиже қабылданған  код сөзінде қатенің бар екендігін  көрсетіп тұр. (3.8)

 

 

3. Қате мәндерін анықтау

 

Біз қателерді е_jl деп белгіледік, мұндағы j-қатенің орналасу жерін, l-қатені білдіреді. Қатенің әрбір мәні нақты орнымен байланысты болғандықтан, белгілеу жүйесін, е_jl-ні е_l деп белгілеу арқылы, қарапайымдауға болады. β² пен β⁵ позицияларымен байланысты қателер мәнін е₁ жєне е₂ табу үшін, синдромды теңдеулердің кез-келгенін пайдалануға болады.

 

S₁=r(β)=e_j1α₁+e_j2α₂+e_j3α₃

S₂=r(β²)= e_j1α₁²+e_j2α₂²+e_j3α₃²  

S₃=r(β³)= e_j1α₁³+e_j2α₂³+e_j3α₃³                           (3.9)

 

 

Бұл теңдеулерді матрица  түрінде былай жазуға болады:

 

                                       (4)

 

е₁, е₂, e₃ қателерінің мәнін табу үшін, әдеттегідей кері матрицаны табуымыз керек. [ Жалпы қатерлер мәндерің қосымша А тарауында көруге болады]

 

 

2 РИД-СОЛОМОН КОДТАРЫ   КӨМЕГІМЕН АҚПАРАТТЫ ЖІБЕРУ ЖӘНЕ ЗЕРТТЕУ

 

2.1 Рид-Cоломон кодтары

 

Рид-Соломон коды деп- негізі екіге  тең емес, k санына тең айналмалы  кодты айтады:

K=2^m, (m=1, 2, 3, …, k) (4.1)

Рид-Соломон кодтары- бұл екілік емес айналмалы кодтар. Олардың символдары m биттік тізбектерді құрайды.Рид-Соломон кодтарының (n,k) көбі үшін

(n,k)=(2^m-1,2^m-1-2t) (4.2)

мұндағы t- символдағы код  түзете алатын қате биттердің саны,

n-k=2t=m – бақылау символдарының  саны,

n=2^m-1- Рид-Соломон кодының ұзындығы, ақпарат символдар саны k=n-m=2^a-d.

Рид-Соломон кодының минималды аралығы, кодердің кіріс және шығыс блоктарының бірдей ұзындығы бар сызықты код үшін мүмкін болатын, ең үлкен болып табылады. Екілік емес кодтар үшін, екі кодтық сөздің аралығы тізбектіліктердің бір-бірінен өзгешеленетін символдар саны ретінде анықталады. Рид-Соломон кодтары үшін минималды аралық келесі түрде анықталады:

d_min=n-k+1                              (4.3)

t немесе одан да  аз битте қатесі бар бұрмалданған  символдарды түзететін кодты  келесідей өрнектеуге болады: 

t=[(d_min-1)/2]=[(n-k)/2]                                (4.4)

(2.2)-теңдеуінен t символды  қатені түзететін Рид-Соломон  кодтары 2t бақылау символдарын  ғана керек етеді.Әрбір қате  үшін бір артықтылық (бақылау)  символы қатені табу үшін, бір  символ дұрыс мәнді анықтау  үшін пайдаланылады.

Рид-Соломон коды айналмалы  кодқа жатады. Бұдан – айналмалы  кодтың қасиеттері аталмыш кодқа  да ортақ екені түсінікті.

Айналмалы кодтаудың  негізіне келтірілмеген көпмүшелікті пайдалану жатады. Оны жасаушы  көпмүшелік деп айтады және оны мына формуламен есептеуге болады:

             (4.5)

мұндағы d- түзбе аралығы (тақ);

β- мультипликативті топтың примитивті элементі, ол барлық екілік емес алфавиттің k- символдарын біріктіреді.

Код алфавиті- 0 элементі, 1 элементі және β примитивті элементі, сондай-ақ β-ның екіден k-2 дейінгі барлық бүтін оң дәрежелері кіретін мультипликативті топ болып табылады.

 

Код алфавитін құрастыру  үшін төмендегі кестеде келтірілген  қарапайым көпмүшеліктерді пайдаланамыз.

1-Кесте – GF(2) өрісіне  қатысты қарапайым көпмүшеліктер

 

m, бақылау символы	Примитивті көпмүшелік
2	x2+ x+1
3	x3+ x+1
4	x4+ x+1
5	x5+x2+1
6	x6+ x+1
7	x7+ x3+1
8	x8+ x4+x3+ x2+1
9	x9+ x4+1
10	x10+ x3+1
11	x11+ x2+1
12	x12+ x6+x4+ x+1

 

 

GF(q) өрісінің p(x) примитивті  көпмүшелігі деп- p(x) модулі бойынша құрылған өріс кеңейтуінде көпмүшелікке сәйкес келетін x өріс элементі примитивті болып табылатын көпмүшелікті айтамыз.

GF(q) өрісінің нульден  басқа элементтерінің барлығы  х элементінің дәрежесі түрінде  берілсе, онда х примитивті элемент болып табылады.

Рид-Соломон кодтары  сияқты екілік емес кодтардың кодтау мен декодтау принциптерін түсіну үшін, Галуа өрісі (Galois fields - GF) ретінде  танымал шекті өріс түсінігіне жүгініп  көрейік. Кез-келген р саны үшін, шекті  өріс бар, ол GF(q) болып белгіленеді және р элементтен тұрады. GF(q) түсінігін p^m элементтен тұратын GF(q) өрісінің кеңейуі деп аталады және GF(q^m) деп белгіленеді. GF(q^m)-ның әрбір нольдік емес элементін β-ның дәрежесі түрінде келтіруге болады. F элементтерінің шексіз жиыны {0,1,β} бастапқы жиыннан құралады және соңғы жазбаны α-ға тізбектей көбейту арқылы қосымша элементтермен толықтырылады.

F-тан GF(q^m) элементтерінің шекті жиынын есептеу үшін, F-қа шарттар қою керек: ол тек қана 2^m элементтен тұруы мүмкін және көбейту операциясына қатысты тұйықталған болуы керек. Көбейту операциясына қатысты өріс элементтері жиынының тұйықталу шарты келтірілмеген полиномның түріне ие. β^(2-m)+1=0 немесе β^(2-m)=1=β⁰ .

Осы полиноминалдық шектеу көмегімен дәрежесі (2-m)-ге тең немесе одан үлкен элементті дәрежесі  (2-m)-нен кем элементке дейін төмендетуге болады.

Бастапқы берілген мәліметтерге сүйеніп (m=5) Рид-Соломон кодын құрамыз.

Ең алдымен шекті  өрісті (код алфавитін) құрып алуымыз керек. Ол үшін теңдеуге сәйкес алфавитіміз қанша элементтен тұратынын анықтаймыз:

K=2^m=2⁵=32                                            (4.6)

 

Шекті өрісті примитивті полиномның түбірлерін табу арқылы құрамыз. Яғни, кеңейту өрісінің элементін  β р(х) полиномының түбірі деп  аламыз.

Мысалға, төрт разрядты Рид-Соломон кодының алфавитін құрайық:

р(β)=0

β⁴+β+1=0                                     (4.7)

         β⁴=-β-1

Екілік өріске жасалған амалдар кезінде +1=-1 болғандықтан, β⁴ мына түрде келтіруге болады:

β⁴=β+1

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

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

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

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

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

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

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

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

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

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

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

 

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

 

Топ элементтері	Көпмүшелік түрінде	Вектор түрінде
0	-	0000
1	1	0001
Β	Х	0010
β2	Х2	0100
β3	Х3	1000
β4	Х+1	0011
β5	Х2+Х	0110
β6	Х3+Х2	1100
β7	Х3+Х+1	1011
β8	Х2+1	0101
β9	Х3+Х	1010
β10	Х2+Х+1	0111
β11	Х3+Х2+Х	1110
β12	Х3+Х2+Х+1	1111
β13	Х3+Х2+1	1101