IEEE Menu Close
Publications lead hero image abstract pattern

Publications

Running Faster than Nyquist: An Idea Whose Time May Have Come

IEEE CTN
Written By:

Angelos D. Liveris, Microwave Networks Inc. and Costas N. Georghiades, Electrical and Computer Engineering at Texas A&M

Published: 14 Feb 2017

circuit

CTN Issue: February 2017

A note from the editor:

This month's story is about a fascinating idea that refused to die from the dawn of communications theory and that has recently come back due to shifting implementation constraints and the introduction of new complementary technologies. Like LDPC this topic was touched by some of the greats in our field who picked at it but then moved on. Always hanging in there over the decades it seems its time may have finally come. As Jack Sparrow might say, it turns out that Nyquist's limit is more of a guideline than a rule. I personally have been fascinated by this little fact for a long time and it is great to see it so beautifully summarized by Angelos and Costas. Comments most welcome as always.

Alan Gatherer, Editor-in-Chief

Faster-than-Nyquist Signaling: A Concept Whose Time has Come?

Angelos D. Liveris
Angelos D. Liveris

Angelos D. Liveris
Microwave Networks Inc.

Costas N. Georghiades
Costas N. Georghiades

Costas N. Georghiades
Electrical and Computer Engineering at Texas A&M

The signaling rate in a baseband digital communication system is the rate at which waveforms from a signal set are transmitted through some medium (the channel) to convey information. Clearly, the smallest number of signals in the signal set to convey non-zero information is two, where one of the signals is mapped into transmitting a 0 and the other is mapped into transmitting a 1. This is referred to as binary signaling, and in general we refer to M-ary signaling when the signal set contains M signals. A popular binary signal set which maximizes the distinction between the two signals, to combat noise in the channel for a given signal energy, is one which has a pulse and its negative. At the output of the channel, the receiver typically passes the received noisy signal through a filter, the output of which is sampled at the signaling rate and at the appropriate timing phase to produce a sequence of samples. These samples are then used to extract information by deciding whether the pulse or its negative (in the binary example here) was transmitted, producing a 0 or 1 accordingly. The filter which optimally processes the received noisy signal in the sense of ultimately resulting in the smallest probability of making a decision error, known as the matched-filter, has an impulse response which is a time-reversed version of the transmit pulse.

Besides achieving a small probability for a given transmit pulse energy, it is also important to transmit at a signaling rate which is as high as possible, under bandwidth constraints imposed by the channel. So, what prevents us to transmit at an as high a rate as we desire? The answer is because the bandlimited channel may distort the transmitted waveforms if the combination of pulse shape and signaling rate result in a transmit signal bandwidth larger than the channel bandwidth. This distortion may make it such that samples at the output of the matched-filter may be a function of not just one transmitted pulse but several neighboring ones. This is known as intersymbol-interference (ISI). According to the Nyquist theorem, the maximum signaling rate for ISI-free reception at the matched-filter output samples, known as the Nyquist rate, is twice the channel bandwidth measured in Hz [1], [2]. This is achieved with pulse-shapes which are strictly bandlimited to the channel bandwidth. For these pulses, when the signaling rate equals the Nyquist rate, each matched-filter sample depends on just one transmit pulse; as such, it contains all the information necessary to make a decision on whether a 0 or a 1 was transmitted by solely processing that sample, a process known as symbol-by-symbol decisions. The top plot in Fig. 1 shows a sequence of four binary-modulated strictly bandlimited sinc pulses at the Nyquist rate and the corresponding sampling instants that the receiver uses to process this sequence. The peak value of each pulse occurs at the zero crossings of the rest of the pulses and thus, each sample depends only on a single transmitted symbol.

To limit the bandwidth occupied by the transmit signal, a limited bandwidth pulse shape is used. In the case of the sinc pulse shape used in Fig. 1, the signal spectrum has the ideal strictly bandlimited square shape.

