Frequency Permutations
for Joint Radar and Communications

The main challenge in developing such a joint system lies in finding a new waveform that is capable of simultaneously transmitting information and performing radar sensing. Existing literature proposes several new techniques to achieve this convergence. In [4, 5, 6], excellent reviews of joint radar and communication techniques are provided.

Several papers have proposed communication-centric designs in which traditional communication waveforms are exploited for radar sensing purposes. In [8], a new waveform suitable for long-range radar (LRR) is proposed based on the IEEE 802.11ad-based waveform which is traditionally used for wireless local area networks (WLANs). The special structure of repeated Golay sequences in the preamble of the 802.11ad-based waveform, which has good correlation properties, is exploited to estimate the radar parameters. In [12], the IEEE 802.11p waveform, which is used for dedicated short-range communication (DSRC) in vehicles, is considered for radar range estimation of the closest target. The paper also presents an alternative to forward collision detection in vehicles based on the communication waveform. In [13], new algorithms based on wireless communication standards such as IEEE 802.11ad and IEEE 802.11p have been proposed for radar range and velocity estimation.

Orthogonal frequency division multiplexing (OFDM) waveforms, which incorporate frequency diversity, have also been proposed in [14, 15, 16], where the target range and Doppler is extracted from the reflected OFDM signal. The OFDM waveform also has similarities to phase coded radar. However, due to the addition of subcarrier components it introduces a high peak-to-average power ratio (PAPR) which is problematic in typical radar operation as it requires power amplifiers with a large linear range. While some attempt has been made to improve this by randomizing the carrier phase and amplitude [17], the transmit power amplifier is not used efficiently from a radar perspective. Some papers have proposed the use of cyclic prefixed orthogonal frequency division multiplexing (CP-OFDM) which has limitations involving the length of the cyclic prefix [18]. Similar to OFDM, spread spectrum waveforms such as direct sequence spread spectrum (DSSS) have also been proposed for joint radar and communications systems [19].

From the opposite perspective, several papers have focused on using conventional radar waveforms for joint radar and communication purposes. In [20, 21], pulse position modulation and pulse amplitude modulation are considered to embed data in pulsed radar signals. The popular linear frequency modulated (LFM) waveform is considered in [22], where separate up and down chirps are used for radar and communication pulses, respectively. In this work, communication data rates are further enhanced by using $\pi/4$-Differential Quadrature Phase Shift Keying (DQPSK) modulation. The LFM waveform is also considered in [23], resulting in a low communication symbol rate that corresponds only to the chirp rate. Recently, a chirp-based $M$-ary Frequency Shift Keying (chirp-$M$-FSK) modulation method has been proposed in [24], together with the frequency modulated continuous wave (FMCW) radar waveform. Embedding data into traditional radar waveforms is challenging due to the lack of randomness in the available parameters. Also, when adjusting waveform parameters it is important to make sure radar performance is not compromised. None of the above works characterise the effect of embedding data on the radar performance in-terms of key analytical tools in radar waveform design such as the ambiguity function and the Fisher information matrix. As such, analysis of the behavior of new waveforms under important phenomena such as radar clutter is lacking.

In this paper, we focus on the stepped frequency radar waveform, which, to the best of our knowledge, has not been considered for this joint operation before, and propose a new method to randomize the frequency tones to modulate data. In order to make the paper complete and clearly readable to both the communications and radar communities we have conducted a rigorous analytical investigation on a number of important performance measures. While some of these measures are considered in the literature they are not always rigorously developed. We hope that the level of detail presented here is helpful and valuable to the reader.

Radar waveforms consisting of a sequence of step changes in frequency are popular in many radar applications and are being used extensively in the emerging automotive radar application [25, 26, 27]. In a stepped frequency waveform, the available bandwidth is divided into equally spaced frequency tones separated by a constant step $\Delta f$ Hz. The most common stepped frequency waveform employs a linear stepping pattern where the frequency of each pulse is increased by $\Delta f$ from the preceding pulse [28]. Costas codes, on the other hand, arrange the frequency tones according to a special sequence that results in an extremely good radar waveform with zero side-lobes [29]. However, the number of available Costas codes are limited and it does not provide enough randomization to be used in a joint radar communication system. Interestingly, in [25, 26], a pseudo random stepped frequency radar is considered where the transmitted waveforms consist of a train of short tones with frequencies defined according to a pseudo-random sequence. The randomization in the sequence of tones appears to be more suitable for the automotive radar application as it can significantly reduce the interference arising from a large number of radars operating in close proximity [25].

