We start from the Zak-OTFS (orthogonal frequency space modulation) carrier waveformfoot_0 [13][14][15] and use the Heisenberg-Weyl group to construct a large family of radar waveforms. The Zak-OTFS carrier waveform is a pulse in the delay-Doppler (DD) domain, more specifically a quasi-periodic localized function defined by a delay period τ p and a Doppler period ν p where τ p ν p = 1 . We then apply a DD domain pulse shaping filter. The TD representation of the filtered signal is a TD pulsone, that is a train of narrow impulses modulated by a sinusoid, with time duration T and bandwidth B inversely proportional to the Doppler and delay spread, respectively, of the filter. In Zak-OTFS modulation, we transmit information using nonoverlapping DD domain pulses spaced 1/B apart along the delay axis and 1/T apart along the Doppler axis. Since each pulse repeats quasi-periodically, there are M = τ p /1/B = Bτ p pulse locations along the delay axis and N = ν p /1/T = T ν p pulse locations along the Doppler axis. The number of dis- tinct nonoverlapping information carriers is the time-bandwidth product BT = MN , and arithmetic modulo MN plays an essential role in the mathematical development of our framework for discrete radar. Throughout this paper we assume, for simplicity, that M, N are distinct odd primes. We design radar waveforms by applying discrete affine Fourier transforms to a Zak-OTFS carrier.

The inverse Zak transform converts a DD domain waveform to a time domain (TD) waveform. The discrete Zak transform (DZT) [6] defines a unitary equivalence between the Hilbert space of MN-periodic sequences in the TD and the Hilbert space of quasiperiodic M × N arrays in the DD domain. Note that a quasi-periodic M × N array is periodic modulo MN. Section 3.1 describes how the Heisenberg-Weyl group acts on both Hilbert spaces, and how the DZT respects both group actions.

It is customary in radar theory to regard a waveform as a signal that is modulated onto a carrier and to separate carrier modulation and demodulation from the analysis of ambiguity. Separating the choice of the modulating signal from the choice of carrier makes the problem of waveform design modular, and this modularity is at the heart of conventional processing for pulse Doppler radars. In this paper, we focus not on sequence design, but on designing carrier waveforms with target ambiguity properties.

In Sect. 4.1, we compare our direct approach to radar waveform design with sequence design, followed by modulation onto a carrier. We compare against constant amplitude (CA) sequences with zero autocorrelation (ZAC), known as CAZAC sequences, which are widely used to design discrete-time radar waveforms (see [16]). The family of CAZAC sequences includes Zadoff-Chu (ZC) sequences [17] that are used in 5 G wireless standards because of their correlation properties. By applying a discrete affine Fourier transform to a Zak-OTFS carrier, we are able to construct a discrete chirp waveform that coincides with the ZC sequence when sampled appropriately. When we compare the magnitude of the self-ambiguity function of our discrete chirp waveform with the magnitude of the self-ambiguity function of the ZC phase-coded rectangular waveform, we see a 100 dB difference in the level of the sidelobes.

The phase of the Zak-OTFS carrier waveform changes when the pulse location shifts by an integer multiple of τ p along the delay axis, and there is no change in phase when the pulse location shifts by an integer multiple of ν p along the Doppler axis. We study the ambiguity properties of a general radar waveform v through its isotropy group I v which is the subgroup of the discrete Heisenberg-Weyl group that acts on v by multiplication by a complex phase. The isotropy group of the Zak-OTFS carrier has size MN, generated by a delay shift of Mτ p and a Doppler shift of N ν p . The Zak-OTFS carriers form an orthonormal basis, the discrete Heisenberg-Weyl group permutes the carriers, the self-ambiguity function takes the value 1 when the delay shift is a multiple of M and the Doppler shift is a multiple of N, and it takes the value 0 elsewhere. In general, the selfambiguity function of a radar waveform v takes the value 1 on the isotropy group I v and is constant on cosets of I v in the discrete Heisenberg-Weyl group. We understand the structure of the ambiguity function of a radar waveform v by understanding the orbits of v under the discrete Heisenberg-Weyl group, and we understand the orbits by under- standing the isotropy group I v .

Isotropy groups must be commutative, and a commutative subgroup of the discrete Heisenberg-Weyl group has size at most MN. The operators in a maximal commutative subgroup of size MN can be simultaneously diagonalized, giving an orthonormal basis of common eigenvectors. The isotropy subgroup of any eigenvector has size MN, and the self-ambiguity function takes the value 1 on the isotropy group and takes the value 0 elsewhere. By selecting radar waveforms that are eigenvectors of maximal commutative subgroups, we minimize the support of the self-ambiguity function, and we simplify target detection by reducing ambiguity. When we select the radar waveform to be a Zak-OTFS carrier, the self-ambiguity function is supported on points (aM, bN) where a, b are arbitrary integers (the self-ambiguity function is periodic modulo MN and in Sect. 3.2 we show that this support set has the structure of a line modulo MN). The intended delay resolution 1/B and intended Doppler resolution 1/T of the radar determine the delay and Doppler periods that define the Zak-OTFS modulation. We have shown in [14,15] that if we select the radar waveform to be a Zak-OTFS carrier, then we can separate targets if their delays differ by more than 1/B or if their Doppler shifts differ by more than 1/T . In fact, we can read off an image of the scattering environmentfoot_1 from the response to a single Zak-OTFS carrier waveform [14,15,23].

