1024-битный генератор псевдослучайных чисел в Verilog для FPGA

Я хочу генерировать случайные векторы длиной 1024 в verilog. Я рассмотрел некоторые реализации, такие как генераторы Таусворта и вихри Мерсенна. Большинство твистеров Мерсенна имеют 32-битные/64-битные выходные данные. Я хочу смоделировать шаблон ошибки 1024 бита с некоторой вероятностью p . Итак, я генерирую 32-битное случайное число (равномерно распределенное), используя Mersenne Twister. Поскольку у меня есть 32-битные случайные числа, это число будет находиться в диапазоне от 0 до 2^32-1. После этого я устанавливаю число равным 1, если число, сгенерированное из этого 32-битного значения, меньше p*(2^32-1). В противном случае число сопоставляется с 0 в моем 1023-битном векторе. По сути, каждое 32-битное число используется для генерации бита в векторе 1023 в соответствии с вероятностным распределением.

Приведенный выше метод подразумевает, что мне нужно 1024 тактовых цикла для генерации каждого 1024-битного вектора. Есть ли другой способ, который позволяет мне сделать это быстро? Я понимаю, что мог бы использовать несколько экземпляров Mersenne Twister параллельно, используя разные начальные значения, но я боялся, что эти числа не будут действительно случайными и что будут коллизии. Есть ли что-то, что я делаю неправильно или что-то, чего мне не хватает? Я был бы очень признателен за вашу помощь


random fpga verilog mersenne-twister
person Sushrut Kaul    schedule 20.01.2019    source источник
comment
Я не думаю, что это сработает. Вероятность того, что бит равен 1, равна p. Итак, если p мало, вы получите 1024-битные числа с несколькими единицами. например, с очень низким p у вас есть высокая вероятность иметь только 1 бит, который дает числа 1,2,4,8...   -  person Oldfart    schedule 20.01.2019

Ответы (1)


arrow_upward
1
arrow_downward

Итак, я немного почитал о Мерсеннских вихрях в целом из википедии. Я согласен, что не сразу понял все это, но я получил следующее: при заданном начальном значении (для инициализации массива) модуль генерирует 32-битные случайные числа.

Теперь, из вашего описания выше, для вычисления одного случайного числа требуется один цикл.

Таким образом, ваша проблема в основном сводится к математике, а не к verilog как таковой.

Я постараюсь объяснить математику как можно лучше.

У вас есть 32-битное равномерно распределенное случайное число. Таким образом, вероятность того, что любой бит равен high или low, точно равна (ну, близка к псевдослучайной) 0.5.

Давайте забудем, что это псевдослучайный генератор, потому что это лучшее, что вы получите (так что давайте считать это нашим идеалом).

Даже если мы сгенерируем 5 чисел одно за другим, вероятность того, что каждое из них будет каким-либо конкретным числом, по-прежнему будет равномерно распределена. Итак, если мы соединим эти пять чисел, мы получим 160-битное совершенно случайное число.

Если это все еще не ясно, подумайте об этом.

Я разберу проблему. Допустим, у нас есть 4-битный генератор случайных чисел (ГСЧ), и нам нужны 16-битные случайные числа.

Каждый выход ГСЧ будет шестнадцатеричным числом с равномерным распределением вероятностей. Таким образом, вероятность получить какую-то конкретную цифру (скажем... A) равна 1/16. Теперь я хочу сделать 4-значный шестнадцатеричный номер (скажем... 0xA019).

Вероятность получения А в качестве старшей цифры = 1/16

Вероятность получения 0 в качестве числа 2 = 1/16

Вероятность получения 1 в качестве цифры 3 = 1/16

Вероятность получения 9 в качестве младшей значащей цифры = 1/16

Таким образом, вероятность получения 0xA019 = 1/(2^16). На самом деле, вероятность получения любого четырехзначного шестнадцатеричного числа будет точно такой же. Теперь распространите ту же логику на системы счисления с основанием 32 с 32-значными числами в качестве требуемого вывода, и вы получите свое решение.

Итак, мы видим, что мы могли бы сделать всего 32 повторения скручивания Мерсенна, чтобы получить 1024-битный вывод (это заняло бы 32 цикла, все еще довольно медленно). Что вы также можете сделать, так это синтезировать 32 твистера параллельно (это даст вам результат за один ход, но будет очень тяжело для fpga с точки зрения площади и ограничений по мощности).

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

Что касается предоставления различных начальных значений, большинство PRNG обычно предусматривают входные начальные значения только для увеличения случайности, из того, что я читал в Mersenne Twisters, это тот же случай.

Надеюсь это ответит на твой вопрос.

person Parth K    schedule 21.01.2019
comment
Я думал о твоем комментарии. Проблема здесь в следующем: нам нужно, чтобы в 1024-битном числе было мало единиц. По сути, идея состоит в том, чтобы сделать декодер с исправлением 3 ошибок. Это означает, что у меня есть 1024-битный шаблон. Вы можете перевернуть до 3 бит (позиция не имеет значения), и мой декодер сможет исправить эти ошибки. Чтобы проанализировать производительность моего декодера, мне нужно иметь возможность запускать симуляции. Мне нужны векторы (случайные) для этой цели. Теперь, если я соединим 32 числа, каждые 32 бита, чтобы получить этот 1024-битный шаблон, каждое из 32-битных чисел будет между 0 и 2^32-1. - person Sushrut Kaul; 21.01.2019
comment
Таким образом, весьма вероятно, что я получу более 3 ошибок во всем 1024-битном кодовом слове. Как я уже говорил ранее, мой декодер способен исправить только до 3-х случайных ошибок. Если он получит больше этого, он просто объявит об ошибке декодирования, и это будет происходить часто, если мы будем следовать предложенной вами схеме. - person Sushrut Kaul; 21.01.2019
comment
Кажется, что вы хотите имитировать декодер с исправлением ошибок, - person Parth K; 21.01.2019
comment
Таким образом, в основном вы хотите, чтобы генератор случайных чисел дал вам число, состоящее не более чем из трех единиц. Тогда я предполагаю, что вы будете переворачивать биты (в исходном 1024-битном вводе) в тех позициях, где случайное число имеет единицы. - person Parth K; 21.01.2019
comment
Если это так, возможный альтернативный способ сделать это — просто сгенерировать 3 11-битных числа. Это даст вам три числа в диапазоне 0-1023. Затем вы можете принять решение, переворачивать или не переворачивать соответствующий бит, основываясь на старшей значащей цифре числа. - person Parth K; 21.01.2019