How to detect first "1"

[eexuke]

Hi all,
If I have a sequence of binary bits such as "00001010111",how can I detect the position of the first "1" in the fifth position from left during hardware implementation?
One way is continuous "OR" the adjacent bits until a "1" is got. e.g forth"0" | fifth "1" = 1,so I know the first one is at position five. However,I don't think that is an efficient way. Can anybody give me some advice on how to deal with such situation?

Many thanks in advance!

 

[eda_wiz]

How about a priority encoder circuit??

 

[eexuke]

How about a priority encoder circuit??

Can you give me a more detail description about the said "priority encoder circuit"?

Thanks!

 

[eda_wiz]

I think priority encoder is a very basic digital circuit, that you can find in ANY digital logic design text book.

The RTL code of the circuit will look like.

If(vector[0]==1'b1) out = 0;
else if(vector[1]==1'b1) out = 1;
else if(vector[2]==1'b1) out = 2;
else if(vector[3]==1'b1) out = 3;
...
...
...
...

else out = 0;

///Full sample Code below

7 module pri_encoder_using_if (
8 binary_out , // 4 bit binary output
9 encoder_in , // 16-bit input
10 enable // Enable for the encoder
11 );
12 output [3:0] binary_out ;
13 input enable ;
14 input [15:0] encoder_in ;
15
16 reg [3:0] binary_out ;
17
18 always @ (enable or encoder_in)
19 begin
20 binary_out = 0;
21 if (enable) begin
22 if (encoder_in == 16'h0002) begin
23 binary_out = 1;
24 end else if (encoder_in == 16'h0004) begin
25 binary_out = 2;
26 end else if (encoder_in == 16'h0008) begin
27 binary_out = 3;
28 end else if (encoder_in == 16'h0010) begin
29 binary_out = 4;
30 end else if (encoder_in == 16'h0020) begin
31 binary_out = 5;
32 end else if (encoder_in == 16'h0040) begin
33 binary_out = 6;
34 end else if (encoder_in == 16'h0080) begin
35 binary_out = 7;
36 end else if (encoder_in == 16'h0100) begin
37 binary_out = 8;
38 end else if (encoder_in == 16'h0200) begin
39 binary_out = 9;
40 end else if (encoder_in == 16'h0400) begin
41 binary_out = 10;
42 end else if (encoder_in == 16'h0800) begin
43 binary_out = 11;
44 end else if (encoder_in == 16'h1000) begin
45 binary_out = 12;
46 end else if (encoder_in == 16'h2000) begin
47 binary_out = 13;
48 end else if (encoder_in == 16'h4000) begin
49 binary_out = 14;
50 end else if (encoder_in == 16'h8000) begin
51 binary_out = 15;
52 end
53 end
54 end
55
56 endmodule


also look here..
**broken link removed**

 

[omid219]

priority encoder is used when you have the sequence stored in a register, but what yo do when it is comming serially and you don't know the length?
I think a counter should count the comming bits and check for the first 1.

 

[Raptor]

You can use a Mealy or Moore state machine. It will be simpler. State in one state until you get a one and if you want to get the bit position at which 1 occured you can use a counter. As soon as you get one you can jump to processing stage. You will find lot of information on state maching on web I suggest you go through them.

 

[eexuke]

Hi whizkid,
Thank you for your information. During your statement,the decoding flow is sequential from highest bit to lowest bit. The delay will depend on the input data length. However,I am wondering a more power efficient or high performance way to do this. Also,I don't prefer to use multi-cycle on it. Does anybody have more idea on this?

 

[beowulf]

If you want information on the "position" of the first 1, a counter is the only way according to me. I would love to hear of any other method.

This gets complicated when you do not know the length of the incoming data, i.e. you have to determine 'what is the size of the counter' else it will overflow and you will get a incorrect position.

Also, you will need to make sure that a glitch or some noise is not detected as a 1, either use a two FFs (one +ve edge and one -ve) or sample the incoming data faster than the normal clock, like its done in UARTs.

HTH,
Beowulf

 

[eda_wiz]

The delay will depend on the input data length.

I guess since u want to find the position , delay will be dependant on the input length..

Another option is to use a mux..
check out //synopsys parallel_case details.
but i guess it will take more area, though the timing will be better

 

[tony_taoyh]

I think you can use this method:

Please note now I am using VHDL,
so there may be syntax error in my verilog codes.

module tt (rst, clk, in, out);
input in;
input rst;
input in;
output out; // the indicate flag

reg out;

reg [4:0] in_buf;

always @(posedge clk and negedge rst)
begin
if (rst == 0)
in_buf <= 5'b00000;
else
in_buf <= {in_buf [3:0], in};
end

always @(posedge clk and negedge rst)
begin
if (rst == 0)
out <= 0;
else
begin
if (in_buf == "00001")
out <= 1'b1;
else
out <= 1'b0;
end

endmodule

It think it is no need to use state machine for this, you need consider much more, and at the same time, use same area. Here, I just use 5 DFFs, and one small combination logical, like 3 AND.

Hope help you.

Best Regards,
Tony Tao

 

[carrot]

Hi

use of Melay Machine is best for sequence detection.

 

[omid219]

tony_taoyh,

What is the usage of in_buf shfit register?
What about the position of the first '1' in stream?

 

[ashishjindal76]

hi folks

if speed is not the concern then what i think is that u convert this data into serial form and one by one compare the bit with 1 and activate the counter every time u convert the data into serial form and at the time of match while comparison check the counter position. if u want the simple verilog programme just mail me out i shall try that for u

ashish