一类II型偶长Z-互补序列对的构造

Construction of Even-Length Type II Z-Complementary Pairs

摘要: 文章以二进制互补对的核为基础，利用Turyn构造法得到一种长度为$N=2^{\alpha }{10}^{\beta }{26}^{\gamma }$ ($\alpha ,\beta ,\gamma$ 为非负整数)的Golay互补对(Golay Complementary Pair, GCP)，在此基础上利用级联和删除函数得到长度为II型$2N-2$ 的偶长Z-互补对，并且它们非周期相关函数和在零相关区外的幅值为4，丰富了II型偶长Z-互补序列对的数量。与已知传统的序列构造方法相比，文章提出了一种新的构造方法。

Abstract: Based on the kernel of binary complementary pairs, a Golay Complementary Pair (GCP) with a sequence length of $N=2^{\alpha }{10}^{\beta }{26}^{\gamma }$ (and $\alpha ,\beta ,\gamma$ are non-negative integers) was constructed by using Turyn Construction. On this basis, the Deletion Function and Cascading were used to obtain the Type II EB-ZCP with a length of $2N-2$ , and their aperiodic correlation functions and amplitudes outside the zero-correlation region were 4, which enriches the number of Type II EB-ZCP. Compared with the known traditional sequence construction methods, a new construction method is proposed.

1. 引言

零相关区互补序列在通信系统[1] [2]、雷达[3]、信道估计[4]等领域有着重要应用。特别地，II型Z-互补对(Z-Complementary Pair, ZCP)在宽带无线通信系统中可解决最小干扰信号延迟的抑制问题。互补对又称格雷互补对[5] (Golay Complementary Pair, GCP)，在序列设计中已经被广泛应用。因此，ZCPs对于无线通信系统的研究具有十分重要的意义。

2007年，Fan [6]等人首次提出了Z-互补对(Z-Complementary Pairs, ZCPs)的概念。2021年，Gu等人[7]通过Turyn构造了长度为3N和14N的Z-最优II型偶长ZCP。同年，文献[7]通过迭代法还构造了一类有新长度的II型偶长ZCP，其参数为$\left(2^{k}N+2^{k-1},2^{k}N+2^{k-1}-N\left(N\in Z,k\ge 2\right)\right)$ $2^{k}N+2^{k-1}-N\left(N\in Z,k\ge 2\right)$ 。2021年，Kumar等人[8]通过多变量函数，构造了一类II型偶长ZCP，其长度为$\left(2^{m}P,2^{m}P+\text{1}-P\left(m,P\ge 1\right)\right)$ ，此构造可以满足任意II型偶长ZCP的长度。2022年，Peng等人[9]基于布尔函数，构建了长度为$\left(2^m+3+2^m+2+2^m+1,2^m+3+2^m+2\right)$ 的II型偶长ZCP，其相关区比率6/7。2023年，Zeng等人[10]通过映射和交织的方法得到一类长度为$2\times 2^{\alpha }{10}^{\beta }{26}^{\gamma }$ 的Z-最优II型偶长ZCP。2023年，陈等人[11]通过迭代技术，构造了长度分别为$\left(2^{k+2}N,\left(2^{k+2}-1\right)N\right)$ 、$\left(2N+2,\frac{3N}{2}+2\right)$ 和$\left(2^{k+2}N+2^{k+1},2^{k+2}N+2^{k+1}-\frac{N}{2}\right)$ 的II型偶长ZCP，且零相关区外相关函数值较小。2023年，陈等人[12]通过交织法构造了长度为$\left(\left(2k+1\right)N,\left(2k+1\right)N-k\right)$ 的II型偶长ZCP，其零相关区宽度可以接近或达到II型偶长二进制Z-互补对的理论上界。2023年，陈等人通过插入法构造了长度为$\left(2N+2,\frac{3}{2}N+2\right)$ 的II型偶长ZCP。综上所述，构造出长度更为灵活的II型EB-ZCPs具有重要的意义和价值。

本文结构如下：第二节介绍了一些需要用到的符号与定义；第三节给出了II型偶长Z-互补序列对的构造，证明与实例；第四节对本文进行了总结。

2. 预备知识

本文中的一些符号表示如下：

+和−分别表示+1和−1；

$a\otimes b$ 表示$a$ 和$b$ 的克罗内克积；

$a\left|\right|b$ 表示$a$ 与$b$ 的级联。

