Генератор псевдовипадкової послідовності на основі використання матриці зв’язків першого ступеня в кінцевому полі gf(3)

Реферат: Генератор псевдовипадкової послідовності на основі використання матриці зв'язків першого ступеня в кінцевому полі GF(3) містить дворозрядний регістр збереження стану генератора та суматор за модулем три. В нього введені дворозрядний регістр для збереження матриці зв'язків першого ступеня та блок множення. UA 67880 U (54) ГЕНЕРАТОР ПСЕВДОВИПАДКОВОЇ ПОСЛІДОВНОСТІ НА ОСНОВІ ВИКОРИСТАННЯ МАТРИЦІ ЗВ'ЯЗКІВ ПЕРШОГО СТУПЕНЯ В КІНЦЕВОМУ ПОЛІ GF(3) UA 67880 U UA 67880 U 5 10 15 20 25 30 35 40 45 Корисна модель належить до обчислювальної техніки та може використовуватися у системах тестового діагностування цифрових пристроїв, циклічного кодування, імовірнісного моделювання, криптографії, створення штучних завад. Відомий пристрій [1], який містить три групи регістрів зсуву, n груп по n двовходових елементів "І", nn - входових суматорів по модулю два, генератор тактових імпульсів, блок керування, блок завдання початкового стану, шину "Установка" та групу з nn двовходових елементів "І". Недоліком відомого пристрою є неможливість генерування псевдо випадкової послідовності з трьома станами. Найбільш близьким до того, що пропонується технічним рішенням, вибраним як прототип, є пристрій [2], який містить групу блоків дворозрядних регістрів, групу блоків множення на два за модулем три, комутатор та схему суматора за модулем три. Основним недоліком такого пристрою є складність зміни полінома за рахунок складного керування комутатором. В основу корисної моделі поставлена задача створення пристрою з розширенням функціональних можливостей технічної реалізації генератора за рахунок генерування третього стану сигналу з використанням будь-яких поліномів без використання регістра зсуву. Задача вирішується тим що, у відомий генератор псевдовипадкових послідовностей, який містить дворозрядний регістр та суматор за модулем три додатково введені дворозрядний регістр для збереження матриці зв'язків першого ступеня та блок множення. Генерування псевдовипадкової послідовності в кінцевому полі GF(3) в залежності від вибраного утворюючого поліному виконується завдяки перемноженню за модулем три попереднього стану генератора на матрицю зв'язків першого ступеню. Матриця зв'язків першого ступеню розміром (r  r) розрядів описує взаємозв'язок входів та виходів дворозрядного класичного регістра, зворотні зв'язки якого вибрані відповідно до вигляду характеристичного не приведеного примітивного поліному, який генерує період циклу генерації максимальної довжини. Позитивним технічним рішенням є те, що отримано пристрій, який дозволяє генерувати псевдовипадкову послідовність в кінцевому полі GF(3) для будь-якого поліному, який генерує послідовність максимальної довжини, та генерування цієї послідовності з будь-якого стану без використання регістра зсуву. При пошуку в патентній та науково-технічній літературі не виявлено об'єктів з ознаками, подібними до відмінних ознак технічного рішення, що заявляється, на підставі чого можна зробити висновок про відповідність його критерію "суттєві відмінності". Технічний результат, що може бути отриманий при здійсненні корисної моделі, полягає в тому, що запропонований пристрій генерує псевдовипадкову послідовність в кінцевому полі GF(3) для будь-якого примітивного не приведеного характеристичного поліному, який утворює період циклу генерації максимальної довжини без використання регістра зсуву. На кресленні наведена схема генератора псевдовипадкової послідовності в кінцевому полі GF(3) на основі використання матриці зв'язків першого ступеня, який містить дворозрядний регістр 1 збереження матриці зв'язків першого ступеня, дворозрядний регістр 2 збереження стану генератора, блок 3 перемноження значень регістра зв'язків першого ступеня на стан регістра, суматор 4 за модулем три та групу 5 вихідних станів генератора. Сигнали синхронізації та ланцюги початкового встановлення регістрів на схемі не наведені. Для побудови генератора спочатку будується матриця зв'язків S першого ступеня, яка описує зв'язки входів та виходів регістра зсуву зі зворотними зв'язками згідно з утворюючим характеристичним поліномом, який генерує псевдовипадкову послідовність максимальної довжини: a1a 2 ... ar 1ar 1 0 ... 0 0 S , 0 1 0 ... 0 0 .... 0 0 ... 1 0 50 де r=degP(x). Коефіцієнти а1, а2, … аr-1, аr, які розміщені в першому рядку матриці зв'язків позначують наявність зворотних зв'язків через суматор за модулем три виходів 2-розрядних регістрів з вагою відповідного коефіцієнта ( ai  0, 1, 2 ) згідно до обраного утворюючого полінома зі входами першого регістра. 4 Наприклад, для Р(х) = х 3 2x 3 3 2 матриця зв'язків має вигляд: 1 UA 67880 U 0 0 2 1 S 1 0 0 0 0 1 0 0 0 0 1 0 Вільний член а0 утворюючого характеристичного поліному Р(х) = arx  3 ar-1x  3…  3 ах  3 а0 однозначно описує перший стан h1 матриці станів Η та дорівнює: h  a 0...0 . Наприклад, 1 0 r 5 r-1 4 3 для полінома в кінцевому полі GF(3) Р(х) = x  2 ×  2 перший стан h1  20...0 . Інші стани hi матриці станів Η знаходяться в результаті перемноження матриці стовпця hi-1 з 1 попереднім індексом на матрицю зв'язків S першого ступеня. В загальному випадку матриця станів містить всі стани регістра та має вигляд:   h1h2 ...hi ...hn 10 15 20 25 для n-розрядної вихідної псевдовипадкової послідовності. Зміна полінома виконується за рахунок завантаження відповідної матриці зв'язків першого ступеню в регістр 1, а зміна початкового стану - за рахунок завантаження відповідного стану в регістр 2. Пристрій працює наступним чином. Перед початком роботи в регістр 1 заноситься значення матриці зв'язків першого ступеня, а в регістр 2 - початкове значення стану hi генерації полінома. З подачею імпульсу синхронізації виконується множення r-розрядного стану hi на квадратну r  r матрицю зв'язків першого ступеня, обчислення результату за модулем три в блоці 4, видача значення генерації на вихід 5 схеми та подальше занесення цього значення в регістр 2 збереження поточного стану. Якщо в регістрі 2 початковим значенням є стан hb то стан генерації на виході 5 схеми буде наступним, тобто h2. Стан hi на виході 5 схеми буде виданий на наступному циклі генерації полінома. Причому, починати видавати r-розрядні псевдовипадкові послідовності можна з якого завгодно початкового стану в регістрі 2 у відповідності до вибраного поліному, який генерує період максимальної довжини. Джерела інформації: 1. Патент на винахід № 86401, Україна, МПК G06F 7/58. Генератор псевдовипадкових двійкових послідовностей. /Н.В.Олійник, М.М. Солощук. - № U200609286; Заяв. 23.08.2006; опубл. 27.04.2009; Бюл. № 8-12с. 2. Патент на винахід № 47876, Україна, МПК G06F 7/58. Генератор псевдовипадкових послідовностей. /О.М. Рисований, О.В.Коломійцев, В.В.Гоготов. - № U200909574; Заяв. 18.09.2009; опубл. 25.02.2010; Бюл. № 4-6 с. (прототип). 30 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 35 40 Генератор псевдовипадкової послідовності на основі використання матриці зв'язків першого ступеня в кінцевому полі GF(3), який містить дворозрядний регістр збереження стану генератора та суматор за модулем три, який відрізняється тим, що в нього введені дворозрядний регістр для збереження матриці зв'язків першого ступеня та блок множення, причому виходи регістра збереження матриці станів з'єднані з першою групою входів блока множення, виходи якого підключені до блока суматорів за модулем три, виходи якого підключені до групи вихідних сигналів та до входів регістра збереження матриці станів, виходи регістра зв'язку першого ступеня підключені до другої групи входів блока множення. 2 UA 67880 U Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3