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

1. Спосіб генерування псевдовипадкових чисел, згідно з яким бінарні значення кодів псевдо C2 1 3 комбінації всіх нулів, значення коду якої в більшості випадків є початковим, а також при збоях, вимушених перезапусках, які спричиняють обнуления регістру. Це зумовлено тим, що комбінація всіх нулів є логічно виключеною в повному наборі генерованих чисел [Литиков И.П. Кольцевое тестирование цифровых устройств. -М: Энергоатомиздат, 1990. - с.13, 16]. В ряді випадків відсутність вказаного значення коду спричиняє трудності ініціюванні нульового відліку при перетворенні форми інформації. Вказаний спосіб дозволяє генеруn вати числа діапазону 1 N , де N=2 , n розрядність коду псевдовипадкового числа. Метою винаходу є розробка способу та пристрою генерування псевдовипадкових чисел з рівномірним розподілом та виключенням повторення чи втрати певних значень кодів на повному періоді їх генерування, включенням коду формату всіх нулів до діапазону генерування, із можливістю автоматичного рестарту, за умови простої та дешевої алгоритмічної та апаратної реалізації. Поставлена мета досягається шляхом того, що в способі генерування кодів псевдовипадкових чисел, в якому, на відміну від відомих способів, iрозрядний двійковий код формується з виходів тактованого в інкрементному режимі двійкового лічильника, кожен із i-х виходів сi двійкового лічильника підключений до кожного із відповідних входів bj шини даних у зворотному дзеркальному впорядкуванні згідно аналітичної залежності ci=bn-i-1=bj (1) та способу, зображеного на фігурі 1. Якщо нормальне впорядкування розрядів двійкових ваг шини даних системи має наступну вагову мережу b0 20, b1 21, b2 22, ..., bj 2j, ..., bn-3 2n-3, bnn-2 n-1 2 2 , bn-1 2 , то, згідно запропонованого способу генерування, у відповідних порядкових позиціях розрядів генератором буде сформовано коди із таким зворотним дзеркально відображеним впорядкуванням вагової мережі n-1 n-2 n-3 b0=cn-1 2 , b1=сn-2 2 , b2=cn-3 2 , ..., і bj=сi 2 , ..., 2 1 0 bn-3=c2 2 , bn-2=c1 2 , bn-1=c0 2 . Для відомих способів формування nрозрядних кодів псевдовипадкових чисел (bi-n+1...bi2 bi-1 bi) здійснюється рекурсивне формування кожного наступного біту bi+1 послідовності згідно аналітичної залежності i n 1 bi aibi (mod 2) , 1 i де аi - коефіцієнти вектора зворотних зв’язків. Як можна зауважити, кодова комбінація (bi-n+1...bi-2 bi-1 bi) із n нулів для генерування є виключеною, оскільки спричиняє формування значення bi+1 та наступних як нулів [Литиков И.П. Кольцевое тестирование цифровых устройств. -М: Энергоатомиздат, 1990. - c.13, 16], що ускладнює перехід до двійкового числення внаслідок відсутності комбінації n нулів та виконання процедур перетворення форми інформації. Інвертування логічного сигналу у ланцюгу зворотного зв’язку в рівноймовірні випадкові моменти часу дозволяє уникнути неможливості рестарту із 89173 4 формату коду всіх нулів, але потребує додаткового часу очікування виконання чергової операції інвертування, необхідної для зміни обнуленого стану регістру зсуву. Іншим істотним недоліком є повторення деяких кодових n-розрядних фрагментів та цілих послідовностей, або втрата деяких інших внаслідок інвертування логічного сигналу у ланцюгу зворотного зв’язку в рівноймовірні випадкові моменти часу, що спотворює рівномірність розподілу псевдовипадкових чисел і, як наслідок, унеможливлює застосування вказаного способу в методах статистичних досліджень Монте-Карло. Суть запропонованого способу полягає в тому, що зміна порядку підключення кожного із розрядів двійкових виходів двійкового лічильника на обернений щодо відповідних двійкових розрядів шини даних системи дозволяє уникнути вказаних недоліків, для якого згідно виразу (1) отримано можливість здійснювати генерування кодів псевдовипадкової послідовності з рівномірним розподілом в діапазоні від значення початкового двійкового коду формату п нулів до значення кінцевого двійкового коду формату п одиниць, а також здійснювати автоматичний рестарт при виникненні нештатних ситуацій. Уникнено дублювання чи втрати деяких значень кодів. Суть запропонованого способу генерування псевдовипадкових чисел, згідно якого бінарні значення кодів псевдовипадкових чисел формуються циклічно із лінійного інкрементованого впорядкування значень двійкового коду на періоді N їх формування, де N=2n, n - розрядність коду псевдовипадкового числа, який відрізняється тим, що кожен із розрядів с, двійкової вагової мережі сформованого двійкового коду формується як відповідний bj розряд вихідної системної шини даних у зворотному впорядкуванні згідно залежності сi=bn-i-1=bjі полягає в тому, що зміна порядку підключення кожного із розрядів двійкових виходів двійкового лічильника на обернений щодо відповідних двійкових розрядів шини даних системи дозволяє уникнути вказаних недоліків, для якого згідно виразу (1) отримано можливість здійснювати генерування кодів псевдовипадкової послідовності з рівномірним розподілом в діапазоні від значення початкового двійкового коду формату n нулів до значення кінцевого двійкового коду формату n одиниць, а також здійснювати автоматичний рестарт при виникненні нештатних ситуацій. Уникнено дублювання чи втрати деяких значень кодів. Приклад конкретного виконання. Запропонований спосіб дозволяє реалізувати пристрій, структурну схему якого наведено на фігурі 2. Пристрій містить генератор тактових імпульсів G, вихід якого підключено до лічильного входу двійкового лічильника СТ2, виходи c0, c1, с2, ... сi, ..., cn-3, cn-2, cn-1 якого становлять вихідну шину даних GB і під’єднані у зворотному порядку до входів b0, b1, b2, ... bj, ..., bn-3, bn-2, bn-1 системної шини даних DB. Пристрій функціонує в циклічному режимі, в кожному із тактів якого синхроімпульси з виходу генератора тактових імпульсів G в лічильному режимі інкрементують вміст двійкового лічильника 5 СТ2, внаслідок чого на двійкових виходах с0, с1, с2, ... сi, ..., cn-3, cn-2, cn-1 лічильника СТ2 формується лінійна розгортка всіх без винятку значень двійкових кодів від коду формату n нулів до коду формату n одиниць. Суть побудови пристрою генерування на основі запропонованого способу полягає у зворотному впорядкуванні комутування відповідних розрядів cі на відповідні входи системної шини даних bj згідно залежності (1), внаслідок чого на системній шині даних формуються бінарні коди псевдовипадкової послідовності, розгортка знаn чень яких на періоді N=2 (n=10) їх генерування в функції часу наведено на фігурі 3. Проведено дослідження генерованих чисел для визначення типу розподілу псевдовипадкових чисел із застосуванням статистичних методів зна 89173 6 ходження закону розподілу випадкових чисел 2 метод та метод Колмогорова-Смірнова, згідно яких на основі вибірки отриманих значень було визначено тип емпіричного розподілу як рівномірний. Результати експериментальних досліджень підтвердили високу якість рівноймовірного розподілу псевдовипадкових чисел діапазону 0 N без пропусків та дублювання деяких значень кодів, включаючи комбінацію із n нулів, із можливістю автоматичного рестарту генератора, а також просту алгоритмічну та апаратну реалізацію запропонованого способу і низький кошт пристрою генерування. 7 Комп’ютерна верстка А. Крижанівський 89173 8 Підписне Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601