定义1 对于一个长度为N的二进制序列对$\left(a,b\right)$ ，定义非周期互相关函数(ACCF)

${\rho }_{a,b}\left(\tau \right)={\displaystyle \sum _{i=0}^{N-1-\tau }{a}_i{b}_{i+\tau }}\text{, 0}\le \tau \le N-1$ 。

当$a=b$ ，${\rho }_{a,b}\left(\tau \right)$ 被称之为非周期自相关函数(AACF)，记为${\rho }_a\left(\tau \right)$ 。

定义2 令$a$ 和$b$ 为两条长度为N的二进制序列，若对任意$\text{1}\le \tau \le N-1$ ，且序列对$\left(a,b\right)$ 满足

${\rho }_a\left(\tau \right)+{\rho }_b\left(\tau \right)=0,$

则称序列对$\left(a,b\right)$ 为格雷互补对(GCP)。

引理1 如果$\left(a,b\right)$ 是长度为N、ZCZ宽度为Z的II型EB-ZCP，则

$Z\le N-1$ 。

定义3 如果上式可以取等号，则称$\left(a,b\right)$ 达到Z-最优，即II型EB-ZCP的ZCZ宽度的理论上界为$Z=N-1$ 。

引理2 [13]当

$\left(a_0;b_0\right)=K_2$ ；

$\left(a_i;b_i\right)=Turyn\left(A_0,\left(a_{i-1};b_{i-1}\right)\right),A_0\in \left\{K_2,K_{10},K_{26}\right\},$

则$\left(a;b\right)=\left(a_i;b_i\right)$ 是长度为$N=2^{\alpha }{10}^{\beta }{26}^{\gamma }$ ($\alpha \ge 1,\beta ,\gamma \ge 0$ 且为整数的GCP)，并且$\left(a_i;b_i\right)$ 该序列对的前$N/2$ 项每列都具有相同的符号。

3. 构造

定理1 设序列对$\left(a,b\right)$ 是由引理2生成的长度为N的GCP，构造序列对$\left(c,d\right)$ ，$c=\left(a\parallel \overleftarrow{b}\right)$ ，$d=\left(b\parallel -\overleftarrow{a}\right)$ ，$\left(r_1,r_2\right)=\left(0,2N-1\right)$ 或$\left(r_1,r_2\right)=\left(\frac{N}{2}-1,\frac{N}{2}\right)$ ，$e\equiv \upsilon \left(c,r_1,r_2\right)$ ，$f\equiv \upsilon \left(d,r_1,r_2\right)$ ，其中$\upsilon (\cdot )$ 是删除函数。则序列对$\left(e,f\right)$ 是II型偶长Z-互补序列对，参数是$\left(2N-2,\frac{3}{2}N-1\right)$ ，并且在零相关区外的幅值为4。

证明 令$a=\left(a_0,a_1,\cdots ,a_{N-1}\right)$ 和$b=\left(b_0,b_1,\cdots ,b_{N-1}\right)$ 是一个长度为$N=2^{\alpha }{10}^{\beta }{26}^{\gamma }$ 的GCP，并且它满足$\alpha \ge 1$ ，$\beta ,\gamma \ge 0$ ，$\alpha ,\beta ,\gamma$ 为非负整数。根据删除函数的定义：

1) 当$r_1=0,r_2=2N-1$ ，可以得到$\left(e,f\right)$ ，即

$\begin{array}{l}e=\left(e_0,e_1,\cdots ,e_{N-1}\right)=\left(a_1,a_2,\cdots ,a_{N-1},b_{N-1},b_{N-2},\cdots ,b_1\right)\\ f=\left(f_0,f_1,\cdots ,f_{N-1}\right)=\left(b_1,b_2,\cdots ,b_{N-1},-a_{N-1},-a_{N-2},\cdots ,-a_1\right)\end{array}$

根据$\tau$ 取值范围分下面三种情形讨论$\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|$ ：

情形1：当$N-1\le \tau \le 2N-3$ 时，

$\begin{array}{l}{\rho }_e\left(\tau \right)={\displaystyle \sum _{i=1}^{N-1}{a}_i{b}_{2N-\tau -i-1}}\\ {\rho }_f\left(\tau \right)={\displaystyle \sum _{i=1}^{N-1}{b}_i\left(-a_{2N-\tau -i-1}\right)}\end{array}$

有

