Source-linked AI summary
32-point DFT Approximations Based on Minimal Frobenius Error and DFT Symmetries
L. Andrade-Silva, W. A. S. Aleixo, R. J. Cintra
TL;DR
The paper addresses the design of low-complexity, multiplierless approximations for the 32-point DFT. It minimizes Frobenius error over trivial multipliers using a row-wise, symmetry-constrained search reduction, and reports lower energy-based errors than the reference method with low arithmetic cost.
Problem
The paper seeks a 32-point DFT approximation that combines low error with low-complexity, multiplierless arithmetic.
Method
The method minimizes DFT-matrix error over trivial multipliers using row-wise greedy optimization and symmetry constraints to reduce the search space.
Results
71.2% reduction in total energy error and 47.3% reduction in MAPE are reported against the reference method.
Takeaways & Limitations
The approximation is presented as a candidate core block for low-complexity multiplierless statistical estimation and low-cost, low-power spectral-estimation hardware.
Takeaways & Limitations
The proposed approximation is not strictly orthogonal, although the paper discusses its deviation from orthogonality.
Abstract
from arXiv · showhide
This work introduces low-complexity, multiplierless approximations for the 32-point discrete Fourier transform. The proposed methods are obtained by minimizing the Frobenius error compared against the DFT matrix over a set of trivial multipliers. A row-wise, symmetry-constrained parameterization is employed to reduce the search space size, rendering the task computationally tractable. The resulting approximations could outperform the reference method in the literature according to energy-based error measurements. A sparse matrix factorization is provided for efficient computation; the arithmetic costs are 152 real additions and 34 bit-shifts only.
1 Introduction
The paper develops a competing 32-point DFT approximation over trivial multipliers, targeting low error, low arithmetic complexity, and preservation of relevant DFT properties. It uses the Villagrán–Cintra design as the reference baseline for comparison.
- A DFT approximation is designed to preserve relevant context-dependent properties of the exact DFT while reducing performance loss and arithmetic complexity.
- The study formulates approximation design as minimizing an application-linked error measure, including the Frobenius norm, between a candidate matrix and the DFT matrix.
- The Villagrán–Cintra approximation is selected as the reference method because it provides superior performance and has been mapped to dedicated beamforming hardware.
- The proposed work seeks a competing 32-point DFT approximation defined over trivial complex-valued multipliers.
2 Methodology
The methodology converts DFT approximation into an integer optimization problem and reduces its search through greedy, row-wise, symmetry-constrained parameterization. Candidate rows preserve DFT magnitude-group and sign patterns while using low-complexity multipliers.
- 2.1 Integer Optimization Problem: The polar function turns the search for a competing DFT approximation into integer optimization over a low-complexity matrix T.The resulting approximation is obtained from a near-orthogonalization procedure applied to T.
- 2.1 Integer Optimization Problem: Exhaustive search is computationally feasible only for small N, motivating greedy search to address the large optimization space.For N = 32, the search space is described as consisting of a very large number of candidate matrices.
- 2.2 Greedy Approach: The greedy approach decomposes the exact DFT into real and imaginary parts and independently approximates rows in a row-by-row manner.The real and imaginary components of each row are represented by vectors c_k and s_k, then replaced by low-complexity approximations.
- 2.3 Search Space Reduction: The search space is further reduced by parameterizing each row with vectors generated from the DFT row structure and trivial multipliers.The number of parameters is determined from the unique absolute-value patterns of the DFT matrix, using gcd and lcm relationships.
- 2.3 Search Space Reduction: DFT-consistent candidate vectors preserve equal absolute values and the sign pattern of corresponding exact DFT elements.These constraints are applied analogously to both the real and imaginary row components.
3 Results
For N = 32, symmetry and trivial-multiplier structure reduce the optimization to a tractable exhaustive search, yielding three related low-complexity DFT approximations and a sparse factorization.
- Rows k ∈ {0,8,16,24} require no approximation because their DFT entries are trivial multipliers ±1 and ±j.
- 211.30 × 10^3 candidate vectors make the minimization problems tractable by exhaustive search.
- The exhaustive-search solution is denoted T∗ and forms the proposed low-complexity matrix for the 32-point case.
- Three interrelated approximations are defined: raw, normalized, and standard.The raw form uses T∗ directly; normalization follows near-orthogonalization, while the standard form applies a scaling factor.
- The raw form suits unscaled spectral estimation, whereas the normalized form applies when a unitary DFT is required.
- T∗_32 admits a sparse-matrix factorization using inherited factors, diagonal matrices, permutation matrices, Kronecker products, and direct sums.Explicit numerical forms of the symbolic matrix terms are supplied in the Appendix for reproducibility.
4 Assessment and Comparison
The approximations are assessed against exact DFT variants and a literature baseline using energy, percentage-error, orthogonality, frequency-response, and arithmetic-complexity measures.
- Performance comparisons: The assessment compares proposed raw and standard forms with the exact DFT and baseline bF(0), while the normalized form is compared with the exact unitary DFT.
- Error measurements: The reported figures of merit are total energy error ε, mean absolute percentage error, and deviation from orthogonality δ.Measurements are taken relative to the relevant reference transforms.
- Frequency analysis: Rows k ∈ {0,8,16,24} of the exact DFT have null energy error because they consist of trivial multipliers.
- Frequency analysis: For the baseline approximation, the smallest nonzero row-wise energy error is 2.745 at k ≡ 4 (mod 8), while the largest is 4.019 for odd rows.Rows k = 4 and k = 1 represent the best and worst cases, respectively; other odd rows have the same error.
- Frequency analysis: Figure 1 compares magnitude and phase responses for best and worst cases of the raw, normalized, and standard approximations.
- Frequency analysis: Figure 2 compares exact and approximate frequency responses for baseline and proposed methods in best, average, and worst cases.Average curves are formed by means of centered individual responses or phase curves.
- Arithmetic complexity: The proposed factorization requires 152 real additions and 34 bit-shifts, compared with 144 real additions and no bit-shifts for bF(0)_32.Bit-shifts occur in D1, D2, D3, W9, W10, and W13.
5 Discussion
The proposed 32-point DFT approximations generally reduce energy-based and spectral errors relative to the baseline while retaining low arithmetic complexity. Their main limitation is a small deviation from strict orthogonality, and normalized performance depends on scaling conventions.
- Orthogonality: The approximation is not strictly orthogonal, but its deviation is small and essentially the same as the baseline method's deviation.This property supports considering it for applications where orthogonality is sought, including communications systems.
- Error Measurements: The raw approximation exhibits smaller energy error than the baseline for all rows in the row-wise analysis.It also offers very close performance to the standard DFT approximation.
- Frequency Response: The proposed approximations produce lower spectral leakage because their magnitude-response sidelobes are consistently closer to the exact DFT.Their phase responses also show close agreement with the exact phase plots and reduced spurious disturbances.
- Arithmetic Complexity: 152 real additions and 34 bit-shifts are required, keeping the proposed method close in arithmetic cost to the baseline.The factorization uses purely real intermediate matrix terms, with the final complex composition adding no arithmetic cost.
- Arithmetic Complexity: The proposed approximation can provide spectral estimation of real data without requiring complex arithmetic operations.Its factorization maps two real values to a complex output only at the final composition step.
- Arithmetic Complexity: The combined error-operation analysis reports 69.63% lower energy-error-operation and 44.37% lower MAPE-operation.These figures quantify the trade-off between approximation error and the number of required additions.
6 Conclusions
The proposed 32-point DFT approximation is presented as an alternative to the state-of-the-art design, with lower errors, better phase estimation, and only a small added arithmetic cost.
- 71.2% lower total energy error and 47.3% lower MAPE distinguish the proposed design from the reference method.
- The proposed approximation maintains a very small deviation from orthogonality.
- Eight extra additions deliver the reported error reductions relative to the reference design.
- Frequency-response phase plots indicate better phase-estimation properties for the proposed method.
- The approximation is presented as potentially favorable where an improved accuracy-complexity trade-off is desired.
A Explicit Numerical Form of the Sparse Factors
The paper provides the explicit numerical form of the sparse-factorization matrix for the proposed 32-point approximation.
- The explicit numerical factorization of the proposed 32-point approximation is provided below.