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

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

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


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

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

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

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

σ(β)= β0+β29+β13+β10 0

 σ(β2)= β0+β30+β15+β13 0

σ(β3)= β0+β0+β17+β16 0

σ(β4)= β0+β1+β19+β19 0                                  

σ(β5)= β0+β2+β21+β22 0

σ(β6)= β0+β3+β23+β25 0

σ(β7)= β0+β4+β25+β28 0

σ(β8)= β0+β5+β27+β0 0

σ(β9)= β0+β6+β29+β3 0

σ(β10)= β0+β7+β0+β6 0

σ(β11)= β0+β8+β2+β9 0

 σ(β12)= β0+β9+β4+β12 0

  σ(β13)= β0+β10+β6+β15 0

  σ(β14)= β0+β11+β8+β18 0

  σ(β15)= β0+β12+β10+β21 0

   σ(β16)= β0+β13+β12+β24 0

   σ(β17)= β0+β14+β14+β27 0

   σ(β18)= β0+β15+β16+β30 0

  σ(β19)= β0+β16+β18+β2 0

  σ(β20)= β0+β17+β20+β5 0

  σ(β21)= β0+β18+β22+β8 0

  σ(β22)= β0+β19+β24+β11 0

   σ(β23)= β0+β20+β26+β14 0

  σ(β24)= β0+β21+β28+β17 0                                                      (3.7)

    σ(β25)= β0+β22+β30+β20 0

  σ(β26)= β0+β23+β1+β23 0

       σ(β27)= β0+β24+β3+β26®қате

  σ(β28)= β0+β25+β5+β29 0

                      σ(β29)= β0+β26+β7+β1®қате

                      σ(β30)= β0+β27+β9+β4®қате                      

 

Қателердің орналасуы  көпмүшелік түбірлеріне кері шама болып  табылады. Сондықтан, σ(β27)=0 бір түбірдің 1/α1=β27, бұдан α1=1/β26=β4. Осылай σ(β29)=0 екінші түбірдің  1/α1=β29, бұдан α1=1/β29=β2 . Үшінші түбірдің 1/α1=β29, бұдан α1=1/β30=β1. Бізде қате үш символдық болғандықтан, қате көпмүшелігін былай жазады:

                   e(x)=ej1xj1+ej2xj2+ei3xi3

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

S=rHT 

Синдром- берілген код  сөздерінің жиынына тиістілігін  анықтау үшін, сигналға жасалатын  жұптыққа тексерудің нәтижесі. Оң нәтиже берген кезде синдром нольге тең.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) дұрыс код сөзі болып табылса, онда синдром символдары Si нульге тең болып шығады. Берілген жағдайда синдромның алты символы келесі түрде болады:

 

S1=r(β)= b7+β3+β7+β8+β20+β11+β20+b8+b2+b30 +β29+β18+β8+β25 +b30+b9 =β9

 

S2=r(β2)= b7+β3+β7+β8+β20+β11+β20+b8+b2+b30 +β29+β18+β8+β25 +b30+b=β25

 

S3=r(β3)= b7+β3+β7+β8+β20+β11+β20+b8+b2+b30 +β29+β18+β8+β25 +b30+b =β6

 

S4=r(β4)= b7+β3+β7+β8+β20+β11+β20+b8+b2+b30 +β29+β18+β8+β25 +b30+b=β28

 

S5=r(β5)= b7+β3+β7+β8+β20+β11+β20+b8+b2+b30 +β29+β18+β8+β25 +b30+b=β3

 

S6=r(β6)= b7+β3+β7+β8+β20+β11+β20+b8+b2+b30 +β29+β18+β8+β25 +b30+b=β4

 

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

 

 

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

 

Біз қателерді еjl деп белгіледік, мұндағы j-қатенің орналасу жерін, l-қатені білдіреді. Қатенің әрбір мәні нақты орнымен байланысты болғандықтан, белгілеу жүйесін, еjl-ні еl деп белгілеу арқылы, қарапайымдауға болады. β2 пен β5 позицияларымен байланысты қателер мәнін е1 жєне е2 табу үшін, синдромды теңдеулердің кез-келгенін пайдалануға болады.

 

S1=r(β)=ej1α1+ej2α2+ej3α3

S2=r(β2)= ej1α12+ej2α22+ej3α32  

S3=r(β3)= ej1α13+ej2α23+ej3α33                           (3.9)

 

 

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

 

                                       (4)

 

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

 

 

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

 

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

 

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

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

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

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

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

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

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

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

dmin=n-k+1                              (4.3)

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

t=[(dmin-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) түсінігін pm элементтен тұратын GF(q) өрісінің кеңейуі деп аталады және GF(qm) деп белгіленеді. GF(qm)-ның әрбір нольдік емес элементін β-ның дәрежесі түрінде келтіруге болады. F элементтерінің шексіз жиыны {0,1,β} бастапқы жиыннан құралады және соңғы жазбаны α-ға тізбектей көбейту арқылы қосымша элементтермен толықтырылады.

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

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

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

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

K=2m=25=32                                            (4.6)

 

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

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

р(β)=0

β4+β+1=0                                     (4.7)

         β4=-β-1

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

β4=β+1

β5=ββ4=β(1+β)=β+β2

β6=ββ5=β(β+β2)=β2+β3

β7=ββ6=β(β2+β3)=β3+β+1

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

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

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

β11=ββ10=β(β2+β+1)=β3+β2+β                               (4.8)

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

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

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

β15=ββ14=β(β3+1)=1=β0

 

                         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

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