$\begin{array}{l}\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|=\left|{\displaystyle \sum _{i=1}^{N-1}{a}_i{b}_{2N-\tau -i-1}}{\displaystyle \sum _{i=1}^{N-1}{b}_i\left(-a_{2N-\tau -i-1}\right)}\right|\\ =0\end{array}$

情形2：当$\frac{N}{2}\le \tau \le N-2$ 时，

$\begin{array}{l}{\rho }_e\left(\tau \right)={\displaystyle \sum _{i=1}^{N-\tau -1}{a}_i{a}_{i+\tau }}+{\displaystyle \sum _{i=N-\tau }^{N-1}{a}_i{b}_{2N-\tau -i-1}}+{\displaystyle \sum _{i=1}^{N-\tau -1}{b}_i{b}_{i+\tau }}\\ {\rho }_f\left(\tau \right)={\displaystyle \sum _{i=1}^{N-\tau -1}{b}_i{b}_{i+\tau }}+{\displaystyle \sum _{i=N-\tau }^{N-1}{b}_i\left(-a_{2N-\tau -i-1}\right)}+{\displaystyle \sum _{i=1}^{N-\tau -1}{a}_i{a}_{i+\tau }}\end{array}$

因为${\rho }_a\left(\tau \right)+{\rho }_b\left(\tau \right)=0$ ，根据引理2知，$\left(a,b\right)$ 在$0\le i<\frac{N}{2}$ 时，$a_i=b_i$ ；在$\frac{N}{2}\le i<N$ 时，$a_i=-b_i$ ，所以

$\begin{array}{l}\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|=\left|{\displaystyle \sum _{i=N-\tau }^{N-1}{a}_i{b}_{2N-\tau -i-1}}+{\displaystyle \sum _{i=N-\tau }^{N-1}{b}_i\left(-a_{2N-\tau -i-1}\right)}-2a_0{a}_{\tau }-2b_0{b}_{\tau }\right|\\ =\left|-2a_0\left(a_{\tau }+b_{\tau }\right)\right|\\ =0\end{array}$

情形3：当$1\le \tau \le \frac{N}{2}-1$ 时，

$\begin{array}{l}{\rho }_e\left(\tau \right)={\displaystyle \sum _{i=1}^{N-\tau -1}{a}_i{a}_{i+\tau }}+{\displaystyle \sum _{i=N-\tau }^{N-1}{a}_i{b}_{2N-\tau -i-1}}+{\displaystyle \sum _{i=1}^{N-\tau -1}{b}_i{b}_{i+\tau }}\\ {\rho }_f\left(\tau \right)={\displaystyle \sum _{i=1}^{N-\tau -1}{b}_i{b}_{i+\tau }}+{\displaystyle \sum _{i=N-\tau }^{N-1}{b}_i\left(-a_{2N-\tau -i-1}\right)}+{\displaystyle \sum _{i=1}^{N-\tau -1}{a}_i{a}_{i+\tau }}\end{array}$

因为${\rho }_a\left(\tau \right)+{\rho }_b\left(\tau \right)=0$ ，根据引理2知，$\left(a,b\right)$ 在$0\le i<\frac{N}{2}$ 时，$a_i=b_i$ ，所以

$\begin{array}{l}\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|=\left|{\displaystyle \sum _{i=N-\tau }^{N-1}{a}_i{b}_{2N-i-\tau -1}}+{\displaystyle \sum _{i=N-\tau }^{N-1}{b}_i\left(-a_{2N-i-\tau -1}\right)-2a_0{a}_{\tau }-2b_{0}b\tau }\right|\\ =\left|-4a_0{a}_{\tau }\right|\\ =4\end{array}$

2) 当$r_1=\frac{N}{2}-1,r_2=\frac{N}{2}$ ，可以得到$\left(e,f\right)$ ，即

$\begin{array}{l}e=\left(e_0,e_1,\cdots ,e_{N-1}\right)=\left(a_0,a_1,a_2,\cdots ,a_{N-2},b_{N-2},\cdots ,b_1,b_0\right)\\ f=\left(f_0,f_1,\cdots ,f_{N-1}\right)=\left(b_0,b_1,b_2,\cdots ,b_{N-2},-a_{N-2},\cdots ,-a_1,-a_0\right)\end{array}$

根据$\tau$ 取值范围分下面三种情形讨论$\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|$ ：

情形1：当$N-1\le \tau \le 2N-3$ 时，

