fpga - Random bit sequence using Verilog

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

Answer

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.