Генератор випадкових чисел

Винахід належить до обчислювальної техніки і може бути використаним для моделювання різних технологічних процесів та статистичного аналізу випадкових процесів і полів. Відомий генератор випадкових чисел, що містить блок пам'яті, суматор, проміжний регістр, m лічильників адреси читання, лічильник адреси запису та елемент затримки, причому вихід суматора є ви ходом генератора і з'єднаний із входом проміжного регістру, вихід якого з'єднаний з інформаційним входом блока пам'яті, вхід синхронізації якого з'єднаний із виходом джерела тактових імпульсів та до входу елемента затримки, вихід якого з'єднаний із входами m лічильників адреси читання та лічильника адреси запису, виходи яких з'єднані відповідно з m адресними входами читання і адресним входом запису блока пам'яті, n виходів якого з'єднані із входом суматора. (Миронов І.Я. Генератор випадкових чисел. Патент України №22171А від 30.06.98р., М.кл G06F7/58). Недоліком даного генератора є відсутність апаратурних засобів формування випадкових чисел з довільними законами розподілення імовірностей. Відомий генератор випадкових чисел, що містить генератор тактових імпульсів, лічильник, регістр, ви хід якого є ви ходом генератора випадкових чисел, два елементи затримки, елементи АБО, датчик нормально розподілених випадкових чисел, квадратор, суматор, два блоки обчислення квадратного кореня, дільник, помножувач та схему порівняння, причому входом генератора являється вхід датчика нормально розподілених чисел. (Башликов В.М., Борисов Е.В. Генератор випадкових чисел. Патент РФ №1651281-1991р. M.кл. G06F7/58). Недоліком даного генератора є великі апаратні витрати і низька швидкодія. Він також виробляє тільки випадкові числа за законом Ст‘юдента. Найближчим до винаходу є генератор випадкових чисел, що містить датчик рівномірно розподілених випадкових чисел, вхід синхронізації якого з'єднаний з виходом джерела тактових імпульсів, блок задання функцій розподілу, помножувач, суматор, ви хід якого є виходом генератора, перший вхід помножувача з'єднаний з виходом групи молодших розрядів датчика рівномірно розподілених випадкових чисел. (Порфірьов Г.М., Бурнашев М.М. Генератор випадкових чисел. Авт. свід. СРСР №1619261 від 7.01.91р., М.кл. G06F7/58). Недоліком даного генератора є великі апаратні витрати. В основу винаходу поставлено задачу зменшення апаратних витрат та підвищення швидкодії генератора випадкових чисел шля хом введення блоку пам'яті опорних значень, що дозволяє за одне арифметичне ділення обчислити поправку для опорного значення випадкового числа заданого закону розподілу імовірностей. Для вирішення цієї задачі генератор випадкових чисел містить блок пам'яті опорних значень, перший і другий входи якого з'єднані відповідно з виходом групи старших розрядів датчика рівномірно розподілених випадкових чисел та виходом блоку задання функцій розподілу, вхід якого є входом параметрів закону розподілу, перший і другий входи суматора з'єднані відповідно з першим виходом блоку пам'яті опорних значень і виходом помножувача, другий вхід якого з'єднаний з другим виходом блоку пам'яті опорних значень. Винахід пояснюється рисунками: на фіг.1 представлена функціональна схема генератора випадкових чисел, на фіг.2 - ілюстрація алгоритму формування випадкових чисел довільного закону. Генератор випадкових чисел (фіг.1) містить: 1. Датчик рівномірно розподілених випадкових чисел. 2. Блок задання функцій розподілу. 3. Блок пам'яті опорних значень. 4. Помножувач. 5. Суматор. Вихід джерела тактових імпульсів з'єднаний із входом синхронізації датчика 1 рівномірно розподілених випадкових чисел, виходи якого з'єднані з першими входами помножувача 4 і блоку 3 пам'яті опорних значень, другий вхід якого з'єднаний з виходом блока 2 задання функцій розподілу, вхід якого є входом параметрів закону розподілу імовірностей. Перший і другий виходи блоку 3 пам'яті опорних значень з'єднані відповідно з першим входом суматора 5 і другим входом помножувача 4, ви хід якого з'єднаний з другим входом суматора 5, вихід якого є виходом генератора випадкових чисел. Генератор випадкових чисел призначений для моделювання роботи різних технологічних установок та систем і формує випадкові послідовності довільного закону розподілу імовірностей із заданими параметрами. В наш час використовується достатньо велика кількість законів розподілу імовірностей. Наприклад, програмне середовище Mathcad дозволяє формувати серії випадкових чисел з довільними параметрами для близько 20 законів розподілу. Тому доцільно мати таблиці опорних значень випадкових чисел різних законів розподілу імовірностей, які легко перетворюються для заданих параметрів за методом лінійної інтерполяції. На практиці широко використовують наступний метод формування випадкових чисел для довільного закону розподілу із заданими параметрами: рівномірно розподільне число 0 £ x(n ) £ 1. 0 перетворюється в число x(x ) за формулою: x = F(x); , (1) x = F -1 (x) де F(x) - функція розподілу імовірностей, F -1 (x ) - зворотна функція розподілу. Функція F(x) є гладкою кривою і змінюється в інтервалі 0 .0 £ F(n ) £ 1 .0 як імовірність P(y £ x ) події, що випадкові значення чисел у менше значення х. Пропонуємий генератор формує випадкові числа х на підставі лінійної інтерполяції зворотної функції x= F (x ) -1 за відношенням: x - x0 x = x0 + 1 × Dx = F -1 (x 0 ) + K × Dx , x1 - x0 (2) де x = x 0 + D x - рівномірно розподілене випадкове число в інтервалі 0 .0 £ x < 1. 0 . Алгоритм (2) формування випадкових чисел для заданого закону розподілу імовірностей і його параметрів пояснюється графіком, який представлений на фіг.2. Припустимо, що інтервал значень випадкових чисел 0 .0 £ x < 1. 0 був розподілений на М=2m пpoмiжків. Представимо цифровий код n-розрядного випадкового числа у ви гляді: x = 0.aa..abb..b 13 { 2 n-m m x 0 = 0.aa...a 00... 0 (3) Dx = 0. 00... 0 bb...b x1 - x 0 = 0.00... 1 00... 0 = 2 -m Тоді для реалізації алгоритму (2) формування випадкових чисел x = F 1 (x ) достатньо мати у блоці пам'яті 3 М=2m опорних значень x 0 = F -1 (x0 ) . Адресою читання опорних чисел х0; х1 є код групи старши х розрядів рівномірно розподілених чисел, які формує датчик 1 пропонуємого генератора випадкових чисел. Блок k = пам'яті опорних значень зберігає випадкові числа x 0 F -1 (x0 ) = та коефіцієнти x1 - x0 = 2 -m (x 1 - x 0 ) , які поступають відповідно у суматор 5 та помножувач 4, котрий обчислює поправку x1 - x0 Dx = k × Dx . Величина Dx поступає в помножувач 4 як код молодших розрядів рівномірно розподілених чисел x з виходу датчика 1. x - x0 Таблицю опорних значень випадкових чисел x 0 = F -1 (x0 ) та коефіцієнтів k = 1 формує блок 2 задання x1 - x 0 функцій розподілу імовірностей. Вхідною інформацією для блоку 2 являється код потрібного закону розподілу імовірностей та значення параметрів. Звичайно використовуються на практиці одно та двопараметричні функції розподілу F(x, u, J) , де u, J - значення параметрів функції x = F(x ) . Зворотні функції x = F -1 (x, u, J ) для опорних аргументів x 0 = 0.aa...a 00... 0 можна обчислити окремо та записати у постійну пам'я ть блоку 2 задання функцій розподілу. У тому вкладку, коли параметри u, J відрізняються від параметрів потрібного закону розподілу імовірностей, тоді доцільно формувати таблицю опорних значень x 0 = F -1 (x 0 , u, J ) за відношенням: x 00 = F (x 0 , u 0 , J0 ); (x 0 , u1, J0 ); -1 x 01 = F (x 0 , u0 , J1 ); -1 x10 = F x11 = F (x 0 , u1, J1 ); x 10 - x 00 x - x 01 y0 = + x 00 ; y 1 = 11 + x 01 (4) u1 - u 0 u1 - u0 y1 - y0 x0 = × (u - u0 ) + y 0 u1 - u0 -1 -1 Таблиця опорних значень випадкових чисел x 0 = F -1 (x 0 , u, J ) та коефіцієнтів k=2-m(x1-x0)для заданого закону розподілу імовірностей F = (x, u, J ) поступають у блок 3 пам'яті опорних значень. Серія випадкових чисел x = F -1 (x) для довільного, але заданого закону розподілу імовірностей формується шляхом сум ування опорного значення х0 та поправки Dx = k × Dx . Якість випадкових чисел x = F -1 (x) залежить від якості рівномірно розподілених чисел 0 .0 £ x < 1. 0 , які поступають у блок 3 пам'яті опорних значень (група старших розрядів) з виходу датчика 1. Можна пропонувати для використання генератор випадкових чисел за патентом України №22171А від 30.06.98 року. Це технічне рішення реалізує один із найкращих алгоритмів формування рівномірно розподілених випадкових чисел: (5) x (n ) = x(n - k1) + x (n - k 2) + ... + x(n - k p ) mod 2 2n Швидкодія генератора за патентом №22171А є швидкодія суматора, тому що зсув інформації у блоці пам'яті відсутній. Виробляємі (2n)-розрядні числа x(n) можливо закругляти до n-розрядних чисел, які використовуються [ ]( ) для формування випадкових чисел x = F -1 (x) за відношенням (2). Пропонуємий генератор випадкових чисел (фіг. 1) працює таким чином: У блок 2 поступають вхідні дані - потрібний закон розподілу імовірностей та значення його параметрів, блок 2 виробляє таблицю опорних значень x 0 = F -1 (x 0 ) випадкових чисел для потрібного закону розподілення імовірностей x = F (x, u, J ) та коефіцієнтів k=2-m(x1-x0). Потім у генератор 1 поступає серія довжиною N тактових імпульсів. Для кожного тактового імпульсу генератор 1 виробляє рівномірно розподілені випадкові числа x(n ); n = 0,N - 1 . Код числа x(n) має адрес (як група старших розрядів) вибору опорних значень х0 та коефіцієнтів k, які поступають у суматор 5 і помножувач 4 відповідно. Величина Dx , як група молодших розрядів, також поступає у помножувач, на ви ході якого виробляється поправка Dx = k × Dx . Величини х0 та Dx поступають в суматор, на виході якого формується серія довжиною N випадкових чисел x(n) = (x 0 + D x); n = 0, N - 1 для заданого закону розподілу імовірностей x = F(x, u, J) та потрібних значень параметрів u, J зворотної функції x = F -1(x) розподілу імовірностей. Доцільно формувати числа x(n) форматі фіксованої коми, однак випадкові числа x = F -1(x) потрібно формувати у форматі плаваючої коми. Коли числа x(n) є 16-ти розрядні коди, тоді можливо 8 розрядів використовува ти як адресу опорних значень у блоці 3 пам'яті. Решта 8 молодших розрядів представляють код величини Dx = 0. 00... 0 bb...b для обчислення поправки Dx . Пропонуємий генератор випадкових чисел має високу швидкодію, тому що термін виробки рівномірно розподілених чисел доведений до часу сумування чисел у форматі фіксованої коми. Для перетворення числа x(n) у випадкове число x = F -1 (x) достатньо виконати одне множення Dx = k × Dx , де Dx має тільки на приклад 8 розрядів. Позитивний ефект використання випадкових чисел полягає у тому, що він дозволяє реалізувати алгоритм лінійної інтерполяції гладких функції x = F -1 (x) при обчисленні поправки Dx = k × Dx . Порівняння з відомим технічним рішенням дозволяє зробити висновок, що введення блока 3 пам'яті опорних значень суттєво скорочує апаратурні витрати та термін формування випадкових чисел для довільного закону розподілу імовірностей.