Need help with sorting a 32 bit string

Question

I have to program a combinational circuit which sorts a 32 bit array like this: 10011011010101101010101010110010 ==> 00000000000000011111111111111111

The input must be parallel and 32 bit. The output must serial and 32 tacts.

I hope it's clear what the problem wants. I'm not doing very well with verilog so i need help with a project. I don't even know how to start.

• Eugene Sh.: Look for "sorting networks".
• gbulmer: Welcome to ee.se. Please read the help center to understand how to ask good questions. We expect questions to show some evidence of research or effort, especially questions that look like homework (we don't want to rob you of the opportunity to learn). Otherwise it will likely get close. I believe EugeneSh has given you enough help to answer the question, so you might not care if it gets closed. However, if you want more help, you should explain what you have done so far, and where you are stuck. That way we don't close the question, or attempt to write a chapter of a book giving an answer.

Answer 1

I think viewing this as sorting is a complicated way to address this problem. Shuffling the bits all the way in Verilog would certainly be a pain.

Unless I did not uderstood the problem well, it seems to boil down to counting the bits that are set to 1, and outputting a string that has this number of 1 to the right. I think this would be a more appropriate way to solve this problem in Verilog.

The most difficult part here is counting the bits. How to do it was asked here and here. A simple way is to add all the bits (and trust the optimizer for generating an efficient way of combining the logic).

Then, serially output the appropriate number of 0 followed by the appropriate number of 1 (depending on the result).

• Eugene Sh.: This would be a complicated solution. A layered compare-and-swap network is easier to implement (well, it might be less efficient, which is BTW questionable...)
• dim: @Eugene It actually takes two lines of code: c = x[0] + x[1] + x[2] + ... + x[31] and out = (1 << c) - 1, or something like that. Regarding the efficiency, I don't really know. But your solution is nice, too. It would be interesting to compare area/speed. Too bad I'm too lazy...
• Eugene Sh.: Oh well, I was thinking about gate-level implementation...

Answer 2

Start by making the problem smaller. What if you only had two-bits. Then you would have the truth table

0 0 => 0 0
0 1 => 0 1
1 0 => 0 1
1 1 => 1 1

Notice that the LSB is the OR of the input bits, and the MSB is the AND of the input bits. Then think about a repetitive structure that could be applied to give you the result you are looking for.,