Спосіб генерації випадкових чисел та пристрій для його здійснення

1. Спосіб генерації випадкових чисел, Е якому двійковий код циклічно зсувають і в ланцюгу зворотного зв'язку виконують логічну операцію "ВИКЛЮЧНЕ АБО" над останнім та проміжними бітами коду, який відрізняється тим, що логічний сигнал у ланцюзі зворотного зв'язку інвертують у рівноймовірні випадкові моменти часу. 2. Пристрій генерації випадкових чисел, що містять вузол генерації випадкових логічних рівнів, який складається з послідовно з'єднаних генератора шуму, підсилювача-обмежувача та лічильно 36108 нерації випадкових бітів, який включає в себе послідовно з'єднані генератор шуму, підсилювачобмежувач і лічильний тригер, і вузол спряження з ПЕОМ, що включає в себе регістр зсуву, ви ходи якого увімкнуті до входів вихідного регістру, з'єднаного виходами з шиною даних ПЕОМ, тактовий генератор, вихід якого з'єднаний з синхровходом регістру зсуву та входом лічильника імпульсів, вихід якого під’єднаний до синхровходу вихідного регістру та входу тригера "прапора", а його вихід з'єднаний з виходом запиту переривання та через буферний елемент І з шиною даних ПЕОМ, і дешифратор адреси, включений входами до шини адреси ПЕОМ, а першим виходом до входу дозволу вихідного регістру та входу скидання тригера "прапора", а другим виходом до буферного елементу І. Швидкість формування випадкових бітів, що визначається частотою тактового генератора, в описаному пристрої повинна бути у 5-10 разів менша за середню частоту генератора шумових імпульсів, таким чином, частота генерації випадкових бітів у реальних схемах не перевищує 100200 кГц. В основу винаходу поставлена задача створення такого способу та пристрою генерації випадкових чисел, в яких додавання нових дій та схемних елементів і зв'язків дозволило б підвищити швидкість формування випадкових рівноймовірних чисел і, як наслідок, поширити область застосування. Такий технічний результат може бути досягнутий, якщо в способі генерації випадкових чисел, в якому двійковий код циклічно зсувають і в ланцюгу зворотного зв'язку виконують логічну операцію "ВИКЛЮЧНЕ АБО", над останнім та проміжними бітами коду, згідно з винаходом, логічний сигнал у ланцюзі зворотного зв'язку інвертують у рівноймовірні випадкові моменти часу. Крім цього, в пристрої генерації випадкових чисел, що містить вузол генерації випадкових логічних рівнів, який виконує функції вузла генерації випадкових бітів за прототипом і складається з послідовно з'єднаних генератора шуму, підсилювачаобмежувача та лічильного тригера, і вузол спряження з ПЕОМ, що включає в себе регістр зсуву, виходи якого увімкнуті до входів вихідного регістру, з'єднаного виходами з пінною даних ПЕОМ, тактовий генератор, вихід якого з'єднаний з синхровходом регістру зсуву і входом лічильника імпульсів, вихід якого під'єднаний до синхровходу ви хідного регістру та. входу тригера "прапора", а його вихід з'єднаний з входом запиту переривання ПЕОМ і через буферний елемент І з шиною даних ПЕОМ, і деши фратор адреси, включений входами до шини адреси ПЕОМ, а першим виходом до входу дозволу ви хідного регістру і входу скидання тригера "прапора", і другим виходом до буферного елементу І, згідно з винаходом, додатково введений суматор по модулю два, перший вхід якого з'єднаний з виходом лічильного тригера, інші входи суматора з'єднані з виходами регістру зсуву, а вихід суматора з'єднаний з входом даних регістру зсуву. Таким чином, введення нової дії в способі генерації випадкових чисел, а саме - інвертування логічного сигналу у ланцюгу зворотного зв'язку у рівноймовірні випадкові моменти часу, а також введення додаткового суматора по модулю два у ланцюгу зворотного зв’язку регістра зсуву у пристрої генерації випадкових чисел та введення додаткових зв'язків дозволяє підвищити швидкість генерації випадкових чисел, яка визначається частотою тактового генератора і не залежить від частоти генератора шумових імпульсів, тому частоту тактового генератора можна збільшити до максимальної частоти логічних мікросхем (понад 100 МГц). Крім цього, отримано додатковий позитивний результат - порівняння імовірності одиничних і нульових бітів випадкових чисел, що генеруються. Це можна пояснити таким чином: Якщо у формувача псевдовипадкових послідовностей, виконаного на основі регістру зсуву та елемента ВИКЛЮЧНЕ АБО в ланцюзі зворотного зв'язку, включити інвертор (або виконати елемент ВИКЛЮЧНЕ АБО з інверсією), то це призводить до того, що в повному циклі генерується на один нульовий біт більше, ніж одиничних бітів за рахунок винятку стану "усі одиниці", тому імовірність нульових бітів більше імовірності одиничних. Зміни логічного сигналу в ланцюзі зворотного зв'язку формувача, з інверсного значення на пряме та назад в рівноймовірні випадкові часові інтервали дозволяє вирівняти імовірності одиничних і нульових бітів. На фігурі зображена структурна схема пристрою генерації випадкових чисел. Пристрій містить вузол 1 генерації рівноймовірних випадкових логічних рівнів, який складається з послідовно з'єднаних генератора 2. шум у, підсилювача-обмежувача 3 і лічильного тригера 4, і вузол 5 спряження з ПЕОМ, що містить регістр 6 зсуву, ви ходи якого з’єднані зі входами вихідного регістру 7, з'єднаного виходами з шиною даних ПЕОМ, тактовий генератор 8, вихід якого з'єднаний з синхровходом регістру 7 зсуву та входом лічильника 9 імпульсів, вихід якого з'єднаний з синхровходом вихідного регістру 7 і входом тригера 10 "прапора", вихід якого з'єднаний з входом запиту переривання ПЕОМ і через буферний елемент 11 І з шиною даних ПЕОМ, дешифратор 12 адреси, з’єднаний входами з шиною адреси ПЕОМ, першим виходом з входом дозволу вихідного регістру 7 і входом скидання тригера 10 "прапора", а другим виходом - до буферного елементу 11 І. Суматор 13 по модулю два, що формує сигнал зворотного зв'язку і виконує функцію інверсії цього сигналу, з’єднаний першим входом з виходом лічильного тригера 4, а іншими входами - до виходів регістру 6 зсуву, ви хід суматора по модулю два з’єднаний з входом даних регістру 6 зсуву. Пристрій генерації випадкових чисел працює у такий спосіб. На виході генератора 2 шуму формуються імпульси випадкової амплітуди, наступні через випадкові часові інтервали. Амплітуда цих імпульсів підсилювачем-обмежувачем 3 перетворюється в логічні рівні ТТЛ, КМОН або ЕЗЛ мікросхем. Імпульси з виходу підсилювача-обмежувача подаються на вхід лічильного тригера 4, на виході якого формуються логічні рівні, що з рівною імовірністю приймають значення нуля або одиниці у випадкові моменти часу. 2 36108 Випадкові логічні рівні з виходу лічильного тригера 4 перемикають формувач псевдовипадкових послідовностей, який складається з регістру зсуву 6, суматора 13 по модулю два в ланцюзі зворотного зв'язку і тактового генератора 8, у випадкові моменти часу з режиму роботи "з інверсією" сигналу зворотного зв'язку в режим - "без інверсії" та навпаки. Завдяки цьому, вихідний сигнал формувача стає непередбачуваним, тобто випадковим (недетермінованнм). Лічильник 9 імпульсів через задане число періодів тактового генератора 8 формує імпульс для запису коду з регістру зсуву 6 у ви хідний регістр 7 та для установи тригера 10 "прапора" в одиничний стан. Вихідний сигнал тригера 10 "прапора" подається на вхід запиту переривання IRQ ПЕОМ. Виконуючи підпрограму обробки переривання. ПЕОМ зчитує випадкове число з вихідного регістру 7 на шину даних. Для цього на шину адреси ПЕОМ виставляється адреса порту пристрою, що розпізнається дешифратором 12 адреси. Вихідний сигнал дешифратора 12 дозволяє зчитування коду вихідного регістру 7, а також скидає в нуль тригер 10 "прапора". Стан тригера "прапора" може бути також прочитаний на шині даних ПЕОМ через буфе рний елемент 11 І, на вхід якого подається імпульс з другого ви ходу деши фратора 12 адреси. Для підвищення надійності формування випадкових чисел вузол 1 генерації випадкових логічних рівнів може бути виконаний багатоканальним, аналогічно описаному пристрою-прототипу. Функціонування пристрою генерації випадкових чисел можливо тільки в складі програмноапаратного комплексу, що включає в себе власне пристрій генерації випадкових чисел, програмний драйвер зчитування випадкових чисел і програми тестування При тестуванні генератора рівномірно розподілених випадкових чисел перевірялася відповідність випадкових чисел, що генеруються, умовам: - рівноймовірності з використанням критерію Пірсона; - випадковості за критерієм серій; - некорельованості за коефіцієнтами кореляції розрядів байтів випадкової послідовності; - незалежності за засобом спряження ознак; - однорідності за засобом перевірки гіпотези про збіг розподілення. Результати експериментальних досліджень підтвердили рівноймовірний закон розподілу випадкових чисел, що генеруються. 3 36108 Фіг. 4 36108 __________________________________________________________ ДП "Український інститут промислової власності" (Укрпатент) Україна, 01133, Київ-133, бульв. Лесі Українки, 26 (044) 295-81-42, 295-61-97 __________________________________________________________ Підписано до друку ________ 2001 р. Формат 60х84 1/8. Обсяг ______ обл.-вид. арк. Тираж 50 прим. Зам._______ ____________________________________________________________ УкрІНТЕІ, 03680, Київ-39 МСП, вул. Горького, 180. (044) 268-25-22 ___________________________________________________________ 5