In Sect. 3.4, we introduce symplectic operators that normalize the discrete Heisenberg-Weyl group. Conjugation by a symplectic operator defines an isomorphism of the Heisenberg-Weyl group that maps maximal commutative subgroups to maximal commutative subgroups. If a symplectic operator W maps an eigenvector v to Wv then the isotropy group of Wv is simply

, is a function of a delay shift k and a Doppler shift l, and is periodic modulo MN. In Sect. 3.4, we introduce discrete affine Fourier transforms, prove that they normalize the discrete Heisenberg-Weyl group, and describe how they transform ambiguity functions. We show that a discrete affine Fourier transform W determines a 2 × 2 matrix g with entries in Z MN and determinant 1 such that

. Symplec- tic operators rotate ambiguity functions, and the development in Sect. 3.4 is the discrete counterpart of the continuous theory used to construct waveform libraries [24][25][26][27].

These operators also map the optimal radar waveforms to counterparts with small peakto-average power ratio (PAPR). Section 4 describes how to reduce the complexity of radar signal processing by taking advantage of underlying discrete structure in the radar waveform. Our baseline is traditional continuous radar processing (Fig. 2a & b) where the complexity of computing the radar cross-ambiguity function is O B 2 T 2 dominates signal processing complexity. We propose a discrete architecture that is based on choosing a radar waveform that is highly symmetric-the isotropy subgroup of the waveform is a maximal commutative subgroup of the Heisenberg-Weyl group. The received waveform is matched filtered to optimize SNR, then sampled and periodized in the time domain, resulting in a periodic discrete-time signal with period BT = MN . The DD domain locations of the targets are obtained by calculating the discrete cross-ambiguity between the discrete-time MNperiodic transmitted waveform and the sampled and periodized received signal. Utilizing a Zak-OTFS carrier (or its symplectic transformations) as a radar waveform enables low-complexity cross-ambiguity calculations at a sublinear complexity of O BT log T . Our discrete architecture makes it possible to improve delay and Doppler resolution for a fixed complexity budget.

There is an additional benefit to working with discrete chirps modulo MN within our framework. The self-ambiguity function of a continuous chirp is a line, whereas the self-ambiguity functions of our chirps are supported on noncontiguous sets in the DD domain. This enables simultaneous resolution in both delay and Doppler, which is not possible with continuous chirps. For more information about target resolution using chirp waveforms and Zak-OTFS waveforms, we refer the reader to [23].

Notation: x denotes a complex scalar, x denotes a vector with nth entry

This Section prepares the ground for our development of discrete radar based on Zak-OTFS. We use the following identity from classical number theory repeatedly.

Identity 1 ( [28], pg.18) The sum of all Nth roots of unity satisfies:

Here, we briefly review how Zak-OTFS signals are formed in the delay-Doppler (DD) domain and are transmitted in the time domain (TD). We refer the interested reader to [13][14][15] for a more detailed description of Zak-OTFS. The Zak-OTFS carrier waveform is a pulse in the delay-Doppler (DD) domain, formally a quasi-periodic localized function termed the DD pulsone defined by a delay period τ p and a Doppler period ν p where τ p ν p = 1 . The DD pulsone occupies infinite time and bandwidth. To enable practical implementation, the DD pulsone is limited to a time interval T and a bandwidth B via DD domain pulse shaping (filtering). The resulting TD representation of the filtered signal is a train of narrow impulses modulated by a sinusoid, with time duration T and bandwidth B inversely proportional to the Doppler and delay spreads of the filter, respectively.

Information symbols in Zak-OTFS are transmitted using nonoverlapping DD domain pulsones spaced 1/B apart along the delay axis and 1/T apart along the Doppler axis. Since each pulsone repeats quasi-periodically, this corresponds to mounting information on M = τ p /1/B = Bτ p distinct locations along delay and N = ν p /1/T = T ν p dis- tinct locations along Doppler. Thus, the number of distinct nonoverlapping information carriers in Zak-OTFS is the time-bandwidth product BT = MN . The MN information symbols are mounted on pulsones in the DD domain as: where X ∈ C M×N denotes the M × N DD array of information symbols, τ and ν are delay and Doppler axes, respectively, and δ(•) is the delta function. The continuous TD representation of the DD signal in (1) is via the inverse Zak transform: Substituting (1) in (2): Note that (3) is defined in terms of the DD array of information symbols X . Formally, X is a quasi-periodic array 3 (see [6,[13][14][15] for more details). We now introduce the discrete Zak transform (DZT), which is a unitary map from MN-periodic discrete-time sequences x to M × N quasi-periodic arrays X (see [6] for details). This fundamental equivalence makes it possible to implement signal processing functions in either the time domain or the delay-Doppler domain.

) The discrete Zak transform (DZT) maps an MN-periodic sequence x to a quasi-periodic M × N array X as follows:

(1)

x(t, ν)dν.

(3)

where k ∈ Z M is the delay and l ∈ Z N is the Doppler index. The M × N quasi-periodic arrays X[k, l] form a Hilbert space, and inner products can be calculated on any M × N subarray. Similarly, the MN-periodic sequences x form a Hilbert space, and inner prod- ucts can be calculated on any interval of length MN.