In this paper, we exploit this randomization in frequency to send data. We focus on a random stepped frequency radar waveform based on Lehmer codes, in which the transmitted waveform consists of a train of short tones with frequencies defined according to a permutation of the sequence of tones. As such, a set of $M$ frequency tones generates $M!$ different waveforms - all suitable for typical radar applications. These waveforms also maintain a constant amplitude resulting in a PAPR of unity which is ideally suited to radar operation. Our novel contributions are detailed as follows:

• •

  We propose a novel joint radar and communication technique in which the incoming data is modulated based on the selection of the frequency permutation in the transmitted waveform. We provide an efficient implementation for the mapping between the incoming data and the corresponding waveform based on a combinatorial transform called the Lehmer code.

• •

  From a communication perspective, we consider optimum maximum likelihood (ML) detection and analyse the baseband communication in additive white Gaussian noise (AWGN) channels to provide a union bound and a nearest neighbour approximation on the block error probability of the proposed signaling scheme. Then, we extend the analysis to consider Rician fading and provide closed-form analytical expression for the same performance measures. The Rayleigh channel model is also considered as a special case.

• •

  We provide an efficient communication receiver implementation based on the Hungarian algorithm which always results in the optimum solution. Compared to the exhaustive search which has a time complexity of $O(M!)$, the Hungarian algorithm has a worst case complexity of $O(M^{3})$, where $M$ is the number of frequency tones in the waveform.

• •

  From a radar perspective, we derive the ambiguity function and the Fisher information matrix of the proposed waveform. Based on the ambiguity function, we analyse the behavior of the waveform in relation to the matched filter output and provide a detailed discussion on the overall structure of the ambiguity function. Based on the Fisher information matrix we derive approximate Cramer-Rao Lower Bounds (CRLBs) on the delay and Doppler estimation error and illustrate the effect of different parameters on radar range and Doppler resolution.

Numerical examples are provided to support the discussion and also to illustrate the accuracy of the analysis. The remainder of the paper is organized as follows. In Section II, the system model and the waveform of the novel joint radar and communications system are described. The communication and radar performance of the Lehmer code based random stepped frequency radar waveform is analysed in Section III and IV, respectively. Simulation results are provided in Section V with conclusions and future research directions provided in Section VI.

Consider the system model illustrated in Fig. 1, where the transmitter sends a joint waveform for both communication and radar systems. The return signal from the radar target is received and processed by the radar receiver to estimate the range and the velocity of the target. The signal received at the communications receiver, which is equipped with multiple antennas, is processed to detect the transmitted information.

Consider $M$ equally spaced frequency tones $f_{0},f_{1},\ldots,f_{M-1}$. Based on the fact that there are $M!$ permutations of this sequence of $M$ frequencies we formulate $M!$ stepped frequency radar waveforms. In each waveform a given frequency is used only once. As illustrated in Fig. 2, the $i$-th waveform is generated using $M$ pulses, each $T$ seconds long and, the frequencies follow the $i$-th permutation of the set of $M!$ permutations with $f^{i}_{m}$ denoting the $m$-th frequency of the $i$-th permutation. As such, the complex baseband representation of the $i$-th waveform is given by

where

$T$ denotes the pulse duration and $E$ is the signal energy satisfying

We also assume that the frequencies are orthogonal. Thus, the separation between two frequency tones $\Delta f=n/T$, where $n$ is an integer. Since all frequencies are permutations of the $M$ frequency tones, the set of $M!$ sequences are given by

We note that all $M!$ waveforms generated by the above permutations maintain a constant amplitude. This, in contrast to OFDM, results in a PAPR of unity which is suitable for typical radar operation. Moreover, these waveforms maintain a short individual pulse width $T$ which results in good delay resolution. A good Doppler resolution is obtained by changing the frequency from one pulse to another, thus, utilizing a total bandwidth of $M\Delta f$ when considering the waveform as a whole. Due to the randomness in frequency, all $M!$ waveforms generated by the permutations are suitable for the automotive radar application [27]. We embed data in the selection of the waveform by maintaining a direct mapping between the data symbol and the selected waveform. In other words, we take $\log_{2}{M!}$ number of bits and depending on the symbol it represents, select the waveform to be transmitted.

