高斯整数是实部和虚部都为整数的复数，元素为高斯整数的序列被称为高斯整数序列.实际应用的大部分序列是元素取自有限域或环的序列.序列的级定义为序列一个周期内不同非零元素的个数.在已有高斯整数序列的构造^[1-7]中，仅文献[2, 5]和[6]中构造了p级序列，但其序列中元素不能在指定域内取值，文献[7]中序列为p－1级序列，序列仅为几乎完备序列.

对于给定的奇素数p=4f+1=ππ^*，分别基于m-序列和GMW (Gordon-Mills-Welch) 序列构造了p元完备或几乎完备的高斯整数序列，序列中元素在由素数p确定的高斯整数剩余类G_π中取值，序列长度为 (pⁿ－1)/(p－1) 的整数倍.

1 基本概念

令p为素数，下面介绍要用到的符号和概念.

1) F_q为包含q个元素的有限域，q为素数幂.

2) F_q^k={(a₀, a₁, …, a_k－1)|a_i∈F_q, 0≤i≤k－1}为F_q上的k元向量，k为整数.

3) Z_m={j mod m:0≤j≤m－1}为模m的剩余类.

4) G为所有高斯整数的集合，G_π为对集合G中元素进行模π运算后的剩余类，这里模函数μ(·) 定义为

$ \begin{array}{*{20}{c}} {\mu \left( g \right) = g\bmod \pi = \gamma = g - \left[ {\frac{{g{\pi ^ * }}}{{\pi {\pi ^ * }}}} \right]\pi ,}\\ {g \in G,\gamma \in {G_\pi }} \end{array} $

(1)

其中[·]为对复数取整运算.模函数μ(·) 定义了从F_p到G_π的同构映射.显然μ(x+y)=μ(x)+μ(y)，μ(xy)=μ(x)μ(y) 和 (μ(g))^*=μ(g^*) 成立.高斯整数集G模π的剩余类G_π和有限域F_p在数学上是等价的.

5) ${\rm{Tr}}_m^n\left( x \right) = \sum\limits_{i = 0}^{n/m-1} {{x^{{q^{im}}}}} $为从扩展域F_qⁿ到有限域F_q^m的迹函数，其中m和n为正整数，且m整除n.当m=1时，常简记为Tr (x).

6) log _βx为对数 (指标) 函数，对F_q中元素x，定义为

$ {\log _\beta }x = \left\{ \begin{array}{l} k, x = {\beta ^k}, 0 \le k \le q - 2\\ 0, x = 0 \end{array} \right. $

(2)

其中β为有限域F_q的本原元.

7) $C\left( \tau \right) = \sum\limits_{k = 0}^{N-1} {s\left( k \right)s*} \left( {k + \tau } \right)$是周期为N的序列S={s(k)}的周期自相关函数，其中s^*(k) 为s(k) 的复共轭，k+τ为模N加法.

2 序列构造

设p=4f+1为奇素数，则存在高斯素数π=a+bi，使p可表示为p=a²+b²=(a+bi)(a－bi)=ππ^*的形式.设φ为G_π中阶为p－1的元素，那么G_π可表示为G_π={0, 1, φ, φ², …, φ^p－2}.

构造1   假设n和s都为正整数，且满足gcd (s, pⁿ－1)=1.设{a(k)}为有限域F_p上周期为L=pⁿ－1的m-序列，则

$ a\left( k \right) = {\rm{Tr}}\left( {{\alpha ^{sk}}} \right),k = 0,1, \cdots ,{p^n} - 2 $

(3)

其中α为F_pⁿ的本原元.定义序列{b(k)}为