$\begin{array}{l}{\rho }_e\left(\tau \right)={\displaystyle \sum _{i=0}^{N-2}{a}_i{b}_{2N-\tau -i-3}}\\ {\rho }_f\left(\tau \right)={\displaystyle \sum _{i=0}^{N-2}{b}_i\left(-a_{2N-\tau -i-3}\right)}\end{array}$

有

$\begin{array}{l}\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|=\left|{\displaystyle \sum _{i=0}^{N-2}{a}_i{b}_{2N-\tau -i-3}}{\displaystyle \sum _{i=0}^{N-2}{b}_i\left(-a_{2N-\tau -i-3}\right)}\right|\\ =0\end{array}$

情形2：当$\frac{N}{2}\le \tau \le N-2$ 时，

$\begin{array}{l}{\rho }_e\left(\tau \right)={\displaystyle \sum _{i=0}^{N-\tau -2}{a}_i{a}_{i+\tau }}+{\displaystyle \sum _{i=N-\tau -1}^{N-2}{a}_i{b}_{2N-\tau -i-3}}+{\displaystyle \sum _{i=0}^{N-\tau -2}{b}_i{b}_{i+\tau }}\\ {\rho }_f\left(\tau \right)={\displaystyle \sum _{i=0}^{N-\tau -2}{b}_i{b}_{i+\tau }}+{\displaystyle \sum _{i=N-\tau -1}^{N-2}{b}_i\left(-a_{2N-\tau -i-3}\right)}+{\displaystyle \sum _{i=0}^{N-\tau -2}{a}_i{a}_{i+\tau }}\end{array}$

因为${\rho }_a\left(\tau \right)+{\rho }_b\left(\tau \right)=0$ ，根据引理2知，$\left(a,b\right)$ 在$0\le i<\frac{N}{2}$ 时，$a_i=b_i$ ；在$\frac{N}{2}\le i<N$ 时，$a_i=-b_i$ ，所以

$\begin{array}{l}\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|=\left|{\displaystyle \sum _{i=N-\tau -1}^{N-2}{a}_i{b}_{2N-\tau -i-1}}+{\displaystyle \sum _{i=N-\tau -1}^{N-2}{b}_i\left(-a_{2N-\tau -i-1}\right)}-2a_{N-1}{a}_{N-\tau -1}-2b_{N-1}{b}_{N-\tau -1}\right|\\ =\left|-2a_{N-1}\left(a_{N-\tau -1}+b_{N-\tau -1}\right)\right|\\ =0\end{array}$

情形3：当$1\le \tau \le \frac{N}{2}-1$ 时，

$\begin{array}{l}{\rho }_e\left(\tau \right)={\displaystyle \sum _{i=0}^{N-\tau -2}{a}_i{a}_{i+\tau }}+{\displaystyle \sum _{i=N-\tau -1}^{N-2}{a}_i{b}_{2N-\tau -i-3}}+{\displaystyle \sum _{i=0}^{N-\tau -2}{b}_i{b}_{i+\tau }}\\ {\rho }_f\left(\tau \right)={\displaystyle \sum _{i=0}^{N-\tau -2}{b}_i{b}_{i+\tau }}+{\displaystyle \sum _{i=N-\tau -1}^{N-2}{b}_i\left(-a_{2N-\tau -i-3}\right)}+{\displaystyle \sum _{i=0}^{N-\tau -2}{a}_i{a}_{i+\tau }}\end{array}$

因为${\rho }_a\left(\tau \right)+{\rho }_b\left(\tau \right)=0$ ，根据引理2知，$\left(a,b\right)$ 在$0\le i<\frac{N}{2}$ 时，$a_i=b_i$ ，所以

$\begin{array}{l}\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|=\left|{\displaystyle \sum _{i=N-\tau -1}^{N-2}{a}_i{b}_{2N-\tau -i-3}}+{\displaystyle \sum _{i=N-\tau -1}^{N-2}{b}_i\left(-a_{2N-\tau -i-3}\right)}-2a_{N-1}{a}_{N-\tau -1}-2b_{N-1}{b}_{N-\tau -1}\right|\\ =\left|-4a_{N-1}{a}_{N-\tau -1}\right|\\ =4\end{array}$

综上所述，$\left(e,f\right)$ 是长度为$2N-2$ 、零相关区为$\frac{3}{2}N-1$ ，且在零相关区外的幅值为4的II型偶长Z-互补序列对。

为了更好地阐述上述定理，我们给出如下例子，并且例子的结果皆由Matlab得到。

