23. Бөгеуілге тұрақты модульденген сигналдардың бағасы

1. Қателерді табудың және дұрыстаудың негізгі принциптері

Қателерден қорғау үшін өтімділікті қолданудың екі негізгі тәсілін қарастырайық. Бірінші тәсілде қатені табу және қате болуының тексеру үшін қайта жіберу жұптық бақылау биті (контрольный бит четности)  қолданылады. Бірақ қабылдау (оконечное) құрылғысы қатені түзету үшін ешқандай әрекет жасамайды, ол тек қана таратқышқа мәліметтерді қайта жіберуге сұраныс жасайды.  Осындай таратқыш және қабылдағыш арасындағы диалог үшін екі жақты байланыс қажет. Екінші тәсіл, тура түзету,  бұл тек қана бір жақты байланыс желісін қажет етеді, өйткені бұл жағдайда жұптық бақылу биті қателерді табу үшін де, оларды түзету үшін де қызмет етеді.  Ары қарай біз барлық қателер комбинациясын түзетуге болмайтынын көреміз, сондықтан түзету кодтары қателерді дұрыстау мүмкіндіктеріне байланысты жіктеледі. Қателерді кодтар арқылы  табу және түзеу  принципі  геометриялық модельдердің көмегімен суреттеледі. Кез-келген  n-элементті екілік  кодты n – бір қалыпты куб ретінде қарастыруға болады, онда әрбір шың кодалық комбинацияны көрсетеді, ал куб қабырғасының  ұзындығы бір бірлікке сай келеді. Бұндай кубта шыңдар арасының қашықтығы олардың арасында орналасқан қабырғаларының минималды санымен есептеледі, ол d болып белгіленеді және кодалық қашықтық деп аталады .

2. Кодалық қашықтық және кодтың түзету қабілеті

Кодалық қашықтық - бұл кез-келген кодалық комбинация басқасынан ажыратылатын  элементтердің минималды саны. Мысалы, код мынандай комбинациялардан тұрады:  1011, 1101, 1000 және  1100. Бірінші екі комбинацияны салыстыра отырып  d=2  табамыз. Ең үлкен шама d=3 бірінші және төртінші комбинацияларын салыстырғанда табылады, ал ең кішісі  d=1 екінші және төртінші, үшінші және төртінші  комбинацияларды салыстырғанда табылады. Үш өлшемді кубта бір-бірінен d=3-ке ажыратылатын кодалық белгілері бар шыңдарды таңдайық. Бұндай шыңдар кубтың кеңістік диагоналдарының ұштарында орналасады.  Олар тек төрт жұпты болады: 000 және 111, 001 және 110, 100 және 011, 010 және 101.  Осындай ережемен  жасалған код дара қатені түзете алады немесе екі дара қатені таба алады.

Кодтың түзету қабілеті кодалық қашықтыққа байланысты: а) d=1 кезінде қате табылмайды; б)  d=2 кезінде дара қателер табылады; в)  d=3 кезінде дара қателер түзетіледі немесе екілік қателер табылады. Жалпы жағдайда

 ,                                             (1)

мұндағы    d - минималды кодалық қашықтық,      r - табылған қателер саны,

s - түзетілген қателер саны. Сонымен  r≥s қажетті шарт болып табылады.

3. Кодтарды түзету классификациясы

Түзету кодтары деп кодалық комбинациялардағы қателерді түзете алатын және қателерді таба алатын кодтарды атайды. Олар екі топқа бөлінеді: 1) табылған қателер кодтары; 2) табылған және түзетілген қателер кодтары.

1) Табылған қателер кодтарының ерекшелігі болып оның құрамындағы кодалық комбинциялардың бір-бірінен кем дегенде d=2–ге ажыратылатынында. Оларды шартты түрде екі топқа бөлуге болады:

а) қолданылатын комбинациялардың санын кеміту арқылы құрылған кодтар.

Комбинациялардағы бірліктер және нөлдердің тұрақты саны бар код.

  ,                                          (2)

мұндағы  l – n ұзындықты сөздегі бірліктер саны.

Бөліп тұратын  код Бұл да бірге  тең тұрақты салмақпен кодтың түрі. Кез-келген кодалық  комбинацияда тек қана бір бірлік болады.  Бөліп тұратын  кодтағы кодалық комбинациялар саны

.                                                (3)

n=6 кезінде кодалық комбинацияларды мынандай түрде жазуға болады: 000001,000010,000100,001000,010000,100000. Екі комбинацияның  2 модулі бойынша бірігуі олардың бір-бірінен  d=2 кодалық қашықтыққа ажыратылатынын көрсетеді.

1 К е с т е - Тұрақты бірліктер және нөлдер саны бар кодтар 

Код	Код
11000   10010 01010   00011 01100   01001 00101   10001 00110   10100	1010100 0101010 1110000 0000111 1001001

 

