Надлишковість та здатність виявляти та виправляти помилки

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

Кодова послідовність Галуа базується на основі базису Галуа, згідно рекурентної процедури G_i+i=G_iÅG_i-(n-1).

V=N; n= V/2,

Представлення рекурентного коду Галуа: N – число комбінацій; V- об’єм кодової системи; n – число елементів системи.

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

Для виявлення помилок при передаванні сигналу використовують стандартні методи на основі рекурентних надлишкових коректуючих кодів.

В загальному випадку надлишковість даних, які передаються згідно стандартного протоколу, можна оцінити у вигляді коефіцієнта надлишковості як відношення об’єму даних, що передаються, до об’єму вхідних даних, які підлягають передачі, згідно формули:

К_н = V_k / V_x,

де V_х – об’єм вхідних даних; V_с – об’єм службових даних; V_k = V_с+ V_х , V_с= V_Ф+ V_A+ V_Y+ V_kk+ V_Б ; V_Ф, V_A, V_Y, V_kk, V_Б – відповідні об’єми кодів флага, адреса станцій, типу фрейму та коректуючого коду Боуза – Чоудхурі – Хоквінгхема, символів біт-стаффінга; V_k – об’єм даних, що передаються в інформаційних каналах.

З метою оцінки надлишковості існуючих протоколів типу HDLC, HP-IL, KT-1 проаналізовані структури фреймів, які формалізовані на основі аналітичних виразів:

К_{н (HDLC)} = (V_Ф+ V_A+ V_Y+ V_kk+ V_Б +V_x) / K_ФС ×V_x,

К_{н (HDLC)} = (V_Ф+ V_A+ V_Y+ V_kk+ 2^b +2^k ×8) / 2^k ×8,

де K_ФС – коефіцієнт форми сигналу; К_{ФС (HDLC)} = 0.5.

К_{н (HP-IL)} = (3 +2^k ×8 +V _kk) / K_ФС ×2^k ×8,

К_ФС(HP-IL) = 0.3; V _kk = 16.

К_{н (КТ-1)} = (4 +2^k ×8 +V _kk) / K_ФС ×2^k ×8,

К_{ФС (КТ-1)} = 1.0 ; V _kk = 16.

Аналіз показує, що надлишковість існуючих протоколів різко зростає при малих об’ємах даних, які передаються, що характерно для низових рівнів РКС. Тому їх застосування на різних рівнях сучасних комп’ютерних систем є недостатньо ефективне і потребує вдосконалення як в теоретичному, так і в практичному планах.

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

Суть методів безнадлишкового сигнального кодування з можливістю виявлення та виправлення помилок полягає в тому, що при формуванні такого класу кодів використовують до п’яти сигнальних ознак наступного типу:

фронт наростання __­¯¯( Ù ); фронт спаду ¯¯¯__(Ú ); додатній потенціал |^▬▬| (+); від’ємний потенціал |_▬▬| (–); нульовий потенціал |▬| (S), при чому послідовність бітів даних додатково модулюється кодом поля Галуа.

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

Розроблено чотири способи і, відповідно, методи формування такого класу кодів: позиційно-сигнальний код (ПСК); несиметричний рекурентний сигнальний код (НРСК); рекурентний симетричний сигнальний код (РССК); квазісимвольний сигнальний код (КССК).

Метод формування позиційно-сигнального коду полягає в наступному: введемо систему представлення сигнальних та кодових ПСК

G₀¹ Þ «+» ; G₀⁰ Þ «–» ; G₁¹ Þ «Ù» ; G₁⁰ Þ «Ú».

Формування ПСК коду показано в табл.1.

Представлення символіки розрядно-позиційного сигнального коду Галуа, для півбайтових потоків даних, що відповідає потоку чисел або цифр має наступний вигляд:

1 1 1 1 0 0 0 0

G1 G1 G0 G0 G1 G1 G0 G0

­ ­ ¯ ¯ +1 +1 -1 -1

Ù Ù Ú Ú + + – – .

Для 4-х бітового повідомлення, яке передається, існує m=2⁴ комбінацій ПСК, які в сигнальному та кодовому виді наведені в табл.1.

Таблиця 1 Коректуючі властивості ПСК.

Таким чином, при формуванні інформаційних повідомлень на основі ПСК незалежно від обсягу масиву даних та різних модулюючих кодів Галуа ймовірність виявлення помилок є постійна і число невиявлених помилок є сталим. Позитивною характеристикою ПСК є можливість виявлення та в окремих випадках виправлення помилок типу «стирання» та «вставок» бітів, які можуть виникати під впливом мультиплікативних завад. Функціональним обмеженням є відсутність можливості визначення числа нулів та одиниць у блоці даних.

Метод формування НРСК полягає в тому, що послідовність нулів, які передаються в пакеті даних, нумеруються рекурентним кодом Галуа G₂^k. Причому біт Галуа “1” передається фронтом спаду, тобто маніпуляційним сигналом “10”, а нулі бітів Галуа передаються сигналом “00”. Для передавання інформаційних одиниць використовується фронт наростання .

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

Таблиця 2 Реалізація методу НРСК даних з використанням кодової

послідовності Галуа G₂³ (11101000).

У табл.2 введені наступні позначення: Д - дані, які передаються; SК – сигнальний код каналу зв'язку (Манчестерський код); SК1–сигнальний код передавання "1" в каналах зв'язку; G(0)–код Галуа, який нумерує нулі; SК01 – сигнальний код нулів, коли біт-Галуа "1" передає кодом "11", а біт-Галуа "0" передає кодом "00"; SК02 – сигнальний код нулів, коли біт-Галуа "1" передає "10", а "0" —> "00"; GK01 – сигнальні коди маніпуляції, в яких нулі нумеруються кодом Галуа; GK02 – сигнальні коди маніпуляції, в яких нулі нумеруються кодом Галуа по фронту спаду.

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

Другою модифікацією НРСК є використання коду Галуа для одночасного симетричного сигнального формування нулів і одиниць потоку даних (РССК), причому об’єм коду Галуа відповідає об’єму даних, що передаються.