Ақпараттар және кодтау теориясы

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

жүктеу 1,27 Mb.

бет	12/28
Дата	04.03.2023
өлшемі	1,27 Mb.
	#41586

1 ... 8 9 10 11 12 13 14 15 ... 28

А параттар ж не кодтау теориясы

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

Декодердің міндеті-қабылданған R сөзіне сәйкес Код құрылымын қолдана отырып, берілген ақпараттық векторды қалпына келтіру.

Жоғарыда қарастырылған (7, 4)-Хэмминг коды үшін келесі қателерді анықтау алгоритмін ұсынуға болады. Қарастырылып отырған код жүйелі болғандықтан, біз үш тексеру таңбаларының әрқайсысын ақпараттық вектордың символдары арқылы білдіреміз. Егер арнада қате болса, онда қабылданған R векторында теңдіктердің кем дегенде біреуі орындалмайды. Алынған тексеру қатынастарын R векторының құрамдас бөліктері үшін теңдеулер жүйесі түрінде жазамыз:
(8.1)
Осылайша, G матрицасының алғашқы үш бағанынан (3.2 формуласын қараңыз) біз үш тексеру теңдеулерінің жүйесін алдық, онда операциясы 2-модуль бойынша арифметика ережелеріне сәйкес жасалады (2-кестені қараңыз). Егер алынған теңдеулер жүйесінде кем дегенде бір компонент нөлге тең болмаса, онда арнада қате пайда болды. Тексеру теңдеулерінің жүйесін жалпы түрде жазамыз. Генератор матрицасы бар кез-келген жүйелік Код үшін (3.5), тексеру матрицасы
, (8.2)
Мұндағы –транспонирленген матрица, яғни матрицаның жолдарын оның бағандарына ауыстыру арқылы алынған k x (n – k) өлшем матрицасы. Содан кейін тексеру теңдеулерінің жүйесін келесідей жазуға болады
. (8.3)

S векторы әдетте синдром деп аталады. Осылайша, егер s компоненттерінің кем дегенде біреуі нөлге тең болмаса, қате анықталады. (8.3) теңдікті келесі түрде қайта жазуға мүмкіндік береді

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

(8.5)

u = (1010) ақпараттық сөзді арна арқылы шуылсыз беру кезінде r = v = (0011010). Бұл жағдайда синдромның келесіге тең екеніне көз жеткізе аламыз

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

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

8.1-кестеХэмминг (7,4) - кодының бір реттік қате синдромдарының кестесі.

Код сөзі r	r₀	r₁	r₂	r₃	r₄	r₅	r₆
Синдром s	100	010	001	110	011	111	101

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

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

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

С коды k сызықтық тәуелсіз базалық векторлардың 2^k комбинациясы бойынша жасалады. Бұл векторлар С кодының генерациялық матрицасының жолдарын құрайды

. (8.8)

Генеративті матрицаны Р матрицасына және I матрицасына жүйелік кодтар болған жағдайда ғана бөлуге болатындығын ескеріңіз.

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

, (8.9)

Синдромды кодтау кезінде қабылдағыш кодтардың ортогоналдылық қасиетін қолданады

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

Кодқа жатпайтын әрбір қабылданған сөз нөлден өзгеше синдромға сәйкес келеді

. (8.12)

Екілік компоненттер деңгейінде синдромдық декодтауды талдайық (8.2-сурет).

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

Арнада V код векторының екілік модуліне Е екілік қате векторымен компоненттік қосу жасалады, осылайша, егер i-векторының i-компоненті "1" болса, онда V код векторының i компонентінде қате пайда болады.

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

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

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

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

8.1-кестеде бір қателік болған жағдайда оның позициясы синдроммен нақты анықталатындығы және осылайша бір қате әрдайым түзетілетіні көрсетілген. Үлкен жиіліктің қателерін декодер әрқашан жалғыз деп түзетеді, ал тұтынушыға қате ақпарат сөзі беріледі. Мысалы, u = (1010) ақпараттық векторына сәйкес келетін v = (0011010) код сөзі жіберілсін, ал қате векторы e = (1100000), яғни арнада екі рет қате пайда болды. Содан кейін r = (1111010) қабылданған сөз үшін синдром s = (110). 8.1-кестеден бұл синдром r векторының төртінші қате компонентіне сәйкес келеді. Сондықтан тұтынушыға = (0010) векторы беріледі
Декодер тұтынушыға қате ақпарат сөзін арнада Анықталмайтын қателер болған кезде немесе арна қатесінің жиілігі кодтың түзету қабілетінен асып кетсе ғана бере алады. Жоғарыда келтірілген мысалдан белгілі бір кодтың тиімділігі оның қолданылу саласына, әсіресе байланыс арнасына байланысты екендігі шығады. Егер біз ақпаратты аддитивті ақ гаусс шуылмен (АБГШ) арна арқылы жіберетін болсақ, онда кодтық сөздегі қателер тәуелсіз болады. Егер сигнал / шу қатынасы жеткілікті үлкен болса, онда бір қатенің ықтималдығы жоғары жиіліктегі қателіктер ықтималдығынан бірнеше есе көп, сондықтан мұндай арнада бір қатені түзете отырып, Хэмминг кодын қолдану өте тиімді болуы мүмкін. Екінші жағынан, бірнеше қателер басым болатын арналарда (мысалы, қатып қалған арналарда) жалғыз қателерді түзету мағынасы жоқ. Нақты шуылға төзімді кодты практикалық таңдау кезінде оны декодтау жылдамдығы мен техникалық іске асырудың күрделілігін ескеру қажет

жүктеу 1,27 Mb.

Достарыңызбен бөлісу:

1 ... 8 9 10 11 12 13 14 15 ... 28