Since we have $M!$ possible waveforms, one could argue that for large $M$, the implementation of the mapping between incoming data and the corresponding waveform may not be practical as it requires a large lookup table. However, it is important to identify that the the use of a lookup table is unnecessary for the implementation of the proposed signaling scheme. The mapping between incoming data and the corresponding waveform can be efficiently implemented using a combinatorial transform called the Lehmer code [30]. With Lehmer codes, we first present the natural number of the incoming data symbol in the factorial number system, which is also known as the factoradic form. Then, we exploit the natural mapping between the integers $0,1,\ldots,M!-1$ and permutations of $M$ elements in lexicographic order to map incoming data to a unique permutation of frequency tones [31]. At the communications receiver, a similar decoding procedure is followed to map the detected permutation of frequency tones to the corresponding data symbol. This procedure is a straightforward mapping between integers and permutations and can be efficiently implemented as it only involves simple operations such as selection from a sequence and deletion from it. For more details on mapping and demapping using Lehmer codes please refer to [31].

Consider a communication receiver with $N$ receive antennas. The $N\times 1$ complex baseband received signal vector is given by

where $\mathbf{h}$ is the small-scale fading channel vector, $s_{i}(t)\in\{s_{1}(t),s_{2}(t),\ldots,s_{M!}(t)\}$ is one of the $M!$ possible waveforms bearing transmit data and $\mathbf{n}(t)$ is an AWGN vector where each element is complex Gaussian with zero mean and variance $N_{0}$.

Assuming that the channel vector $\mathbf{h}$ is known at the receiver, we consider a coherent ML detector and write write the detected symbol as

Using some straight forward mathematical manipulations, the ML detection rule in (6) can be reexpressed as

where $\textrm{Re}(.)$ denotes the real part of the argument.

Consider the hypothesis that $s_{i}(t)$, which corresponds to the the $i$-th sequence, is being transmitted. The sequence is correctly detected if $\hat{s}_{i}(t)={s}_{i}(t)$. Thus, the probability of a correct decision is given by

where

denotes the decision variable. The transmitted data is assumed to be equally likely. Thus, the a priori probabilities of the $M!$ sequences are $1/M!$, and the error probability performance of the sequence can be defined based on a block error rate as

The exact expression of $P_{e}$ requires complex multi-dimensional integrals over the multivariate Gaussian density. These integrals cannot be computed in closed-form. Thus, we take a more tractable approach by considering the union bound which is given by

where $P_{ik}$ denotes the pairwise error probability of detecting the $k$-th sequence when the $i$-th sequence is transmitted. Please note that while the union bound is commonly used in literature, its derivation in the present context is not straight forward as we consider an unconventional method of modulating data based on the frequency permutation. Let $!x$, given by

denote the number of derangments of an $x$-element set [32]. By analysing the $M!$ permutations of the sequence of $M$ frequency tones we note that we have $!l\binom{M}{M-l}$ pairwise error probabilities where the frequency tones differ by $l$ positions. Using this observation and considering the symmetry in pairwise error probabilities, we can further simplify (10) as

where $k_{l}\in\{1,2,\ldots,M\}$ is such that $\psi_{1}$ and $\psi_{k_{l}}$, which are the frequency sequences used to generate $s_{1}(t)$ and $s_{k_{l}}(t)$, respectively, differ by $l$ frequency tones. Next we proceed to derive $P_{1k_{l}}$ which is the probability of detecting $s_{k_{l}}(t)$ when $s_{1}(t)$ is transmitted. Using the ML detection rule we can write $P_{1k_{l}}$ as

Using some mathematical manipulations (13) can be reexpressed as

where $N_{1}=\textrm{Re}\left(\mathbf{h}^{H}\int_{0}^{MT}{s}^{*}_{1}(t)\mathbf{n}(t)dt\right)$ and $N_{2}=\textrm{Re}\left(\mathbf{h}^{H}\int_{0}^{MT}{s}^{*}_{k_{l}}(t)\mathbf{n}(t)dt\right)$. When conditioned on channel fading, $N_{2}-N_{1}$ has a Gaussian distribution with zero mean and variance $\frac{ElN_{0}}{M}\mathbf{h}^{H}\mathbf{h}$. Thus, we can write a simple expression for $P_{1k_{l}}$ as

where $\alpha_{l}=\sqrt{\frac{N_{0}M}{El}}$ and $Z\sim\mathcal{N}(0,1)$. Next, we proceed to solve (15) with respect to different wireless communication channel models.

We propose an efficient method for the implementation of the optimal communications receiver under the proposed modulation method. An optimal receiver for the fading channel implements the ML decision rule, which is given in (7), where the detected signal maximizes correlation between the transmitted signal and the received signal correlated with the channel vector. This can be implemented using a correlation receiver (or a matched filter) using the relation

where the basis function $\phi_{m}(t)$ is defined by $\phi_{m}(t)=\sqrt{\frac{2}{T}}s_{p}(t)\cos(2\pi f_{m}(t))$. Based on (30), we formulate the following matrix

