Генератор псевдовипадкових бітових послідовностей на основі клітинних автоматів

Реферат: Генератор псевдовипадкових бітових послідовностей на основі клітинних автоматів містить клітинний автомат. Генератор псевдовипадкових бітових послідовностей на основі клітинних автоматів містить матричну систему комутації, кожний перший вхід якої підключений до інформаційного виходу відповідної клітини клітинного автомату, кожна клітина якого містить тригер збудження та тригер стану, комутатор, блок логічних функцій та чотири диз'юнктори, вихід блока логічних функцій підключений до першого входу третього диз'юнктора, другий вхід якого підключений до входу установки клітини, інформаційні входи комутатора підключені до інформаційних виходів клітин околиці, а відповідний вихід комутатора підключений до відповідного першого входу четвертого диз'юнктора відповідної клітини околиці, другий вхід четвертого диз'юнктора підключений до входу сигналу збудження клітини. UA 93427 U (54) ГЕНЕРАТОР ПСЕВДОВИПАДКОВИХ БІТОВИХ ПОСЛІДОВНОСТЕЙ НА ОСНОВІ КЛІТИННИХ АВТОМАТІВ UA 93427 U UA 93427 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до обчислювальної техніки, до радіотехніки, систем зв'язку та може бути використана при формуванні ансамблів псевдовипадкових послідовностей для діагностування цифрових об'єктів та шифрування повідомлень. Відомий генератор псевдовипадкових послідовностей в кінцевому полі GF(3) [Патент України № 66502, Бюл. № 1, 2012 p.], що містить групу блоків дворозрядних регістрів, кількість яких дорівнює максимальному ступеню утворюючого полінома, комутатор та схему суматора за модулем три, блоки множення на два у вигляді перехресних ліній передачі даних, при цьому виходу суматора за модулем три підключаються до молодшого дворозрядного регістра, виходи якого підключаються до однойменних входів комутатора, виходи яких підключаються до входів суматора за модулем три. Недоліками даного пристрою є складність за рахунок використання значної кількості регістрів зсуву та зворотних зв'язків. Також в даному пристрої існує невисокий степінь випадковості, який залежить від завдання початкового поліному. Відомо генератор випадкової двійкової послідовності [Патент Росії № 2281603], що містить групу щонайменше з двох взаємозв'язаних генераторів періодичного імпульсного сигналу, джерело управляючого сигналу, блок формування випадкової імпульсної послідовності, вихідний регістр, в якому вихід кожного з генераторів групи зв'язаний з відповідним інформаційним входом блока формування випадкової імпульсної послідовності, інформаційний вихід якого зв'язаний з інформаційним входом регістра, вихід якого є виходом пристрою, а вихід джерела управляючого сигналу підключений до управляючого входу блока формування випадкової імпульсної послідовності і до тактового входу вихідного регістра. Кожний з генераторів періодичного імпульсного сигналу виконаний у вигляді інвертора, охопленого позитивним зворотним зв'язком. Блок формування випадкової імпульсної послідовності містить мультиплексор та лічильник, виходи якого підключені до адресного входу мультиплексора, прямі та інверсні інформаційні входи мультиплексора є інформаційними входами блока, лічильний вхід лічильника є управляючим входом блока формування, а вихід мультиплексора є виходом блока. Джерело управляючого сигналу складається з послідовно з'єднаних генератора періодичного сигналу та дільника частоти, вихід якого є виходом джерела управляючого сигналу. Недоліком даного пристрою є низька надійність функціонування за рахунок великої кількості зворотних зв'язків, а також великої кількості генераторів періодичного імпульсного сигналу, які потребують особистих налаштовувань. Найбільш близьким до генератора псевдовипадкових бітових послідовностей на основі клітинних автоматів, що заявляється, є генератор псевдовипадкових послідовностей на основі клітинних автоматів [Сухинин Б.М. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов./ Электронное научно-техническое издание "Наука и образование", - № 9, - 2010 г., - С. 16, - рис. 1], що містить два клітинних автомати, регістр зсуву з лінійними зворотними зв'язками, та суматори за модулем 2. Недоліком даного пристрою є низька надійність функціонування за рахунок використання генераторів псевдовипадкових послідовностей бітів на регістрах зсуву та застосування перетворювачів паралельних кодів у послідовні. Крім того, такий генератор використовує аналіз та обчислення значень значної кількості клітин на двох клітинних автоматах, що ускладнює апаратну реалізацію клітинних автоматів та знижує швидкодію самого пристрою. Задачею корисної моделі є підвищення швидкодії, надійності функціонування та підвищення степені випадковості формування двійкової послідовності. Дані характеристики покращуються за рахунок використання клітинного автомату, в якому кожна клітина по заданій функції та значенням сигналів від клітинного автомату обчислює біт на виході, а також визначає наступну клітину для формування наступного випадкового біту у наступний момент часу. Поставлена задача вирішується тим, що генератор псевдовипадкових бітових послідовностей на основі клітинних автоматів, що містить клітинний автомат, матричну систему комутації, кожний перший вхід якої підключений до інформаційного виходу відповідної клітини клітинного автомату, кожна клітина якого містить тригер збудження та тригер стану, комутатор, блок логічних функцій та чотири диз'юнктори, вихід блока логічних функцій підключений до першого входу третього диз'юнктора, другий вхід якого підключений до входу установки клітини, інформаційні входи комутатора підключені до інформаційних виходів клітин околиці, а відповідний вихід комутатора підключений до відповідного першого входу четвертого диз'юнктора відповідної клітини околиці, другий вхід четвертого диз'юнктора підключений до входу сигналу збудження клітини, а вихід четвертого диз'юнктора підключений до входу установки тригера збудження, вихід третього диз'юнктора підключений до входу установки тригера стану, вхід установки в нульовий стан якого підключений до входу обнулення клітини, 1 UA 93427 U 5 10 15 20 25 30 35 40 45 50 55 60 прямий вихід тригера стану підключений до інформаційного виходу клітини та до першого входу блока логічних функцій, другий вхід якого підключений до прямого виходу тригера збудження та до управляючого входу комутатора, третій вхід блока логічних функцій підключений до входу вхідної послідовності, четвертий, п'ятий, шостий, сьомий, восьмий, дев'ятий, десятий та одинадцятий входи блока логічних функцій підключені, відповідно, до інформаційних виходів клітин околиці власної клітини, вхід установки тригера збудження в нульовий стан підключений до виходу другого диз'юнктора, другий вхід якого підключений до входу сигналу обнулення збудження клітини, перший вхід другого диз'юнктора підключений до виходу першого диз'юнктора, кожний з восьми входів якого підключений до відповідних виходів тригерів збудження відповідних клітин околиці, а його вхід управління підключений до прямого виходу тригера збудження, вихід матричної системи комутації підключений до виходу пристрою, а кожний другий вхід її підключений до виходу тригера збудження відповідної клітини, вхід синхронізації підключений до входів синхронізації тригерів кожної клітини та входу синхронізації матричної системи комутації. На Фіг. 1 подано функціональну схему генератора псевдовипадкових бітових послідовностей на основі клітинних автоматів, на Фіг. 2 представлена схема можливої організації формування розрядів вхідної бітової послідовності, на Фіг. 3 - приклад функціонування генератора, на Фіг. 4 - інтерфейс програмної моделі процесу генерації бітових послідовностей, на Фіг. 5 - приклад сформованої бітової послідовності, а на Фіг. 6 - приклад сформованих десяткових чисел, поданих кодом довжиною вісім біт. Генератор псевдовипадкових бітових послідовностей на основі клітинних автоматів (Фіг. 1) містить клітинний автомат 1, матричну систему 2 комутації (МСК), кожний перший вхід 3 якої підключений до інформаційного виходу 4 відповідної клітини 5 клітинного автомата 1 (КА), кожна клітина 5 якого містить тригер 6 збудження (Т 3б) та тригер 7 стану (Т ст), комутатор 8 (К), блок 9 логічних функцій (БЛФ) та чотири диз'юнктори (10-13), вихід 14 БЛФ 9 підключений до першого входу третього диз'юнктора 12, другий вхід якого підключений до входу 15 установки клітини 5, інформаційні входи 16 К 8 підключені до інформаційних виходів 4 клітини околиці, а відповідний вихід 171, ….,178 K 8 підключений до відповідного першого входу 18 четвертого диз'юнктора 13 відповідної клітини 5 околиці, другий вхід 19 четвертого диз'юнктора 13 підключений до входу 20 сигналу збудження клітини 5, а вихід четвертого диз'юнктора 13 підключений до входу 21 установки Т 3б 6, вихід третього диз'юнктора 12 підключений до входу 22 установки Тст 7, вхід 23 установки в нульовий стан якого підключений до входу 24 обнулення клітини 5, прямий вихід Тст 7 підключений до інформаційного виходу 4 клітини 5 та до першого входу 25 БЛФ 9, другий вхід 26 якого підключений до прямого виходу 27 Т 3б 6 та до управляючого входу 28 К 8, третій вхід 29 БЛФ 9 підключений до входу 30 вхідної послідовності, четвертий, п'ятий, шостий, сьомий, восьмий, дев'ятий, десятий та одинадцятий входи 31,…, 38 БЛФ 9 підключені, відповідно, до інформаційних виходів 4 клітин 5 околиці власної клітини 5, вхід 39 установки Т3б 6 в нульовий стан підключений до виходу другого диз'юнктора 11, другий вхід якого підключений до входу 40 сигналу обнулення збудження клітини 5, перший вхід другого диз'юнктора 11 підключений до виходу першого диз'юнктора 10, кожний з восьми входів 41 підключений до відповідних виходів 27 Т 3б 6 відповідних клітин 5 околиці, а його вхід 42 управління підключений до прямого виходу 27 Т 3б 6, вихід 43 МСК 2 підключений до виходу пристрою, а кожний другий вхід 44 її підключений до виходу 27 Тзб 6 відповідної клітини 5, вхід 45 синхронізації підключений до входів 46, 47, Т 3б 6, Тст 7 кожної клітини 5 входу 48 синхронізації МСК 2. Схема (Фіг. 2) можливої організації формування розрядів вхідної послідовності складається з фрагменту КА 1, який складається з дев'яти клітин 5, інформаційні виходи 4 яких підключені до відповідних входів 49 комутаційної системи 50 (КС), інформаційні виходи 51 якої підключені до входів 30 розрядів послідовності відповідних клітин 5, інформаційні виходи лічильника 52 (Л) підключені до других інформаційних входів 53 КС 50. Генератор псевдовипадкових бітових послідовностей на основі КА (ГГТВПКА) функціонує в такий спосіб. Загальний алгоритм функціонування генератора складається з наступних кроків. 1. Записують карти станів у клітини КА. 2. Вибирають початкову клітину для розповсюдження сигналу збудження. 3. Проводять операцію додавання за модулем 2 значень сусідніх клітин околиці із значеннями власного стану та значенням відповідного розряду заданої послідовності. 4. Формують значення результуючого біту на виході генератора псевдовипадкових бітових послідовностей на основі клітинних автоматів. 5. Передають сигнал збудження одній із сусідніх клітин околиці по заданій функції. 2 UA 93427 U 5 10 15 20 25 30 35 40 45 50 55 Після передачі сигналу збудження відбувається повтор пунктів 3, 4, 5. Перший крок алгоритму характеризується встановленням усіх клітин 5 КА 1 у стани логічних "0" або "1". Установка клітин здійснюється по входах 15 установки (Фіг. 1). Сигнал з входу 15 через третій диз'юнктор 12 подається на вхід 22 установки Тст 7. На прямому виході Т ст 7 з'являється сигнал, який відповідає сигналу на його вході 22 установки. Другий крок алгоритму характеризується подачею одиничного сигналу на вхід 20 однієї з клітин 5 (вибрана початкова клітина 5 для розповсюдження сигналу збудження) КА 1. Даний сигнал подається на вхід 21 установки Т 3б 6, який встановлюється у стан логічної "1" (на прямому виході 27 присутній одиничний сигнал) Т 3б 6 встановлюється у відповідний стан по надходженню імпульсу синхронізації на вхід 45 синхронізації, який подається на синхровхід 46 Т3б 6. Отже клітина 5 КА 1 вважається такою, що знаходиться у збудженому стані, якщо її Т 3б 6 знаходиться у одиничному стані. На третьому кроці алгоритму одиничний сигнал з виходу 27 Т3б 6 подається на другий вхід 26 БЛФ 9, на управляючий вхід 28 К 8 та на відповідний другий вхід 44 МСК 2. БЛФ 9 здійснює додавання за модулем 2 значень сигналів клітин околиці, які подаються з їх виходів 4 на відповідні входи 31-38 БЛФ 9, значення власного стану, що подається на перший вхід 25 з прямого виходу Тст 7, та значення сигналу розряду вхідної послідовності, яке подається з входу 30 розряду вхідної послідовності клітини 5 на третій вхід 29 БЛФ 9. Згідно четвертого кроку алгоритму отриманий результуючий біт з виходу 14 БЛФ 9 подається на перший вхід третього диз'юнктора 12, з виходу якого даний сигнал подається на вхід 282 установки Тст 7. Тст 7 встановлюється у стан результуючого біту. З прямого виходу Т ст 7 сигнал поступає на відповідний перший вхід 3 МСК 2 і також подається на вихід 43 МСК 2 за рахунок того, що на відповідному другому вході 44 МСК 2 присутній одиничний сигнал від прямого виходу 27 Т3б 6 цієї ж клітини 5. Сигнал з першого входу 3 на вихід 43 МСК 2 подається в момент присутності синхросигналу на вході 48 синхронізації. На п'ятому кроці алгоритму сформований сигнал логічної "1" з'являється на одному з виходів 17 К 8. Сигнал з'являється на тому виході на який указують сигнали на входах 16, а також такт синхронізації та наявність одиничного сигналу на управляючому вході 28. З відповідного виходу 17, К 8 подаються на перший вхід 18 четвертого диз'юнктора 13 тієї і-ї клітини 5 околиці, до якої підключений даний вихід 17j. Коли клітина 5 околиці у наступний тактовий момент встановлюється у збуджений стан, з виходу 27 її Т 3б 6 одиничний сигнал подається на один з входів 41 першого диз'юнктора 10 і поступає на перший вхід другого диз'юнктора 11. На вході 39 обнулення Т 3б 6 з'являється одиничний сигнал, який переводить даний Т3б 6 у нульовий стан. Дана клітина 5 переходить у незбуджений стан. Таким чином, одна клітина околиці переходить у збуджений стан і обнулює стан збудження попередньої клітини. Клітина 5 функціонує в такий спосіб. У початковий момент часу обнуляються Т 3б 6 та Тст 7 по сигналах, що подаються на вхід 40 сигналу обнулення збудження та вхід 24 установки у стан логічного "0". З входу 40 сигнал через другий вхід другого диз'юнктора 11 подається на вхід 39 установки Т зб 6 в нульовий стан. З входу 24 сигнал поступає на вхід 23 установки Тст 7 у нульовий стан. Початок роботи ГПВПКА здійснюється встановленням Т ст 7 у стан логічного "0" або "1", подачею на вхід 15 установки відповідного сигналу. Якщо сигнал збудження у вигляді логічної "1" на вхід 20 збудження не поступає, то стани елементів клітини 5 не змінюються. З моменту надходження сигналу збудження на вхід 20 та вхід 21 Т 3б 6 встановлюється у одиничний стан. Починає функціонувати БЛФ 9 за рахунок надходження одиничного сигналу на його другий вхід 26 з прямого виходу 27 Тзб 6. БЛФ 9, згідно закладеної функції, формує на виході 14 заданий сигнал, який з виходу 14 поступає через перший вхід третього диз'юнктора 12 подається на вхід 22 установки Тст 7. К 8 враховує сигнали, що присутні на входах 16, та, згідно закладеної в ньому схемотехнічної функції, формує на одному з восьми виходів 17; сигнал збудження, який подається на один з входів четвертого диз'юнктора 13 і на вхід 21 установки Т 3б 6 вибраної клітини 5 околиці. Вибрана клітина переходить у збуджений стан. З виходу 27 вибраної клітини 5 околиці одиничний сигнал подається на один з входів 41 першого диз'юнктора 10 попередньої збудженої клітини 5. За рахунок присутності одиничного сигналу на управляючому вході 42 першого диз'юнктора 10, на його виході з'являється логічна "1", яка подається, через другий диз'юнктор 11, на вхід 39 обнулення Т зб 6. Т3б 6 переходить у нульовий стан, а клітина 5 стає не збудженою. Тобто, коли сусідня клітина 5 переходить у стан збудження, попередня збуджена клітина 5 обнуляється. 3 UA 93427 U 5 10 15 20 25 30 35 40 45 50 55 60 Приклад схеми формування додаткової вхідної послідовності на вході 30 подано на Фіг. 2. Вхідна додаткова бітова послідовність дозволяє позбавитись за циклювань та тупикових ситуацій при формуванні псевдовипадкової бітової послідовності. її можливо сформувати ззовні використовуючи різні засоби генерації бітової послідовності. Для досягнення більшої непередбачуваності формування додаткової бітової послідовності здійснюється з виходів клітин КА. Шляхом поступового перебору (підключення виходів) клітин формується додаткова бітова послідовність, яка складається із значень станів клітин КА. Згідно заданої послідовності перебору інформаційні виходи 4 кожної клітини 5 КА 1 підключаються до входу 30 розрядів послідовності відповідної збудженої клітини. Схема (Фіг. 2) формування додаткової бітової послідовності працює в такий спосіб. Клітини 5 КА 1 встановлюються в стани згідно початкової карти установки КА 1. Інформаційні виходи 4 усіх клітин 5 КА 1 підключені до відповідних входів 51 КС 50, виходи 49, якої підключені до відповідних входів 30 розрядів послідовності. Л 52 лічить імпульси синхронізації, які подаються на вхід 41 синхронізації. Код з виходів Л 52 подається на входи 53 КС 50. Даний код указує на клітину 5 КА 1, інформаційний вихід 4 якої через відповідний вхід 51 КС 50 підключається до відповідного виходу 49 КС 50. Значення сигналу на виході 4 вибраної клітини 5 подається з відповідного виходу 49 на входи 30 усіх клітин 5, але сприймається тільки збудженою клітиною, на виході 27 якої присутня логічна "1". Таким чином, в процесі функціонування ГПВПКА змінюються стани клітин, що призводить до зміни значень бітів вхідної додаткової послідовності. Змінюючи послідовність переключення входів 51 та виходів 49 КС 50 можливо змінювати послідовність підключення (перебору) інформаційних виходів 4 клітин 5 КА 1. На Фіг. 3 показано приклад функціонування ГПВГЖА. Як приклад представлено три часових такти формування трьох бітів на виході ГПВПКА. На першому такті показано зліва направо перший біт (логічний "0") додаткової бітової послідовності. Далі показано стан КА, який складається зі станів кожної клітини. Виділено першу збуджену клітину та клітини її околиці. З правого боку показано формулу, кожний член якої подає значення першого біту околиці (перша складова формули), значення станів клітин околиці (друга, третя, четверта, п'ята, шоста, сьома, восьма та дев'ята складові формули) та значення стану збудженої клітини (десята складова формули). Результатом формули (логічний "0") є результат стану збудженої клітини на наступному часовому такті. На другому такті збуджена клітина, яка визначається на першому такті як клітина околиці, що має стан логічної "1" з найбільшим номером в околиці клітин. На третьому такті збудженою клітиною є клітина околиці з попереднього такту, що має стан логічного "0" з найбільшим номером в околиці клітин. Отже, згідно прикладу, на парному такті аналізуються клітини околиці, які мають стан логічної "1", а на непарному такті аналізуються клітини околиці, що мають стан логічного "0". На Фіг. 4 представлено програмну модель, що моделює роботу запропонованого ГПВПКА. Показано три інтерфейси для різних режимів функціонування. Верхній інтерфейс показує початковий стан КА розміром 10×10. Одиниці у клітинах відповідають станам даних клітин логічної "1". Пусті клітини відповідають стану клітин логічного "0". Поле КА подано у верхньому лівому полі вікна програми. Другий інтерфейс показує автоматичний режим роботи генератора. В даному режимі у полі КА виділена збуджена клітина та виділена її околиця. Указано кількість кроків роботи генератора. У правій частині інтерфейсу у виділеному полі подано біти сформованої бітової послідовності. Третій інтерфейс показує роботу генератора у покроковому режимі. Даний режим дозволяє оцінити роботу на кожному кроці і перевірити правильність функціонування. На Фіг. 5 показано приклад сформованої бітової послідовності для прикладу, поданого на Фіг. 4. На Фіг. 6 показано приклад послідовності десяткових чисел, яка отримана розбиттям вихідної бітової послідовності на групи по 8 біт і перетворення у десяткове число. Запропонований ГПВПКА дозволяє підвищити надійність функціонування за рахунок спрощення схеми та зменшення кількості зворотних зв'язків та заданої організації клітин КА і зв'язків між ними. Підвищено швидкодію за рахунок швидкої передачі сигналів між клітинами околиці, а також за рахунок того, що час формування одного біту залежить від часу спрацьовування тригера та комбінаційної схеми, яка реалізується декількома логічними елементами. Крім того, підвищується степінь непередбачуваності біту на виході та збільшується період повторення послідовності за рахунок формування додаткової бітової послідовності самим КА, стани якого змінюються в процесі генерації вихідної послідовності. Випадковість 4 UA 93427 U досягається також за рахунок вільного формування карти станів та вибору першої збудженої клітини. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 5 10 15 20 25 30 Генератор псевдовипадкових бітових послідовностей на основі клітинних автоматів, що містить клітинний автомат, який відрізняється тим, що містить матричну систему комутації, кожний перший вхід якої підключений до інформаційного виходу відповідної клітини клітинного автомата, кожна клітина якого містить тригер збудження та тригер стану, комутатор, блок логічних функцій та чотири диз'юнктори, вихід блока логічних функцій підключений до першого входу третього диз'юнктора, другий вхід якого підключений до входу установки клітини, інформаційні входи комутатора підключені до інформаційних виходів клітин околиці, а відповідний вихід комутатора підключений до відповідного першого входу четвертого диз'юнктора відповідної клітини околиці, другий вхід четвертого диз'юнктора підключений до входу сигналу збудження клітини, а вихід четвертого диз'юнктора підключений до входу установки тригера збудження, вихід третього диз'юнктора підключений до входу установки тригера стану, вхід установки в нульовий стан якого підключений до входу обнулення клітини, прямий вихід тригера стану підключений до інформаційного виходу клітини та до першого входу блока логічних функцій, другий вхід якого підключений до прямого виходу тригера збудження та до управляючого входу комутатора, третій вхід блока логічних функцій підключений до входу вхідної послідовності, четвертий, п'ятий, шостий, сьомий, восьмий, дев'ятий, десятий та одинадцятий входи блока логічних функцій підключені, відповідно, до інформаційних виходів клітин околиці власної клітини, вхід установки тригера збудження в нульовий стан підключений до виходу другого диз'юнктора, другий вхід якого підключений до входу сигналу обнулення збудження клітини, перший вхід другого диз'юнктора підключений до виходу першого диз'юнктора, кожний з восьми входів якого підключений до відповідних виходів тригерів збудження відповідних клітин околиці, а його вхід управління підключений до прямого виходу тригера збудження, вихід матричної системи комутації підключений до виходу пристрою, а кожний другий вхід її підключений до виходу тригера збудження відповідної клітини, вхід синхронізації підключений до входів синхронізації тригерів кожної клітини та входу синхронізації матричної системи комутації. 5 UA 93427 U 6 UA 93427 U 7 UA 93427 U 8 UA 93427 U 9 UA 93427 U Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 10