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

Реферат: Генератор псевдовипадкової послідовності на основі використання першого стовпця матриці станів в кінцевому полі GF(3) належить до обчислювальної техніки та може використовуватися у системах тестового діагностування цифрових пристроїв, циклічного кодування, імовірнісного моделювання, криптографії, створення штучних завад. UA 67872 U (54) ГЕНЕРАТОР ПСЕВДОВИПАДКОВОЇ ПОСЛІДОВНОСТІ НА ОСНОВІ ВИКОРИСТАННЯ ПЕРШОГО СТОВПЦЯ МАТРИЦІ СТАНІВ В КІНЦЕВОМУ ПОЛІ GF(3) UA 67872 U UA 67872 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 регістрів збереження матриць зв'язків відповідних ступенів, причому регістр 2 1 зберігає матрицю зв'язків першого ступеня, а регістр 2 2 - матрицю зв'язків поточного ступеня; групу 3 блоків перемноження, причому блок 3 1 виконує перемноження значень регістра 21 матриці зв'язків першого ступеня на регістр 22 матриці зв'язків поточного ступеня, а блок 32 виконує перемноження отриманої матриці зв'язків поточного ступеня на перший стан генератора з регістра 1; суматор 4 за модулем три та групу 5 вихідних станів генератора. Сигнали синхронізації та ланцюги початкового встановлення регістрів на схемі не наведені. 4 3 Наприклад, матриця зв'язків для Р(х)=х 3 2 × 3 2 має вигляд: 0 0 2 1 S 50 1 0 0 0 0 1 0 0 0 0 1 0. Вільний член α0 утворюючого характеристичного поліному Р(х)=аrх 3 аr-1х 3 … 3 ax: 3 а0 однозначно описує перший стан h1 матриці станів Н та дорівнює: h1=||20…0||. Наприклад, для 4 3 полінома в кінцевому полі GF(3) Р(х)=х  2 ×  2 перший стан h1=||20…0||. Інші стани hi матриці станів Н знаходяться в результаті перемноження матриці стовпця першого стану hi на матрицю зв'язків ступеня з показником ступеня на одиницю меншим, ніж номер стану генерації полінома, який утворює період циклу максимальної довжини. r 55 1 r-1 UA 67872 U 5 10 15 В загальному випадку матриця станів містить всі стани регістра та має вигляд: H=|h1 h2… hi … hn| для n-розрядної вихідної псевдовипадкової послідовності. Пристрій працює наступним чином. Перед початком роботи дворозрядний регістр 1 містить початковий стан генерації, дворозрядний регістр 21 – значення матриці зв'язків першого ступеня, дворозрядний регістр 22 - одиничну матрицю. З подачею першого імпульсу синхронізації в блоці 31 виконується множення значень дворозрядних регістрів 21 на 22 та перемноження в блоці 32 отриманого результату на значення регістру 1 й подальшого занесення результату блока 31 в регістр 22 для збереження матриці зв'язків наступного ступеня. Вихідний стан у вигляді матриці-стовпця розрядністю r через суматор 4 за модулем три видається на вихід 5 схеми генератора. З подачею кожного нового імпульсу синхронізації регістр 22 зберігає матрицю зв'язків відповідного ступеня. Джерела інформації: 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 с. (прототип). 20 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 25 30 Генератор псевдовипадкової послідовності на основі використання першого стовпця матриці станів в кінцевому полі GF(3), який містить регістр збереження першого стану генератора та суматор за модулем три, який відрізняється тим, що в нього введені дворозрядний регістр для збереження матриці зв'язків першого ступеня, дворозрядний регістр для збереження матриці зв'язків поточного ступеня, перший та другий блоки множення, причому виходи регістра збереження матриць зв'язків першого ступеня з'єднані з першими входами першого блока множення, до других входів яких підключені виходи регістра збереження матриці зв'язків поточного ступеня, виходи першого блока множення підключені як до входів регістра збереження матриці зв'язків поточного ступеня, так й до перших входів другого блока множення, до других входів якого підключені виходи регістра збереження першого стану генератора, виходи другого блока множення підключені до входів суматора за модулем три, виходи якого підключені до виходів генератора. Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 2