Кодова відстань - студопедія

Можливість коригувальних кодів по виправленню і виявлення помилок визначається кодовою відстанню.

Кодовою расстояніемd називається мінімальна кількість розрядів в яких одна кодова комбінація відрізняється від іншої кодової комбінації.

Для конкретного коду кодовою відстанню даного коду називається мінімальне число елементів, якими одна кодова комбінація даного коду відрізняється від іншої кодової комбінації того ж коду.

Іноді кодове відстань називається хеммінговим відстанню (по імені Річарда Хеммінга, засновника перешкодостійких кодів).

У простого двійкового коду d = 1. Яким має бути кодове відстань у кодів, що виявляють помилки, і у кодів, що виправляють помилки?

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

Нехай є n-розрядний двійковий код. Виберемо 2 кодові комбінації і, які будемо вважати дозволеними (рисунок 7.1). Кожній дозволеної кодової комбінації відповідає своє підмножина заборонених кодових комбінацій з поодинокими помилками. Число їх одно Cn 1. а кодова відстань відносно початкової кодової комбінації d = 1. Графічно це представляється окружністю з радіусом d = 1.

Малюнок 7.1 - Визначення кодового відстані

Аналогічно, підмножина заборонених кодових комбінацій з подвійною помилкою має кодове відстань відносно початкової d = 2, а число їх одно Cn 2. І так далі до помилок кратності t включно.

Для того щоб при прийомі відновити саме кодову комбінацію необхідно, щоб набір її заборонених кодових комбінацій не перетинався з набором заборонених кодових комбінацій.

Для виправлення помилок кратності t кодове відстань повинна задовольняти умові:.

Для виправлення помилки кратності s кодове відстань повинна бути:

Якщо код повинен виправляти помилки кратності t і виявляти помилки кратності s. то кодова відстань повинна бути не менше

Перешкодостійкі коди діляться на два великі класи:

1. Блокові коди;

2. Безперервні коди.

Для блокових кодів до кожної вихідної комбінації додається блок надлишкових символів і виходить нова комбінація (рисунок 7.2).

Малюнок 7.2 - Побудова блокового коду

Розрізняють разделімие і нероздільні блокові коди. У разделімих блокових кодах k символів є інформативними, а r - перевірочними.

Такі коди позначають як (n, k) - коди.

Для нероздільних кодів розділити символи на інформативні та перевірочні неможливо (див. Далі кореляційний код).

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