Почему выходы этого генератора псевдослучайных чисел (LFSR) настолько предсказуемы?

Недавно я спросил здесь, как генерировать случайные числа в аппаратном обеспечении и было сказано использовать LFSR. Он будет случайным, но начнет повторяться после определенного значения.Почему выходы этого генератора псевдослучайных чисел (LFSR) настолько предсказуемы?

Проблема в том, что генерируемые случайные числа настолько предсказуемы, что следующее значение можно легко догадаться. Например, проверьте ниже моделирование:

enter image description here

Следующее «случайное» число можно угадать, добавив предыдущий номер с +1 самих по себе. Может кто-то, пожалуйста, проверьте, нормально ли это и что ожидать.

Вот код, я использовал для LFSR:

module LFSR(
    input clock, 
    input reset, 
    output [12:0] rnd 
    ); 

wire feedback = rnd[12]^rnd[3]^rnd[2]^rnd[0]; 

reg [12:0] random; 

always @ (posedge clock or posedge reset) 
begin 
    if (reset) 
     random <= 13'hF; //An LFSR cannot have an all 0 state, thus reset to FF 
    else 
     random <= {random[11:0], feedback}; //shift left the xor'd every posedge clock 
end 

assign rnd = random; 

endmodule

Расположение битов в XOR подобраны здесь: The table page 5

источник

2013-02-10 ipunished

Подождите, пока «1 достигнет MSB, а затем посмотрите, все ли последующие номера« предсказуемы »... –

Приношу свои извинения. Я ответил поспешно и рассердился. Это было явно неуместно с моей стороны. –

ЛРСОС генерирует только один случайный бит за такт. Он не генерирует новое (в вашем случае) 13-битное число каждого цикла. Остальные 12 бит в rnd - это только старые случайные значения, поэтому он не будет казаться очень случайным.

Если вам нужно 13-битное случайное число, вы должны либо пробовать LFSR каждые 13 циклов, либо поставить 13 LFSR параллельно с разными семенами, а использовать 13 нулевых бит в качестве вашего случайного числа.

источник

2013-02-10 17:50:17 Tim

Спасибо. Мне удалось заставить его работать, пробовав резистор каждые 13 циклов, как вы предложили. И теперь он случайный, поэтому по этому методу теперь он истинный случайный? это уже не псевдо? Я избегал вашей параллельной реализации, так как было бы нецелесообразно повторять весь этот код, например, 100-битный LFSR. – ipunished

Нет, это все еще псевдослучайно, поскольку следующее число можно было предсказать, зная алгоритм, используемый для его создания, и текущее состояние системы. Но хороший псевдослучайный случай, вероятно, так же хорош, как и истинный случайный для большинства целей (не связанных с безопасностью). – Tim

Вам не нужно ждать 13 тактов, чтобы получить 13 бит. Вы можете развернуть цикл и добавить еще XOR, чтобы предсказать, какое значение будет в 13 циклов. Конечно, это логично, так что это может не сработать для вас. – nguthrie

-1

LFSR, безусловно, не является «случайным» в каком-либо реальном смысле. Процитировать фон Неймана «Любой, кто рассматривает арифметические методы производства случайных цифр, конечно, находится в состоянии греха». Я не искал, являются ли выбранные вами условия обратной связи максимальными, что означает, что они предоставят последовательность с длиной, равной количеству бит в вашем LFSR, но это лучшее, что вы можете сделать.

Так что да, следующее значение в вашем LFSR чрезвычайно предсказуемо. Если вам нужно что-то более безопасное «случайное», вам нужно заглянуть в криптографические методы, они, конечно, зависят от секретного ключа и также намного более интенсивно вычислительны, чем LFSR. Вы получаете то, за что платите ».

Кстати, система, в которой вы получаете предсказуемые «случайные» номера, очень полезна сама по себе. Обычно для целей моделирования.

источник

2013-02-10 22:17:05

Почему выходы этого генератора псевдослучайных чисел (LFSR) настолько предсказуемы?

ответ

Смежные вопросы