МАРСОХОД

Open Source Hardware Project

Проекты Altera Quartus Prime для платы Марсоход3

Простой генератор псевдослучайных чисел

lfsr, Регистр сдвига с линейной обратной связью
Давно ничего не писал в блоге Марсохода - много всякого навалилось, всякие дела, командировка, встречи..
Вот решил восполнить пробел и сделать очень простой проект. Простые проекты ведь тоже нужны, особенно тем, кто только начинает изучать ПЛИС. Это проект выходного дня. Собственно я его в воскресенье и сделал, а вот описать его - это то же работа требующая времени и внимания.

Очень простой генератор случайных чисел. Такой простой, что я его даже и не придумывал, а просто взял описание в википедии: Регистр сдвига с линейной обратной связью. В англоязычной литературе такой метод генерации псевдослучайных чисел называется linear feedback shift register, LFSR.

Берется сдвиговый регистр и по каждому такту сдвигается вправо, а новый, вычисленный бит задвигается в регистр слева. Вычисление нового бита ведется операцией исключающего ИЛИ (XOR).

Написать такое на языке описания аппаратуры Verilog HDL - очень просто:


 module lfsr(

  input wire rst,
  input wire clk,
  input wire enable,
  output wire [31:0]out,
  output wire [7:0]out_lb
);

reg [31:0]shift_reg;
assign out = shift_reg;
assign out_lb = shift_reg[7:0];
wire next_bit;
assign next_bit =
  shift_reg[31] ^
  shift_reg[30] ^
  shift_reg[29] ^
  shift_reg[27] ^
  shift_reg[25] ^
  shift_reg[ 0];

always @(posedge clk or posedge rst)
  if(rst)
    shift_reg <= 32'h00000001;
  else
  if(enable)
    shift_reg <= { next_bit, shift_reg[31:1] };

endmodule


Вычисление нового значения сдвигового регистра происходит в строке shift_reg <= { next_bit, shift_reg[31:1] }; 
Следующий задвигаемый бит next_bit вычисляется выше: assign next_bit =...

Нужно обратить внимание, что регистру shift_reg обязательно требуется начальная инициализация, сброс по сигналу rst. В сдвиговый регистр нужно положить что-то отличное от нуля, иначе next_bit так и останется в нуле и они, эти нули так и будут бегать по кругу в сдвиговом регистре.

Предположим, модуль генерации псевдослучайных чисел готов. Что дальше? Я думаю пусть плата Марсоход3 с ПЛИС MAX10 генерирует случайные байты и я буду отправлять их через последовательный порт в компьютер. А на компьютере напишу программу, которая будет принимать поток байт и строить гистограмму распределения случайных чисел в интервале времени.

Значит теперь мне нужен модуль передачи в последовательный порт:


module serial(
  input wire clk12,
  input wire [7:0]sbyte,
  input wire sbyte_rdy,
  output wire tx,
  output wire end_of_send,
  output wire ack
);

reg [9:0]sreg;
assign tx = sreg[0];
reg [3:0]cnt = 0;
wire busy; assign busy = (cnt<11);
assign ack = sbyte_rdy & ~busy;

