12-1、设3级线性反馈移位寄存器的特征方程为:2
3
()1f x x x =++,试验证它为本原多 项式。
解:由题意n=3,所以217n
m =-=。
而7
3
2
4
3
2
11(1)(1)m
x x x x x x x +=+=+++++
上式说明()f x 可整除7
1x +,且()f x 既约,除不尽6
5
4
1,1,1x x x +++所以f (x)为
本原多项式。
12-2、己知三级移位寄存器的原始状态为111,试写出两种m 序列的输出序列。 解:因为反馈移存器能产生m 序列的充要条件为:反馈移位寄存器的特征多项式为本原多项
式。当n=3时,有2个3阶本原多项式:
31()1f x x x =++,322()1f x x x =++
1()f x 和2()f x 为互逆的本原多项式,都可以产生m 序列。
根据第5题,由3
1()1f x x x =++产生的m 序列为11101000, 同理,由32
2()1f x x x =++产生的m 序列为11100100。
12-3、设4级线性反馈移存器的特征方程为:2
3
4
()1f x x x x x =++++,试证明此移位寄 存器产生的不是m 序列。
证明:方法一:由题意n =4,得2115n
m =-=。因为 4
3
2
5
(1)(1)1x x x x x x +++++=+
()f x 可整除5
1x +,故()f x 不是本原多项式,它所产生的序列不是m 序列。 方法二:由特征多项式2
3
4
()1f x x x x x =++++构成的4级线性反馈移位寄存器如图9-4所示。
假设初始状态为:1 1 1 1 状态转换位: 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1
可见输出序列的周期为4
62115≠-=,故不是m 序列。
图 12-1
12-4、己知一个由9级移位寄存器所产生的m 序列,写出在每一周期内所有可能的游程长度的个数。
解:该m 序列中共有8
2256=个游程。
根据m 序列游程分布的性质,长度为k 的游程数目占游程总数的2,1(1)k
k n -≤≤-。
而且在长度为k 的游程中[其中1(2)k n ≤≤-],连“1”和连“0”的游程各占一半。所以:
长度为1的游程有128个,“1”和“0"各为64个, 长度为2的游程有64个,“11”和“00”各为32个, 长度为3的游程有32个,“111”和“000”各为16个, 长度为4的游程有16个,“1111”和“0000”各为8个, 长度为5的游程有8个,“11111”和“00000”各为4个, 长度为6的游程有4个,“111111”和“000000”各为2个, 长度为7的游程有2个,“”和“”各为1个, 长度为8的游程有1个,即“”,
长度为9的游程有1个,即“111111111”。
12-5、有一个9级线性反馈移存器所组成的m 序列产生器,其第3、6和9级移存器的输出分别为369,,Q Q Q ,试说明:
(1)将它们通过“或”门后得到一个新的序列,得到序列的周期仍为921-,并且“1”的符号出现率约为7/8。
(2)将它们通过“与”门后得到一个新的序列,得到序列的周期仍为921-,并且“1”的符号出现率约为1/8。
解:设九级移存器所组成的序列为9{},1,
21i a i =-,则其周期为921T =-
则369,,Q Q Q 的输出序列分别为369{},{},{}i i i a a a +++ (1)设它们通过“或”门后得到的新序列为*
{}i a ,
则*
369i i i i a a a a +++=∨∨
因为{}i a 的周期为T ,
所以369{},{},{}i i i a a a +++的周期也为T ,
所以**
369369i T i T i T i T i i i i a a a a a a a a ++++++++++=∨∨=∨∨=
所以*
{}i a 的周期仍为T ,
九级移存器的状态共有921-种,并且一个周期内各种状态出现1次,即等概率出现,所以369{},{},{}i i i a a a +++在一个周期内000,001,010,…,111八种状态等概率出现,通过“或”门后,只有000输出为0,其余为1,所以为0的概率为1/8,为1 的概率为7/8。
(2)同理,经过“与”门后,*
369i i i i a a a a +++=
所以*
{}i a 的周期仍为T ,369{},{},{}i i i a a a +++通过“与”门后,只有111输出为1,其余为0,所以为1的概率为1/8,为0 的概率为7/8。
12-6、写出p=7和p=11的二次剩余序列。
考点分析:考察二次剩余式的概念和求解方法。如果能找到一个整数x ,它使2
1(mod )x p ≡。若方程成立,认为方程有解,满足此方程的i 就是模p 的二次剩余;否则i 就是模p 的非二次剩余。当规定01a =-时,有
1,1,i i a i ?=?-?若是模p 的二次剩余若是模p 的非二次剩余
解:(1)当p=7时,有
2222
2
2
11(mod 7),24(mod 7),32(mod 7)42(mod 7),54(mod 7),61(mod 7)
======
所以1,2,4为模7的二次剩余,3,5,6为模7的非二次剩余。因此得到p=7的
二次剩余序列:-111-11-1-1
(2)当p=7时,有
222222
2
2
2
2
11(mod11),24(mod11),39(mod11),45(mod11),53(mod11)63(mod11),75(mod11),89(mod11),94(mod11),101(mod11)
==========
所以1,3,4,5,9为模11的二次剩余,2,6,7,8,10为模11的非二次剩余。
因此得到p=11的二次剩余序列:-11-1111-1-1-11-1。
12-7、试验证p=3和p=7的二次剩余序列为m 序列。
解:(1)p=3,二次剩余序列:一+一,用二进制表示即101。因为2
213-=,所以为两级
移存器。由序列可看出状态转换为100111→→,无重复,所以该序列为m 序列。
(2)p=7,二次剩余序列:一+十一+一一,即10010110因为3
217-=,所以为三级移
存器,由序列可看出状态转换为100001010101011111110→→→→→→,无重复,所以该序列为m 序列。
12-8、若用一个由九级移存器产生的m 序列进行测距,已知最远目标为1500km ,求加于移存器的定时脉冲的最短周期为多少?
考点分析:考察m 序列的应用。m 序列进行测距的原理框图,如图12-2所示。用一移位的m 序列与被测量的经过传输路径时延的m 后列相关。当两个序列的相位相同时,得到的相关峰,有移位r ,序列与原m 序列的相位差可以求得时延。这种方法的测量杆度是所用m 序列的一个码元宽度。
图 12-2
解:本题中,传输的距离是150023000km ?=
所以,传输m 序列共需时间 28
3000
10310
t s -=
=? 定时脉冲的最短周期是在移位另外整个序列时才得到相关峰的情况下发生的。此时,共需移位9
21511-=,故最短周期为 619.51019.5511
t
T s us -=≈?≈
附录:
12-1、已知特征方程231()1f x x x =++,3
2()1f x x x =++。
(1)构造两个m 序列发生器;
(2)求这两个m 序列发生器产生的m 序列; (3)验证这两个m 序列的正交性。
解:(1)特征方程231()1f x x x =++,3
2()1f x x x =++所对应的m 序列发生器分别如
图12-3(a)和(b)所示。
图 12-3
(2)设初始状态为110,图12-3(a)所示的状态变换时序表如表12-1所示,输出的。序列为1110010:图12-3(b)所示的状态变换时序表如表12-2所示,输出的m 序列为1110100。
表12-1 表12-2
12-2、若多项式满足3()1f x x x =++,试验证它为本原多项式? 解(1)3()1f x x x =++为既约的;
(2)由n=3,m=7,73321(1)(1)(1)x x x x x x +=+++++,则能整除1m
x +
(3)62221(1)(1)x x x x +=+++,54321(1)(1)x x x x x x +=+++++,441(1)x x +=+,则不能整除则能整除1q
x +。故为本原多项式。
12-3、若特征多项式3
()1f x x x =++,试: (1)验证它是本原多项式;
(2)由它构造一个m 序列产生器;
(3)设初始状态为110,写出一个周期的时序表; (4)写出一个周期的输出序列。 解:(1)本原多项式需满足三个条件: 1)3
()1f x x x =++为即约; 2)3,217n
n p ==-=
又 7323
11
(1)(1)()1p x x x x x f x x x
++==+++++,说明()f x 能整除1p x +; 3)6q =时,6
2
2
2
1(1)(1)x x x x +=+++; 5q =时,5
4
3
2
1(1)(1)x x x x x x +=+++++; 4q =时,4
4
1(1)x x +=+;
说明()f x 不能整除1,p
x q p +<;于是得结论:3
()1f x x x =++是本原多项式。 (2)m 序列产生器如图12-4所示。
图 12-4
(3)由上图得,2201201',','a a a a a a a =+==,于是得时序表如表12-3所示。
表 12-3
(4)输出序列为11101000。
说明:3
()1f x x x =++对应的二进制码为1011,对应的八进制码为8(13),其逆多 项式2
3()1f x x x =++,对应的二进制码为1101,对应的八进制码为8(15)。 用逆多项式'()f x 作为特征多项式亦可产生m 序列,它与()f x 产生的m 序列互为逆
码。
12-4、已知m 序列的本原多项式为4
()1f x x x =++,试用移位寄存器构成m 序列产生器, 并写出该m 序列。
解:m 序列是最长线性移位寄存器序列,是伪随机序列中最重要的序列中的一种,这种序列 易于产生,有优良的自相关特性,在直扩系统中用于扩展要传送的信号,在调频系统中用来控制调频系统的频率合成器,组成随机调频图案。
m 序列的本原多项式为4
()1f x x x =++,所以用移位寄存器构成的m 序列产生器如图 12-5所示。
图 12-5
求该m 序列用长除法,即按升幂排列(除法中的加减均为模二加)
0123456789101112131415161718191
11
10
10
11
00
1
1
1
1
1
a a a a a a a a a a a a a a a a a a a
a
从以上可以看出从15a 开始重复原序列,故该序列的周期为15,正好为4级最长线性移位 寄存器序列,即m 序列,该序列为1111。
12-5、已知某线形反馈移存器序列发生器的特征多项式为3
2
()1f x x x =++,请画出此序列发生器的结构图,写出它的输出序列(至少包括一个周期),并指出其周期是多少? 解:此序列发生器的结构图如图12-6所示。
图 12-6
输出序列为:10111001011100
周期为:7
12-6、已知m 序列的特征多项式为4
()1f x x x =++,写出此序列的一个周期中的所有游程。 解:该m 序列的周期为15,一个周期为1100,共有8个游程:
1 000 1111 0 1 0 11 00
其中长度为1的游程有4个,长度为2的游程有2个,长度为3的游程有1个,长度为4的游程有1个。
12-7、利用本原多项式7
3
()1f x x x =++构成m 序列,试: (1)构造相应的移存器结构; (2)求其一个周期内的游程分布。 解:(1)移存器的结构如图12-7所示。
图 12-7 (2)游程总数为2
712
264n --==个,具体分布如表12-4所示。