Июн 12 2015

О подсчете нулей

В задачах, связанных с арифметическими функциями, часто необходимо подсчитать количество нулей в старших разрядах числа. Эту функцию можно реализовать по-разному.

Итак, вариант 1:

function [ZERO_DATA_WIDTH - 1: 0] zero_cnt;
input [DATA_WIDTH - 1: 0] in;
integer i;
begin
  zero_cnt = DATA_WIDTH;
  for(i = DATA_WIDTH - 1; i >= 0; i = i - 1)
  begin
    if(in[i] && zero_cnt == DATA_WIDTH)
	   zero_cnt = DATA_WIDTH - i - 1;
  end
end
endfunction

Возможно написать и второй вариант, с рекурсией:

function [ZERO_DATA_WIDTH - 1: 0] zero_cnt_recursive;
input [DATA_WIDTH - 1: 0] in;
begin
  if(in == 0)
    zero_cnt_recursive = DATA_WIDTH;
  else
    zero_cnt_recursive = (zero_cnt_recursive(in && 1) - 1);
end
endfunction

Разумеется, при симуляции оба варианта работают одинаково:

pic1

(картинка кликабельна)

На скриншоте верхний сигнал (zero_counter1) соответствует первому варианту реализации, сигнал zero_counter2, соответственно, второму.

Теперь попробуем синтезировать. Делаем простейший модуль:

module zero_cnt_1
#(
parameter DATA_WIDTH = 53,
parameter ZERO_DATA_WIDTH = 6
)
(
  input wire clk, rst_n,
  input wire [DATA_WIDTH - 1: 0] in,
  output reg [ZERO_DATA_WIDTH - 1: 0] result
);

always@(posedge clk or negedge rst_n)
begin
  if(!rst_n)
    result <= 0;
  else
    result <= zero_cnt(in);  
end
  function [ZERO_DATA_WIDTH - 1: 0] zero_cnt;
  input [DATA_WIDTH - 1: 0] in;
  integer i;
  begin
      zero_cnt = DATA_WIDTH;
  for(i = DATA_WIDTH - 1; i >= 0; i = i - 1)
  begin
    if(in[i] && zero_cnt == DATA_WIDTH)
      zero_cnt = DATA_WIDTH - i - 1;
  end
end
endfunction

endmodule

И синтезируем. Итак, синтез в Quartus II 11.1 для Cyclone II: 134 логических элемента, синтез в ISE14.4 для Spartan 3: 121 LUT.

Пробуем синтезировать вторую функцию, и тут нас ожидает неудача: ни Quartus, ни ISE не умеют синтезировать рекурсивные функции (что логично, впрочем).

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