Я программирую LFSR (регистр сдвига с линейной обратной связью) в программном обеспечении для целей обучения и столкнулся с некоторыми ограничениями в его использовании в качестве генератора псевдослучайных чисел (PRNG).
- Если начальное число имеет несколько битов «1» и используется несколько отводов, требуется большое «время запуска» для получения явно случайного вывода с почти равным распределением между прогонами «1» и «0» или «короткими» 0. Я предполагаю, что при большем количестве нажатий такой запуск будет намного быстрее, но все таблицы, которые я рассчитал, дают два или четыре нажатия.
- Последовательные числа сильно коррелированы, что и следовало ожидать, учитывая, что если выходной бит равен 0, следующее число будет половиной предыдущего. Для 15-разрядного LFSR с ответвлениями [15, 14] построение пары последовательных чисел в виде точек на плоскости дает следующее. Идеальный PRNG должен распределить эти точки повсюду.
Я знаю, что LFSR используются в качестве быстрого аппаратного счетчика, но я также видел, что он используется в качестве PRNG для создания белого шума. Как это используется в таких реальных приложениях с таким низким качеством?
digital-logic
Бруно Ким
источник
источник
Ответы:
Отличным источником для всего PRNG является «Последовательности регистра сдвига» Соломона Голомба. Здесь обсуждаются различные классы и приемы.
Для запуска путем сброса всех регистров является одним из способов. Или параллельная загрузка семени - это другое. Но помните, что жало всех нулей является допустимым состоянием.
Выбор правильных кодов важен, поскольку не каждая настройка обратной связи в сдвиговом регистре гарантирует получение максимальной последовательности PRNG.
То, как вы работаете с PRNG, влияет на его производительность.
Для 15-битного регистра и поиска кодов [15,4] является максимальным, как [15,1], но [15,14] не указан. -> Источник - «Системы и приложения с расширенным спектром» - Роберт Диксон, 3-е изд. Стр. 94. Эта книга - очень хороший справочник по реализации.
В общем случае LFSR создают плохие PRNG, и общая практика заключается в использовании только младших битов. В качестве альтернативы вы можете сгенерировать два PRNG различной длины и кодов и xor младших битов для генерации нового кода. Вероятно, следует использовать менее половины длины бит. Таким образом, регистр длиной 30 и 31 бит и XOR 15 LSB.
NIST имеет отличный тестовый код здесь . Так что да, это отстой, для PRNG.
источник
[nbits, a, b, c], другой набор, который является максимальным[nbits, nbits-a, nbits-b, nbits-c]. Таким образом, [15,14] и [15,1] являются максимальными.Если вы хотите генерировать случайные числа с 15-битным LFSR, вы не тянете новое случайное число каждый тактовый цикл. Как вы сказали , так как вы только добавив один новый бит в регистр каждый тактовый цикл, значение в цикле
NиN+1будет очень сильно коррелируют. Если вы хотите сгенерировать случайные значения (при условии, что у вас есть правильные нажатия), то вам нужно только вытягивать новое значение каждые 15 часов.LFSR гарантирует вам только один случайный бит за цикл, а не 15 случайных бит.
источник
Пример из реальной жизни можно найти в Справочном руководстве по семейству микропроцессоров MPC7450. 7450 использовал pRNG для замены L2 и L3, который состоит из 16 защелок, имеющих три простых регистра сдвига с битами от 0 до 4, битами с 5 по 9 и битами с 10 по 15. Бит 0 происходит от XOR битов 4 и 15, бит 5 исходит из XOR битов 4 и 9, а бит 10 - из XOR битов 6 и 15. Путь замены в 8-канальных кэшах указывается битами 4, 9 и 15 для L2 и битами 0 5 и 10 для L3. Биты менялись каждый цикл, но, очевидно, замены кеша происходили не так часто. (Был также предоставлен альтернативный механизм замены на основе счетчика.)
Это было признано потенциально проблемным:
источник