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

Артықшылықтың үлкеюi, мысалға символ өлшемінің үлкеюі, биттік қателердің пайда болу ықтималдығының азаюына әкеледі (сурет 5), сонымен бірге п кодтық ұзындық мәлiметтердiң символдарының санының төмендетуiнде k = 60 мәнінен k = 4 ке дейін (артықшылық 4 тен 60 символға дейін өседі) тұрақты 64  мәніне тең.

Гипотеза декодерлерiнің  беріліс функциясы ( кіріс символдық қателердің пайда болу ықтималдығынан тәуелді шығыс биттік қателердің пайда болу ықтималдығы) көрсетілген (сурет 5). Себебі бұл жерде анықталған жүйе немесе канал ескерілмейді (тек декодердің кірісі мен шығысы ), берiлудi сенiмдiлiк артықшылықтың бiр қалыпты функциясы болып табылатынын және кодтау дәрежесінiң нөлге жуықтауымен өсетiнi жөнінде қорытынды жасауға болады.

 

Сурет 4. Символ өлшемінің функциясы ретінде (кодтау дәрежесі= 7/8 ) Рид-Соломон декодерінің сипаттамалары.

 

 

Сурет 5. (64, k) Рид-Соломон декодерінің артықшылық функциясы ретінде сипаттамалары.

 

Бірақ бұл  нақты уақыттың байланыс жүйесінде қолданылатын код  үшін емес. Кодтың максимальді мәнінен  минимальді мәніне дейін (0 ден 1 ге дейін) кодтау дәрежесінің өзгеру шарасы бойынша көрсетілген эффектілерді көруге болады (сурет 6). Мұнда жұмыстың қисықтық мiнездемелері екiлiк фазалық манипуляциясы (BPSK) кезінде және әр түрлі типтегі каналдардың (31, к)  кодтарында көрсетілген. Нақты уақыттағы байланыс жүйелері көрсетілген (сурет 6), бұл жүйеде қателерді түзетудегі кодтауына кодтаудың кері дәрежесіне тең көлеміне пропорционал келетін өткiзу жолағының кеңейтуiмен төлеуге тура келеді. Келтірілген қисықтар тиiстi мәнді минималдайтын кодтау дәрежесінің айқын ұтымдылығын көрсетеді.  Гаусстық канал үшін кодтау дәрежесінің ұтымды мәні 0,6 және 0,7 мәндері аралығында жатады, райсовкілік қатуымен каналы үшін 0,5 шамасында (түзу сигнал қуаттылығының шағылған К = 7 дБ қуаттылығына қатынасы) және 0,3 -релеевті қатуы бар канал үшін. Неге мұнда кодтаудың өте жоғарғы дәрежесінде де (аз артықшылықта) және өте төменгі (артықшылықтың көп болуында) дәрежесінде де нашарлауы байқалады. Кодтаудың жоғарғы дәрежесі үшін кодтаудың жоғарғы дәрежесін кодтаудың ұтымды дәрежесімен салыстыра отырып мұны түсіндіру оңай. Кез келген код негізінен кодтаудың барлық артықшылықтарын қамтамасыз етедi; демек, кодтаудың дәрежесі бiрлiкке жақындатылған бойда (кодталу болмайды) жүйе жіберілудің сенімділігі бойынша ұтылады. Кодтаудың төменгі дәрежесінде сипаттамалардың нашарлауы өте маңызды сұрақ болып табылады, себебі нақты уақыттағы байланыс жүйелерінде модуляция және кодтау қолданылады, яғни екі механизм жұмыс істейді. Бір механизм қателердің пайда болу ықтималдығын азайтады, ал басқасы оны жоғарылатады.  Қателердің пайда болу ықтималдығын азайтатын механизм - бұл кодтау; артықшылық көп болған сайын кодтың қателерді түзету мүмкіндігі де үлкен болады. Бұл ықтималдылықты үлкейететін механизм -  бұл каналдық символға (ақпараттық символмен салыстырғанда) келетін энергиянының азаюы, ол артықшылықтың үлкеюінен ( және нақты уақыттағы байланыс жүйелеріндегі сигналдардың жылдамырақ жіберілуінен) болады.  Символдың азайтылған энергиясы демодуляторды қателерді көп жасауына мәжбүрлейді. Түпкі есепте екінші механизм біріншісін басады, сол себепті кодтаудың өте төмен дәрежесі код сипаттамаларының нашарлауына әкеледі [3], [5].

Сурет 6 - да көрсетілген қателердің пайда болу ықтималдылығының кодтау дәрежесінен тәуелділігін сурет 2 - де бейнеленген қисықтардың көмегімен растап көрейік. Суреттерді тікелей салыстыру сәтті болмайды, себебі  сурет 6 - да BPSK (екiлiк фазалық манипуляциясы) модуляциясы қолданылады, ал сурет 2 - де 32-лік MFSK (манипуляцияның бiрнеше жиiлiктерi) модуляциясы.

 

 

