1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ A typical FSM kinda problem. You can take one register array holding the no of ones so far. Whenever a 1 comes, increment a counter. If a zero comes, compare counter with register, and if it is larger than reg, overwrite it. This is one of many possible ways. \$\endgroup\$ – Plutonium smuggler May 10 '15 at 1:55
  • \$\begingroup\$ I am a beginner in this design language so I couldn't understand your advice. Would you please wright the code. \$\endgroup\$ – Ramon May 10 '15 at 12:22
  • 1
    \$\begingroup\$ Nope. Cant really do that. Be specific what part you dont understand. \$\endgroup\$ – Plutonium smuggler May 10 '15 at 14:03
  • \$\begingroup\$ Ok first of all i have to use xlinix. second i don't know how to make the module count a series of ones and then stop when a zero comes then start counting again and comparing the second result with the first one \$\endgroup\$ – Ramon May 10 '15 at 14:09
  • 1
    \$\begingroup\$ Looks like you are just getting started using verilog. I would say you get some good book like this -> amazon.com/FPGA-Prototyping-Verilog-Examples-Spartan-3/dp/… .....and spend some time learning synthesis using verilog. \$\endgroup\$ – Plutonium smuggler May 10 '15 at 14:14
4
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Didn't understand /: \$\endgroup\$ – Ramon May 12 '15 at 22:50
  • \$\begingroup\$ Can you be more precise, please. I'll try to explain these parts more in detail. \$\endgroup\$ – Paebbels May 12 '15 at 23:20
  • \$\begingroup\$ can u just build a 5 bits counter in verilog please \$\endgroup\$ – Ramon May 14 '15 at 14:00
  • \$\begingroup\$ "for i in 1..N-1" ... That's not the syntax I'm familiar with for a Verilog for statement. Is this VHDL? (I'm not too sure about the "..") \$\endgroup\$ – Tut May 14 '15 at 15:31
  • \$\begingroup\$ That's pseudo code. \$\endgroup\$ – Paebbels May 14 '15 at 15:51

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.