Коди, що коректують
 
а б в г д е ж з и й к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я
 

Коди, що коректують

коди, що Коректують, перешкодостійкі коди, коди виявлення і виправлення помилки, коди, що дозволяють по наявній в кодовій комбінації надмірності виявляти і виправляти певні помилки, поява яких приводить до утворення помилкових або заборонених комбінацій. Застосовуються при передачі і обробці інформації у обчислювальній техніці, телеграфії, телемеханіці і техніці зв'язку, де можливі спотворення сигналу в результаті дії різного роду перешкод. Кодові слова До. до. містять інформаційні і перевірочні розряди (символи). В процесі кодування при передачі інформації з інформаційних розрядів відповідно до визначених для кожного До. до. правилами формуються додаткові символи — перевірочні розряди. При декодуванні з прийнятих кодових слів по тих же правилах знов формують перевірочні розряди і порівнюють їх з прийнятими; якщо вони не збігаються, означає при передачі сталася помилка. Існують коди, що виявляють факт спотворення повідомлення, і коди, що виправляють помилки, тобто такі, за допомогою яких можна відновити первинну інформацію.

загрузка...

  Як приклад розглянемо код Хеммінга. Хай потрібно передати деяке слово 1010. При кодуванні воно буде представлено як 1011010, де 1-й, 2-й і 4-й розряди перевірочні (зліва направо 101), а останні інформаційні. Якщо при передачі сталася помилка, наприклад в 3-м-коді розряді замість 1 отриманий 0, то при декодуванні перевірочні розряди приймуть значення: 1-й (молодший) — 1, 2-й — 1, 4-й — 0 (тобто 011). Неспівпадання кодових комбінацій перевірочних розрядів не лише сигналізує про наявність помилки, але і вказує номер спотвореного розряду (011 — 3 в двійковому коді).

  здатність код, що Коректує і виявляюча, залежить від кодової відстані d між словами, чисельно рівного мінімальному числу помилок, яке може перетворити одне слово на інше. Наприклад, є кодова комбінація: 0111100; 0100101; 0010110. Перша група (слово) відрізняється від другої в трьох розрядах, друга від третьої — в чотирьох розрядах, перша від третьої — в трьох розрядах. Мінімальна відстань d між цими словами рівне 3. Якщо в першому слові станеться 3 помилки, то воно може перетворитися або на друге, або на третє слово; при декодуванні така помилка не буде виявлена. Максимальне число помилок, яке в даному випадку може бути виявлене, дорівнює 2. Якщо в першому слові сталася помилка в другому розряді, то отримане слово відрізняється від другого в чотирьох розрядах, від третього — в двох розрядах, від першого — в одному розряді. Згідно максимальної правдоподібності методу, при декодуванні робиться вивід, що, найімовірніше, передавалося перше слово. Для правильного декодування необхідно, щоб максимальне число помилок в передаваному слові перетворювало його на слово, що відрізняється від початкового в найменшому числі розрядів. Щоб виправляти всі комбінації з t помилок, необхідно і досить, щоб d ³ 2 t+ 1.

  Помилки в передаваних словах можуть виникати унаслідок або незалежних спотворень розрядів (в цьому випадку застосовують, наприклад, коди типа коди Хеммінга), або спотворень групи рядом розрядів, що стоять (для таких випадків розроблені коди, що виправляють одиночні пачки помилок, і коди, що виправляють більш за одну пачку помилок); для виявлення помилок в процесі обчислень на ЕОМ(електронна обчислювальна машина) розроблені так звані арифметичні коди.

  Літ.: Пітерсон В., Коди, що виправляють помилки пер.(переведення) з англ.(англійський), М., 1964.

  Р. Н. Оникий.