Complexity: Number of MAC operations on a DSP

Question

Suppose a complex $(N \times N)$ matrix $\mathbf{T}$, multiplying a complex vector $\mathbf{x}$ with length $N$.

On a given application that I'm studying, which is irrelevant for this discussion, I can get the same results of $\mathbf{Tx}$ by the following operation:

\begin{align} \mathbf{W_1} \Re\{ \mathbf{y} \} + \mathbf{W_2} \Im\{ \mathbf{y} \} \end{align} where are $\mathbf{W_1}$ and $\mathbf{W_2}$ are complex $(\frac{N}{2} \times \frac{N}{2})$ matrices, $\mathbf{y}$ is a complex vector of length $\frac{N}{2}$, $\Re$ denote the real part and $\Im$ the imaginary part.

I'm trying to asses which one requires more operations in a real implementation.

My analysis is that the first ($\mathbf{Tx}$) requires $N^2$ MACs, while the second requires

$ 2(\frac{N}{2})^2 = \frac{N^2}{2}$ MACs, plus $\frac{N}{2}$ sums.

I'm not completely sure about this, neither about how a DSP deals with complex numbers. Am I making any mistake?

I'd appreciate your help.

Answer 1

I'm getting a completely different answer. I get the same answer for the number of total scalar operations, but the number of scalar complex operations is not the same as the number of scalar real operations.

Let's look at how much work it takes to do a complex scalar multiplication and complex scalar addition.

Given two complex scalars $z_0 = \langle x_0, y_0 \rangle$ and $z_1 = \langle x_1, y_1 \rangle$ then $z_0 z_1 = \langle x_0 x_1 - y_0 y_1, x_0 y_1 + x_1 y_0\rangle$, so 4 real multiplications and 2 real additions. $z_0 + z_1 = \langle x_0+x_1, y_0+y_1 \rangle$, so 2 scalar additions. The computation $\mathbf{Tx}$ requires a total of $N^2$ complex scalar multiplications and $N (N-1) = N^2-N$ complex scalar additions, so $4N^2$ real multiplications and $4N^2 - 2N$ scalar additions ($2N^2$ from the complex multiplications and $2N^2-2N$ from the sums for the dot products).

In the other case you seem to have some magical way of transforming to two much smaller complex matrices (perhaps your original matrix $\mathbf{T}$ was very sparse?), and your vectors are pure real (or pure imaginary) so a scalar multiplication only takes two real multiplications. $z_0 x_1 = \langle x_0 x_1, y_0 x_1\rangle$. So $\mathbf{W_1} \Re\{ \mathbf{y} \}$ requires $\frac{N^2}{4}$ complex times real multiplications, so $\frac{N^2}{2}$ total real multiplies, and $\frac{N}{2}(\frac{N}{2}-1)$ complex additions, so $\frac{N^2}{2}-N$ real additions. $\mathbf{W_2}\Im\{y\}$ has the same cost, and then you need to do a final sum of the two products at a cost of $\frac{N}{2}$ complex additions, so $N$ real additions. So your second technique takes a total of $N^2$ real multiplies and $N^2 - N$ real additions. So your second technique should take about $\frac{1}{4}$^th the work of the original technique.

Answer 2

It appears to me that your analysis is basically correct, except that in the second case there are $\frac{N}{2}$ sums, not $N$ sums.

I'm not sure what you are looking for when you ask "how a DSP deals with complex numbers", but generally they are represented in one of two ways: as separate real and imaginary values, or as a "complex" entity (structure/object/whatever- depends on the language) that contains real and imaginary members.