3.10. Хеминг код

Един от най-честите системни кодове е код на Хеминг [132].

Те обикновено включват кодове с минимално разстояние коригиране на всички единични грешки и кодове с разстояние коригиране на всички единични и откриване на всички двойни грешки. Дължината на кода на Хеминг

(R - брой битове за четност). От това неравенство получаваме

Формула (3.29) може да се редуцира до следната форма:

където броят на бита данни. Това неравенство дава възможност да се определи дължината на кода за даден брой битове за данни. Таблица. Фигура 21 показва характеристиките на някои от кодовете на Хеминг.

Таблица 21 (виж фиг. Scan)

.. Характерна особеност на проверка код матрица е, че колони са комбинация от различни не-нулева дължина, например, когато m е, за кода (15,11), матрицата за проверка на четността може да има следната форма:

пермутиране колони, съдържащи една единица, тази матрица може да се намали до формата

Използването на този код може да се коригира всеки единствена грешка или грешка откриване на произволно множество две.

Ако информацията и проверка на кодови бита, номерирани от ляво на дясно, в съответствие с матрицата получаваме система от уравнения за проверка, чрез която да се изчисли нивото на подбор:

където "ниво скрининг; бита данни.

В случая, когато настъпи предаване кодова дума единична грешка, проверка ще бъде неизпълнени тези съотношения, които включват стойността на погрешно отговорност. Например, ако възникне грешка в петата бита данни ще бъде невъзможно първия и четвъртия уравнение, т. Е. синдром е 1001 (идентичен на петата колона на матрицата Н). Следователно ние получаваме алгоритмите определят местоположението на единична грешка: местоположение колона на матрицата, която съвпада с изчисленото синдром показва местоположението на грешката. Ясно е, че изчислената стойност на синдром задължително равно на една от колоните на матрицата, тъй като всички избрани колони като възможни-битови двоични числа.

Hamming предложено да се използва такова подреждане на колоните на матрицата за проверка на номер матрица колона и номера на кодова дума ранг съответства на двоичното представяне на броя в този случай, синдром получен от проверка за четност уравнения, е двоичен комбинации газоразрядни брой представяне в която е настъпила грешка. За това ниво скрининг не трябва да бъде в края на кодовата дума, както и номера на позицията, която може да бъде изразена като на два, така че всеки от тях се появява само в един от проверка за четност уравнения.

Пример. В следната матрица могат да бъдат избрани за проверка като:

Както битовете за контрол изберете първия, втория и четвъртия. За да кодирате съобщение в 1101, е необходимо да се определи нивото на инспекция в комбинацията от матрицата са

Следователно, кодиран съобщението има формата 1010101. приемем, че шестият символ приет с грешка, тогава съобщението е получено 1010111. синдром в този случай има форма. Е. двоичното представяне на 6.

Binary Hamming код с дължина на код, получен чрез добавяне на кода на Хеминг с една контролна цифра, която е резултат от сумиране по модул два бита на код слой. Дължината на код в този цифри от които са на чека.

операция за кодиране може да се извърши на два етапа. В първия етап матрица кодова дума се използва код I, съответстващо на втория - тест освобождаване добавен в една, в която се записва резултат от сумиране по модул два бита на кодовата дума, получена в първия етап.

операция декодиране включва също -dvuh етапа. В първия изчисленото синдром кода, съответстващ на втората - продължи тя проверява чрез съотношение на проверка. Резултатите от тези операции и техните заключения са показани в таблица. 22

Таблица 22 (виж фиг. Scan)

-code за матрицата за проверка паритет може да има форма

връзка Допълнителна проверка се прилага за увеличаване на минималната Хеминг разстояние на кода, представена по следния начин: Като се има предвид (3.31), получаваме

Системата от уравнения (3.31) и съотношението на последния, можете да записвате в квадратчето матрица за кода (16, 11):

Понякога, в практическото използване на кода отговаря на проблема с получаването на съкратен код с предварително определена минимална дистанция, или 4). В този случай, проверка матрица за neukorochennogo код с най-малката стойност отговаря на следните условия:

Във втория случай, броят на проверка бита равни на кода в получената матрица след това се отстраняват всички излишни колони подматрици

Пример. Construct проверка матрица за Хеминг код като информационни бита. Най-малката стойност, която отговаря на неравенството (3.34) е равно на 4.

дължина код е 16. Матрицата за този код е дадено в (3.32) в подматрица включващ и освобождава пресичат от последната колона за икономии хардуер (обикновено колони се заличават от най-голям брой ediints).

съкратен код за проверка на матрица (15, 10) в този случай има формата

При използване на таблицата. 21 много просто определят, за които на neukorochennyh кодове Hemmiiga необходими за изграждане на проверка матрица, в която за изграждане на паритет проверка матрица на съкратен код. Например, за да се изгради проверка матрица за код с т. Е. код (63, 57), и след това се заличава от колони подматрица двадесет и седем.

Тегло характеристики на кода на Хеминг е удобно да се намери функция за определяне на броя на кодовите вектори с различни тегла 193].

Във формули (3.35), (3.36) брой кодови вектори с тежести, равна на стойността на коефициентите обърната

Пример. Да предположим, че даден Хеминг код за определяне на размера на фалшиви преходи. За този код съгласно формула (3.35), имаме

Ето защо, този код съдържа една кодова дума тегло около седем думи на тегло 3, 4 седем тегло думи и една дума на тегло 7. Това означава, че разпределението на работните вектори за код разстояние на кода е както следва! Коефициентите на фалшиви реализации

Затова UGTT код открива всички едно-, дву-, пет-, шест грешки, 80% от тройни и четворни.