User:Cohere-OTFS/sandbox

Orthogonal Time Frequency Space (OTFS)

Orthogonal Time Frequency & Space (OTFS) is an innovative modulation scheme (air interface) that delivers a multi-dimensional characterization of the wireless channel to comprise a complete, continuous and reliable representation of the wireless channel.

OTFS’ two-dimensional (2D) modulation scheme modulates information (that is, QAM) symbols onto a set of 2D orthogonal basis function, which spans the bandwidth and time duration of the transmission burst or packet. This 2D modulation scheme transforms data carried in a delay-Doppler coordinate system to the familiar time-frequency domain that is utilized by traditional modulation schemes, such as OFDM, CDMA and TDMA. From a broader perspective, OTFS establishes a conceptual link between radar and communication. 

OTFS overcomes inherent issues of wireless communication far more effectively than current modulation schemes, such as TDMA and OFDM, to dramatically increase bandwidth and throughput. Since OTFS is a multi-dimensional scheme, it completely changes how a wireless channel is seen – from the transmitter to the receiver and everything in between. OTFS manages signal defraction, reflection and absorption inherent in wireless transmission to virtually eliminate signal fading, capacity loss, and other issues to ensure excellent signal reception throughout coverage areas while maximizing throughput.

OTFS method of transforming the time-varying multipath channel into a time-invariant delay-Doppler two-dimensional convolution channel helps eliminate the difficulties in tracking time-varying fading, for example in high speed vehicle communication. Moreover, OTFS increases the coherence time of the channel by orders of magnitude. It simplifies signaling over the channel using well studied AWGN codes over the average channel SNR (signal-to-noise ratio). More importantly, it enables linear scaling of throughput with the number of antennas in moving vehicle applications due to the inherently accurate and efficient estimation of channel state information (CSI). In addition, since the delay-Doppler channel representation is very compact, OTFS enables massive MIMO and beamforming with CSI at the transmitter for four, eight, and more antennas in moving vehicle applications. The CSI information needed in OTFS is a fraction of what is needed to track a time varying channel.

History

Since the introduction of cellphones, every transition to a new generation of wireless network involves a disruption in the underlying air interface. Starting with the transition from 2G networks based on single carrier GSM to 3G networks based on code division multiplexing (CDMA), then followed by the transition to contemporary 4G networks based on orthogonal frequency division multiplexing (OFDM).

The main motivation to introduce a new air interface is made when the demands of a new generation of wireless devices cannot be met by the current (legacy) technology. This can be because of performance, capabilities, and cost. For example, the demand for higher capacity data services drove the transition from interference-limited CDMA network (limited in flexibility to adapt and its inferior achievable throughput) to a network based on an orthogonal narrowband OFDM, which is optimally fit for opportunistic scheduling to achieve higher spectral efficiency.

Introduction

OTFS modulation scheme multiplexes QAM information symbols in a signal representation called delay-Doppler. In mathematical literature, the delay-Doppler representation is sometimes referred to as the lattice representation of the Heisenberg group. The structure was later rediscovered by physicists who refer to it as the Zak representation. Delay-Doppler representation generalizes time and frequency representations, rendering OTFS as a far-reaching generalization.

OTFS creates a waveform that optimally couples with the wireless channel to capture the physics of the channel. This yields a high-resolution delay-Doppler radar image of the constituent reflectors. This results in a simple symmetric coupling between the channel and the information carrying QAM symbols. The symmetry manifests itself through three fundamental properties:

• Invariance
• Separability
• Orthogonality

Invariance is the coupling pattern that is the same for all QAM symbols (that is, all symbols experience the same channel, or the coupling is a translation invariant). Separability (also known as, “hardening”) means that all diversity paths are separated from one another, which makes each QAM symbol experience all the diversity paths of the channel. Finally, orthogonality means that the coupling is localized, which implies that each QAM symbol remains roughly orthogonal to one another at the receiver. The orthogonality property should be contrasted with conventional PN (pseudonoise) sequence-based CDMA modulations, where every codeword introduces a global interference pattern that affects all the other codewords. The invariance property should be contrasted with TDM and FDM, where the coupling pattern vary significantly among different, time-frequency coherence intervals.

