псевдослучайное перемешивание с малым объемом памяти для фиксированного массива произвольной длины - PullRequest
Новая
       50

псевдослучайное перемешивание с малым объемом памяти для фиксированного массива произвольной длины

0 голосов
/ 27 февраля 2020

Контекст: я пишу внешний тестер SRAM для встроенной системы на основе микроконтроллера. Без защиты, без криптографии. Для воспроизводимого доступа к областям памяти «как непоследовательный как возможный» я ищу реализацию

y = shuffle(x), принимающую и возвращающую целое число от 0 до фиксированного N = 2 ^ 16 - 1

Он может не использовать много ОЗУ, как, например, простое перетасованное массив адресов. С другой стороны, это разрешено быть медленным. Нет строгого определения непоследовательности - речь идет об увеличении и уменьшении адресных линий, поиске пайки и других неисправностях печатной платы. Предложения?

Я нашел до сих пор Кнут Шафл ака Фишер-Йейтс Шафл .

Поздний РЕДАКТИРОВАТЬ : я думаю, Я пытаюсь максимально увеличить расстояние Хэмминга. " Анти-серый код "?

Ответы [ 2 ]

2 голосов
/ 28 февраля 2020

Я согласен с Джимом Мишелем в том, что xorshift - хороший кандидат на быстрый нешифрующий PRNG. Необходимо тщательно выбирать коэффициенты для достижения полного цикла, который включает в себя все значения, кроме 0.

Поскольку вы задали для проблемы 16 бит в своем вопросе, вот 16-битная реализация, написанная на Ruby, но легко перенесенная на все остальное, что вам нравится: 

# << is shift left, >> is shift right, ^ is bitwise XOR, & is bitwise AND

MASK_16 = (1 << 16) - 1

def xorshift(x)
  x ^= x << 7 & MASK_16
  x ^= x >> 9
  x ^= x << 8 & MASK_16
  return x
end

counter = 0
x = 1
y = 1

# Floyd's "Tortoise and Hare" cycle-finding algorithm shows
# the generator to be full cycle for 16 bits, excluding zero.
loop do
  counter += 1
  x = xorshift(x)
  y = xorshift(xorshift(y))
  break if x == y
end
puts counter   # => 65535
2 голосов
/ 27 февраля 2020

Я бы предложил реализовать Xorshift или что-то подобное. Они быстрые, требуют мало памяти, могут быть построены так, чтобы иметь длительный период, и удовлетворять многим тестам случайности.

Другой способ сделать это - уникально отобразить каждое число в диапазоне 0 .. (n -1) на другой номер в этом диапазоне. Это достаточно легко сделать с помощью модульного обратного умножения, как я описываю в этот ответ .

...