Log 2 N general comparison tree

Question

I am working on a Redundant Binary Representation ( RBR ) algorithm where every two bits represent a digit.

I designed a comparator that takes 4 bits and produces 2 bits. I want to make a comparison in log 2 n, so if I have X and Y. I compare every 2 bits of X with every 2 bits of Y. This is smooth if the number of bits of X or Y is n, where (n = 2 ^ X), i.e. n = 2,4,8,16,32, ... etc. Like this:

alt text http://www.freeimagehosting.net/uploads/th.a57569d23f.png

However, if my input is, say, 6 or 10 .. then it gets nonsmooth and I have to take into account some odd situations like this:

alt text http://www.freeimagehosting.net/uploads/th.28bd84300d.png

I have a little experience in algorithms. Is there a general way to do this. So in the end I get only 2 bits no matter what the input is?

I only need hints or pseudo codes. If my question is not appropriate here, so feel free to tag it or tell me to delete it.

I am using VHDL by the way!

Answer 1

Put your input bit string with 0until it is a nice length, maybe? The easiest way to do this is implicitly in your comparator: if the number of bits specified as an argument to the comparator is less than 4, just shift the bits you have to the left until the input word has the right size.

Answer 2

2, , - , , .