WorksEngineering
Greedy Vector Approximation Based on Rotation for Multiplierless Complex Products
Abstract
This paper proposes a greedy approximation algorithm for performing complex-valued inner products in multiplierless hardware. The matching pursuits for accurate rotation approximation (MPARA) algorithm approximates the tangent of the phase of complex elements as a sum of signed powers of two (SOPOT) representation, enabling multiplierless hardware for complex-valued multiplication. The proposed algorithm outperforms other state-of-the-art approximation methods for approximating the twiddle factors of a fast Fourier transform (FFT).
Introduction
Complex-number multiplication is a key operation in many digital signal processing applications for communications. It is the basis for the discrete Fourier transform (DFT), the core of orthogonal frequency division multiplexing (OFDM). The DFT also appears in other countless communication applications, such as multiple-input multiple-output (MIMO) systems, direction of arrival (DoA) estimation, precoding and postcoding in transceivers, and antenna selection [1, 2].
Performing bit shifts instead of conventional multiplications is a well-known way to reduce the computational cost of inner products. The shift-and-add structure for multiplication falls under multiplierless hardware and is a known design for efficient finite impulse response (FIR) filter hardware designs [3, 4, 5].
In [4], the authors explore efficient sums of signed powers of two (SOPOT) representations that rely on signed powers of two (SPTs) to represent real numbers. As the computational complexity is proportional to the number of SPTs, they propose an algorithm called matching pursuits with generalized bit planes (MPGBP) that achieves vector approximation based on SOPOT representations with a minimal number of SPTs for FIR filters. However, their solution is based on real-valued multiplications.
For complex values, multiplication is interpreted as a phase rotation and an amplitude gain. A multiplierless solution for rotation is the coordinate rotation digit computer (CORDIC), which iterates over quantized micro-rotations (MR) performed by bit shifts to approximate a given rotation [6, 7]. Although efficient, CORDIC cannot select the steps it should take in the approximation, so it takes unnecessary steps and leaves room for improvement [7, 8, 9, 10, 11, 12].
In this paper, we propose a middle-ground algorithm that approximates complex-valued vectors for multiplierless hardware using the fewest bit shifts. The matching pursuits for accurate rotation approximation (MPARA) combines MPGBP and CORDIC. It approximates the vector by considering each element’s phase. The solution allocates MRs to the vector elements that most reduce the cost function and enables mixed-precision quantization based on the rotation.
As a use case, we approximate the twiddle factors of a fast Fourier transform (FFT) and show that our method mitigates the non-orthogonality between the transform and its inverse.
Multiplierless Rotation
Let be two complex values such that , where is the absolute value operator. The product of these values is written as
where is the resulting complex number, , and and indicate the real and imaginary components of the complex number.
Complex-Number Multiplication as a Rotation
Complex numbers have amplitude and phase. When we multiply two complex numbers, the resulting amplitude is the Algorithm 1 CORDIC phase rotation
Input: , ,
Output:
product of the amplitudes, and the resulting phase is the sum of the phases. Let be the phase of , we have
The phase rotation transforms, by rotation, into , and by operating (2) and (3) instead of Eq. (1), explains the phase rotation in the cartesian form. Figure 1 shows the phase rotation, using four multipliers and two adders.
Figure 1. Diagram of complex-number multiplication, , as a phase rotation.
Coordinate Rotation Digit Computer (CORDIC)
CORDIC exploits equations (2) and (3) by approximating as a SOPOT, enabling shift-and-add computation. In each CORDIC iteration, we take an angular step of size in the direction of the desired rotation, where is the algorithm’s iteration index. Algorithm 1.
At each iteration, the residual rotation is calculated as
and is the residual rotation and defines the direction of the next iteration’s step.
Algorithm 1 disregards the amplitude correction of , which is due to in equations (2) and (3). In CORDIC, the correction is performed as follows
where is the amplitude correction. As with shift-and-add multiplierless structures, CORDIC hardware design can be optimized to minimize FPGA area, latency, or other criteria [3, 5, 6].
CORDIC and the Signed Bit Plane
When representing vectors as SOPOT, the vector is mapped into signed bit planes. We allocate symbols from the set in the signed bit plane. A bit plane is defined by its maximum value, or the shallowest bit, and by its minimum value, or deepest bit.
Algorithm 1 allocates symbols from the nonzero set , where in a bit plane. The bit plane starts at and increases in depth in each iteration, up to the maximum bit plane depth, . Each allocated symbol represents two shift-and-add operations.
By using the set , we promote sparsity in the bit plane, enabling approximations with few nonzero elements [4]. This reduces the number of shift-and-add operations. We propose a greedy algorithm to achieve this approximation.
Greedy Phase Approximation
Let be a complex-valued vector, composed as
where is the transpose operator, and . We assume that and that , where is the phase of , which can be achieved in a preprocessing step justified further in this section. Let be a vector which elements are , i.e., , where is the Hadamard division operator, returns the real components of a complex, and its imaginary.
Let be a dictionary composed of -length complex-valued vectors, referred as codewords, and a vector containing the tangent of each element of . The inner product between and is defined as
and the projection of in is
where is the projection coefficient, and is the Euclidean norm. We use the following -term approximation
where is the approximated vector, is a quantization function to round to the nearest power of two, is the -th codeword index, and is the -th bit plane depth.
We base the approximation on a matching pursuits (MP) algorithm, namely the matching pursuits with generalized bit planes (MPGBP) [4]. Starting at and , the algorithm iteratively performs the approximation by computing
where indexes the algorithm iterations. Next, we discuss codeword and bit plane depth selection.
Codeword Selection
The dictionary is composed of codewords of length with elements from the set , i.e., . We limit the number of nonzero elements in the codeword to , with . At the -th iteration, we select the codeword that maximizes the projection coefficient,
with . The dictionary size, , becomes rapidly impractical for an exhaustive codeword search as and increases. However, we can generate the codeword that solves (12). Let be the set of indices of the vector . Since the codeword is composed of elements from , the optimal codeword must select and sum the greatest absolute values of , i.e., the set
where is any subset of with size . Therefore, the codeword is composed as
Bit Plane Depth Selection
At the -th iteration, performs the quantization of the projection coefficient, . It consists of finding that best approximates . By bounding by and , we have
Algorithm 2 MP for accurate rotation approximation
Input: w ∈ ℂ^N, L ∈ ℕ, L_max ∈ ℕ, k_max ∈ ℕ
Output: r̂_M ∈ ℝ^N, k_m, φ_m ∀m
1: m ← 0, r̂_0 ← 0 ▷ Initialization
2: r_0 ← arctan(ℑ{x} ⊘ ℜ{x}) ▷ Initialization
3: M ← ⌊L_max/L⌋ ▷ Initialization
4: while m < M do
5: r̃_m ← tan(r_m)
6: ℒ* ← arg max_{ℒ⊆𝒩,|ℒ|=L} ∑_{n∈ℒ}|r̃_m(n)| ▷ Eq. (13)
7: φ_m(n) ← { sign(r̃_m(n)), n ∈ ℒ*
0, otherwise } ▷ Eq. (14)
8: k_m ← ⌈−log₂((4/(3L))φ_m^T r̃_m)⌉ ▷ Eq. (16)
9: r̂_{m+1} ← r̂_m + arctan(2^{−k_m})φ_m ▷ Eq. (11)
10: r_{m+1} ← r_m − arctan(2^{−k_m})φ_m ▷ Eq. (10)
11: if k_m > k_max or ε < (r_{m+1}^T r_{m+1})/N then
12: M ← m
13: end if
14: m ← m + 1
15: end while
yielding,
Algorithm and Implementation Constraints
We propose Algorithm 2 as an MP for accurate rotation approximation (MPARA), summarized in the pseudocode.
Parameter Considerations
The algorithm requires four extra parameters, which are described as follows. (i) specifies the number of non-zero elements in the codewords; it determines how many elements are changed at each iteration. (ii) sets the maximum number of non-zero elements in the bit planes; it is a complexity constraint for the final inner product. For a rotation, each non-zero element is equivalent to 2 shifts and 2 additions. (iii) sets the maximum bit plane depth, or the maximum length of the bit shifts. (iv) sets a minimum approximation error for the total rotation on the vector.
Input Normalization
The input signal, is normalized to have elements of amplitude and phase . In preprocessing, we can normalize the amplitude and phase. Although amplitude normalization might add extra shift-and-add in the final implementation, phase normalization is achieved through trivial rotations of and requiring only signal inversions and changes between real and imaginary values.
This is mapped in the solution as rotations that require no extra additions.
Amplitude Correction
In CORDIC, the accumulated amplitude gain is calculated as
where is the accumulated amplitude gain. Although our proposition uses only a subset of the product in (17), the value remains bounded in . Because rotations in shallower bit planes incur larger amplitude gains, we set the shallowest bit plane to and propose the heuristic in Table 1 for amplitude correction.
| bit plane | Correction | Amplitude Gain |
| 0 | 0.9944 | |
| 1 | 0.9957 | |
| 2 | 0.9986 | |
Table 1. Heuristic for the amplitude gain correction.
Using a few supplementary shift-and-add operations when bit planes 0, 1, and 2 are active, significantly mitigates amplitude gain. In our proposition, we use no corrections in deeper bit planes, and the amplitude gain is limited to 1.0078 in the worst-case scenario, which is obtained by activating the depths . The proposed heuristic incurs a gain in the interval .
Results
Several FFT hardware designs exist [13], and each benefits from an optimization criterion; however, they still rely on twiddle-factor multiplications. We approximate the twiddle factors of a 256-point FFT. We use the radix-16 FFT for the 256-point FFT and the radix-4 for the 16-point FFT
where is a -point DFT matrix defined as
is the Kronecker product, is the identity matrix, is a vector containing the twiddle factors,
with as the radix and is a permutation matrix defined

