Сторінка 1

Відстань Хеммінгу між двома послідовностями рівної довжинивідповідає числу позицій, зайнятих несхожими елементами. У разі послідовностей різної довжини відстань Хеммінга визначається як мінімальна кількість позицій, зайнятих несхожими елементами при.  

Відстань Хеммінгу d (u, v) між двома словами та і v однакової довжиниодно числу несхожих розрядів цих слів. Воно використовується в теорії блокових кодів (Ст.  

З використанням метричних властивостей відстані Хеммінга безпосередньо перевіряється, що л є метрикою на Хц, але не є метрикою на безлічі змішано-періодичних послідовностей.  

Ця функція близькості еквівалентна відстані Хеммінгу.  

p align="justify"> Метрика р в алгоритмі KLOP задана відстанню Хеммінга.  

Якщо процедура пошуку зможе знайти положення, де відстань Хеммінга дорівнює нулю, завдання буде вирішено.  

Зіставлення нечітких підмножин В і В3, ступенів нечіткості, а також відстані Хеммінга показує, що нечіткі підмножини, що розглядаються, відрізняються. Однак якщо як розраховане значення приймати елемент м2 G Uz, ступінь належності якого отриманому нечіткому підмножині максимальна, то застосування нечіткого відношення R, обчисленого таким способом, може бути виправдане. Поряд з тим, що при даному підході вдається описати нелінійність зв'язку між максимальною температурою в другій зоні реактора та показником плинності розплаву поліетилену, цей спосіб не враховує нестаціонарність процесу одержання ПЕВС, яка пов'язана із зміною характеристик технологічного процесу.  

Передатна функція цього коду вказує на те, що є єдиний шляхз відстанню Хеммінга d - від шляху з одних нулів, який зливається з шляхом з одних нулів при даному вузлі. З діаграми станів, показаної на рис. 8.2.6, або ґратчастої діаграми, показаної на рис. 8.2.5 видно, що шлях з d6 це acbe. Знову з діаграми станів або ґрат ми бачимо, що цими шляхами є acdbe і acbcbe. Третій доданок (8.1.2) вказує, що є чотири шляхи з відстанню d 0 і так далі. Таким чином, передатна функціядає нам дистанційні властивості згорткового коду.  

Цей результат узгоджується зі спостереженням, що шлях з одних нулів (/ 0) має відстань Хеммінгу d3 від послідовності, в той час як шлях з / 1 має відстань Хеммінгу d5 від шляху, що приймається. Таким чином, відстань Хеммінга є еквівалентною метрикою декодування з жорстким рішенням.  

Цей результат узгоджується зі спостереженням, що шлях з одних нулів (/ 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 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 кодових слів, що дуже неефективно.

Одним із економних способів опису схеми кодування є методика матричного кодування.

Раніше кожна схема кодування описувалась таблицями, що задають кодове слово довжини. n для кожного вихідного слова довжини m. Для блоків великої довжини цей спосіб потребує великого обсягу пам'яті і тому непрактичний. Наприклад, для ( 16, 33 )-коду потрібно 33 * 2 16 = 2162688 біт.

Набагато меншого обсягу пам'яті вимагає матричне кодування. Нехай E матриця розмірності m × n, що складається з елементів e ij , де i - це номер рядка, а j - Номер стовпця. Кожен із елементів матриці e ij може бути або 0 або 1. Кодування реалізується операцією b = аЕ або де кодові слова розглядаються як вектори, тобто як матриці-рядки розміру 1 × n.

Кодування не повинно приписувати те саме кодове слово різним вихідним повідомленням. Простий спосіб досягти цього полягає в тому, щоб m стовпців матриці утворювали одиничну матрицю. При множенні будь-якого вектора на одиничну матрицю виходить цей самий вектор, отже, різним векторам-повідомленням будуть відповідати різні вектори систематичного коду.

Матричні коди називають також лінійними кодами. Для лінійних (n - r, n)-кодів з мінімальною відстанню Хеммінга d існує нижня межа Плоткіна (Plotkin) для мінімальної кількостіконтрольних розрядів rпри n³ 2d − 1,

Двійковий ( m, n)-код називається груповим, якщо його кодові слова утворюють групу.

Зауважимо, що множина всіх двійкових слів довжини m утворює комутативну групу з операцією покоординатного складання по модулю 2, в якій виконується співвідношення a a. Отже, множина слів-повідомлень a довжини m є комутативна група.

Блоковий код називається груповим, якщо його кодові слова утворюють групу.

Якщо код є груповим, то найменша відстань між двома кодовими словами дорівнює найменшій вазіненульового слова.

Це випливає із співвідношення d(b i , b j ) = w(b i + b j ).

При використанні групового коду непоміченими залишаються ті й лише помилки, які відповідають рядкам помилок, точно рівним кодовим словам.

Такі рядки помилок переводять одне кодове слово інше.

Отже, ймовірність того, що помилка залишиться невиявленою, дорівнює сумі ймовірностей всіх рядків помилок, рівних кодовим словам.

Безліч всіх двійкових слів a = a 1 ... a m довжини mутворює абелеву (комутативну) групу щодо порозрядного складання.

Нехай E - кодуюча m × n-матриця, яка має m × m-підматриця з відмінним від нуля визначником, наприклад, поодинока. Тоді відображення a → a Eперекладає групу всіх двійкових слів довжини m у групу кодових слів довжини n.

Припустимо, що Тоді для отримуємо

тобто. Отже, взаємно однозначне відображення групи двійкових слів довжини m за допомогою заданої матриці E зберігає властивості групової операції, що означає, що кодові слова утворюють групу.

Властивість групового коду: мінімальна кодова відстань між кодовими векторами дорівнює мінімальній вазі ненульових векторів. Вага кодового вектора дорівнює числу одиниць кодової комбінації.

Групові коди зручно ставити за допомогою матриць, розмірність яких визначається параметрами k і n. Число рядків дорівнює k, а число стовпців дорівнює n = k + m.

Коди, що породжуються цими матрицями, називаються (n, k)-кодами, а відповідні їм матриці, що породжують (утворюють, що виробляють).

Відстань Хеммінга

Американський математик Хеммінг дослідив, від чого залежить даний код, чи він виявлятиме помилки і коли може їх виправляти. Інтуїтивно ясно, що це залежить від того, як рознесені між собою кодові слова і скільки помилок може з'явитися в переданому слові. Ми зараз формалізуємо наступну ідею. При кодуванні треба узгоджувати число можливих помилоку переданому слові так, щоб при зміні кодового слова, що передається, воно залишалося ближчим до вихідного кодового слова, ніж до будь-якого іншого кодового слова.

Визначення 13.1.Розглянемо на множині всіх двійкових слів в алфавіті У= (0,1) довжини твідстань d(x, у), яке дорівнює числу незбігаючих позицій цих слів. Наприклад, Для слів х = 011101, у= 101010 відстань дорівнює d(x, y) = 5. Ця відстань носить назву відстань Хеммінга .

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

1) d(x, у) ≥ 0, d(x, у) = 0 тоді і лише тоді, коли х = у;

2) d(x, y) = d(y, x);

