+ Post New Thread
Results 1 to 15 of 15

30th September 2019, 14:18 #1
 Join Date
 Feb 2016
 Posts
 714
 Helped
 1 / 1
 Points
 3,695
 Level
 14
Determine whether a binary number is of power of two in verilog code
I am trying to determine whether a binary number is of power of two (in other words, is it of onehot encoding).
I found a method to do so, but it is for integer.
Could anyone help to transform the method for usage with binary number in verilog ?

Advertisement

30th September 2019, 15:38 #2
 Join Date
 Mar 2005
 Location
 California, USA
 Posts
 4,759
 Helped
 1055 / 1055
 Points
 24,850
 Level
 38
Re: Determine whether a binary number is of power of two in verilog code
Without thinking too hard early on a Monday morning, I think this could be done with a bunch of cascaded XORs. Output would be logic 1 if only one bit is set. Exception: is zero a power of 2?

30th September 2019, 15:45 #3
 Join Date
 Jun 2010
 Posts
 6,922
 Helped
 2036 / 2036
 Points
 38,244
 Level
 47
Re: Determine whether a binary number is of power of two in verilog code
@barry  I was going to say that , but it doesnt work.
1011:
1 XOR 0 = 1 XOR 1 = 0 XOR 1 = 1
So you dont get a power of 2.

30th September 2019, 16:30 #4
 Join Date
 Feb 2016
 Posts
 714
 Helped
 1 / 1
 Points
 3,695
 Level
 14
Re: Determine whether a binary number is of power of two in verilog code
See the verilator linting output with is_power_of_two.v
Code:verilator Wall lintonly is_power_of_two.v %WarningWIDTH: is_power_of_two.v:6: Logical Operator LOGAND expects 1 bit on the LHS, but LHS's VARREF 'v' generates 8 bits. : ... In instance is_power_of_two always @(*) f = v && !(v & (v  1)); ^~ ... Use "/* verilator lint_off WIDTH */" and lint_on around source to disable this message. %WarningWIDTH: is_power_of_two.v:6: Logical Operator LOGNOT expects 1 bit on the LHS, but LHS's AND generates 32 or 8 bits. : ... In instance is_power_of_two always @(*) f = v && !(v & (v  1)); ^ %WarningUNUSED: is_power_of_two.v:4: Signal is not used: 'f' : ... In instance is_power_of_two reg f; ^ %Error: Exiting due to 3 warning(s) %Error: Command Failed /usr/bin/verilator_bin Wall lintonly is_power_of_two.v
Code Verilog  [expand] 1 2 3 4 5 6 7 8
module is_power_of_two(); reg [7:0] v = 8'b11110000; reg f; always @(*) f = v && !(v & (v  1)); endmodule

Advertisement

30th September 2019, 16:51 #5

30th September 2019, 17:26 #6
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,430
 Helped
 1742 / 1742
 Points
 32,130
 Level
 43