Substituting Definition 1 in (3):

From Identity 1, the inner summation over l vanishes unless d ≡ p mod N , when it takes the value N. Hence, we obtain:

We can view the continuous TD signal x(t) as a discrete-time sequence x mounted on delta functions spaced at the delay resolution 1/B = τ p /M . This fact is central to our proposed framework for discrete radar based on Zak-OTFS.

At a high-level, the operation of a radar consists of transmitting a waveform, which is reflected by the scattering environment and its return is processed at the receiver [18,29,30]. Representing the scattering environment by a DD function h(τ , ν) and the continuous TD transmit signal by x(t), the continuous TD received signal is:

where we have neglected additive noise at the receiver. To derive the system model corresponding to a discrete radar, we map the transmit and received continuous TD signals to MN-periodic sequences by projecting the continuous TD signals onto the 1/B = τ p /M-spaced delta function basis from (5). Specifi- cally, from (6) we compute:

(5)

To evaluate the integral A , we substitute (5):

To evaluate the integral in (8), we assume the delay τ and Doppler ν are integer multiples of the delay and Doppler resolutions, i.e., τ = kτ p /M for some k ∈ Z MN , and ν = lν p /N for some l ∈ Z MN . Substituting into (8):

where the final expression follows from the conditions (m + k) ≡ n mod MN and t = nτ p /M obtained from the delta functions. Substituting the value for A back into (7):

where h[k, l] = N τ p h kτ p /M, lν p /N is the scaled & sampled version of the DD function h(τ , ν) at multiples of the delay and Doppler resolutions. Thus, as per (10), the output of a discrete radar is an MN-periodic sequence y given by the weighted sum of various delay-shifted and Doppler-modulated versions of the transmit sequence x. Note: Although our derivation above utilizes delta functions in the transmit waveform, in practice, the function h(τ , ν) takes into account both pulse shaping and the physical scattering environment, which is referred to as the effective channel in the literature [13][14][15]. Pulse shaping helps limit the time and bandwidth of the waveform to T and B, respectively. Moreover, our framework is capable of considering paths in the physical scattering environment with fractional delay and Doppler values as long as the effective channel is sampled at multiples of the delay and Doppler resolutions. For more details, we refer the interested reader to [13-15, 23, 31, 32].

Given the system model in (10), radars generate a discrete image of the scattering environment by cross-correlating the received sequence y with different delay- shifted and Doppler-modulated versions of the transmit sequence x . Formally, this is accomplished via the cross-ambiguity function, defined below for sequences in the Hilbert space H of all complex-valued MN-periodic sequences. Note that since the (7)

sequences are MN-periodic, inner products can be calculated within any window of length MN.

The cross-ambiguity function of two unit-norm MN-periodic sequences x, y ∈ H is defined as:

where k, l ∈ Z MN , the integers modulo MN. When y = x , A x,x [k, l] is referred to as the self-ambiguity function of x , and is abbreviated to A x [k, l] for brevity.

Radars represent the scattering environment by calculating from (10):

The above expression shows that the image formed by the radar is essentially the DD function h[k, l] "blurred" by the (phase-scaled) self-ambiguity function of the transmit- ted sequence x . Ideally, it would be desirable to choose a sequence x with a "thumb- tack-like" self-ambiguity function. However, fundamental properties of the ambiguity function limit the amount of waveform shaping that is possible. Specifically, Moyal's Identity stated below shows that though the shape of the self-ambiguity function surface depends on the choice of waveform, the volume under the surface always remains fixed and equals the (scaled) energy of the waveform.

