Sorting the bits of a 32-bit vector.

Hello,

I need to do a design that sorts the bits of a 32-bit vector(not sure if it's called vector) like this:
I must have a 32-bit parallel in and a serial out.

And it must be combinational.

I tried something like this:
But I tought I would need to do the design sequential if I count the ones.

Can you please help me do this? My head hurts from trying to understand verilog.

A serial output already implies there is some sort if sequential logic. I have no idea how you can make a serial shift without some sort of storage or at least a MUX with a counter.

Hi,

I'd do it with a counter.

Shift your 32 bits in.
Every time it is "1" jncreae the counter.

After this the counter shows the count of "1".
Now generate 32 "output" pulses, count down the counter (above) until it is zero. As long as it is not zero shift out a "1".

Klaus

Klaus the circuit is supposed to be combinatorial.

alexmihai said:

Hello,

I need to do a design that sorts the bits of a 32-bit vector(not sure if it's called vector) like this:

Code:

1010010101010 => 00000001111111

I must have a 32-bit parallel in and a serial out.

And it must be combinational.

I tried something like this:

Code:

assign c=in[0]+in[1]+in[2]+in[3]+in[4]+in[5]+in[6]+in[7]+in[8]+in[9]+in[10]+in[11]+in[12]+in[13]+in[14]+in[15]+in[16]+in[17]+in[18]+in[19]+in[20]+in[21]+in[22]+in[23]+in[24]+in[25]+in[26]+in[27]+in[28]+in[29]+in[30]+in[31];
assign out=(1<<c)-1;

But I tought I would need to do the design sequential if I count the ones.

Can you please help me do this? My head hurts from trying to understand verilog.

Click to expand...

In Verilog/VHDL, you are describing a circuit that solves the problem.

Adding a bit to another can be done with a full adder. A simple circuit.
Adding three bits together would create more than one full adder.
Adding 32 bits together requires more still.

This means that the size and delay increase as more bits are processed per cycle.

For this case, the 32b bitcount operation is probably feasible. The circuit isn't actually that complex, and has some ability to make use of faster FPGA resources. The output generation should also be feasible. I'm not sure if the tools will create an ideal implemention, but even a basic implementation isn't that bad.

The issue with software based design methods is that you can create very large, possibly very slow circuits if you are not careful. It makes more sense to find a way to perform the computation over several cycles _if_ a circuit is too large/slow. For very complex operations, it can even make sense to generate a small CPU, if the operation can be allowed to take many cycles.

You must clarify since "must be combinatorial" and "serial out" is not compatible.
Do you want the ones or the zeros first in the output?

Is this a school homework or a real problem?
If it is a real problem, it is enough to generate the first output bit combinatorial. That is easy, compare with all ones or all zeros depending on if you want the ones or the zeros first.
The following bits can be generated one per clock cycle by a special shift register that will shift out only ones or zeros until there is no more of that kind.
If this is an acceptable solution, we can continue to discuss this special shift register.
Also, if one or two clock cycles delay is acceptable for the first output bit, the design will be "cleaner".