Разстояние между кодовите думи. Описание на алгоритъма на HEngine за статична задача

Страница 1

Разстояние на Хеминг между две последователности еднаква дължинасъответства на броя на позициите, заети от несъвпадащи елементи. В случай на последователности с различни дължини, разстоянието на Хеминг се определя като минималния брой позиции, заети от несъвпадащи елементи при.

Разстояние на Хеминг d(u,v) между две думи u и v същата дължинаравен на броя на несъответстващите цифри на тези думи. Използва се в теорията на блоковите кодове (V.

Използвайки метричните свойства на разстоянието на Хеминг, директно се проверява, че /l е метрика на Xt, но не е метрика на набор от смесено-периодични последователности.

Тази функция за близост е еквивалентна на разстоянието на Хеминг.

Метриката p в алгоритъма KLOP се определя от разстоянието на Хеминг.

Ако процедурата за търсене може да намери позиция, където разстоянието на Хеминг е нула, проблемът ще бъде решен.

Сравнението на размитите подмножества B и B3, степените на размиване, както и разстоянието на Хеминг показва, че разглежданите размити подмножества са различни. Въпреки това, ако вземем като изчислена стойност елемента m2 G Uz, чиято степен на принадлежност към полученото размито подмножество е максимална, тогава използването на размитата връзка R, изчислена по този начин, може да бъде оправдана. Наред с факта, че с този подход е възможно да се опише нелинейността на връзката между максималната температура във втората зона на реактора и дебита на полиетиленовата стопилка, този метод не отчита нестационарния характер на процес на получаване на LDPE, който е свързан с промени в характеристиките на технологичния процес.

Трансферната функция на този код показва, че има единственият начинс разстояние на Хеминг d - от пътя на всички нули, който се слива с пътя на всички нули в даден възел. От диаграмата на състоянието, показана на фиг. 8.2.6, или диаграмата на решетка, показана на фиг. 8.2.5, ясно е, че пътят от d6 е acbe. Отново от диаграмата на състоянието или решетката виждаме, че тези пътища са acdbe и acbcbe. Третият член в (8.1.2) показва, че има четири пътя с разстояние d 0 и така нататък. по този начин трансферна функцияни дава свойствата на разстоянието на конволюционен код.

Този резултат е в съответствие с наблюдението, че пътека от всички нули (/0) има разстояние на Хеминг d3 от получената последователност, докато пътека от /1 има разстояние на Хеминг d5 от получената пътека. По този начин разстоянието на Хеминг е еквивалентна метрика за декодиране на твърди решения.

На набор от двоични думи с дължина m разстоянието d(a,b) между думите a и b е броят на несъвпадащите позиции на тези думи, например: разстоянието между думите a = 01101 и b = 00111 е 2.

Понятието, дефинирано по този начин, се нарича разстояние на Хеминг.

Той отговаря на следните аксиоми за разстояние:

1) d(a,b)  0 и d(a,b)=0 тогава и само ако a = b;

2) d(a,b) = d(b,a) ;

3) d(a,b) + d(b,c)  d(a,c) (неравенство на триъгълник).

Теглото w(a) на дума a е броят единици сред нейните координати. Тогава разстоянието между думите a и b е теглото на тяхната сума a b: d(a,b)=w(a b) , където символът  обозначава операцията на покоординатно събиране по модул 2. Интуитивно е ясно, че кодът е по-подходящ за откриване и коригиране на грешки, колкото по-различни са кодовите думи. Концепцията за разстоянието на Хеминг ни позволява да изясним това.

ТеоремаЗа да може един код да открие грешки в k (или по-малко) позиции, е необходимо и достатъчно най-малкото разстояние между кодовите думи да бъде  k + 1.

Доказателството на тази теорема е подобно на доказателството на следното твърдение.

Теорема.За да може кодът да коригира всички грешки в k (или по-малко) позиции, е необходимо и достатъчно най-малкото разстояние между кодовите думи да бъде  2k + 1.

32. Теорема за коригиращата способност на кодовете.

