3.2 Надлишкові коди

Для ефективної боротьби з перешкодами застосовуються надлишкові коди. Вони дозволяють виявити і виправити помилки, що виникають при передачі і породжуються впливом перешкод. Розвиток цих кодів почався в 1950 році.

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

N₀ = mⁿ , (3.7)

де m – основа коду ;

n - значимість коду (кількість символів в кодовій комбінації),

а тільки деяких їх частин:

N<N₀ (3.8)

Комбінації, що використовуються в даному коді, називаються дозволеними, а ті, що не використовуються – забороненими. Перетворення дозволеної комбінації в заборонену в результаті дії перешкоди виявляє існування помилки. Однак, якщо одна дозволена комбінація перетворюється в іншу дозволену комбінацію, то помилка виявлена не буде. Таким чином, будь-який код, що задовільняє умову (3.8), здатен виявити N(N₀-N) помилок з їх можливої кількості N(N₀-1). Відношення виявлених кодом помилкових комбінацій до всіх можливих помилок складає

. (3.9)

Аналогічно справа ведеться з виправленням помилок. Для використання коду в якості виправляючого потрібно виконати розбиття множини заборонених кодових комбінацій N₀ – N на N підмножин M_i , що не перетинаються (рис. 3.1). Кожна з цих підмножин приписується до своєї дозволеної кодової комбінації. Виправлення полягає в тому, що дану заборонену комбінацію завжди приймають за ту дозволену комбінацію, до якої дана заборонена комбінація приписана. Таким чином, відношення помилок, що виправляються, до всіх можливих помилок складає:

(3.10)

а до всіх помилок, що виявлені

(3.11)

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

A_k B_j M_k

Рисунок 3.1 – Можливий розподіл заборонених кодових комбінацій за дозволеними.

Таблиця 3.3 – Виправлення помилок нищої кратності

Вектор помилки	Дозволені комбінації
	0001	0101	1110	1111
Прийняті комбінації
0001 0010 0100 1000	0000 0011 0101 1001	0100 0111 0001 1101	1111 1100 1010 0110	1110 1101 1011 0111
0011 0101 1001 0110 1010 1100	0010 0100 1000 0111 1011 1101	0110 0000 1100 0011 1111 1001	1101 1011 0111 1000 0100 0010	1100 1010 0110 1001 0101 0011
0111 1011 1101 1110	0110 1010 1100 1111	0010 1110 1000 1011	1001 0101 0011 0000	1000 0100 0010 0001
1111 1110 1010 0001 0000

Викладене ілюструє табл.3.3. В ній показано дію всіх можливих помилок на випадково вибрані дозволені комбінації чотиризначного коду. Введений вектор помилки треба розуміти так: 0 – помилки нема; 1 – помилка є. Прийнята комбінація отримується шляхом складання передачі і помилки. Правила складання:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0

В розглянутому прикладі:

кількість можливих комбінацій N₀ = mⁿ =2⁴=16;

кількість векторів помилок N_пом =mⁿ-1=2⁴-1=15;

кількість можливих помилок N(N₀-1) = 4(16-1) = 60;

кількість виявлених помилок N(N₀-N)=4(16-4)= 48(80%);

кількість невиявлених помилок (комбінації, підкреслені в таблиці)

N(N₀-1) - N(N₀-N) = 60-48 = 12(20%);

кількість помилок, що не виправляються

N(N₀-1) - (N₀-N) = 60-12=48 (80%).

Спосіб виправлення помилок повинен забезпечити мінімум їх середньої ймовірності. Тому розбиття заборонених кодових комбінацій (помилки, що можна виправити) на підгрупи відбувається в залежності від статистики помилок. У випадку, якщо в каналі зв’язку діють переважно взаємонезалежні помилки, їх ймовірність зменшується із збільшенням кратності помилки q. При такому положенні в першу чергу треба виправляти помилки нижчої кратності. Для прикладу, приведенного в таблиці 3.3, це зводиться до розподілу, що показане в табл. 3.4, в якій до дозволених комбінацій перш за все приписані помилки з кратністю q =2 і т.д. Множини заборонених кодових комбінацій, що приписуються дозволеним кодовим комбінаціям не повинні бути взаємоперетинаючими. Тому у випадку попадання однієї забороненої комбінації в дві множини її залишають тільки в одній з них, довільно вибраній.

