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

Недавно я спросил здесь, как аппаратно генерировать случайные числа, и мне сказали использовать LFSR. Это будет случайным образом, но начнет повторяться после определенного значения.

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

введите здесь описание изображения

Следующее «случайное» число можно угадать, добавив к предыдущему числу +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 взято отсюда: страница таблицы 5< /а>


fpga verilog hdl hardware
person ipunished    schedule 10.02.2013    source источник
comment
Подождите, пока '1 не достигнет старшего разряда, а затем посмотрите, предсказуемы ли последующие числа...   -  person Oliver Charlesworth    schedule 10.02.2013
comment
Мои извенения. Я ответил в спешке и гневе. Это было явно неуместно с моей стороны.   -  person Brian Magnuson    schedule 11.02.2013

Ответы (2)


arrow_upward
6
arrow_downward

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

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

person Tim    schedule 10.02.2013
comment
Спасибо. Мне удалось заставить его работать, отбирая резистор каждые 13 циклов, как вы предложили. И это теперь случайно, так что теперь по этому методу это правда случайно? это уже не псевдо? Я избегал вашей параллельной реализации, так как было бы нецелесообразно повторять весь этот код, скажем, для 100-битного LFSR. - person ipunished; 11.02.2013
comment
Нет, это по-прежнему псевдослучайное число, поскольку следующее число можно предсказать, зная алгоритм, использованный для его создания, и текущее состояние системы. Но хороший псевдослучайный, вероятно, так же хорош, как и настоящий случайный, для большинства целей (не связанных с безопасностью). - person Tim; 11.02.2013
comment
Вам не нужно ждать 13 тактов, чтобы получить 13 бит. Вы можете развернуть цикл и добавить больше XOR, чтобы предсказать, какое значение будет через 13 циклов. Конечно, это целая логика, поэтому она может не сработать для вас. - person nguthrie; 22.11.2013

arrow_upward
-1
arrow_downward

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

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

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

person Brian Magnuson    schedule 10.02.2013