A variant of OTFS can be architected over an arbitrary multicarrier modulation scheme by means of a two-dimensional (symplectic) Fourier transform between a grid in the delay-Doppler plane and a grid in the reciprocal time-frequency plane. The Fourier relation creates a family of orthogonal 2D basis functions on the time-frequency grid, where each function can be viewed as a codeword that spreads over multiple tones and multiple multicarrier symbols. This interpretation renders OTFS as a time-frequency spreading technique that generalizes CDMA.

Key features

The following are the key features of OTFS:

OTFS Key Features

Attribute	OTFS Feature	Benefit	Application
Channel characteristics	Deterministic and stationary	Completely eliminates fading resulting in high SNR	Highest channel capacity and cell edge coverage achievable
Channel state acquisition	Accurate, efficient and timely	Granular control of energy per bit	Energy efficiency for IoT
Scalability	Wide-band, uniform, robust and stable spatial multiplexing	Uniform scaling of capacity with MIMO and channel bandwidth	100x – 1000x network capacity
Interference mitigation	Optimal spreading	Interference immunity	Massive MIMO Network densification
MAC	Maps to existing LTE MAC	Reuse existing MAC and higher layer platform	Logical evolution from LTE to OTFS
Network optimization	Distributed algorithm to achieve convergence	Manage addition/removal of nodes in the network	Efficient and robust capacity and coverage utilization

Background

To begin to understand OTFS, consider the foundation of signal processing, which at its core revolves around two basic signal principles: time and frequency representation. Using Fourier transform, these two representations are interchangeable and complement one another.

Specifically, if a signal is localized in time, then it is non-localized in frequency. Equivalently, if a signal is localized in frequency, then it is non-localized in time (shown in the following figure). This mathematical fact hides a deeper truth. As it turns out, there are signals that behave as if they are simultaneously localized to any desired degree both in time and in frequency; that is, a property that renders them optimal both for delay-Doppler radar multi-target detection and for wireless communication (two use cases are strongly linked).

• 

Delay-Doppler variables are commonly used in radar and communication theory. In radar, they are used to represent and then separate moving targets by both delay (range) and Doppler (velocity). In communication, they are used to represent channels by the superposition of time and the frequency of shift operations. The delay-Doppler channel representation is important in wireless communication, since it coincides with the delay-Doppler radar image of the constituent reflectors. The following figure shows an example of the delay-Doppler representation of a specific channel. It is composed of two main reflectors that share similar delay (range), but differ in their Doppler characteristic (velocities).

• 

The use of the delay-Doppler variables to represent channels is well known. However, what is less known is the fact that these variables can also be used to represent information-carrying signals in a way that is harmonious with the delay-Doppler representation of the channel. The delay-Doppler signal representation is mathematically subtler and requires the introduction of a new class of functions called quasiperiodic functions. Therefore, the delay period is represented by 𝜏_𝜏 and the Doppler period is 𝜈_𝜏 satisfying the condition 𝜏_𝜏 ∙ 𝜈_𝜏 = 1 and, thus, defining a box of unit area (as shown in the following figure). A delay-Doppler signal is a function of 𝜙 𝜏, 𝜐 that satisfies the following quasiperiodic condition:

𝜙 (𝜏 + 𝑛𝜏_𝜏, 𝜐 + 𝑚𝜐_𝜏) = 𝑒^j2π(nvr_r-mrv_r) 𝜙 (𝜏, 𝜐)

• 

In summary, there are three fundamental ways to represent a signal:

• A function of time
• A function of frequency
• A function of aquasi-periodic of delay-Doppler.

These three fundamentals are interchangeable by means of canonical transforms. The conversion between the time and frequency representations is carried through the Fourier transform. The conversion between delay-Doppler and the time-frequency representations is carried by the Zak transforms. The Zak transforms are realized by means of periodic Fourier integration formulas:

• 

Specifically, the Zak transform’s time representation is given by the inverse Fourier transform along a Doppler period; and (equally) the Zak transform’s frequency representation is given by the Fourier transform along a delay period. In addition, the quasi-periodicity condition is required for the Zak transform to be a one-to-one equivalence between functions on the one-dimensional line and on the two-dimensional plane. Without it, a signal on the line will admit (infinitely) many delay-Doppler representations.