б) барлық комбинациялар қолданылатын, бірақ олардың әр біреуіне белгіленген ереже бойынша бақылау символдары қосылатын кодтар,  m - символдар.  Жұптыққа тексеретін кодтар. Бұндай түр (неизбыточного) кодтың ақпараттық символдардан тұратын жіберіліп жатқан комбинацияға m (0 немесе 1) бақылау символын  қосу арқылы жүзеге асады. Жіберіліп жатқан комбинацияның бірліктерінің жалпы  саны жұп болу үшін жасалады.   Жалпы жағдайда:

.                                                  (4) 

2  К е с т е - Жұптыққа тексеретін кодтар 

к  ақпараттық символдары	m бақылау символдары	n=k+m толық кодалық комбинация
1	2	3
11011 10101 00010 11000 11110 11111	0 1 1 0 0 1	110110 101011 000101 110000 111100 111111

 

Комбинациялардың жалпы саны     N=2n-1

в) бірліктер саны үшке тең бөлінетін кодтар. Бұл код ақпараттық символдарға кодалық комбинациялар сызығына жіберілетін бірліктер қосындысы тең болатын мәндері бар  екі қосымша бақылау символдарын (m=2) қосу арқылы жасалады.

3 К е с т е - Бірліктер саны үшке тең бөлінетін кодтар

Ақпараттық символдар к	Бақылау символдары m	Толық кодалық комбинация
000110 100011 101011	10 00 11	00011010 10001100 10101111

2) Қателерді табатын кодтардың ерекшелігі  олардың  түзететін код құруында. Түзететін кодтарды құрастыру келесі ереже бойынша жасалады: алдымен ақпараттық символдардан тұратын  кодалық комбинацияға қосу керек  бақылау символдарын анықтайды. Содан осы бақылау символдары орналасатын  орын белгілінеді.

Хемминг кодтары. Хемминг кодтары (Hamming codes) - бұл келесідей құрылымы болатын блокты кодтардың қарапайым класы: 

,                                                  (4)

мұндағы m= 2,3,.. Осы кодтардың минималды қашықтығы 3, сондықтан олар барлық бірбитті қателерді түзете алады немесе блоктағы барлық екі не одан аз қателер комбинациясын таба алады.  Хемминг кодтарына синдромдар көмегімен декодалау оңай жүзеге асады.  Фактілі түрде синдромды қатенің орналасуының екілік көрсеткішіне айналдыруға болады.  Бірақ Хемминг кодтары қатты қуатты болып табылмайды, олар блокты кодтардың өте  шектелген класына жатады.  Циклдік кодтар. Сызықты блокты кодтардың маңызды класстар ішіндегі  болып  екілік циклдік кодтар табылады  (cyclic codes). Сызықты код (n, к)  циклдік деп аталады, егер  ол  келесі қасиетке ие болса.   Егер n-кортеж U= (u0, u1, и2, …, un-1)  S кеңістік ішіндегі  кодтық сөз болса, онда U(1)=(un-1, u0, u1, и2,..., un-1),  циклдық ығысудың көмегі арқылы U-дан алынған S-да да кодтық сөз болып табылады.  Немесе  жалпы алғанда  U(i)=(un-i;. un-i+1,…, un-1, u0, u1,… un-i-1), алынған i циклдық ығысулармен  S-те кодтық сөз болып табылады.

Файра циклдік коды. Қателер жинағын табатын және түзететін циклдік кодтар (Файра кодтары). b ұзындықты қателер жиынтығын шеткі разрядтардың арасындағы бөгеттермен бұзылған b-2 разряды бар бөгет комбинациясының түрін түсінеді. Мысалы, b=5 кезінде бөгеттер комбинациясы, яғни қателер жиыны  келесі түрде болуы мүмкін: 10001 (тек шеткі екі символдар ғана бұзылған), 11111 (барлық символдар бұзылған ), 10111, 11101, 11011 (тек бір ғана символ бұзылмаған), 10011, 11001, 10101 (үш символ бұзылған). Файра кодтары b ұзындықты қателер жиынын түзете алады және b ұзындықты қателер жиынын таба алады.

Боуза-Чоудхури-Хоквингэм кодтары . Бұл кодтарды Боуз, Чодхури и Хоквингэм (қысқартылғанда БЧХ кодтары)  құрастырған, осы кодтар кез-келген қателер санын тауып, түзей алады. БЧХ кодтарың қателерді табу үшін келесі тәсілмен құрайды. Егер жұп санды қателерді табатын код құру қажет болса, онда берілген  r саны бойынша d және s мәндерін табады.  Егер тақ санды қателерді табатын код құру қажет болса, онда  жақын аз бүтін  s санын табады және алдыңғы жағдайдағыдай кодтау жүргізіледі: көпмүшені қосымша екі мүшегекөбейтеді. Мысалы, n=15 кезіндегі  жеті қатені табатын код құру керек. Осыдан  d=8 , ал ең жақын аз шама s=3. Енді көпмүшеніанықтаймыз және оны екімүшегекөбейтеміз, яғниаламыз. Осындай тәсілмен БЧХ(15,4) коды құрылады.