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

1. Спосіб генерування псевдовипадкових чисел, згідно з яким початкове значення бінарного коду заносять до кола циклічного зсуву, над вмістом розрядів коду, місця яких в форматі коду маскують і визначають вектором зворотних зв'язків, C2 2 (19) 1 3 рувати числа діапазону від 1 до N, де N=2n, n- розрядність коду псевдовипадкового числа. В якості прототипу обраний найбільш близький за сукупністю ознак спосіб генерування випадкових чисел, «в якому двійковий код циклічно зсувають і в ланцюгу зворотного зв'язку виконують логічну операцію «ВИКЛЮЧНЕ АБО» над останнім та проміжними бітами коду ... логічний сигнал у ланцюзі зворотного зв'язку інвертують у рівноймовірні випадкові моменти часу» [Опис до декл. пат. UA 36108 від 16.04.2001 G06F7/58, G07C15/00]. Недолік цього способу полягає в тому, що процедура інвертування у рівноймовірні проміжки часу спричиняє до спотворення логічної рекурсивної взаємозалежності кодових елементів у генерованій послідовності, внаслідок чого на періоді генерування псевдовипадкової послідовності певні значення кодів дублюються, а деякі втрачаються, що значно порушує рівномірність розподілу значень кодів на періоді та унеможливлює використання вказаного способу при перетворенні форми інформації, зокрема при кодуванні та імовірнісних дослідженнях Монте-Карло. Метою винаходу є розробка способу та пристрою генерування псевдовипадкових чисел з рівномірним розподілом та виключенням повторення чи втрати певних значень кодів на повному періоді їх генерування, включенням коду формату всіх нулів до діапазону генерування, що уможливлює автоматичний рестарт при обнуленні кола циклічного зсуву, за умови простої та дешевої реалізації. Поставлена мета досягається внаслідок того, що в способі генерування випадкових чисел, в якому двійковий код зсувають і в ланцюгу зворотного зв'язку виконують логічну операцію "ВИКЛЮЧНЕ АБО" над останнім та проміжними бітами, а логічний сигнал у ланцюгу зворотного зв'язку інвертують в рівноймовірні випадкові моменти часу, на відміну від прототипу операція інвертування виконується постійно в часі згідно заданого значення коду вектора зворотних зв'язків. Для відомих способів формування nрозрядних псевдовипадкових чисел (bi-n+1 … bi-2 bi-1 bi) здійснюється рекурсивне формування кожного наступного біту bi+1 послідовності згідно аналітичної залежності bi+1 = i -n+1 å aibi(mod 2) (1) i де аi - коефіцієнти вектора зворотних зв'язків. Як можна зауважити, кодова комбінація (bi-n+1 … bi-2 bi-1 bi) із n нулів для генерування є виключеною, оскільки спричиняє формування значення bli+1 та наступних як нулів [Литиков И.П. Кольцевое тестирование цифровых устройств. -Μ.: Энергоатомиздат, 1990. - ее. 13, 16]. Інвертування логічного сигналу у ланцюгу зворотного зв'язку в рівноймовірні випадкові моменти часу дозволяє уникнути неможливості рестарту із формату коду всіх нулів, але потребує додаткового часу очікування виконання чергової операції інвертування, необхідної для зміни обнуленого стану регістру зсуву. Іншим істотним недоліком є повторення деяких кодових n-розрядних фрагментів, або втрата деяких інших внаслідок інвертуван 86941 4 ня логічного сигналу у ланцюгу зворотного зв'язку в рівноймовірні випадкові моменти часу, що спотворює рівномірність розподілу псевдовипадкових чисел і, як наслідок, унеможливлює застосування вказаного способу в методах статистичних досліджень Монте-Карло. Суть запропонованого способу полягає в тому, що виконання процедури додаткового інвертування результату суми (1) у ланцюгу зворотного зв'язку постійно в функції часу дозволяє уникнути вказаних недоліків, для якого згідно виразу bi+1 = i -n +1 å aibi (mod 2) i отримано можливість здійснювати генерування кодів псевдо випадкової послідовності із значення початкового коду формату n нулів, а також здійснювати автоматичний рестарт при виникненні нештатних ситуацій. Процедура постійного інвертування (а не у рівноймовірні випадкові моменти часу) дозволяє уникнути дублювання та втрати деяких значень кодів, а також генерувати всі значення кодів діапазону від 0 до Ν-1, включаючи код формату всіх нулів. Запропонований спосіб дозволяє реалізувати пристрій, структурну схему якого наведено на Фіг.1. Пристрій містить генератор тактових імпульсів G, вихід якого підключено до входів тактування регістра зсуву RG, побудованого на послідовно включених тригерах, виходи яких становлять вихідну шину даних DB і під'єднано до других входів лінійки логічних елементів & пристрою маскування за вектором зворотних зв'язків, код якого по шині VB задається на перші входи лінійки логічних елементів &, виходи яких включено на входи логічного елементу сумування за модулем два XOR, вихід якого підключено на вхід інвертора NOT, вихід якого включено на вхід регістра зсуву RG. Пристрій функціонує в циклічному режимі, в кожному із тактів якого синхроімпульси з виходу генератора тактових імпульсів G здійснюють тактування та циклічний зсув вмісту послідовно комутованих тригерів регістру зсуву RG, виходи кожного із яких становлять паралельну вихідну шину кодів псевдовипадкових чисел DB, заданих на другі входи лінійки логічних елементів & пристрою маскування за кодом вектора зворотних зв'язків, заданого на перші входи лінійки логічних елементів & по шині VB, сумуються логічним елементом сумування за модулем два XOR та інвертуються з його виходу інвертором NOT і записуються на вхід регістру зсуву RG. На Фіг.2 зображено осцилограму розподілу значень псевдовипадкових чисел на періоді їх генерування в функції часу. Проведено дослідження генерованих чисел для визначення типу розподілу псевдовипадкових чисел із застосуванням статистичних методів знаходження закону розподілу випадкових чисел метод c2 та метод Колмогорова-Смірнова, згідно яких на основі вибірки отриманих значень було визначено тип емпіричного розподілу як рівномірний. Результати експериментальних досліджень підтвердили рівноймовірний розподіл псевдовипа 5 86941 дкових чисел діапазону від 0 до N-1 без пропусків та дублювання деяких значень кодів, включаючи комбінацію із n нулів, що дозволило здійснювати Комп’ютерна верстка А. Крижанівський 6 автоматичний рестарт генератора, а також просту реалізацію запропонованого способу та низький кошт пристрою генерування. Підписне Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601