Electronic – How to get the longest one’s sequence in verilog

verilog

I have some problems with a question that ask me to get the number of one's in the longest one's sequence in a 16 bit input using a 5 bit number in verilog. For example
(0111011111010101 = 00101 the answer is five duo to the sequence in the middle)
(1111111111111111 = 100000) I would like to know how to do it using both combinational and sequential circuits.

Best Answer

You can solve this question with a shift and kill method.

Let's say you have N input bits and N is 16.

Step 1)
Load a N bit wide shift register with your input in parallel. Add a zero bit at LSB.

0111 1010 0111 0011|0

reset your result counter to 0

Step 2)
Perform a 'shift' operation that expands existing zeros to the left neighbor bit.

0111 1010 0111 0011|0
0111 0000 0110 0010|0

Increment the result counter.

Step 3)
Check if the register is all zero.
false -> repeat step 2 and 3
true -> result counter holds your longest one sequence.

Example:

0111 1010 0111 0011|0 cnt=0 / input
0111 0000 0110 0010|0 cnt=1
0110 0000 0100 0000|0 cnt=2
0100 0000 0000 0000|0 cnt=3
0000 0000 0000 0000|0 cnt=4 / done

Minimum execution time is 1 load and 1 compare -> can be solved in 1 cycle.

Maximum execution time is 1 load and N shifts -> 17 cycles in the example.

Real execution time is 1 load and n shifts if n is the length of the longest one sequence -> 5 cycles in the example.

How to calculate the bits while shifting?
Let's name the shift register a.

a(0) := 0
for i in 1..N-1
  a(i) := a(i) and a(i-1)
next

How many hardware is used?
- N registers for a
- N LUTs for load and shift before each register
- a ld(N+1) bit counter
- a N bit zero comparator

On Xilinx hardware: Xilinx FPGAs have 6-input LUTs which can be used as 2 5-input LUTs moreover there are 2 FF per LUT. Synthesis can map a 16 bit shift register into only 2 slices and the comperator into a third slice.

As requested - a 5 bit counter

reg     [4:0]   counter;

always @(posedge Clock)
begin
  if(Reset)
     counter <=      5'b0;
  else if(counter_en)
     counter <=      counter + 1;
end

Related Solutions

Electronic – Does it take long to implement RSA in hardware

RSA will not be easy to implement and may require a very large FPGA. RSA is far better suited to running on a general purpose CPU than an FPGA. I have seen some implementations of RSA on an FPGA that use a softcore to run the algorithm and the FPGA to accelerate some of the math, but the complete algorithm is not implemented in Verilog. And generally when a file is "RSA encrypted," it usually isn't - the file is generally AES encrypted and the AES key is then RSA encrypted since AES is much faster than RSA. If you want to implement an encryption algorithm on an FPGA, especially for a streaming signal, AES would be a much better idea than RSA. You can probably implement AES in a week, it's a pretty simple algorithm.

Electronic – Verilog – Synthesize High Speed Leading Zero Count

Leading zero encoders can be made with a nice balanced tree structure.

First, encode bits 2 by 2 :

00 => 10 : 2 leading zeros
01 => 01 : 1 leading zero
10 => 00 : 0 leading zero
11 => 00 : 0 leading zero

Then, assemble as pairs.

If both sides start with 1xxx, the result is 10...0
If the left side start with 0 the result is 0[left]
If the left side starts with 1, the result is 01[right(msb-1:0)]

You only need multiplexers.

For example the 8 bits value : 00000111

2 by 2 : 00 00 01 11
encoded : 10 10 01 00
assemble : 100 001
assemble : 0101 = 5 leading zeros.

In VHDL (I have no Verilog code at hand), you get that :

FUNCTION enc(CONSTANT a : unsigned(1 DOWNTO 0)) RETURN unsigned IS
BEGIN
  CASE a IS
    WHEN "00" => RETURN "10";
    WHEN "01" => RETURN "01";
    WHEN "10" => RETURN "00";
    WHEN OTHERS => RETURN "00";
  END CASE;
END FUNCTION enc;

FUNCTION clzi(
  CONSTANT n : IN natural;
  CONSTANT i : IN unsigned) RETURN unsigned IS
  VARIABLE v : unsigned(i'length-1 DOWNTO 0):=i;  
BEGIN
  IF v(n-1+n)='0' THEN
    RETURN (v(n-1+n) AND v(n-1)) & '0' & v(2*n-2 DOWNTO n);
  ELSE
    RETURN (v(n-1+n) AND v(n-1)) & NOT v(n-1) & v(n-2 DOWNTO 0);
  END IF;
END FUNCTION clzi;

FUNCTION clz64 (CONSTANT v : unsigned(0 TO 63)) RETURN unsigned IS
  VARIABLE e : unsigned(0 TO 63);     -- 64
  VARIABLE a : unsigned(0 TO 16*3-1); -- 48
  VARIABLE b : unsigned(0 TO 8*4-1);  -- 32
  VARIABLE c : unsigned(0 TO 4*5-1);  -- 20
  VARIABLE d : unsigned(0 TO 2*6-1);  -- 12
BEGIN
  FOR i IN 0 TO 31 LOOP e(i*2 TO i*2+1):=enc(v(i*2 TO i*2+1));  END LOOP;
  FOR i IN 0 TO 15 LOOP a(i*3 TO i*3+2):=clzi(2,e(i*4 TO i*4+3)); END   LOOP;
  FOR i IN 0 TO 7  LOOP b(i*4 TO i*4+3):=clzi(3,a(i*6 TO i*6+5)); END   LOOP;
 FOR i IN 0 TO 3  LOOP c(i*5 TO i*5+4):=clzi(4,b(i*8 TO i*8+7)); END LOOP;
 FOR i IN 0 TO 1  LOOP d(i*6 TO i*6+5):=clzi(5,c(i*10 TO i*10+9)); END LOOP;
 RETURN clzi(6,d(0 TO 11));
END FUNCTION clz64;

enc() does the encoding clzi() merges two vectors. clz64() is a sample implementation for a 64bits input.

Best Answer

Related Solutions

Electronic – Does it take long to implement RSA in hardware

Electronic – Verilog – Synthesize High Speed Leading Zero Count

Related Topic