Binary Signal Perfect Recovery From Partial DFT Coefficients
Journal
IEEE Transactions on Signal Processing
Journal Volume
70
Pages
3848
Date Issued
2022-01-01
Author(s)
Chang, Kuo Wei
Abstract
How to perfectly recover a binary signal from its discrete Fourier transform (DFT) coefficients is studied. The theoretic lower bound and a practical recovery strategy are derived and developed. The concept of ambiguity pair is introduced. This pair of signals has almost the same DFT coefficients except for some positions. It can prove that when the signal length is N, then at least τ (N) DFT coefficients must be sampled, where τ (N) is the number of factors of the signal length N. A recovery algorithm is proposed and implemented. It can achieve the lowed bound for length N=2m, m ≤ 6. To overcome the length limitation problem, a more practical recovery method is also proposed and implemented for N=2m, m>6. We can sample 11% of the total DFT coefficients to perfectly recover the binary signal. We also extend the concept of ambiguity pair to other discrete transforms (DCT and WHT) and two-dimensional DFT cases.
Subjects
2D-DFT | binary reconstruction | DCT | DFT | number theory | WHT
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Type
journal article