Кодовете, които могат автоматично да коригират грешки, се наричат самокоригиращи се. За да се създаде самокоригиращ се код, предназначен да коригира единични грешки, една контролна цифра не е достатъчна. Както може да се види от това, което следва, броят на контролните битове k трябва да бъде избран така, че да е изпълнено неравенството 2k≥k+m+1 или k≥log2(k+m+1), където m е броят на основните двоични битове на кодовата дума. Понастоящем най-голям интерес представляват кодовете за коригиране на двоични блокове. Когато се използват такива кодове, информацията се предава под формата на блокове с еднаква дължина и всеки блок се кодира и декодира независимо един от друг. В почти всички блокови кодове знаците могат да бъдат разделени на информационни и верификационни.

Основните характеристики на самокоригиращите се кодове са:

1. Брой разрешени и забранени комбинации. Ако n е броят на символите в блока, r е броят на символите за проверка в блока, k е броят на информационните символи, тогава 2n е броят на възможните кодови комбинации, 2k е броят на разрешените кодови комбинации, 2n −2k е броят на забранените комбинации.

2. Излишък на кода. Стойността rn се нарича излишък на коригиращия код.

3. Минимално кодово разстояние. Минималното кодово разстояние d е минималният брой изкривени символи, необходими за преминаване от една разрешена комбинация към друга.

4. Брой открити и коригирани грешки. Ако g е броят на грешките, които кодът може да коригира, тогава е необходимо и достатъчно d≥2g+1

5. Коригиращи възможности на кодовете.

33. Матрично кодиране. Групови кодове.

При изрично указване на схемата за кодиране в ( m, n)-кодът трябва да указва 2 m кодови думи, което е много неефективно.

Един икономичен начин за описване на кодираща схема е техниката на матрично кодиране.

Преди това всяка схема на кодиране беше описана чрез таблици, определящи кодова дума с дължина п за всяка изходна дума с дължина м. За дълги блокове този метод изисква голямо количество памет и следователно е непрактичен. Например за ( 16, 33 ) кодът ще изисква 33 * 2 16 = 2 162 688 бита.

Изисква много по-малко памет матрично кодиране. Нека д размерна матрица m×n, състоящ се от елементи e ij , където аз е номерът на реда и й - номер на колона. Всеки от елементите на матрицата д ij може да бъде 0 или 1. Кодирането се изпълнява от операцията b = aE или където кодовите думи се разглеждат като вектори, т.е. като редови матрици с размер 1×n.

Кодирането не трябва да присвоява една и съща кодова дума на различни съобщения източник. Лесен начин да постигнете това е да м матрични колони формира единична матрица. Когато който и да е вектор се умножи по матрицата на идентичност, се получава един и същи вектор;

Матричните кодове също се наричат линейни кодове. За линеен (n − r, n)-кодове с минимално разстояние на Хеминг d съществува Долна граница на Плоткин (Плоткин) за минимално количествоконтролни битове rпри n³ 2d − 1,

двоичен (Код m, n) се нарича групов код, ако неговите кодови думи образуват група.

Обърнете внимание, че множеството от всички двоични думи с дължина m образува комутативна група с операцията на покоординатно събиране по модул 2, в която важи отношението a a. Следователно наборът от думи за съобщения a с дължина m е комутативна група.

Извиква се блоков код група, ако неговите кодови думи образуват група.

Ако кодът е групов код, тогава най-малкото разстояние между две кодови думи е най-малко теглоненулева дума.

Това следва от релацията d(b аз , б й ) = w(b аз + b й ).

Когато използвате код със заместващ знак, онези и само онези грешки, които съответстват на низове за грешки, точно равни на кодовите думи, остават неоткрити.

Такива редове за грешки превеждат една кодова дума в друга.

Следователно вероятността грешката да остане неоткрита е равна на сумата от вероятностите на всички низове за грешки, равни на кодови думи.

Набор от всички двоични думи а = а 1 ... а м дължина мобразува абелева (комутативна) група по отношение на побитово събиране.

Нека д - кодиране m×n-матрица, която има м × м-подматрица с ненулева детерминанта, например идентичност. След това картографирането a → a Eпревежда група от всички двоични думи с дължина м към група от кодови думи с дължина п.

Нека приемем, че Тогава за получаваме

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

Свойство на груповия код: минималното кодово разстояние между кодовите вектори е равно на минималното тегло на ненулевите вектори. Теглото на кодовия вектор е равно на броя единици в кодовата комбинация.

Удобно е груповите кодове да се задават с помощта на матрици, чиято размерност се определя от параметрите k и n. Броят на редовете е k, а броят на колоните е n = k+m.

