Программные датчики. Общая модель.docx

Программные датчики. Общая модель

a   = j (a   ,...,a    ),   <

l                i

Исходные   величины    a a

a 2 ,...,a -( p-1)

фиксируются   заранее   и    называются

стартовыми величинами. Линейные рекуррентные формулы

1.      Мультипликативный конгруентный метод (метод вычетов)

a = (þ ×a -1 )mod

, = 1,2,...

þ M a 0

–   натуральные числа – параметры программного датчика.

a a ,.. Î {0,1,..., (M - 1)}

Эта ПСП зацикливается, начиная с некоторого номера i = T. Её период, равный Т, не превосходит М-1.

Пусть М = 2^q, q – количество бит целой константы ПК. Тогда: T_max = 2^q-2 = M/4 достигается, если:

1)   a 0    – нечётное число, причём   £ a 0 £ M - ;

2)   b mod 8 = 3 mod 8 или b mod 8 = 5 mod 8.

Это условие выполняется, например, при b = 5^2p+1, p = 0,1,2,… , или когда b = 2^m + 3, m

= 3,4,5,…

2.      Метод, использующий линейные смешанные формулы, в частности, смешанный конгруентный метод.

a = (þ ×a -1 +

)mod

, i = 1,2,...

Для получения максимального периода следует брать М = 2ⁿ и использовать b = 2^q + 1,

q    ³ 2, C – нечётное и a 0

условия b mod 4 = 1.

–    произвольное. Хоффман рекомендует выбирать b из

Методы, использующие нелинейные рекуррентные формулы

3.      Метод середины квадрата.

(((     )2 )mod 23k

((a

)2 )mod 22

)/ 2

, i = 1,2,...

Параметры датчика: k и

a 0 . Заметим, что a 0

–    число, образованное средними 2k

битами 4k-разрядного двоичного числа (a

i -1

)2 .

4.      Модификация метода – метод середины произведения.

((       a i

)mod 23k - (a

×a -

))/ 2k , i = 1,2,...

5.      Квадратичный конгруентный метод (обобщение линейного).

(  (a

)2  + þ ×a    +

)mod

, i = 1,2,...

Параметры датчика: a 0

þ ,y ,   .

Если М = 2^q и q ³ 2, то наибольший период

Т_max = M = 2^q достигается, если b, С – нечётные, g – чётное, причём

þ mod 4 = (y + 1)mod 4

6.      Метод Маклорена-Марсальи.

Метод основан на комбинации двух простейших датчиков. Пусть {b_i}  и  {c_i},  i  = 0,1,2,… есть ПСП, порожденные двумя независимо работающими датчиками D₁ и D₂ соответсвенно. А V = {V(0), V(1), …, V(k-1)} – вспомогательная таблица из k целых чисел.

Сначала таблица V заполнена k членами ПСП {b_i}, т.е. V(j) = b_j , j = 0,1,2,…,k-1.

Результирующая ПСП получается в результате следующей последовательности действий:

s := Int(c_j×k)

d_i := V(s)             i = 1,2,… V(s) := b_i+k

Т.е. датчик D₂ делает случайный выбор из таблицы V, а также случайно заполняет её числами, порождёнными датчиком D₁. Можно получить очень большой период ПСП, если периоды датчиков D₁ и D₂ – взаимно простые числа.