Разширен код на Хеминг
Теоретична справка
Кодът на Хеминг с кодово разстояниеdmin= 4 се нарича разширен. Осигурява коригиране на всички единични грешки и откриване на всички двойни и тройни грешки. За целта се въвежда допълнителен контролен битb0, който се добавя към контролната матрица на Хеминг с кодово разстояниеdmin= 3, поради което последното се увеличава с 1.
Допълнителна контролна цифра заема последната колона на идентификационната подматрица на контролната матрица. В допълнение, увеличаването на броя на контролните цифри в комбинацията от кода на Хеминг води до увеличаване на броя на редовете на контролната матрица. Допълнителен ред се получава чрез допълване на колоните на матрицата за проверка за раздвояване.
На практика е по-добре да се използва различен метод за получаване на разширен код на Хеминг. За да направите това, кодовата дума на кода на Hamming просто се допълва с допълнителен контролен елементb0, който се намира чрез проверка на кодовата дума за паритет. В този случай контролният елемент е равен на 1, ако броят на единиците в кодираната кодова комбинация не е сдвоен, и 0, ако е сдвоен.
Декодирайте в обратен ред: първо се извършва обща проверка, а след това проверка без допълнителен елементb0. В този случай могат да възникнат следните опции:
1) няма грешки (и двете проверки дават нулеви синдроми);
2) има единична грешка (обща проверка показва наличието на грешка, а проверка без допълнителен елемент дава синдром, който показва номера на грешния елемент);
3) има двойна грешка (обща проверка показва липсата на грешки, а проверка без допълнителен контролен елемент показва мястото на грешката; но тази грешка не трябва да се коригира, просто трябва да посочите, чекакви грешки 2).
4) има тройна грешка (общата проверка показва наличието на грешка, а синдромът на проверка без допълнителен контролен елемент може да приеме всяка стойност, включително нула).
С оглед на горното, кодовете на Hamming сdmin= 4 се използват като правило за откриване на еднократни, двукратни и тройни грешки.
Кодиране
Кодова комбинация за кодиране:
Първо е необходимо да се кодира комбинацията с обичайния код на Хеминг (с кодово разстояниеdmin= 3), което беше направено в раздел 3.5.3. Получен е следният резултат:
11 11 1101 11111110 01001.
За да получим разширен код на Хеминг, след това извършваме кодиране с проверка на четността, като по този начин разширяваме обикновения код на Хеминг с допълнителен контролен елементb0. Броят на единиците в кодовата дума е 16, следователно битът за проверка е 0, тъй като тогава броят на единиците в кодираната кодова дума ще бъде четен. Добавяме допълнителна контролна цифра и получаваме кодираното съобщение:
1111110111111110010010.
Декодиране
Да предположим, че е възникнала грешка в 13-ия бит по време на предаването на кодираното съобщение и декодерът е получил следната изкривена кодова комбинация:
1111110111110 110010010.
Първо, нека декодираме кода с проверка на четността. Сумата от единици в получената дума е 15, т.е. числото е нечетно, което показва наличието на грешка. Тъй като разширеният код на Hamming позволява да се коригират само единични грешки, приемаме, че възникналата грешка е единична и я коригираме. Изхвърляме допълнителната контролна цифра и получаваме кодовата комбинацияобичайният код на Хеминг, който има една грешка:
След това извършваме декодирането на обичайния код на Hamming. За да направим това, за дадена кодова комбинация изчисляваме синдрома на грешка, като използваме системата, получена в раздел 3.5.3. от матрицата за проверкаH21,16:
Следователно синдромът изглежда така:
Полученият резултат показва, че е допусната грешка в 13-ия бит на получената кодова комбинация.
Обръщаме изкривения 13-ти бит, отхвърляме проверките 1-ви, 2-ри, 4-ми, 8-ми и 16-ти битове и получаваме декодираното съобщение с коригираната грешка:
Итеративен код
Теоретична справка
За предаване на информация широко се използват итеративни кодове с висока способност за откриване. При определяне на контролните елементиq-итеративни кодове, елементите на кодовите комбинации на базовия код се добавят по модулq. Откриването на грешки се извършва по аналогия с двоичния код - чрез сравняване на контролните елементи на всеки ред (колона), получени от канала и получени от приемащата страна чрез изчисление.
Корекцията на изкривения елемент се извършва по следния начин. Ако проверката не е извършена заi-тия ред иj-та колона, тогава елементът, разположен в пресечната точка наi-ия ред иj-та колона, се заменя с елемента, изчислен чрез добавяне на този получен елемент (грешен) със стойността, получена чрез изваждане на стойностите, получени от канала и изчислени от приемащата страна на контролните елементиi-ти ред (илиj-та колона).
Кодиране
Кодова комбинация за кодиране:
11101111 11101001 11110111.
Необходимо е да разбием нашата кодова комбинация на блокове като тозитака че матрицата, чиито редове представляват тези блокове, да е възможно най-близо до квадрата - тогава броят на контролните цифри ще бъде най-малък. Следователно нашата 24-битова комбинация трябва да бъде разделена на блокове от 6 бита (6x4 = 24):
111011 111110 100111 110111.
Изграждаме матрица от тези 4 блока и изчисляваме контролните символи, като добавяме елементите на редовете и колоните на матрицата по модул 2, тоест кодираме редовете и колоните с код с проверка на четността.