多序列S的周期,其最小周期记为per(S),显然
lcm(per(A1),per(A2),?,per(At))?per(s),其中per(Aj)是Aj,1?j?t的最小周期。周期为N的t-维多序列S?(A1,A2,?,At)的极小多项式F(x)是指序列A1,A2,?,At的次数最低的共同特征多项式,则: F(x)?lcm(f1(x),f2(x),?,ft(x)),其中fj(x)是
F(x))称为多序列S的联合线性复杂Aj,1?j?t的极小多项式。那么L(S)?deg(度。设序列Aj的周期为N,记AjN(x)为Aj,1?j?t的第一个周期所对应的多项
1?xN式。由于:fj(x)? ,1?j?t，那么F(x)?lcm(f1(x),f2(x),?,ft(x)) NNgcd(1?x,Aj(x))1?xN1?xN1?xN?lcm(,,?,)NNNNNNgcd(1?x,A1(x))gcd(1?x,A2(x))gcd(1?x,At(x))1?xN ?gcd(1?xN,A1N(x),A2N(x),?,AtN(x))
5.2 二元周期多序列及其广义对偶序列的联合线性复杂度
定义
5.2.1 周期为N的t-维多序列S?(A1,A2,?,At)，其中
如果S?(A1,A2,?,At)满足Aj?(a0j,aAj?(aa?0j,a1j,?2j,，)1j,a2j,，)其中
i?0,1,2,?，1?j?t，则称S为S的广义对偶多序列。周期为N的t-aji?1?a，ji
维多序列S?(A1,A2,?,At)的极小多项式F(x)是指序列A1,A2,?,At的次数最低的共同特征多项式，显然F(x)?lcm(f1(x),f2(x),?,ft(x)),，其中fj(x)是Aj，1?j?t的极小多项式，那么L(S)?deg(F(x))称为多序列S的联合线性复杂度。设序列Aj的周期为N，记AjN(x)为Aj，1?j?t的第一个周期所对应的多项式。
1?xN由于fj(x)? ，1?j?t，
gcd(1?xN,AjN(x))则F(x)?lcm(f1(x),f2(x),?,ft(x))
1?xN1?xN1?xN ?lcm(,,?,)
gcd(1?xN,A1N(x))gcd(1?xN,A2N(x))gcd(1?xN,AtN(x))1?xN ? NNNNgcd(1?x,A1(x),A2(x),?,At(x))引理5.2.1
[31]
设F2上周期序列S生成函数s(x)??Sixi????i?0rs(x)，其中fs(x)gcdrs(x(fs)x,?(，且))fs(x)是S的极小多项式，记fs(x)??cjxj (c0?cm?1)，
?mj?0以l记x?1为fs(x)根的次数（l?0），即：fs(x)?(1?x)lf1(x)，其中f1(1)?0，则
23
对S?的按位取反序列S?的生成函数：
?(1?x)rs(x)?fs(x)，l?0??(1?x)fs(x)(1?x)rs(x)?fs(x)?(rs(x)?f1(x))/(1?x)s(x)???,fs(x)(1?x)f1(x)??rs(x)?f1(x),l?2?fs(x)??(1?x)fs(x),l?0?,l?1 S?的极小多项式为：fs(x)??f1(x)?f(x),l?2?sl?1
推论5.2.1 设F2上周期多序列S?(A1,A2,?,At)，N-周期序列Aj，1?j?t的生成函数Aj(x)??ajixi?i?0m??rj(x)fj(x)，其中gcd(rj(x),fjx())?，且1fj(x)是Aj的极小多
项式，记fj(x)??crxr(c0?cm?1)，以lj记x?1时fj(x)根的次数(lj?0)，即：
r?0fj(x)?(1?x)jgjx(,)其中gj(1)?0，则对Aj按位取反序列Aj的生成函数：
?(1?x)rj(x)?fj(x),?(1?x)fj(x)?(1?x)rj(x)?fj(x)??(rj(x)?gj(x))/(1?x)Aj(x)???,fj(x)(1?x)g(x)j??rj(x)?gj(x)?,f(x)?j?lj?0lj?1 ； lj?2l?(1?x)fj(x),?Aj的极小多项式为： fj(x)??gj(x),?f(x),j?lj?0lj?1
lj?2定理5.2.1设周期t-维多序列S?(S0,S1,?)?(A,,A)1,A2?t的广义对偶多序列
S?(S0,S1,?)?(A1,A2,?,At)，其中Si?(a1i,a2i,?,ati)，Aj?(aj0,aj1,aj2,?)，
Aj?(aj0,aj1,aj2,?)，aji?1?aji，i?0,1,2,?，1?j?t，fj(x)和fj(x)分别表示Aj与Aj的极小多项式。如果：fj(x)?(1?x)jgj(x)，1?j?t，lj?0，其中：gj(1)?0，则：S的极小多项式F(x)与S的极小多项式F(x)存在以下关系：
?(1?x)F(x),lj?0?lj?1 ，其中：G(x)?lcm[g1(x),g2(x),?,gt(x)] F(x)??G(x),?F(x),lj?2?证明 由推论5.2.1知：若fj(x)?(1?x)jgj(，1?j?t，lj?0，gj(1)?0，x)
24
ll?(1?x)f(x),l?0jj??,lj?1 则fj(x)??gj(x)?,lj?2??fj(x)而：F(x)?lcm(f1(x),f2(x),?,ft(x))，F(x)?lcm(f1(x),f2(x),?,ft(x)),那么： (1)当lj?0时，
F(x)?lcm(f1(x),f2(x),?,ft(x))
?lcm[(1?x)f1(x),(1?x)f2(x),?,(1?x)ft(x)] ?(1?x)lcm[f1(x),f2(x),?,ft(x)]
?(1?x)F(x)
(2)当lj?1时，
F(x)?lcm(f1(x),f2(x),?,ft(x))
?lcm[g1(x),g2(x),?,gt(x)] 令：G(x)?lcm[g1(x),g2(x),?,gt(x)] 则：F(x)?G(x) (3)当lj?2时，
F(x)?lcm(f1(x),f2(x),?,ft(x))
?lcm[f1(x),f2(x),?,ft(x)]
?F(x)
从而得证。
?L(S)?1,lj?0?推论5.2.2：在上述记号下，L(S)??L(S)?t,lj?1。
?L(S),lj?2?证明 由定理5.2.1的结论及周期多序列的联合线性复杂度定义可以直接得出结果。
定义5.2.2 设F2上周期为N的t-维多序列S?(A1,A2,?,At)的广义对偶多序列S?(A1,A2,?,At)，其中Aj?(aj0,aj1,aj2,,Aj?(aj0,aj1,aj2,?)， ?)aji?1?aji，i?0,1,2,?,1?j?t,SN的广义重量复杂度定义为：
NNWcu(SN)?minL(A?M) jjNWH(Mj)?u?m10?m20?这里M?(m0,m1,...)?????mt0m11m12???m21m22??用Mj?(M1,M2,...,Mt),其中第i列为mi，
????mt1mt2?? 25
N表示上述矩阵的第j行,即：Mj?(mj0,mj1,mj2,?)，1?j?t。WH(MNj)?u表示Mj的Hamming重量，即MjN中非零分量的个数，L(SN)表示序列SN的线性复杂度。 定理5.2.2设SN是F2上N-周期多序列，SN与SN重量复杂度有下列关系：
Wcu(SN)?WcN?u(SN)。
证明 Wcu(SN)?minL(AjN?MjN)?minL(AjN?MjN?1N) NNWH(Mj)?uWH(Mj)?uNN?minL(A?M)?jjNWH(Mj)?uWH(Rj)?N?uminNL(AjN?RjN)?WcN?u(SN)
5.3 p元周期多序列及其广义对偶序列的联合线性复杂度
设S是一个字长为t的以“字”为单位的序列,即S?(S0,S1,?),其中
Si?(a1i,a2i,?,ati),aji?Fp,1?j?t,i?0,1,?,称S为Fp上t?维多序列,当t?1时,即为通常所指的单序列。多序列S可以写成矩阵的形式:
a12???a21a22??,其中第i列为Si。
?????at1at2??用Aj?(aj0,aj1,aj2,?),j?1,2,?,t,那么S可以看成由t个“平行序列”构成的新?a10?aS?(S0,S1,?)??20????at0a11序列,并记: S?(A1,A2,?,At)。
在Fp上t?维多序列S?(S0,S1,?),如果满足: Si?N?Si,i?0,则称正整数N是多序列S的周期,其最小周期记为per(s),显然
per(s)?lcm(per(A1),per(A2),?,per(At)),其中per(Aj)是Aj,1?j?t的最小周期。周期为N的t?维多序列S?(A1,A2,?,At)的极小多项式F(x)是指序列A1,A2,?,At的次数最低的共同特征多项式,则:
F(x)?lcm(f1(x),f2(x),?,ft(x))其中fj(x)是Aj,1?j?t的极小多项式。那么
L(S)?degF(x(称为)多序列S的联合线性复杂度。设序列Aj的周期为N,记
AjN(x)为Aj,1?j?t的第一个周期所对应的多项式。由于:
1?xN ,1?j?t fj(x)?gcd(1?xN,AjN(x))那么F(x)?lcm(f1(x),f2(x),?,ft(x))
1?xN1?xN1?xN?lcm(,,?,)gcd(1?xN,A1N(x))gcd(1?xN,A2N(x))gcd(1?xN,AtN(x))
26
1?xN ?gcd(1?xN,A1N(x),A2N(x),?,AtN(x))定义5.3.1 设Fp上周期为N的t?维多序列S?(A1,A2,?,At)，其中
Aj?(aj0,aj1,aj2,?)，如果S?(A1,A2,?,At)满足Aj?(a0j,a?1j,a2j,，)其中
1?j?t，则称S为S的广义对偶多序列。周期为N的t?aji?1?a，jii?0,1,2,?，
维多序列S?(A1,A2,?,At)的极小多项式F(x)是指序列A1,A2,?,At的次数最低的共同特征多项式，显然F(x)?lcm(f1(x),f2(x),?,ft(x))，其中fj(x)是Aj，1?j?t的极小多项式，那么L(S)?deg(F(x))称为多序列S的联合线性复杂度。设序列Aj的周期为N，记AjN(x)为Aj，1?j?t的第一个周期所对应的多项式。
1?xN由于fj(x)? ，1?j?t，
gcd(1?xN,AjN(x))则：F(x)?lcm(f1(x),f2(x),?,ft(x))
1?xN1?xN1?xN ?lcm(,,?,) NNNNNNgcd(1?x,A1(x))gcd(1?x,A2(x))gcd(1?x,At(x))1?xN ?
gcd(1?xN,A1N(x),A2N(x),?,AtN(x))引理5.3.1 设Fp上周期序列的S?极小多项式为fs(x)?(1?x)tg(x)，其中t为非负整数g(1)?0.S的生成函数s(x)??sixi????i?0rs(x),其中gcd(rs(x),fs(x))?1，则S?fs(x)的对偶序列S?的生成函数：
?(p?1)g(x)?rs(x)(1?x),?(1?x)g(x)?(p?1)fs(x)?(1?x)rs(x)??(p?1)(1?x)g(x)?rs(x)(1?x)??,s(x)?2(1?x)g(x)fs(x)(1?x)??(p?1)(1?x)tg(x)?r(x)(1?x)s,?t?1(1?x)g(x)??t?0t?1 t?2?(1?x)fs(x),?1?f(x),??S的极小多项式为：fs(x)??1?xs?fs(x),???fs(x),??t?0g(1)?rs(1)?p,t?1g(1)?rs(1)?p,t?1t?2
推论5.3 .1 设Fp上周期多序列S?(A1,A2,?,At)，N-周期序列Aj，1?j?t的生成函数Aj(x)??ajix?ii?0rj(x)fj(x)，其中gcd(rj(x),fjx())?，且1fj(x)是Aj的极小多
27