1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//! Binary pseudo-random sequences (linear-feedback shift registers, the length-31 Gold
//! sequence of 3GPP) and the Zadoff–Chu sequences.
//!
//! # Model
//!
//! A Fibonacci register of order $r$ produces $x(i + r) = \sum_{t \in T} x(i + t) \bmod 2$
//! from its first $r$ bits ([`lfsr`]): every m-sequence and Gold sequence of the
//! standards is one or a sum of two. The pseudo-random sequence of 3GPP (TS 38.211,
//! Sec. 5.2.1; TS 36.211, Sec. 7.2) is
//!
//! $$
//! c(n) = \left(x_{1}(n + N_{c}) + x_{2}(n + N_{c})\right) \bmod 2, \qquad N_{c} = 1600,
//! $$
//!
//! with $x_{1}(n+31) = (x_{1}(n+3) + x_{1}(n)) \bmod 2$, $x_{1}(0) = 1$,
//! $x_{1}(1..30) = 0$, and $x_{2}(n+31) = (x_{2}(n+3) + x_{2}(n+2) + x_{2}(n+1) +
//! x_{2}(n)) \bmod 2$ initialised by $c_{\mathrm{init}} = \sum_{i} x_{2}(i) 2^{i}$
//! ([`gold_3gpp`]): the scrambling of the coded bits and the sequences of the reference
//! signals.
//!
//! The Zadoff–Chu sequence of root $u$ and odd length $N_{\mathrm{ZC}}$ ([`zadoff_chu`]),
//!
//! $$
//! x_{u}(n) = e^{-j\pi u n (n + 1) / N_{\mathrm{ZC}}}, \qquad 0 \le n < N_{\mathrm{ZC}},
//! \quad \gcd(u, N_{\mathrm{ZC}}) = 1,
//! $$
//!
//! has a constant amplitude and a zero periodic autocorrelation at every nonzero lag
//! (a CAZAC sequence; Chu 1972), and two roots $u_{1} \ne u_{2}$ with $u_{1} - u_{2}$
//! prime to a prime $N_{\mathrm{ZC}}$ cross-correlate with the constant magnitude
//! $1/\sqrt{N_{\mathrm{ZC}}}$: the primary synchronisation signal of LTE (TS 36.211,
//! Sec. 6.11.1.1, $N_{\mathrm{ZC}} = 63$, its middle element punctured) and the
//! preambles of the random access.
//!
//! # Examples
//! ```
//! use comnum_math::sequences::{gold_3gpp, lfsr};
//! // x³ + x + 1: the m-sequence of period 7
//! assert_eq!(lfsr(&[0, 1], 3, &[1, 0, 0], 10), vec![1, 0, 0, 1, 0, 1, 1, 1, 0, 0]);
//! assert_eq!(gold_3gpp(0, 8).len(), 8);
//! let x = comnum_math::sequences::zadoff_chu(25, 63)?;
//! assert!(x.iter().all(|v| (v.norm() - 1.0).abs() < 1e-12));
//! # Ok::<(), comnum_core::Error>(())
//! ```
//!
//! # References
//!
//! 1. 3GPP TS 38.211, *NR; Physical channels and modulation*, Sec. 5.2.1.
//! 2. 3GPP TS 36.211 V18.0.2, *E-UTRA; Physical channels and modulation*, Sec. 6.11.1.1, 7.2.
//! 3. D. Chu, "Polyphase codes with good periodic correlation properties," *IEEE Trans.
//! Inf. Theory* 18(4), 531–532, 1972.
use crateC64;
use ;
/// The sequence of a linear-feedback shift register of order `order`: the first
/// `order` bits are `init` (zero-padded), then $x_{i + \mathrm{order}} = \sum_{t} x_{i + t}
/// \bmod 2$ over the `taps`, up to `len` bits in all (the Fibonacci form of every
/// m-sequence, Gold sequence and PRBS of the standards).
///
/// # Examples
/// ```
/// use comnum_math::sequences::lfsr;
/// // x³ + x + 1: the m-sequence of period 7
/// let x = lfsr(&[0, 1], 3, &[1, 0, 0], 10);
/// assert_eq!(x, vec![1, 0, 0, 1, 0, 1, 1, 1, 0, 0]);
/// ```
/// The first `n` bits of the Gold sequence $c$ of 3GPP with the initial value `c_init`
/// (31 bits; see the module).
/// The Zadoff–Chu sequence $x_{u}(n) = e^{-j\pi u n (n + 1) / N_{\mathrm{ZC}}}$ of root `u`
/// and odd length `n_zc` (see the module).
///
/// # Errors
/// [`comnum_core::Error::Config`] for an even or zero length, or a root that is zero
/// modulo $N_{\mathrm{ZC}}$ or not prime to it.
///
/// # Examples
/// ```
/// use comnum_math::sequences::zadoff_chu;
/// let x = zadoff_chu(29, 63)?;
/// // zero periodic autocorrelation at every nonzero lag
/// let r: comnum_math::C64 = (0..63).map(|n| x[n] * x[(n + 5) % 63].conj()).sum();
/// assert!(r.norm() < 1e-9);
/// # Ok::<(), comnum_core::Error>(())
/// ```