Кодовете, генерирани от тези матрици, се наричат (n, k)-кодове, а съответните матрици се наричат генератори (генератори).

Разстояние на Хеминг

Американският математик Хеминг изследва какво определя този коддали ще открие грешки и кога може да ги коригира. Интуитивно е ясно, че това зависи от това как кодовите думи са разделени една от друга и колко грешки могат да се появят в предадена дума. Сега ще формализираме следната идея. Когато кодирате, трябва да се съгласите с номера възможни грешкив предадената кодова дума, така че когато предадената кодова дума се промени, тя остава по-близо до оригиналната кодова дума, отколкото до всяка друга кодова дума.

Определение 13.1.Помислете за набора от всички двоични думи в азбуката IN= (0,1) дължина Тразстояние d(х, при), което е равно на броя на несъвпадащите позиции на тези думи. Например За думи X = 011101, при= 101010 разстоянието е d(х, г) = 5. Това разстояние се нарича Разстояние на Хеминг .

Може да се покаже, че разстоянието на Хеминг удовлетворява аксиомите на метричното пространство:

1) d(х, при) ≥ 0, d(х, при) = 0 ако и само ако X = y;

2) d(х, г) = d(г, х);

3) d(х, при) ≤ d(х, z) + d(z, при) - неравенство на триъгълник.

Теорема 13.1(относно кода за откриване). Кодът се открива в случай, че предаваната дума съдържа не повече от к

d(b 1, b 2) ≥ к+ 1.

Теорема 13.2(относно кода за корекция.). Кодът коригира всички грешки в случай, че предадената дума съдържа не повече от кгрешки, ако и само ако най-малкото разстояние между кодовите думи

d(b 1, b 2) ≥ 2к+ 1.

Доказателство. Доказателствата на тези теореми са подобни. Затова ще докажем само последната теорема.

Адекватност. Нека за всички кодови думи, които имаме d(b 1, b 2) ≥ 2к+ 1. Ако при предаване на кодова дума b 1 не се случи повече кгрешки, тогава за приетата дума с имаме d(b 1, c) ≤ к. Но от неравенството на триъгълника за всяка друга кодова дума b 2 имаме d(b 1, с) + d(c, b 2) ≥ d(b 1, b 2) ≥ 2 к+ 1. Следователно от получената дума до всяка друга кодова дума разстоянието е d(c, b 2) ≥ k + 1, т.е. повече от преди b 1. Следователно според приетото слово сопределено можете да намерите най-близката кодова дума b 1 и след това го декодирайте.

Необходимост. От обратното. Да приемем, че минималното разстояние между кодовите думи е по-малко от 2 к+ 1. След това има две кодови думи, разстоянието между тях ще бъде d(b 1, b 2) ≤ 2 к. Нека при предаване на думата b 1 приета дума ссе намира между думите b 1, b 2i има точно кгрешки. Тогава d(c, b 1) = к, d (c, b 2) = d(b 1, b 2) – d(c, b 1) ≤ к. По този начин от думата c е невъзможно недвусмислено да се реконструира кодовата дума, която е била предадена, b 1или b 2. Стигнахме до противоречие.

Пример 13.3 . Разгледайте следните петбитови кодове за думи с дължина 2 в азбуката IN = {0,1}:

b 1= К(00) = 00000, b 2= К(01) = 01011,

b 3= К(10) = 10101, b 4= к(11) =11110.

Минималното разстояние между различните кодови думи е d(би, bj) = 3. По силата на първата теорема за кода за откриване, този код е в състояние да открие не повече от две грешки в една дума. По силата на втората теорема кодът може да коригира най-много една грешка в дума.

Групови кодове

Нека разгледаме по-подробно кодовете на думите в азбуката IN= (0, 1). Ако за думи с дължина Тизползват се кодови думи с дължина п, тогава ще наричаме такива кодове ( Т , п)-кодове. Обща дължина на думите ме равно на 2 м. За да зададете ( Т , п)-код, можете да изброите кодови думи за всички възможни думидължина м, както в предишния пример. По-икономичен начин за определяне на кодови думи е матрична задача.

В този случай се посочва генериращата матрица Ж= ∣∣ гиж∣∣ поръчка Т × пот 0 и 1. Кодовите думи се определят всеки път по дума А = А 1а 2... причрез умножаване на тази дума отляво, като вектор, по генериращата матрица

