一种利用约束Viterbi算法改进IS95协议信道编码的方法

1、例：设顾客以每分钟6人的平均速率进入某商场，这一过程可用用Poisson过程来描述。又该进入该商场的每位顾客买东西的概率为，且每位顾客是否买东西互不影响，也与进入该商场的顾客数无关。求一天（12小时）在该商场买东西的顾客数的均值。3条件Poisson过程定义：设随机变量，在的条件下，计数过程是参数为的Poisson过程，则称为条件Poisson过程。定理：设是条件Poisson过程，且，则（1）；（2）例：设意外事故的发生频率受某种未知因素影响有两种可能，且 ，为已知。已知到时刻t已发生了n次事故。求下一次事故在t+s之前不会到来的概率。另外，这个发生频率为的概率是多少？第三章 Markov

2、链3.1 基本概念定义：随机过程称为Markov链，若它只取有限或可列个值（常用非负整数集来表示），并且对任意的，及任意状态，有=，其中表示过程在时刻n处于状态，称为该过程的状态空间，记为. 上式刻画了Markov链的特性，称为Markov性。定义：称条件概率为Markov链的一步转移概率，简称转移概率，记为，它代表处于状态的过程下一步转移到状态的概率。定义：当Markov链的转移概率=只与状态有关，而与n无关时，称之为时齐Markov链；否则，就称之为非时齐的。注：我们只讨论时齐Markov链，简称Markov链。定义：当Markov链的状态为有限时，称为有限链，否则称为无限连。但无论状态有

3、限还是无限，我们都可以将（）排成一个矩阵的形式，令P=（）=为转移概率矩阵，简称转移矩阵。容易看出（）具有性质：（1），；（2）=1，。例3.1.1：考虑一个包含三个状态的模型，若个体健康，认为他处于状态，若他患病，认为他处于状态，若他死亡，认为他处于状态，易见这是一个Markov链，转移矩阵为P=例：（赌徒的破产或称带吸收壁的随机游动）系统的状态时，反映赌博者在赌博期间拥有的钱数，当他输光或拥有钱数为n时，赌博停止，否则他将持续赌博。每次以概率p赢得1，以概率q=1-p输掉1。这个系统的转移矩阵为P=例：（带反射壁的随机游动）设上例中当赌博者输光时将获得赞助1继续赌下去，就如同一个在直线上做

4、随机游动的球在到达左侧0点处立刻反弹回一样，这就是一个一侧带有反射壁的随机游动，此时转移矩阵为：P=例：（自由随机游动）设一个球在全直线上做无限制的随机游动，它的状态为0，它是一个Markov链，转移矩阵为：P=练习：设有一只蚂蚁在图上爬行，当两个节点相邻时，蚂蚁将爬向它邻近的一点，并且爬向任何一个邻近节点的概率是相同的，求转移矩阵。2 n步转移概率， C-K方程定义3.1.5：称条件概率，为Markov链的n步转移概率，相应地称为n步转移矩阵。规定：问题：和是什么关系？定理3.1.1：Chapman-Kolmogorov方程，简称C-K方程对一切有（1）（2）证明：例3.1.5：（赌徒的破产

5、或称带吸收壁的随机游动）系统的状态时，反映赌博者在赌博期间拥有的钱数，当他输光或拥有钱数为n时，赌博停止，否则他将持续赌博。每次以概率p赢得1，以概率q=1-p输掉1。设，赌博者从2元赌金开始赌博，求他经过4次赌博之后输光的概率。例：甲乙两人进行某种比赛，设每局甲胜的概率是p。乙胜的概率是q，和局的概率是r，。设每局比赛后，胜者记“+1”分，负者记“-1”分，和局不计分，且当两人中有一人获得2分时比赛结束。以表示比赛至第n局时甲获得的分数，则为时齐Markov链，求甲获得1分的情况下，不超过两局可结束比赛的概率。例：质点在数轴上的点集上做随机游动，质点到达点-2后，以概率1停留在原处；到达点2

6、后，以概率1向左移动一点；到达其他点后，分别以概率向左、右移动一点，以概率停留在原处。试求在已知该质点处于状态0的条件下，经3步转移后仍处于状态0的概率。例：（广告效益的推算）某种啤酒A的广告改变了广告方式，经调查发现买A种啤酒及另外三种啤酒B, C，D的顾客每两个月的平均转换率如下（设市场中只有这四种啤酒）：假设目前购买A，B, C，D四种啤酒的顾客的分布为（25%，30%，35%，10%），试求半年后啤酒A的市场份额。3.2 状态的分类及性质定义3.2.1：若存在使得，称状态可达状态，记为。若同时有，则称与互通，记为。定理3.2.1：互通是一种等价关系，即满足：（1） 自反性：；（2） 对