Re: Determine whether a binary number is of power of two in verilog code
Cascaded XOR is a parity generator.
In Verilog the code looks exactly the same as the C example.
Code Verilog  [expand] 1 2
logic [3:0] v; assign f = v && !(v & (v 1));
Though I prefer using a reduction NOR (~) instead of the ! as the logic is trying to detect the all 0 condition, which is easily done by a reduction NOR operation instead of a logical NOT.
The whole point of the v & (v 1) is to find any values that result in a bitwise ANDing of the values resulting in all zeros, which incidentally only happens on powers of 2 or when the value is 0.
Code Verilog  [expand] 1 2 3 4 5 6 7 8 9 10 11 12 13 14
module not_test; logic [3:0] v; logic [3:0] vm1; initial begin for (int i=0; i<16; i++) begin v = i; $display ("v=%4b, v1=%4b, v&(v1)=%4b, !(v&(v1))=%4b, v&&!(v&(v1))=%4b, v&&~(v&(v1))=%4b", v, v4'b1, v&(v4'b1), !(v&(v4'b1)), v&&!(v&(v4'b1)), v&&~(v&(v4'b1))); end $stop; end endmodule
test run results in the following:
Code:v=0000, v1=1111, v&(v1)=0000, !(v&(v1))=0001, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=0001, v1=0000, v&(v1)=0000, !(v&(v1))=0001, v&&!(v&(v1))=0001, v&&~(v&(v1))=0001 v=0010, v1=0001, v&(v1)=0000, !(v&(v1))=0001, v&&!(v&(v1))=0001, v&&~(v&(v1))=0001 v=0011, v1=0010, v&(v1)=0010, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=0100, v1=0011, v&(v1)=0000, !(v&(v1))=0001, v&&!(v&(v1))=0001, v&&~(v&(v1))=0001 v=0101, v1=0100, v&(v1)=0100, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=0110, v1=0101, v&(v1)=0100, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=0111, v1=0110, v&(v1)=0110, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=1000, v1=0111, v&(v1)=0000, !(v&(v1))=0001, v&&!(v&(v1))=0001, v&&~(v&(v1))=0001 v=1001, v1=1000, v&(v1)=1000, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=1010, v1=1001, v&(v1)=1000, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=1011, v1=1010, v&(v1)=1010, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=1100, v1=1011, v&(v1)=1000, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=1101, v1=1100, v&(v1)=1100, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=1110, v1=1101, v&(v1)=1100, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000 v=1111, v1=1110, v&(v1)=1110, !(v&(v1))=0000, v&&!(v&(v1))=0000, v&&~(v&(v1))=0000

Advertisement

1st October 2019, 05:21 #7
 Join Date
 Feb 2016
 Posts
 714
 Helped
 1 / 1
 Points
 3,695
 Level
 14
Re: Determine whether a binary number is of power of two in verilog code
The solution is to use
Code:always @(*) f = (v != 0) && ((v & (v  1)) == 0);
Someone suggested me to use power_of_two = ^v which is so much simpler.
Any comment ?

1st October 2019, 11:42 #8
 Join Date
 Jan 2008
 Location
 Bochum, Germany
 Posts
 46,168
 Helped
 14041 / 14041
 Points
 264,236
 Level
 100
Re: Determine whether a binary number is of power of two in verilog code
The solution is to use
Code:always @(*) f = (v != 0) && ((v & (v  1)) == 0);
Someone suggested me to use power_of_two = ^v which is so much simpler.

1st October 2019, 15:47 #9
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,430
 Helped
 1742 / 1742
 Points
 32,130
 Level
 43
Re: Determine whether a binary number is of power of two in verilog code
No it's not the preferred solution, it is a verbose solution. Maybe you should switch to VHDL.
Since you ignored my post, I'll just assume you have me on your ignore list....
Yeah my comment is, don't listen to them they don't know much. ^v is reduction XOR which is how you compute PARITY it does not compute powers of 2. I already mentioned that in my previous post #6.

3rd October 2019, 08:37 #10
 Join Date
 Feb 2016
 Posts
 714
 Helped
 1 / 1
 Points
 3,695
 Level
 14
Re: Determine whether a binary number is of power of two in verilog code
@adsee
The following will also work, with less LUTs and higher fmax compared to the solution above.
Code Verilog  [expand] 1
always @(*) is_power_of_two = ((in[7] + in[6] + in[5] + in[4] + in[3] + in[2] + in[1] + in[0]) == 1);
Please correct me if wrong.

3rd October 2019, 13:21 #11
 Join Date
 Jun 2010
 Posts
 6,922
 Helped
 2036 / 2036
 Points
 38,244
 Level
 47
Re: Determine whether a binary number is of power of two in verilog code
Yes, but it assumes but it has the following limitations:
1. It doesnt allow for In = 0 (2^0)
2. It is always 8 bits.
The previous case covered the 0 case and allowed for any length of bits

3rd October 2019, 14:43 #12
 Join Date
 Jan 2008
 Location
 Bochum, Germany
 Posts
 46,168
 Helped
 14041 / 14041
 Points
 264,236
 Level
 100
Re: Determine whether a binary number is of power of two in verilog code
The performance difference is nevertheless remarkable, at least with Quartus tool. The capability of a synthesis tool to find optimal solutions can't be predicted, you need to try.
I can write a parameterizable solution in VHDL with the same performance as the post #10 code, but I didn't succeed in Verilog.
Code VHDL  [expand] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
library ieee; use ieee.std_logic_1164.all; use ieee.numeric_std.all; entity test is generic ( DATA_WIDTH : natural := 8 ); port ( inp : in std_logic_vector(DATA_WIDTH1 downto 0); result : out std_logic ); end entity; architecture rtl of test is begin process (inp) variable n: integer; begin n := 0; for i in 0 to data_width1 loop n := n + to_integer(unsigned(inp(i downto i))); end loop; result <= '0'; if n=1 then result <= '1'; end if; end process; end rtl;
The RTL schematic shrinks down to gate level
1 members found this post helpful.

Advertisement

3rd October 2019, 15:53 #13
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,430
 Helped
 1742 / 1742
 Points
 32,130
 Level
 43
Re: Determine whether a binary number is of power of two in verilog code
Interesting that you are pointing this out to me as if I don't already know this solution. I have been discussing the question posted in #1 and the desire to translate it to Verilog. I was also commenting about how you cannot use a reduction XOR operation to check for power of two.
If you wanted to discuss optional ways of doing this I would have suggested using a simple add up all the bits, which is typically the easiest way to determine if only a single bit is set. The adding bits method does not require the bit width wide add operation as required by the post #1 algorithm (which is probably where most of the resulting performance hit issue comes from). Though to correctly deal with finding a power of two, you need to modify the above logic by not adding bit0 and ANDing the entire addition result with the inverse of bit0 (i.e. if bit0 is 1 then the input is odd and the result should be 0).
e.g.
Code Verilog  [expand] 1
assign is_power_of_two = ((in[7] + in[6] + in[5] + in[4] + in[3] + in[2] + in[1]) == 1) & ~in[0];

3rd October 2019, 17:07 #14
 Join Date
 Feb 2016
 Posts
 714
 Helped
 1 / 1
 Points
 3,695
 Level
 14
Re: Determine whether a binary number is of power of two in verilog code
2^{0} = 1
So, in[0] could have the value of 1
Note: I am trying to detect onehot as mentioned in post #1

3rd October 2019, 19:30 #15
 Join Date
 Sep 2013
 Location
 USA
 Posts
 7,430
 Helped
 1742 / 1742
 Points
 32,130
 Level
 43
Re: Determine whether a binary number is of power of two in verilog code
+ Post New Thread
Please login