$ b\left( k \right) = \left\{ \begin{array}{l} {\varphi ^{k + {{\log }_\beta }\left( {a\left( k \right)} \right)}}, a\left( k \right) \ne 0,0 \le k \le {p^n} - 2\\ 0, 其他 \end{array} \right. $

(4)

其中：$\beta = {\alpha ^d}, d = \frac{{{p^n}-1}}{{p-1}}$.于是，得到G_π上的高斯整数序列{s(k)}，这里s(k) 定义为

$ s\left( k \right) = \mu \left( {b\left( k \right)} \right), k = 0,1, \cdots {p^n} - 2 $

(5)

定理1   设n和s为满足gcd (s, pⁿ－1)=1的正整数，且

$ \left( {n + s} \right) \equiv 0\left( {\bmod p - 1} \right) $

(6)

那么由式 (5) 定义的序列{s(k)}具有如下性质：

1) 周期为N=d，其中$d = \frac{{{p^n}-1}}{{p-1}}$；

2) 具有完备的周期自相关值，自相关值函数分布为

$ C\left( \tau \right) = \left\{ \begin{array}{l} \frac{{{p^{n - 1}}}}{{p - 1}}E, \tau = 0\\ 0, 其他 \end{array} \right. $

(7)

其中$E = \sum\limits_{g \in {G_\pi }\backslash \left\{ 0 \right\}} {\mu \left( {g{g^*}} \right)} $为G_π中符号的总能量.

证明  显然序列{s(k)}的周期N必然整除m-序列{a(k)}的周期L.因此首先计算时间间隔L上序列{s(k)}的自相关值函数为

$ \begin{array}{*{20}{c}} {C'\left( \tau \right) = \sum\limits_{k = 0}^{L - 1} {s\left( k \right){s^ * }\left( {k + \tau } \right)} = }\\ {\sum\limits_{\begin{array}{*{20}{c}} {s\left( k \right) \ne 0}\\ {s\left( {k + \tau } \right) \ne 0}\\ {k = 0} \end{array}}^{L - 1} {s\left( k \right){s^ * }\left( {k + \tau } \right)} } \end{array} $

(8)

时间间隔L上序列{s(k)}的自相关值函数C′(τ) 的计算，分以下2种情形讨论.

1) 当τ≠0(mod d) 时.根据m-序列的二重平衡性质，当k遍历Z_pⁿ－1中元素时，(a(k), a(k+τ)) 取到F_p²中每一对非零元素对恰好p^n－2次.从而可得

$ \begin{array}{*{20}{c}} {C'\left( \tau \right) = \sum\limits_{\begin{array}{*{20}{c}} {s\left( k \right) \ne 0}\\ {s\left( {k + \tau } \right) \ne 0}\\ {k = 0} \end{array}}^{L - 1} {\mu \left( {{\varphi ^{k + {{\log }_\beta }\left( {a\left( k \right)} \right)}}} \right){{\left( {\mu \left( {{\varphi ^{k + \tau + {{\log }_\beta }\left( {a\left( {k + \tau } \right)} \right)}}} \right)} \right)}^ * }} = }\\ {{p^{n - 2}}\sum\limits_{i = 0}^{p - 2} {\mu \left( {{\varphi ^i}} \right)} \sum\limits_{j = 0}^{p - 2} {{{\left( {\mu \left( {{\varphi ^j}} \right)} \right)}^ * }} = }\\ {{p^{n - 2}}\mu \left( {\sum\limits_{g \in {G_\pi }\backslash \left\{ 0 \right\}} g } \right){{\left[ {\mu \left( {\sum\limits_{g \in {G_\pi }\backslash \left\{ 0 \right\}} {g'} } \right)} \right]}^ * } = 0} \end{array} $

(9)

最后1个等式成立是因为G_π中所有元素之和恰好为0.

2) 当τ=0(mod d) 时，存在某个j(0≤j≤p－1)，使τ=jd.此时，由于gcd (s, pⁿ－1)=1，显然a(k+τ)=a(k+jd)=Tr (α^s(k+jd))=β^jsa(k).于是 (a(k), a(k+τ))=(a(k), β^jsa(k))=(g, β^jsg)，其中g为F_p中任意元素.在m-序列一个周期中，F_p中任意非零元素恰好出现p^n－1次.经过基本的对数运算，周期自相关函数C′(τ) 可写为

