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

кеңейтілген Хэмминг кодтары

жүктеу 1,27 Mb.

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

1 ... 14 15 16 17 18 19 20 21 ... 28

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

кеңейтілген Хэмминг кодтары. Хэмминг кодтарының өте пайдалы кеңейтілуін қарастырамыз. Бұл код векторларын әр код сөзіндегі бірліктер саны жұп болатындай қосымша екілік битпен толықтырудан тұрады. Паритетті тексерумен Хэмминг кодтары келесі екі артықшылыққа ие.
 Кодтардың ұзындығы -ден -ге дейін ұзартылады, бұл ақпаратты сақтау және беру тұрғысынан ыңғайлы болып табылады.
 Кеңейтілген Хэмминг кодтарының ең аз d_min қашықтығы 3 орнына 4-ке тең, бұл 3 есе қателерді анықтауға мүмкіндік береді.

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

Мысал ретінде кеңейтімді (15,11)-Хэмминг кодын қарастырыңыз. (16,11)-хэмминг кодының әрбір кеңейтілген код векторы (15,11)-кодының код векторынан, жұптылыққа тексерудің қосымша разрядын қосу, арқылы алынады, яғни.

, (11.10)
Мұндағы
. (11.11)
(16,11)-кодының тексеру матрицасы (15,11) Хэмминг кодының тексеру матрицасынан екі әдіспен алынады:
 (15,11)-Хэмминг кодының матрицасына сол жағына нөлдік баған қосамыз;
 алынған матрицаны толығымен бір бірліктен тұратын жолмен толықтырамыз.
Нәтижесінде алатынымыз
. (11.12)

Синдромдық декодтауда

, (11.13)

Бастапқы компонент

. (11.14)
(7.10) және (7.12) ескере отырып
. (11.15)
(11.10) және (11.12)-тен шығатыны s синдромның басқа да компоненттері нөлге тең
Хэмминг кодтарын паритетті тексерумен декодтау туралы айтпас бұрын, әдеттегі Хэмминг кодтарын декодтаудың екі мүмкін режимін еске түсірейік.
1. Қателерді анықтау режимі. Егер синдром болса, онда декодер қате сигналын береді. Hamming кодының d_min =3 болғандықтан, қателері әрқашан анықталады.
2. Қателерді түзету режимі. Егер синдром болса, онда декодер әрқашан кодтық сөз разрядтарының бірін түзетеді (өйткені Хэмминг коды t = 1радиусының тығыз оралған сфералары болып табылады). Осылайша, декодер барлық бірлік қателерді түзетеді.

Жоғарыда айтылғандардан Хэмминг коды 2-ден аспайтын барлық қателіктерді анықтайды немесе барлық қателерді түзетеді.

Енді жұптық тексерумен Хэмминг кодтарына көшейік. Мұндай кодтардың d_min 4 болғандықтан, анықтау режимінде 3 және одан төмен барлық қателер жазылады. Қателерді түзету режимін кодтық сөздерде паритетті тексерудің қосымша категориясының болуына байланысты айтарлықтай жақсартуға болады.
Ең алдымен, тексеру процесін қоспағанда, барлық разрядтардағы жалғыз қателерді түзету процесі әдеттегі Хэмминг кодынан еш айырмашылығы жоқ екенін ескеріңіз. Осылайша, бір қате әрдайым түзетілуі мүмкін. (Бұл жағдайда тексеру разрядтағы бір қатенің белгісі синдромның барлық компоненттерінің нөлге тең болуы, -ден басқасы, ол бірге тең). Екінші жағынан, бір қателікте теңдік әрқашан орындалатынын ескеріңіз . Екі есе қателікпен компонент әрқашан "0" - ге тең болады. Осылайша, біз жетілдірілген Хэмминг кодындағы қателерді түзетудің келесі жетілдірілген алгоритмін аламыз.

1. Егер , онда бір қате түзетіледі
2. Егер және (вектор) болса, онда арнада қате пайда болды және қабылданған сөз өшірілуі керек немесе кері арнаға қайта сұрау сигналы берілуі керек деп санаймыз.
Осылайша, жұптық тексерумен Хэмминг коды тек үшеуден аспайтын қателерді анықтай алады немесе барлық қателерді түзете алады және бір уақытта барлық екі еселік қателерді де анықтай алады.

жүктеу 1,27 Mb.

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

1 ... 14 15 16 17 18 19 20 21 ... 28