• 

Signal Processing

The general framework of signal processing consists of three signal representations:

• Time
• Frequency
• Delay-Doppler

All three are interchangeable by means of canonical transforms. The setting can be organized in a form of a triangle, as shown in the following figure. The nodes of the triangle represent the three representations (time, frequency and delay-Doppler), and the edges represent the canonical transformation rules that converts them.

• 

It is important to note that in this diagram, any pair of transform is equal in that it traverses along the edges of the triangle and results in the same answer no matter of which path is chosen. As a result, one can write the Fourier transform as a composition of two Zak transforms:

FT = Z_t ° Z_f^–1

This means that instead of transforming from frequency to time using the Fourier transform, OTFS transforms from frequency to delay-Doppler using the inverse Zak transform (Z_f^–1), as well as from delay-Doppler to time using the Zak transform (Z_t). The above decomposition yields an alternative algorithm for computing the Fourier transform, which turns out to coincide with the fast Fourier transform algorithm discovered by Cooley-Tukey. This fact is an evidence that the delay-Doppler representation silently plays an important role in classical signal processing. Note that the delay-Doppler representation is not unique, but depends on a choice of a pair of periods (𝜏_r, 𝜐_r), which satisfies the relation: 𝜏_r∙ 𝜐_r = 1. This implies that there is a continuous family of delay-Doppler representations that correspond to points on the hyperbola 𝜐_r = 1/𝜏_r (shown in the following figure).

• 

Note what happens in the limits of the variable 𝜏_𝜏 → ∞ and the variable 𝜐_𝜏 → ∞. In the first limit, the delay period is extended at the expense of the Doppler period contracting; thus, converging in the limit to a one-dimensional representation coinciding with the time representation. Equally, in the second limit, the Doppler period is extended at the expense of the delay period contracting; thus, converging in the limit to a one-dimensional representation coinciding with the frequency representation.

Therefore, the time and frequency representations is a limiting case of the more general family of delay-Doppler representations. That is, all delay-Doppler representations are interchangeable by means of appropriately defined Zak transforms, which satisfies the commutativity relations generalizing the triangle relation. This means that the conversion between any pair of representations along the curve is independent of the polygonal path that connects them. Furthermore, the delay-Doppler representations and the associated Zak transforms constitute the building blocks of signal processing; in particular, to the classical notions of time and frequency and the associated Fourier transformation rule.

Modulation Scheme

Basically, communication theory is the transfer of information through two main physical media: wired and wireless. The method that couples a sequence of information-carrying QAM symbols with the communication channel is referred to as a modulation scheme. Thus, the channel-symbol coupling depends both on the physics of the channel and on the modulation carrier waveform. Consequently, every modulation scheme gives rise to a unique coupling pattern, which reflects the way the modulation waveforms interact with the channel.

The classical communication theory revolves around two basic modulation schemes, which are associated with the time and frequency signal representations. The first scheme multiplexes QAM symbols over localized pulses in the time representation called TDM (Time Division Multiplexing). The second scheme multiplexes QAM symbols over localized pulses in the frequency representation (and transmits them using the Fourier transform) called FDM (Frequency Division Multiplexing).

• 

When converting the TDM and FDM carrier pulses to the delay-Doppler representation using the respective inverse Zak transforms, the TDM pulse reveals a quasi-periodic function that is localized in delay, but non-localized in Doppler. Conversely, converting the FDM pulse reveals a quasi-periodic signal that is localized in Doppler, but non-localized in delay. The polarized, non-symmetric delay-Doppler representation of the TDM and FDM pulses suggests a superior modulation based on symmetrically localized signals in the delay-Doppler representation.

OTFS allows for an infinite number of corresponding modulation schemes to the different delay-Doppler representation, which are parameterized by points of the delay-Doppler curve. However, the traditional time and frequency modulation schemes (that is, TDMA and OFDM) appear as limiting cases of the OTFS family, when the delay-Doppler periods approach infinity. The OTFS family of modulation schemes smoothly interpolates between time and frequency division multiplexing.

Carrier Waveform