$ \begin{array}{*{20}{c}} {C'\left( \tau \right) = \sum\limits_{\begin{array}{*{20}{c}} {a\left( k \right) \ne 0}\\ {k = 0} \end{array}}^{L - 1} {\mu \left( {{\varphi ^{k + {{\log }_\beta }\left( {a\left( k \right)} \right)}}} \right){{\left( {\mu \left( {{\varphi ^{k + jd + js + {{\log }_\beta }\left( {a\left( k \right)} \right)}}} \right)} \right)}^ * }} = }\\ {{p^{n - 1}}\sum\limits_{i = 0}^{p - 2} {\mu \left( {{\varphi ^i}{{\left( {{\varphi ^i}{\varphi ^{j\left( {d + s} \right)}}} \right)}^ * }} \right)} = }\\ {{p^{n - 1}}\sum\limits_{g \in {G_\pi }\backslash \left\{ 0 \right\}} {\mu \left( {g{{\left( {{\varphi ^{j\left( {d + s} \right)}}g} \right)}^ * }} \right)} = }\\ {{p^{n - 1}}\mu \left( {{{\left( {{\varphi ^{j\left( {d + s} \right)}}} \right)}^ * }} \right)E} \end{array} $

(10)

结合情形1) 和情形2)，可得时间间隔L上序列的相关值分布，下面计算序列{s(k)}的周期.由于

$ d = \frac{{{p^{n - 1}}}}{{p - 1}} = 1 + p + \cdots {p^{n - 1}} = n\bmod \left( {p - 1} \right) $

(11)

因此

$ d + s = n + s\left( {\bmod p - 1} \right) $

(12)

由假设 (n+s)≡0(mod p－1) 知对于每一个j都有φ^j(d+s)=1，于是有s(k+jd)=s(k).从而，得到序列{s(k)}周期为N=d，且序列具有完备的周期自相关值.确切地说，序列{s(k)}的周期自相关值为

$ C\left( \tau \right) = \frac{N}{L}C'\left( \tau \right) = \left\{ \begin{array}{l} \frac{{{p^{n - 1}}}}{{p - 1}}E, \tau = 0\\ 0, 其他 \end{array} \right. $

(13)

证毕.

对于给定的素数p，高斯整数剩余类G_π中元素与复平面的点一一对应，在通信术语中称G_π的二维可视化图形为信号星座.构造1得到的序列正是信号星座中元素构成的序列，通过选择满足条件的参数n和s，可得不同的完备序列.

例1   设p=5，则π=2+i.接下来在高斯整数剩余类G_2+i={0, i, －i, 1, －1}上利用构造1构造完备高斯整数序列.当n=3时，可分别取s=1, 9, 13, …得到具有相同周期N=31和周期自相关值C(0)=25，C(τ)=0, 1≤τ≤30的循环不等价完备高斯整数序列，结果如表 1所示.

当p=5时，对应的高斯整数剩余类G_2+i={0, i, －i, 1, －1}中非零元素恰好为单位圆的复数根，此时构造的序列与文献[8]中所构造的5-元复数序列相同.构造1可通过选择参数n和s得到具有不同周期和相关值的序列，灵活性更高.当p>5时，相应的高斯整数剩余类集合G_π中非零元素不再是单位圆的复数根，此时构造1所构造的序列与文献[8]中序列不同，后者构造序列为复数序列.

当p=13时，在高斯整数剩余类G_3+2i={0, 1, 1+i, 2i, －i, 1－i, 2, －1, －1－i, －2i, i, －1+i, －2}上，当n=5时，s=7, 19, …满足定理1的条件.

