# Bit compression in Verilog

I am trying to write a Verilog code for a multiplier based on the abacus principle. I want to compress an array of 8X15 bits to the lowest rows. For e.g. for an array of

    p0 = 0000000000000000
p1 = 1111111111111111
p2 = 0000000000000000
p3 = 1111111111111111
p4 = 0000000000000000
p5 = 1111111111111111
p6 = 0000000000000000
p7 = 1111111111111111


I want my output to be:

    pp[0] = 000000000000000
pp[1] = 000000000000000
pp[2] = 000000000000000
pp[3] = 000000000000000
pp[4] = 111111111111111
pp[5] = 111111111111111
pp[6] = 111111111111111
pp[7] = 111111111111111


I have written the following code to accomplish this:

    always @ (p0 or p1 or p2 or p3 or p4 or p5 or p6 or p7)
begin
pp[1] = p0;
pp[2] = p1;
pp[3] = p2;
pp[4] = p3;
pp[5] = p4;
pp[6] = p5;
pp[7] = p6;
pp[8] = p7;

for (i=1; i<=15; i=i+1)
begin
for (j=8; j>=1; j=j-1)
begin
for (k=j-1; k>=1; k=k-1)
begin
if ((!pp[j][i]) && (pp[k][i]))
begin
pp[j][i] <= pp[k][i];
pp[k][i] <= pp[j][i];
end
end
end
end
end


but the output that I am getting is this:

    pp[0] = 000000000000000
pp[1] = 000000000000000
pp[2] = 111111111111111
pp[3] = 000000000000000
pp[4] = 111111111111111
pp[5] = 000000000000000
pp[6] = 111111111111111
pp[7] = 111111111111111


Can someone please tell where the fault is?

You can get this to work if you replace the non-blocking assignments with blocking assignments. It is still not readily synthesizable, but it would be OK as a testbench. Example below.

Non-blocking assignments which use <= don't take effect immediately, but rather are delayed until a later point in time, which can be thought of as the end of the current time step. Since all the for loops are inside the same time step, if they use non-blocking assignments, they schedule a series of events to occur at the end of the current time step. So thefor j and for k loops always see the initial values of the array. As this algorithm is expressed, it is necessary for these two loops to be working with the data after the swap has occurred.

module compressMe();

reg [15:0] p0;
reg [15:0] p1;
reg [15:0] p2;
reg [15:0] p3;
reg [15:0] p4;
reg [15:0] p5;
reg [15:0] p6;
reg [15:0] p7;

reg [15:0] pp [7:0];

integer i,j,k;

reg swapTemp;

initial
begin
p0 <= 16'b0000000000000000;
p1 <= 16'b1111111111111111;
p2 <= 16'b0000000000000000;
p3 <= 16'b1111111111111111;
p4 <= 16'b0000000000000000;
p5 <= 16'b1111111111111111;
p6 <= 16'b0000000000000000;
p7 <= 16'b1111111111111111;
end

always @ (p0 or p1 or p2 or p3 or p4 or p5 or p6 or p7)
begin
pp[0] = p0;
pp[1] = p1;
pp[2] = p2;
pp[3] = p3;
pp[4] = p4;
pp[5] = p5;
pp[6] = p6;
pp[7] = p7;

for (i=0; i<=15; i=i+1)
begin
for (j=7; j>=1; j=j-1)
begin
for (k=j-1; k>=1; k=k-1)c
beginc
if (    ( !pp[j][i] )     &&    (  pp[k][i]  )    )
begin
swapTemp = pp[j][i];
pp[j][i] = pp[k][i];
pp[k][i] = swapTemp;
end
end
end
end
end

initial
begin
#100 for (i=0; i<=7; i=i+1)
\$display("pp[%d] = %16b ", i, pp[i]);
end

endmodule


This will produce:

 ncsim> run
pp[          0] = 0000000000000000
pp[          1] = 0000000000000000
pp[          2] = 0000000000000000
pp[          3] = 0000000000000000
pp[          4] = 1111111111111111
pp[          5] = 1111111111111111
pp[          6] = 1111111111111111
pp[          7] = 1111111111111111


The problem is that you're writing code that would be appropriate for a software programming language in a hardware description language.

Remember, in a HDL, a for loop describes parallel hardware constructs, not sequential processing steps.

In your case, the outer for loop is appropriate, since you want to build logic that handles each column independently. But within each column, you want to count the number of ones and then output a bit vector that has that many bits set in a row. The easiest way to specify this might be to simply enumerate all of the possibilities with a case statement or a lookup table.

If you really want to do it with logic, this answer may offer a clue. (You're basically sorting a list of 1-bit values.)