Таблиця 3.4 – Виправлення пакетних помилок

Дозволені комбінації
0001	0101		1110		1111
Приписані заборонені комбінації
0000 0011 1001		0100 0111 1 101		1100 1010 0110		1101 1011 0 111
0 010 1000				1000 0010

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

Таблиця 3.5-Виправлення помилок

Дозволені комбінації
0001	0101		1110	1111
Приписані заборонені комбінації
1010
1100 0110	1011 1000 0010	0011 1001		0010 0100 1000
1101 0111		0111 1101

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

1 2 3 4

1 0 1 4 3

2 0 3 2

3 0 1

4 0

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

101

Рисунок 3.2- Геометрична інтерпретація двійкового коду

а)–двозначного; б)–трьохзначного; в) – чотиризначного

Розглядаючи двійковий код з геометричної точки зору (звідки і взяли термін “віддаль”), кожну кодову комбінацію ми можемо уявити собі як одну з вершин куба, існуючого в n – мірному просторі, де n відповідає значимості коду. Якщо виходити з такого припущення, то кодова відстань двійкового коду буде дорівнювати найменшому числу ребер одиничного куба, що відділяють одну кодову комбінацію від іншої (рис.3.2). Вибір складу множин заборонених комбінацій, що приписуються до дозволених, зводиться до вибору власних областей в просторі сигналів.

Із поняття кодової віддалі ρ випливає, що для виявлення всіх одиничних помилок ( тобто помилок з q = 1 ) необхідно і достатньо, щоб ρ ≥2, а для виявлення всіх помилок кратності q_d величина ρ повинна відповідати нерівності

ρ ≥ q_d +1 . (3.12)

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

ρ ≥2 q_с + 1 . (3.13)

Для того, щоб код міг виправляти всі помилки з кратністю ≤ q_с і одночасно виявляти всі помилки з кратністю ≤ q_d , достатньо, щоб кодова відстань виконувала умову

ρ ≥ q_с + q_d +1 . (3.14)

При використанні кодів, що виправляють помилки, ймовірність помилки після декодування зменшується, якщо ймовірність викривлення окремих символів не дуже велика. В каналах з великим рівнем перешкод надлишкові коди стають малоефективними.

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

Поряд із застосуванням виправляючих кодів визначене розповсюдження одержали так звані дешифратори ( канали ) із стиранням (erasure channel). Особливість цих дешифраторів в тому, що їх розв’язуючий пристрій має область невизначеності, в яку попадають всі сумнівні сигнали. Крім символів двійкового коду 0 і 1 на виході такого пристрою може з’явитися також символ невизначеності, або стирання, 0. Зміст викладеного в тому, що встановити стерті знаки при повній надійності решти легше, ніж виправити помилкові. При заданій кодовій відстані ρ найбільша кратність відновлюваних стирань t рівна кратності помилок, які виявлені, т.б.

ρ ≥ t + 1 . ( 3.15)

Щоб код міг одночасно виправити q_с помилок і відновити t стертих символів, достатньо, щоб кодова відстань виконувала умову

ρ ≥ q_с + t + 1 . ( 3.16)

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

Неперервні, або рекурентні, коди утворюються у вигляді неперервної послідовності символів, нерозподіленої на блоки.

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

До найбільш поширених блочних кодів відносяться систематичні і циклічні коди. Поняття “ систематичний код” тут застосоване в найвужчому його понятті . Обидва ці коди подільні, т.б. символи, які входять в їх кодові комбінації, що діляться на основні, або інформаційні, і контрольні, або провірочні. Кожна з цих груп символів у всіх кодових комбінаціях ( векторах ) займає одні і тіж позиції. Роздільні коди звичайно позначаються , як (n, k ) – коди,

де n – значність коду,

k–число інформаційних символів в кодовій комбінації.

Кожний рівномірний надлишковий блочний код складається виходячи з кількості кодуючих елементів N і вимог, які пред’являються до виправляючої здатності коду, які визначають кодову відстань ρ (формули (3.13), (3.14)).

З виразу

N = 2^k ( 3.17 )

можна визначити кількість інформаційних символів кодової комбінації. Природньо, що k завжди заокругляється до ближчого цілого числа. Далі визначається значність коду, хоча загальний розв’язок цієї задачі невідомий, деякі часткові результати показані в таблиці 3.6.

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