Задача следующая:

имеется 32-х разрядное число. Нужно вычислить, сколько у этого числа последовательных нулей или единиц, начиная со старшего разряда. Поясню на примере 8-разрядного числа:

0001xxxx или 1110xxxx дают результат 2 (3 одинаковых соседних бита в старших разрядах)
10xxxxxx или 01xxxxxx дают результат 0 (одинаковых соседних битов нет)
0000001x или 1111110x дают результат 5 (6 одинаковых соседних битов в старших разрядах)

x означает, что значение этих битов уже не имеет значения.

Задача тривиальна, если вычисления завязать на клок и строить внутри процесса (код пишется на Верилоге). Однако ищется возможность реализации на комбинационной логике (вопрос быстродействия стоит остро).

Буду благодарен за любые конструктивные идеи.

А можно посмотреть на этот код?

если всё упирается в быстродействие, тогда делаете таблично(ROM)
адрес это ваши 0001xxxx и т.д.
а на выходе уже получаете "ответ" за 1 такт

а комбинационой логикой врядли получится быстрее

Какой код? Если этот , то я его даже не писал, там никаких трудностей нет.
Этот вариант написан на C, перевести его в верилог не проблема(будет время - переведу).


Но фишка в том, что такой вариант не катит.

Думал уже... Это какой же ROM нужен, чтобы таким макаром 32-х битное число обработать...
Проблема в том, что эта процедура - мизерная часть офигенно развесистого алгоритма, который пишется для создания ASIC на его базе, поэтому затраты по площади (так же, как и быстродействие) - основные проблемы.
Я уже попробовал минимизировать аналогичную функцию для 8-битного числа - результат впечатляет
С 32-битным даже пробовать не буду.
Похоже, вариантов всего два - попытаться вообще исключить эту гнусную процедуру из алгоритма или все таки делать ее синхронно.

Если данные идут последовательно, то можно использовать счётчик.
Сбрасывать его когда последующий бит не равен предыдущему.

поток нужен ?
или мона и ждайт ?

Приветствую!

У меня вот этот вариант работает для VirtexII-5 с частотой >140 МГц
(только положительные чисела -ищется цепочка 0)

Успехов! Rob.

function [WHE-1:0] GetExpU;
input [WHI-1:0] N; //входное число с разряднотью WHI (у меня 48)
input integer M; //максимальная длинна иследуемого куска (у меня 26)
integer k,rz;
begin
rz=0;
k=WHI-1;
while(~N[k] && k>(WHI-1-M))
begin
k=k-1;
rz=rz+1;
end
GetExpU=rz;//WHI-1-k;
end
endfunction

always @(posedge clk)
rExp<=GetExpU(Din,(WHI-WHF));

module comp32
(
input [31:0] in,
output [4:0] out
);


reg temp;
integer temp_a;

integer i;

always @(in) begin
temp=1;
temp_a=0;
for (i=31; i>0; i=i-1) begin
if (in[i] != in[i-1]) temp = 0;
if ((in[i] == in[i-1]) & temp) temp_a = temp_a+1; end
end
assign out = temp_a[4:0];

endmodule

glock17,
любые верилоговские конструкции, не стоящие под always @(edge signal), синтезируются в комбинаторную логику. Ваша задача элементарна:
integer i, result;
i=30;
while ((a[31]==a[i]) && (i>=0)) i=i-1;
result=30-i;
м.б. сделал ошибку, но принцип должен быть понятен.

To Gate
В вашем примере неправильно будет интерпитироваться код все нули. Числа 31 не получить.

To Gate:
Это последовательный путь.. А надо параллельный, т.е. за 1 такт, тут задача на мой взгляд решается просто: Ставим 62 компаратора на (2,3,4..32 разряда), которые будут сравнивать наше слово с константами типа 11, 111, 1111,.... и т.д. 00, 000,0000... и т.д. соответсвтвенно цепляем на них старшие разряды шины и сравниваем со всеми одновременно выход будет работать по двоично-десятичной логике.

Причем тут последовательный или параллельный. И то и другое за один такт. Другое дело как это одной строчкой оформить. А то о чем вы говорите, что case это уже дело рук.

