Рид-Соломон кодын

КІРІСПЕ

 

Дипломдық жұмыс тақырыбының өзектілігі.

Қазіргі ақпараттық ғасырда деректерді жіберу, сақтау және іздеу үшін тек  қана оның жылдамдығы маңызды емес, сонымен қатар оның қатесіздігі  маңызды. Ақпаратты өңдеу және сақтау, жіберу құрал-жабдықтарының қазіргі даму сатысында  барлық үлкен өзектілік жоғарғы қорғаушылықты қамтамасыз ету  мәселесінде жатыр, оның бәрi өсетiн сапаға қойылатын талаптарымен және нақты жүйелердiң сенiмдiлiгiне шартталған.

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

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

Дипломдық жұмыстың мақсаты. Телекоммуникация желілерінде Рид-Соломон кодын қолдану және зерттеу болып табылады. Жобаның басты мақсаты қазіргі телекоммуникация жүйелерінде мәліметтердің берілуі үшін Рид-Соломон кодын қолдану арқылы бағдарлама жобасын құру. Рид-Соломон кодтары деректерді сақтау және жіберу құрылғыларында қателерді табу және түзету үшін кеңінен қолданылады. Осылайша, Рид-Соломон кодының ақпаратты жеткізу кезінде қолданылуын зерттеп, бағдарлама жасау арқылы құрылымын түсіндіру. Яғни теориялық білімді тәжірибе жүзінде бекіту.

Қойылған зерттеу мақсатқа жету үшін келесі міндеттер орындалуы тиіс:

• Рид-Соломон кодының ерекшеліктерін қарастыру;
• Рид-Соломон кодының телекоммуникацияның қандай жүйелерінде

қолданылатынын анықтау;

• «С #»   бағдарламалау ортасының   түсініктері мен   принциптерін

түсіну;

• Бағдарламаны құрудың қадамдарын жасау.

Бұл жұмысты жазу үшін «С #» ортасы қолдандылды. С # бұл бағдарламашы  жұмысының жоғарғы нәтижелігін қамтамасыз ететін күрделі механизм. Бағдарламалау тілдерін құру облысында өте белгілі жаңа өнім болып келеді. Бұл тіл визуалды бағдарламалау ортасы, бағдарламалауға тиімді және қолайлы. Оның көмегімен әртүрлі клиенттік орындарға арналған тиімді (өнімділігі жоғарғы және салыстырмалы көп емес сиымдылығы) бағдарламалық өнімдер құруға болады.

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

Кіріспеде дипломдық жобаның өзектілігі, мақсаттары, міндеттері мен жұмыс структурасы талқыланып ашылынды.

Дипломдық жұмыстың бірінші  тарауында Рид-Соломон кодының алгоритмі, қателердің пайда болу ықтималдылығы, импулсьті кедергілер кезінде тиімділігі мен Рид-Соломоннның кодталуы, декодталуы талқыланған.

Екінші бөлімінде Рид-Соломон кодының телекоммуникация желілерінің қандай түрлерінде қолданылатыны қарастырылған. Код қолданылатын телекоммуникация жүйелері: сымсыз (мобильді) байланыс, WiMAX технологясы, микротолқынды байланыс, радиорелейлік байланыс, жерсерiктiк байланыс, ADSL технологиясы туралы мәдіметтер анықталған.

Үшінші бөлімінде С # программалау ортасымен таныстыру есебі толығымен жүзеге асырылған. Бұл бөлімде С # – тың барлық нұсқалары қарастырылып, олардың арасындағы айырмашылықтары талдаудан өткізілген.

Төртінші бөлімінде Рид-Соломон кодын талдау бағдарламасын С # ортасында жобалау үрдісі сипатталған. Жобаны құрастыру барысында аспаптық бағдарламаның қоданылған компоненттері, бағдарламаны құру сатылары қарастырылған.

Дипломдық жобадағы зерттеу  мәні қорытындыда талқыланған.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Рид-Соломон кодтарына жалпы шолу

1.1 Рид-Соломон кодтарының ерекшеліктері

 

 

Рид-Соломон кодтары  (Reed-Solomon code, R-S code) - бұл екілік емес циклдық кодтар, оның символдары т – биттік тізбекті құрайды, мұндағы т – 2 санынан үлкен  оң бүтін сан. (n, K) коды барлық п және k да т – биттік символдарда анықталған

 

                                                                                         (1.1.1)

 

