Low-Complexity Detection of Multiple Preambles in the Presence of Mobility and Delay Spread

Current wireless infrastructure is optimized to support applications such as music/video streaming and internet browsing, where information flows from the base station to the user. This paper anticipates the emergence of applications such as distributed machine learning and automated driving, resulting in a shift of engineering focus from downlink to uplink as users become significant sources of data. The current paradigm of scheduling users on reserved uplink resources (grants) is not able to deal efficiently with unpredictable traffic patterns. As a result, Release 15, 3GPP introduced the 2 -step RACH as a mechanism to enable grant-free (random) initial access. The first of the two steps is preamble detection in a RACH slot, and in this paper we describe a very low-complexity algorithm for simultaneous detection of multiple preambles in the presence of mobility and delay spread. We provide a pathway to standards adoption by choosing Zadoff-Chu (ZC) sequences as preambles, taking advantage of the fact that ZC sequences already appear in 5G standards. We construct preambles by using the discrete Zak transform to pass from a ZC sequence of length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M N$</tex> in the time domain (TD) to a quasi-periodic <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M \times N$</tex> array in the delay-Doppler (DD) domain. There are <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M N$</tex> quasi-periodic Dirac pulses, each corresponding to a Zak-OTFS carrier waveform, and the ZC preamble is simply the corresponding sum of Zak-OTFS carrier waveforms. We detect multiple preambles in the presence of mobility and delay spread by sampling the received signal on the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M \times N$</tex> period grid in the DD domain. We approach detection as a compressed sensing problem. We represent a preamble as a column of length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M N$</tex> in the DD domain and apply discrete shifts in delay and Doppler to produce a block with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(M N)$</tex> columns in the compressed sensing matrix. The superposition of multiple preambles determines a block sparse sum of columns in the sensing matrix. The correlation properties of ZC sequences result in a highly structured compressed sensing matrix, making it possible to identify constituent preambles using One-Step Thresholding (OST), which has complexity <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}\left(M^{3} N^{3}\right)$</tex>. In this paper, we describe an algorithm with complexity that is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}\left(M^{2} N^{2}\right)$</tex> in the size of an individual column (<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M N$</tex>).