(a) Average squared error outside the main diagonal.

(b) Average squared error in the main diagonal.
Figure 2. Study on the orthogonality of the transform.
We select in a binary search for minimal reconstruction phase error degradation, is variable so that the number of MR per element varies, and is fixed for a maximum bit shift of 6. We define
where is the approximated FFT matrix, and . The matrix should approach to maintain the transform’s property of orthogonality between frequencies. We define as
Figure 2a and Figure 2b present the mean squared error outside the main diagonal and on the main diagonal, respectively. These are calculated using the square of the Frobenius norm and averaged by . Our method better approximates the FFT than the other solutions. In our solution, the error increases with the number of additions because of additional MR allocated at bit planes of depth , which incur additional amplitude gain.
Conclusion
The paper proposes a greedy complex-valued vector approximation algorithm based on the phase shift, or rotation, of each element, enabling a multiplierless architecture. The MPARA algorithm is a vector approximation method that allocates MRs into elements that most minimize the phase error, yielding approximations with mixed-precision quantization in the phase domain. Our proposition outperforms the CSD and the MPGBP in the approximation of a radix-16 256-point FFT with radix-4 sub-decomposition of the butterflies.
References
References
- [1]Mikael Henriksson, Hugo Winbladh, and Oscar Gustafsson, “Multi-stream fft architectures for a distributed mimo large intelligent surfaces testbed,” in 2024 IEEE Nordic Circuits and Systems Conference (NorCAS), 2024, pp. 1–6.DOI
- [2]Cheolyong Bae and Oscar Gustafsson, “Architectural trade-offs for high-speed real-time chromatic dispersion compensation fir filters with time-multiplexed streaming ffts,” Journal of Lightwave Technology, vol. 43, no. 14, pp. 6744–6753, 2025.DOI
- [3]Bah-Hwee Gwee, Joseph S. Chang, Yiqiong Shi, Chien-Chung Chua, and Kwen-Siong Chong, “A low-voltage micropower asynchronous multiplier with shift–add multiplication approach,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 56, no. 7, pp. 1349–1359, 2009.DOI
- [4]Eduardo A. B. da Silva, Lisandro Livoloso, Alessandro J. S. Dutra, and Paulo S. R. Diniz, “Fir filter design based on successive approximation of vectors,” IEEE Transactions on Signal Processing, vol. 62, no. 15, pp. 3833–3848, 2014.DOI
- [5]R.I. Hartley, “Subexpression sharing in filters using canonic signed digit multipliers,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 43, no. 10, pp. 677–688, 1996.DOI
- [6]Ray Andraka, “A survey of cordic algorithms for fpga based computers,” in Proceedings of the 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays, New York, NY, USA, 1998, FPGA ’98, pp. 191–200, Association for Computing Machinery.DOI
- [7]Pramod K. Meher, Javier Valls, Tso-Bing Juang, K. Sridharan, and Koushik Maharatna, “50 years of cordic: Algorithms, architectures, and applications,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 56, no. 9, pp. 1893–1907, 2009.DOI
- [8]Mario Garrido, Fahad Qureshi, and Oscar Gustafsson, “Low-complexity multiplierless constant rotators based on combined coefficient selection and shift-and-add implementation (ccssi),” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 61, no. 7, pp. 2002–2012, 2014.DOI
- [9]Cheng-Shing Wu, An-Yeu Wu, and Chih-Hsiu Lin, “A high-performance/low-latency vector rotational cordic architecture based on extended elementary angle set and trellis-based searching schemes,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 50, no. 9, pp. 589–601, 2003.DOI
- [10]Mario Garrido, Daniel Medina, Pedro Paz, and Marisa López-Vallejo, “Uniformly distributed cordic,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 72, no. 11, pp. 6948–6961, 2025.DOI
- [11]Naveen Jones and M. Surya Prakash, “Sam-cordic: A scaling free accurate memoryless cordic for logarithm computation,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 73, no. 8, pp. 5501–5514, 2026.DOI
- [12]Chengyang Han, Jifeng Luo, Qianjian Xing, and Feng Yu, “Cordic-based computation of arcsine/arccosine integrated with prefix binary tree mapping,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 73, no. 5, pp. 593–597, 2026.DOI
- [13]Guang-Ting Deng, Mario Garrido, Sau-Gee Chen, and Shen-Jui Huang, “Radix-2 k msc fft architectures,” IEEE Access, vol. 11, pp. 81497–81510, 2023.DOI