3) d(x, у) ≤ d(x, z) + d(z, у) - нерівність трикутника.

Теорема 13.1(про виявляючий код). Код є виявляючим у випадку, коли в слові, що передається, є не більше ніж k

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

Теорема 13.2(про виправний код.). Код виправляє всі помилки у випадку, коли в слові, що передається, є не більше kпомилок, тоді і лише тоді, коли найменша відстань між кодовими словами

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

Доказ. Докази цих теорем є аналогічними. Тому доведемо лише останню теорему.

Достатність. Нехай для будь-яких кодових слів маємо d(b 1, b 2) ≥ 2k+ 1. Якщо під час передачі кодового слова b 1відбулося не більше kпомилок, то для прийнятого слова маємо d(b 1, c) ≤ k. Але з нерівності трикутника для будь-якого іншого кодового слова b 2маємо d(b 1, з) + d(c, b 2) ≥ d(b 1, b 2) ≥ 2 k+ 1. Отже, від прийнятого слова до будь-якого іншого кодового слова відстань d(c, b 2) ≥ k + 1, тобто більше, ніж до b 1. Тому за прийнятим словом зможна однозначно знайти найближче кодове слово b 1і далі декодувати його.

Необхідність. Від неприємного. Припустимо, що мінімальна відстань між кодовими словами менша, ніж 2 k+ 1. Тоді знайдуться два кодові слова, відстань між якими буде d(b 1, b 2) ≤ 2 k. Нехай під час передачі слова b 1прийняте слово ззнаходиться на відрізку між словами b 1, b 2і має рівно kпомилок. Тоді d(c, b 1) = k, d (c, b 2) = d(b 1, b 2) – d(c, b 1) ≤ k. Тим самим за словом не можна однозначно відновити кодове слово, яке було передано, b 1або b 2. Прийшли до суперечності.

Приклад 13.3 . Розглянемо наступні п'ятирозрядні коди слів завдовжки 2 в алфавіті У = {0,1}:

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

b 3= K(10) = 10101, b 4= k(11) =11110.

