Коригувальні коди

Коригувальні коди
Перешкодостійкі коди, коди виявлення і виправлення помилки, коди , дозволяють за наявною в кодової комбінації надмірності (Див. Надмірність) виявляти і виправляти певні помилки, поява яких призводить до утворення помилкових або заборонених комбінацій. Застосовуються при передачі і обробці інформації в обчислювальній техніці, телеграфії, телемеханіки і техніці зв'язку, де можливі спотворення сигналу в результаті дії різного роду перешкод.
перешкодостійкі коди, коди виявлення і виправлення помилки, коди , дозволяють за наявною в кодової комбінації надмірності (Див. Надмірність) виявляти і виправляти певні помилки, поява яких призводить до утворення помилкових або заборонених комбінацій. Застосовуються при передачі і обробці інформації в обчислювальній техніці, телеграфії, телемеханіки і техніці зв'язку, де можливі спотворення сигналу в результаті дії різного роду перешкод. Кодові слова К. к. Містять інформаційні та перевірочні розряди (символи). У процесі кодування (Див. Кодування) при передачі інформації з інформаційних розрядів відповідно до визначених для кожного К. к. Правилами формуються додаткові символи - перевірочні розряди. При декодуванні з прийнятих кодових слів за тими ж правилами знову формують перевірочні розряди і порівнюють їх з прийнятими; якщо вони не збігаються, значить при передачі відбулася помилка. Існують коди, які виявляють факт спотворення повідомлення, і коди, що виправляють помилки, т. Е. Такі, за допомогою яких можна відновити первинну інформацію. Як приклад розглянемо код Хеммінга. Нехай потрібно передати деяке слово 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. Г. Н. Оникій.

Велика радянська енциклопедія. - М.: Радянська енциклопедія. 1969-1978.