Подсчет числа одинаковых разрядов двоичного числа, ищется комбинаторная реализация Опции

[glock17]

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

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

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

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

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

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

[sazh]

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

[Postoroniy_V]

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

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

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

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

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

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

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

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

[glock17]

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

Какой код? Если этот

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

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

int16 L32_exp(int32 x)
{
int16 exp = 0;

if (!x)
return 0;

while ((x ^ (x << 1)) > 0)
{
x <<= 1;
exp++;
}
return (exp);
}

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

[glock17]

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

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

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

[lelik]

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

[des00]

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

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

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

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

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

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

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

[RobFPGA]

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

У меня вот этот вариант работает для 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));

[sazh]

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

[Gate]

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

[sazh]

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

[Magnum]

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

Сообщение отредактировал Magnum - Apr 28 2006, 10:09

[sazh]

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

[Gate]

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

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

[id_gene]

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

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

[sazh]

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

[DS]

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



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

[Chudik]

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

Код

if (!(^data[31:0])) cnt = 31;
else if (!(^data[31:1])) cnt = 30;
else if (!(^data[31:2])) cnt = 29;
...
else if (!(^data[31:30])) cnt = 1;
else cnt=0

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

Код

   for(i=0; i<32; i=i+1)
       if(!(^data[31:i])
          begin
               cnt = 31 - i;
               break;
          end

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

Сообщение отредактировал Chudik - Apr 30 2006, 18:05

[DS]

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

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

[Gate]

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

Код

if (!(^data[31:0])) cnt = 31;
else if (!(^data[31:1])) cnt = 30;
else if (!(^data[31:2])) cnt = 29;
...
else if (!(^data[31:30])) cnt = 1;
else cnt=0

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

Код

   for(i=0; i<32; i=i+1)
       if(!(^data[31:i])
          begin
               cnt = 31 - i;
               break;
          end

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

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

[glock17]

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

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

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

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

[Chudik]

А как Вы думаете, что построится по Вашим IF ? Это и будет приоритетный шифратор.
Лучше об этом самому подумать. А то потом возникает удивление, почему в микросхеме площади не хватает.

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

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

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

[sazh]

А разве мой первый вариант это разве не 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