4
\$\begingroup\$

I want to generate a random bit sequence using Verilog. i.e. the random bit sequence would be composed of 1 and 0. Can someone guide me as to how to do it? Does anything equivalent of rand() in C/C++ exist in Verilog?

Update-1: FPGA is Spartan 3E Starter Kit

\$\endgroup\$
  • 2
    \$\begingroup\$ You can create a pseudo-random generator using shift registers and XOR gates, but I don't know about the Verilog implementation \$\endgroup\$ – clabacchio Apr 23 '12 at 8:18
  • 1
    \$\begingroup\$ The PRBS options that clabacchio and Curd have suggested produce a sequence with statistical properties similar to random numbers, which is useful for lots of things. But they are very predictable, so not at all useful for, for example, cryptography. Is a PRBS good for your application or do you need a truly random sequence? \$\endgroup\$ – The Photon Apr 23 '12 at 15:39
  • \$\begingroup\$ Also, are you working in FPGA or ASIC, or is this for a testbench? and if you're designing an FPGA, which vendor? -- because some vendor's FPGAs have hardware tricks that can be used to build an LFSR/PRBS circuit efficiently. \$\endgroup\$ – The Photon Apr 23 '12 at 15:40
  • \$\begingroup\$ I am working on Spartan 3E Starter Kit \$\endgroup\$ – Neel Mehta Apr 23 '12 at 18:49
  • \$\begingroup\$ If you need real randomness for some reason (crypto and gambling being the main ones) I recommend you hook up a source of random pulses to the FPGA (such as shot noise of a PN junction) and use a counter in the FPGA to distill random bits. \$\endgroup\$ – drxzcl Apr 23 '12 at 19:27
7
\$\begingroup\$

You probably do want something like the circuit shown by clabacchio.

This is easily rendered in Verilog as

reg [4:0] d;
always @(posedge clk) begin
    d <= { d[3:0], d[4] ^ d[2] };
end

This is, as others mentioned, a linear feedback shift register, or LFSR, and it generates the maximal length pseudo-random bit sequence that can be produced with a 5-bit state machine. The state machine traverses 31 states (\$2^n-1\$, where n is the number of registers) before repeating itself.

Of all the states that can be encoded by 5 registers, only one is not used, which is the all-0's state. The all-0's state is a lock-up state --- if the state machine gets into that state by an error, it will be stuck permanently in the all-0's state, as you can see because 0 ^ 0 = 0. This means you have to be sure (using a synthesis directive in the Verilog or constraints file) that the registers don't initialize to the all-0's state.

If you need the all-0's state not to lock up, you can use an XNOR in place of the XOR gate, and get a sequence that includes the all-0's state and locks up in the all-1's state.

Also be aware that the longest run of 1's produced by this state machine is 5 in a row, and the longest run of 0's is 4 in a row. This can be important if you are using the PRBS to test a system with ac-coupling...longer runs will stress the system more.

In communications testing, longer sequences are more common, mainly to exercise more of the low frequency behavior of the system:

PRBS7

reg [6:0] d;
always @(posedge clk) begin
    d <= { d[5:0], d[6] ^ d[5] };
end

PRBS23

reg [22:0] d;
always @(posedge clk) begin
    d <= { d[22:0], d[22] ^ d[17] };
end

PRBS31

reg [30:0] d;
always @(posedge clk) begin
    d <= { d[30:0], d[30] ^ d[27] };
end

Notice that it is not always the final two registers that are "tapped" to generate the incoming bit of the shift register.

Xilinx app note XAPP052 gives a handy table of connections to be used to generate any size PRBS from 3 to 168 registers.

App note XAPP211 shows how to implement them efficiently in Xilinx devices. Essentially, a single look-up table in a single logic block can be used to implement up to 32 registers worth of shift register (depending on architecture).

LFSRs can also be used to implement a counter efficiently if you don't care about the intervening states, just how long takes to count down to some terminal value.

\$\endgroup\$
  • \$\begingroup\$ For 5bits. d <= { d[3:0], d[4] ^ d[3] }; is wrong, it should be 2 and 4 (xapp052) \$\endgroup\$ – Alexis_FR_JP Nov 17 '19 at 10:05
  • \$\begingroup\$ @Alexis_FR_JP, thanks, fixed. \$\endgroup\$ – The Photon Nov 17 '19 at 17:05
3
\$\begingroup\$

The standard way of generating pseudo-random sequences with digital logic is using a Linear Feedback Shift Register.

