二元二值序列偶的定义及性质

二元二值序列偶的定义及性质2.2.1 二元二值序列偶的定义定义2.195：设a=(a0,aN-1)和b=(b0,bN-1)分别是周期为长的序列，那么序列和组成一个序列偶，记为()。如果ai=1，bi=1，i=0,N-1，那么称()为二元序列偶。定义2.295：二元序列偶()的周期自相关函数（亦称循环自相关函数），用表示，定义为 (2-1)式中当时，称为二元序列偶()的同相周期自相关函数，也称为序列偶()的主峰；当时，称为异相周期自相关函数。定义2.395：设()和()为两个N长二元序列偶，那么两序列偶间的周期互相关函数表示为 (2-2)定义2.4：如果二元序列偶()的周期自相关函数满足 (2-3)式中E和F是两个不等的常数，分别表示序列偶()的同相和异相周期自相关函数，那么称二元序列偶()为二元二值周期自相关序列偶，简称二元二值序列偶，记为BSPT。特别地，若F=0，二元序列偶(a,b)称为最佳序列偶，若F=-1，二元序列偶(a,b)称为伪随机序列偶。在定义2.4中，当时，二元二值序列偶()退化为一般的二元二值序列，这说明二元二值序列偶是二元二值序列的扩展。另外，根据失配滤波的定义145，可将二元二值序列偶看作为一类失配序列。定义2.5149：周期为长的二元序列a=(a0,aN-1)，ai=1，i=0,N-1，其特征多项式定义为，表示为= (2-4)定义2.6：集合G是整数环ZMZm，有这种表示法吗？上的子集，那么整数集G的特征多项式定义为，表示为= (2-5)2.2.2 二元二值序列偶的变换性质由于序列偶由两个不同序列组成作为一个通信地址码应用，所以讨论其变换性质具有实际意义，尤其掌握其等价变换性质对于二元二值序列偶的搜索、构造及应用都是十分有意义的。二元二值序列偶具有与周期序列相似的变换性质1,2,8，首先定义二元序列的几种变换形式：(1)序列的取补变换记为 序列中的每一个元素为序列中相对应元素取补，由于序列中的元素为+1或-1，所以取补变换也相当于对序列中的元素易号，因此取补变换可以称为序列的负元变换，记为，与序列取补变换相同，即有。(2)序列a的向左循环移m位变换记为 ，为m位移位算子，。因为序列a是以N为周期的，所以序列a中的各元素向左循环移m位，等于向右循环移位，即有。(3)序列a的逆序变换记为 ，T为逆序变换算子。(4)序列a的完全采样变换记为 为的采样算子，为与互素的正整数，元素下标对周期进行取模运算，即有。由此定义可知，由于与互为素数，所以序列实际是序列a中元素的重新排列。将以上序列的基本变换形式应用于序列偶得到了二元二值序列偶的如下变换性质：性质2.1：互易变换。二元二值序列偶经互易变换得到的序列偶()也是二元二值序列偶。证明：由于二元序列偶()和()的周期自相关函数满足= (2-6)显然性质2.1得证。 证毕。这是什么意思？性质2.2：取补变换。二元二值序列偶()取补变换得到的、以及都为二元二值序列偶。证明：由于取补变换相当于负元变换，即，故根据定义2.4得 (2-7) (2-8) (2-9)性质2.2显然成立。 证毕。性质2.3：循环移位变换。二元二值序列偶的左移n位变换为，亦是二元二值序列偶。证明：由序列偶的周期自相关函数的定义2.1有 (2-10)令，则由式(2-10)得由定义2.4可知，为二元二值序列偶。 证毕。性质2.4：逆序变换。二元二值序列偶()经过逆序变换得到的仍为二元二值序列偶。证明：由定义2.1有 由定义2.4可知，为二元二值序列偶。 证毕。性质2.5：完全采样变换。二元二值序列偶()经过完全采样变换得到的为二元二值序列偶。证明：由定义2.1有 (2-11)由于q与N互素，则可以取从0到N-1的N个取值，因此式(2-11)可得由定义2.4可知，为二元二值序列偶。 证毕。2.2.3 二元二值序列偶的特征多项式性质定义2.5给出了序列的特征多项式定义，那么可以得到二元二值序列偶中两个组成序列的特征多项式，由此下面给出二元二值序列偶的特征多项式性质，它是判断二元二值序列偶的充分必要条件，同时也是判断二元二值序列偶通信唯一性的重要工具注意论文中的定义和定理的编号，别弄混了。定理2.1：设和分别是二元序列a和b的特征多项式，其中，且，。若二元序列偶()为二元二值序列偶，当且仅当这里好像不是一句话？式中，E和F分别表示()的同相和异相周期自相关函数。证明：由于 根据定义2.4，若()为二元二值序列偶，当且仅当+即=，式中。 证毕。将定理2.1的二元二值序列偶的特征多项式性质进一步扩展得到下面结论。定理2.2：序列和，且，设和，若二元序列偶()为二元二值序列偶，当且仅当 式中na和nb分别表示序列a和b中“”的个数。证明：由于根据定义2.4，若()为二元二值序列偶，当且仅当因此，若()为二元二值序列偶，当且仅当 式中且na和nb分别表示序列a和b中“”的个数，。证毕。事实上，如果用和分别表示序列a和b中“”的位置，那么Ga和Gb为整数环ZN上子集，而依据定义2.6，定理2.2中的和则分别是对Ga和Gb的特征多项式表示，因此定理2.2是在定理2.1的二元二值序列偶的特征多项式基础上描述了二元二值序列偶中“”位置整数集的特征多项式性质。定理2.1和定理2.2给出的特征多项式性质为研究二元二值序列偶提供了有效的数学工具，为二元二值序列偶的构造提出了一种方便的数学方法。2.2.4 二元二值序列偶的二值谱特性任意周期长为N的序列的离散付立叶变换会生成周期为N的离散谱Fa(k)： (2-12)反之，利用离散付立叶逆变换可以从频谱序列获得周期序列： (2-13)定义2.2用式(2-1)给出了序列偶(a,b)的周期自相关函数表示，那么的付立叶变换表示为： (2-14)定理2.3：若(a,b)是周期为N长二元二值序列偶，E和F分别表示同相和异相周期自相关函数，那么二元二值序列偶(a,b)的周期自相关函数的付立叶变换谱亦满足二值特性，即 (2-15)证明：由式(2-12)得序列偶(a,b)中组成序列a和b的付立叶变换，那么由式(2-14)有 证毕。定理2.3表明若二元序列偶(a,b)的周期自相关函数具有二值性，那么其离散付立叶变换后的谱序列亦是一个二值实序列。特别地，若二元二值序列偶的异相周期自相关F=0时即为最佳二元序列偶时，其周期自相关函数的谱序列具有相同幅度。由定理2.3可以得出下面推论：推论2.1：二元二值序列偶(a,b)中序列a和b的付立叶变换谱和满足 (2-16)式中表示的共轭函数。证明：由式(2-15)可直接得出。 从以上讨论中可知，如果二元序列偶(a,b)应用于通信系统中，其二值特性已知，发送方以序列a作为扩频地址码，那么接收方可根据式(2-16)获得扩频码序列b的付立叶变换谱，再经(2-13)的逆变换计算得到。下面举例说明。例2.1：若为二元二值序列偶，同相自相关函数E=5，异相自相关函数F=1，周期长N=11，由定理2.3可得假设序列a=(-+-+-+-+)和=(-+-+)都满足上述条件，其中“-”和“+”分别表示“-1”和“+1”，那么借助计算机可以计算出序列a和付立叶变换谱的幅值，分别为|Fa(k)|2=9.00, 7.82, 4.74, 1.19, 0.56, 41.70, 41.70, 0.56, 1.19, 4.74, 7.82和=9.00, 4.32, 18.73, 6.7611, 15.32, 10.86, 10.86, 15.32, 6.76, 18.73, 4.32，那么由推论2.1可计算出序列b和的共轭谱和，经式(2-13)对其进行付立叶逆变换得到b=(-+-+-+)和=(-0.1 -0.1 0.4 0.4 -0.2 0.7 0.3 0.9 0.6 1 0.9)，显然是二元二值序列偶，而不是。由例2.1看出，定理2.3和推论2.1只能为获得或判断二元二值序列偶提供必要条件，它可能带来不确定的结果，从而加大了计算量。为了更准确更简便的研究二元二值序列偶，下面引入差集偶的概念127，这是近来引入的组合数学的新概念，它与二元二值序列偶间存在着密切的关系。2.3 差集偶与二元二值序列偶目前具有较好的相关性的序列偶是通过盲搜索和统计搜索方法例如遗传算法等获得的，还没有找到直接构造的数学方法，为了进一步研究序列偶，引入了差集偶，它是组合数学中一个新的概念，事实证明，差集偶与序列偶间有着密切的关系。2.3.1 差集偶的定义和性质定义2.71,8：设G是整数环Zv上的子集，集合， ，参数。若对于任意mod v，有这里的mod v对吗？对()满足那么()称为差集偶，记为(v,k,e,)-DSP。例2.2：设，=0,1,3,5,2n-1，n为大于1的整数，那么是 (2n+1,2,n+1,2,1)-DSP。特别地，当时，差集偶()即为普通的差集定义，因此可认为差集是组成差集偶的两个组成集合相等时的特例，同时也可将差集偶看作差集的推广。2.3.2 差集偶与二元二值序列偶的等价关系定理2.6127：集合D和为整数环ZN 上的两个子集，序列和分别等价对应于D和，即，(D,)为(N,k,e,)-DSP的充分必要条件是序列偶(a,b)为二元二值序列偶，且其周期自相关函数满足定理2.6表明了二元二值序列偶与差集偶间存在的等价关系，也就是说二元二值序列偶的构造问题可以转化为在整数环ZN上对差集偶的构造。目前还没有找到构造差集偶的直接方法，不过特征多项式法是实现差集偶构造的一个有效方法，定理2.5给出了关于差集偶构造的充分必要条件，即差集偶构造的一种手段。由二元二值序列偶与差集偶间存在的这种等价关系可以确定定理2.5与定理2.2的结论是统一的，这样更进一步说明差集偶的构造等同于序列偶构造。下面由定理2.6引申出相关结论。定理2.7：若(a,b)是周期为N的二元二值序列偶，那么其异相周期自相关函数值F满足也就是说序列偶的周期长N为偶数，那么F为偶数，反之，N为奇数，则F为奇数。.证明：由定理2.6直接得出 证毕。定理2.8：周期长为N的二元二值序列偶(a,b)，其同相和异相周期自相关函数分别为E和F，那么有(1)；(2)E-F=4n式中m与n都为为大于零的整数。证明：由定理2.6，有，因此，。由定理2.6，因此，。 证毕。2.5 二元二值序列偶的唯一性二元二值序列偶引入工程实践应用的一个至关重要的前提是保证其通信的唯一性150，也就是说发送方的地址码可以被接收方唯一接收，即只有唯一的接收方地址码满足相关性要求。下面给出二元二值序列偶的唯一性证明。定理2.16：若二元序列偶和为二值自相关序列偶，其同相和异相周期自相关函数值分别为E和F，那么。证明：设、和分别为序列a、b和的特征多项式，如果和都为二元二值序列偶，那么根据定理2.1有 (2-17) (2-18)式(2-17)减式(2-18)得 ( (2-19)式(2-19)两边同乘得 (2-20)由于=0，那么 (2-21) (2-22)由定义2.5确定序列的特征多项式的唯一性，因此 证毕。定理2.17：若存在最佳二值序列偶()和()，即二者的异相周期自相关函数相同为F0，同相自相关不同分别为E和，且，则，且。证明：设、和分别为序列a、b和的特征多项式，二元二值序列偶()和()的同相周期自相关函数分别为E和，异相周期自相关函数为F。序列a、b、的特征多项式分别为、，那么由定理2.1 (2-23) (2-24)式(2-23)减式(2-24)得 (2-25)式(2-25)两边同乘，得 (2-26)式(2-25)两边同乘，得 (2-27)由式(2-26)和式(2-27)得 (2-28)因为，F0，所以有且和中各项系数为，因此，显然那么，则 证毕。5.3 伪随机序列偶的构造5.3.1 伪随机序列偶的存在条件定理5.1：伪随机序列偶存在的充要条件。设fa(x)和fb(x)分别是二元序列a和b的特征多项式，其中，且ai=1，bi=1，。若二元序列偶()是伪随机二元序列偶，当且仅当 式中。E表示()的同相周期自相关函数。证明：由于伪随机序列偶是一类二元二值序列偶，因此根据定理2.1的二元二值序列偶的特征多项式性质有 (5-1)令代入式(5-1)即得 (5-2)式中。定理5.2得证。 证毕。目前伪随机序列偶的构造还没有找到有效的数学方法，但是定理5.1提示出对伪随机二元序列偶进行递归构造依据的充要条件，从而实现长周期伪随机序列偶的构造，而这是采用穷搜索方法无法实现的。根据伪随机序列偶的定义可知，伪随机序列偶是周期异相自相关函数为-1的二元二值序列偶，由定理2.6知二元二值序列偶与组合数学概念差集偶之间存在着等价对应关系，因此伪随机序列偶的构造也可以转化为特殊条件(F=-1)下差集偶的构造问题，定理5.2给出的充要条件等价于定理2.6在特定条件下即的结果。下面给出差集偶的特征序列偶满足伪随机序列偶定义的差集偶的存在条件，也即伪随机序列偶存在的必要条件。定理5.2：伪随机二元序列偶存在的必要条件。D和是整数环Zv上的子集，D和分别含有k和个元素，构成差集偶-DSP，为等价对应的二元序列偶，即的特征序列偶，d为序列a和序列b的汉明距离，则序列偶具有，的二值自相关特性的必要条件为参数满足, +,)。证明：由于为-DSP，故满足54 (5-3) (5-4)由定理2.6得： (5-5)以及由定理2.8得： (5-6)此时可令，并由式(5-3)和(5-4)导出 (5-7)再由式(5-3)、式(5-4)和式(5-6)得：整理得： (5-8)因此，根据式(5-7)和式(5-8)可以得出为-DSP的必要条件。证毕。特别地，考虑两种情况：其一，当时，为-DSP的必要条件为参数满足(,)；其二，当时，参数满足(2d+3,+ ,+1,)。下面依据定理5.3对于上述两种情况下参数分别为及，即对应于(3+2d,2,2+d,2,1)型和(,)型差集偶给出构造证明，此时差集偶所对应的伪随机序列偶的同相及异相周期自相关函数值分别为，。以下各类差集偶所等价对应的伪随机序列偶之间相互不具有移位、取补、完全采样的等价变换性质。5.3.2 (3+2d, 2, 2+d, 2, 1)型差集偶对于型差集偶给出几种情况的构造。当时，可得到定理5.3和定理5.4。定理5.3：集合D和是整数环Z上的两个子集，=0,1, 2,n，n为大于1的整数，是-DS