При числе, состоящем из всех 1 или 0, выход из цикла произойдет с i=-1, result=31. Что неверно?Проблема только в вычислении a[-1] (синтезатор может и не ругнуться) - ну тогда надо индекс сдвинуть на +1 или переписать условие цикла. Впрочем, пускай глок проверяет, принцип ему три человека рассказали.

в исходном коде стоит
if (!x)
return 0;

Уважаемый id_gene. Дело в том, что я не программист. И хотя текст этот понимаю, в железе освоил только FO, а вот условие в while ну никак осилить не могу. Ошибку выдает. Может Вы мне поможете. Написать пару формул.

По моему делается из 31 элемента XOR, который сводит 0 к 1 в соотвествии с первым разрядом и приоритетного шифратора. Как его сделать, написано в любой книжке по цифровой логике. Чтобы не делать многовходовых функций, он каскадируется.



Если полагаться, что компилятор Вам такую штуку придумает по поведенческому описанию, то в ней может оказаться тысяч сто вентилей

Я тоже, почитав ответы, пришёл к выводу об использовании XOR. Можно каскадированием, как предложил DS_, но при этом, имхо, это будет последовательное сравнение, т.е. тратим время.
Я бы, возможно, сделал примерно так:



или, если хочется короче:


всё это, естественно, под always @(data)

А как Вы думаете, что построится по Вашим IF ? Это и будет приоритетный шифратор. Собрать 16 входов физически нельзя, и поскольку компилятор не понимает сущности задачи, он его нарежет произволльным образом и либо вентилей получится больше чем надо, либо логических уровней.А скорее всего вообще будет построен коммутатор на 32 входа, который вектора от 0 до 31 на выход пропускает.

Лучше об этом самому подумать. А то потом возникает удивление, почему в микросхеме площади не хватает.

Код неверен, т.к. поразрядный ксор будет выдавать парити.

Всем откликнувшимся - большое спасибо!
Проблема на предварительном уровне решена.
Докладываю результаты проверки :
- конструкция, предложенная sazh, заработала без проблем, так что беру её на карандашик (sazh, отдельное спасибо)
- кроме того, есть собственный вариант (после отладки опубликую).
- все остальные варианты пока досконально не ковырял (я пишу "досконально", потому что сразу они не заработали, каждый нуждается в доделках (на что пока не было времени), хотя идеи практически везде правильные). Единственное замечание из личного опыта: использование конструкции while допустимо при создании функционального кода, при синтезе лучше такой конструкции избегать, так как часто это выливается в неоправданное расходование ресурсов.

Окончательный вариант пока не выбран, точку в этом деле поставим после синтеза (жду, когда заработает FTP, что бы сразу использовать синтезатор, указанный заказчиком). Вариант sazh намного компактнее нашего по коду, однако насчет компактности при синтезе я пока не уверен.

Тем не менее, тема пока не закрыта, поэтому дальнейшие предложения приветствуются.

Еще раз спасибо всем участникам дискуссии.

Да я как-то и не спорю с этим . Насколько я понимаю, эти IF выродятся именно в то, что я написал чуть выше. Только более короткая форма в программе. Собственно, вопрос в том, что автору топика важнее: время или количечство занимаемого силикона. Если второе, то можно просто сдвигать и счимтать количество одинаковых битов. Если важнее первое, то приоритетный шифратор - вот он


Да, пожалуй. Он хорошо работает с лидирущими нулями. С нечётным количеством лидирующих единиц приведёт к неправильному результату. Значит, к сожалению придётся ставить поразрядные & и |. Какая неприятность....

А разве мой первый вариант это разве не XOR в связке с преоритетным шифратором?. Другое дело : при таком описании синтезатор сумматоры задействовал. так можно и без сумматоров. А можно и с клоком на конвейере. А лучше синтезатора (ручками) приоритетный шифратор все равно не сделаете.
module comp32p
(
input [31:0] in,
output [4:0] out
);


reg temp;
integer temp_a;

integer i;

always @(in) begin
temp=1;
temp_a=31;
for (i=31; i>0; i=i-1) begin
if ((in[31] != in[i-1]) & temp) begin
temp_a = 31-i;
temp = 0;end end
end
assign out = temp_a[4:0];

endmodule