Problem statement

Often, you come across digital designs where a vector of length M-bit has to be added N times or N no. of M-bit vectors have to be added together. A use case of this while designing accumulators for n-tap digital filters in RTL. So, the problem statement is what should be the minimum size K of the accumulator which can store the sum without any overflow or redundant bits.

Naive solution

I have often seen the naive way used by beginners where the size of the accumulator is simply configured as: K = M + N - 1. Well, this could accommodate any overflow, but it has redundant bits. For e.g: consider adding 4-bit unsigned number 6 times. The max. sum possible is 15 * 6 = 90 = 7'b1011010 . So, making k = 4 + 6 - 1 = 9 bits is pessimistic, as 7 bits are enough to accommodate the result; the rest two MSbs are redundant. It is fairly easy to calculate and hardcode the value of K, if the size of M and N are fixed values in the design. What if they are not?…

Generic solution with a bit math!

If M and N configurable parameters in the design, we have to come up with an expression to fix the width K of accumulator. Let’s assume unsigned numbers and apply a bit old-school math to solve this…

The largest no. which can be represented by M-bit vector = 2^{M}-1
The worst-case or largest sum, if they are added N times = N * (2^{M}-1)
Therefore, the size of accumulator, K should be at least:

K = ceil(log_2(N * (2^{M}-1)))

In SV, K can be parameterized as:

parameter M = 8,
parameter N = 16,
parameter K = $clog2(N*((2**M)-1))

A sub-case or corollary is when N is a power of 2, say N=2^n. This is a common case for e.g. when doing linear interpolations over 2, 4, 8… taps in digital filters . Then, K can be further simplified as:

K = ceil(log_2(2^n * (2^{M}-1)))
\implies K = ceil(log_2(2^n)+log_2(2^{M}-1))

Analytically, log_2(2^{M}-1) = log_2(2^{M}) for all values of M > 0
\implies K = ceil(n+M)

Since n and M are whole numbers, ceil(n+M) = n+M

\therefore K = n+M, or:

K=log_2(N) + M

In SV, K can be parameterized as:

parameter M = 8,
parameter N = 16,
parameter K = $clog2(N)+M  // $clog2 is used for log2 in SV

Support

Leave a comment or visit support for any queries/feedback regarding the content of this blog.
If you liked Chipmunk , do follow here: