219
ететін бинарлық кодтау және кодсыздандыруды қарастырайық. Ақпаратты
жіберу теориясында әдетте элементтері ақырлы алфавиттен алынған ақырлы
тізбекті символдардан тҧратын хабарламаны жіберу керек. Мысалы, бҧл
алфавит 0 және 1 символдарынан тҧрсын, онда бҧл хабарламаны екілік жҥйеде
жазылған сан ретінде қарастырамыз. Бинарлық коды ҥшін
1
,
0
алфавиті
жеткілікті моделі екілік симметриялы канал деп аталады.
Анықтама [1: 595].
1
2
m
m
ӛлшемді Н тексеруші матрицасы бар,
ҧзындығы
2
,
1
2
m
n
m
тең С
m
бинарлық код Хэмминг бинарлық коды деп
аталады, егер Н матрицасының бағандарын екілік жҥйеде жазылған 1, 2, ... ,
1
2
m
сандары қҧраса.
Хэмминг кодында кодталған сӛздердің ең кіші ара қашықтығы 3-ке тең,
сондықтан ол бір реттік қателерді тҥзейді. Хэмминг коды кемел кодтарға
жатады.
Хэмминг коды ҥшін бір ғана позициядағы қателерді табушы кодының
кодсыздандыру схемасы қарапайым. Хэмминг кодтары класына ҧзындықтары
әртҥрлі кодтар кіреді. Біз тек қана кемел кодтарды қарастырамыз.
Хэмминг кодын қҧру тәртібі мынадай [2: 253]:
1. Бҥтін оң r санын таңдап аламыз. Хабардағы сӛздердің ҧзындығы
r
r
1
2
-ге тең, ал кодталған сӛздер ҧзындығы
1
2
r
-ге тең болады.
2. Әрбір
1
2
2
1
,...,
,
r
b
b
b
b
кодталған сӛзде
1
2
1
0
2
2
2
2
,...,
,
,
r
b
b
b
b
бақылаушы
символдар болады, ал қалғандары – рет-ретімен хабар символдары. Мысалы,
r
=
4
болғанда,
8
4
2
1
,
,
,
b
b
b
b
бақылаушы
символдар,
ал
15
14
13
12
11
10
9
7
6
5
3
,
,
,
,
,
,
,
,
,
,
b
b
b
b
b
b
b
b
b
b
b
хабар символдары.
3.
1
2
r
қатардан r бағаннан тҧратын М матрицасын қҧрамыз. i-інші
бағанда i санының екілік жҥйеде жіктелу символдары тҧрады.
r = 2, 3 және 4 ҥшін М матрицасы тӛмендегідей болады:
1
1
1
1
0
1
1
1
1
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
1
0
0
0
,
1
1
1
0
1
1
1
0
1
0
0
1
1
1
0
0
1
0
1
0
0
,
1
1
0
1
1
0
4
,
15
3
,
7
2
,
3
M
M
M
220
4.
0
bM
теңдеулер жҥйесін жазамыз, мҧндағы М – 3 пунктегі матрица.
Жҥйе r теңдеуден тҧрады: мысалы, r = 3 ҥшін:
0
0
0
7
5
3
1
7
6
3
2
7
6
5
4
b
b
b
b
b
b
b
b
b
b
b
b
5. Сигналды кодтау ҥшін,
i
j
2
ҥшін
j
b
ретінде сәйкес символды аламыз
және жазылған теңдеулер жҥйесінен
i
b
2
-ді табамыз. Осылайша әрбір теңдеуден
бір-бірден
i
b
2
-ді табамыз. Жазылған жҥйеде
4
b
бірінші теңдеуге,
2
b
екінші
теңдеуге,
1
b
ҥшінші теңдеуге кіреді.
Кодталған сӛздің нӛлдік емес ең кіші салмағы бҧл мысалда 3-ке тең.
Кодсыздандыру қиын емес. Келген сӛз
e
b
болсын, мҧндағы
b
жіберілген сӛз.
0
bM
болғандықтан,
eM
eM
bM
M
e
b
. Егер нәтиже нӛлге тең болса, онда
қабылдау барысында қате болмаған. Егер
00
...
1
...
00
e
қателіктер векторының
i-ші позициясында бірлік кездесетін болса, онда оны М матрицасына
кӛбейткенде М матрицасының i-ші бағанында i санының екілік жҥйеде жіктелуі
болады. Онда i-ші позицияда
e
b
сӛзінің символын ӛзгерту керек.
Мысал. (4, 7)-Хэмминг коды бір ғана
0001111
b
кодталған сӛз ретінде
берілсін. М матрицасы мынадай болады:
1
1
1
0
1
1
1
0
1
0
0
1
1
1
0
0
1
0
1
0
0
.
000
bM
аламыз.
b
сӛзіне
0010000
e
қате қатар қосамыз. Онда
0011111
e
b
және
011
M
e
b
. Бҧл – 3 санының екілік жҥйеде жіктелуі, сондықтан қате
ҥшінші позициядан табылады. Егер
0000001
e
болса, онда
111
M
e
b
, ал, бҧл
7 санының екілік жіктелуі, яғни қате жетінші позицияда.
Егер қате бірден артық позицияда кеткен болса, кодсыздандыру қате
нәтиже береді. Мысалы, егер қате қатар кодталған болса, онда
0
M
e
b
және
кодсыздандыру қабылданған сӛзді ӛзгертпейді. Егер қате екінші позицияда
кеткен болса, код бәрібір бірінші позицияда кӛрсетеді.
Бҧл кодқа жҧптылықпен тексеруді қосуға болады. Кодтың ең кіші
салмағы 4-ке тең болады да, сонда код бір позицияда қатені тҥзетуші, екінші
позицияда қатені табуға қабілетті болады.
Хэмминг кодына қатысты екі мысал қҧрастырамыз.
Есеп 1. 1001 0001 1101 1110 0000 000 берілген сӛзді Хэмминг кодымен
кодтау керек.
Шешуі: ҧзындығы m = 23 хабарды кодтау ҥшін, k = 5 қосымша разряд
керек, яғни кодтағанда ҧзындығы n = 28 болатын хабар алуымыз керек
(қосымша разрядтың санын
1
2
n
k
қатынасы арқылы аламыз, мҧндағы n –
алынған разрядтың саны, k – қосымша разрядтың саны).
Достарыңызбен бөлісу: |