7、称性：，则（3） 传递性：，则证明：定义3.2.2：把任何两个互通状态归为一类，若Markov链只存在一个类，就称它是不可约的；否则称为可约的。例3.2.1：在例3.1.1中考三个状态：健康状态，患病状态，死亡状态，可分为几个类？定义3.2.3：若集合非空，则称它的最大公约数为状态的周期。若，称是周期的。若，称是非周期的。规定，上述集合为空集时，称的周期为无穷大。注：（1）虽然有周期但并不是对所有的n，都大于0。请举出反例：（2）虽然有周期但可能，举出反例：定理3.2.2：若状态同属一类，则。证明：定义3.2.4：对于任何状态，以记从出发经n步后首次到达的概率，则有令，如果，称状态为常返状态；

8、如果，称状态为非常返状态。问题：的含义是什么？定义3.2.4：（1）对于常返状态，定义，可以知道表示的是由出发再返回到所需的平均步数（时间）。（2）对于常返状态，若，则称为正常返状态；若，则称为零常返状态。（3）若为正常返状态，且是非周期的，则称之为遍历状态。若是遍历状态，且，则称为吸收状态，此时显然。例3.2.3：设Markov余轮, 许明, 周霆, 陈东侠(福州大学信息工程学院, 福建福州350002摘要:I S95具有两个速率集, 在同一个速率集中, 不同的速率其数据帧的长度不同, 为了使进入正交调制的数据帧的长度相同, 其采用了信号重复器。信号重复器进行简单的重复作用, 使得带宽不能充

9、分利用。文中提出的方法利用一个信号发生器, , 卷积编码后的数据帧长度同样符合要求, 约束V iterbi 译码。在BSC 。关键词:信道编码; 约束V ; ; 中图分类号:A me for I mprovi n g the Channel Codi n g Perfor mance i nI S 95Protocol by Usi n g Constra i n ed Viterbi Algorith mYU L un, XU M ing, ZHOU Ting, CHEN D ong -xia(I nfor mati on Engineering School, Fuzhou Univers

10、ity, Fuzhou 350002, China Abstract:I S95p r ot ocol has t w o rate sets, in each rate set, different rate has different fra me length . I n or 2der t o adjust the fra me length t o the sa me, a sy mbol repeater is used, which just repeats the sy mbol si m 2p ly, and the band width is not fully made

11、use of . I n the sche me p r oposed in this paper, a sy mbol generat or is used t o p r oduce s ome known sy mbols, this known sy mbol sequence is taken as an input t o convoluti onal encoder, and makes the length of data fra mes after encoder meet the require ment of I S95p r ot ocol . Since the co

12、nstrained V iterbi algorith m is used in the receiver, those sy mbols p r oduced by sy mbol generat or can be regarded as useful contrained condit ons and i m p r ove the decoding perf or mance greatly . The si m ulati on result over BSC channel shows that this sche me can achieve good perf or mance

13、 when the channel err or rate is high .Key words:channel coding; constrained V iterbi algorithm; I S95p r ot ocol; sy mbol repeater; sy mbol gener 2at or国Qualcomm 公司提出的I S95通信协议, 于1993年1引言当前的无线通信系统的信道编码都采用级联1码, 其中外码为循环冗余校验码, 内码为卷积码。此外, 为了实现了传输功率控制技术(Trans m it Pow 22er Contr ol, TPC , 都采用了多码率设计。例如,

14、美定理3.2.3：状态第47卷第3期2007年6月Teleco mmunicati on Engineering Vol . 47No . 3Jun . 2007m s, 所以不同的传输速率对应不同的数据帧长。在发送端数据进行卷积编码后, 为了使进入交织器的数据帧长相同, 其采用了信号重复器(Sy mbol Repe 2titi on , 针对不同的速率对编码后的数据帧分别进行1×、2×、4×、8×的重复, 在接收端则采用维特比译码。在本文提出在无线通信系统中采用约束V iterbi为非常返状态时，有 的速率, 每个原始数据信号进入编码后, 信号发生器产

15、生3个规定的符号进入编码器进行编码, 之后再对下一个原始数据的信号进行编码。据帧长度同样符合要求, 码。本文首先介绍了其信道编码方案, 之后探讨了在这一协议中利用约束V iterbi 算法的可能性, 最后就所提出的改进方案和原I S95协议中的相关方案进行比较。到的用户信息帧为每帧20m s 。除了2. 4kbit/s 和1. 2kbit/s 数据外, 帧质量指示器(Fra me Quality I n 2dicat or 在每帧的末端加帧质量指示比特(循环冗余校验比特 , 用于帮助接收端判断数据速率和误帧率。2. 4kbit/s 和1. 引理3.2.1：对任意状态80882882400814

16、4416087282无线通信系统中信道编码方案当前主要的无线通信系统的信道编码部分基本相同, 都采用了循环冗余校验加卷积码的级联码作为主要的编码方案, 其中又因为传输功率控制技术而采用了多码率设计, 为了保证码率匹配又采用了信号重复器。现以I S95协议中的业务信道的信道编码部分作为范例, 说明其信道编码的主要技术。I S95的信道编码部分见图1。卷积编码器为R =1/3, K =9, 生成多项式为g 0=557, g 1=663, g 2=711, 其经过重复后的数据帧长度为576bit 。对于业务信道, 码元经过编码后, 在分组交织之前, 只要输入信号的数据率低于本信道的最高输入数据率,

17、在分组之前都要进行码元重复处理。例如对于输入9. 6kbit/s, 码元不重复; 如果输入是4. 8kbit/s, 则每个码元重复1次(每个码元符号连续出现2次 ; 如果输入是2. 4kbit/s, 则每个码元重复3次(每个码元符号连续出现4次 ; 如果输入是1. 2kbit/s, 则每个码元重复7次(每个码元符号连续出现8次 。重复符号的发送功率必全速率符号的功率低, 例如对于4. 8kbit/s, 每个码元符号重复一次, 但在半功率上发送。同时, 重复的符号可以进行时间分集接收, 为无线信道抵抗衰落提供附加的措施, 增加接收的可靠性。3约束V ite rbi 译码在无线通信系统中的应用 。

18、 引理3.2.2：若且为常返状态，则。定理3.2.4：常返性是一个类性质。2。图4无约束时的错误译码和有约束时的正确译码5采用约束V ite rb i 译码前后的性能比较测试采用I S95的速率集1, 其具体数据见表1, 卷积编码器为R =1/3, K =9, 生成多项式为g 0=557, g 1=663, g 2=711, 其经过重复后的数据帧长度为576bit 。数据经过AW G N 信道, 调制方式为BPSK 调制, 最后进行V iterbi 译码。在改进的算法中, 信号生成器生成的信号为全零, 一个数据帧的信号进入卷积编码后, 再由M 个信号生成器生成的信号(即M 个零 进入卷积编码,

19、 不同速率下M 的值见表2, 编码后的数据帧的长度仍然为576bit 。I S95考虑两种对重复信号的处理方法, 一种是图3递归系统卷积码(2, 1, 2当一个位被确定为正确后, 其不仅自身译码正确, 同时可以影响其附近的位。例如采用图3所示的递归系统卷积码(Recursive Syste matic Convolu 2ti onal Code, RSC , 从零状态开始, 到零状态结束。直接去掉重复信号(D irectly D iscarded , 这种方法比较简单, 但效果不好; 另一种是考虑对重复信号进行5时间的分集接收(D iversity , 该方案较为复杂, 但经过信道后, 由于噪

20、声干扰, 接收段收到的序列中, 有3位数据发生错误(加框的数据 :00110010111。如果按照一般的V iterbi 译码(图4(a 中粗线表示的路径 , 其得到的结果将是0011可以充分利用重复信号。图5为实验结果, 测试了译码后的误包率(Packet Err or Rate, PER 与误比特率(B it Err or Rate, BER 。对于每种传输速率在采用改进后的系统与约束算法进行译码后与I S95协议进行比较。5第47卷第3期2007年6月Teleco mmunicati on Engineering Vol . 47No . 3Jun . 2007每帧作为一包, 共测试10

21、00组。表2I S95标准速率集1具体数据传输速率(bit/ s 每帧数据长度(bit 添加的CRC 校验位(bit 卷积编码器复位(bit 编码后每帧的长度(bit 重复次数(次M (bit 48008088288212400400814443可以提高约45dB 甚至更多, 但是应考虑到分集接收需要有较复杂的硬件支持, 故其分集可在解调之前完成。本文提供的改进算法的性能居于中间, 与简单得译码方案相比约提高23d B , 但差于分集接收的方法; 同样其复杂度也处于中间, 在编码端需要引入信号发生器, 在解码端需要进行修改。虽然直接去掉重复信号的方法最简单, 但是其效果最差。参考文献:1. M.北京:电子工业, . M.北京:北京邮, 2000:76-125.3Lei Cao , ChangW en Chen . A Novel Pr oduct Coding andR