мұндағы  k – кодталуға жататын ақпараттық биттер саны,  ал n – кодталатын блоктағы кодтық символдар саны. Рид - Соломонның өте нақты көптеген кодтары үшін (n,k) 

                                                                          (1.1.2)

 

мұндағы t – кодты түзей алатын символдағы қателік  биттерінің саны, ал  және – бақылау символдарының саны. Рид-Соломонның кеңейтілген кодын немесе арқылы алуға болады, бірақ одан артық емес.

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

 

                                                                                          (1.1.3)

 

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

 

                                                                              (1.1.4)

 

Бұл теңдіктен t  символдық қателіктерді түзейтін Рид-Соломон кодтары 2t –дан көп болмайтын бақылау символдарын талап ететіні көрініп тұр.  (1.1.4) тедігінен декодерде п-k  "пайдаланылған" артылған символдары бар екенін көруге болады, олардың саны қателерді түзейтін символдардың санынан екі есеге артық болады. Әрбір қате үшін бір артылған символ қатені анықтау үшін қолданылады және біреуі ақиқат мәнін анықтау үшін қолданылады [1]. Өшіруді түзету үшін кодтың мүмкіндігі келесідей үлгіде көрсетіледі.

 

                                                                                       (1.1.5)

 

Бір уақытта қателерді түзету және өшіру мүмкіндігін қойылатын  талап ретінде көрсетуге болады.

 

                                                                                 (1.1.6)

 

мұндағы - түзетуге мүмкін болатын қателік символдық комбинцияның саны, ал - смиволдық өшіру комбинациясының саны, олар түзетілуі мүмкін. Рид-Соломон кодтары сияқты екілік емес кодтардың артықшылығын келесі салыстырулардан көруге болады. (п, k) = (7, 3) екілік кодын қарастырайық. Толықтай n-кортеждер кеңістігі n-кортеждер құрайды, ондағы (немесе барлық n-кортеждердің 1/16 бөлігі) кодтық сөздер болып табылады. Одан кейін (n, k)=(7, 3) екілік емес кодты қарастырайық, мұнда әрбір символ т = 3 биттен тұрады. n-кортеждер кеңістігі 2 097 152 n-кортежді құрайды, оның ішінде (немесе  барлық n-кортеждердің 1/4096 бөлігі) кодтық сөздер болып табылады. Егер операциялар әрбірі т биттен құралған екілік емес символдарға жүргіліп жатса, онда тек маңызды емес мүмкін болатын n-кортеждер бөлігі ( яғни  үлкен санының )  кодтық сөздер болып табылады. Бұл бөлік т өскен сайын кішірейеді. Мұнда маңызды болып табылатыны сол, егер  кодтық сөз ретінде n-кортеждер кеңістігінің маңызды емес бөлігі қолданылса, онда үлкен алу мүмкін болады [1].

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

Рид-Соломон кодтары  үшін қателердің пайда болу ықтималдылығы.

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

 

                                                       (1.1.7)

 

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

Кейбір модуляция типтері  үшін биттік қателік ықтималдығын жоғарыдан  символдық қателік ықтималдығымен шектеуге болады. М= мен MFSK ( манипуляцияның бiрнеше жиiлiктерi ) модуляциясы үшін Р_В (биттік қателік ықтималдығы) және Р_Е арасындағы қатынас келесі формуламен өрнектеледі.

 

                                                                                                 (1.1.8)

 

-ның p каналдық символда қателіктің пайда болу ықтималдығынан тәуелділігі көрсетілген (сурет 1). Символдағы t  қателік биттерін түзету мүмкіндігі және n = 31 (кодтық блоктағы отыз бір 5-биттік символ) бар әр түрлі ортогональді 32- лік Рид-Соломон кодтары үшін (1.1.7) және (1.1.8) теңдіктерінен алынған. Сурет 2.-де MFSK ( манипуляцияның бiрнеше жиiлiктерi ) модуляциясын және AWGN ( аддитивтiк ақ гаустық шумен) каналында когерентті емес демодуляциясын қолданатын кодтау жүйесі үшін  - ның /N₀-дан тәуелділігі көрсетілген.

 

 

Сурет 1. Символда t битті түзету мүмкіндігі бар және п = 31 әртүрлі ортогональді 32- лік Рид-Соломон кодтары үшін

- ның p-дан тәуелділігі.

 

