Дәріс 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.3)
Реттілік r6, r0 және т.б. компоненттеріндегі бір реттік қателік синдромдарына сәйкес келеді (15.1-кесте). 15.1-кестедегі мәндер 8.1-кесте(8 дәріс). мәндерімен толық сәйкес келеді. 8.1-кестесі Хэммингтің жүйелік (7,4) кодының тексеру матрицасы үшін алынған
15.1-кесте – генеративті көпмүшесі бар Циклдік (7,4)-хэмминг кодының бір реттік қателік синдромдары
Такт
|
s0 s1 s2
|
Ошибочная компонента
|
0
|
1 1 1
|
r5
|
1
|
1 0 1
|
r6
|
2
|
1 0 0
|
r0
|
3
|
0 1 0
|
r1
|
4
|
0 0 1
|
r2
|
5
|
1 1 0
|
r3
|
6
|
0 1 1
|
r4
|
Замечание. В рассмотренном примере вся таблица синдромов однократных ошибок генерируется с помощью простейшей схемы, поэтому, для кодов большей длины можно хранить в памяти декодера таблицы синдромов, а не саму проверочную матрицу.
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-сурет). Қателер пакетін келесі көпмүшелікпен сипаттауға болады
. (11.7)
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% - дан астамы анықталады.
Достарыңызбен бөлісу: |
