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

1. Спосіб отримання залишку по модулю незвідного багаточлена G(x) ступеня "n", який утворює код, що полягає в тому, що апріорно, наприклад, при виготовленні пристрою обчислення залишку, формують і записують у кожний біт переданих даних, у ході сеансу зв'язку зчитують з пам'яті і додають за модулем два тільки ті елементи кільця залишків, порядковий номер яких співпадає з порядковим номером одиничних символів інформаційної послідовності, при цьому порядок додавання не грає ролі. 2. Спосіб за п. 1, який відрізняється тим, що для розширення функціональних можливостей, наприклад, таких, як оперативна зміна незвідного багаточлена G(x), елементи кільця залишків по модулю G(x) обчислюють у процесі формування залишку ітераційно-циклічним зсувом попереднього елемента кільця на один розряд праворуч, якщо старший розряд попереднього елемента кільця рівний нулю, а, якщо старший розряд рівний одиниці, додатково до результату циклічного зсуву додають за модулем два константу C (x )= G(x ) Å x n-1 , при цьому початковий елемент кільця залишків = 1. a0 де А0(х) - ділене - вихідний інформаційний поліном, і=0; і - номер кроку ітерації, і Î 0, 1, 2, 3...; Аі(х) - результат проміжних перетворень інформаційного полінома на і-му кроці; Gn(x) - дільник – кодовий поліном ступеня "n"; m - різниця порядків Аі(х) і Gn(x). (11) UA Таким чином, якщо порядок дільника менше порядку діленого на m, поліном-дільник домножуєтся на хm (зсувається убік старших розрядів на m позицій) і сумується по модулю два з діленим на i-му кроці. Отримане значення приймається як нове ділене, виконується наступна ітерація. Операція продовжується доти, поки значення m не стане від'ємним, значення Аі(х) є залишок. Наведена процедура перетворення інформаційного масиву в масив залишку відповідає процедурі ділення А(х):G(х) "у стовпчик". Недоліком цього способу є те, що число ітерацій у процесі ділення є випадковою величиною, що залежить як від А(х), так і від G(х) (наприклад, можна порахувати число ітерацій і залишки при діленні 12:7 і при діленні 111:7). Через випадковість витрат часу на обчислення залишку ця процедура не може бути використана в системах передавання даних, які працюють у реальному масштабі часу, тобто тоді, коли процедура виконання ділення виконується в темпі надходження даних від джерела. (19) Корисна модель відноситься до області технічної кібернетики, може бути використаний у системах передавання інформації з послідовним блоковим обміном, наприклад, у системах з кодовим захистом переданих даних від помилок блоковими циклічними кодами, і призначений для обчислення залишку в кінцевому полі, зокрема, контрольної суми і синдрому помилок, відповідно, для кодера і декодера. Загальновідомим способом отримання залишку по модулю незвідного багаточлена є ітераційна процедура, відповідно до якої кожен крок процесу формування залишку зводиться до операції: (1) Ai+1( x) = Ai (x ) Å xm × Gn (x ), 30628 (13) постійну пам'ять 2n - 1 елементів кільця залишків по модулю G(x) з розрядністю кожного елемента кільця, рівною ступеню кодового багаточлена, який відрізняє ться тим, що для зменшення числа операцій перетворення інформаційної послідовності в послідовність залишку до однієї на 2 U 1 3 30628 Відомий спосіб отримання залишку по модулю незвідного багаточлена, який реалізований у пристрої для формування залишку по довільному модулю від числа [1]. Спосіб спрямований на зменшення часових витрат і передбачає представлення в паралельному коді і модуля, за яким обчислюється залишок, і самого числа, залишок якого обчислюється. Недоліком цього способу є велика кількість операцій додавання і, відповідно, суматорів за великої розмірності числа. Зокрема, для слова розрядності k, необхідно не менше, ніж k-1 суматорів. Найбільш близьким до пропонованого за технічною сутністю і результатом, що досягається, є спосіб отримання залишку по модулю незвідного багаточлена, що використовується в стандартних системах передавання даних [2], які відповідають міжнародним стандартам і працюють у режимі реального часу, для реалізації якого використовують регістр зсуву зі зворотними зв'язками, що реалізує рівняння: R( x ) = A( x) T -1 Gn ( x ) = å aj x j j =0 , (2) Gn ( x ) де А(х) - ділене - вихідний інформаційний поліном; j - номер біта у кодованому блоці даних; Gn(x) - дільник - кодовий поліном ступеня "n"; Т - число біт у коді числа А(х) (довжина інформаційного блоку) і Т≤2n-1; аj - кодовий елемент інформаційного полінома, що приймає значення "нуль" і "одиниця". Часова затримка при реалізації цього способу обчислення залишку не залежить від структури інформаційного багаточлена А(х), а залежить тільки від структури G(х), є постійною і дорівнює кількості ненульових символів кодового поліному (це чило називається вагою Хеммінга кодового поліному) [3]. В силу вказаної обставини цей спосіб можна застосовувати в системах передавання даних, що працюють у реальному масштабі часу. Недоліком цього способу є необхідність виконання на кожен біт блоку даних операцій додавання, число яких дорівнює вазі Хеммінга кодового поліному. Використання цього способу обчислення залишку вирішує завдання кодування/декодування у реальному масштабі часу, але ускладнює реалізацію обчислювача залишку у високошвидкісних системах, зокрема, реалізацію кодера на програмувальних матрицях або однокристальних мікроЕОМ. Ціль корисної моделі - спрощення способу отримання залишку по модулю незвідного багаточлена при одночасному скороченні числа операцій на кожен біт блоку даних. Технічним результатом пропозиції є зменшення числа виконуваних операцій додавання до однієї на кожен біт переданих даних. Сутність корисної моделі полягає в тому, що обчислення залишку, згідно з запропонованим способом, не передбачає виконання перетворень інформаційної послідовності А(х) за формулами (1) і (2), а передбачає виконання операцій над 4 елементами кільця залишків по модулю незвідного багаточлена Gn(х), які обчислюються як a j = xj , (3) Gn ( x ) n де j - номер елемента кільця і j Î [0, (2 -1)). Операцією обчислення залишку є процедура додавання з накопиченням тих елементів кільця, номери яких співпадають з номерами позицій ненульових елементів блока даних А(х). Результатом виконання цієї операції, яка може бути представлена у вигляді T -1 T -1 R( x ) = å a jx j j= 0 = å aj × aj , G n ( x) j=0 (4) є залишок інформаційного багаточлена А(х) по модулю незвідного багаточлена Gn(x), який співпадає з результатом перетворень за формулами (1) і (2). Звідси випливає, що: 1) елементи кільця можуть бути обчислені апріорно до початку сеансу зв'язку і, отже, не вимагати часових витрат на їх формування в процесі утворення залишку; 2) інформаційна послідовність А(х) є керуючою і забезпечує вибірку й накопичення тільки тих елементів кільця залишків по модулю незвідного багаточлена Gn(x), номери яких співпадають з номерами позицій ненульових елементів блока даних А(х); 3) вказаний спосіб забезпечує постійність затримки в силу наявності тільки однієї операції додавання на кожен біт блока даних. Варто відзначити, що в реальних умовах не завжди є можливість неоперативного обчислення елементів кільця залишків, наприклад, коли необхідно виконувати передавання даних каналами, які використовують різні поліноми. У цих випадках елементи кільця залишків по модулю незвідного багаточлена обчислюють у процесі формування залишку ітераційно за модифікованою формулою (3) виду a j = x × a j-1 , G( x ) (5) при цьому a 0 = 1. Це означає, що на початку процесу обчислення залишку (при надходженні початкового-нульового біта блока даних) завантажується початковий елемент кільця = залишків a 0 1. При надходженні наступних бітів даних елементи кільця залишків обчислюються ітераційно-циклічним зсувом попереднього елемента кільця на один розряд управо, якщо старший розряд попереднього елемента кільця рівний нулю, а, якщо старший розряд рівний одиниці, то додатково до результату циклічного зсуву додають по модулю два константу С(х)=G(x)Åхn-1. Список джерел: 1. Патент Російської федерації №2007033 "Устройство для формирования остатка по произвольному модулю от числа", авт. Петренко В.І., Чипига О.Ф., кл. Н03М7/18, опублікований 1994.01.30. 2. Рекомендація V-41 МККТТ. Женева. 1976р. 5 30628 Стор.349. 3. У. Питерсон, Э. Уэлдон. Коды, исправляющие ошибки. - Μ.: Мир, 1976. - с.594. 6