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

[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;