例1 设$\left(a,b\right)=\left(+---+-++-++++-++,+---+-+++----+--\right)$ 是由引理2产生的长度为$N=16$ 的GCP，验证定理1当$r_1=0,r_2=2N-1$ 的情况下产生得到的$\left(e,f\right)$ 是II型偶长Z-互补序列对。

解 二进制序列$\left(e,f\right)$ 通过定理1产生得到，当$r_1=0,r_2=2N-1$ 时

$\begin{array}{l}e=\left(---+-++-++++-++--+----+++-+---\right)\\ f=\left(---+-+++----+----+----+--+-++\right)\end{array}$

计算得到其非周期自相关函数和为

$\left({\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|}_0^{29}\right)=\left(60,4_7,0_{22}\right)$

所以$\left(e,f\right)$ 是一个长度为30的II型偶长Z-互补序列对，并且零相关区长度为$Z=23$ 。

例2 设$\left(a,b\right)=\left(+-++---+,+-+++++-\right)$ 是由引理2产生的长度为$N=8$ 的GCP，验证定理1当$r_1=\frac{N}{2}-1,r_2=\frac{N}{2}$ 的情况下产生得到的$\left(e,f\right)$ 是II型偶长Z-互补序列对。

解 二进制序列$\left(e,f\right)$ 通过定理1产生得到，当$r_1=\frac{N}{2}-1,r_2=\frac{N}{2}$ 时

$\begin{array}{l}e=\left(+-++---+++++-+\right)\\ f=\left(+-++++++++--+-\right)\end{array}$

计算得到其非周期自相关函数和为

$\left({\left|{\rho }_e\left(\tau \right)+{\rho }_f\left(\tau \right)\right|}_0^{13}\right)=\left(28,4_3,0_{10}\right)$

所以$\left(e,f\right)$ 是一个长度为14的II型偶长Z-互补序列对，并且零相关区长度为$Z=11$ 。现有II型EB-ZCP见表1。

Table 1. Existing type II EB-ZCP

表1. 现有II型 EB-ZCP

文献	长度	ZCZ	零相关区外的值
[7]	$\begin{array}{l}{2}^{k}N+2^{k-1}\\ N\in Z^{+},k\ge 2\end{array}$	$2^{k}N+2^{k-1}-N$	$4\le v\le 2^k\left(2N-1\right)$
[7]	$3N$	$3N-1$	$2N$
[7]	$14N$	$14N-1$	$4N$
[8]	$2^{m}P$	$2^{m}P+1-P$	--
[11]	$\begin{array}{l}{2}^{k+2}N\\ k\in \left\{1,2,3,\cdots \right\}\\ N=2^{\alpha }{10}^{\beta }{26}^{\gamma }\end{array}$	$\left(2^{k+2}-1\right)N$	$2^k\times 4N$
[11]	$\begin{array}{l}2N+2\\ N=2^{\alpha }{10}^{\beta }{26}^{\gamma }\end{array}$	$\frac{3}{2}N+2$	4
[14]	$8N+4$	$5N+2$	8
[15]	$2N+3$	$N+2$	2 or 6
[15]	$4N+4$	$\frac{7}{2}N+4$	8
定理1	$\begin{array}{l}2N-2\\ N=2^{\alpha }{10}^{\beta }{26}^{\gamma }\end{array}$	$\frac{3}{2}N-1$	4

本文与文献[11] [15]的构造方法相比，存在以下的不同之处。

1) 本文删除的码元是2个，文献[11]是插入2个码元，文献[15]是插入3个码元。

2) 本文删除的位置有2种方法，文献[11]的插入位置在种子对的后端，文献[15]的插入位置在种子对第1个码元前，中端以及最后1个码元后，本文的删除位置在种子对的前端和后端或者种子对的中端。

3) 本文构造的序列与文献[15]相比，其零相关区外的值更小。

4. 结语

本文主要研究了II型偶长Z-互补序列对，在二进制互补对的核的基础上，利用Turyn构造新的序列，在此序列上利用级联和删除2个码元，得到了长度为$2N-2,N=2^{\alpha }{10}^{\beta }{26}^{\gamma }$ 的II型EB-ZCP，其中$\alpha \ge 1,\beta \ge 0,\gamma \ge 0$ ，$\alpha ,\beta ,\gamma$ 为非负整数。本文所得的II型EB-ZCP在特定的长度上是最优的，与现有的ZCPs相比包含许多新长度，其零相关区外的值较低，可以为无线通信系统提供更加性能优良的Z-互补对。