IEEE Signal Processing - March 2018 - 162

Tips & Tricks
Stephen So
and Kuldip K. Paliwal

Reconstruction of a Signal from the Real Part
of Its Discrete Fourier Transform

I

n this tutorial, we present a procedure
for reconstructing a complex-valued,
discrete-time signal from only partial
Fourier transform (FT) information,
more specifically, the real part of its discrete FT (RDFT). By applying a delay,
coupled with appropriate zero-padding
to ensure a sufficiently dense sampling of
the frequency axis, we show that any signal can be reconstructed perfectly from
the RDFT alone. The presented procedure can, in the case of a densely sampled
DFT, provide a reduction in the computational complexity of analysis-modification-synthesis-based speech processing
methods that independently process the
real and imaginary (RI) parts temporally.
Furthermore, the perfect reconstruction
property of this method implies that the
RDFT alone captures all of the information about the signal, which suggests that
it may be a potentially useful frequencyderived domain for the processing of
speech signals.

Introduction
Discrete-time signal reconstruction from
complete or partial frequency domain
information is a very common task in
digital signal processing. When referring to frequency domain information,
we mean in terms of the magnitude and
phase components, or RI parts that are
computed from the DFT of the signal.
By using the inverse DFT with appropriate zero-padding, a discrete-time signal
Digital Object Identifier 10.1109/MSP.2017.2771817
Date of publication: 7 March 2018

162

can be completely and uniquely determined, if both the magnitude and phase,
or similarly, both the RI parts at each
frequency sample are known.
Some previous literature has studied
signal reconstruction techniques from
partial FT information. Van Hove et al.
[1] showed that a one- or two-dimensional
signal can be uniquely specified by its FT
magnitude and limited (1-bit) FT phase
information. An iterative reconstruction algorithm was presented, where
the mean squared error of the reconstructed sequence decreased monotonically with each iteration, provided that
the "signed FT magnitude is densely
sampled in the frequency domain" [1].
Hayes et al. [2] developed a set of conditions for reconstruction (to within a scale
factor) of a discrete-time signal by using
only FT magnitude or phase. An iterative
reconstruction algorithm was presented
that utilized an M-point DFT. The authors
reported the total squared error was observed to monotonically decrease with
each iteration, as long as M $ 2N, where
N is the length of the discrete-time signal.
In this tutorial, we present a simple,
noniterative procedure for reconstructing a discrete-time signal using only
the RDFT. In contrast to the iterative
methods that reconstructed a discretetime signal using only FT magnitude
or phase [1]-[3], this procedure can
perfectly reconstruct the original signal, if appropriate zero-padding and
DFT sizes are used. This implies that
the RDFT captures all the information
about the signal.
IEEE Signal Processing Magazine

|

March 2018

|

Signal reconstruction
from the RDFT
RDFT reconstruction procedure
Let us assume an N-length discretetime complex-valued signal x (n), where
n = 0, 1, f, N - 1. An extended signal
xu (n) is created by first delaying x (n)
by one sample and padding a zero at the
beginning and then padding a sufficient
number of zeros at the end, to give it a
length of M $ 2N + 1
xu (n)
0,
for n = 0
= * x (n - 1), for n = 1, 2, f, N
.
0,
for n = N + 1, f, M - 1
(1)

[Zero-padding the first sample is only
required if x(n) is a complex-valued signal. If x(n) is real-valued, the zero at the
beginning is not necessary.]
An M-point discrete FT is performed
on this extended signal

Xu (k) =

M-1

/

xu (n) e -j2rnk/M,

n=0

for k = 0, 1, f, M - 1

(2)

where k is the frequency sample. The
complex DFT can be written as a sum of
RI parts, Xu R (k) and Xu I (k), respectively,
Xu (k) = Xu R (k) + jXu I (k) .

(3)

To reconstruct the signal using only the real
part Xu R (k), we first multiply it by a factor
of two and then take the inverse DFT
1053-5888/18©2018IEEE
Table of Contents for the Digital Edition of IEEE Signal Processing - March 2018
