Efficient DFT of Zadoff-Chu Sequences using lmFH Pattern
Fanping Du · 2025
Read Efficient DFT of Zadoff-Chu Sequences using lmFH Pattern by Fanping Du (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23200.txt.
Introduction
Fanping Du, writing alone, presents a 2025 paper on fast Fourier transforms of Zadoff-Chu sequences, signal patterns used in wireless systems. The paper first shows these sequences act as linear micro-frequency hopping symbols. That view gives a clear, visual way to compute their forward and inverse transforms.
From the same view, Du derives a second form for the cumulative sum of the sequences, based on a generalized Gauss sum. The transform of a sequence turns out to be another hopping symbol, with a frequency shift and a phase offset. So the transform can be built from cumulative frequency points, much like normal hopping symbols. The results may speed signal processing that leans on these sequences.
Catalog record
| CREATOR | Fanping Du |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-23200
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient DFT of Zadoff-Chu Sequences using lmFH Pattern Fanping Du Abstract Having established that Zadoff-Chu (ZC) sequences are inherently linear micro-frequency hopping (lmFH) symbols, this paper first presents an intuitive and visual exposition of the computation of the DFT and IDFT of ZC sequences using the lmFH pattern. This yields interesting results. Subsequently, an alternative form for computing the cumulative sum of ZC sequences using the Generalized Quadratic Gauss Sum is introduced. Furthermore, building on the micro-frequency hopping (mFH) concept, this paper shows that the DFT of ZC sequences can be transformed into an lmFH symbol with frequency shift and phase offset. Therefore, the DFT of ZC sequences can be computed via cumulative frequency points, similar to the computation of normal mFH symbols. K eywords ZC sequences \cdot Efficient Computation \cdot lmFH pattern \cdot DFT/IDFT \cdot Generalized Quadratic Gauss Sum 1 Introduction A novel spread-spectrum modulation technique, termed micro-frequency hopping (mFH), has revealed that Zadoff-Chu (ZC) sequences can be interpreted as linear micro-frequency hopping (lmFH) symbols, and thus ZC sequences can also be intuitively and visually represented by the lmFH pattern, as illustrated in Fig. 4 of Ref. [ 1 ] . As is well known, ZC sequences possess several distinctive properties, such as perfect autocorrelation and cross-correlation in both the time and frequency domains [ 2 ] . Moreover, when ZC sequences have prime length, the Discrete Fourier Transform (DFT) of the ZC sequences is a conjugated, scaled, and time-scaled version of itself. This property has improved the computational efficiency of the DFT of ZC sequences greatly [ 3 ] . However, by employing the mFH concept, the computational efficiency of the DFT of ZC sequences can be significantly further enhanced from a completely new perspective. 2 Understanding ZC sequences using lmFH pattern ZC sequences are lmFH symbols in nature. According to the definition of the mFH symbol, where the phase is determined by the cumulative sum of frequency points in the mFH pattern, an lmFH symbol with a slope s , s\not\equiv 0\pmod{P} , and a prime length P can be expressed as: L_{s}(k)=\exp(i2\pi\frac{\sum_{t=0}^{k}s\cdot t}{P}) (1) where L_{s} is the lmFH symbol with slope s , \exp(\cdot) is the exponential function, i=\sqrt{-1} , t are time points in the lmFH pattern, the frequency points f in the lmFH pattern are f=s\cdot t\pmod{P} , and k=0,1,\dots,P-1 . It is evident that the lmFH symbol is the conjugate of the ZC sequence, i.e., L_{s}=Z_{u}^{*} , or L_{-s}=Z_{u} , meaning that the ZC sequences with root u corresponds to an lmFH pattern with slope of -s . Therefore, we use -u to denote the slope of the lmFH pattern. Fig. 1 shows an example of an lmFH pattern with length P=13 and slope s=-u=-3 . Figure 1: lmFH pattern with P13 & u3 Furthermore, according to the definition of micro-frequency hopping cyclic frequency shift (mFHCFS) modulation [ 1 ] , an lmFH symbol with a frequency shift F_{s} can be expressed as: L_{-u}(k)=\exp(i2\pi\frac{\sum_{t=0}^{k}(-u\cdot t+F_{s}^{\prime})}{P}) (2) Note: Here, F_{s}^{\prime}=F_{s} when t\neq 0 ; otherwise, F_{s}^{\prime}=0 to avoid introducing an extra initial phase. Unless otherwise specified, in this paper, when expressing ZC sequences in the form of lmFH symbols, the F_{s} used refers to F_{s}^{\prime} . Then an lmFH symbol with a frequency shift F_{s} and a phase offset P_{o} can be expressed as: L_{-u}(k)=\exp(i(2\pi\frac{\sum_{t=0}^{k}(-u\cdot t+F_{s})}{P}+P_{o})) (3) On the other hand, Eqs. 4 and 12 in Ref. [ 3 ] demonstrate that the DFT of a ZC sequences with prime length P and root u can be formulated as the conjugate and frequency shift of a dual ZC sequences with root u^{-1} , scaled by a constant factor: F_{u}(k)=Z_{u^{-1}}^{*}(k)\cdot e^{i2\pi\frac{2^{-1}(1-u^{-1})k}{P}}\cdot F_{u}(0) (4) where u^{-1} is the inverse of u modulo P , i.e., u\cdot u^{-1}\equiv 1\pmod{P} , 2^{-1} is the inverse of 2 modulo P , equals to \frac{P+1}{2} , ∗ means conjugate, Z_{u^{-1}}^{*}(k)=e^{i\pi\frac{u^{-1}k(k+1)}{P}} , F_{u} is the DFT of Z_{u} , and F_{u}(0)=\sum_{n=0}^{P-1}Z_{u}(n) . According to Eq. 2 , it can be expressed in the form of lmFH symbols with a frequency shift as: F_{u}(k)=\exp(i2\pi\frac{\sum_{t=0}^{k}(u^{-1}\cdot t+\frac{P+1}{2}(1-u^{-1}))}{P})\cdot F_{u}(0) (5) And, according to Eq. 3 it can be expressed with a phase offset as: F_{u}(k)=\exp(i(2\pi\frac{\sum_{t=0}^{k}(u^{-1}\cdot t+\frac{P+1}{2}(1-u^{-1}))}{P}+\angle{F_{u}(0)}))\cdot|F_{u}(0)| (6) Or, further expressed as: F_{u}(k)=\exp(-i(2\pi\frac{\sum_{t=0}^{k}(-u^{-1}\cdot t+\frac{P+1}{2}(u^{-1}-1))}{P}-\angle{F_{u}(0)}))\cdot|F_{u}(0)| (7) Thus, if we can obtain the argument \angle{F_{u}(0)} and magnitude |F_{u}(0)| of F_{u}(0) , we can rapidly derive the DFT of ZC sequences using Eq. 7 based on the principle of mFH. Before delving into this, we first present an intuitive and visual exposition of the DFT of ZC sequences using lmFH patterns. 2.1 Visual DFT of ZC sequences using lmFH pattern In this subsection, we use the lmFH pattern to intuitively and visually demonstrate why the DFT of ZC sequences in Eq. 4 is associated with the conjugate of a dual ZC sequences whose root is the inverse, along with a frequency shift. In the first step, we illustrate the DFT of ZC sequences by flipping the lmFH pattern across the line f=t , thereby transforming the time domain to the frequency domain, as shown in Fig. 2 . In a time-frequency plane, flipping a point (t,f) across f=t yields the coordinates (f,t) , formalized by the matrix equation: \begin{pmatrix}t\\ f\end{pmatrix}\to\begin{pmatrix}f\\ t\end{pmatrix}=\underbrace{\begin{pmatrix}0&1\\ 1&0\end{pmatrix}}_{\sigma_{x}}\begin{pmatrix}t\\ f\end{pmatrix} Figure 2: DFT of ZC (reverse side) with P13 & u3 The flipping matrix has a determinant of -1 , indicating that the "flip" not only transposes the lmFH pattern by swapping t and f , but also reverses the side of the lmFH pattern due to the determinant’s sign. The transposition of the lmFH pattern causes its slope to transform from -u\propto\frac{f}{t} to its inverse -u^{-1}\propto\frac{t}{f} , while the side reversal induces a right-handed to left-handed coordinate system change, corresponding to complex conjugation. These explain why the DFT of Z_{u} is associated with the conjugate of Z_{u^{-1}} , as shown by \mathcal{F}\{Z_{u}\}\propto Z_{u^{-1}}^{*} . Interestingly, as an extra mathematical result , Fig. 1 and Fig. 2 present a novel visualization method for obtaining multiplicative inverses, which maps the algebraic inverse operation to flipping the lmFH pattern in the time-frequency plane. Subsequently, we further analyze the origin of frequency shift using Fig. 2 and Fig. 1 . Obviously, the first frequency point in Fig. 2 is not at the zero frequency point. Since the lmFH pattern is obtained by flipping Fig. 1 across the line f=t , the first frequency point in Fig. 2 corresponds to the most negative frequency point in Fig. 1 , whose time value t satisfies t\cdot-u\equiv-\frac{P-1}{2}\pmod{P} . By solving the congruence relation t\cdot u\equiv\frac{P-1}{2}\pmod{P} , we derive the explicit solution for t , t\equiv\frac{P-1}{2}u^{-1}\pmod{P} . The value t equals the frequency points difference between the first frequency point and the most negative frequency point in Fig. 2 . Thus, the frequency shift F_{s} of the first frequency point is given by: F_{s}=t+(-\frac{P-1}{2}) , further derivation yields: F_{s}\equiv\frac{P-1}{2}(u^{-1}-1)\pmod{P} , or F_{s}\equiv\frac{P+1}{2}(1-u^{-1})\pmod{P} as in Eq. 4 . Thus, through the first step of flipping the lmFH pattern across the line f=t , we can intuitively and visually explain why the DFT of the ZC sequences is associated with the conjugate of Z_{u^{-1}} and a frequency shift F_{s} , as shown by \mathcal{F}\{Z_{u}(k)\}\propto Z_{u^{-1}}^{*}(k)\cdot e^{i2\pi\frac{\frac{P+1}{2}(1-u^{-1})k}{P}} . In the second step, we further flip