Спосіб факторіального кодування з виявленням і виправленням помилок

Реферат: Спосіб факторіального кодування інформації з виявленням і виправленням помилок включає взаємно-однозначне перетворення, наприклад, за допомогою таблиці замін, породженої джерелом інформаційної послідовності у перестановку чисел деякого порядку. З метою виправлення помилок у каналі зв'язку кількість дозволених кодових слів зменшується, а відстань між ними збільшується на величину, що залежить від необхідного ступеня підвищення достовірності передавання інформації. При цьому для забезпечення її стійкості до несанкціонованого доступу параметри перетворення інформаційного блока в перестановку можуть триматися в таємниці. UA 121361 U (54) СПОСІБ ФАКТОРІАЛЬНОГО КОДУВАННЯ З ВИЯВЛЕННЯМ І ВИПРАВЛЕННЯМ ПОМИЛОК UA 121361 U UA 121361 U 5 10 15 20 25 30 35 40 45 Спосіб факторіального кодування з виявленням і виправленням помилок під час передавання інформації каналами зв'язку належить до обчислювальної техніки та може бути використаний в системах передавання даних, що вимагають захисту від несанкціонованого читання та стійкості до помилок. Відомим аналогом до запропонованого способу є спосіб каскадного кодування даних [1], у основі якого лежить принцип використання зовнішнього та внутрішнього завадостійких кодів. Такий підхід дозволяє суттєво підвищити пропускну здатність систем передавання даних і їх достовірність. Недоліком систем з каскадним кодуванням є необхідність введення надлишковості як для внутрішнього, так і для зовнішнього кодів, що призводить до зменшення швидкості коду та втрати частини пропускної здатності. Крім того, використання каскадних кодів обмежено високою складністю реалізації оптимальних декодерів, що забезпечують мінімальну ймовірність помилкового декодування кодових слів [2]. Ще одним аналогом до запропонованого способу є реалізований у пристрої [3] спосіб кодування інформації для виправлення однократних і виявлення багатократних помилок. Недоліком цього способу є те, що його використання можливе лише для циклічних кодів з невеликим порядком кодового поліному, а також те, що він направлений на виправлення лише однократних помилок. Найбільш близьким за суттю до запропонованого способу є спосіб факторіального кодування з відновленням даних за перестановкою (ФКВД) [4], який і прийнято як прототип. У відповідності до цього способу інформаційна послідовність із k біт замінюється на перестановку чисел порядку M , де M!  2k , причому для забезпечення взаємно-однозначного перетворення інформаційної послідовності в перестановку частина множини перестановок вважається забороненою. Крім того, з метою забезпечення захисту даних від несанкціонованого доступу параметри цього перетворення тримаються в таємниці. Недоліком запропонованого способу [4] є неможливість виправлення помилок, що може призвести до недостатньої швидкості передавання, а також обмежує використання ФКВД в системах реального масштабу часу. Задачею цієї корисної моделі є забезпечення за допомогою ФКВД прямого виправлення помилок, а також забезпечення можливості суміщення процедур виявлення та виправлення помилок. Суть корисної моделі полягає в наступному. Інформаційний блок, що містить k біт, надходить на вхід пристрою кодування, де послідовно перетворюється в факторіальне число, синдром і перестановку  порядку M , M!  2k , з наступним кодуванням її символів рівномірним двійковим кодом. Зазначимо, що тільки 2 k кодових слів є дозволеними. Представлені в двійковому вигляді перестановки дозволеної множини будемо називати сигнальними векторами, а множину сигнальних векторів - сигнальнокодовою конструкцією (СКК). Сигнальними точками будемо називати точки відрізку [0;M!1] числової осі, які відповідають числовому значенню синдромів перестановок дозволеної множини. Для забезпечення виправлення помилок передбачено 2 способи формування СКК: 1) СКК на основі мінімальної відстані Евкліда між сигнальними точками (СКК першого типу, або СКК-1); 2) СКК на основі мінімальної відстані Хеммінга між сигнальними векторами (СКК другого типу, або СКК-2). Для СКК-1 мінімальна відстань між сигнальними точками на відрізку [0;M!1] обмежена виразом: Dmin  [(M!1) /( 2k  1)] Для забезпечення виправлення помилок мінімальна відстань між сигнальними точками повинна становити Dmin  3 , що досягається за рахунок збільшення надлишковості коду. Для 50 цього інформаційний вектор A( x ) , двійковий еквівалент якого відповідає точці відрізку [0; 2k  1] , проектується в сигнальну точку інтервалу [0;M!1] . При цьому відстань між сигнальними точками і та j становить Di, j  Di  D j , де D i , D j - відповідно, відстані від 0 до сигнальних точок i та j, і задовольняє нерівності D i, j  D min , i, j  [0; 2k  1] , i  j . У найпростішому випадку сигнальні точки розміщуються рівномірно з кроком Dmin . Для цього інформаційний вектор проектується на 1 UA 121361 U інтервал [0;L  1] , де    D  1 L  Dmin  2k  1  2   min   2  шляхом перетворення  D  1 D  A 10  Dmin   min  , де A10 - десятковий еквівалент двійкового представлення вектора  2  A( x ) , A 10  [0; 2k  1] ; D - значення, що відповідає сигнальній точці вектора A( x ) . Після цього на 5 10 15 20 25 основі значення D формується перестановка порядку M , M!  L , яка передається каналом зв'язку. Процес декодування полягає в наступному. Прийнятий з каналу зв'язку блок даних надходить на вхід декодера, де виконується перевірка, чи є отримана послідовність перестановкою. Ця перевірка полягає у встановленні факту, що кожен символ з відрізку [0;M!1] зустрічається рівно один раз в отриманій послідовності. Якщо ця умова не виконується, відбувається формування сигналу запиту на повторне передавання отриманого з помилкою блока. В іншому випадку знаходиться точка D відрізку [0;M!1] , яка відповідає отриманій перестановці. Після цього виконується пошук найближчої (в метриці Евкліда) до неї сигнальної точки. У випадку, якщо існує дві сигнальні точки, відстань до яких однакова і мінімальна, декодер формує сигнал запиту на повторне передавання блока. Якщо найближча сигнальна точка одна, виконується її зворотне відображення на інтервал [0; 2k  1] . За рівномірного розташування сигнальних точок зворотне перетворення має вигляд: A10  D Dmin  , вираз D Dmin  означає, що береться ціла частина. Для СКК-2 виправлення помилок кратності t досягається за мінімальної відстані Хеммінга між сигнальними векторами dmin  2t  1. Для цього, пристрій кодування, наприклад, за допомогою таблиці замін, відображує множину інформаційних векторів у множину сигнальних векторів, причому відстань між сигнальними векторами і та j, i, j  [0; 2k  1] , i  j , задовольняє умові di, j  dmin . Процес декодування полягає в наступному. Декодер виконує перевірку, чи є отримана послідовність перестановкою. Якщо ця умова не виконується, відбувається формування сигналу запиту на повторення пошкодженого блока. В іншому випадку декодер визначає відстань Хеммінга ri між прийнятим вектором та всіма сигнальними векторами, i  [0; 2k  1] , і знаходить мінімальну відстань rmin  min  i . Якщо існує єдине i  [0; 2k  1] : ri  rmin , то прийнятий r вектор ототожнюється з i-им сигнальним вектором. Якщо ж існує як мінімум два значення i, j  [0; 2k  1] : ri  rj  rmin , то формується сигнал на повторний запит блока даних. 30 35 40 Джерела інформації: 1. Золотарев В.В. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник / В.В. Золотарев, Г.В. Овечкин. - М: Горячая линия - Телеком, 2004. - 126 с: с ил. 2. Гладких А.А. Основы теории м'якого декодирования избыточных кодов в стирающем канале связи / А.А. Гладких. - Ульяновск : УлГТУ, 2010. - 379 с. 3. Пат. 23944А Україна, МПК G06F 7/498 (2006.01), G06F 11/08 (2006.01). Пристрій для виправлення однократних та виявлення багатократних помилок/ Мусаєв Ікрам Мохтарамович, Боцюра Ірина Петрівна, Фадеева Олена Григорівна; заявник та патентовласник ВДТУ. - № 95083815; заявл. 15.08.1995; опубл. 31.08.1998, Бюл. № 4. 4. Фауре Э.В. Факториальное кодирование с восстановлением данных / Э.В. Фауре // Вісник Черкаського державного технологічного університету. - 2016. № 2. С. 33-39. Режим доступу: http://vtn.chdtu.edu.ua/article/view/82932/78400. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 45 50 1. Спосіб факторіального кодування інформації з виявленням і виправленням помилок, що включає взаємно-однозначне перетворення, наприклад, за допомогою таблиці замін, породженої джерелом інформаційної послідовності у перестановку чисел деякого порядку, який відрізняється тим, що з метою виправлення помилок у каналі зв'язку кількість дозволених кодових слів зменшується, а відстань між ними збільшується на величину, що залежить від необхідного ступеня підвищення достовірності передавання інформації, при цьому для забезпечення її стійкості до несанкціонованого доступу параметри перетворення інформаційного блока в перестановку можуть триматися в таємниці. 2 UA 121361 U 5 2. Спосіб за п. 1, який відрізняється тим, що відстань між кодовими словами визначається як відстань Евкліда між сигнальними точками, що відповідають синдромам перестановок дозволеної множини, які обчислюються шляхом перетворення символів інформаційної частини або перестановки в послідовність взаємопов'язаних чисел у факторіальній системі числення. 3. Спосіб за п. 1, який відрізняється тим, що відстань між кодовими словами визначається як відстань Хеммінга між представленими в двійковому вигляді перестановками дозволеної множини, а її мінімальне значення визначає максимальну кратність помилки, яку код здатен виправити. 10 Комп’ютерна верстка А. Крулевський Міністерство економічного розвитку і торгівлі України, вул. М. Грушевського, 12/2, м. Київ, 01008, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3