Метод структурно-логічного кодування

Особливості корегуючих властивостей СЛК перетворень

2009

Анотація

Метод структурно-логічного кодування (СЛК) інфімумних диз'юнктивних нормальних форм (ІДНФ) булевих функцій базується на використанні природної логічної надмірності змінних послідовностей розгортання покриваючих n-мірних кубів .

Принципова відмінність кодування СЛК від відомих методів кодування як блокових так і безперервних кодів полягає в тому, що необхідність введення додаткової надмірності в інформаційну послідовність при структурно-логічному кодуванні відсутня, оскільки логічні варіанти подання даних у вигляді диз'юнктивно-нормальних форм (ДНФ) мають природну надмірність.

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

В даній роботі проведений аналіз основних особливостей коректуючих властивостей структурно-логічних кодів інфімумних диз'юнктивних нормальних форм БФ для каналів з незалежними помилками.

СЛК – структурно-логічне кодування, ДНФ – диз’юнктивна нормальна форма, ІДНФ – інфімумна диз’юнктивна нормальна форма.

Зміст

ВСТУП

1.        Коректуючі властивості мінімального інтервалу декодування

2.        Визначення ймовірності помилкового декодування ЄКФ

3.        Висновок

4.        СПИСОК ВИКОРИСТАННОЇ ЛІТЕРАТУРИ

ДОДАТОК

Вступ

Метод структурно-логічного кодування (СЛК) інфімумних диз'юнктивних нормальних форм (ІДНФ) булевих функцій базується на використанні природної логічної надмірності змінних послідовностей розгортання покриваючих n-мірних кубів [1].

Принципова відмінність кодування СЛК від відомих методів кодування як блокових так і безперервних кодів полягає в тому, що необхідність введення додаткової надмірності в інформаційну послідовність при структурно-логічному кодуванні відсутня, оскільки логічні варіанти подання даних у вигляді диз'юнктивно-нормальних форм (ДНФ) мають природну надмірність.

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

1. Коректуючі властивості мінімального інтервалу декодування

Структурно-логічні коди (СЛК) використовують природну логічну надлишковість інфимуних диз'юнктивних нормальних форм (ІДНФ) булевих функцій, які є основою побудови кодів СЛК, для виправлення помилок, які виникають при передачі даних по реальним дискретним каналам, окремо по каналам с незалежними помилками. Основною задачею являється встановлення базисних співвідношень між реалізованої кодами СЛК логічної надлишковості і граничним значенням кратності незалежних помилок, що виправляються.

Показано, що в межах мінімального інтервалу декодування (МІД)

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

спотвореної помилками кратності

Обов'язковою умовою виправлення помилок в такій скривленій вершині є коректне визначення 3-х останніх із чотирьох вершин МІД.

Таким чином, в межах МІД можливе виправлення будь-якої - кратної помилки на довжині розрядів вершини  куба .

Якщо помилка кратності  спотворює одночасно розряди двох сусідніх вершин, то така помилка виправлена бути не може, оскільки порушується обов'язкова умова коректності 3-х вершин МІД при виправленні четвертої вершини, тобто спотвореними стають 2 вершини МІД.

Пакетна помилка, окремим випадком якої є -кратна помилка, починається і закінчується завжди, як і  -кратна помилка, помилковим бітом

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

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

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

Ймовірність  відповідає ймовірності 1-кратної помилки. Двократна помилка визначається наявністю 2-х помилкових біт одночасно що відповідає ймовірності  (2)_==.

Ймовірність  -кратної помилки визначається виразом

 _=, (1)

 

де - розрядність кожної вершини МІД, визначеної в -мірному кубі .

З іншої сторони, ймовірність правильного прийому одного біта складе

 (1)=(1-), а ймовірність правильного прийому двох біт –

(2)=(1-).

Тоді ймовірність правильного прийому  біт складе

₌(1-) (2)

Розглянемо варіанти помилкового прийому двох сусідніх -розрядних вершин МІД на прикладі 4-х розрядних вершин. Якщо -кратна помилка перевищує розрядність  хоча б на одиницю (=+1), то така помилка в межах МІД не може бути виправлена, оскільки помилками будуть зачеплені 2 сусідніх вершини, як це показано на рис. 3.3

   

  

 (5)  (4)  (4)

Рис.1 Рис.2

Як видно з рис.1. 5-кратна помилка з ймовірністю  (5)⁼ _=, при =4 зачіпає 2 сусідніх вершини.

У загальному випадку помилки кратності  не можуть бути виправлені в межах МІД. Таким чином, ймовірність помилкового прийому 2-х вершин МІД, обумовлена дією помилки кратності >п на довжині 2 п біт вершин

 

 і , з урахуванням виразу (1) і (2) складе

 (3)

У разі попадання -кратної помилки (=п) з ймовірністю  (4)=  = в межі тільки однієї вершини МІД вершина повністю відновлюється, тобто така помилка виправляється (рис.3.4). Інакше, коли помилка кратності  не потрапляє в межі тільки однієї вершини можливо декілька варіантів помилкового прийому двох сусідніх вершин МІД.

     

  

 (4)  (4)  (4)

Рис.3

Як видно з рис.З, який являє собою приклад одночасного спотворення двох вершин для = п=4, число варіантів спотворення сусідніх вершин  і  визначається як . Це дійсно так, оскільки максимальне число помилкових біт -1 в межах п біт однієї вершини обов'язкове припускає хоча б 1 помилковий біт в межах п біт іншої вершини для забезпечення

одночасного спотворення вершин  і . Ймовірність появи  спотворених біт на довжині 2 біт рівна, як відомо, . Звідси витікає, що ймовірність помилкового прийому 2-х вершин МІД в результаті дії помилки кратності 1< п на довжині 2 біт з урахуванням числа варіантів спотворення складе

 (4)

Вирази (3) і (4) дозволяють оцінити ймовірність помилки мінімального інтервалу декодування, обумовлену дією незалежних 1<tп і t>n - кратних помилок одночасно на дві вершини  і  МІД в межах 2n біт.

Ймовірність помилки МІД n-мірного куба Е, обумовленої помилковим прийомом двох вершин завдовжки 2п біт, при дії незалежних помилок кратності 1<tn і t<n визначається виразом

 (5)

Вираз (5) дозволяє оцінити коректуючі властивості мінімального інтервалу декодування, який є основою побудови єдиного кодуючого формату (ЄКФ), тобто кодової комбінації коду СЛК. Оцінка базових коректуючих властивостей МІД дає можливість визначити коректуючі властивості коду СЛК в цілому для заданого каналу з незалежними помилками.

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

 

при різній довжині n вершин.

При визначенні вірогідності помилки МІД Р_МІД(5) враховувалися тільки ті варіанти помилок t, які приводили до помилкового прийому, тобто по суті справи до неправильного декодування МІД, що визначається точніше як ймовірність помилки декодування фрагмента кодової комбінації СЛК, тобто ЄКФ.

Аналіз фрагментарного декодування СЛК, на основі залежності  при n=3,4,5 представлений на рис.3.6, показав, що вплив розрядності n вершин куба  на ймовірність помилки декодування Р_МІД практично відсутній. У достатньо важких каналах при  фрагментарне декодування СЛК зіставно по ймовірності помилки декодування з згортковим кодом, що виправляє помилки t  2, що указує на можливість успішного використання кодів СЛК в реальних каналах передачі даних.