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

Реферат: Спосіб формування корегуючих кодів в системі залишкових класів, при якому інформаційне повідомлення із двійкової системи числення перетворюють у систему залишкових класів із використанням розширеної системи взаємно простих модулів, зокрема, використання додаткових модулів дозволяє виявляти та виправляти помилки в процесі передачі даних. При цьому, повідомлення розділяють на частини, і систему модулів вибирають таким чином, що отримані частини повідомлення є залишками по вибраних модулях, з яких після перетворення у позиційну систему числення обчислюють перевірочні символи. UA 117493 U (12) UA 117493 U UA 117493 U 5 10 15 20 25 30 Корисна модель належить до систем передачі інформації і може бути використана для передавання та приймання дискретних інформаційних повідомлень. Відомий спосіб формування корегуючих кодів в системі залишкових класів ґрунтується на тому, що інформаційне повідомлення перетворюється в систему залишкових класів з використанням розширеної системи взаємно простих чисел (модулів) [1,2]. Основним недоліком такого способу є необхідність перетворення інформаційного повідомлення, представленого в позиційній системі числення, в систему залишкових класів, що потребує значних обчислювальних ресурсів для кодування повідомлень. Тому він не може бути використаний в пристроях з обмеженими апаратними ресурсами, наприклад, в бездротових сенсорних мережах. Найбільш близьким за технічною суттю до винаходу, що заявляється, є спосіб формування корегуючих кодів в системі залишкових класів, при якому здійснюється перетворення повідомлення в систему залишкових класів на основі розширеної системи взаємно простих модулів [3, 4]. Суть способу полягає в тому, що для однозначного представлення числа X достатньо k залишків, при цьому k  n . За робочі модулі приймаємо - p1, p2 , ..., pk . Для представлення числа X залишками a , a , ..., a використовуються r  n  k додаткових залишків. В даному коді кожна 1 2 n цифра несе інформацію про число, включаючи надлишкові символи, таким чином появляється можливість виявлення і виправлення помилок. Проте такий спосіб значно обмежує використання корегуючих кодів системи залишкових класів, оскільки вимагає перетворення всього інформаційного повідомлення, представленого в позиційній системі числення, в систему залишкових класів при кодуванні і виконання зворотного перетворення після декодування. В основу корисної моделі поставлена задача розробки нового способу формування корегуючих кодів системи залишкових класів шляхом поділу повідомлення на частини (тетради, байти) та вибору інформаційних і перевірочних модулів певної розрядності, що забезпечить зменшення апаратних затрат на реалізацію пристроїв кодування та розширить область застосування корегуючих кодів системи залишкових класів в цифрових системах передавання даних. Поставлена задача вирішується завдяки тому, що спосіб формування перевірочних символів, при якому повідомлення в кодері розділяється на k частин розрядністю m з одержаних частин формується позиційне представлення повідомлення за вибраною системою модулів, з якого в свою чергу обчислюються перевірочні символи, згідно з корисною моделлю вибір інформаційних та перевірочних модулів здійснюється за умовою: pi  2m , 35 p1  p2  ...  pi  ...  pn , при виконанні якої отримані частини повідомлення k будуть залишками 40 за вибраною системою модулів, відповідно немає необхідності додаткового перетворення інформаційного повідомлення в систему залишкових класів. Спосіб здійснюють таким чином. Послідовність бітів, яка підлягає передачі, розділяється на k частин по 4 або 8 біт: j j j 2 2 k a1 a1 ... a1 ...a1 , a1 a 2 ... ai2 ...am , ..., a1 a 2 ... aij ...am , ..., a1 ak ... ak ...ak , (1) 1 2 i m 2 2 i m   де a - розряд даних в двійковому коді, m  4,8 . Кожній частині двійкового коду k ставляться у відповідність взаємно прості модулі pi ( p1  p2  ...  pi  ...  pk  ...  pn ) з яких перші k модулів інформаційні, n - загальна кількість i модулів, r  n  k - перевірочні модулі. Значення модулів вибираємо з умови pi  2m . При цьому k n i 1 45 i 1 перші k модулів визначають робочий діапазон pk   pi , повний діапазон дорівнює p   pi . При вказаному способі вибору інформаційних модулів значення тетрад або байтів в позиційному представленні можна вважати залишками, так як вони завжди менші за відповідні модулі pi . В результаті вказаного перетворення повідомлення набуде вигляду: x1, x2, ... xi, ..., xk  , (2) 50 де xi - частини повідомлення, які є залишками по вибраних модулях pi , m x i   ai  2i . i 1 1 UA 117493 U Для обчислення перевірочних символів повідомлення (2) перетворюємо в позиційну систему числення [2]: k X   xi  Mi  i modPk , i 1 де Mi  Pk , i  Mi1 modpi . pi 5 10 15 20 25 Перевірочні символи обчислюються за формулою [1]: xk i  X modpk i , i  1 (n  k ) , , де X - повідомлення в позиційній системі числення. В результаті кодове слово, яке складається з інформаційних і перевірочних символів, і має вигляд: x1, x2, ... xi, ..., xk , xk 1,... xn . В запропонованому способі формування перевірочних символів зберігаються всі переваги корегуючих кодів системи залишкових класів, при цьому значення інформаційних символів не змінюються, тобто залишаються в позиційній системі числення. Джерела інформації: 1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. - Μ.: Сов. Радио. - 1968. - 460 с. 2. Goh, Vik Tor, Mohammad Umar Siddiqi. Multiple error detection and correction based on redundant residue number systems. Communications, IEEE Transactions on 56.3, 2008. - Pp. 325330. 3. Червяков Η.И., Сахнюк П.Α., Шапошников А.В., Ряднов С.А. Модулярные параллельные вычислительные структуры нейро-процессорных систем / Под. ред. Н.И. Червякова. - М.: ФИЗМАТЛИТ, 2003. - 288 с. 4. Chervyakov N.I., Lyakhov Р.Α., Babenko Μ.G., Garyanina A.I., Lavrinenko I.N., Lavrinenko A.V., Deryabin M.A. An efficient method of error correction in fault-tolerant modular neurocomputers. Neurocomputing, 205, 2016. - Pp. 32-44. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 35 Спосіб формування корегуючих кодів в системі залишкових класів, при якому інформаційне повідомлення із двійкової системи числення перетворюють у систему залишкових класів із використанням розширеної системи взаємно простих модулів, зокрема, використання додаткових модулів дозволяє виявляти та виправляти помилки в процесі передачі даних, який відрізняється тим, що повідомлення розділяють на частини, і систему модулів вибирають таким чином, що отримані частини повідомлення є залишками по вибраних модулях, з яких після перетворення у позиційну систему числення обчислюють перевірочні символи. Комп’ютерна верстка О. Гергіль Міністерство економічного розвитку і торгівлі України, вул. М. Грушевського, 12/2, м. Київ, 01008, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 2