Log 2 N универсальное дерево сравнения

Question

Я работаю над алгоритмом для избыточного двоичного представления ( RBR ), где каждые два бита представляют собой цифру.

Я разработал компаратор, который принимает 4 бита и выдает 2 бита,Я хочу сделать сравнение в журнале 2 n, поэтому, если у меня есть X и Y .. Я сравниваю каждые 2 бита X с каждыми 2 битами Y. Это гладко, если число битов X или Y равно n, где (n= 2 ^ X) то есть n = 2,4,8,16,32, ... и т. Д. Примерно так:

альтернативный текст http://www.freeimagehosting.net/uploads/th.a57569d23f.png

Однако, если мой ввод позволит намскажем, 6 или 10 .. тогда это становится не гладким, и я должен принять во внимание некоторые странные ситуации, подобные этой:

альтернативный текст http://www.freeimagehosting.net/uploads/th.28bd84300d.png

У меня небольшой опыт работы с алгоритмами.... есть ли общий способ сделать это ... так что в конце я получаю только 2 бита, независимо от того, что ввод?

Мне просто нужны подсказки или псевдокод.Если мой вопрос здесь неуместен ... не стесняйтесь пометить его или скажите мне удалить его.

Кстати, я использую VHDL!

Answer 1

Дополните вашу строку ввода битами 0, пока она не станет хорошей длины, может быть? Это проще всего сделать неявно в вашем компараторе: если число битов, переданных компаратору в качестве аргумента, меньше 4, просто сдвиньте влево те биты, которые у вас есть, пока входное слово не станет нужного размера.

Answer 2

Каждое сравнение будет уменьшать ваше общее количество битов на 2, поэтому, если порядок не имеет значения по какой-либо другой причине, вы будете выполнять одинаковое количество сравнений, независимо от того, как вы организуете сравнения.