Challenge to Verilog programmers
Jonathan Bromley
I have a solution that works, but it's clunky and long,
and I reckon it's fun to try to find a better one...
PROBLEM:
Write functions that convert a regular Verilog 4-state
vector value into a 2-state representation, and vice versa.
DETAILS:
Any Verilog bit can have values 0, 1, x, z. I would
like to represent (encode) those 4-state values as the
four 2-bit vector values 0->00, 1->01, x->10, z->11
(the "aval/bval" representation used in PLI etc).
Furthermore, I'd like to be able to represent any
N-bit Verilog vector as a 2N-bit number, thus:
4'b01xz -> 8'b00_01_10_11
// 0 1 X Z
(Yes, I know this is not quite the same way the
PLI aval/bval representation works).
RULES OF THE GAME:
Write the following two functions in the most
compact/elegant/cunning/fast possible way:
parameter N = ...; /// number of 4-state bits
function [2*N-1:0] to_2state(input [N-1:0] vec_4state); ...
function [N-1:0] to_4state(input [2*N-1:0] vec_2state); ...
There is no need to error-check the 2-state input "vec_2state"
(which, of course, should contain no Xs or Zs) but such
checking would be a nice bonus.
No PLI/DPI/DirectC permitted. No SystemVerilog permitted.
Otherwise, it's up to you. No prize except the kudos :-)
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan...@MYCOMPANY.com
http://www.MYCOMPANY.com
The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
Jonathan Bromley
<jonathan...@MYCOMPANY.com> wrote:
>Here's a challenge to your Verilog coding ingenuity.
Sheesh, I thought you would all be trying to show off :-)
To add encouragement, here's a code skeleton for you to
complete, and a test fixture (it's what I used to check
my own implementation).
/////////////////////////////////////////
// Verilog Coding Challenge, 25 May 2007
// offered by Jonathan Bromley
/////////////////////////////////////////
//
// PROBLEM:
// Write functions that convert a regular Verilog 4-state
// vector value into a 2-state representation, and vice versa.
//
// DETAILS:
// Any Verilog bit can have values 0, 1, x, z. I would
// like to represent (encode) those 4-state values as the
// four 2-bit vector values 0->00, 1->01, x->10, z->11
// (the "aval/bval" representation used in PLI etc).
// Furthermore, I'd like to be able to represent any
// N-bit Verilog vector as a 2N-bit number, thus:
// 4'b01xz -> 8'b00_01_10_11
// // 0 1 X Z
// (Yes, I know this is not quite the same way the
// PLI aval/bval representation works).
//
// RULES OF THE GAME:
// Write the following two functions in the most
// compact/elegant/cunning/fast possible way:
// parameter N = ...; /// number of 4-state bits
// function [2*N-1:0] to_2state(input [N-1:0] vec_4state); ...
// function [N-1:0] to_4state(input [2*N-1:0] vec_2state); ...
// There is no need to error-check the 2-state input "vec_2state"
// (which, of course, should contain no Xs or Zs) but such
// checking would be a nice bonus.
// No PLI/DPI/DirectC permitted. No SystemVerilog permitted.
// Otherwise, it's up to you. No prize except the kudos :-)
//
/////////////////////////////////////////
//
// INSTRUCTIONS:
//
// Write your functions inside the body of module ab_xz01
// (template below). Then compile and simulate the whole
// of this file. It tests the functions with ten different
// random values, all 11 bits wide, and checks that the
// results are right. Simulate in console or text-only mode.
// It should generate output like this...
// x x x z z 0 x 0 z 1 x
// 10_10_10_11_11_00_10_00_11_01_10
// x x x z z 0 x 0 z 1 x
// The first line is the randomly generated test value.
// The second line is the result of converting that to
// 2-state coding using to_2state(). The third line is
// the result of converting the 2-state value back to
// 4-state using to_4state().
/////////////////////////////////////////
module ab_xz01 #(parameter N = 32); // number of bits
function [N-1:0] to_4state(input [2*N-1:0] vec_2state);
...WRITE THIS FUNCTION
endfunction
function [2*N-1:0] to_2state(input [N-1:0] vec_4state);
...WRITE THIS FUNCTION
endfunction
endmodule
// Test code, no need to touch this unless you want to
// tweak its parameters
module test_xz01;
parameter N = 11; // number of bits for test
parameter nTests = 10; // number of random tests
ab_xz01 #N funcs(); // instantiate "functions" module
reg [0:3] LUT = 4'b01xz;
integer seed = 42;
function [N-1:0] rng(input xz);
integer i;
integer h;
begin
h = xz? 3: 1;
for (i=0; i<N; i=i+1)
rng[i] = LUT[$dist_uniform(seed, 0, 3)];
end
endfunction
function test(input [N-1:0] v);
reg [N-1:0] v2;
reg [2*N-1:0] ab;
integer i;
begin
ab = funcs.to_2state(v);
v2 = funcs.to_4state(ab);
for (i=N-1; i>=0; i=i-1) $write(" %b ", v[i]);
$display;
$write("%b", ab[2*(N-1)+:2]);
for (i=N-2; i>=0; i=i-1) $write("_%b", ab[2*i+:2]);
$display;
for (i=N-1; i>=0; i=i-1) $write(" %b ", v2[i]);
test = (v2 === v);
if (test)
$display;
else
$display(" <--- WRONG");
$display;
end
endfunction
initial begin : Test
integer good = 0;
repeat (nTests) good = good + test(rng(1));
$display("%0d/%0d good\n", good, nTests);
end
endmodule
Alex
wrote:
>
> The contents of this message may contain personal views which
> are not the views of Doulos Ltd., unless specifically stated.
function [2*NB-1:0] to_2state;
input [NB-1:0] val;
begin
while (to_2state[0] === 1'bx) begin
to_2state = {(val[0]===1'bx)?2'b01:((val[0]===1'bz)?2'b10:
{2{val[0]}}),to_2state[2*NB-1:2]};
val = val >> 1;
end
end
endfunction
Another function looks similar to this one, but in opposite direction.
-Alex
gtw...@pacbell.net
wrote:
> Here's a challenge to your Verilog coding ingenuity.
> I have a solution that works, but it's clunky and long,
> and I reckon it's fun to try to find a better one...
>
> PROBLEM:
>
> Write functions that convert a regular Verilog 4-state
> vector value into a 2-state representation, and vice versa.
>
Jonathan,
This solution doesn't follow your rules, but I'll post anyway.
The qualification for sticking it in a verilog function makes
it difficult. If you can live with a module instead, you can
take advantage of an array of instances. Do the lower
level modules which just do one bit:
module two_state_to_four_state
(
input wire [ 1 : 0 ] a
output wire y
);
wire [ 3 : 0 ] all_states = { 1'bz, 1'bx, 1'b1, 1'b0 };
assign y = all_states[ a ];
endmodule
module four_state_to_two_state
(
input wire a,
output wire [ 1 : 0 ] y
);
assign y[ 0 ] = ( a === 1'b1 ) | ( a === 1'bx );
assign y[ 1 ] = ( a === 1'bx ) | ( a === 1'bz );
endmodule
Then, an upper module which instanciates the lower levels,
one per bit:
module n_two_state_to_four_state
#( parameter N = 8 )
(
input wire [ 2 * N - 1 : 0 ] a,
output wire [ N - 1 : 0 ] y
)
two_state_to_four_state two_state_to_four_state[ N - 1 : 0 ]
( .a( a ), .y( y ) );
endmodule
module n_four_state_to_two_state
#( parameter N = 8 )
(
input wire [ N - 1 : 0 ] a,
output wire [ 2 * N - 1 : 0 ] y
)
four_state_to_two_state four_state_to_two_state[ N - 1 : 0 ]
( .a( a ), .y( y ) );
endmodule
Untried, untested, and doesn't follow the rules...
--Mark
Alex
One more line to make it working properly ;)
function [2*NB-1:0] to_2state;
input [NB-1:0] val;
begin
to_2state = {2*NB{1'bx}};
while (to_2state[0] === 1'bx) begin
to_2state = {(val[0]===1'bx) ? 2'b01 : ((val[0]===1'bz)?2'b10 :
Petter Gustad
> parameter N = ...; /// number of 4-state bits
> function [2*N-1:0] to_2state(input [N-1:0] vec_4state); ...
> function [N-1:0] to_4state(input [2*N-1:0] vec_2state); ...
Wouldn't this do (not tested):
function [1:0] single_to_2state (input sbit);
case (1'b1)
(sbit === 1'b0): single_to_2state = 2'b00;
(sbit === 1'b1): single_to_2state = 2'b01;
(sbit === 1'bx): single_to_2state = 2'b10;
(sbit === 1'bz): single_to_2state = 2'b11;
endcase
endfunction
function [2*N-1:0] to_2state (input [N-1:0] vec_4state);
integer i;
for (i = (2*N)-1; i>0; i=i-2) begin
{to_2state[i],to_2state[i-1]} = single_to_2state(vec_4state[i/2]);
end
endfunction
Petter
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
sh...@cadence.com
Jonathan Bromley wrote:
>
> RULES OF THE GAME:
>
> Write the following two functions in the most
> compact/elegant/cunning/fast possible way:
>
> parameter N = ...; /// number of 4-state bits
> function [2*N-1:0] to_2state(input [N-1:0] vec_4state); ...
> function [N-1:0] to_4state(input [2*N-1:0] vec_2state); ...
Seems fairly straightforward:
module ab_xz01 #(parameter N = 32); // number of bits
reg [0:3] LUT = 4'b01xz;
function [N-1:0] to_4state(input [2*N-1:0] vec_2state);
integer i;
for (i = 0; i < N; i = i + 1)
to_4state[i] = LUT[vec_2state[2*i +: 2]];
endfunction
function [2*N-1:0] to_2state(input [N-1:0] vec_4state);
integer i;
for (i = 0; i < N; i = i + 1)
case (vec_4state[i])
1'b0: to_2state[2*i +: 2] = 2'b00;
1'b1: to_2state[2*i +: 2] = 2'b01;
1'bx: to_2state[2*i +: 2] = 2'b10;
1'bz: to_2state[2*i +: 2] = 2'b11;
endcase
endfunction
endmodule
What part made your implementation klunky? The only tricks I see are
the indexed part selects and knowing that case uses the case equality
comparison.
I don't see any approach that doesn't use a loop. If your 2-state
representation had separate aval and bval fields instead of
interleaving them, and there were bitwise versions of the case
equality and/or conditional operators, you c ould do it without loops
and make it more efficient.
Jonathan Bromley
>> Write the following two functions in the most
>> compact/elegant/cunning/fast possible way:
[...]
>Seems fairly straightforward:
Pretty much word-for-word what I did. Nice to know I'm not
getting completely daft in my old age.
>What part made your implementation klunky? The only tricks I see are
>the indexed part selects and knowing that case uses the case equality
>comparison.
>I don't see any approach that doesn't use a loop. If your 2-state
>representation had separate aval and bval fields instead of
>interleaving them, and there were bitwise versions of the case
>equality and/or conditional operators, you c ould do it without loops
>and make it more efficient.
Yes. I was vaguely wondering if there were any way to fake up
such operators, but I couldn't find any. Agreed that the
merged bit-pairs representation forces the use of a loop and
indexed part selects, but again I was wondering if there were
some niftier solution to this fairly common problem. Someone
else offered a cumulative-shift idea, which is quite neat but
would probably be quite a lot slower to execute.
Thanks
Jonathan Bromley
<gtw...@pacbell.net> wrote:
>> Write functions that convert a regular Verilog 4-state
>> vector value into a 2-state representation, and vice versa.
>
>This solution doesn't follow your rules, but I'll post anyway.
>The qualification for sticking it in a verilog function makes
>it difficult. If you can live with a module instead, you can
>take advantage of an array of instances.
You can do something similar by writing functions to
operate on a single bit(pair), and then invoking
those functions in a loop; probably cheaper to
simulate than an array of instances.
I wonder if your
assign y[ 0 ] = ( a === 1'b1 ) | ( a === 1'bx );
assign y[ 1 ] = ( a === 1'bx ) | ( a === 1'bz );
would be faster than the case statement that Steven Sharp
and I both used? Here's my procedural version:
y[1] = (a^a) === 1'bx;
y[0] = y[1]? a===1'bz: a;
Thanks
Jonathan Bromley
>function [2*NB-1:0] to_2state;
>input [NB-1:0] val;
>
>begin
> to_2state = {2*NB{1'bx}};
> while (to_2state[0] === 1'bx) begin
> to_2state = {(val[0]===1'bx) ? 2'b01 : ((val[0]===1'bz)?2'b10 :
> {2{val[0]}}),to_2state[2*NB-1:2]};
> val = val >> 1;
> end
>end
>
>endfunction
I like it! Later I'll compare its speed with my solution...
Thanks
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan...@MYCOMPANY.com
Jonathan Bromley
<newsma...@gustad.com> wrote:
>Wouldn't this do (not tested):
>
> function [1:0] single_to_2state (input sbit);
> case (1'b1)
> (sbit === 1'b0): single_to_2state = 2'b00;
> (sbit === 1'b1): single_to_2state = 2'b01;
> (sbit === 1'bx): single_to_2state = 2'b10;
> (sbit === 1'bz): single_to_2state = 2'b11;
> endcase
> endfunction
'case' does === comparison anyway, so I think the obvious
style is probably better:
case (sbit)
1'b0: ...
1'b1: ...
1'bx: ...
But otherwise, yes, I think that's the answer. I really
wish there were some simple way of turning X values reliably
into 1 (or 0). In SystemVerilog you can do that by casting
a 4-state (reg, logic) vector to 2-state (bit) type.
Petter Gustad
> 'case' does === comparison anyway, so I think the obvious
> style is probably better:
That is true. But at some point in time, quite a few years ago so it's
might not be valid anymore, the above was a little faster (VCS)...
rajba...@gmail.com
// D flip-flop
for (i =0; i <N;i= i+1)
begin
if ({vec_2state[2*i],vec_2state[2*i+1]} == 2'b00)
to_4state[i] = 0;
else if ({vec_2state[2*i],vec_2state[2*i+1]} == 2'b01)
to_4state[i] = 1;
else if ({vec_2state[2*i],vec_2state[2*i+1]} == 2'b10)
to_4state[i] = 1'bx;
else
to_4state[i] = 1'bz;
end
endfunction
if (vec_4state[i] == 1'b0)
{to_2state[2*i],to_2state[(2*i)+1]} = 2'b00;
else if (vec_4state[i] == 1'b1)
{to_2state[2*i],to_2state[(2*i)+1]} = 2'b01;
else if (vec_4state[i] === 1'bz)
{to_2state[2*i],to_2state[(2*i)+1]} = 2'b11;
else
{to_2state[2*i],to_2state[(2*i)+1]} = 2'b10;
end
endfunction
endmodule
This works fine but I dont know if its efficient