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

Реферат: Спосіб опису генераторів псевдовипадкової послідовності на основі використання матриці зв'язків першого ступеня в кінцевому полі GF(3) полягає в тому, що для опису вихідної послідовності використовують матрицю зв'язків та перевірочну матрицю. Вихідні сигнали схеми отримують в результаті перемноження сигналів з регістра збереження попереднього стовпця перевірочної матриці на сигнали з регістра збереження матриці зв’язків першого ступеня. UA 71580 U (12) UA 71580 U UA 71580 U 5 Корисна модель належить до обчислювальної техніки та може використовуватися у системах діагностування цифрових об'єктів. Відомий "Спосіб представлення часових послідовностей з використанням оператору затримки" [1], який полягає у тому, що вхідна інформаційна послідовність представляється як багаточлен f (x) , а вихідна послідовність представляється у вигляді багаточлена c( x ) . Пристрій кодування описується як пристрій, що виконує операції множення інформаційного багаточлена f (x) на багаточлен g( x ) , який породжує цей код, а саме c(x)  f (x)  g(x) . 10 15 20 25 30 Недоліком такого способу є те, що із збільшенням довжини кодового обмеження складність (кількість арифметичних операцій множення та складання) швидко зростає. Найбільш близьким до того, що пропонується, технічним рішенням, вибраним як прототип, є спосіб матричного опису циклічних кодів [2], основою яких є регістр зсуву зі зворотними зв'язками, який полягає в тому, що для опису вихідної послідовності використовуються матриця зв'язків та матриця станів. Недоліками способу-найближчого аналога є: складність побудованих генераторів за рахунок того, що формування вихідних сигналів відбувається за змістом перевірочної матриці, в якій крім коефіцієнтів багаточлена використовується одинична матриця, значення якої необхідно компенсувати додатковими елементами схеми; неможливість використання поліномів без додаткового перетворення схеми. В основу корисної моделі поставлена задача створення опису генераторів псевдовипадкової послідовності в кінцевому полі GF(3) для спрощення технічної реалізації та збільшення функціональної можливості схеми за рахунок використання утворюючих поліномів без додаткового перетворення схеми. Поставлена задача вирішується тим, що в способі опису генераторів псевдовипадкової послідовності виконаних на основі регістрів зсуву зі зворотними стовпцями, взаємодія між регістрами описана матрицею зв'язків S, але для рахування всіх елементів матриці станів H вводиться стан першого стовпця h1 матриці станів, а інші стани hi , матриці отримуються в результаті перемноження попереднього стовпця hi1 матриці H на відому матрицю зв'язків S1 першого ступеня. Позитивним технічним рішенням є те, що отримано спосіб опису генераторів псевдовипадкової послідовності, який дозволяє визначити всі стовпці матриці станів на основі відомого попереднього стану hi , матриці станів H та матриці зв'язків S першого ступеня, яка залежить тільки від вигляду примітивного неприведеного характеристичного поліному P( x )  r x r 3 r 1xr 1 3 ...  3 x 3  0 , 35 40 що утворює період циклу генерації максимальної довжини. Технічний результат, що може бути отриманий при здійсненні корисної моделі, полягає в тому, що запропонований спосіб дозволяє алгебраїчно підрахувати стовпці матриці станів в кінцевому полі GF(3) та бути застосованим при визначенні вихідної послідовності з використанням примітивного неприведеного характеристичного полінома, що утворює період циклу генерації максимальної довжини. Суть запропонованого способу полягає в наступному. Спочатку будується матриця зв'язків S першого ступеня, яка описує зв'язки входів та виходів регістра зсуву зі зворотними зв'язками, згідно з утворюючим характеристичним поліномом: 1  2 ... r 1 r 1 0 ... 0 0 S  0 1 0 ... 0 0 , ... 0 0 45 ...1 0 де r  derP(x) . Коефіцієнти 1 ,  2 , ... r 1,  r , які розміщені в першому рядку матриці зв'язків позначують наявність зворотних зв'язків через суматор за модулем три виходів 2-розрядних регістрів з вагою відповідного коефіцієнта (i  0,1, 2) , згідно з вибраним утворюючим поліномом зі входами першого регістра. Наприклад, для P( x )  x 4  3 x 3  3 1 матриця зв'язків буде мати вигляд: 1 UA 71580 U 0 0 1 1 S 1 0 0 0 0 1 0 0 0 0 1 0 . Вільний член утворюючого 0 P( x )  r x r 3 r 1xr 1 3 ...  3 x 3  0 характеристичного полінома однозначно описує перший стан h1 матриці станів H та дорівнює: h1  0 0...0 . Наприклад, для P1( x )  x 4 3 x 3 3 1 перший стан h1  1000 , а для 5 P2 ( x )  x 4  3 x 3  3 2 перший стан h1  2000 . Різниця між циклами генераціїполіномів P ( x ) та 1 P2 ( x) , які є характеристичними, неприведеними та примітивними, полягає в тому, що вони мають інверсні один до одного півперіоди генерації максимальної довжини. Для отримання інших станів перевірочної матриці Н необхідно попередній стан перевірочної матриці помножити за модулем три на матрицю зв'язків першого ступеня, наприклад, для 10 P( x )  x 4  3 x 3  3 1: 1 h2  h1 3 S1  0 0 1 1 0 1 0 0 0 0 0  0 1 0 0 0 0 1 0 0 h3  h 2 3 S1  1 0 0 0  0 0 1 1 1 0 0 0  0 1 0 0 0 0 1 0 1 0 0 0  0  1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 1 1 h5  h 4 3 S1  0 1 0 0 0 ; 1 h 4  h3 3 S1  15 ; 1 0 0 1   0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 ; 1  1 0 0 ; і так далі. Інші стани hi перевірочної матриці Н знаходяться в результаті перемноження за модулем три матриці стовпця hi1 з попереднім індексом на матрицю зв'язків S1 першого ступеня. Таким чином, hi  hi 1  3 S1 . 20 25 30 Спосіб, що пропонується, може бути реалізований, наприклад, за допомогою пристрою, структурна схема якого в загальному вигляді наведена на кресленні. Пристрій включає: регістр 1 збереження квадратної матриці зв'язків S1 розміром r  r , де r  degP(x) ; групу з n блоків регістрів 21  2n збереження матриць стовпців станів; n блоків 31  3n множення за модулем три та групу 4 n-розрядних станів. Ланцюги синхронізації на схемі не наведено. Пристрій працює наступним чином. На всі блоки регістрів 21  2n та блоки 31  3n множення послідовно подаються синхросигнали, які дозволяють видавати по черзі всі стани генератора від h1 до hn . Причому, починати видавати r-розрядні дані можна починати з якого завгодно стану. Таким чином, за рахунок відповідних з'єднань сигналів з регістра збереження матриці зв'язків першого ступеня з сигналами з регістрів збереження матриць стовпців станів досягається отримання схеми зі спрощенням її технічної реалізації та збільшення функціональної можливості схеми шляхом використання різних утворюючих поліномів без додаткового перетворення схеми. 2 UA 71580 U 5 Джерела інформації: 1. Теория кодирования: Пер. с япон. /Т. Касами, Н. Токура, Е. Ивадари, Я. Инагаки /Под ред. Б.С. Цыбакова и С.И. Гельфанда. - М.: Мир.-1978. - С. 226-230. 2. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. - М: Мир.1986. - С. 128-131 (прототип). ФОРМУЛА КОРИСНОЇ МОДЕЛІ 10 Спосіб опису генераторів псевдовипадкової послідовності на основі використання матриці зв'язків першого ступеня в кінцевому полі GF(3), який полягає в тому, що для опису вихідної послідовності використовують матрицю зв'язків та перевірочну матрицю, який відрізняється тим, що вихідні сигнали схеми отримують в результаті перемноження сигналів з регістра збереження попереднього стовпця перевірочної матриці на сигнали з регістра збереження матриці зв’язків першого ступеня. Комп’ютерна верстка Л. Ціхановська Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3