If you can't pipeline this for any reason (or pipelining would not get you better timings as you hinted), I guess the easiest approach would be to implement this as a simple function.
If the number of integers is/can be made a power of two, then you can use a binary tree structure, which will limit the number of comparison levels.
A naive approach (as suggested in a previous post) would require N - 1 comparisons and N - 1 comparison levels.
A binary tree approach will require N - 1 comparisons and log2 N levels, which should get you (much) better timings unless the number of integers is smaller than 4. (So how small is small? In your example, with 3 values, obviously this won't make a difference.) [This is basically what Bruce suggested I think.]
I would personally implement this (on first intention) as a recursive function in VHDL, which easily maps to a tree structure with most synthesis tools.
Pseudo-code:
* T is an array of N signed integers (N a power of 2)
FindMin(T) =
* if N = 2 => T[0] if abs(T[0]) < abs(T[1]), T[1] otherwise
* if N > 2 => (N0 = FindMin(T[0..N/2-1]), N1 = FindMin(T[N/2..N-1])), N0 if abs(N0) < abs(N1), N1 otherwise
If N is not a power of 2, you could use a mixed algorithm to deal with this while still limiting the number of levels.
I don't know if you can find a fancy algorithm than would require less than N - 1 comparisons?
Note: in VHDL, this could be something like this (for N a power of two):
constant MinAbs_DataWidth : integer := 16;
subtype MinAbs_Data_t is signed(MinAbs_DataWidth - 1 downto 0);
type MinAbs_DataArray_t is array (integer range <>) of MinAbs_Data_t;
function MinAbs(DataSet : MinAbs_DataArray_t) return MinAbs_Data_t is
variable N0, N1, Result : MinAbs_Data_t;
variable iMid : integer;
begin
if DataSet'length > 2 then
iMid := (DataSet'low + DataSet'high) / 2;
N0 := MinAbs(DataSet(0 to iMid - 1));
N1 := MinAbs(DataSet(iMid to DataSet'high));
else
N0 := DataSet(DataSet'low);
N1 := DataSet(DataSet'high);
end if;
if abs(N0) < abs(N1) then
Result := N0;
else
Result := N1;
end if;
return Result;
end MinAbs;
Home
Help
Search
Login
Register
