Изграждането на Хеминг кодове на базата на паритета проверка на принципа на тегло W (брой единични знака) в информационната група на код блок.
Нека обясним идеята за проверка на паритета на примера на най-простият корекция код, който се нарича код с четност или код за проверка паритет (равенство).
Този код за кодови комбинации bezizbytochnogo първична двоичен м - битов код добавя един допълнителен бит (символ за проверка на четността на нарича проверка или контрол). Ако броят на символите "1" на първоначалната кодова дума е още, допълнителното отговорност генерира пилотен символ 0, и ако броят на символите "1" е странно, след това образуване на символ освобождаване 1. В резултат на това, общият брой на символите "1" в която и предава кодирана дума Той винаги ще бъде още.
Така, обикновено паритет генератор е както следва:
,
където I - съответната информация символ (0 или 1), т - и общия брой по операция "" оттук нататък се отнася до прибавяне на pomod2. Очевидно е, че добавянето на допълнително освобождаване увеличава общия брой възможни комбинации два пъти в сравнение с броя на първоначалните комбинации първичен код и разделя състоянието на четността е разрешена за всички комбинации и нерешен. Код с паритет може да открие една единствена грешка при получаване на кодовата дума, тъй като нарушава грешка паритет, превод допустимо в комбинация забранено.
Към критериите, приети правилната комбинация е равен на нула, S pomod2 vsehn кодовите символи сумиране резултат включително проверка simvolk1. В присъствието на еднократна oshibkiS приема стойността 1:
.
Този код е (m + 1, т) - код или (N, N -1) - код. Минималната код разстояние е равно на две (Dmin = 2), и поради това не могат да бъдат коригирани, без грешки. Прост код с паритет може да се използва само за определяне (но не и корекция) единствена грешка.
Увеличаване на броя на допълнителни битове за четност и формиране съответствие с определени правила, на паритетен к. равна на 0 или 1, могат да бъдат подобрени чрез коригиране на свойствата на кода, така че тя ви позволява не само да се открие, но и поправяне на грешки. Въз основа на това и изграждането на Хеминг кодове.
Хеминг кодове. Помислете за тези кодове могат да се коригира една единствена грешка от пряк описание. За всеки брой на чек simvolovk = 3,4,5 ... има класическа Хеминг код маркирана
т.е. - (7,4) (15,11) (31,26) ...
За други стойности на брой м на информационните символи, получени от така наречените скъсени (скъсени) Hamming кодове. Така че, за международен телеграфен код MTC-2. 5, които имат информация символи трябва да се използват за корекция код (9,5) се скъсява, като класическа код на Хеминг (15,11), тъй като броят на знаците в този код се намалява (съкратено) до 6. Да разгледаме например код на Хеминг (7,4 ), който може да се образува и е описано от енкодера показано на ris.13.1. В най-простата си форма за дадени четири (m = 4) информационни символи (i1, i2, i3, i4), ние приемаме, че те са групирани заедно в началото на кодовата дума, въпреки че не е задължително. Допълнение тези информационни символи са паритета три (к = 3), молба следните уравнения паритет, които се определят чрез подходящи алгоритми. Известно е, че код разстояние, равно на минималния брой проверки, което включва символа информация плюс един. В този kodedmin. Следователно всяка информация символ трябва да включва най-малко две проверки. Ние определяме правилата за формиране на паритета, както следва:
В съответствие с този алгоритъм определяне паритетни стойности за Ki ris.13.3 16 показва всички възможни кодови думи (7,4) - Hamming код.
Фиг. 13.2privedena схема на декодер за (7,4) - Hamming код, на входа на който получава кодовата дума
.
Апострофът означава, че всеки знак на думата може да бъде изкривен пречка в канала на предаване.
В декодера в грешка режим коригиране за конструиране на последователност:
Trohsimvolnaya последователност (s1. S2. S3) се нарича синдром. Терминът "синдром" се използва в медицината, където той представлява комбинация от характеристики, специфични за определена болест. В този случай sindromS = (s1. S2, S3) е комбинация от резултатите от теста за съответните символи за четност и код група характеризира някои грешки конфигурация (векторни грешка).
Ris.13.1. Енкодер за проста (7.4) - Хеминг код
Ris.13.2. Декодер за проста (7,4) - Hamming код
По този начин, кодът (7.4) ви позволява да коригирате всички единични грешки. А просто проверка показва, че всяка грешка има уникален синдром. Възможно е да се осигури такъв цифров коректор на грешката (синдром декодер), която е подходяща синдром коригира съответния символ в получения код група. След като направите корекция паритет Ки достъпен на изход декодер (ris.13.2) да не се оттегля. Две или повече грешки надвишават капацитета на коригиране на Хеминг код и декодер, ще бъде погрешно. Това означава, че е погрешно да се правят корекции и да даде изкривени информационни символи.
Идеята за изграждане на такъв код за коригиране, разбира се, не променя обмен на позиции на символи в кодовите думи. Всички тези възможности са известни също и като (7,4) - Хеминг кодове.
Разширен Hamming кодове са конструирани в резултат на комплемента кодове sdmin = 3 общо проверка на всяка от кодови думи в паритет, т.е. друга контролна цифра. Това увеличава минимално разстояние dodmin = 4.
За да продължите с изтеглянето, което трябва да се съберат на снимка:
Свързани статии