The Nyquist rate limitation on the signaling rate guarantees orthogonality at the receiver and results in simple receivers. However, it is not a fundamental limit in the sense that if the samples at the receiver become non-orthogonal by transmitting above the Nyquist rate, there may not be fundamental loss associated with it. The only immediate effect is the additional complexity at the receiver that now needs to deal with the interference between samples and must process sequences of samples to make decisions. In summary, one might say the Nyquist rate limitation is geared more toward receiver complexity reduction than fundamental performance loss. Notice the qualifications above with “may” and “might” in italics. There are limits to how fast faster-than Nyquist we can get away with without irrecoverable loss of information. But even if the signaling rate gains are not unlimited, any gain we can achieve nowadays with the spectrum scarcity is worthwhile.

The idea to exceed the Nyquist rate may have been conceived even before Landau’s paper [3] and Saltzberg’s paper [4], the first work we found including such discussion. The term “faster-than-Nyquist” signaling seems to have been first introduced by Lucky [5] in the context of decision-feedback-equalization. In the same decision-feedback context, a low complexity intersymbol-interference mitigation approach, Salz later showed the optimality of the Nyquist rate [6].

In 1975 James E. Mazo was the first to report potential faster-than-Nyquist gains [7]. Mazo himself later admitted to John B. Anderson that his faster-than-Nyquist research was “just a curiosity” [8]. Mazo’s investigation, as most of the preceding faster-than-Nyquist work, was motivated by an effort to increase the bit rate through the bandwidth limited voice-band telephone channel [7]. To understand Mazo’s surprising results, we will briefly provide some additional background.

CTN February 2017 Figure 1: Sequence of sinc pulses at the Nyquist rate (top) and at the 25% faster-than-Nyquist rate (bottom). The values of each pulse at the sampling instants is also shown in both cases.
Figure 1: Sequence of sinc pulses at the Nyquist rate (top) and at the 25% faster-than-Nyquist rate (bottom). The values of each pulse at the sampling instants is also shown in both cases.

When signaling faster than the Nyquist rate, the signal bandwidth, e.g., using the sinc pulse, does not change, but more PAM symbols are transmitted in the same time interval as shown in the bottom part of Fig. 1. In this case the receiver samples include interference from the other symbols in the sequence as the sampling instants in the bottom sequence Fig. 1 no longer correspond to the zero crossings of the neighboring pulses.

Faster-than-Nyquist signaling increases the number of symbols transmitted within the same time interval at the cost of a more complex receiver that has to mitigate the interference introduced between the transmitted symbols.

A common way to evaluate the effect of the interference introduced by faster-than-Nyquist signaling to the performance of the receiver is to find the minimum Euclidean distance between any two pairs of transmitted modulated pulse sequences. For so-called additive, white Gaussian noise channels, the Euclidean distance between between pulses in the binary signal set determines the error probability performance. Mazo [7] investigated the minimum distance of binary faster-than-Nyquist signaling and found that for the ideal sinc pulses the minimum Euclidean distance between any two binary modulated pulse sequences transmitted at a rate up to 25% higher than Nyquist was the same as the minimum distance of sequences transmitted at the Nyquist rate. Thus, if we design an optimal receiver which looks at sequences of matched-filter samples to make decisions on sequences of transmitted bits, it is possible to boost the bit rate by 25% at no performance loss and the only penalty is in higher receiver complexity. This 25% minimum distance limit is referred to as the Mazo limit in the faster-than-Nyquist literature and Mazo’s work was the first to show the faster-than-Nyquist signaling potential.

The minimum Euclidean distance between transmitted sequences is a method to evaluate the performance of maximum likelihood sequence detection and the intersymbol interference between symbols when signaling faster than the Nyquist rate was severe, theoretically infinite for the sinc pulse. At about the same time as Mazo’s paper, the Viterbi algorithm was being introduced for maximum likelihood intersymbol interference receivers [9], [10] and handling the severe faster-than-Nyquist intersymbol interference with a maximum likelihood receiver meant extremely high receiver complexity for that time.

In 1984 Foschini realized this complexity issue and showed that binary faster-than-Nyquist signaling of limited maximum likelihood receiver complexity could not outperform Nyquist-rate Quadrature Amplitude Modulation (QAM) at the same bit rate [11].

