Генератор случайных чисел с использованием 8051

1.3 Метод Фибоначчи с запаздываниями

В этом алгоритме используется соотношение
Xi = Xi-a — Xi-b,
где переменная состояния X — беззнаковое целое. Величины запаздываний a и b берутся не какие угодно, а строго определенные, для достижения максимального качества рекомендуются пары (17,5), (55,24) или (97,33). Чем больше запаздывания, тем больше период и лучше спектральные свойства последовательности. С другой стороны, для работы генератора требуется хранить max{a,b} предыдущих чисел, что не всегда приемлемо. Также для запуска генератора нужно max{a,b} чисел, которые обычно получают при помощи более простого ГПСЧ.
Плюсы:

• 
  не требует операций умножения;
  
• 
  все биты случайного числа равнозначны по статистическим свойствам.
  

Минусы:

• 
  требует большого объема памяти;
  
• 
  требует большого массива чисел для запуска.
  

Резюме: очень качественный, но ресурсоемкий алгоритм.

Рис 1.2 Регистр сдвига с линейной обратной связью
Переменная состояния хранится в регистре длины N. Генерация следующего состояния включает два шага:
Подсчитывается значение бита C = Xi1 xor Xi2 xor… Xik, где i1, i2… ik — номера битов регистра, называемые отводами.
Регистр сдвигается на 1 бит вправо, крайний левый бит принимает значение С.
Выходом генератора является крайний правый (или крайний левый, или любой другой) бит регистра, то есть псевдослучайная последовательность генерируется по одному биту за итерацию. При правильно выбранных номерах отводов период генератора составит 2N — 1. «Минус один», так как существует запрещенное нулевое состояние регистра. Номера отводов для N от 3 до 168 можно посмотреть в этом документе.
Рис 1. 3 - Конфигураця Фибоначчи
Кроме описанной выше конфигурации, которая, кстати, называется конфигурацией Фибоначчи (не путать с одноименным методом ГПСЧ!), существует т.н. конфигурация Галуа.
Вместо того, чтобы использовать для генерации нового крайнего левого бита сумму битов отводной последовательности, выполняется XOR каждого бита отводной последовательности с крайним правым битом, затем выполняется циклический сдвиг всего регистра вправо. Эта схема сложнее для понимания, но проще в реализации, так как все опрерации XOR можно выполнить одновременно. По длине периода и качеству псевдослучайных чисел схемы Фибоначчи и Галуа эквивалентны.
Плюсы:

• 
  очень простая реализация, не требуется даже арифметики, только битовые операции и сдвиги;
  
• 
  очень быстрый алгоритм (особенно схема Галуа);
  
• 
  хорошие статистические свойства.
  

Минусы:

• 
  нужно проверять начальное значение на неравенство нулю.
  

Резюме: очень быстрый и довольно качественный алгоритм.