Метод структурно-логічного кодування Особливості корегуючих властивостей СЛК перетворень 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<t n і t<nвизначається виразом (5) Вираз (5) дозволяє оцінити коректуючі властивості мінімального інтервалу декодування, який є основою побудови єдиного кодуючого формату (ЄКФ), тобто кодової комбінації коду СЛК. Оцінка базових коректуючих властивостей МІД дає можливість визначити коректуючі властивості коду СЛК в цілому для заданого каналу з незалежними помилками. Для оцінки коректуючих властивостей МІД побудуємо залежність при різній довжині n вершин. При визначенні вірогідності помилки МІД РМІД (5) враховувалися тільки ті варіантипомилокt, які приводили до помилкового прийому, тобто по суті справи до неправильного декодування МІД, що визначається точніше як ймовірність помилки декодування фрагмента кодової комбінації СЛК, тобто ЄКФ. Аналіз фрагментарного декодування СЛК, на основі залежності при n=3,4,5 представлений на рис.3.6, показав, що вплив розрядності n вершин куба на ймовірність помилки декодування РМІД практично відсутній. У достатньо важких каналах при фрагментарне декодування СЛК зіставно по ймовірності помилки декодування з згортковим кодом, що виправляє помилки t 2, що указує на можливість успішного використання кодів СЛК в реальних каналах передачі даних. 2. Визначення ймовірності помилкового декодування ЄКФ Використання МІД як єдиного кодуючого формату, тобто кодової комбінації СЛК, як це витікає з аналізу, не є достатньо ефективним, оскільки фрагментарне використання коду СЛК поступається по ймовірності помилки декодування відомим коректуючим кодам, зокрема згортковим кодом, в каналах з ймовірністю помилки . Нехай в якості ЄКФ прийнята послідовність вершин куба 3 , тобто n=3. Прийнятий куб 3 містить два мінімальні інтервали декодування МІД1 і МІД2 , що складаються з 4-х вершин кожен (рис.1). Нехай всі вершини МІД1 повністю відновлені, що указує на те, що було спотворене не більше однієї вершини в МІД1 . Тоді для повного відновлення всіх вершин в МІД2 необхідне знання відповідної змінної розгортання. Як видно з рис.5 для визначення цієї змінної необхідно і достатньо, щоб тільки одна з 4-х вершин МІД2 була б прийнята коректно, оскільки кожна з вершин МІД1 пов'язана з відповідною вершиною МІД2 по однаковій змінній (на рис. 3.7 такою змінною виступає ). Тому для будь-якої з вершин МІД2 (5,6,7,8), прийнятої коректно, можливо визначення змінної , що розгортає МІД1 в ЄКФ, тобто куб 3 . Інші три вершини МІД2 можуть бути прийняті з помилками на етапі визначення змінної розгортання , оскільки надалі на цьому етапі відновлення всі помилки у вершинах МІД2 виправляються. У межах МІД в якості породжуючих використовуються 2 змінні розгортання (у нашому прикладі це і ). Одна змінна, що залишилася ( у нашому прикладі) використовується для повного відновлення всіх вершин в МІД2 , а отже і всього ЄКФ. Якби в якості ЄКФ виступав куб , то, при повністю відновлених вершинах одного МІД, для правильного прийому всіх вершин ЄКФ необхідне знання відповідних змінних розгортання на кожному етапі перетворення МІД в ЄКФ кубів . В загальному випадку таких змінних повинно бути n-2, оскільки в МІД використовується 2 змінні розгортання з всієї кількості . У зв'язку з вищевикладенимсправедлива. МІД1 МІД2 Рис.1 Для повного відновлення всіх вершин ЄКФ куба Еп необхідно і достатньо при коректно прийнятому одному МІД наявність хоча би однієї, прийнятої безпомилково вершини в межах відновлюваного куба на кожному етапі перетворення. Це дійсно так, оскільки наявність однієї правильної вершини в межах відновлюваного куба, окрім відновлених вершин на попередніх етапах, дає можливість визначити змінну відновлення однозначно. Для n-розрядної вершини ймовірність помилкового прийому з урахуванням одночасності збою розрядів і правильного прийому n- розрядів складе . Число варіантів збою розрядів очевидно рівно . Зрозуміло, що кількість збитих розрядів в межах оцінки вершини може змінюватись від 1 до n. У такому разі ймовірність помилкового визначення змінної відновлення із-за неправильного прийому однієї вершини у межах відновлюваного n- мірного куба буде рівна (2) Ймовірність Р' визначає, по суті справи, ймовірність помилкового декодування чергового відновлюваного МІД в межах ЄКФ куба . Тоді ймовірність помилкового декодування ЄКФ куба з урахуванням ймовірності помилки РМ1Д (3.25) буде визначатьсятаким чином. Ймовірність помилкового декодування ЄКФ визначається ймовірністю помилки МІД РМ1Д і ймовірністю помилки змінної відновлення (3) де РМ1Д - ймовірність помилки МІД п -мірного куба Е , Р' - ймовірність помилки змінної відновлення . Використовуючи вираз (3) побудуємо залежність (рис.2) для У тих же координатах розмістимо залежність для згорткового коду, що виправляє всі одиночні та двійні помилки. У відміну від фрагментарного декодування СЛК аналіз залежностей показав, що з ростом ,тобто із збільшенням мірності куба ЄКФ, кодової комбінації кода СЛК, значно збільшується виграш у завадостійкості, тобто зменшується ймовірність декодування . Порівнюючи Р для згорткового коду і РЕКФ для n=3,4,5 помічаємо, що для n=3 при (ймовірність збою біта в каналі з незалежними помилками) виграш складає в першому наближенні 1 порядок (Р =2 10 ,РЄКФ =2 10 ). Для n=4 виграш складає 2 порядки (Р =2 10 , РЄКФ =1,5 10 ), а для n=5 - більш, чим 3 порядки (Р =2 10 , РЄКФ =8 10 ). У важкому каналі з виграш в завадостійкості для СЛК коду складає від 0,5 порядку (n=3) до 1,5 порядку (n=5). Крім того, із зменшенням вірогідності помилки в каналі до виграш в завадостійкості для коду СЛК, принаймні, не зменшується, особливо для n=4,5 , тобто як нахил прямих декодування до осі абсцис в порівнянні з згортковим кодом зменшується. Таким чином, використання структурно-логічних кодів в каналах з незалежними помилками забезпечує істотні переваги взавадостійкості, особливо у важких каналах з і каналах середньої тяжкості з. Висновок Проведений аналіз основних особливостей коректуючих властивостей структурно-логічних кодів інфімумних диз'юнктивних нормальних форм БФ для каналів з незалежними помилками. Визначена ймовірність помилкового декодування ЄКФ коду СЛК де - ймовірність помилки мінімального інтервалу декодування (МІД) мірного кубу , - ймовірність помилки змінної відновлення. Показано, що змінні кодів СЛК в каналах з незалежними помилками дозволяє отримати значний виграш в завадостійкості даних, причому коди СЛК достатньо впевнено працюють в каналах з ймовірністю помилки тобто достатньо тяжких каналах. Список використанної літератури 1. Іванов Ю.Д., Пампуха І.В., Захарова О.С., Жиров Г.Б. Метод структурно-логічного кодування інфімумних диз’юнктивних нормальних форм булевих функцій в базисі куба //Збірник наукових праць Військового інституту Київського національного університету ім. Тараса Шевченка.-К.,2006.-№5.-с.46-49. 2. Лєнков С.В., Боряк К.Ф., Іванов Ю.Д., Селюков О.В. Метод представлення дискретної інформації на основі інфімумних диз’юнктивних нормальних форм булевих функцій//Збірник наукових праць Військового інституту Київського національного університету імені Тараса Шевченка.-К.,2008.-№11.-с.90-97. 3. Іванов Ю.Д., Пампуха І.В., Перегудов Д.О., Захарова О.С. Основи реалізації природньої структурно-логічної надмірності диз’юнктивних нормальних форм представлення данних // Вісник Київського національного університету імені Тараса Шевченка. Військово спеціальні науки -К.,2007.-№14.-с.12-15. 4. Іванов Ю.Д., Пампуха І.В., Осипа В.О., Охрамович М.М. Узагальнений метод структурно-логічного декодування інфімумних форм подання булевих функцій //Збірник наукових праць Військового інституту Київського національного університету імені Тараса Шевченка.-К.,2006.-№4.-с.48-53. 5. Лєнков С.В., Іванов Ю.Д., Пампуха І.В., Боряк К.Ф. Особливості корегуючих властивостей структурно-логічних кодів // Науково-технічний журнал «Захист інформації».- К.,2007.-№4(36).-с.75-81. Додаток Блок-схема алгоритму визначення ймовірності помилки МІД n-мірного куба Е , та ймовірність помилкового декодування ЄКФ