Мінімальна відстань між різними кодовими словами дорівнює d(bi, bj) = 3. У силу першої теореми про виявляє код, цей код здатний виявляти не більше двох помилок у слові. У силу другої теореми код здатний виправляти не більше однієї помилки в слові.

Групові коди

Розглянемо докладніше коди слів в алфавіті У= (0, 1). Якщо для слів завдовжки твикористовуються кодові слова завдовжки n, то такі коди будемо називати ( т , п)-Коди. Усього слів завдовжки mодно 2 m. Щоб поставити ( т , п)-код, можна перерахувати кодові слова для всіх можливих слівдовжиною m, як у попередньому прикладі. Більше економним способом завдання кодових слів є матричне завдання.

У цьому випадку задається матриця, що породжує G= ∣∣ gij∣∣ порядку т × пз 0 та 1. Кодові слова визначаються щоразу за словом а = а 1a 2... атшляхом множення цього слова зліва, як вектора, на матрицю, що породжує

Тут додавання визначається за модулем 2. Для того щоб різним словамвідповідали різні кодові слова, достатньо мати у матриці Gодиничний базовий мінор порядку тнаприклад крайній лівий.

Приклад 13.4 . Розглянемо матрицю, що породжує.

Ця матриця задає (3, 4) код. У цьому три перші символи в кодовому слові інформаційні, а четвертий - контрольний. Він дорівнює 0, якщо парне числоодиниць у вихідному слові, і 1, якщо непарне числоодиниць. Наприклад, для слова а= 101 кодом буде b= aG= 1010. Мінімальна відстань Хеммінгу між кодовими словами дорівнює d(bi, bj) = 2. Тому це - код, що виявляє одноразову помилку.

Визначення 13.2.Код називається груповим якщо безліч всіх кодових слів утворює групу. Число одиниць у слові а називається вагамслова і позначається Якщо b- кодове слово та прийняте в каналі зв'язку слово з = b + е, то слово еназивається вектором помилок .

Теорема 13.3.Нехай є груповий ( т , п)-код. Тоді комутативна група Довсіх кодових слів є підгрупою комутативної групи Звсіх слів довжини пякі можуть бути прийняті в каналі зв'язку. Найменша відстань між кодовими словами дорівнює найменшій вазі ненульового кодового слова та

Розглянемо фактор-групу С/K. Сумежні класи тут визначатимуться зрушенням е + b, b∈ K.

Як представник суміжного класу виберемо елемент з найменшою вагою. Будемо такі елементи називати лідерами суміжного класу .

Якщо лідери трактувати як вектори помилок, то кожен суміжний клас - безліч спотворених слів у каналі зв'язку з фіксованим вектором помилок, зокрема при е= 0 маємо суміжний клас слів без спотворень, т. е. безліч кодових слів. Процес корекції та декодування слова зполягає у пошуку того суміжного класу, до якого відноситься слово з = е + b. Вектор помилок евизначає число та локалізацію помилок, кодове слово bвизначає корекцію прийнятого слова.

Щоб полегшити пошук суміжного класу і тим самим вектора помилок, Хеммінг запропонував використовувати групові коди зі спеціальними матрицями, що породжують.

Хеммінгові коди

Розглянемо побудову хеммінгова ( т , п)-коду з найменшою вагою кодового слова рівним 3, тобто коду, що виправляє одну помилку.

Покладемо п = 2 r– 1 і нехай у кожному кодовому слові будуть rсимволів контрольними, а тсимволів ( т = п – r= 2 r– 1– r) - інформаційними, r≥ 2, наприклад (1, 3)-код, (4, 7)-код і т. д. При цьому в кожному кодовому слові b= b 1b 2... b псимволи з індексами, рівними ступеня 2, будуть контрольними, інші інформаційними. Наприклад, для (4, 7)-коду в кодовому слові b= b 1b 2b 3b 4b 5b 6b 7 символи b 1b 2b 4будуть контрольними, а символи b 3b 5b 6b 7- інформаційними. Щоб задати матрицю, що породжує Gхеммінгова ( т , п)-коду, розглянемо допоміжну матрицю Мпорядку r× п, де п = 2 r- 1, таку, що в кожному jстовпці матриці Мстоятимуть символи двійкового розкладання числа jнаприклад для (4, 7)-коду матриця Мбуде 3 × 7:

Багато кодових слів поставимо як безліч рішень однорідної системилінійних алгебраїчних рівняньвиду

b МТ= 0.

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

