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

Реферат: Спосіб отримання псевдовипадкової послідовності на основі використання матриці зв'язків в кінцевому полі GF(3) належить до обчислювальної техніки та може використовуватися у системах діагностування цифрових об'єктів. UA 67874 U (54) СПОСІБ ОТРИМАННЯ ПСЕВДОВИПАДКОВОЇ ПОСЛІДОВНОСТІ НА ОСНОВІ ВИКОРИСТАННЯ МАТРИЦІ ЗВ'ЯЗКІВ В КІНЦЕВОМУ ПОЛІ GF(3) UA 67874 U UA 67874 U 5 10 15 20 25 30 35 40 Корисна модель належить до обчислювальної техніки та може використовуватися у системах діагностування цифрових об'єктів. Відомий "Спосіб представлення часових послідовностей з використанням оператора затримки" [1], який полягає у тому, що вхідна інформаційна послідовність представляється як багаточлен f(x), а вихідна послідовність представляється у вигляді багаточлену с(х). Пристрій кодування описується як пристрій, що виконує операції множення інформаційного багаточлену f(x) на багаточлен g(x), який породжує цей код, а саме c(x)=f(x)-g(x). Недоліком такого способу є те, що із збільшенням довжини кодового обмеження складність (кількість арифметичних операцій множення та складання) швидко зростає. Найбільш близьким технічним рішенням до того, що пропонується, вибраним як прототип, є спосіб матричного опису циклічних кодів [2], основою яких є регістр зсуву зі зворотними зв'язками, який полягає в тому, що для опису вихідної послідовності використовуються матриця зв'язків та матриця станів. Недоліком способу-прототипу є складність отримання вихідних станів за рахунок великої кількості арифметичних операцій множення та складання елементів матриць. В основу корисної моделі поставлена задача створення способу отримання псевдовипадкової послідовності на основі використання матриці зв'язків в кінцевому полі GF(3), заснований на виявленні кільцевої закономірності формування стовпців матриці зв'язків згідно з виглядом утворюючого характеристичного примітивного неприведеного полінома. Поставлена задача вирішується за рахунок того, що у відомому способі отримання псевдовипадкової послідовності на основі регістрів зсуву зі зворотними стовпцями взаємодія між регістрами описана матрицею зв'язків S, але для рахування всіх елементів матриці станів Н пропонується використовувати тільки стовпці матриці зв'язків різних ступенів, які й є відповідними стовпцями матриці станів регістрів зсуву зі зворотними стовпцями. Позитивним технічним рішенням є те, що отримано спосіб отримання псевдовипадкової послідовності в кінцевому полі GF(3) зі зменшенням операцій обробки елементів матриць для поліномів, які мають максимальний період генерації. Цей спосіб дозволяє визначити всі стовпці перевірочної матриці на основі кільцевого розташування стовпців матриці зв'язків. При пошуку в патентній та науково-технічній літературі не виявлено об'єктів з ознаками, подібними до відмінних ознак технічного рішення, що заявляється, на підставі чого можна зробити висновок про відповідність його критерію "суттєві відмінності". Технічний результат, що може бути отриманий при здійсненні корисної моделі полягає в тому, що запропонований спосіб без виконання арифметичних операцій над матрицею станів дозволяє визначити всі її стовпці на основі кільцевої закономірності матриці зв'язків. Стовпці матриці зв'язків є вихідною послідовністю регістрів зсуву зі зворотними стовпцями у r r-1 відповідності до примітивного неприведеного характеристичного поліному Р(х)=аrх  аr-1х  …  ах 3 a0, який утворює період циклу генерації максимальної довжини. Суть запропонованого способу полягає в наступному. Спочатку вибирається утворюючий поліном. Потім будується матриця зв'язків S першого ступеня, яка описує зв'язки входів та виходів регістра зсуву зі зворотними зв'язками відповідно до утворюючого характеристичного поліному. Матриця зв'язків S має вигляд: a1 a 2 ... a r 1 a r 1 0 ... 0 S  0 1 0 ... 0 ... 0 0 0 0 , ... 1 0 де r=degP(x) 4 3 Наприклад, для Р(х) =х 3 х 3 1 матриця зв'язків буде мати вигляд: 0 0 1 1 45 S 1 0 0 0 0 1 0 0 0 0 1 0 . Вільний член a0 утворюючого характеристичного поліному Р(х)=а1х 3 аr-1х 3 … 3 ах 3 а0 однозначно описує перший стан h1 матриці станів Н та дорівнює: h1=||a00…0||. Наприклад, 4 3 4 2 для Р1(х)=2x 3 2x 3 1 перший стан h1=||1000||, а для Р2(х)=х 3 x 3 2 перший стан h1=||2000||. r 1 r-1 UA 67874 U Кожен стовпець матриці зв'язків представляє собою один із стовпців матриці станів Н 4 регістра псевдовипадкової послідовності. Усічена матриця станів H(1-16) для поліному Р(х)=х 3 3 x 3 1 має вигляд: Рг1 Рг2 Рг3 Рг4 1 0 0 0 1 0 1 0 0 2 0 0 1 0 3 1 0 0 1 4 1 1 0 0 5 0 1 1 0 6 1 0 1 1 7 2 1 0 1 8 1 2 1 0 9 1 1 2 1 10 0 1 1 2 11 0 0 1 1 12 2 0 0 1 13 1 2 0 0 14 0 1 2 0 15 2 0 1 2 16 5 10 В цій матриці Рг1-Рг4 позначають стани відповідного 2-розрядного регістра зсуву зі зворотними зв'язками, вибраними відповідно до утворюючого полінома. Для кожного поліному з максимальним періодом генерації є своя закономірність кільцевого 4 3 розташування стовпців матриць зв'язку. Наприклад, для Р(х)=х 3 x 3 1 розташування елементів буде таким: 0 0 1 1 1 0 0 0 S1  0 1 0 0 0 0 1 0  h 2 h 3 h 4 h1 ; 0 1 1 0 S2  0 0 1 1 S3  0 1 1 0 1 0 0 0 0 1 0 0  h3h 4h5h 2 ; 1 1 0 0 0 0 1 1 1 0 0 0  h 4 h 5 h 6 h 3 й так далі. Отже, узагальнена формула розрахунків ступенів матриці зв'язків для Р(х)=х 3 x 3 1 має вигляд: i S =||hi+1 hi+2 hi+3 hi|| 4 3 Для поліному P(х)=х 3 x 3 1 усічена матриця станів H(1-16) має вигляд: 4 15 Рг1 Рг2 Рг3 Рг4 20 1 0 0 0 1 1 1 0 0 2 1 1 1 0 3 1 1 1 1 4 2 1 1 1 5 0 2 1 1 6 1 0 2 1 7 2 1 0 2 8 1 2 1 0 9 1 1 2 1 10 2 1 1 2 11 1 2 1 1 12 2 1 2 1 13 3 0 2 1 2 14 2 0 2 1 15 0 2 0 2 Для цього полінома розташування елементів буде таким: 1 0 0 1 S1  1 0 0 0 0 1 0 0 0 0 1 0  h 2 h 79 h 80 h1 ; 1 0 1 1 S2  1 0 0 1 1 0 0 0 0 1 0 0  h 3 h 80 h1h 2 ; 1 1 1 1 S3  1 0 1 1 1 0 1 1 1 0 0 0  h 4 h1h 2 h 3 й так далі Отже, узагальнена формула розрахунків ступенів матриці зв'язків для Р(х)=х 3 х 3 1 має вигляд: i S =||hi+1 hi-2 hi-1 hi|| 4 25 2 UA 67874 U 5 10 15 20 25 Таким чином, для кожного полінома є своя закономірність розміщення стовпців перевірочної i матриці Н в матриці зв'язків S . При чому, для наведених прикладів всі стовпці матриці станів отримуються зі стовпця, який розташовується останнім. Тобто, ці стовпці отримуються шляхом відповідного зсуву останнього стовпця в регістрі зсуву зі зворотними зв'язками. Отримані узагальнені формули дозволяють знайти всі інші стовпці на основі відомого одного шляхом його зсуву. Спосіб, що пропонується, може бути реалізований, наприклад, за допомогою пристрою, структурна схема якого в загальному вигляді наведена на кресленні. Пристрій включає: блок 1 керування видачею псевдовипадкових даних; групу з n блоків регістрів 21-2n збереження матриць зв'язків різних ступенів та групу 3 r-розрядних вихідних станів. Пристрій працює наступним чином. В регістрах блоків 21-2n занесені матриці зв'язку відповідних ступенів, кожен стовпець якої є одним зі станів матриці Н. Блок керування 1 послідовно за вибраним для кожного поліному алгоритмом подає сигнали зчитування. В результаті чого r-розрядні стани через блок 3 передаються на вихід схеми. Кожен блок 2i видає свої стани, які не повинні бути повторені, щоб не порушити псевдовипадкову послідовність. Блок керування 1 забезпечує видачу відповідних до вибраного алгоритму даних. Причому, починати видавати r-розрядні дані можна з якого завгодно стану. Запропонований спосіб, визначений у вигляді отриманого виразу, дозволяє визначити всі стовпці матриці станів Н без виконання підрахунків та бути застосованим при визначенні вихідної послідовності з використанням примітивного неприведеного характеристичного поліному, який утворює період циклу генерації максимальної довжини. Джерела інформації: 1. Теория кодирования: Пер. с япон. /Т. Касами, Н. Токура, Е. Ивадари, Я. Инагаки /Под ред. Б.С. Цыбакова и С.И. Гельфанда. - М.: Мир. - 1978. - С. 226-230. 2. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. - М.: Мир. 1986. - С. 128-131 (прототип). ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 35 Спосіб отримання псевдовипадкової послідовності на основі використання матриці зв'язків в кінцевому полі GF(3), який полягає в тому, що для опису вихідної послідовності використовуються матриця зв'язків та матриця станів, який відрізняється тим, що для визначення всіх станів матриці станів визначається відповідна закономірність кільцевого розташування стовпців матриці зв'язків для регістра зсуву зі зворотними зв'язками, вибраними у відповідності до примітивного неприведеного характеристичного поліному, що утворює період циклу генерації максимальної довжини. 3 UA 67874 U Комп’ютерна верстка В. Мацело Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4