An explicit description of the OTFS carrier waveform as a function of time, consider a two-dimensional grid in the delay-Doppler plane as specified by the following parameters:

• 

This defined grid consists of an 𝑁 point along the delay period, with spacing Δ𝜏 and 𝑀 points along the Doppler period, with spacing 𝛥𝜐, resulting with a total of 𝑁𝑀 grid points inside the fundamental rectangular domain. Next, there is a localized pulse (𝑤_n,m) in the delay-Doppler representation at a specific grid point 𝑛Δ𝜏,𝑚Δ𝜐. In addition, a pulse is only localized inside the boundaries of the fundamental domain (enclosed by the delay-Doppler period), and will repeat itself quasi-periodically over the whole delay-Doppler plane (shown in the following figure) with 𝑛 = 3 and 𝑚 = 2. It is assumed that 𝑤_n,m is a product of two one-dimensional pulses:

W_n,m(𝜏,v) = W_r(r–nΔ𝜏) • w_v(v–nΔv)

where the first factor is localized along delay (time) and the second factor is localized along Doppler (frequency). In a sense, the delay-Doppler two-dimensional pulse is a stitching of the one-dimensional TDMA and OFDM pulses. To describe the structure of 𝑤3,8 in the time representation, we compute the Zak transform:

Z_t(W_n,m)

Using the Zak transform formula, a direct verification shows that the resulting waveform is a pulse train shifted in time and in frequency, where the shift in time is equal to the delay coordinate 𝑛𝛥𝜏, as well as the shift in frequency is equal to the Doppler coordinate 𝑚𝛥𝜈. Locally, the shape of each pulse is related to the delay pulse, 𝑤_𝜏. Globally, the shape of the total train is related to the Fourier transform of the Doppler pulse, 𝑤_v. Moving the grid point along delay causes each pulse in the train to shift along time by the same displacement, which makes it resemble TDMA. Equally, moving the grid point along Doppler causes a shift in frequency of the whole train by the same frequency displacement, which makes it resemble OFDM. Specifically, the local structure of the OTFS carrier waveform resembles TDMA, while the global structure resembles OFDM.

• 

Delay-Doppler Channel Symbol Coupling

The wireless channel is composed of a collection of specular reflectors, some static and some moving. The transmitted waveform propagates through the medium and bounces off each reflector. The signal that arrives at the receiver is a superposition of the direct signal and reflected echoes. Each of the reflected echoes arrives at the receiver at a delayed time (multipath effect) and (possibly) also the shift in frequency (Doppler effect) due to the relative velocity between the reflector and the transmitter/receiver. The channel physics is mathematically modeled through the delay-Doppler impulse response, where each tap represents a cluster of reflectors with specific delay and Doppler characteristics (as shown in the following figure).

• 

Transmitting a localized TDM pulse in the time representation notifies the receiver of a configuration of echoes that appear at specific time displacements and corresponds to the multipath delays imposed by the various reflectors. The phase and amplitude of each echo depends on the initial position of the transmitted pulse and might change significantly among different coherence time intervals – a phenomenon referred to as “time selectivity.” There are two mechanisms involved: the phase of the echo changes due to the Doppler effect and the amplitude of the echo changes due to destructive superposition of numerous reflectors sharing the same delay but differing in Doppler. This results in the inability of the TDM pulse to separate reflectors along Doppler. In the previous figure, when counting the TDM echoes (from left to right) note that the first and third echoes are due to static reflectors, thus are time invariant. The second echo is due to superposition of two reflectors, one of which is moving and therefore is fading. The fourth echo is due to moving reflector, thus is time varying. Equally, transmitting a localized FDM pulse in the frequency representation alerts the receiver to a configuration of echoes at specific frequency displacements that correspond to the Doppler shifts induced by the various reflectors. The phase and amplitude of each echo depends on the initial position of the transmitted pulse and might change significantly among different coherence frequency intervals – a phenomenon referred to as “frequency selectivity.” The phase of the echo changes due to the multipath effect, and the amplitude of the echo changes due to destructive superposition of numerous reflectors sharing the same Doppler, but differ in delay. This results in the inability of the FDM pulse to separate reflectors along delay. For example, in the above figure, counting the received FDM echoes (from bottom to up), note that the first and third echoes are frequency varying, and the second echo is due to superposition of three static reflectors, thus are fading.