Рид-Соломон кодтары  үшін қателердің пайда болу ықтималдығы n блоктың ұзындығының өшіруші дәрежелік функциясы болып табылады, ал декодтау күрделілігі блок ұзындығының үлкен емес дәрежесіне пропорционал. Кейде Рид-Соломон кодтары каскадтық жүйелерде қолданылады. Мұндай жүйелерде ішкі өте нақты декодер алдымен демодулятор шығысындағы шешімнің жұмсақ схемасынан туындайтын қателерден кейбір қорғанысты жүзеге асырады; одан кейін  өте нақты декодер  қатал схема бойынша жасалған деректерді сыртқы Рид-Соломон декодеріне жібереді, ол қателердің пайда болу ықтималдығын азайтады [2].

 

 

Сурет 2. Символда t бит түзету мүмкіндігі бар және AWGN каналында 32-лік MFSK модуляциясында п = 31 болатын әр түрлі ортогональді Рид-Соломон кодтары үшін рв – ның  Et/N_Q - дан тәуелділігі.

 

 

1.2 Рид-Соломон кодтарының импулсьті  кедергілер кезінде тиімділігі

 

 

Әрбір символы т = 8 биттен тұратын ( мұндай символдарды байт деп аталуға қабылданған ) (n, k) = (255, 247) кодты қарастырайық. п-k=8 болғандықтан, (1.1.4) теңдігінен көруге болады: бұл код 255 ұзындықтағы блоктағы кез – келген 4-символдық қателерді түзей алады. 25 бит ұзындықтағы блок жіберілу жүрісі кезінде кедергілерге тап болсын делік.

3 суретте 25 тізбектелген битке түсетін шу дестелері тура 4 символды бұрмалайды. (255, 247) коды үшін декодер кез – келген 4-символдық қателерді символдың бұзылу сипаттарына қарамай  түзей алады. Басқаша айтсақ, егер декодер байтты түзейтін (бұрысын дұрысымен алмастырады) болса, онда қате бір биттің немесе барлық сегіз биттердің бұрмаланғанымен шақырылған болады. Сол себепті егер символ дұрыс емес болса, ол барлық екілік позицияда бұрмалануы мүмкін. Бұл екілік кодтармен салыстырғанда импульстік кедергілер кезінде Рид-Соломон кодына үлкен артықшылық береді ( тіпті екілік кодта алмасуларды қолданғанның өзінде). Бұл мысалда егер 25 биттік кездейсоқ кедергі қаралатын болса, 4  символдан да артық бұрмалануы мүмкіндігі анық көрінеді (25 символға дейін бұрмалануы мүмкін). Әрине мұндай қателер санын түзеу (255, 247) кодынан тыс болады [2].

 

Сурет 3. 25 бит ұзындықтағы блок.

 

Рид-Соломон кодының  функция өлшемі, артықшылығы мен кодтаудың дәрежелері сияқты негізгі сипаттамалары. 

Код шу эффекттерiне ойдағыдай  қарсы тұру үшін кедергілердің ұзындығы кодтық сөздердің санының санына қатысты үлкен емес пайыздық мөлшерін құрауы тиіс. Осылайша ұзақ мерзімде болатынына сенімді болу үшін, қабылданған шуды ұзақ мерзім аралығында ортақ шамаға  келтіру керек, осылайша нашар қабылданудағы кенеттен немесе ерекше жолақтардың эффектілерін азайтады. Сондықтан қателерді түзейтін код жіберілуші блоктың өлшемін арттыру кезінде ( берілудегі сенімділік көтеріледі) әлдеқайда тиімді болады, бұл Рид-Соломон кодын тиімдірек көрсетеді, егер блоктың ұзындығы үлкенірек болса. Мұны көрсетілген қисықтар жиыны бойынша бағалауға болады (сурет 4), ол жерде кодтау дәрежесі 7/8 тең деп алынған, блок ұзындығы n = 32 символдан ( символға  w = 5 биттен келеді ) n=256 символға дейін өседі.

Осылайша, блок мөлшері 160 биттен 2048 битке дейін өседі.

Кодтың артықшылығының үлкею шарасы бойынша ( және оның кодтау дәрежесінің төмендетулері )  бұл  кодтың жүзеге асырылу қиындығы жоғарылайды ( әсіресе жоғарғы жылдамдықты құрылғылар үшін ). Сонымен бірге нақты уақыттағы байланыстағы жүйелер үшін өткiзу жолағының енi үлкеюi керек.