р визначили переважне застосування лише деяких з них, зокрема коригуючого коду Хеммінга.
1. Принципи побудови коригуючого коду Хеммінга
Розглянутий код призначений для виявлення та виправлення одиночної помилки. При побудові такого коду кожен з перевірочних символів визначається як результат підсумовування по модулю 2 певного поєднання інформаційних символів. У результаті цього сума перевіряються інформаційних та контрольного символів завжди є парною. При прийомі комбінацій такого коду прийняті комбінації піддаються аналогічним перевіркам, що охоплює інформаційні та контрольний символи. При наявності одноразової помилки в символах, що входять до перевірку, контрольна сума на приймальній стороні виявляється непарною. Оскільки інформаційні символи входять в перевірочні суми в різних поєднаннях, то число непарних контрольних сум може бути різним (від до). У коді Хеммінга перевірки на парність організовані таким чином, що виходить число, яке вказує номер позиції, на якій відбулося спотворення. Для цього результати перевірок, що представляють собою контрольні суми за модулем 2 і є, таким чином, одиницями або нулями, записуються у вигляді контрольного числа. Це число має вказувати номер спотвореного символу. Розглянемо, за яких умов контрольне число дійсно вкаже номер спотвореної позиції.
Якщо кодова комбінація не містить помилок, то контрольне число буде зображувати нуль. Якщо в молодшому розряді контрольного числа з'являється одиниця, то це означає, що є помилка в символі, що стоїть на одній з позицій, двійковий номер яких має одиницю в молодшому розряді. Такими позиціями будуть всі непарні позиції. Таким чином, перша перевірка повинна охоплювати всі символи, що стоять на непарних позиціях:
. (1)
Одиниця в другому розряді контрольного числа свідчить про наявність помилки на одній з позицій, двійкові номера яких мають одиницю в другому розряді. Такими позиціями є 2, 3, 6, 7, 10, 11 і т. д. Символи з перерахованими номерами увійдуть в другу перевірку:
. (2)
Аналогічно в третьому перевірку повинні увійти символи, що стоять на тих позиціях, двійкові номера яких мають одиницю в третьому розряді, тобто:
. (3)
Для останньої перевірки з номером легко отримати, що:
; (4)
код Хеммінг моделювання масив
де.
Оскільки контрольні символи повинні забезпечувати парність перевірочних сум, вони включаються лише в одну перевірку. Тільки в одну перевірку входять символи, двійкові номера позицій яких є цілими ступенями двійки, тобто 1, 2, 4, 8, 16 і т. д. На цих позиціях і розміщуються контрольні символи. Значення контрольних символів знаходяться як результат підсумовування всіх символів, що входять в дану перевірку. З виразів (1) - (4) можна визначити значення контрольних символів:
;
;
; (5)
Шляхом введення в даний код ще однієї перевірки та додаткового перевірочного символу можна утворити код, що виправляє одиночну і виявляє подвійну помилку. У додаткову перевірку включаються всі символи кодової комбінації. При цьому останній перевірочний символ розташовується в кінці комбінації, а його значення обчислюється за формулою:
. (6)
що забезпечує парність останньої перевірки.
При декодуванні спочатку проводиться перевірок на...
