binary sorter circuit

[cyboman]

I want to get back to circuit design and decided to practice some of the problems. I'm using VHDL for coding. The problem looked simple to me, but to my surprise I was not able to solve it. Please bear in mind that it is not a homework problem. I work full time and simply want to do more of circuit design and want to pick my brain. Here is the problem.

Binary sorter.

Using concurrent code, design a circuit capable of ordering the bits of a bit vector. The ordering should be from left to right, with all '1's coming first (for example, "00011001" would become "11100000").

Does anybody have any idea?
Any help is appreciated.

 

[std_match]

One solution:

Design a sorter with 2 inputs and 2 outputs:

In Out
00 00
01 10
10 10
11 11

It is easy to solve your problem with a bunch of these 2-bit sorters.
As an excercise, try to do it with as few source code lines as possible.
You can use a VHDL "for generate" loop.

 

[mrflibble]

What std_match said.

If you do the 2-bit swap method, for a 4-bit input it would look something like this in ascii art:

  3 2 1 0
  o o o o
   X   X
  o o o o
  |  X  |
  o o o o
   X   X
  o o o o

Where o represents a bit, X is a 2-bit sorter, and | is just a straight copy. Data flow is from top to bottom.

 

[std_match]

One more stage is needed, otherwise input "0011" will fail:

  3 2 1 0
  o o o o
   X   X
  o o o o
  |  X  |
  o o o o
   X   X
  o o o o 
  |  X  |
  o o o o

 

[mrflibble]

Well, darnit. I knew I should have checked it more carefully. In any event 3 stages should by definition be enough. The trick is to do the first stage as swap(D3,D0) ; swap(D2,D1) and then you can avoid my silly mistake. I knew there was going to be a price to be payed for laziness and not making optimal use of the opportunity of swapping more bits at 2nd stage.