Особливостікорегуючих властивостей СЛК перетворень
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>n — кратних помилок одночасно на двівершини /> і/> МІД вмежах 2n біт.
Ймовірність помилки МІД n-мірного куба Е/>, обумовленої помилковимприйомом двох вершин завдовжки 2п біт, при дії незалежних помилок кратності 1n і t
/> (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-мірного куба Е/>, та ймовірність помилковогодекодування ЄКФ
/>
/>