See e.g. Wikipedia "Linear feedback shift register"

If you need a real random sequence you need some non-deterministic element, e.g. a noise source. I.e. you can't do it with standard logic alone.

\$\endgroup\$
2
\$\begingroup\$

If a Linear Feedback Shift Register's pseudo-random output is acceptable for your application, then I recommend using the Xilinx Core Generator. It comes free with Xilinx ISE (even the WebPack!)

http://www.xilinx.com/tools/coregen.htm

CoreGen has a bunch of templates for creating digital logic blocks. One of them is the LFSR. CoreGen will allow you to specify various parameters (type, size, reset, enable, etc). It also allows you to generate VHDL or Verilog output.

Note that LFSR can be implemented very efficiently in a Xilinx FPGA using an SRL16 implementation, which the CoreGen is capable of doing.

\$\endgroup\$
  • \$\begingroup\$ I cant find LFSR in Core Generator. Can you point me to it? Note that I am using Spartan 3E Starter Kit \$\endgroup\$ – Neel Mehta Apr 24 '12 at 9:55
2
\$\begingroup\$

If you can settle for pseudo-random numbers (which is, they change all the time but the sequence is repeatable from a given starting point), you can go for a shift register-based pseudo random generator (link on the image):

enter image description here

See also this alternative page

You can extend it to the number of bits that you require at the output, but make sure that the XOR "scrambles" the bits so as it doesn't fall into a loop with a limited number of different output sequences.

Here there is a tool to generate CRC (Cyclic Redundancy Code?) in VHDL and Verilog, and it's also discussed here

\$\endgroup\$
  • \$\begingroup\$ "Probably this solution is more easily implemented in VHDL", how come? \$\endgroup\$ – avakar Apr 23 '12 at 9:46
  • \$\begingroup\$ @avakar well I don't know Verilog very well, but I think I understood that Verilog was more c-like, while VHDL is closer to the hardware implementation... \$\endgroup\$ – clabacchio Apr 23 '12 at 9:55
  • \$\begingroup\$ @clabacchio: Verilog is only C-like in syntax - it's stilla hardware description language. Building a shift register with XOR feedback is perfectly doable (not being a verilogger, I'll let someone else post the right syntax :) \$\endgroup\$ – Martin Thompson Apr 23 '12 at 11:21
1
\$\begingroup\$

There's a really good presentation on random number generation here. It goes through several implementations and describes how they work. Essentially it comes down to a pair of racing ring counters. There is also a paper describing and comparing a number of random number generation techniques for FPGAs here, although it is more academic.

\$\endgroup\$
  • \$\begingroup\$ You meant ring oscillators, right? RFC 4086 "Randomness Requirements for Security" also describes more-or-less the same system. \$\endgroup\$ – davidcary Sep 8 '12 at 14:18
0
\$\begingroup\$

Yes, you want the $random call. For example the Verilog FAQ says:

Q: Is there a function in verilog to generate random numbers?

Yes. It is $random(seed). The seed is optional. The random number sequence for a given seed (or no seed) will always be the same. Where b > 0, the expression ($random % b) gives a number in the following range: [(-b+1):(b-1)].

\$\endgroup\$
  • 2
    \$\begingroup\$ @NeelMehta, FYI, BrianCarlton's answer answers the question you asked, but will not be synthesizable. \$\endgroup\$ – The Photon Apr 23 '12 at 19:09
  • 1
    \$\begingroup\$ @ThePhoton: not synthesizable, does that mean you can't create FPGA code from it? What's the use then? \$\endgroup\$ – Federico Russo Apr 24 '12 at 8:15
  • \$\begingroup\$ I agree with Federico. Why have something which is non-synthesizable? \$\endgroup\$ – Neel Mehta Apr 24 '12 at 9:56
  • 2
    \$\begingroup\$ @FedericoRusso, Yes, "not synthesizable" means the synthesis tool will not be able to generate corresponding logic in the physical FPGA. You could, however, for example, use this function in a testbench to generate a stimulus when you simulate a design you are working on. \$\endgroup\$ – The Photon Apr 24 '12 at 15:52
  • 2
    \$\begingroup\$ @NeelMehta, the basic reason is that HDLs (Verilog and VHDL) were not invented for the purpose of designing logic, but for modeling logic that already exists. Why we use it for designing logic instead of the original purpose is a whole new question. But functions like $random let you model logic at a higher level, in terms of behavior, instead of the detailed level that is needed for synthesis. \$\endgroup\$ – The Photon Apr 24 '12 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.