Структурна схема одноплатного мікроконтролера

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

3.2.1. Лінійна конгруентна послідовність

Найкращою з відомих сьогодні давачів випадкових чисел являють собою окремі випадки наступної схеми запропонованої в 1948 році Дж.Лемером.

Вибираємо чотири числа:

X₀ - початкове значення (X₀ ≥0);

a - множник (a ≥0);

c - збільшення (c ≥0);

m - модуль (m>X₀, m>a, m>c).

Тоді шукана послідовність випадкових чисел <X_n> утворюється із співвідношення:

X_n+1=(aX_n+c)mod m , n > 0

Таку послідовність називають лінійною конгруентною послідовністю. Ця послідовність не випадкова, але виглядяє як випадкова. Така послідовність називається псевдовипадковою.

Наприклад, при X₀=a=c=7, m=10 послідовність виглядає так:

7, 6, 9, 0, 7, 6, 9, 0, …

Як видно з даного приклада, послідовність не завжди виявляється «випадковою», якщо обрати X₀, a, c, m довыльними. Приведений приклад ілюструє той факт, що конгруентні послідовності завжди «зациклюються», тобто зрештою, числа утворюють цикл, що повторюються нескінченне число разів. Повторюваний цикл називають періодом. Довжина періоду в цьому прикладі дорівнює 4.

3.2.2. Вибір модуля

Значення модуля m повинно бути достятньо великим, щоб забезпечити якнайбільший період послідовності, тому що максимальна довжина періоду не може бути більшою за m. Для привильного вибору множника а, потрібно щоб m було простим числом, тобто ділилось тільки саме на себе і не розкладалося на прості множники.

Таблиця 1.

Розрядність n	Максимальне число 2n-1	Розкладання на прості множники
6	63	3x3x7
7	127	-
8	255	3x5x17
9	511	7x73
10	1023	3x11x31
11	2047	23x89
12	4095	3x3x5x7x13
13	8191	-
14	16383	3x43x127
15	37367	7x31x151
16	65535	3x5x17x257
17	131071	-
18	261143	3x3x7x17x73
19	524278	-
…	…	…
31	2147483647	-

Як видно з таблиці 1, при n<32 усього 5 чисел є простими.

Таблиця 2.

Розрядність n	Максимальне число 2n-1	Розкладання на прості множники
7	127	-
13	8191	-
17	131071	-
19	524278	-
31	2147483647	-

При роботі з ЕОМ необхідно вибирати невелике число n=13, тому що при цьому для збереження кожного числа буде потрібно всього 2 байта пам’яті, а це значно спростить обробку чисел ц упорядкування програми генерації «псевдовипадкових» чисел. При меншому n=7 утворюэться занадто малий перыод генератора, а при великих n=17, 19 або 31 значно ускладнюється програма.

Число n=13 забезпечує жовжину періоду «псевдовипадкових» чисел рівною 8191.