in which the $nm$-th element, $r_{nm}$, represents the correlation between the received signal and the basis function $\phi_{m}(t-(n-1)T)$. Now, the ML detection rule reduces to selecting the $M$ elements from R in such a way that the selected $M$ elements are in $M$ different rows (because the frequencies are not repeated in a given waveform) and $M$ different columns (because only one frequency is used during a given pulse duration) and the sum of the $M$ elements is maximized.

We note that this optimization is an assignment problem which can be solved efficiently using the Hungarian algorithm [38]. More specifically, we formulate the cost matrix by negating R and follow the Hungarian algorithm to pick at most one element from each row and column in such a way that the summation is maximized. It is important to note that the Hungarian algorithm always results in the optimum solution. For the sake of completion, in Algorithm 1, we summarize the main steps of the Hungarian algorithm that we follow in order to obtain the optimum solution. A working example of the algorithm is also provided in B. For further details please refer to [38]. Compared to the exhaustive search which has a time complexity of $O(M!)$, the Hungarian algorithm has a worst case complexity of $O(M^{3})$.

In radar waveform design, the time-frequency autocorrelation function of the transmitted waveform provides a measure of the degree of similarity between the complex envelope of the transmitted waveform and a replica of it that is shifted in time and frequency [39]. The ambiguity function is defined as the magnitude of the time-frequency autocorrelation function and it fully characterizes the behavior of a radar waveform in relation to the matched filter output [28, 40]. More specifically, it describes the output of a matched filter when the signal input to the radar receiver is delayed by $\tau$ and Doppler shifted by $\omega$. The ambiguity function is useful for examining several radar parameters including, resolution, side-lobe structure and accuracy in both delay and Doppler. In fact, the local accuracy of the delay and Doppler estimates are characterized by the behavior of the ambiguity function around the origin, while the global accuracy is characterized by its broader structure [39].

In order to derive the ambiguity function, we re-write the expression in (1) as

where $\omega^{i}_{m}=2\pi f^{i}_{m}$ and without loss of generality we have normalized the signal energy to one. Based on [28, eq. (4.30)], the time-frequency autocorrelation function, which is also known as the complex ambiguity function, of the above waveform can be written using $s_{i}(t)$ and its complex conjugate $s_{i}^{*}(t)$ as

where $\tau$ is the time delay relative to the expected matched filter peak output and $\omega$ is the Doppler mismatch. Substituting (32) into (33) we can write

Substituting $s^{\prime}=s-mT$ and rearranging (34) we get

If the complex ambiguity function of the simple pulse $s_{p}(t)$ is represented by $\hat{A}_{p}(\tau,\omega)$, the integral in (35) can be reexpressed as

where $\hat{A}_{p}(\tau,\omega)$ is given by

Then, the ambiguity function of the waveform is defined as the magnitude of $\hat{A}(\tau,\omega)$

The expression in (41) succinctly characterizes the behavior of the Lehmer code based stepped frequency radar waveform in the whole delay-Doppler plane.

The matched filter output when there is no Doppler mismatch is given by the zero-Doppler response ${A}(\tau,0)$, which can be found by setting $\omega=0$ in (41) which results in

Note that ${A}(\tau,0)$ is the autocorrelation function of $s_{i}(t)$. Similarly, the matched filter output when there is no delay is given by the zero-delay response ${A}(0,\omega)$, which can be found by setting $\tau=0$ in (41) which results in

Note that ${A}(0,\omega)$ is the Fourier transform of the magnitude squared of $s_{i}(t)$. In radar, the zero-Doppler response and the zero-delay response are used to quantify the range estimation accuracy and the velocity estimation accuracy, respectively [28]. This is further discussed using numerical examples in Section V.

For the $i$-th transmitted waveform, we define the complex envelope of the received radar waveform as given in [39, eq. 3]

where $\tau$ and $\omega$ are the unknown delay and Doppler to be estimated, the multiplier $\tilde{b}$ represents fading induced by multiple reflecting surfaces on the target and is modelled by a zero mean and unit variance complex Gaussian random variable and $n(t)\sim\mathcal{CN}(0,N_{0})$ represents the AWGN. Then, the $2\times 2$ Fisher information matrix for $\tau$ and $\omega$ is defined as [39]

where we identify subscript 1 with $\tau$ and subscript 2 with $\omega$. Based on [39, eq. (63) - (65)] we can write the elements of ${\bf{J}}$ as