Виберемо природний базисний мінор системи b МТ= 0, що стоїть у стовпцях з номерами, рівними ступеня 2. Тим самим змінні розділимо на базисні (кодові) та вільні (інформаційні). Тепер, поставивши вільні змінні, легко отримати базисні. Знайдемо фундаментальну систему m= п – rрішень цієї однорідної системи. Тоді будь-яке рішення системи є лінійна комбінація цих mрішень. Тому, виписавши построчно mрішень фундаментальної системи у вигляді матриці Gрозміром m× п, Отримаємо матрицю хеммінгова групового ( т , п)-коду, наприклад для (4, 7)-коду фундаментальною системоюрішень будуть 4 = 7 – 3 наступні рішення однорідної системи:

g 1= 1110000, g 2= 1001100, g 3= 0101010, g 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- Кодове слово. Тоді помножимо його на допоміжну матрицю сМТ= (е + b)МТ= еМ T. Якщо еМ T= 0, то слово з- кодове та вважаємо: помилки немає. Якщо еМ T≠ 0, то слово евизначає помилку.

Нагадаємо, що побудований хеммінг ( т , п)-код визначає одну помилку. Тому вектор помилки емістить одну одиницю в iпозиції. Причому номер iпозиції виходить у двійковому поданні як результат еМ T, що збігається з iстовпцем матриці М. Залишилось змінити символ iу прийнятому каналом слові з, викреслити контрольні символи і виписати декодоване слово.

Наприклад, нехай прийняте слово буде з= 1100011 для (4, 7) коду Хеммінга. Помножимо це слово на матрицю М T. Отримаємо

(1100011)М T=(010).

Отже, є помилка у другому символі. Тому кодове слово буде b= 1000011. Викреслимо контрольні символи b 1, b 2, b 4.Декодоване слово буде а = 0011.

Звичайно, якщо помилка була допущена більш ніж в одному символі, цей код її не виправить.

) в векторному просторікодових послідовностей, у цьому випадку відстанню Хеммінга між двома двійковими послідовностями (векторами) і довжиною називається число позицій, в яких вони різні - у такому формулюванні відстань Хеммінга увійшла до Словнику алгоритмів і структур даних Національного ІнститутуСтандартів США ( англ. NIST Dictionary of Algorithms and Data Structures ).

Так, відстань Хеммінга між векторами 0 011 1 і 1 010 1 дорівнює 2 (червоним відмічені різняться біти). Надалі метрика була узагальнена на q-ічні послідовності: для пари рядків «вибори» і «за бору» відстань Хеммінга дорівнює трьом.

У загальному виглядівідстань Хеммінга для об'єктів та розмірності задається функцією:

Відстань Хеммінга має властивості метрики, задовольняючи наступним умовам:

Відстань Хеммінга біоінформатикиі геноміці

Література

• Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950.
• Річард Блейхут. Теорія та практика кодів, що контролюють помилки. М., «Світ», 1986

Посилання

• Річард Хеммінг та початок теорії кодування // Віртуальний комп'ютерний музей

Wikimedia Foundation. 2010 .

Дивитись що таке "Відстань Хеммінга" в інших словниках:

відстань Хеммінга- хемінгівська відстань Відстань d (u,v) між двома кодовими послідовностями u і v однакової довжини, рівну числусимволів, у яких вони відрізняються. Блоковий код з мінімальною хемінгівською відстанню d дозволяє виявити (d 1) і…

кодова відстань- Мінімум відстані Хеммінга, взятий по всіх скриньках різних кодових слів у рівномірному коді. [Збірник термінів, що рекомендуються. Випуск 94. Теорія передачі. Академія наук СРСР. Комітет з технічної термінології. 1979] Тематики теорія ... ... Довідник технічного перекладача

У галузі математики та теорії інформації лінійний код це важливий типблокового коду, що використовується у схемах визначення та корекції помилок. Лінійні коди, в порівнянні з іншими кодами, дозволяють реалізовувати ефективніші алгоритми… … Вікіпедія

У галузі математики та теорії інформації лінійний код це важливий тип блокового коду, що використовується у схемах визначення та корекції помилок. Лінійні коди, в порівнянні з іншими кодами, дозволяють реалізовувати ефективніші алгоритми… … Вікіпедія

Виявлення помилок у техніці зв'язку дія, спрямоване на контроль цілісності даних під час запису/відтворення інформації або її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) ... Вікіпедія

Виявлення помилок у техніці зв'язку дія, спрямоване на контроль цілісності даних під час запису/відтворення інформації або її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) Вікіпедія

Виявлення помилок у техніці зв'язку дія, спрямоване на контроль цілісності даних під час запису/відтворення інформації або її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) Вікіпедія

Виявлення помилок у техніці зв'язку дія, спрямоване на контроль цілісності даних під час запису/відтворення інформації або її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) Вікіпедія