Сурет 6. Кодтау дәрежесінің (BPSK модуляциясы) функциясы ретінде (31, k) Рид-Соломон декодерінің сипаттамалары.

 

 

1.3 Рид-Соломоннның кодталуы

 

 

(1.1.2) теңдігінде Рид-Соломон  кодтарының ішінде ең көп таралған  формасы  n, k, t  параметрлері арқылы және кейбір m > 2 оң саны арқылы көрсетілген. Осы теңдікті қайта келтірейік.

 

                                        (1.3.1)

 

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

 

                                             ( 1.3.2)

 

Полиномды генератор дәрежесі бақылау  симводарының санына тең. Рид-Соломон  кодтары БЧХ (Боуза - Чоудхури - Хоквингхема) кодының ішкі жиыны болып табылады. Сол себепті  БЧХ  кодтарындағыдай полиномды генератор дәрежесі мен бақылау символдары арасындағы байланыстың  болғаны күтпеген жағдай емес.  Сондықтан полиномды генератор 2t қатарына ие, біз нақты полином түбірі болып келетін дәрежесінің нақты тізбектілігін алуымыз керек. түбірлерін деп белгілейміз. Тек қана түбірінен бастаудың қажеттілігі жоқ, мұны – ның кез келген дәрежесінің көмегімен жасауға болады. Екі символдық қателерді түзету мүмкіндігі бар (7,3) кодты мысалға алайық. Біз түбірі арқылы полиномды генераторды келесідей өрнектейміз [4], [9]. 

 

( 1.3.3)

                               

1.4 Систематикалық формада кодтау

 

 

Рид-Соломон коды циклдық  болғандықтан систематикалық формада  кодтау екілік кодтауға ұқсас. m(X) хабарламасы полиномын кодтық сөздің регстрінің оң жақ шеттегі k  разрадтарына жылжыта аламыз және келесі p(X)  ақиқаттық полиномын сол жақ шеттегі n – k разрядтарына қоса аламыз. Сол себепті m(X) – ті – ке көбейтеміз, осылайша алгебралық операцияны орындай отырып, m(X)  оңға қарай n – k позицияға жылжыған болады. Одан кейін – ті g(X) полиномды генераторына бөлеміз, оны келесідей түрде жазуға болады.

                           (1.4.1)  

                              

мұндағы q(X) және p(X) – бұл бөлімді және полиномды бөлінуден кейінгі қалдық. Екілік кодтаудағы жағдайдағыдай қалдық жұп сан болады. (1.4.1)                                    теңдігін келесідей ұсынуға болады.

 

                                                       (1.4.2)

 

U(X) кодтық сөзінің нәтижелік полиномын келесідей жазуға болады.

 

                                  (1.4.3)

 

(1.4.2) және (1.4.3) теңдіктерімен ойластырылған қадамдарды көрсетеміз, хабарламаны үш сөзбен кодтау арқылы

(7,3) кодының көмегімен  және генераторы (1.3.3)                                   теңдігімен анықталады.  Алдымен хабарлама полиномын – ті

–ке көбейтеміз (жоғарға жылжыту), ол мынаны береді Одан кейін жоғарыға жылжытылған хабарлама полиномын полиномды генераторға бөлеміз, (1.3.3)                                    теңдігінен Екілік емес коэффициенттердің полиномды бөлінуі – бұл шаршататын процесс. Полиномды бөліну нәтижесінде келесідей полиномды қолдықты (полином ақиқаттығы) беретінін дәлелдеу ретінде алымға қосымша жаттығуды береміз.

 

                                  

                           (1.4.4)

 

(1.4.3) теңдігінен кодтық сөздің полиномын келесідей үлгіде жазуға болады [5].

 

          

         (1.4.5)

 

 

1.5  Рид – Соломон декодталуы

 

 

1.3 бөлімінде мәтіндік  хабарлама (7,3) кодының көмегімен  систематикалық формада кодталады,  оның нәтижесінде кодтық сөздің полиномы алынады.  Хабарлама жіберу кезінде кодтық сөз бұрмалануға ұшыраған болсын: екі символ қате қабылданған. (Қателердің мұндай саны қателерді түзетуші кодтың мүмкіндігіне сәйкес келеді). 7-символдық кодтық сөзді пайдалану кезінде қателік комбинациясын келесідей полиномды үлгіде көрсетуге болады.

                                         

                                                                   (1.5.1)

 

Екі символдық қателік  мынадай болсын:

 

    (1.5.2)

 

Басқаша айтатын болсақ, бақылау  символы 1-биттік қателікке бұрмаланған ( түрінде көрсетілген), ал хабарлама символы 3-биттік қателікке ( түрінде берілген). Бұл жағдайда r(Х) өзгеріске ұшыраған кодтық сөздің  қабылданған полиномы жіберілген кодтық сөздің полиномы мен қателік комбинациясының полиномының қосындысы түрінде болады, төменде көрсетілгендей.

 

                                                                                (1.5.3)

 