always @(posedge clk12)
begin
  if(sbyte_rdy & ~busy)
    sreg <= { 2'b11, sbyte, 1'b0 }; //load
  else
    sreg <= {2'b11, sreg[9:1] }; //shift

  if(sbyte_rdy & ~busy)
    cnt <= 0;
  else
  if(busy)
    cnt <= cnt + 1'b1;
end

reg prev_busy;
always @(posedge clk12)
  prev_busy <= busy;

assign end_of_send = busy==1'b0 && prev_busy==1'b1;

endmodule


По сигналу sbyte_rdy входной байт sbyte фиксируется в сдвиговом регистре sreg. Как-то я писал про передачу в последовательный порт. При этом, в младший бит регистра записывается ноль - это будет старт-бит, а 9й и 10й биты - записываются единицы - это будут стоп биты. Далее по каждому такту данные сдвигается влево, младшими вперед.

Счетчик cnt сбрасывается в начале передачи и считает переданные биты до 11-ти. По окончании передачи выдается имульс end_of_send - конец передачи. Дальше в проекте я хочу, чтобы сигнал окончания передачи тут же брал следующий байт из генератора псевдослучайных чисел и начинал следующею передачу.

Как мне все это проверить? В принципе проект простой, можно сразу в плате пытаться смотреть как работает, например, с помощью Altera SignalTap.

Но я думаю было бы интересно, например, сделать функциональную симуляцию этих двух модулей: lfsr и serial.
Для симуляции нужен тестбенч. Это такая же программа на Verilog, но только ее цель - это исключительно отладка проекта. В тестбенче я соединю модули lfsr и serial и подам на них тактовую частоту. Вот тестбенч:


 module tb;

reg clk;
reg rst;

initial
begin
  clk <= 1'b0;
  while (1)
  begin
    #5 clk <= ~clk;
  end
end

wire w_tx,w_ack;
wire [31:0]w_random;

lfsr u_lfsr(
  .rst( rst ),
  .clk( clk ),
  .enable( w_eos ),
  .out( w_random )
  );

serial u_serial(
  .clk12( clk ),
  .sbyte( w_random[7:0] ),
  .sbyte_rdy( w_eos ),
  .tx( w_tx ),
  .end_of_send( w_eos ),
  .ack( w_ack )
  );

initial
begin
  $dumpfile("out.vcd");
  $dumpvars(0,tb);
  rst <= 1'b1;
  #50 rst <= 1'b0;
  #100;
  #10000;
  $finish;
end

endmodule


Выход генератора псевдослучайных чисел u_lfsr проводами w_random подключен к модулю u_serial. Сигнал окончания передачи u_serial.end_of_send проводом w_oes передается на u_lfsr.enable для генерации следующего числа и начинает новую передачу u_serial.sbyte_rdy( w_eos ).

Для симуляции использую Icarus Verilog.
Компилирую: iverilog -o outfile tb.v serial.v lfsr.v
Симулирую: vvp outfile
В результате получаю временные диаграммы out.vcd, которые можно посмотреть программой GtkWave:

waveform icarus verilog, gtkwave

Теперь, убедившись с помощью симуляции, что все должно работать, перехожу к проекту в среде Quartus Prime.
Эта среда проектирования используется для разработки проектов для микросхем ПЛИС серии Altera MAX10.
За основу своего проекта я беру проект leds с нашего сайта и вставляю туда мои модули.
Получается вот такой топ модуль:

prj top

Для тех, кто впервые использует квартус: сделать графический компонент из текста verilog просто: из главного меню пункты File => Create / Update => Create Symbol Files for Current File. Потом получившиеся модули можно вставить в графический дизайн через правый клик мыши и Insert => Synbol...

В топ модуле кроме lfsr и serial еще есть модуль display - это совсем простая штука, случайные числа генерируются слишком часто. Если их просто вывести на светодиоды, то они просто будут равномерно светиться. Поэтому тут в модуле display я буду показывать только случайный байт из последовательности один раз примерно в 200 миллисекунд.

Ну и обратите внимание на вход кнопочки KEY0 - это сброс генератора.
В настройках проекта (в меню Assignments => Assignment Editor) на кнопочке KEY0 прямо в ПЛИС назначен подтягивающий резистор Weak Pull Up Resistor. Эта фишка есть только в микросхемах серии MAX II и MAX10. В Cyclone III или Cyclone IV такого нет. Если кнопочку на плате Марсоход3 не нажимать, то подтягивающий резистор делает единицу на входе KEY0. Когда кнопочка нажата - то ноль.

Выход модуля передатчика serial идет на вывод ftdi_bd1, который, в свою очередь идет на микросхему FTDI на плате Марсоход3. Она позволяет организовать связь платы Марсоход3 с компьютером через последовательный порт FTDI USB-to-COM.

Чтобы дополнительно проиллюстрировать работу генератора я встроил в систему модуль SignalTap. Он позволит смотреть в реальном времени некоторые сигналы проекта прямо из чипа ПЛИС, а именно вот эти три сигнала: serial:inst7|tx, serial:inst7|end_of_send, и serial:inst7|sbyte[7..0].

Altera SignalTap Waveforms

Ну или вот другой масштаб, чтобы увидеть "шум" случайных чисел:

Altera SignalTap Waveforms

Теперь следующая задача.
Нужно для компьютера написать программу, которая будет читать из последовательного порта и рисовать гистограмму плотности вероятности случайных чисел за какой-то промежуток времени. Я написал эту программу для Windows в среде Visual Studio 2012. Программа, как диалоговое окно MFC.

гистограмма распределения случайных чисел из генератора LFSR

Программа открывает последовательный порт (тот который в выпадающем списке в дропбоксе), программирует его на скорость передачи 12МБит/Сек - такая скорость передачи из платы и периодически выполняет чтение и порта всех имеющихся там данных. По этим принятым байтам строится гистограмма значений и рисуется на экране.

Весь проект для среды Quartus Prime и Visual Studio можно скачать вот здесь: 

Ну и видео демонстрация как это все работает:

В принципе, распределение похоже на равномерное. Значит мой генератор работает!

Однако, должен предупредить, что это, конечно, очень примитивный генератор.
Это написано и в Википедии, по которой я делал свой проект и в разных других источниках. Говорят, что анализируя последовательность байт из такого генератора очень легко раскрыть его структуру и, следовательно, предсказывать последующие значения. Таким образом, использовать такие генераторы в программах шифрования напрямую нельзя. Другое дело, что эти алгоритмы могут сочетаться при использовании нескольких независимых генераторов разной природы. Например, можно установить два независимых генератора с разными схемами обратной связи и коммутировать его третьим. Такие методы могли бы улучшить распределение и сделать генератор более криптостойким.

Пожалуй нужно еще добавить, что современные процессоры Интел (теперь - подразделение компании Альтера, ой, шучу.. наоборот) имеют встроенные аппаратные генераторы случайных последовательностей. Причем они используют для создания случайных последовательностей несколько асинхронных "источников энтропии" (Entropy Source) от теплового шума кристалла (The ES runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz). Такой генератор повторить или хотя бы сделать подобный в "гаражных" условиях весьма трудно. Еще труднее доказать, что созданный генератор случайных чисел имеет действительно равномерное распределение и действительно весьма случаен. Кому интересно, про генераторы случайных чисел в процессорах Интел написано вот здесь.

 PS: у этой статьи есть продолжение.

Комментарии  

+2 #7 Eka 09.12.2016 10:25
как посмотреть по симуляции выходные числа для самого регистра? какие сигналы нужно брать?
+1 #6 ева 09.12.2016 03:17
извините, а у вас нет этой программы написанной в Altera Quartus II 13.0 ? очень нужно :cry: :cry:
+1 #5 nckm 17.03.2016 06:32
Цитирую Alexandr:
Приветствую!
"В принципе, распределение похоже на равномерное. Значит мой генератор работает!"
Этого недостаточно! Плотность распределения будет равномерной и у пилы. Тема интересная, но доведите до логического конца, раз уж перегнали данные в ПК, то вычислите период повторения, спектр, автокорреляционную функцию.

вы, конечно, правы..
+3 #4 Alexandr 16.03.2016 18:06
Приветствую!
"В принципе, распределение похоже на равномерное. Значит мой генератор работает!"
Этого недостаточно! Плотность распределения будет равномерной и у пилы. Тема интересная, но доведите до логического конца, раз уж перегнали данные в ПК, то вычислите период повторения, спектр, автокорреляцион ную функцию.
+1 #3 teslacoil 16.03.2016 16:41
Кудысь летали если не секрет? :lol:
+1 #2 nckm 15.03.2016 08:08
Цитирую nfader:
...и получился обычный генератор М-последовательности..
А вместо сброса все-таки лучше использовать выход из запрещенного состояния (все нули), а то мало-ли.. :)

Ну я в общем и не планировал делать что-то сильно умное..
А вот сброс по нулю - это хорошая мысль.
+1 #1 nfader 14.03.2016 20:38
...и получился обычный генератор М-последовательности..
А вместо сброса все-таки лучше использовать выход из запрещенного состояния (все нули), а то мало-ли.. :)

Добавить комментарий


Защитный код
Обновить


GitHub YouTube Twitter
Вы здесь: Начало Проекты Проект Марсоход3 Простой генератор псевдослучайных чисел