第5讲_伪随机序列及编码.ppt

第5章伪随机序列及编码 5 1伪随机序列的概念5 2正交码与伪随机码5 3伪随机序列的产生5 4m序列5 5M序列5 6伪随机序列的应用 5 1伪随机序列的概念 在通信技术中 随机噪声是造成通信质量下降的重要因素 因而它最早受到人们的关注 如果信道中存在着随机噪声 对于模拟信号来说 输出信号就会产生失真 对于数字信号来说 解调输出就会出现误码 另外 如果信道的信噪比下降 那么信道的传输容量将会受到限制 伪随机序列应当具有类似随机序列的性质 在工程上常用二元 0 1 序列来产生伪噪声码 它具有以下几个特点 1 在随机序列的每一个周期内0和1出现的次数近似相等 2 每一周期内 长度为n的游程取值 相同码元的码元串 出现的次数比长度为n 1的游程次数多一倍 3 随机序列的自相关类似于白噪声自相关函数的性质 5 2正交码与伪随机码 若M个周期为T的模拟信号s1 t s2 t sM t 构成正交信号集合 则有 5 1 设序列周期为p的编码中 码元只取值 1和 1 而x和y是其中两个码组 式中 xi yi 1 1 i 1 2 n 则x和y之间的互相关函数定义为 5 2 若码组x和y正交 则有 x y 0 如果一种编码码组中任意两者之间的相关系数都为0 即码组两两正交 这种两两正交的编码就称为正交编码 由于正交码各码组之间的相关性很弱 受到干扰后不容易互相混淆 因而具有较强的抗干扰能力 类似地 对于长度为 的码组x的自相关函数定义为 5 3 对于 0 1 二进制码 式 5 2 的互相关函数定义可简化为 x y A D A D A D p 5 4 式中 A是x和y中对应码元相同的个数 D是x和y中对应码元不同的个数 式 5 3 的自相关函数也表示为 x j A D A D A D p 5 5 式中 A是码字xi与其位移码字xi j的对应码元相同的个数 D是对应码元不同的个数 伪随机码具有白噪声的统计特性 因此 对伪随机码定义可写为 1 凡自相关函数具有 5 6 形式的码 称为伪随机码 又称为狭义伪随机码 2 凡自相关函数具有 5 7 形式的码 称为广义伪随机码 狭义伪随机码是广义伪随机码的特例 5 3伪随机序列的产生 编码理论的数学基础是抽象代数的有限域理论 一个有限域是指集合F元素个数是有限的 而且满足所规定的加法运算和乘法运算中的交换律 结合律 分配律等 常用的只含 0 1 两个元素的二元集F2 由于受自封性的限制 这个二元集只有对模二加和模二乘才是一个域 一般来说 对整数集Fp 0 1 2 p 1 若p为素数 对于模p的加法和乘法来说 Fp是一个有限域 可以用移位寄存器作为伪随机码产生器 产生二元域F2及其扩展域F2m中的各个元 m为正整数 可用域上多项式来表示一个码组 域上多项式定义为 5 8 称其为F的n阶多项式 加号为模二和 式中 ai是F的元 anxn称为f x 的首项 an是f x 的首项系数 记F域上所有多项式组成的集合为F x 若g x 是F x 中的另一多项式 5 9 如果n m 规定f x 和g x 的模二和为 5 10 其中 bm 1 bm 2 bn 0 规定f x 和g x 的模二乘为 5 11 若g x 0 则在F x 总能找到一对多项式q x 称为商 和r x 称为余式 使得 f x q x g x r x 5 12 这里r x 的阶数小于g x 的阶数 式 5 12 称为带余除法算式 当余式r x 0 就说f x 可被g x 整除 图5 1是一个4级移位寄存器 用它就可产生伪随机序列 规定移位寄存器的状态是各级存数从右至左的顺序排列而成的序列 这样的状态叫正状态或简称状态 反之 称移位寄存器状态是各级存数从左至右的顺序排列而成的序列叫反状态 图5 1中的反馈逻辑为 5 13 图5 14级移位寄存器 当移位寄存器的初始状态是1000时 即an 4 1 an 3 0 an 2 0 an 1 0 经过一个时钟节拍后 各级状态自左向右移到下一级 末级输出一位数 与此同时模二加法器输出加到移位寄存器第一级 从而形成移位寄存器的新状态 下一个时钟节拍到来又继续上述过程 末级输出序列就是伪随机序列 在这种条件下 图5 1产生的伪随机序列是 这是一个周期长度p 15的随机序列 当图5 1的初始状态是0状态时 即an 4 an 3 an 2 an 1 0移存器的输出是一个0序列 4级移存器共有16个状态 除去一个0状态外 还有15个状态 对于图5 1来说 只要随机序列的周期达到最大值 这时无论如何改变移存器的初始状态 其输出只改变序列的初相 序列的排序规律不会改变 但是 如果改变图5 1四级移存器的反馈逻辑 其输出序列就会发生变化 例如 当反馈逻辑变成 5 14 时 给定不同的初始状态1111 0001 1011 可以得到三个完全不同的输出序列 111100111100 000101000001 101101101101 它们的周期分别是6 6和3 结论 1 线性移位寄存器的输出序列是一个周期序列 2 当初始状态是0状态时 线性移位寄存器的输出是一个0序列 3 级数相同的线性移位寄存器的输出序列与寄存器的反馈逻辑有关 4 序列周期p 2n 1 n级线性移位寄存器 的同一个线性移存器的输出还与起始状态有关 5 序列周期p 2n 1的线性移位寄存器 改变移位寄存起初始状态只改变序列的起始相位 而周期序列排序规律不变 5 4m序列 5 4 1线性反馈移位寄存器的特征多项式 1 线性反馈移位寄存器的递推关系式递推关系式又称为反馈逻辑函数或递推方程 设图5 2所示的线性反馈移位寄存器的初始状态为 a0a1 an 2an 1 经一次移位线性反馈 移位寄存器左端第一级的输入为 若经k次移位 则第一级的输入为 5 15 其中 l n k 1 n k 1 2 3 由此可见 移位寄存器第一级的输入 由反馈逻辑及移位寄存器的原状态所决定 式 5 15 称为递推关系式 图5 2n级线性反馈移位寄存器 2 线性反馈移位寄存器的特征多项式用多项式f x 来描述线性反馈移位寄存器的反馈连接状态 5 16 式 5 16 称为特征多项式或特征方程 其中 xi存在 表明ci 1 否则ci 0 x本身的取值并无实际意义 ci的取值决定了移位寄存器的反馈连接 由于c0 cn 1 因此 f x 是一个常数项为1的n次多项式 n为移位寄存器级数 可以证明 一个n级线性反馈移位寄存器能产生m序列的充要条件是它的特征多项式为一个n次本原多项式 若一个n次多项式f x 满足下列条件 1 f x 为既约多项式 即不能分解因式的多项式 2 f x 可整除 xp 1 p 2n 1 3 f x 除不尽 xq 1 q p 则称f x 为本原多项式 以上为我们构成m序列提供了理论根据 5 4 2m序列产生器 用线性反馈移位寄存器构成m序列产生器 关键是由特征多项式f x 来确定反馈线的状态 而且特征多项式f x 必须是本原多项式 现以n 4为例来说明m序列产生器的构成 用4级线性反馈移位寄存器产生的m序列 其周期为p 24 1 15 其特征多项式f x 是4次本原多项式 能整除 x15 1 先将 x15 1 分解因式 使各因式为既约多项式 再寻找f x 其中 4次既约多项式有3个 但 x4 x3 x2 x 1 能整除 x5 1 故它不是本原多项式 因此找到两个4次本原多项式 x4 x 1 和 x4 x3 1 由其中任何一个都可产生m序列 用f x x4 x 1 构成的m序列产生器如图5 3所示 图5 3m序列产生器 设4级移位寄存器的初始状态为1000 c4 c1 c0 1 c3 c2 0 输出序列 ak 的周期长度为15 5 4 3m序列的性质 1 均衡特性 平衡性 m序列每一周期中1的个数比0的个数多1个 由于p 2n 1为奇数 因而在每一周期中1的个数为 p 1 2 2n 1 偶数 而0的个数为 p 1 2 2n 1 1 奇数 上例中p 15 1的个数为8 0的个数为7 当p足够大时 在一个周期中1与0出现的次数基本相等 2 游程特性 游程分布的随机性 我们把一个序列中取值 1或0 相同连在一起的元素合称为一个游程 在一个游程中元素的个数称为游程长度 例如图5 2中给出的m序列 ak 000111101011001 在其一个周期的15个元素中 共有8个游程 其中长度为4的游程1个 即1111 长度为3的游程1个 即000 长度为2的游程2个 即11与00 长度为1的游程4个 即2个1与2个0 m序列的一个周期 p 2n 1 中 游程总数为2n 1 其中 长度为1的游程个数占游程总数的1 2 长度为2的游程个数占游程总数的1 22 1 4 长度为3的游程个数占游程总数的1 2 3 1 8 等等 一般地 长度为k的游程个数占游程总数的1 2k 2 k 其中1 k n 2 而且 在长度为k的游程中 连1游程与连0游程各占一半 长为 n 1 的游程是连0游程 长为n的游程是连1游程 3 移位相加特性 线性叠加性 m序列和它的位移序列模二相加后所得序列仍是该m序列的某个位移序列 设mr是周期为p的m序列mp的r次延迟移位后的序列 那么 5 17 其中 ms为mp某次延迟移位后的序列 例如 mp 000111101011001 mp延迟两位后得mr 再模二相加 mr 010001111010110 ms mp mr 010110010001111 可见 ms mp mr为mp延迟8位后的序列 4 自相关特性 m序列具有非常重要的自相关特性 在m序列中 常常用 1代表0 用 1代表1 此时定义 设长为p的m序列 记作 a1 a2 a3 ap p 2n 1 经过j次移位后 m序列为 aj 1 aj 2 aj 3 aj p 其中 ai p ai 以p为周期 以上两序列的对应项相乘然后相加 利用所得的总和 来衡量一个m序列与它的j次移位序列之间的相关程度 并把它叫做m序列 a1 a2 a3 ap 的自相关函数 记作 5 18 当采用二进制数字0和1代表码元的可能取值时 式 5 18 可表示为 5 19 式中 A D分别是m序列与其j次移位的序列在一个周期中对应元素相同 不相同的数目 式 5 19 还可以改写为 5 20 由移位相加特性可知 ai ai j仍是m序列中的元素 所以式 5 20 分子就等于m序列中一个周期中0的数目与1的数目之差 另外由m序列的均衡性可知 在一个周期中0比1的个数少一个 故得A D 1 j为非零整数时 或p j为零时 因此得 5 21 如图5 4所示 m序列的自相关函数只有两种取值 1和 1 p R j 是一个周期函数 即 R j R j kp 5 22 式中 k 1 2 p 2n 1 为周期 而且R j 是偶函数 即 R j R j j 整数 5 23 图5 4m序列的自相关函数 5 伪噪声特性 如果我们对一个正态分布白噪声取样 若取样值为正 记为 1 若取样值为负 记为 1 将每次取样所得极性排成序列 可以写成 1 1 1 1 1 1 1 1 1 这是一个随机序列 它具有如下基本性质 1 序列中 1和 1出现的概率相等 2 序列中长度为1的游程约占1 2 长度为2的游程约占1 4 长度为3的游程约占1 8 一般地 长度为k的游程约占1 2k 而且 1 1游程的数目各占一半 3 由于白噪声的功率谱为常数 因此其自相关函数为一冲击函数 把m序列与上述随机序列比较 当周期长度p足够大时 m序列与随机序列的性质是十分相似的 可见 m序列是一种伪噪声特性较好的伪随机序列 且易产生 因此应用十分广泛 5 5M序列 M序列是一种非线性的伪随机序列 它是最长序列 是由非线性移位寄存器产生的码长为2n的周期序列 M序列已达到n级移位寄存器所能达到的最长周期 所以又称为全长序列 M序列的构造可以在m序列基础上实现 因为m序列包含了2n 1个非零状态 仅缺一个0状态 因此 只要在m序列适当的位置上插入一个0状态 即可完成码长为2n 1的m序列向码长为2n的M序列转换 一般地讲 0状态插入应在状态xnxn 1 x1 100 0之后 同时紧跟0状态的后继序列状态应当是原m序列状态 后继状态应是0 001即可 因此 重要是检测后n 1个0 即检测M序列的状态xn 1xn 2 x1然后加上原反馈逻辑f0 x1 x2 xn 得到新的反馈逻辑 5 24 现以本原多项式f x 1 x x4产生的码长为15的m序列加长码长为16的M序列四级移位寄存器为例说明 四级M序列发生器的原理图如图5 5所示 反馈逻辑函数为 5 25 图5 5中的000状态检测器可检测到1000和0000两个状态 当检测到1000状态时 检测器输出为1 这个1与反馈输入an 此时为1 模二加得到0 输入到an 1 使后续状态成为0状态 在0状态时检测器继续输出1 此1与反馈输入an此时为0 模二加得到1 输入到an 1 使0状态的后续状态保持原来的循环状态0001 这样就把0状态插进原始序列之中 图5 5四级M序列发生器 下面给出M序列状态流程 设初始状态为0100 0100 1001 0011 0110 1101 1010 0101 1011 0111 1111 1110 1100 1000 0000 0001 0010 0100 初态 构成M序列的方法很多 但实现起来并非易事 要能方便 简练地得到M序列 仍需作不懈努力 周期为p 2n的M序列的随机特性有下列几点 1 在一个周期内 序列中0和1的元素各占一半 即各为2n 1 2 在每一个周期内共有2n 1个游程 其中同样长度的0游程和1游程的个数相等 当1 k n 2时 长为k的游程占总游程数的一半 长为n 1游程不存在 长为n的游程有两个 3 归一化自相关函数RM 具有如下相关值 RM 0 1 RM 00 n RM n 1 4W f0 p 0 其中 W f0 是M序列发生器的反馈逻辑函数表示成 f x1 x2 xn f0 x1 x2 xn 1 xn 的形式时 f0取值为1的个数 通常把W f0 叫做f0的权重 当 n时 RM 无确定表示式 只能从给定的M序列中逐点移位计算得到 以上特点说明 M序列的自相关函数是多值的 而且有较大的旁峰 长度相同的M序列具有不同的自相关特性 M序列的自相关特性也是多值的 对于任意的自然数n 一定有n级M序列以及产生此M序列的n级移位寄存器存在 n级M序列的总长为 Mn 2 2n 1 n 5 26 表5 1列出了不同n值时所得到的M序列和m序列的数目 可以看出 当n 4时 M序列比m序列的数目多得多 这对于某些需要地址序列很多的应用场合提供了选择的灵活性 表5 1M序列和m序列数目的比较 5 6伪随机序列的应用 5 6 1扩展频谱通信 扩展频谱通信系统是将待传送的基带信号在频域上扩展为很宽的频谱 远远大于原来信号的带宽 在接收端再把已扩展频谱的信号变换到原来信号的频带上 恢复出原来的基带信号 该系统的方框图如图5 6所示 图5 6扩展频谱通信系统 扩展频谱技术的理论基础是香农公式 对于加性白高斯噪声的连续信道 其信道容量C与信道传输带宽B及信噪比S N之间的关系可以用下式表示 5 27 这个公式表明 在保持信息传输速率不变的条件下 信噪比和带宽之间具有互换关系 就是说 可以用扩展信号的频谱作为代价 换取用很低信噪比传送信号 同样可以得到很低的差错率 扩频系统有以下特点 1 具有选择地址能力 2 信号的功率谱密度很低 有利于信号的隐蔽 3 有利于加密 防止窃听 4 抗干扰性强 5 抗衰落能力强 6 可以进行高分辨率的测距 扩频通信系统的工作方式有 直接序列扩频 跳变频率扩频 跳变时间扩频和混合式扩频 1 直接序列扩频方式 直接序列扩频 DirectSequenceSpreadSpectrum 又称为直扩 DS 它是用高速率的伪随机序列与信息序列模二加后的序列去控制载波的相位而获得直扩信号的 图5 7 a 和 b 就是直扩系统的原理方框图和扩频信号传输图 在图5 7中 信息码与伪码模二加后产生发送序列 进行2PSK调制后输出 在接收端用一个和发射端同步的伪随机码所调制的本地信号 与接收到的信号进行相关处理 相关器输出中频信号经中频电路和解调器 恢复原信息 图5 7直扩系统方框图和扩频信号传输图 图5 7直扩系统方框图和扩频信号传输图 2 跳变频率扩频方式 跳变频率扩频 FrequencyHoppingSpreadSpectrum 又称跳频 FH 它是用伪码构成跳频指令来控制频率合成器 并在多个频率中进行选择的移频键控 跳频指令由所传信息码与伪随机码模二加的组合来构成 它又称为跳频图案 跳频系统原理图如图5 8所示 在发送端信息码与伪码调制后 按不同的跳频图案去控制频率合成器 使其输出频率在信道里随机跳跃地变化 在接收端 为了对输入信号解跳 需要有与发送端相同的本地伪码发生器构成的跳频图案去控制频率合成器 使其输出的跳频信号能在混频器中与接收到的跳频信号差频出一个固定中频信号 经中频放大器后 送到解调器恢复出原信息 图5 8跳频系统原理图 3 跳变时间扩频方式跳变时间扩频 TimeHoppingSpreadSpectrum 又称为跳时 TH 该系统是用伪码序列来启闭信号的发射时刻和持续时间的 该方式一般和其他方式混合使用 以上3种工作方式是基本的工作方式 最常用的是直扩方式和跳频方式两种 4 混合式扩频方式在实际系统中 仅仅采用单一工作方式不能达到所希望的性能时 往往采用两种或两种以上工作方式的混合式扩频 如 FH DS DS TH FH TH 等 5 6 2码分多址 CDMA 通信多址系统是指多个用户通过一个共同的信道交换消息的通信系统 传统的信号划分方式有频分和时分 相应地可构成频分多址系统和时分多址系统 一种新的多址方式是码分多址系统 它给每个用户分配一个多址码 要求这些码的自相关特性尖锐 而互相关特性的峰值尽量小 以便准确识别和提取有用信息 同时各个用户间的干扰可减小到最低限度 码分多址扩频通信方式如图5 9所示 同时工作的通信用户共有k个 各自使用不同的伪随机码PNi t i 1 2 k 发射的信息数据分别是di t i 1 2 k 对于扩频通信系统中的某一接收机 尽管想接收第i个通信用户发送来的信息数据di t 实际进入接收机的信号除第i个发来的信号外 也有其他 k 1 个用户发射出来的信号 由于伪随机码的相关特性 该接收机可以识别和提取有用信息 而把其他用户的干扰减小到最低 图5 9码分多址扩频通信系统模型 5 6 3通信加密 数字通信的一个重要优点是容易做到加密 在这方面m序列应用很多 数字加密的基本原理如图5 10所示 将信源产生的二进制数字消息和一个周期很长的m序列模二相加 这样就将原消息变成不可理解的另一序列 将这种加密序列在信道中传输 被他人窃听也不可理解其内容 在接收端再加上一同样的m序列 就能恢复为原发送消息 图5 10利用m序列加密 设信源发送的数码为X1 1011010011 m序列Y 1100001011 数码X1与m序列Y的各对应位分别进行模二加运算后 获得序列E 显然E不同于X1 它已失去了原信息的意义 如果不知道m序列Y 就无法解出携带原信息的数码X1 从而起到保密作用 假设信道传输过程中无误码 序列E到达接收端后与m序列Y再进行模二加运算 可恢复原数码X1 即 上述工作过程如图5 5所示 图5 5数字信号的加密与解密 5 6 4误码率的测量 在数字通信中误码率是一项主要的性能指标 在实际测量数字通信系统的误码率时 一般测量结果与信源送出信号的统计特性有关 通常认为二进制信号中0和1是以等概率随机出现的 所以测量误码率时最理想的信源应是随机信号产生器 由于m序列是周期性的伪随机序列 可作为一种较好的随机信源 通过终端机和信道后 输出仍为m序列 在接收端 本地产生一个同步的m序列 与收码序列逐位进行模二加运算 一旦有错 就会出现 1 码 用计数器计数 如图5 12所示 图5 12误码率测试 5 6 5数字信息序列的扰码与解扰数字通信系统的设计及其性能都与所传输的数字信号的统计特性有关 如果我们能够先将信源产生的数字信号变换成具有近似于白噪声统计特性的数字序列 再进行传输 在接收端收到这个序列后先变换成原始数字信号 再送给用户 这样就可以给数字通信系统的设计和性能估计带来很大方便 所谓加扰技术 就是不用增加多余度而搅乱信号 改变数字信号统计特性 使其近似于白噪声统计特性的一种技术 具体做法是使数字信号序列中不出现长游程 且使数字信号的最小周期足够长 这种技术的基础是建立在伪随机序列理论之上的 采用加乱技术的通信系统通常在发送端用加乱器来改变原始数字信号的统计特性 而接收端用解扰器恢复出原始数字信号 图5 13中给出一种由7级移存器组成的自同步加扰器和解扰器的原理方框图 由图可以看出 加扰器是一个反馈电路 解扰器是一个前馈电路 它们分别都是由5级移存器和两个模二加法电路组成的 图5 13自同步加扰器和解扰器原理框图 设加乱器的输入数字序列为 ak 输出为 bk 解乱器的输入数字序列为 bk 输出为 ck 加扰码器的输出为 而解扰器的输出 上两式表明 解扰后的序列与加扰前的序列相同 这种解扰器是自同步的 因为如果信道干扰造成错码 它的影响只持续错码位于移存器内的一段时间 即最多影响连续7个输出码元 如果断开输入端 扰码器就变成一个线性反馈移存器序列产生器 其输出为一周期性序列 一般设计反馈抽头的位置 使其构成