Тук събирането е дефинирано по модул 2. За да различни думисъответстват различни кодови думи, достатъчно е да има в матрицата Жединична основа второстепенна от порядъка Т, например най-лявата.

Пример 13.4 . Помислете за генериращата матрица

Тази матрица дефинира кода (3, 4). В този случай първите три знака в кодовата дума са информационни, а четвъртият е контролен. Равно е на 0, ако четно числоединици в оригиналната дума и 1 ако нечетно числоединици. Например за думата А= 101 код ще бъде b= aG= 1010. Минималното разстояние на Хеминг между кодовите думи е d(би, bj) = 2. Следователно това е код, който открива еднократна грешка.

Определение 13.2.Кодът се нарича група , ако наборът от всички кодови думи образува група. Броят на единиците в думата а се нарича везнидуми и се обозначава Ако b- кодова дума и дума, получена в комуникационния канал с = b + e, след това думата днаречен вектор на грешките .

Теорема 13.3.Нека има група ( Т , п)-код. След това комутативната група ДОна всички кодови думи е подгрупа на комутативната група СЪСвсички думи с дължина п, които могат да бъдат получени в комуникационния канал. Най-малкото разстояние между кодовите думи е равно на най-малкото тегло на ненулева кодова дума и

Помислете за факторната група S/K. Косетите тук ще се определят от смяната e + b, b∈ К.

Като представител на класа coset избираме елемента с най-малко тегло. Ние ще наричаме такива елементи ръководители на съседни класове .

Ако лидерите се интерпретират като вектори на грешка, тогава всеки съседен клас е набор от изкривени думи в комуникационен канал с фиксиран вектор на грешка, по-специално когато д= 0 имаме съседен клас думи без изкривявания, т.е. множеството от всички кодови думи. Процесът на коригиране и декодиране на думи ссе състои в търсене на съседния клас, към който принадлежи думата с = д + b. Вектор на грешката допределя броя и местоположението на грешките, кодова дума bопределя корекцията на получената дума.

За да се улесни търсенето на coset и по този начин на вектора на грешката, Хеминг предложи използването на групови кодове със специални генериращи матрици.

Кодове на Хеминг

Нека разгледаме конструкцията на Hamming ( Т , п)-код с най-малко тегло на кодовата дума, равно на 3, т.е. код, който коригира една грешка.

Да сложим п = 2 r– 1 и нека всяка кодова дума съдържа rконтролни знаци и Тгерои ( Т = п – r= 2 r– 1– r) - информационен, r≥ 2, например (1, 3) код, (4, 7) код и т.н. Освен това във всяка кодова дума b= b 1b 2... b pсимволи с индекси, равни степени 2 ще бъдат контролни, а останалите ще бъдат информационни. Например за код (4, 7) в кодовата дума b= b 1b 2b 3b 4b 5b 6b 7 знака b 1b 2b 4 ще бъдат контролни, а символите b 3b 5b 6b 7- информационен. Да се уточни генераторната матрица Жна Хеминг ( Т , п)-код, помислете спомагателна матрица Мред r× п, Къде п = 2 r– 1, така че във всяка йматрична колона Мще има двоични символи й, например, за (4, 7) кодирайте матрицата Мще бъде 3 × 7:

Дефинираме набора от всички кодови думи като набор от решения хомогенна системалинеен алгебрични уравнениявид

b MT= 0.

Например за (4, 7) код такава система би била:

Нека изберем естествен базисен минор на системата b MT= 0, стоящи в колони с числа, равни на степен 2. Така разделяме променливите на основни (код) и безплатни (информация). Сега, след дефиниране на свободни променливи, е лесно да се получат основни. Нека намерим фундаменталната система м= п – rрешения на тази хомогенна система. Тогава всяко решение на системата е линейна комбинация от тях мрешения. Следователно, изписване ред по ред мрешения на фундаменталната система под формата на матрица Жразмер м× п, получаваме генериращата матрица на групата на Хеминг ( Т , п)-код, например за (4, 7)-код фундаментална системарешения ще има 4 = 7 – 3 следните решения на хомогенна система:

ж 1= 1110000, ж 2= 1001100, ж 3= 0101010, ж 4= 1101001.

Всяка линейна комбинация от тези решения ще бъде решение, т.е. кодова дума. Нека съставим генерираща матрица от тези фундаментални решения

