Систематичні коди

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

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

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

Система контролю повинна будуватися з таким розрахунком, щоб вона дозволяла виявити і по можливості виправити будь-які порушення. При цьому потрібно розрізняти наступні види помилок результату:

- що виникають із-за погрішностей в початкових даних;

- обумовлені методичними погрішностями;

- що з'являються із-за виникнення несправностей в роботі машини.

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

Функції контролю можна здійснювати при інформаційній надмірності. Така можливість з'являється при використанні спеціальних методів кодування інформації.

Завдання кодування інформації представляється як деяке перетворення числових даних в заданій системі числення. У окремому випадку ця операція може бути зведена до групування символів (представлення у вигляді тріад або тетрад) або представлення у вигляді символів позиційної системи числення. Оскільки будь-яка позиційна система не несе в собі надмірності інформації і усі кодові комбінації є дозволеними, то використовувати такі системи для контролю не представляється можливим.

Систематичний код -код, що містить в собі окрім інформаційних контрольні розряди.

У контрольні розряди записується деяка інформація про початкове число. Тому можна говорити, що систематичний код має надмірність. При цьому абсолютна надмірність виражатиметься кількістю контрольних розрядів k, а відносна надмірність - відношенням k/n де n = m + k – загальна кількість розрядів в кодовому слові (m - кількість інформаційних розрядів).

Поняття здатності коду корегування, зазвичай зв'язують з можливістю виявлення і виправлення помилки. Кількісно здатність коду корегування, визначається імовірністю виявлення або виправлення помилки. Якщо маємо n - розрядний код і вірогідність спотворення одного символу буде Р, то вірогідність того, що спотворені k символів, а інші n- k символів не спотворені, по теоремі множення вірогідності буде

Число кодових комбінацій, кожна з яких містить k спотворених елементів, дорівнює числу поєднань з п по k:

Тоді вірогідність спотворення

Оскільки на практиці Р= 10^-3¸10^-4, найбільша вага в сумі вірогідності має вірогідність спотворення одного символу. Тоді, основну увагу треба звернути на виявлення і виправлення поодинокої помилки.

Здатність коду корегування, пов'язана також з поняттям кодової відстані.

Кодова відстань d(A, В) для кодових комбінацій А і В визначається як вага такої третьої кодової комбінації, яка виходить складанням початкових комбінацій по модулю 2.

Це визначення співпадає з поняттям кодової відстані по Хэмінгу. Тому в теорії кодування воно називається хэмінговою відстанню.

Вага кодової комбінації V(A) - кількість одиниць, що містяться в кодовій комбінації.

Приклад. Знайти ваги і кодову відстань для комбінацій А = 100111001 і В = 011011100.

Знаходимо кодову комбінацію С = АÅВ = 111100101, для якої визначається вага, що дорівнює кодовій відстані для А і В:

Відповідь: d(A, В)= 6.

Коди можна розглядати і як деякі геометричні (просторові) фігури. Наприклад, тріаду можна представити у вигляді одиничного куба, що має координати вершин, які відповідають двійковим символам. В цьому випадку кодова відстань сприймається як сума довжин ребер між відповідними вершинами куба. Виявляється, що будь-яка позиційна система відрізняється тією властивістю, що мінімальна кодова відстань дорівнює 1.

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

де t - кратність помилок, що виявляються (у разі поодиноких помилок t =1 і так далі).

Це означає, що між сусідніми дозволеними кодовими словами повинне існувати принаймні одне кодове слово. У тих випадках, коли необхідно не лише виявити помилку але і виправити її (тобто вказати місце помилки), мінімальна кодова відстань має бути

Чим більше мінімальна кодова відстань, тим більше надмірність коду. Максимальна кодова відстань коду, очевидно, дорівнює його розміру, тобто числу двійкових розрядів в кодовому слові.

Очевидно, що t - кратна помилка приводить до того, що спотворена кодова комбінація відсовується від початкової на відстань . В той же час помилка не може бути виявлена, якщо вона переводить одну дозволену кодову комбінацію в іншу, теж дозволену. Отже, здатність коду виявляти усі помилки деякої кратності залежить від мінімальної відстані між дозволеними кодовими словами: чим більше мінімальна кодова відстань, тим більшій кратності потрібна помилка для перекладу будь-якої дозволеної кодової комбінації в іншу дозволену. Код з мінімальною кодовою відстанню d_min здатний виявляти будь-які помилки кратністю

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

.