• 

Transmitting a localized OTFS pulse in the delay-Doppler representation alerts the receiver to a configuration of echoes that appear at specific delay-Doppler displacements, which corresponds to the delay and Doppler shifts induced by the various reflectors (as shown in the above figure). In contrast to the previous two cases, the following properties now are valid:

• CSC invariance: the phase and amplitude of the delay-Doppler echoes are independent of the location of the original pulse inside the fundamental domain, since the delay and Doppler periods are smaller than the coherence time and bandwidth of the channel, respectively.
• CSC separability: all the reflections are separated from one another along their delay and Doppler characteristics; therefore, their effects do not add up destructively and there is no loss of energy on the QAM symbol level.
• CSC orthogonality: the received echoes are confined to a small rectangular box around the transmitted pulse with dimensions equal the delay and Doppler spread of the channel that are much smaller than the outer delay and Doppler period. As result, when two transmit pulses are geometrically separated at the transmitter, thus they remain orthogonal at the receiver.

Another way to express the OTFS channel-symbol coupling is as a two-dimensional convolution between the delay-Doppler impulse response and the QAM symbols. The following figure displays numerous delta functions (representing QAM symbols) convolved with the delay-Doppler impulse response of the channel.

• 

Multi-carrier Interpretations of OTFS

One variant of OTFS is more adaptive to the classical multicarrier formalism of time-frequency grids and filter-banks, which illuminates that is aspects of OTFS that are not apparent from the Zak definition. As a result of this definition, OTFS can be viewed as a time-frequency spreading scheme composed of a collection of two-dimensional basis-functions (or codewords) defined over a reciprocal time-frequency grid. Another result is that OTFS can be architected as a simple pre-processing step over an arbitrary multicarrier modulation, such as OFDM. This definition is based on Fourier duality relation between a grid in the delay-Doppler plane and a reciprocal grid in the time-frequency plane.

The delay-Doppler grid consists of 𝑁 points along delay with spacing 𝛥𝜏 = 𝜏_r/𝑁 and 𝑀 points along Doppler with spacing 𝛥𝜐= 𝜐_r/𝑀 and the reciprocal time-frequency grid consists of 𝑁 points along frequency with spacing 𝛥𝑓= 1/𝜏_r and 𝑀 points along time with spacing 𝛥𝑡= 1/𝜐_r (as shown in the figure below). The parameter 𝛥𝑡 is the multicarrier symbol duration, and the parameter 𝛥𝑓 is the subcarrier spacing. The time frequency grid can be interpreted as a sequence of 𝑀 multi-carrier symbols each consisting of 𝑁 tones or subcarriers. Note that the bandwidth of the transmission 𝐵= 𝑀𝛥𝑓 is inversely proportional to the delay resolution 𝛥𝜏, and the duration of the transmission 𝑇= 𝑀𝛥𝑡 is inversely proportional to the Doppler resolution 𝛥𝜏.

• 

The Fourier relation between the two grids is realized by a variant of the two-dimensional finite Fourier transform called the "Symplectic Finite Fourier Transform” (SFFT). SFFT sends an 𝑁×𝑀 delay-Doppler matrix 𝑥(𝑛Δ𝜏,𝑚Δ𝜐) to a reciprocal 𝑀×𝑁 time-frequency 𝑋(𝑚′Δ𝑡, 𝑛′Δ𝑓) via the following summation formula:

• 

where the term “symplectic” refers to the specific coupling form 𝑚′𝑚/𝑀− 𝑛′𝑛/𝑁 inside the exponent. Hence, the SFFT transform can easily be verified to be equivalent to an application of an 𝑁-dimensional FFT along the columns of the matrix 𝑥𝑛,𝑚 in conjunction with an 𝑀 dimensional IFFT along its rows. The multicarrier interpretation of OTFS is the statement that the Zak transform of an 𝑁×𝑀 delay-Doppler matrix can be computed alternatively by first transforming the matrix to the time frequency grid using the SFFT, and then transforming the resulting reciprocal matrix to the time domain as a sequence of 𝑀 multi-carrier symbols of size 𝑁 through a conventional multicarrier transmitter (for example, IFFT transform of the columns). Therefore, using the SFFT transform, the OTFS transceiver can be overlaid as a pre- and post-processing step over a multicarrier transceiver. The multicarrier transceiver of OTFS (as depicted in in the following figure) along with a visual representation of the doubly selective multiplicative CSC in the time-frequency domain and the corresponding invariant convolutive delay-Doppler CSC.