where $C=\frac{2}{N_{0}}\left(\frac{1}{1+N_{0}}\right)$ and $\overline{\omega^{2}}$, $\overline{\omega\tau}$ and $\overline{\tau^{2}}$ are given in [39, eq. (67), (68) and (69)], respectively. The term $\overline{\omega}$ can be found by replacing $\omega^{2}$ by $\omega$ in [39, eq. (67)] and similarly $\overline{\tau}$ can be found by replacing $u^{2}$ by $u$ in [39, eq. (69)]. Using lengthy mathematical manipulations, we solve (46) - (48) and find closed-form expressions for the Fisher information matrix elements as

where $B$ is the finite filter bandwidth of the radar receiver and $\omega_{0}=2\pi f_{0}$. As the derivations of the $J_{11}$, $J_{12}$ and $J_{22}$ terms involve lengthy calculations, we have presented them separately in Appendices C, D and E, respectively. Note that the pulse width $T$ in the above expressions are that of the perfectly rectangular pulse before bandwidth limiting. It is a good approximation to the width of the bandwidth-limited pulse for large $BT$. Also, the approximation in (49) comes from neglecting the small terms in the resulting integrals which vanish as we set $BT\rightarrow\infty$. The term $\omega_{0}T$ represents the phase shift between adjacent frequency tones and is further explained in Appendix C.

Based on the Fisher information matrix we can bound the variance of delay and Doppler estimation errors which directly corresponds to the target range and velocity estimation accuracy in radar. More specifically, the variance of any unbiased estimate is bounded by the diagonal elements of ${\bf{J}}^{-1}$ [39]. Thus, the CRLBs on the delay estimation error and the Doppler estimation error, which we denote by $\textrm{CRLB}_{\tau}$ and $\textrm{CRLB}_{\omega}$, respectively, can be approximated as

We can further simplify (52) and (53) based on [39, eq. (94), (95)] by ignoring the effect of the $\overline{\omega\tau}$ term on the CRLB. This simplification allows us to draw more insights on the effect of different parameters on the estimation errors as follows

Note that when we set $M=1$, the right hand sides of (54) and (55) reduce to $C^{-1}T/2B$ and $12C^{-1}/T^{2}$, respectively, which are the CRLBs on the delay and Doppler estimation errors for a simple pulse [28, 41]. Based on (54) we note that the bound on the delay estimation error is proportional to the simple pulse length $T$. In other words, the delay estimation error is inversely proportional to the effective bandwidth of the simple pulse (which is approximately $1/T$). Based on (55) we note that the bound on the Doppler estimation accuracy is determined by the total pulse width. More specifically, the Doppler estimation error decreases as we increase $M$ and $T$. If we keep the energy of the signal fixed, and increase $T$ the accuracy in Doppler will increase and the accuracy in delay will decrease. These observations are further discussed in Section V using numerical examples.

As is the case with any radar waveform with a frequency sweep across the waveform, such as the LFM waveform, the Lehmer code based random stepped frequency radar waveform introduces range-Doppler coupling. Thus, when both the delay and Doppler are unknown, there is an ambiguous region in the delay-Doppler plane. In radar, the classical method of resolving this ambiguity is by transmitting another waveform with the opposite frequency sweep [39]. In our joint radar communication system, this is automatically taken care of by the randomization of the incoming data, because, the transmitted radar waveform will differ based on the communication data, and hence, the effect of the overall range-Doppler coupling will be negligible in average. More specifically, the off-diagonal terms in the Fisher information matrix, i.e., the $J_{12}$ and $J_{21}$ terms in (50) change with $\omega_{m}^{i}$, and hence on the particular frequency permutation of the waveform. They are maximized when $\omega_{m}^{i}$ values are set in ascending order and the resulting ambiguous region lies in the first and third quadrants of the delay-Doppler plane. Similarly, $J_{12}$ and $J_{21}$ terms are minimized when $\omega_{m}^{i}$ values are set in descending order and the resulting ambiguous region lies in the second and fourth quadrants of the delay-Doppler plane.

The overall structure of the AF resulting from the Lehmer code based random stepped frequency radar waveform has a narrow main-lobe and small side-lobes. Such an AF is important to achieve good radar performance specially with clutter. There is a useful averaging effect on the AF side-lobes which occurs because the communications tends to randomly select among all possible frequency combinations which means that clutter enters via the average AF side-lobe level and this is reasonably small for our waveform. The positioning of these side-lobes in the range-Doppler plane changes with the transmitted radar waveform. In situations where AF side-lobe clutter must be minimized, a more advanced coding scheme can be used in which the incoming data is mapped to radar waveforms in such a way that the overall effect of clutter is minimized in average. This could be a topic of interest for future.