chase简化算法分析.docx

Chase译码算法的简化分析本改进的chase译码算法对chase译码原理没有任何改变，也没有任何的近似，只是对中间参数的计算过程进行了简化，降低了计算量。从理论分析上，大大降低了译码复杂度，但性能没有任何改变。可简化的参数：1、校验子 2、偶校验 3、距离度量。一、 测试图样的产生测试图样按照传统排序方法，如图1所示图1 测试图样的产生图中p=4，共24个测试图样。通过观察，下标为m和下标为2b-1+m的测试图样之间，只有jb处的值不同，并且都是从“0”变为“1”，其余位置的值保持不变。其中b=1，2，p；m=0，1，2，2b-1-1。在下文中的校验子等计算中充分利用了此规律。1. 校验子计算传统的chase算法需要对2p个测试序列分别进行代数译码，重复计算太多。改进的chase算法只需计算一次校验子，其他校验子通过递归得出。第一个测试序列Z0的校验子： （1-1）其中Y表示硬判决序列，TP0表示Z0对应的测试图样，TP0为0000。第二个测试序列的校验子： （1-2）表示校验矩阵第l1列的转置。通过以上规律，其余2p-2个测试序列的校验子可以通过递归计算得出： （1-3）其中，b=1，2，p；m=0，1，2，2b-1-1。H(jb)表示校验矩阵的第jb列，正如前面对测试图样的观察规律所得。其余2p-1个测试序列的校验子也可以通过图2直观的表示出来，在扩展汉明码中，若校验子非零，则可通过校验子来表明错误码元的位置。图2 校验子计算2. 计算偶校验2.1 传统算法:设汉明码（n,k,d）的一个码字C=（c1,cl,cn）,其中。其扩展码为，其中cep为偶校验： （2-1）2.2 简化算法：a. 首先计算硬判决序列的偶校验位 （2-2）b. 然后，分别找出各个测试图样中“1”的个数是偶数还是奇数，分别表示“1”的个数为偶数或奇数的测试图样的下标集合，对于图1中给出的测试图样，很明显，剩余集合可通过递归得出： （2-3）其中k=1，2，p-1。当p=3时，可得图3，即下标为0，3，5，6的测试图样中有偶数个“1”，其余为奇数个“1”。图3 测试图样中1个数为偶数或奇数的下标c. 计算候选码字的偶校验位： （2-4）其中， （2-5）3. 度量简化对欧氏距离公式通过简化，用内积度量代替欧氏距离。 欧氏距离定义如下： （3-1）为了有效译码，用内积度量代替欧氏距离度量，选择与接收向量R具有最大内积li的候选码字作为最优判决码字。在计算内积度量li的过程中，我们讨论一种有效方法，引入局部度量hi，当i=0时， （3-2）其中，rj为接收向量元素（软输入），zj为硬判决序列元素，也可以理解成第一个测试序列码字元素。注意：在计算其余局部度量时，zj指的是测试序列元素！也可以通过和修正度量进行对比得出。对于其余测试序列，可通过递归得到： （3-3）其中，b=1,2,p; m=0,1,2,2b-1-1。表示软输入的不可靠位，的符号与硬判决y对应。上式同样利用了在测试图样中发现的规律。为方便此部分理解，举例如下（设p=3）(TP表示测试序列对应的测试图样)图4 以y=0 1 0 时为例得出的测试序列 第1行的y为p个不可靠位对应的硬判决元素，TP表示测试图样，表示测试序列，从图4中发现如下规律：规律1：当硬判决y中最不可靠位元素为0时，下标相差2b-1+m-m的测试序列jb位置处的值会从“0”变为“1”。规律2：当硬判决y中最不可靠位元素为1时，下标相差2b-1+m-m的测试序列jb位置处的值会从“1”变为“0”。又由公式可知，当zj从“0”变为“1”时，度量就会增加2rj；当zj从“1”变为“0”时，度量就会减小2rj。结合这两个规律便可得出上面递归公式。为方便观察，给出了hi的递归计算表图5 hi的递归计算则修正度量ui的值由下式决定：（3-4）其中，表示测试序列中错误位置对应的元素，表示候选码字错误位置对应的元素，不过已经在测试序列的基础上得到纠正，所以两者正好相反。图6是chase算法简