Дәріс 10
Хемминг коды
Шуға қарсы кодттау қатарын құру және өңдеу кезінде қабылданатын кодттардың комбинацияларының жұптарына әр-түрлі әдіспен жүргізуді тексеру. 50-ші жылдардың басында Хемминг бақылау символдары кодттық комбинацияда өз еркімен емес, декодттауды жеңілдетуде қатаң анықталған орындарда орнатылсын деп ұсынды.
Хемминг кодының екі моделі кеңінен таралған: жалғыз қатені тауып түзету коды (минималды кодттық қашықтық d = 3) және екілікті табу (d = 4).
Хемминг кодын синтездеу үшін келесі тапсырмаларды шешу қажет:
Шуға қарсы қорғаныс бойынша берілген талаптарды қамтамасыз ететін, бақылаушы символдар санын анықтау.
Кодттық макет комбинациясын жинап, әр-бір бақылаушы символ шамасын анықтау
Бақылаушы сияқты ақпаратты символдарды да қосатын кодттық комбинацияны құру
Қате бар екенін және орынын анықтайтын тексеруші алгоритмін беру.
d = 3 кодының ситезі
Мұндай берілгендерде ереже бойынша ақпараттық символдар саны nи болып табылады, өз кезегінде  хабарлама жиынымен анықталады. Кей кездерде кодттық комбинациядағы n жалпы саныдық символмен беріледі.
Бірінші тапсырма.
nк бақылаушы символдар санын анықта.
Ол үшін, егер n немесе nи берілсе, сйәкес теңдеуін пайдалану қажет
 (1)
 , (2)
мұндағы ] b [-таңбасы жақын бүтін үлкенсанға дейінгі жуықтау таңбасы.
Екінші есеп.
Жалпы кодттық комбинацияда осы бақылаушы разрядттар орналасу керек, солардың орынын анықтау.
Бақылаушы символдар екілік санды құру қажет (қате синдромы), қателік позиция номерін көрсететін.
Нәтижесінде жұптылықта бірінші жеке тексеруде синдромның бірінші разрядтты (кіші) символын алады, ал екінші тексеруде-екінші символ және т.б.
Егер қате синдромын екілік төрт шамалы сан түрінде келтірілсе және қасына сәйкес келетін ондық эквивалентін жазса, онда 1 кестені аламыз
Кесте 1
Ондық
эквив-т
|
қате сндромы
|
1
2
3
4
5
6
7
8
9
|
0001
0010
0011
0100
0101
0110
0111
1000
1001
|
Кесте түрінде тізбектей позиция номерін жазамыз, жұп санға әр тексеру кезінде қатысқан.
Бірінші тексеруде кіші разрядтағы бірліктен тұратын позициялар қатысуы қажет. 1 кесте бойынша, ол 1, 3, 5, 9, .... .
Екінші тексеруде екінші разрядтағы бірліктен тұратын позициялар қатысуы тиіс. 1 кесте бойынша бұл 2, 3, 6, 7, .... .
Үшінші тексеруде 4, 5, 6, 7, .... позициялар қатысуы қажет.
Нәтижесінде 2 кестені аламыз
Кесте 2
Тексеру нометі
|
Осы тексеруді қамтитын поз-я номері
|
Бірінші
|
1
|
3
|
5
|
7
|
9
|
Екінші
|
2
|
3
|
6
|
7
|
|
Үшінші
|
4
|
5
|
6
|
7
|
|
Екінші кестені талдай отырып мынаны қорытындылауға болады, бақылаушы символдар Кm келесі позицияларға орналастырылуы тиіс: 1 позицияларына К1 , яғни 20;
2 позициясына К2, яғни 21; 4 позициясына К3, яғни 22; 8 позициясына К4, яғни 23; 2m позициясына Кm.
Үшінші тапсырма.
Бақылаушы символдар шамасын анықта. Хемминг кодының макеті құрылады. nи =4, nк = 3, n = 7 болсын. Онда жалпы түрде ол келесідей болады.
Позиция номері 1 2 3 4 5 6 7
Символдар К1 К2 И3 К3 И2 И1 И0 ,
Мұндағы Иi- ақпараттық символдар
Бақылаушы символдарды анықтау алгоритмі
К1 шамасын анықтау. Барлық символдардың 2 модулі бойынша қосындысы құралады, 1, 3, 5, 7, 9, ... , позицияларына орналасқан К1 бірге, бірінші тексеруден қамтығандыа, яғни
К1 И3 И2 И0. (3)
К1 символының шамасы (3) нольге орындағаннан кейін анықталады, жұп шартынан. Егер бірлік саны (К1 сіз) тақ болса, онда К1=1, егер жұп болса онда К1=0.
К2 шамасын анықтау. Барлық символдардың 2 модулі бойынша қосындысы құралады және К1 қоса, екінші тексеруді қамтитын, яғни
К2 И3 И1 И0. (4)
К2 символының шамасы (4) нольге орындағаннан кейін анықталады, жұп шартынан. Егер бірлік саны (К1 сіз) тақ болса, онда К1=1, егер жұп болса онда К1=0.
К3 шамасын анықтау. Үшінші тексеруді қамтитын, барлық символдардың 2 модулі бойынша қосындысы құралады және К3 бірге, яғни
К3 И2 И1 И0. (5)
К3 символы (5) екілік сумма ноліне тәуелді.
Сол сияқты К4, К5 және басқада символдар анықталады, бірақ ол үшін төртінші, бесінші және басқа да тексерулер және сәйкес қосындыларды құру.
Төртінші тапсырма.
Кодттық комбинацияны құру. Ол үшін екілік кодттағы барлық комбинацияларды жазу қажет және кодттық макет сөз макетін пайдалану, сонымен қатар негізгі суммалар (3), (4), (5) негізінде есептелген және бақылаушы символдар шамасын Кm, Хемминг кодының барлық nи комбинациясын жазу.
Бесінші тапсырмада – тексеру алгоритімін өңдеу, онда төмендегідей қарастырылады, Хемминг кодына қатынасты болғандықтан.
Хемминг кодын синтездеу мысалын қарастырамыз.
16 хабарламадан тұратын ансамбль болсын және оны Хемминг кодымен кодттау қажет (d = 3).
Шешуі:
1) бақылаушы символдар санын анықтаймыз. Ансамбль хабарламасы берілгендіктен Nи = 16, онда ақпараттық символдар саны берілсін nи=lb16=4. Ізінше теңдеуді пайдалану қажет
Осы түрде, nк = 3, n = nи + nк = 4 + 3 = 7.
1) үш бақылаушы символ орналасатын, позицияны анықтаймыз. Ол 1, 2, және 4 позициялары (2 кестені қара).
2) артық кодсыз екілік комбинация кестесін құрамыз, бірінші, екінші, төртінші графаларын толтырмаймыз. Барлық комбинация 16 (3 кесте)
3) бақылаушы символдар шамасын анықтаймыз:
нольдік комбинация үшін барлық Кj=0.
Достарыңызбен бөлісу: | 