• 

The multi-carrier interpretation casts OTFS as a time-frequency spreading technique where each delay-Doppler QAM symbol 𝑥(𝑛Δ𝜏,𝑚Δ𝜐) is carried over a two-dimensional spreading ‘code’ or sequence on the time-frequency grid, given by the following symplectic exponential function:

• 

where the slope of this function along time is given by the Doppler coordinate 𝑚Δ𝜐 and the slope along frequency is given by the delay coordinate nΔτ (see the examples in the following figure). Thus, the analogy to two dimensional CDMA is seen, where the codewords are 2D complex exponentials that are orthogonal to each other.

• 

From a broader perspective, the Fourier duality relation between the delay-Doppler grid and the time-frequency grid establishes a mathematical link between Radar and communication, where the first theory is concerned with maximizing the resolution of separation between reflectors/targets (according to their delay-Doppler characteristics). In addition, the second is concerned with maximizing the amount of information that can be reliably transmitted through the communication channel composed of these reflectors.

Summary

OTFS is a novel family modulation scheme based on multiplexing the QAM information symbols over localized pulses in the delay-Doppler signal representation. The OTFS modulation schemes constitute a far-reaching generalization of traditional time and frequency modulation schemes such as TDMA and OFDM, which can be shown to be limiting cases of the OTFS family.

From a broader perspective, OTFS establishes a conceptual link between Radar and communication. The OTFS waveforms couple with the wireless channel in a way that directly captures the underlying physics, yielding a high-resolution delay-Doppler radar image of the constituent reflectors. Thus, the time-frequency selective channel is converted into an invariant, separable and orthogonal interaction, where all received QAM symbols experience the same localized impairment and all the delay-Doppler diversity branches are coherently combined.

The OTFS channel-symbol coupling allow linear scaling of capacity with the MIMO order while satisfying an optimal performance-complexity tradeoff both at the receiver end (using joint ML detection) and at the transmitter end (using Tomlinson-Harashima precode for MU-MIMO). OTFS enables significant spectral efficiency advantages in high order MIMO under general channel conditions over traditional modulation schemes including multicarrier modulations such as OFDM.

OTFS can be viewed as a special type of a time-frequency spreading technique, where each QAM symbol is carried by a two-dimensional basis function spread over the full time-frequency grid. When viewed as a time-frequency spreading technique, OTFS exhibits architectural compatibility with any type of multicarrier modulation scheme, including conventional OFDM. An OTFS packet can be flexibly designed to populate arbitrary regions of the time-frequency grid and be compatible with any convention for channel reference signaling. As a spread spectrum, OTFS enjoys resilience to narrowband interference and full diversity gain.

OTFS resilience to interference makes it ideal to supporting ultra-reliable low latency communication packets overlaid on regular data packets. OTFS diversity gain makes it ideal for communication under mobility conditions. OTFS supports a small packet allocation method (called Doppler transversal allocation) that maximizes link budget and minimizes number of retransmissions under transmit power and latency constraints by achieving the PAPR of single carrier, extracting full time-frequency diversity and maximizing restricted capacity. OTFS, with Doppler transversal allocation, is superior to conventional multicarrier DFT spread techniques such as SC-FDMA and its more elaborate hopped variant for applications of IoT.

3GPP has identified a variety of eMBB deployment scenarios that focus on MU-MIMO. The advantage of OTFS in scaling capacity with the MIMO order makes it ideal for these kinds of deployments. In addition, the new radio air interface must support high spectral efficiency in high Doppler environments. OTFS is ideally suited for these requirements, providing: high spectral efficiency and reliability under diverse channel conditions.

References

Low-Complexity Iterative Detection for Orthogonal Time Frequency Space Modulation