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

Реферат: Генератор псевдовипадкових бітових послідовностей на основі клітинного автомата містить клітинний автомат. Генератор псевдовипадкових бітових послідовностей на основі клітинних автоматів містить блок пам'яті та пристрій порівняння, вихід якого підключений до входу вибору мажоритарної клітини, а перший вхід підключений до виходу блока пам'яті, вхід якого підключений до виходу станів клітинного автомата, інформаційний вихід якого підключений до виходу генератора, вихід поточного стану клітинного автомата підключений до другого входу пристрою порівняння. Перший та другий управляючий входи генератора підключені, відповідно, до першого та другого входам адреси клітин, третій управляючий вхід підключений до входу вибору клітини виходу. UA 98503 U (54) ГЕНЕРАТОР ПСЕВДОВИПАДКОВИХ БІТОВИХ ПОСЛІДОВНОСТЕЙ НА ОСНОВІ КЛІТИННОГО АВТОМАТА UA 98503 U UA 98503 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до обчислювальної техніки, до радіотехніки, систем зв'язку та може бути використана при формуванні ансамблів псевдовипадкових послідовностей для діагностування цифрових об'єктів та шифрування повідомлень. Відомо генератор випадкової двійкової послідовності (Патент Росії № 2281603), що містить групу щонайменше з двох взаємозв'язаних генераторів періодичного імпульсного сигналу, джерело управляючого сигналу, блок формування випадкової імпульсної послідовності, вихідний регістр, в якому вихід кожного з генераторів групи зв'язаний з відповідним інформаційним входом блока формування випадкової імпульсної послідовності, інформаційний вихід якого зв'язаний з інформаційним входом регістра, вихід якого є виходом пристрою, а вихід джерела управляючого сигналу підключений до управляючого входу блока формування випадкової імпульсної послідовності і до тактового входу вихідного регістра. Кожний з генераторів періодичного імпульсного сигналу виконаний у вигляді інвертора, охопленого позитивним зворотнім зв'язком. Блок формування випадкової імпульсної послідовності містить мультиплексор та лічильник, виходи якого підключені до адресного входу мультиплексора, прямі та інверсні інформаційні входи мультиплексора є інформаційними входами блока, лічильний вхід лічильника є управляючим входом блока формування, а вихід мультиплексора є виходом блока. Джерело управляючого сигналу складається з послідовно з'єднаних генератора періодичного сигналу та дільника частоти, вихід якого є виходом джерела управляючого сигналу. Недоліком даного пристрою є низька надійність функціонування за рахунок великої кількості зворотних зв'язків, а також великої кількості генераторів періодичного імпульсного сигналу, які потребують особистих налаштовувань. Відомо генератор псевдовипадкових послідовностей на основі клітинних автоматів (Б.М. Сухинин. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов./ Электронное научно-техническое издание "Наука и образование", 2010. - № 9. - С. 16, - рис. 1), що містить два клітинних автомати, регістр зсуву з лінійними зворотними зв'язками, та суматори за модулем 2. Недоліком даного пристрою є низька надійність функціонування за рахунок використання генераторів псевдовипадкових послідовностей бітів на регістрах зсуву та застосування перетворювачів паралельних кодів у послідовні. Крім цього такий генератор використовує аналіз та обчислення значень значної кількості клітин на двох клітинних автоматах, що ускладнює апаратну реалізацію клітинних автоматів та знижує швидкодію самого пристрою. Найбільш близьким до заявленої корисної моделі є генератор псевдовипадкових бітових послідовностей на основі клітинних автоматів, що містить клітинний автомат, матричну систему комутації, кожний перший вхід якої підключений до інформаційного виходу відповідної клітини клітинного автомата, кожна клітина якого містить тригер збудження та тригер стану, комутатор, блок логічних функцій та чотири диз'юнктори, вихід блока логічних функцій підключений до першого входу третього диз'юнктора, другий вхід якого підключений до входу установки клітини, інформаційні входи комутатора підключені до інформаційних виходів клітин околиці, а відповідний вихід комутатора підключений до відповідного першого входу четвертого диз'юнктора відповідної клітини околиці, другий вхід четвертого диз'юнктора підключений до входу сигналу збудження клітини, а вихід четвертого диз'юнктора підключений до входу установки тригера збудження, вихід третього диз'юнктора підключений до входу установки тригера стану, вхід установки в нульовий стан якого підключений до входу обнуління клітини, прямий вихід тригера стану підключений до інформаційного виходу клітини та до першого входу блока логічних функцій, другий вхід якого підключений до прямого виходу тригера збудження та до управляючого входу комутатора, третій вхід блока логічних функцій підключений до входу вхідної послідовності, четвертий, п'ятий, шостий, сьомий, восьмий, дев'ятий, десятий та одинадцятий входи блока логічних функцій підключені, відповідно, до інформаційних виходів клітин околиці власної клітини, вхід установки тригера збудження в нульовий стан підключений до виходу другого диз'юнктора, другий вхід якого підключений до входу сигналу обнуління збудження клітини, перший вхід другого диз'юнктора підключений до виходу першого диз'юнктора, кожний з восьми входів якого підключений до відповідних виходів тригерів збудження відповідних клітин околиці, а його вхід управління підключений до прямого виходу тригера збудження, вихід матричної системи комутації підключений до виходу пристрою, а кожний другий вхід її підключений до виходу тригера збудження відповідної клітини, вхід синхронізації підключений до входів синхронізації тригерів кожної клітини та входу синхронізації матричної системи комутації. Недоліком даного пристрою є низька надійність функціонування за рахунок складності реалізації клітини клітинного автомата. Крім цього в роботі такого генератора можливі появи 1 UA 98503 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 підключений до виходу БП 2, вхід якого підключений до виходу 6 станів КА 1, інформаційний вихід 7 якого підключений до виходу 8 генератора, вихід 9 поточного стану КА 1 підключений до другого входу 10 ПП 3, причому перший та другий управляючий входи 11, 12 генератора підключені, відповідно, до першого та другого входам адреси клітин, третій управляючий вхід 13 підключений до входу вибору клітини виходу. Схема реалізації фрагменту КА 1 за околицею фон Неймана (Фіг. 3) складається з дев'яти клітин 14, виходи 15 станів яких підключені до відповідних інформаційних входів 16-19, відповідно, верхньої, правої, нижньої та лівої сусідніх клітин 14, а також до відповідного входу 20 комутатора 21 виходів (KB), вихід якого підключений до інформаційного виходу 7 КА 1, перший управляючий вхід 11 підключений до першого входу комутатора 22 вибору адреси мажоритарної клітини (КВАМК), другий вхід 4 якого підключений до ВВМК 4 КА 1, а інформаційні входи КВАМК 22 підключені до другого управляючого входу 12 генератора. Управляючий вхід KB 21 підключений до третього входу 13 генератора. Відповідний вихід 23 КВАМК 22 підключений до входу 24 відповідної клітини. Клітина КА 1 (Фіг. 4) складається з тригера 25 (Т), елемента XOR 26, мажоритарного елемента 27 (ME), комутатора 28 (К) та диз'юнктора 29, перший вхід якого підключений до входу 30 початкової установки (ВПУ), другий вхід підключений до виходу К 28, а вихід - до входу 31 установки Т 25, вихід якого підключений до виходу 15 стану клітини 14, а також до перших входів елемента XOR 26 та ME 26. Вхід обнуління тригера 25 підключений до входу 32 обнуління клітини (ВОК). Вхід управління К 28 підключений до входу 24 клітини, а перший та другий входи 33, 34 підключені до виходів, відповідно, елемента XOR 26 та ME 27, другий, третій, четвертий та п'ятий входи яких підключені, відповідно, до першого, другого, третього та четвертого інформаційних входів 16-19 клітини 14. Генератор псевдовипадкових бітових послідовностей на основі клітинного автомата функціонує в такий спосіб. У початковий момент часу по ВПУ 30 (Фіг. 4) кожна клітина 14 КА 1 встановлюється відповідно у стан логічної "1" або логічного "0". Початкова установка клітин 14 КА 1 може здійснюватись випадковим чином, або жорстко встановлюватись користувачем. На третій управляючий вхід 13 КА 1 подається код, який задає координати клітини 14 КА 1, вихід 15 стану якої (Фіг. 3) підключається через KB 21 до виходу 7 КА 1 і, відповідно, до виходу 8 (Фіг. 1) ГПВП. На перший управляючий вхід 11 ГПВП подається код клітини, яка вибирається для виконання мажоритарної функції. При цьому на вході 4 КА 1 присутній сигнал логічної "1" (Фіг. 1). Даний код подається на відповідні входи КВАМК 22 (Фіг. 3), який формується на відповідному 2 UA 98503 U 5 10 15 20 25 30 35 40 45 50 55 виході 23 сигнал логічної "1", що подається на вхід 24 відповідної клітини 14 КА 1. Адреса клітини 14 задається кодом на вході 11. Таким чином, у початковий момент часу здійснюється початкова установка клітин КА 1 та вибирається клітина, яка виконує мажоритарну функцію. Виконання такої функції однієї клітини полягає в тому, що вона аналізує стани клітин околиці (для нашого ГПВП вибрана околиця фон Неймана) та стан власної клітини і на наступному часовому такті встановлюється у той стан, кількість яких більша. Тобто, якщо більше одиничних станів, то клітина встановлюється у стан логічної "1" і навпаки. З початком роботи ГПВП на кожному часовому такті усі клітини виконують задані функції. Всі клітини КА 1 виконують операцію XOR з сигналами, що надходять від клітин околиці фон Неймана (Фіг. 2) та власної клітини. Стан кожної клітини (крім клітини, що виконує мажоритарну функцію) виконують функцію, яка описується наступним логічним виразом. B0(t+1)=X0(t)X1(t)X2(t)X3(t)X4(t) (1) В даному виразі значення bо указує значення стану на виході 15 відповідної клітини. Клітина, яка виконує мажоритарну функцію по наступному виразу 4  1, якщо  Xi ( t )  3 . (2) b0 ( t  1)   i 0 1, в інших випадках  В даному виразі здійснюється арифметичне додавання одиниць. Отже на наступному часовому такті (t+1) усі клітини КА 1 змінюють власний стан, згідно з заданими функціями. Попередні стани клітин КА 1 у вигляді двійкового коду записуються у БП 2 і зберігаються там. На кожному часовому такті ПП 3 здійснює порівняння поточного стану КА 1, який у вигляді двійкового коду формується на виході 9 і подається на другий вхід 10 ПП 3, з кодами, які подаються на його перший вхід 5. Коди на перший вхід 5 ПП 3 подаються з виходу БП 2. ПП 3 здійснює порівняння коду на другому вході 10 з усіма кодами (попередніми станами КА 1), що зберігаються у БП 2. Якщо на вході ПП 3 формується сигнал логічної "1", то це говорить про те, що код на другому вході 10 співпав з одним з кодів, який зберігається у БП 2 і присутній на першому вході 5 ПП 3. Сигнал логічної "1" з виходу ПП 3 подається на вхід 4 КА 1, зміст БП 2 обнуляється, а на другий управляючий вхід 12 генератора подається код адреси наступної клітини, яка реалізує мажоритарну функцію. З наступним часовим тактом КА 1 змінює власний стан клітин з урахуванням місця розташування нової клітини, що виконує мажоритарну функцію. Відповідно КА 1 змінює власний стан по іншому закону. Після обнуління БП 2 з кожним наступним часовим тактом БП 2 починає знову запам'ятовувати стани КА 1 у вигляді кодів. Сформовані коди станів КА 1 постійно порівнюється з поточними станами КА 1 у ІШ 3. Якщо співпадіння відбулося, то знову проводиться процес зміни координат мажоритарної клітини і обнуляється зміст БП. Даний процес продовжується до кінця формування псевдовипадкової бітової послідовності. Кожна клітина 14 (Фіг. 3) аналізує сигнали з виходів 15 клітин 14 околиці фон Неймана. Сигнали від виходів 15 клітин околиці подаються на відповідні входи 16-19 контрольної клітини 14. По входам 11 КВАМК 22 вибирає клітину, на яку подається відповідно сигнал логічної "1" з входу 4. Входи 12 також здійснюють установку логічної "1" на відповідний вихід 23, яка поступає на вхід 24 заданої клітини 14 для виконання мажоритарної функції. Вхід 13 управління KB 21 указує клітину 14, вихід 15 якої підключається до виходу 7 КА 1. На виході даної клітини формується псевдовипадкова бітова послідовність. Приклад функціонування ГПВП на прикладі функціонування програмної моделі покроково подано на Фіг. 5, а приклад сформованої псевдовипадкової бітової послідовності подано на Фіг. 6. Клітина 14 КА 1 функціонує таким чином (Фіг. 4). По сигналу на ВОК 32 тригер 25 встановлюється в нульовий стан. Початкове встановлення Т 25 здійснюється шляхом подачі на ВПУ 30 відповідного сигналу логічного "0" або "1". Даний сигнал проходить через диз'юнктор 29 на вхід 31 установки Т 25. Відповідно Т 25 встановлюється в заданий стан, сигнал якого формується на його виході і подається на вихід 15 клітини 14. Клітина 14 може функціонувати у двох режимах: режим виконання функції XOR; 3 UA 98503 U 5 10 15 режим виконання мажоритарної функції. В режимі виконання функції XOR на вхід 24 управління подається логічний "0", який подається на вхід управління К 28. К 28 підключає до власного виходу перший вхід 33, який електрично зв'язаний з виходом елемента XOR 26. Елемент XOR 26, згідно з виразом (1), аналізує сигнали на входах 16-19 та на прямому виході Т 25 власної клітини 14. Результуючий сигнал з виходу елемента XOR 26, через К 28 та диз'юнктор 29, подається на вхід 33 установки Т 25 і встановлює його у заданий стан. Т 25 функціонує як D-тригер. В режимі виконання мажоритарної функції на вхід 24 подається сигнал логічної "1". До виходу К 28 підключається його другий вхід 34, який електрично з'єднаний з виходом ME 27. ME 27 аналізує сигнали, що присутні на входах 16-19 та на виході Т 25 власної клітини 14. ME 27 функціонує, згідно з формулою (2), і формує на виході одиничний сигнал, якщо на входах одиничних сигналів більше ніж нульових і навпаки. Сигнал з виходу ME 27 подається на вхід 31 установки Т 25 через К 28 та диз'юнктор 29. ГПВП може формувати псевдовипадкові бітові послідовності досить великої довжини. Якість функціонування залежить від розмірів КА 1 та кількості клітин, які виконують мажоритарну функцію. Постійне обнуління змісту БП 2 при кожному співпадінні дозволяє підвищити швидкодію обробки, а також збільшити довжину послідовності. Вибір функції зміни координат мажоритарної клітини від поточних динамічних параметрів заданого фізично процесу дозволяє підвищити степінь випадковості формування бітової послідовності. 20 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 25 30 Генератор псевдовипадкових бітових послідовностей на основі клітинного автомата, що містить клітинний автомат, який відрізняється тим, що генератор псевдовипадкових бітових послідовностей на основі клітинних автоматів містить блок пам'яті та пристрій порівняння, вихід якого підключений до входу вибору мажоритарної клітини, а перший вхід підключений до виходу блока пам'яті, вхід якого підключений до виходу станів клітинного автомата, інформаційний вихід якого підключений до виходу генератора, вихід поточного стану клітинного автомата підключений до другого входу пристрою порівняння, причому перший та другий управляючий входи генератора підключені, відповідно, до першого та другого входам адреси клітин, третій управляючий вхід підключений до входу вибору клітини виходу. 4 UA 98503 U 5 UA 98503 U 6 UA 98503 U 7 UA 98503 U Комп’ютерна верстка А. Крулевський Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 8