Log 2 N generic comparison tree
- by Morano88
Hey!
I'm working on an algorithm for Redundant Binary Representation (RBR) where every two bits represent a digit.
I designed the comparator that takes 4 bits and gives out 2 bits. I want to make the 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 equals n where (n = 2^X) i.e n = 2,4,8,16,32,... etc. Like this :
However, If my input let us say is 6 or 10 .. then it becomes not smooth and I have to take into account some odd situations like this :
I have a shallow experience in algorithms .. is there a generic way to do it .. so at the end I get only 2 bits no matter what the input is ?
I just need hints or pseudo-code. If my question is not appropriate here .. so feel free to flag it or tell me to remove it.
I'm using VHDL by the way!