Сега според всяка дума Адължина Т= 4 лесни за изчисляване кодови думи bдължина п= 7 с помощта на генераторната матрица b= aG. В същото време символите b 3, b 5, b 6, b 7 ще има информативен характер. Те съвпадат с А 1, А 1, А 3, А 4.Символи b 1, b 2, b 4 ще бъде контролен.

Заключение. Кодовете на Хеминг са удобни, тъй като косетите се определят лесно по време на декодиране. Нека думата, получена по комуникационния канал, бъде с = д + b, Къде д- грешка, b- кодова дума. След това го умножете по спомагателната матрица cMT= (д + b)MT= eM T. Ако eM T= 0, след това думата с- код и считаме: няма грешка. Ако eM T≠ 0, след това думата допределя грешка.

Припомнете си, че конструираният Hammings ( Т , п)-код идентифицира една грешка. Следователно векторът на грешката дсъдържа една единица в азпозиции. Освен това броят азпозиция се получава в двоично представяне като резултат eM T, съвпадаща с азматрична колона М. Остава да сменим символа азв думата c, получена по канала, зачеркнете контролните знаци и запишете декодираната дума.

Например, нека приетата дума да бъде с= 1100011 за (4, 7) кода на Хеминг. Нека умножим тази дума по матрицата М Т. получаваме

(1100011) М Т=(010).

Следователно има грешка във втория знак. Следователно кодовата дума ще бъде b= 1000011. Задраскайте контролните знаци b 1, b 2, b 4. Декодираната дума ще бъде А = 0011.

Разбира се, ако грешката е направена в повече от един знак, този код няма да я коригира.

) В векторно пространствокодови последователности, в този случай разстоянието на Хеминг между две двоични последователности (вектори) и дължина е броят на позициите, в които те са различни - в тази формулировка разстоянието на Хеминг е включено в Речника на алгоритмите и структурите на данни Национален институтСтандарти на САЩ ( английски Речник на NIST за алгоритми и структури от данни ).

Така разстоянието на Хеминг между векторите 0 011 1 и 1 010 1 е равно на 2 (разликите са маркирани в червено битове). Впоследствие метриката беше обобщена до q-ични последователности: за двойка низове „избори“ и „ограда“ разстоянието на Хеминг е равно на три.

IN общ изгледРазстоянието на Хеминг за обекти и размери се дава от функцията:

Разстоянието на Хеминг има свойствата на метрика, отговаряща на следните условия:

Разстояние на Хеминг в биоинформатикаи геномика

Литература

Ричард У. Хеминг. Кодове за откриване и коригиране на грешки, Bell System Technical Journal 29(2):147-160, 1950 г.
Ричард Блейхут. Теория и практика на кодовете за контрол на грешки. М., "Мир", 1986 г

Връзки

Ричард Хеминг и началото на теорията на кодирането // Виртуален компютърен музей

Фондация Уикимедия.

2010 г.

Разстояние на ХемингВижте какво е „разстояние на Хеминг“ в други речници: - Разстояние на Хеминг Разстояние d (u,v) между две кодови последователности u и v с еднаква дължина,равно на числото

знаци, по които се различават. Блок код с минимално разстояние на Хеминг d позволява да се открие (d 1) и... ...кодово разстояние - Минимално разстояние на Хеминг, поето за всички лари от различни кодови думи в единен код. [Сборник с препоръчителни термини. Брой 94. Теория на предаването на информация. Академия на науките на СССР. Комитет по техническа терминология. 1979] Теория на темите... ...

Ръководство за технически преводач В областта на математиката и теорията на информацията линеен код еважен тип

блоков код, използван във вериги за откриване и коригиране на грешки. Линейните кодове, в сравнение с други кодове, позволяват прилагането на по-ефективни алгоритми... ... Wikipedia

Откриването на грешки в комуникационната технология е действие, насочено към наблюдение на целостта на данните при запис/възпроизвеждане на информация или при предаването й по комуникационни линии. Процедура за възстановяване на корекция на грешка (корекция на грешка)... ... Wikipedia

Откриването на грешки в комуникационната технология е действие, насочено към наблюдение на целостта на данните при запис/възпроизвеждане на информация или при предаването й по комуникационни линии. Процедура за коригиране на грешки (коригиране на грешки) за възстановяване на информация след... ... Wikipedia