Дәріс 8 Сызықтық блоктық кодтар. Синдром және қателерді анықтау. Синдромдық декодтау

Жоғарыда қарастырылған (7, 4)-Хэмминг коды үшін келесі қателерді анықтау алгоритмін ұсынуға болады. Қарастырылып отырған код жүйелі болғандықтан, біз үш тексеру таңбаларының әрқайсысын ақпараттық вектордың символдары арқылы білдіреміз. Егер арнада қате болса, онда қабылданған R векторында теңдіктердің кем дегенде біреуі орындалмайды. Алынған тексеру қатынастарын R векторының құрамдас бөліктері үшін теңдеулер жүйесі түрінде жазамыз:

Осылайша, G матрицасының алғашқы үш бағанынан (3.2 формуласын қараңыз) біз үш тексеру теңдеулерінің жүйесін алдық, онда операциясы 2-модуль бойынша арифметика ережелеріне сәйкес жасалады (2-кестені қараңыз). Егер алынған теңдеулер жүйесінде кем дегенде бір компонент нөлге тең болмаса, онда арнада қате пайда болды. Тексеру теңдеулерінің жүйесін жалпы түрде жазамыз. Генератор матрицасы бар кез-келген жүйелік Код үшін (3.5), тексеру матрицасы

Мұндағы –транспонирленген матрица, яғни матрицаның жолдарын оның бағандарына ауыстыру арқылы алынған k x (n – k) өлшем матрицасы. Содан кейін тексеру теңдеулерінің жүйесін келесідей жазуға болады

Декодер тұтынушыға қате ақпарат сөзін арнада Анықталмайтын қателер болған кезде немесе арна қатесінің жиілігі кодтың түзету қабілетінен асып кетсе ғана бере алады. Жоғарыда келтірілген мысалдан белгілі бір кодтың тиімділігі оның қолданылу саласына, әсіресе байланыс арнасына байланысты екендігі шығады. Егер біз ақпаратты аддитивті ақ гаусс шуылмен (АБГШ) арна арқылы жіберетін болсақ, онда кодтық сөздегі қателер тәуелсіз болады. Егер сигнал / шу қатынасы жеткілікті үлкен болса, онда бір қатенің ықтималдығы жоғары жиіліктегі қателіктер ықтималдығынан бірнеше есе көп, сондықтан мұндай арнада бір қатені түзете отырып, Хэмминг кодын қолдану өте тиімді болуы мүмкін. Екінші жағынан, бірнеше қателер басым болатын арналарда (мысалы, қатып қалған арналарда) жалғыз қателерді түзету мағынасы жоқ. Нақты шуылға төзімді кодты практикалық таңдау кезінде оны декодтау жылдамдығы мен техникалық іске асырудың күрделілігін ескеру қажет

Мысал: (7, 4)-Хэмминг кодын синдромды декодтау.

(7.5) және (8.2) қолдана отырып, хэмминг кодының генеративті матрицасынан (3.2) тексеруші матрицасын саламыз. Ол түрі бар

Егер, мысалы, кодтық сөзде r = (0010010) төртінші позицияда бір қате пайда болса, онда синдром-транспонирленген тексеруші матрицасының төртінші жолы болып табылады

Бір қатенің барлық мүмкін позицияларын сұрыптай отырып, біз бір қате синдромдарының толық кестесін аламыз - бұл жағдайда алынған синдромның қате санының сәйкестік кестесі.

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

Оған 2^k кодтық сөзден тұратын k өлшемді сызықтық кеңістік салынған (8.1-сурет).

8.1-сурет-кодтық векторлық кеңістіктердің құрылымы

C коды үшін қосарлы C_d коды бар, сондықтан кез-келген жұп векторлардың скаляр көбейтіндісі, олардың біреуі C кеңістігіне, ал екіншісі C_d кеңістігіне тиесілі, әрқашан нөлге тең болады. Бұл C C_d кодының векторлары c кодының векторларына ортогоналды екенін білдіреді. Екінші жағынан, егер кейбір вектор С кодының барлық векторларына ортогоналды болса, онда ол C_d кодына жатады және керісінше.

Дуалды векторлық ішкі кеңістік (N – k) сызықтық тәуелсіз базистік векторларға" созылған". Бұл векторлар түзетуші матрицасының жолдарын құрайды
, (8.9)
Синдромды кодтау кезінде қабылдағыш кодтардың ортогоналдылық қасиетін қолданады

. (8.10)

Осылайша, әрбір код сөзі үшін дұрыс

8.2-сурет-ақпаратты екілік деңгейде беру моделі.

Жоғарыда қарастырылған мысалда төртінші биттегі бірлік қате е = (0001000) векторына сәйкес келеді.

Векторлардың сызықтық және ортогоналдылық қасиеттеріне байланысты

. (8.13)

Соңғы теңдік синдромды декодтаудың негізі болып табылады. Декодтау процесінде келесі жағдайлар туындауы мүмкін:

1 жағдай:

1.1-жағдай: - ақпаратты қатесіз беру;

1.2-жағдай: - түзетілмейтін қатесі бар ақпаратты беру;

2-жағдай: қате декодтау кезінде анықталады.

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

1. 
   Қателерді тану. Декодер әрқашан қабылданған r векторын қателікке тексереді. Тұтынушының талаптарына байланысты қабылданған Ақпараттық сөз немесе "өшіріледі" немесе оны қайта жіберуге сұраныс жасалады.
   
2. 
   Қателіктерді түзету. Декодердің түзету қабілетін жоғарыда қарастырылған (7,4) Хэмминг кодының мысалымен түсіндіруге болады.
   

Декодер тұтынушыға қате ақпарат сөзін арнада Анықталмайтын қателер болған кезде немесе арна қатесінің жиілігі кодтың түзету қабілетінен асып кетсе ғана бере алады. Жоғарыда келтірілген мысалдан белгілі бір кодтың тиімділігі оның қолданылу саласына, әсіресе байланыс арнасына байланысты екендігі шығады. Егер біз ақпаратты аддитивті ақ гаусс шуылмен (АБГШ) арна арқылы жіберетін болсақ, онда кодтық сөздегі қателер тәуелсіз болады. Егер сигнал / шу қатынасы жеткілікті үлкен болса, онда бір қатенің ықтималдығы жоғары жиіліктегі қателіктер ықтималдығынан бірнеше есе көп, сондықтан мұндай арнада бір қатені түзете отырып, Хэмминг кодын қолдану өте тиімді болуы мүмкін. Екінші жағынан, бірнеше қателер басым болатын арналарда (мысалы, қатып қалған арналарда) жалғыз қателерді түзету мағынасы жоқ. Нақты шуылға төзімді кодты практикалық таңдау кезінде оны декодтау жылдамдығы мен техникалық іске асырудың күрделілігін ескеру қажет