Identity 2 (Moyal's Identity [2-5, 33, 34]) The self-ambiguity functions of unit-norm MN-periodic sequences x, y ∈ H satisfy:

A special case of the above relation corresponds to y = x:

A direct corollary of Moyal's Identity is the following.

Corollary 1 Given a unit-norm MN-periodic sequence x ∈ H , there are at most MN delay-Doppler indices

In this Section, we show how the basic discrete radar theory described in Sects. 2.2 and 2.3 can be studied under a more general group-theoretic framework. We show how the action of the scattering environment in (10) corresponds to the superposed actions of the discrete Heisenberg-Weyl group. We then derive various useful properties of the discrete Heisenberg-Weyl group. We explain how the theory applies to two prototypical examples, which we follow through the Section. In Sect. 4, we explore how the theory developed in this Section enables: (i) designing radar waveforms with ideal self-ambiguity functions, (ii) computing images of the scattering environment at low complexity, and (iii) defining radar waveform libraries that can be implemented at low hardware complexity due to their small peak-to-average power ratios.

For simplicity, we henceforth assume that the integers M and N introduced in Sect. 2 are odd primes 4 (unless mentioned otherwise).

We begin by recalling the action of the scattering environment on the transmitted sequence in (10), which is reproduced here for ease of reference: For a given k, l ∈ Z MN , we may represent the action of the scattering environment by a unitary operator that delay shifts and Doppler modulates any input sequence belonging to the Hilbert space H of MN-periodic sequences. 4 In this paper, we focus on the value of choosing a radar waveform to be an eigenvector of a maximal commutative subgroup (see Sect. 3.3 for more details). When M, N are allowed to be composite and to have common factors, more types of maximal commutative subgroups become possible, and the support of the self-ambiguity function becomes more varied. In the analysis, sums of MNth roots of unity need to be replaced by sums of (MN/d) th roots of unity, where d = (M, N) is the greatest common divisor of M and N. In summary, the principle does not change, but the details become more complicated. The collection of all (phase-scaled) Heisenberg operators forms a group.

The set H MN under operator composition • forms the Heisenberg-Weyl group, which can be equivalently defined in terms of 3 × 3 upper triangular matrices: under matrix multiplication modulo MN.

We verify that the Heisenberg-Weyl group satisfies all group axioms.

(Identity) The identity element is given by D (0,0) ∈ H MN , which corresponds to the identity matrix in the matrix description.

.

(Inverse) Equating ( 13) to the identity matrix and solving for h 1 for a given h 2 , we obtain the conditions:

The following Lemma determines when two elements of H MN commute.

The symplectic form l 1 k 2 ≡ l 2 k 1 mod MN determines when two elements

The symplectic form is not identically zero and the Heisenberg-Weyl group is not commutative in general.

We may express (13) as:

We now place the Heisenberg-Weyl group defined above in the context of the discrete radar theory described in Sects. 2.2 and 2.3. Note that the cross-ambiguity function defined in Definition 2 can be expressed in terms of Heisenberg operators D (k,l) and Heisenberg-Weyl group elements h = e j2π MN m D (k,l) ∈ H MN as:

In other words, the cross-ambiguity function corresponds (up to a phase) to the inner product of a sequence x with the action of a Heisenberg-Weyl group element h ∈ H MN on the sequence y . Hence, properties of the Heisenberg-Weyl group elements directly impact the behavior of the discrete radar ambiguity function. After a brief detour in Sect. 3.1.1 where we define an equivalent representation of the Heisenberg-Weyl group (14)

in the delay-Doppler domain, we investigate various properties satisfied by Heisenberg-Weyl group elements in Sects. 3.2, 3.3 and 3.4.

In Theorem 1, we defined the Heisenberg-Weyl group in terms of MN-periodic sequences. We now derive an equivalent representation of the Heisenberg-Weyl group in the delay-Doppler domain by mapping MN-periodic sequences to M × N quasi-peri- odic arrays through the DZT (Definition 1). This equivalence makes it possible to implement signal processing functions in either the time or delay-Doppler domains.

The DZT in Definition 1 is a unitary transform that preserves inner products.

where v r,s [n] is repeated periodically with period MN, which closely resembles the dis- crete-time version of the pulsone basis element presented in (3). The basis is orthonormal since:

where the last expression follows from Identity 1. Per Definition 1, the DZT of ( 18) is:

The obtained basis is clearly orthonormal since:

where the final result follows from Identity 1. Hence, the DZT preserves inner products since it maps the orthonormal basis v r,s to the orthonormal basis V r,s .

Let H DD denote the Hilbert space of all complex-valued M × N quasi-periodic arrays formed by the DZT of MN-periodic sequences in H . We now define Heisenberg opera- tors, similar to Definition 3, in the delay-Doppler (DD) domain.

(k,l) are unitary operators that act on quasiperiodic arrays X ∈ H DD as:

We now define the Heisenberg-Weyl group in the delay-Doppler domain and show that the group representation in the delay-Doppler domain is unitarily equivalent to the Heisenberg-Weyl group representation given in Theorem 1.

MN denote the collection of phase-scaled DD Heisenberg operators D DD (k,l) :

The set H DD MN under operator composition • forms the Heisenberg-Weyl group in the delay-Doppler domain, which is unitarily equivalent to the Heisenberg-Weyl group representation H MN in Theorem 1 over the Hilbert space of MN-periodic sequences.

MN is unitarily equivalent to H MN from Theorem 1, in which case H DD MN inherits all the properties satisfied by H MN . Letting Z denote the operator rep- resentation of the DZT, we must therefore show:

Consider an M × N quasi-periodic array X . The inverse DZT per Definition 1 is given by: Substituting (21) in Definition 3, we obtain:

where the final expression follows from elementary modular arithmetic identities.

Applying the DZT per Definition 1:

From Identity 1, the inner summation over p vanishes unless q ≡ (l ′l) mod N . Thus:

Hence, H DD MN is unitarily equivalent to H MN from Theorem 1.

Given the unitary equivalence of H DD MN and H MN , in the remainder of this paper we restrict attention to the latter, i.e., the Heisenberg-Weyl group defined over the Hilbert space H of MN-periodic sequences. An equivalent development of all our subsequent results is possible in the delay-Doppler domain based on the results presented above.

We now investigate subgroups of the Heisenberg-Weyl group H MN that are com- mutative, i.e., satisfy the symplectic form in Lemma 1. Commutative subgroups, and especially their specialized forms called maximal commutative subgroups that are introduced in Sect. 3.3, play a special role in the theory of discrete radar since they act on input waveforms simply by a phase multiplication; hence lend desirable properties to ambiguity functions.

Commutative subgroups T MN ⊂ H MN of the Heisenberg-Weyl group satisfy the symplectic form in Lemma 1, l 1 k 2 ≡ l 2 k 1 mod MN , for any

Every commutative subgroup contains the center of the group, given by phase-scaled versions of the identity operator: which is easily seen to commute with the whole Heisenberg-Weyl group.

A nontrivial example of a commutative subgroup of the Heisenberg-Weyl group corresponds to a line modulo MN.

We show that T MN is a commutative subgroup of H MN per Definition 5. Note that T MN contains the identity element D (0,0) ∈ H MN . Hence, it suffices to show commutativity and closure, and the other group properties (associativity and inverse) hold by default.

The subgroup is closed since on substituting (25) in (15) we obtain:

We now define the notion of maximal commutative subgroups of H MN , which are spe- cial commutative subgroups with the property that no group element outside of the subgroup commutes with the subgroup.

Maximal commutative subgroups of H MN admit an orthonormal eigenbasis decompo- sition with unimodular eigenvalues, as described in the following Lemma.

For each maximal commutative subgroup T MN ⊂ H MN , there exists a simultaneous orthonormal eigenbasis v i MN i=1 for all elements t ∈ T MN , with group elements h ∈ T MN not in the subgroup acting orthogonally on the eigenvectors:

1 Proof Since the elements of T MN are unitary and commuting, its follows from linear algebra theory that they must all be simultaneously diagonalizable. Hence, there must exist an orthonormal basis v i MN i=1 such that for all t ∈ T MN , tv i = t,i v i . Since the elements of T MN are unitary, the corresponding eigenvalues must have unit magnitude, | t,i | = 1.

We prove the final condition by contradiction. Assume there exists some h ∈ H MN , h � ∈ T MN such that h • t = t • h for t ∈ T MN . Hence, for an eigenvector v i , we must have: i.e., hv i ∝ v i =⇒ h ∈ T MN . However, this is a contradiction since we assumed h ∈ T MN .

Therefore, for all group elements h ∈ H MN , h � ∈ T MN , we must have hv i ∝ v j for some j = i such that t,i = t,j . Let hv i = α i,j v j for some α i,j ∈ C . Thus, we have: (25)

since the eigenbasis is orthonormal and j = i .

Given an eigenvector v of a maximal commutative subgroup, its self-ambiguity func- tion A v [k, l] depends on the orbit of v under H MN [34]. The isotropy group I v of v com- prises the elements of H MN that act as multiplication by a complex phase. Isotropy groups are commutative, hence v is a waveform with the largest possible isotropy group. Corollary 2 shows that the self-ambiguity function A v [k, l] is constant on cosets of I v .

The self-ambiguity functions of eigenvectors v i MN i=1 of a maximal commutative subgroup T MN ⊂ H MN satisfy: Moreover, the self-ambiguity function is unimodular over exactly MN delay-Doppler indices (k, l), k ∈ Z MN , l ∈ Z MN .

Lemma 4 and Corollary 2 show that the self-ambiguity functions of eigenvectors of maximal commutative subgroups are unimodular only over MN delay-Doppler locations, outside of which they are zero. Around each such location, the ambiguity function has a local "thumbtack-like" property, making it desirable to utilize eigenvectors of maximal commutative subgroups as radar waveforms.

We now show that Example 1 corresponds to a maximal commutative subgroup.

The commutative subgroup T MN in Example 1 is maximal. Moreover, every maximal commutative subgroup of H MN is a line of the form given by T MN .

Let S T MN = (k, l) e

easy to see that the quotient group is commutative. A maximal commutative subgroup of H MN corresponds to a (phase-scaled) subgroup of Q MN with order MN. Since M and N are distinct primes, such a subgroup of Q MN should be cyclic of order MN; hence, must be of the form given by T MN .

We now derive the eigenbases corresponding to the two special cases of Example 1.

To understand the structure of the eigenbasis, we substitute T MN from Special Case 1 in Lemma 4:

For the above condition to be satisfied, we seek an orthonormal basis that is quasi-periodic with period M along delay.

The pulsone basis satisfies the condition in (26), i.e., is the eigenbasis corresponding to the maximal commutative subgroup T MN in Special Case

To prove the Lemma, we first evaluate (hv i )[n] for a Heisenberg-Weyl group element

where the final expression follows on substituting the pulsone basis element defined in the Lemma statement in Definition 3. On substituting k

where the final expression follows from the property of the Kronecker delta function that f

We have:

When h = t ∈ T MN , i.e., k = aM and l = bN , we have j = i = k 0 + l 0 M ; hence:

When h ∈ T MN , i.e., k ≡ 0 mod M and/or l ≡ 0 mod N, (27) implies j = i ; hence: since the pulsone basis is orthonormal. Together, ( 29) and ( 28) satisfy the conditions in Definition 6 and Corollary 2.

To understand the structure of the eigenbasis, we substitute T MN from Special Case 2 in Lemma 4:

For the above condition to be satisfied, we seek an orthonormal basis with quadratic phase terms.

The discrete chirp basis satisfies the conditions in (30), i.e., is the eigenbasis corresponding to the maximal subgroup T MN in Special Case 2:

for an affine function f, with corresponding eigenvalue t,i = e j2π MN m e -j2π MN (αk 2 +βk) . ( 27)

To prove the Lemma, we first evaluate (hv i )[n] for a Heisenberg-Weyl group element

When h = t ∈ T MN , i.e., 2αk -l ≡ 0 mod MN , we have j = i = f (α, β, γ ) ; hence:

Following (31), we may evaluate the inner product with v i as:

where the final expression follows from Identity 1. Thus, (33) satisfies the conditions in Definition 6 and Corollary 2.

We now define a special class of unitary operators called symplectic transformations that act by conjugation on H MN , defining automorphisms that preserve the group structure and hence map commutative subgroups to commutative subgroups.

A symplectic transformation of the Heisenberg-Weyl group H MN is a unitary operator W(g) : H → H associated with an element g ∈ G of the special linear group of order 2 over Z MN : that acts on the Hilbert space H of complex-valued MN-periodic sequences as: (31) ( We may interpret (36) as the statement that W(g) normalizes H MN . Conjugation by W -1 (g) defines an automorphism of H MN that maps commutative subgroups to commuta- tive subgroups.

Symplectic transformations map commutative subgroups of H MN to commutative subgroups.

We now make Lemma 8 explicit. Consider two elements t 1 = e j2π MN m 1 D (k 1 ,l 1 ) ∈ T MN and t 2 = e j2π MN m 2 D (k 2 ,l 2 ) ∈ T MN . As per (36):

Recall from Definition 5 that t 1 , t 2 ∈ T MN satisfy the symplectic form:

can be rewritten as:

Substituting the definition of the group element g ∈ G as per (34), we obtain:

) due to the symplectic transformation W(g) preserves the symplectic form from Definition 5, and hence also represents a commutative subgroup of H MN . ( 36)

1 Lemma 9

Symplectic transformations rotate the ambiguity functions of waveforms. Let W(g) denote a symplectic transformation corresponding to a group element g ∈ G . Then:

1 Proof Since W(g) is unitary, we may express the ambiguity function as:

An example of a symplectic transformation is the DZT introduced in Definition 1. We showed in Theorem 2 that the DZT centralizes H MN , i.e., the DZT is a symplectic trans- formation W(g) corresponding to the identity group element g = 1 0 0 1 ∈ G with:

where the above expression follows from (20) in the proof of Theorem 2. We now present two examples of symplectic transformations corresponding to nonidentity elements g ∈ G . The presented examples have practical implications for radar signal processing, especially in the design of waveform libraries for adaptive radars.

which is defined for the group element g = 1 0 2A 1 ∈ G , and corresponds to a linear fre- quency modulation (LFM) of the input waveform x at rate A.

Example 2 is the discrete form of the continuous linear frequency modulation transform presented in [24,25]. We now derive the group element g ∈ G corresponding to the symplectic transformation. To that end, let ỹ[n] = (W(g)y) [n] . We calculate:

On comparing with (41): and:

1 Example 3

which is defined for any group element g ∈ G with (b, MN ) = 1 , and corresponds to a discrete generalization of the affine Fourier transform, referred to as GDAFT in short.

Example 3 is the discrete form of the continuous affine Fourier transform presented in [24,25]. We now specialize the derivation in (41) to this transformation. Let ỹ[n] = (W(g)x)[n] as before. We calculate: (43) The inner summation over n 2 vanishes unless l + b -1 MN (n 1n + ak) ≡ 0 mod MN =⇒ n 1 = (n -(ak + bl)) MN , when it takes the value MN. Thus: where g = a b c d ∈ G . On comparing with (41):

In this Section, we describe a new architecture for discrete radar that implements the Heisenberg-Weyl group theory described in Sect. 3. Figure 2 illustrates three different radar architectures-continuous radar, discrete radar with separate optimization of sequences and carrier waveforms, and our proposed approach.

Continuous radars [2-5, 35, 36] (Fig. 2a) transmit a continuous TD waveform x(t) after pulse shaping to limit time and bandwidth to T and B, respectively. The receiver performs matched filtering to remove the impact of pulse shaping, following which a continuous domain cross-ambiguity function is computed between the output of the matched filter and the transmit waveform. The radar forms a discrete radar image by sampling the continuous cross-ambiguity function at multiples of the delay and Doppler resolution.

Conventional discrete radars [16,[37][38][39][40][41][42][43][44] (see Fig. 2b) mount a discrete sequence z m onto a continuous carrier waveform (e.g., a rectangular pulse train), where the sequence is optimized separately from the carrier waveform. Possible strategies for sequence (46)

(

optimization include coding either the phase [16,[37][38][39]44], frequency [40][41][42] or amplitude [43] of the carrier waveform. After pulse shaping at the transmitter and matched filtering at the receiver, a continuous cross-ambiguity function is computed, which is sampled to obtain the discrete radar image. We propose a different architecture for discrete radar, which is illustrated in Fig. 2c. We mount BT-periodic discrete sequences onto delta functions, which are pulse shaped and matched filtered at the received. The output of the matched filter is first sampled and periodized to period BT. Then, a discrete cross-ambiguity function is computed between the discrete transmitted sequence and the sampled & periodized matched filter output to obtain the discrete radar image. The key difference with conventional discrete radars (Fig. 2b) is that our approach jointly optimizes the sequence and carrier waveform, which significantly reduces sidelobes of the ambiguity function and improves target detection, as we show in Sect. 4.1. The Heisenberg-Weyl group theory described in Sect. 3 also enables developing radar waveform libraries with low peak-to-average power ratio (PAPR), which we describe in Sect. 4.2. Moreover, sampling prior to the crossambiguity computation results in significant complexity gains over both continuous and discrete radars (Fig. 2a, b), as we show in Sect. 4.3.

Figure 3 compares the discrete radar images obtained using the three radar architectures from Fig. 2 for a four target scattering environment. In Fig. 3a, we consider a continuous radar with an up-slope and down-slope LFM transmit waveform [35]. The resulting radar image suffers from extremely high sidelobes due to the ambiguity function characteristics of the LFM waveform. In Fig. 3b, we consider a discrete radar with a Zadoff-Chu (ZC) phase-coded rectangular waveform. Despite improved target discrimination capabilities, there are significant sidelobes due to the nonzero sidelobes of the waveform (cf. Fig. 4a). In contrast, our proposed approach generates a radar image with perfectly localized targets, as shown in Fig. 3c.

Radars ask questions of scattering environments in order to control higher-layer functions such as target tracking. Images of scatterers are a means to an end rather than an end in itself. There may be small differences in the images of a scattering environment produced by continuous and discrete radars (cf. Fig. 3), but both images have the information necessary to control higher-layer functions. We refer the reader to the work of Bell [45] for information theoretic measures of effectiveness, to Kershaw and Evans [26] for information theoretic criteria for waveform scheduling to support tracking. For more details, see [24][25][26][27].

One benefit of our proposed discrete radar architecture is that it enables perfectly localized "bed-of-nails" ambiguity functions. Recall from Sect. 2.3 that an accurate estimate of the DD scattering environment is achieved when the self-ambiguity function of the Fig. 3 The continuous and discrete radar architectures generate radar images with significant sidelobes around the ground truth target locations due to the choice of the carrier waveforms. Our proposed approach generates a perfectly localized radar image The standard approach taken by discrete radars (see Fig. 2b) is to regard the waveform as a signal modulated onto a carrier and to separate the carrier modulation and demodulation processes from the analysis of ambiguity. However, their performance is limited by the ambiguity function characteristics of the chosen carrier waveform. As an illustration, Fig. 4a plots the magnitude of the self-ambiguity function for a Zadoff-Chu phase-coded rectangular waveform as defined in [16], with the waveform designed to have self-ambiguity function magnitude close to 1 on the line 2αkl ≡ 0 mod MN . The ambiguity characteristics of the rectangular carrier waveform results in significant sidelobes outside the locations given by the line.

In contrast, our proposed discrete radar architecture in Fig. 2c achieves perfectly localized "bed-of-nails" ambiguity functions with minimal sidelobes. Specifically, we choose the radar waveform as an eigenvector of a maximal commutative subgroup. Recall from Corollary 2 that for a maximal commutative subgroup T MN with eigenbasis v i MN i=1 , the self-ambiguity function of any eigenvector v i vanishes for all e j2π MN m D (k,l) ∈ T MN and is unimodular only at e j2π MN m D (k,l) ∈ T MN . Figure 4a illustrates the advantage of our approach. We consider the discrete chirp eigenvector from Lemma 7 corresponding to the Heisenberg-Weyl maximal commutative subgroup example in Special Case 2, and observe essentially no sidelobes in the self-ambiguity function magnitude outside the self-ambiguity function support 2αkl ≡ 0 mod MN.

How should one choose an appropriate maximal commutative subgroup T MN in our approach? Moyal's Identity (Identity 2 and Corollary 1) states that a perfect "thumbtack-like" ambiguity function is unachievable. However, it is feasible to design a waveform whose self-ambiguity function is zero at all locations excluding the origin in a connected region C corresponding to the maximum possible support of the scattering Fig. 4 The proposed discrete radar architecture in Fig. 2c achieves perfectly localized "bed-of-nails" ambiguity functions. a The standard approach of phase coding a rectangular waveform [16] in discrete radars (see Fig. 2b) has high sidelobes due to poor ambiguity characteristics of the chosen carrier waveform. (b) Choosing the transmitted waveform as an eigenvector of a maximal commutative subgroup results in "bed-of-nails" ambiguity functions with minimal sidelobes environment 5 , (k, l) ∈ C , (k, l) = (0, 0) . Recall from Corollary 2 that our approach of transmitting an eigenvector of a maximal commutative subgroup T MN yields self- ambiguity functions that are unimodular only at delay-Doppler indices in the set S T MN = (k, l) e j2π MN m D (k,l) ∈ T MN , akin to a "bed-of-nails. " Therefore, we propose to choose T MN such that translates of the maximum scattering environment support C by the elements of S T MN do not overlap: This is the crystallization condition described in [13][14][15] and it implies that an image of the scattering environment can be read off from the response to the radar waveform at delay-Doppler locations within the scattering environment support S . Figure 5 illus- trates how to choose T MN for a given support C.

Another benefit of our proposed discrete radar architecture is that it enables defining waveform libraries with low PAPR. Adaptive radars define libraries of waveforms from which an appropriate waveform is chosen in real-time based on the operational requirement [24][25][26][27]. For instance, it was shown in [24,25] that waveform libraries that rotate and chirp a template waveform maximize the mutual information for tracking applications. The ability to rotate a template waveform has also shown to be useful in sensing scattering environments where the product of the maximum delay and Doppler spreads exceeds the time-bandwidth product BT [31]. At the same time, it is essential to ensure that each waveform in the library can be transmitted at low hardware cost. A standard metric to quantify the hardware cost of a waveform transmission is the PAPR [46], which measures the ratio of the instantaneous power to the average power of a waveform. Waveforms with a large PAPR are undesirable from a hardware perspective since they require high dynamic range components and degrade the efficiency of power amplifiers.

The theory of symplectic transformations presented in Sect. 3.4 enables meeting both objectives, i.e., defines waveform libraries with low PAPR. Recall from Lemma 9 that symplectic transformations rotate the ambiguity functions of their inputs. Moreover, we presented examples of symplectic transformations in Sect. 3.4; the transformation in Example 2 linearly modulates the frequency of the input waveform, and the GDAFT in Example 3 rotates the self-ambiguity of the input waveform. The combination of the two transformations can be used to define a discrete radar waveform library following the principles presented in [24,25]. Figure 6 illustrates how the GDAFT rotates the self-ambiguity function of a pulsone basis element (Lemma 6).

A useful property of the GDAFT is that it maps pulsones to low PAPR waveforms, which have been previously used by the authors for spread carrier communication in [32]. Figure 7 illustrates how the GDAFT maps the "peaky" pulsone waveform (49)

(Fig. 7a) to a constant amplitude waveform (Fig. 7b). Figure 7c plots the complementary cumulative distribution function (CCDF) of the PAPR (in dB) of both waveforms, showing a 5.6 dB reduction in the PAPR on applying the GDAFT.

The final benefit of our proposed discrete radar architecture is the complexity gain in the cross-ambiguity computation over the conventional continuous and discrete radar architectures. As described in Sect. 2.3, radars form an image of the scattering environment by computing the cross-ambiguity function from Definition 2 between the received and transmitted signals. In the following Lemma, we show that the complexity of calculating the cross-ambiguity with our proposed discrete radar architecture in Fig. 2c is only O(BT log T ) = O(MN log N ) when the pulsone basis element from Lemma 6 (or its symplectic transformation) is used as the transmit waveform. In contrast, the complexity of the cross-ambiguity with the continuous and discrete radar architectures in Fig. 2a The cross-ambiguity between two unit-norm MN-periodic sequences x and y , where y is the Zak-OTFS pulsone from Lemma 6, has O(MN log N ) complexity. Moreover, the com- plexity remains unchanged on applying a symplectic transformation to x and y.

Substituting the pulsone from Lemma 6 in Definition 2:

(50) The summation within the parenthesis simply corresponds to an FFT operation, hence for a given k ∈ Z M its value for all l ∈ Z N can be computed in O(N log N ) complexity. Therefore, across all (k, l) ∈ Z M × Z N , the complexity is O(MN log N ).

A direct consequence of the above result in conjunction with Lemma 9 is that the complexity remains O(MN log N ) on applying a symplectic transformation to x and y .

1 Lemma 11 ( [44]) The cross-ambiguity between two unit-norm MN-periodic sequences x and y , where y is an amplitude-, phase-, or frequency-coded waveform, has O(M 2 N 2 ) complexity.

We substitute the general expression for an amplitude-, phase-or frequency-coded waveform [43]:

where z denotes an MN-periodic coding sequence and s(t) denotes the carrier waveform ("chip") with chip duration T c . On sampling (51) at sampling rate 1/T c , we obtain the MN-length sampled waveform:

where y[n] = y(nT c ) and s[nm] = s(nT c -mT c ) . It is assumed that the coding sequence z and the sampled carrier waveform are normalized appropriately such that y is unit-norm.

In the absence of any additional structure on the coding sequence z and the sampled car- rier waveform, the final expression in (53) corresponds to O(M 2 N 2 ) complexity. It has been shown in [35] that the complexity of calculating the cross-ambiguity with a continuous radar architecture based on LFM waveforms is also O(M 2 N 2 ).

We have described an architecture for radar sensing where the radar waveform is formed in the DD domain, converted to the TD for transmission, match filtered on receive, then returned to the DD domain for ambiguity function analysis. The delay and Doppler periods that characterize the radar waveform are determined by the intended delay and Doppler resolution of the radar. We have described how the intended resolution determines a finite group of delay and Doppler shifts, which we have termed the discrete Heisenberg-Weyl group. We have used this discrete group to provide a framework for ambiguity function analysis, replacing the standard framework which is based on the continuous Heisenberg-Weyl group. By choosing the radar waveform to be a common eigenvector of a maximal commutative subgroup of the discrete Heisenberg-Weyl group, every delay and Doppler shift in the subgroup acts on the waveform by multiplication by a complex phase. Our choice of waveform leads to ambiguity functions that are constant on cosets of the maximal commutative subgroup. We have shown that this choice of waveform reduces the complexity of radar signal processing from quadratic to sublinear in the time-bandwidth product. We have also shown that our approach enables defining waveform libraries with small PAPR.