(1.5.3) теңдігіне сәйкес (1.5.4) теңдігінен U(X) – ті және (1.5.2) теңдігінен e(Х) – пен қосамыз. Және келесіге ие боламыз.

 

(1.5.4)

 

Бұс мысалда 2-символдық  қатені түзеуде төрт белгісіз  айнымалы бар: екеуі қателердің орналасуына жатады, ал екеуі қателік мағынаға қатысты.  (1.5.4) теңдігінде көрсетілген екілік емес декодтау r(Х) мен екілік кодтау арасындағы маңызды айырмашылықты көрсетейік. Екілік кодтау кезінде декодерге тек қана қатенің орналасқан жерін білу керек. Егер қатенің орналасқан жері анықталса, битті 1– ден 0–ге ауыстыру қажет немесе керісінше. Бірақ мұнда екілік емес символдар тек қатенің орналасқан жерін анықтауды талап етіп қоймайды, сонымен бірге символдың осы позициядағы орналасқан дұрыс мәнінің анықталуын талап етеді. Ал оларды табу үшін теңдік керек болады [6]. 

Синдром дегеніміз – бұл ақиқаттылықты тексеру нәтижесі, ол r – ге қатысты орындалады және r – дің  кодтық сөзге жататындығын анықтау үшін қажет. Егер r жиынтық мүшесі болып табылса, онда S синдром мәні 0 – ге тең. Кез келген 0 – ге тең емес S қателердің бар болуын білдіреді. S синдром n-k символдарынан тұрады, . Осылайша, біздің (7, 3) код үшін синдромның әр векторына төрт симводан келеді; олардың мәндерін қабылданған r(Х) полиномынан  есептеуге болады. Полином түбірі g(X) және де ол g(X) генерацияланатын кодтық сөздің түбірі болуы керек, себебі дұрыс кодтық сөз келесідей түрге ие.

 

                                                                                    (1.5.5)

 

Бұл құрылымнан U(X) кодтық сөзінің әрбір дұрыс полиномы g(X) полиномды генераторға еселi екенін көруге болады. Бұдан шығатыны g(X) түбірлері және де U(X) түбірлері болуы керек. Себебі , яғни g(X) әр түбірден есептелетін r(Х) нөлді беру керек, егер де тек r(Х) дұрыс кодтық сөз болса. Кез келген қателер бір жағдайдың (немесе бірнеше жағдайдың) нәтижесінде нөл болады. Синдром символдарын есептеуді келесідей жазуға болады.

 

                                                          (1.5.6)

 

мұндағы  S – синдром мәні,  r(Х) – қабылданған полином. Мұнда r(Х) 2- символдық қателерден тұрады. Егер r(Х) дұрыс кодтық сөз болып шықса, онда бұл синдромның барлық символдары нөлге тең болуына алып келеді. Келесі келтірілген мысалда синдромның төрт символы төмендегідей орналасады.

 

                              (1.5.7)

                 (1.5.8)

                (1.5.9)

               (1.5.10)

 

Нәтижеден қабылданған  кодтық сөз қатеден тұрадынғын көруге болады, себебі [7], [10].

Кодтық сөздің позицияларында орналасқан  қателері бар болсын. Онда қателер полиномын келесідей жазуға болады.

 

                                                         (1.5.11)

 

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

 

                                                 (1.5.12)

 

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

Егер синдромның нөлдік емес векторы (бір немесе бірнеше символдары нөлге  тең емес) есептелген болса, онда қате қабылданғанын білдіреді. Одан кейін қатенің (немесе қателердің)  орналасуын анықтау керек. Қателер локаторының полиномын төмендегідей жолмен анықтауға болады.

 

                                               (1.5.13)

 

- тің түбірлері  болады. түбірлеріне қарсы шамалар e(Х) қате комбинациясының орналастырылуларының нөмiрлерiн ұсынады. Онда авторегрессиялық модельдеу техникасын пайдалана отырып, синдромнан матрица құрамыз, ол матрицада алғашқы t синдромдар келесi синдромды болжауы үшiн қолданылады.

 

                               (1.5.14)                

 

Нөл емес анықтауышы бар  ең үлкен өлшемді матрицасын алып,  авторегрессиялық модельдеу техникасын қолдандық. Екі символдық қателері түзетулері бар (7, 3) коды үшін матрица өлшеміне ие болады, және модель келесідей үлгіде жазылады.

 

                                                                              (1.5.15)

                                                                            (1.5.16)

 

 қателер локаторының полиномының  және коэффициенттерін табу үшін алдымен  (1.5.16) теңдігіне кері матрицаны есептеу қажет. [А] матрицасы үшін кері матрица төмендегідей анықталады [8], [12].