Ақпараттар және кодтау теориясы
Дәріс 15. Циклдік кодтар синдромы және қателерді бақылау. Қателік пакеттері. Меггитт декодері. Хеммингтің циклдік кодтары
жүктеу/скачать 1,27 Mb.
|
лек1 (2)
| Дәріс 15. Циклдік кодтар синдромы және қателерді бақылау. Қателік пакеттері. Меггитт декодері. Хеммингтің циклдік кодтары.
Циклдік кодтар синдромы және қателерді бақылау. Ақпаратты беру моделін қарастырайық (15.1-сурет). Шуылмен байланыс арнасы арқылы беру кезінде v(X) кодтық сөзіне e(Х) қателерінің көпмүшесі қосылады. Нәтижесінде, қабылданған код сөзінің көпмүшелік түрі бар: r(X) = v(X) + e(Х). (15.1) немесе r(X) = a(X)g(X) + s(X), (15.2) мұндағы s(X) синдром. Егер r(X) код сөзі болса, онда s(X) - нөлдік көпмүшелік. 15.1-сурет-ақпаратты беру моделі S(X) синдромын Евклидтің бөліну алгоритмімен есептеуге болады. Мұндай есептеуді жүйелік циклдік код код код кодеріне ұқсас қарапайым тізбекте (15.2-сурет) жүзеге асыруға болады. 15.2-сурет- g(x) генеративті көпмүшелікпен жүйелік (n, k) - код синдромын есептеу 15.2-суретте келтірілген схемада белгілі бір көпмүшені G(Х) генерациялайтын көпмүшеге бөлуден қалған қалдық анықталады. Алдымен, декодерде синдромның екілік разрядтары нөлге теңеледі және синдром регистріне бит каналынан қабылданған алғашқы r енгізіледі. Евклид алгоритмі бойынша R(Х) генерациялайтын көпмүшеге бөлінуден қалған қалдық синдром тіркеліміне енгізіледі. Мысал: циклдік (7,4)- Хэмминг кодының синдромын есептеу. Мысал ретінде біз бұрыннан белгілі генеративті көпмүшесі бар циклдік (7,4)- Хэмминг кодын қарастырамыз . u = (1001) ақпараттық векторы болсын. Алдыңғы мысалдан білетініміздей, v = (011 1001) код сөзі осы векторға сәйкес келеді. Шусыз канал арқылы берілгенде r = v. синдромды цикл бойынша есептеу процедурасы, бұл жағдайда, 15.3-суретте көрсетілген. Арнадан қабылданған сөз код болғандықтан, біз нөлдік синдромды аламыз. 15.3-сурет – Шусыз арнада қабылданған сөз бойынша жүйелік (7,4)-код синдромын есептеу. Арнадағы Шу әсерінен бір қате пайда болсын r = (011 1011). Онда r(X)-ді g(x) - ге (15.4-сурет) бөлудің қалдығын есептеу нәтижесінде біз нөлдік емес синдромды аламыз. Осылайша, қатені таный аламыз.
15.4-сурет – Жүйелік (7,4)-код синдромын қабылданған сөздегі бір қатемен есептеу. Теорема 1. S(X) - арнадан алынған r(Х) сөзінің белгілі бір циклдік (n, k)-код синдромы болсын. Біз s1(X) арқылы X s(X) көпмүшесін g(x) көпмүшеге бөлудің қалдығын белгілейміз. Содан кейін s1(X) - синдромы болады, яғни R(X) циклдік ығысудың g (x) генеративті көпмүшеге бөлінуінің қалдығы. Мысал: Хэмминг циклдік (7,4) коды үшін бір реттік қателер синдромын есептеу. 15.5-сурет – Қабылданған сөздің циклдік ығысу синдромдарын есептеу. Алдыңғы мысалды жалғастырайық. 15.3-суреттен вектордың r5 компонентіндегі бір реттік қателерге синдромы сәйкес келеді (такт N = 7). Кіріс регистрін өшіргеннен кейін біз 15.5 суретте көрсетілген схеманы аламыз. n = 0 тактідегі бастапқы күй r5 компонентіндегі бір қателік синдромымен анықталатынын ескеріңіз.15.36-сурет синдромының регистрінің циклдік өзгерістерін жасай отырып, біз келесі формуладан әр циклде табамыз
15.1-кесте – генеративті көпмүшесі бар Циклдік (7,4)-хэмминг кодының бір реттік қателік синдромдары
Замечание. В рассмотренном примере вся таблица синдромов однократных ошибок генерируется с помощью простейшей схемы, поэтому, для кодов большей длины можно хранить в памяти декодера таблицы синдромов, а не саму проверочную матрицу. s(X) синдромы мен е(Х). қателіктерінің көпмүшесі арасындағы байланысты қарастырайық. Ақпаратты беру моделінен (15.1-сурет) келсіні аламыз , (15.4) мұндағы
. (15.5) себебі
r(X) = a(X)g(X) + s(X), онда
e(X) = [a(X) + c(X)] g(X) + s(X). (15.6) (15.6) өрнегі мынаны білдіреді . Хэмминг коды барлық бір ретік қателерді түзететіндіктен, (n, k)-хэмминг кодына синдромдар кестесін құру үшін e (X) ретінде Х0, X1,..., Хn-1 барлық бірмүшелерді сұрыптау жеткілікті. Синдромды білу e(X) көпмүшесін нақты анықтауға мүмкіндік бермейді. Мысалы, егер e(X) g (X) қалдықсыз бөлінсе, онда бұл жағдай нөлдік синдромға сәйкес келеді және қатені тану мүмкін емес. Бұл жағдайда анықталмаған немесе қалдық декодтау қатесі туралы айтылады.
15.6-сурет - 7 ұзындықтағы қателер пакетінің векторы. Егер қателер пакетінің ұзындығы r = n – k шамасынан аспаса, онда қателер көпмүшелігінің дәрежесі R-ден аз болады. бұл жағдайда E(X) g (X) қалдықсыз бөлінбейді және қабылданған сөз синдромы әрдайым нөлге тең болады, сондықтан r-ге тең немесе одан аз ұзындықтағы қателер пакеті әрқашан танылады. 1 теоремасынан, сондай-ақ R-ден кіші(Х) дәрежедегі көпмүшенің кез келген циклдік ығысуы, яғни R-ден кіші немесе тең ұзындықтағы "соңғы" қателер пакеті танылатыны шығады (15.7-сурет), әрқашан танылады. 15.7-сурет - ұзындықтағы қателіктердің "соңғы" пакетінің векторы 7. Теорема 2. Циклдік (n , k)-код r = n – k және одан аз ұзындықтағы барлық қате пакеттерін (оның ішінде соңғы) анықтай алады. Теорема 3. Циклдік (n , k) код үшін L = r + 1 = n-k + 1 ұзындықтағы Анықталмайтын қателер пакеттерінің үлесі .тең . Теорема 4. Циклдік (n , k) Код үшін Анықталмайтын L > r + 1 = n-k + 1 ұзындықтағы қателер пакеттерінің үлесі тең . Мысал. Қателерді циклдік (7,4)-Хэмминг кодымен тану. Алдыңғы мысалдардан циклдік (7,4)-Хэмминг кодын қарастырайық, мұнда r = n – k = 3. Хэмминг кодының минималды қашықтығы dmin = 3 болғандықтан, ол барлық Қос қателерді анықтай алады немесе жалғыз қателерді түзете алады. Қарастырылған (7.4)-Хэмминг коды циклдік код болып табылады және ол r = 3 ұзындығының барлық пакеттерін анықтай алады. Атап айтқанда, келесі үш қате әрқашан анықталады. Анықталмаған r + 1 = 4 ұзындықтағы қателерінің үлесі тең . Ұзындығы 4-тен асатын қателер пакеттерінде олар тек танылмайды. Ескерту. Іс жүзінде, әдетте, r = n – k = 16 сияқты өте көп тексеру разрядтары бар Циклдік кодтар қолданылады. Мұндай кодтармен Анықталмайтын қателер пакеттерінің үлесі аз. Сонымен, r = 16 кезінде ұзындығы 17 пакеттің 99.9969% және ұзындығы 18 және одан жоғары пакеттердің 99.9984% - дан астамы анықталады.
жүктеу/скачать 1,27 Mb. Достарыңызбен бөлісу:
|