在某些特定场合中，不是所有的异相自相关值都会用到，这就促使人们对几乎完备序列的研究.利用构造1将条件放宽可得几乎完备的高斯整数序列.

推论1   设l为使

$ l\left( {n + s} \right) \equiv 0\left( {\bmod p - 1} \right) $

(14)

成立的最小正整数，且1 < l≤p－1.那么由式 (5) 构造的序列{s(k)}为几乎完备的高斯整数序列，其周期为ld=l(pⁿ－1)/(p－1)，其周期自相关函数值仅在τ=jd, 0≤j≤p－1处可能取得非零值为

$ C\left( {jd} \right) = \frac{{{p^{n - 1}}\left( {p - 1} \right)}}{{l\left( {{p^{n - 1}}} \right)}}\mu \left( {{{\left( {{\varphi ^{j\left( {d + s} \right)}}} \right)}^ * }} \right)E $

且总共最多有l个非零值.

证明   由于推论1仅将定理1中条件式 (6) 推广到条件式 (14)，所以其证明过程仅需说明条件式 (6) 的改变带来的影响.

根据式 (11)、式 (12) 和式 (14) 可知，当τ=jd，0≤j≤p－1时，有φ^j(d+s)≠1，此时序列{s(k)}的周期自相关值为

$ C\left( {jd} \right) = \frac{N}{L}C'\left( \tau \right) = \frac{{{p^{n - 1}}\left( {p - 1} \right)}}{{l\left( {{p^{n - 1}}} \right)}}\mu \left( {{{\left( {{\varphi ^{j\left( {d + s} \right)}}} \right)}^ * }} \right)E $

证毕.

构造1′   在构造1中，将m-序列{a(k)}替换为GMW序列{a₁(k)}，其中

$ {a_1}\left( k \right) = {\rm{Tr}}_1^m\left( {{{\left[ {{\rm{Tr}}_m^n\left( {{\alpha ^{sk}}} \right)} \right]}^r}} \right),k = 0,1, \cdots ,{p^n} - 2 $

(15)

其中：α为F_pⁿ的本原元，m和n为正整数，且m|n；r、s都为正整数，且满足gcd (s, pⁿ－1)=1，gcd (r, p^m－1)=1，gcd (sr, p^m－1)=1和1≤r≤p^m－2，将a₁(k) 代入式 (4) 和式 (5) 中得新的序列{s₁(k)}.

定理2   设m和n为正整数，且m|n，r, s为正整数，且满足gcd (s, pⁿ－1)=1，gcd (r, p^m－1)=1，gcd (sr, p^m－1)=1和 (n+sr)≡0(mod p－1).那么上述构造1′中定义的序列{s₁(k)}是周期为 (pⁿ－1)/(p－1) 的完备周期序列.

证明   利用GMW序列的二重平衡性质，证明方法与定理1类似，且序列的周期自相关值为

$ C\left( \tau \right) = \left\{ \begin{array}{l} \frac{{{p^{n - 1}}}}{{p - 1}}E, \tau = 0\\ 0, 其他 \end{array} \right. $

证毕.

构造1′比构造1更具一般性，当r=1时构造1′即为构造1.可以确定，当p=5时，取n=9, m=3，此时满足定理2中条件的参数对有 (s, r)=(1, 3), (1, 7), (3, 1), (3, 5), ….

3 结束语

将文献[8]在复数循环群中取值的p元序列的构造方法加以扩展，并增加了模函数的复合过程，进而得到高斯整数剩余类上的序列.基于m-序列和GMW序列的二重平衡性质，利用复合映射构造了长度为 (pⁿ－1)/(p－1) 的p－1级完备高斯整数序列和长度为 (pⁿ－1)/(p－1) 的整数倍的几乎完备高斯整数序列.对于给定的素数p=4f+1，新构造的序列为p元序列，可在相应的信号星座图中取值，符号集容量较已有的多数高斯整数序列更大，参数更灵活.