For several years after Foschini’s paper research activity related to faster-than-Nyquist signaling slowed down with a few exceptions. Partial response signaling was proposed as a way to avoid the maximum likelihood detection complexity of faster-than-Nyquist signaling [12], [13], [14] and alternative transmit and receive filters were optimized for different performance criteria [15], [16].

Meanwhile in the 1980s and in the 1990s two independent developments in the field of equalization of uncoded and coded systems introduced low complexity equalization methods of severe intersymbol interference. The first development was reduced complexity receivers with performance close to the maximum likelihood receivers, even with severe intersymbol interference [17], [18], [19]. The second development was the discovery of turbo codes [20] and the subsequent introduction of turbo equalization [21].

These developments were soon combined with faster-than-Nyquist signaling to show that uncoded and coded faster-than-Nyquist equalization could reach the Nyquist-rate performance with reasonable complexity [22], [23]. In addition, for coded faster-than-Nyquist signaling not only does the turbo equalization approach allow a reasonable complexity receiver but the intersymbol interference detector component of this receiver can even have lower complexity than the Viterbi-based approaches used for uncoded faster-than-Nyquist systems, as long as it takes into account all the intersymbol interference [24], [25].

With the receiver complexity under control, the next question in faster-than-Nyquist signaling systems was that of the achievable bandwidth efficiency, typically measured in bits/sec/Hz. Rusek and Anderson answered this question for the Gaussian input case and practical modulating pulses, such as the root raised cosine [26]. They proved that faster-than-Nyquist signaling achieves higher bandwidth efficiency than using the same modulating pulse at the Nyquist rate.

Another direction for practical applications of faster-than-Nyquist signaling, such as multiuser or dispersive systems both encountered in mobile communications, was its extension to multicarrier systems, a special case of which is orthogonal frequency-division multiplexing (OFDM). So far we have been talking about the time-based faster-than-Nyquist approach, also called “time-packing” in the literature, and this extends the concept to the packing carriers in frequency beyond the orthogonality limit.

The time-packing approach was first extended to frequency-packing in a multicarrier system [25], [27] and then to combined time and frequency packing approach [28]. This promised even higher bandwidth efficiency in terms of minimum Euclidean distance gains [29] and flexibility [30].

The time-based approaches for limited complexity receivers can also be extended to uncoded and coded time-frequency-packing systems by accounting for both the intersymbol interference in time and the intercarrier interference in frequency [24], [28], [29], [31].

In addition, due to lack of orthogonality in both time and frequency the pulse shape used does not have to meet either orthogonality constraint; for example, Gaussian pulses have also been used for time and frequency packing [29], [31].

Faster-than-Nyquist signaling in its time-frequency packing approach has been considered as one of the options for the 5G Standard Waveform [30] as an OFDM-based approach is preferred [32]. Fasterthan- Nyquist signaling is also considered for other spectrally efficient applications, such as satellite and optical communication systems [33].

Other directions of faster-than-Nyquist signaling have seen much research activity lately. Hardware implementations of frequency-packed and time-frequency-packed multicarrier systems have been reported recently [8], [25]. The study of faster-than-Nyquist signaling in multiple-input multiple-output (MIMO) channels, multiple access and broadcast systems is on-going [34], [35], [36]. In the MIMO case, apart from extending the time and frequency packing concepts to multiple antenna systems, the “space-packing” concept is currently under investigation in the context of massive MIMO systems [37]. This means that in the same physical space more transmit antennas are used by placing them closer than the minimum distance guaranteeing independent fading and investigating the tradeoff between the introduced transmit antenna correlation and the increased number of transmit antennas.

So, what does the future hold for faster-than-Nyquist signaling? No crystal ball, but two things seem certain to happen: 1) the pressure on spectrum availability will only increase in time with the many new wireless applications envisioned; and 2) processing power will keep growing. These two conditions mean techniques for achieving higher spectral efficiencies will become even more valuable and faster-than- Nyquist signaling is expected to be an active research area for the next few years in view of its spectral efficiency advantage.

