The DFT of Finite-Length Time-Reversed Sequences

Recently I've been reading papers on underwater acoustic communications systems and this caused me to investigate the frequency-domain effects of time-reversal of time-domain sequences. I created this blog because there is so little coverage of this topic in the literature of DSP.

The Two Types of Time-Reversal in DSP

In DSP the two types of finite-length sequence time-reversal are (1) what I call "Flip Time-Reversal", and (2) "Circular Time-Reversal." Figure 1 shows the two types of time-reversal of a six-sample x[n] time sequence.

Appendix A presents a review of Circular Time-Reversal and explains why the word circular is used.

The DFT of Finite-Length Time-Reversed Sequences

Here I present the principal information of this blog in the form of two tables, followed by the definitions of the algebraic notation used in those tables.

The DFTs of Flip Time-Reversed real‑ and complex‑valued time sequences are listed in Table 1.

The key characteristic of Flip Time-Reversal is the e^j2pm/N linear phase shift term in Eqs. (1), (2), and (3). The derivations of Eqs. (1) and (2) are given in Appendix B.

The DFTs of Circular Time-Reversed real‑ and complex‑valued time sequences are listed in Table 2.

The derivations of Table 1's Eq. (3) and Table 2's Eqs. (4), (5), and (6) are given in References [1‑3].

The Notation Used In Tables 1 and 2

The DFT of an arbitrary N-length x[n] time sequence is

where n is the time-domain integer index and m is the frequency-domain integer index. Both n and m are in the range 0, 1, 2, ..., N-1.

The algebraic notation for Flip Time Reversal of an x[n] time sequence is:

An example of Eq. (8) is the sequence in Figure 1(b).

In the literature of DSP I encountered four different algebraic notations for Circular Time Reversal. The notation I choose to use here is:

where

An example of Eq. (10) is the sequence in Figure 1(c). The  x[<N-m>] notation in Eqs. (9) and (10) is modulo N arithmetic notation because typical algebraic derivations of time-reversed sequences require modulo N arithmetic as demonstrated in Appendix B.

Why We Care About Time-Reversal

Regarding the two types of finite-length sequence time-reversal, we encounter Flip Time-Reversal when we:

We encounter Circular Time-Reversal when we:

Conclusion

To provide a more complete description than was currently available in one place, I've presented the two types of time-reversal of finite-length real‑ and complex‑valued sequences, and tabulated their DFT frequency-domain characteristics in Table 1 and Table 2.

Finally, I listed the instances in which we may encounter time-reversal in the field of DSP.

References

[1] S. Mitra, "Digital Signal Processing", Fourth Edition, McGraw Hill Publishing, 2011, pp. 56, 211.

[2] R. Lyons, "Understanding Digital Signal Processing", Third Edition, Prentice Hall, Upper Saddle River, New Jersey, 1996, pp. 863-865.

[3] J. Proakis and D. Manolakis, "Digital Signal Processing-Principles, Algorithms, and Applications", Third Edition, Prentice Hall, Upper Saddle River, New Jersey, 1996, pp. 421.

Appendix A: A Brief Review of Circular Time-Reversal

In this appendix we explain why the word "circular" is used in the phrase Circular Time-Reversal. In the early days of DSP while studying the symmetric behavior of the FFT, the practitioners encountered sequences that we now call "circular time-reversed" sequences.

As an example, if

    x[n] = x[0], x[1], x[2], x[3], x[4], x[5]

the DFT of x[n] is a complex-valued X[m]. If we conjugate X[m] and compute its inverse DFT we obtain the following circularly-reversed y[n] time sequence:

    Inverse DFT of X[m]* = y[n] = x[0], x[5], x[4], x[3], x[2], x[1].

Because all DFT operations are done over an indexing domain that is circular, we can depict the x[n] and y[n] sequences in a circular fashion as shown in Figure A-1. In Figure A-1(a), starting with x[0], we write the x[n] sequence counter clockwise (positive time) around a circle. In Figure A-1(b) we read the y[n] values, starting with x[0], going clockwise (negative time) around the circle.

Thus we refer to y[n] as a circular reversed version of sequence x[n]. The sequences in Figure A-1 correspond to the sequences in this blog's Figures 1(a) and 1(c).

Appendix B: Derivations of Eqs. (1) and (2)

Here we derive this blog's Eqs. (1) and (2). First, consider an N-sample discrete signal x[n], be it real- or complex-valued, having X[m] as its DFT as:

Next let's think about a Flip Time-Reversed x[N‑n‑1] sequence whose N-point DFT, X_FTR[m], is:

We wish to find a closed-form expression for X_FTR[m] that does not use a summation. If we change Eq. (B‑2)'s time indexing by letting p = N‑n‑1, then in terms of p, n = N‑p-1. Substituting p for N‑n‑1, and N-p‑1 for n, in Eq. (B‑2) we now have:

Note that sequence x[p], for 0≤p≤N-1, in Eq. (B‑3) is equal to the original non-reversed x[n] sequence. By factoring Eq. (B‑3) we can write:

In Eq. (B‑4) the first factor in brackets is equal to one for all m, and the last factor in brackets is not a function of p so we move it outside the summation to write:

Because the summation in Eq. (B‑5) is an N-point DFT with negative frequency indexing (‑m), we rewrite that equation as:

Recall that all DFT operations are done over an indexing domain that is circular. When the negative-m indexing in Eq. (B‑6) is interpreted in a circular fashion using modulo N arithmetic, X[‑m] mod N in Eq. (B‑6) is equal to x[<N-m>] enabling us to write:

verifying Table 1's Eq. (2) when x[n] is complex-valued.

Due to the symmetry of the DFT of real-valued sequences, if x[n] is real-valued then Eq. (B‑7) becomes:

verifying Table 1's Eq. (1).

Sign in