Stepping back a bit, there may be broader lessons to be learned from the faster-than-Nyquist story, which began rather quietly several decades ago but is anything but today. What other preconceived notions do we harbor as communications researchers which limit our ability to built even more efficient communication systems?

References

  1. H. Nyquist, “Certain factors affecting telegraph speed,” Bell Syst. Tech. J., vol. 3, pp. 324–346, Apr. 1924.
  2. H. Nyquist, “Certain topics in telegraph transmission theory,” AIEE Trans., vol. 47, pp. 617–644, Apr. 1928.
  3. H.J. Landau, “Sampling, data transmission, and the Nyquist rate,” IEEE Proceedings, vol. 55, pp. 1701–1706, Oct. 1967.
  4. B.R. Saltzberg, “Intersymbol interference error bounds with application to ideal bandlimited signaling,” IEEE Trans. Inform. Theory, vol. IT-14, pp. 563–568, July 1968.
  5. R.W. Lucky, “Decision feedback and faster-than-Nyquist transmission,” in Proc. Int. Symp. Inform. Theory, June 1970.
  6. J. Salz, “Optimum mean-square decision feedback equalization,” Bell Syst. Tech. J., vol. 52, pp. 1341–1373, Oct. 1973.
  7. J.E. Mazo, “Faster-than-Nyquist signaling,” Bell Syst. Tech. J., vol. 54, pp. 1451–1462, Oct. 1975.
  8. D. Dasalukunte, V. Owall, F. Rusek, and J.B. Anderson, Faster than Nyquist Signaling: Algorithms to Silicon, Springer, 2014.
  9. G.D. Forney, “Maximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference,” IEEE Trans. Inform. Theory, vol. IT-18, pp. 363–378, May 1972.
  10. G. Ungerboeck, “Adaptive maximum-likelihood receiver for carrier-modulated data-transmission systems,” IEEE Trans. Commun., vol. COM-22, pp. 624–636, May 1974.
  11. G.J. Foschini, “Contrasting performance of faster binary signaling with QAM,” Bell Syst. Tech. J., vol. 63, pp. 1419–1445, Oct. 1984.
  12. K.T. Wu and K. Feher, “Multi-level PRS/QPRS above the Nyquist rate,” IEEE Trans. Commun., vol. COM-33, pp. 735–739, July 1985.
  13. A. Said and J.B. Anderson, “Bandwidth-efficient coded modulation with optimized linear partial-response signals,” IEEE Trans. Inform. Theory, vol. IT-44, pp. 701–713, Mar. 1998.
  14. A. Gatherer, “Increased bit rate of telephony modems using controlled intersymbol interference,” Jan. 1999, United States Patent 6,636,560.
  15. A. Fihel and H. Sari, “Performance of reduced-bandwidth 16 QAM with decision-feedback equalization,” IEEE Trans. Commun., vol. COM-35, pp. 715–723, July 1987.
  16. C. Wang and L. Lee, “Practically realizable digital transmission significantly below the Nyquist bandwidth,” IEEE Trans. Commun., vol. COM-43, pp. 166–169, Feb./Mar./Apr. 1995.
  17. J. Anderson and S. Mohan, “Sequential coding algorithms: A survey and cost analysis,” IEEE Trans. Commun., vol. 32, pp. 169–176, Feb. 1984.
  18. M.V. Eyuboglu and S.U.H. Qureshi, “Reduced-state sequence estimation with set partitioning and decision feedback,” IEEE Trans. Commun., vol. COM-36, pp. 13–20, Jan. 1988.
  19. A. Hafeez and W.E. Stark, “Decision feedback sequence estimation for unwhitened ISI channels with applications to multiuser detection,” IEEE J. Select. Areas Commun., vol. JSAC-16, pp. 1785–1795, Dec. 1998.
  20. C. Berrou, A. Glavieux, and P. Thitimajshima, “Near shannon limit error-correcting coding and decoding: Turbo-codes,” in Proc. ICC ’93, May 1993, vol. 2, pp. 1064–1070.
  21. C. Douillard, M. Jezequel, C. Berrou, A. Picart, P. Didier, and A. Glavieux, “Iterative correction of intersymbol interference: Turbo-equalization,” European Trans. Telecommun., vol. 6, pp. 507–511, Sept./Oct. 1995.
  22. A.D. Liveris and C.N. Georghiades, “Exploiting faster-than-Nyquist signaling,” IEEE Trans. Commun., vol. 51, pp. 1502–1511, Sept. 2003.
  23. F. Rusek and J.B. Anderson, “Non binary and precoded faster than Nyquist signaling,” IEEE Trans. Commun., vol. 56, pp. 808–817, May 2008.
  24. J.B. Anderson, F. Rusek, and V. Owall, “Faster-than-Nyquist signaling,” Proc. IEEE, vol. 101, pp. 1817–1830, Aug. 2013.
  25. W. Xiang, K. Zheng, and X. Shen (Editors), 5G Mobile Communications, Springer, 2017.
  26. F. Rusek and J.B. Anderson, “Constrained capacities for faster-than-Nyquist signaling,” IEEE Trans. Inform. Theory, vol. 55, pp. 764–775, Feb. 2009.
  27. M. Rodrigues and I. Darwazeh, “A spectrally efficient frequency division multiplexing based communication system,” in 8th International OFDM-Workshop, Hamburg, Germany, Sept. 2003, pp. 70–74.
  28. F. Rusek and J.B. Anderson, “The two dimensional Mazo limit,” in Proc. ISIT ’05, Sep. 2005, pp. 970–974.
  29. F. Rusek and J.B. Anderson, “Multistream faster than Nyquist signaling,” IEEE Trans. Commun., vol. 57, pp. 1329–1340, May 2009.
  30. P. Banelli, S. Buzzi, G. Colavolpe, A. Modenini, F. Rusek, and A. Ugolini, “Modulation formats and waveforms for 5G networks: Who will be the heir of OFDM?: An overview of alternative modulation schemes for improved spectral efficiency,” IEEE Sig. Proc. Mag., vol. 31, pp. 80–93, Nov. 2014.
  31. A. Barbieri, D. Fertonani, and G. Colavolpe, “Time-frequency packing for linear modulations: spectral efficiency and practical detection schemes,” IEEE Trans. Commun., vol. COM-57, pp. 2951–2959, Oct. 2009.
  32. C.J. Zhang, J. Ma, G.Y. Li, W. Yu, N. Jindal, Y. Kishiyama, and S. Parkvall (Editors), “New Waveforms for 5G Networks - Feature Topic,” IEEE Commun. Magazine, pp. 64–112, Nov. 2016.
  33. A. Modenini, F. Rusek, and G. Colavolpe, “Faster-than-Nyquist signaling for next generation communication architectures,” in 2014 Proc. 22nd Europ. Signal Proc. Conf. (EUSIPCO), Sept. 2014, pp. 1856–1860.
  34. F. Rusek, “On the existence of the Mazo-limit on MIMO channels,” IEEE Trans. Wireless Commun., vol. 8, pp. 1118–1121, Mar. 2009.
  35. Y. Feng and J. Bajcsy, “Improving throughput of faster-than-Nyquist signaling over Multiple-Access Channels,” in IEEE Veh. Tech. Conf. (VTC Spring), May 2015, pp. 1–5.
  36. Y.J.D. Kim, J. Bajcsy, and D. Vargas, “Faster-than-Nyquist broadcast in gaussian channels: Achievable rate regions and coding,” IEEE Trans. Commun., vol. 64, pp. 1016–1030, Mar. 2016.
  37. C. Masouros, M. Sellathurai, and T. Ratnarajah, “Large-scale MIMO transmitters in fixed physical spaces: The effect of transmit correlation and mutual coupling,” IEEE Trans. Commun., vol. 61, pp. 2794–2804, July 2013.

Statements and opinions given in a work published by the IEEE or the IEEE Communications Society are the expressions of the author(s). Responsibility for the content of published articles rests upon the authors(s), not IEEE nor the IEEE Communications Society.

Sign In to Comment