7. 循环码
7.1 循环码定义
- 循环码是线性分组码的最重要的一类码，它的结构可以用有限域多项式完整地描述。
循环码有两个基本特点：
- 一是编译码电路非常简单，易于实现
- 二是其代数性质好，编译码性能分析方便
一个（n,k）线性分组码C，如果码组中的任何一个码字的循环移位也是这个码组中的一个码字，则称这个线性分组码为循环码。
- 即，如果C^(0)=[cn-1, cn-2, …, c1, c0] ∈C为一个码字，则有C^(1)=[cn-2, cn-3, …, c1, c0, cn-1]∈C ，这种特性也称为循环自闭性
- 循环码可以用监督矩阵和生成矩阵描述，但更方便的是用域上多项式来描述，一个（n,k）循环的码字向量c^(0)用一个n-1次多项式描述，可以表示为
-
7.2 GF(2)上多项式
如果多项式
的系数取自二元有限域GF(2)，则称 f(x) 为二元域GF (2)上的多项式。fi=0或fi=1- 如果多项式的系数取自有限域GF (q)，则称为有限域GF (q)上的多项式。如果多项式系数取自实数域，那就是我们常见的普通n次多项式。域上多项式的一般形式：
- 通常习惯写成降幂排列形式
- 多项式代数运算
- 域上的多项式也存在加法、减法、乘法和除法的计算。
- 以GF(2)上的多项式为例，如果另一个GF (2)上的m次多项式为(m<n)
- f(x)和g(x)的相加为x的同次幂的系数相加
其中系数的加法为GF (2)上的模二加法
f(x)和g(x)的相减为x的同次幂的系数相减
- f(x)和g(x)的相乘时
- 二元域上多项式的加法和乘法计算具有以下性质：①交换律，②结合律，③分配律
- 如果多项式g(x)的次数不为零，当f(x)除以g(x)时，可以得到二元域上唯一的另外两个多项式
- 或者写成
- 其中q(x)称为商多项式，r(x)称为余多项式，余多项式r(x)的次数低于g(x)的次数。
如果r(x)=0，即f(x)能被g(x)除尽，则称g(x)为f(x)的因式，f(x)为g(x)的倍式。
如果GF(2)上多项式，F(x)，N(x)，Q(x)，R(x)满足：
- 则称在模N(x)条件下F(x)等于R(x)，记为
- 不可约多项式
- 如果f(x)为GF(2)上的m次多项式，它不能被任何次数小于m，大于0的多项式除尽，则称其为GF(2)上的不可约多项式（ irreduciblepolynomial）
- f(x)=x^3+x+1，f(x)=x^4+x+1，均为不可约多项式
根据有限域上多项式理论，可以证明
- GF(2)上的多项式若有偶数项，则一定可被x+1除尽
- 对于任意m≥1，都存在m次不可约多项式
- GF(2)上任意m次不可约多项式，一定能除尽x^n+1，其中n=2^m-1
- 例如：m=3的3次多项式f(x)=x^3+x+1，n=2^m-1=7，则f(x)一定可以除尽x^7+1
本原多项式
对于任意m≥1，如果f(x)为m次不可约多项式，且可整除x^n+1的最小n值为n=2^m-1，则称f(x)为xn+1的一个本原多项式（primitive polynomial）
- f(x)=x^4+x+1能够整除x^15+1，但不能整除任何n小于15的x^n+1，因此x^4+x+1是一个本原多项式
- f(x)=x^4+x^3+x^3+x+1是一个不可约多项式，但它不是本原的，因为它可以整除x^5+1
- 不可约多项式不一定是本原多项式，本原多项式一定是不可约的
- 对于给定的m，m次本原多项式可能是不唯一的
由多项式描述循环码
- 根据GF(2)域上多项式的计算关系可知，码字向量的循环移位可以用x乘上c(x)后的模x^n-1计算来表示，在二元域上模x^n-1等同于模x^n+1
7.3 循环码的生成
- 在一个（n,k）循环码的码组中，有且仅有一个次数为n-k=r的码字多项式，记为
- 同时，每个码字多项式都是g(x)的倍式，并且每个次数小于等于n-1的g(x)的倍式都是一个码字多项式，这时称g(x)为（n,k）循环码的生成多项式
- 在一个（n,k）循环码的码组中，次数最低的非零码字多项式是唯一的，其次数为r=n-k
- 令
为一个（n,k）循环码的码组中最低次数码字多项式，则其常数项必为g0=1 - 一个（n,k）循环码的生成多项式g(x)，一定是
的一个因式 - 若g(x)为一个n-k次多项式，且为
的因式，则g(x)可以生成一个（n,k）循环码 - 因此说明：
的次数为n-k的任何一个因式，均可以生成一个（n,k）循环码- 对于较大的n，
可能有多个n-k次的因式，可以产生不同的（n,k）循环码 例如，多项式
可以分解为：
。可以看出有两种（7,4 ） 循环码的生成多项式 ， 分别为
和
。 当 然
也是一个因式，可以产生一种（7,3）循环码系统循环码编码
- 循环码作为一种线性分组码，也分为系统码和非系统码
- 已知循环码的生成多项式可以按照一定的编码方法产生系统循环码
- 消息码字多项式：
- 循环码字多项式：
- 系统循环码的编码包括以下三个步骤：
- 用
乘上m(x) - 用
除以g(x)，得到余式r(x) - 利用
得到系统循环码的码字多项式
- 用
- 即将信息码除以生成码的余式添加在信息码后面
- 例题
- 非系统码编码
- 因为每个生成多项式倍式多项式都是一个循环码的码字多项式，
- 因此，已知循环码的生成多项式可以按以下关系求出非系统循环码
系统码和非系统码的码字重量分布和最小汉明距离是一样的
循环码生成矩阵
- 循环码可以用域上多项式描述，也可以用生成矩阵描述
- 循环码的生成多项式g(x)为循环码C中的一个码字多项式
也都是码字多项式（根据循环特性），并且是k个线性无关的码字多项式- 它们是k维子空间的一个基底，根据线性分组码生成矩阵的定义，它的行向量是由k个线性无关的码字构成的，因此，可以得到（n,k）循环码的生成矩阵为
- 生成矩阵的一般形式为：
- 根据码字序列与生成多项式的关系
- 利用这种方法产生的循环码为非系统循环码
- 上式给出的生成矩阵为非标准型生成矩阵（非典型生成矩阵）
- 非标准型生成矩阵可以通过矩阵的初等变换转换为标准型生成矩阵
- 例子
- 系统码生成矩阵
- 生成矩阵的每一行都是一个码字向量
- 因此，系统循环码的生成矩阵（标准型）的k个行向量分别为(10…0)，(010…0)，….，(00…01)消息序列对应的循环码字向量。
- 根据这个性质，根据（n,k）循环码的生成多项式，求出这些码字所对应的监督码元作为行向量的后r位，就可以得到系统循环码的生成矩阵
- 例题
- 循环汉明码
- 已知生成多项式g(x)，我们就可以得到生成矩阵，如果生成多项式为：
- 非标准的生成矩阵为：
- 可以得到非系统(7,4)循环码
- 上面的生成矩阵经过初等变换，可以变成标准型的生成矩阵，得到系统循环码，同时它也是一个(7,4)汉明码
7.4 循环码的编译码方法
循环码的优势是因为其循环特性使得编译码电路比较简单
循环码的校验子译码
- 发送码字多项式：
- 接收码字多项式：
- 错误图样多项式：
- 并且有：
- 校验子译码的过程为：
- 接收码字多项式r(x)计算校验子多项式s(x)
- 根据校验子多项式s(x)计算错误图样多项式e(x)
- 计算译码器输出的估计值
- 校验子多项式为：
- 校验子多项式s(x)等于接收码字多项式r(x)除以生成多项式g(x)的余式多项式
- 如果s(x)=0，表示接收码字无差错；如果s(x)≠0，表示接收码字有差错
- （n,k）循环码的校验子多项式的一般表达式为：
- 对应的校验子向量：
- 校验子多项式s(x)为一个r-1次多项式，校验子向量共有
个状态，当
≥n+1时， - 即可以保证至少纠一位码元错误
- 例题
- 系统循环码编码电路
- 已知其生成多项式为
，系统循环码的编码器：
- 编码器电路由n-k=3级移位寄存器及加法器、或门和门控电路构成，其基本工作过程包括：
- 移位寄存器的初始状态为全0，门1接通，门2断开，消息码元以[m3,m2,m1,m0]依次输入编码器。消息码元一方面通过或门输出，另一方面送入除法电路进行除法运算。m(x)在除法电路的右端输入相当于完成了循环移位n-k=3位。
- 四次移位后，消息码元已输出，形成了系统循环码的前四位码元[c6,c5,c4,c3]，同时，寄存器中存放的就是余式多项式的系数，从右到左分别是[c2,c1,c0]。
- 门1断开，门2接通，经三次移位，三个监督位从编码器输出。
门1接通，门2断开，进行第二个码字的编码。
非系统循环码编码电路
- 已知其生成多项式为
，(7,4)非系统循环码的编码电路：
- 循环码译码电路
- 循环码的编码电路由n-k级移位寄存器构成，比较简单。
- 但是循环码译码电路就相对比较复杂。
循环码的译码方法是编码理论和编码技术研究的重要内容。
线性分组码（不仅是循环码）的译码大体分为两类：
- 一是利用码的代数结构进行译码，称为代数译码方法。
- 另一类不仅利用代数结构，还利用概率理论，称为概率译码。
7.5 梅吉特译码器
- 校验子多项式的循环特性可以用来简化循环码译码电路
- 例子
- 接收码字多项式的循环移位等效于校验子多项式的循环移位
- 设s(x)是接收码字多项式r(x)的校验子多项式，则r(x)的循环移位
的校验子
是s(x)在g(x)除法电路中无输入时右移一位的结果，即有
- 这个定理的结果可以推广为，对于任意给定的j=1,2,…,n-1，必有
的校验子多项式为
- 同时有
- 如果r(x)→s(x)， 则
， 
，
工作原理
- 如果c(x)为循环码C中的一个码字多项式则
也一定是这个码组中的一个码字多项式 - 如果s(x)为r(x)=c(x)+e(x)的校验子多项式，则xs(x)也必然是xr(x)=xc(x)+xe(x)的校验子多项式
- 如果e(x)是一个译码器可以纠正的错误图样（相当于译码标准阵中的陪集首），则xe(x)也是一个可以纠正的错误图样，
也是可以纠正的错误图样 - 循环码译码器可以利用这种循环关系，对错误图样分类，将任一错误图样及其所有n-j次的循环移位归为一类。同一类的错误，可以使用同一个译码单元电路，由此可以简化译码器电路的复杂性。
- 例如，可以将“只错一位”的错误图样(100…0)，(010…0)，…，(00…01)归为一类，用一个错误图样(100…0)的校验子s(x)代表这一类错误图样的校验子。这样可以大大减少译码器要识别的错误图样类别的个数。
- 如果c(x)为循环码C中的一个码字多项式则
一个（n,k）循环码要纠正1位码元的错误，译码器要识别的错误图样总数为
- 一个（n,k）循环码要纠正2位码元的错误，译码器要识别的错误图样总数为
- 一个（n,k）循环码要纠正t位码元的错误，译码器要识别的错误图样总数为
- 而通过分类后，译码器需要识别的错误图样的类别数为
，纠2位错
- 这个循环码的
，可以纠正一个码字中的2位错
- 当错误图像多项式e(x)的次数小于7(r-1)时，说明错误码元都在监督位上面
- 这时校验多项式就等于错误图样多项式
- 设c(x)是一个纠t位错误的（n,k）系统循环码的码字多项式，而相应的接收码字多项式为r(x)=c(x)+e(x)，译码器得到的校验子多项式可以表示为
为k位信息位的错误图样
是n-k=r位监督位的错误图样
- 可以看到，如果错误图样多项式e(x)的次数小于等于n-k-1=r-1，即接收码字的错误码元都集中在n-k=r个监督位上，即
，则有
，
。同时考虑到生成多项式g(x)为n-k=r次多项式，因此，校验子多项式
。 - 这样就可以得到一个结论：对于具有这种错误图样的码字多项式c(x)，经过循环移位后，可以使校验子多项式s(x)=e(x)，译码过程就可以变为c(x)=r(x)+s(x)。
- 实际上，只要是错误码元集中在任意连续n-k位上即可，因为码字多项式的循环移位和校验子多项式的循环移位有一一对应的关系。
- 对于（n,k）循环码，若接收码字r(x)对应的校验子多项式为
，经过i次循环移位后，
对应的校验子多项式为
。一旦检测出
的重量
，就认为此时码字的错误码元已经全部集中在
的后n-k位以内。这时可以由
得到已经纠错的接收码字
，再进行n-i次循环移位，即可得到发送码字的估计值
- 这种译码方法称为捕错译码
- 分析可知对于（n,k）系统循环码，只有当所有小于等于t个错误全部集中再连续n-k=r位以内时捕错译码才有效
- 或者说，当码字的错误突发长度b≤(n-k)/2时，捕错译码才有效。
例如，（15,7）循环码，dmin=5，t=2，n-k=8，(n-k)/2=4，b≤4。
纠正t位错误的（n,k）二元循环码，捕错译码器已经把t个错误集中在
的最低n-k位以内的充要条件，是此时的校验子向量的汉明重量满足
7.7 大数逻辑译码
- 非系统循环码的生成矩阵和监督矩阵
- 已知一个(n,k)循环码的生成矩阵为一个r次多项式：
- 也可以写成为：
- 循环码的生成多项式一定为
的因式，因此一定有：
- 根据
- 可以得出如下关系式（只有n次幂和0次幂系数等于1）
- 得到基本关系：
- 例如(7,4)循环码生成多项式为
，它是
的一个因式，并且有：
- 生成矩阵
- 可知，监督多项式为
- 非系统码的生成矩阵和监督矩阵的一般形式：
- 例题
- 所谓对偶码就是其生成矩阵相互正交：
- 循环码生成矩阵的每一行都是一个码字向量，因此，系统循环码的生成矩阵（标准型）的k个行向量分别为(10…0)，(010…0)，….，(00…01)消息序列对应的循环码字向量。
- 根据这个性质，根据（n,k）循环码的生成多项式，求出这些码字所对应的监督码元作为行向量的后r位，就可以得到系统循环码的生成矩阵。
- 因此获得两种办法得到系统线性分组码的生成矩阵标准型和监督矩阵。
- 一种是已知生成多项式的方法，另一种是已知非标准型矩阵通过初等变换的方法。
- 通过一个例子来说明大数逻辑译码的基本思想
- 已知一个(7,3)线性分组码的生成多项式为：
- 其系统码的生成矩阵和监督矩阵：
- 这时的校验子向量为：
- 给出了一个校验方程组，利用这个方程组的线性组合，可以得到另一组校验方程为
- 这三个方程组的系数构成的三个行向量 [A1]=(1011000)，[A2]=(1100010)，[A3]=(1000101)是监督矩阵H的行向量的线性组合。因此，对于任意一个发送码字向量c，由
可知
- 进而得到一个新的（衍生的）监督方程：
- 得到了一个新的监督方程：
- 新的监督方程特点，每个方程中都有码元c6，而码元c5,c4,c3,c2,c1,c0在各方程中只出现一次。我们称其为正交于c6的正交监督方程。其系数矩阵H0称为正交监督矩阵。
- 如（7,3）循环码最小码距dmin=4，可纠正一位错同时检出两位错。
- 如果利用这个正交监督矩阵对接收码字进行校验，可以看到：
- 利用正交监督矩阵进行循环码译码，可以根据正交监督方程（A）取值为1的个数，对正交码元(r6)进行纠错，同时，根据循环码的循环特性，纠正其它各位码元的错误。这种译码方法称为大数逻辑译码。
对于上面的（7,3）循环码的例子，只要用一次大数逻辑判决就可以完成译码，称为一步大数逻辑译码。
大数逻辑译码器电路设计
- 接收码字序列进入由（7,3）循环码生成多项式g(x)=x4+x3+x2+1确定的除法电路，计算r(x)的校验子多项式s(x)。n=7次移位后得到校验子(s0,s1,s2,s3)在移位寄存器中，同时，r(x)已进入7级缓存器中。
- 停止译码器输入，并开始对rn-1=r6进行检查，也就是检查A1=s3，A2=s1，A3=s2+s0中1的个数。如果1的个数为3，大数门输出1。此时，缓存器移位一次，输出r6，对它进行纠错，如果1的个数小于3，大数门无输出，r6直接输出。
- 除法电路循环移位一次，对r5进行检查，此时校验子寄存器中的内容是对r5的计算结果。如果大数门输出1，则对r5进行纠错，否则，r5直接输出。
- 重复上述步骤，直至n=7次为止。
第n=7次移位完毕后，如果校验子除法电路的状态为全0，则说明r(x)中的错误是可以纠正的，否则说明是不可纠正的。若是不可纠正的，译码器送出一个信号至用户，表示r(x)有误。然后重新清洗译码器的初始状态，准备接收第二个码字。图中的虚线是把大数门输出的1反馈到除法电路的输入端，以消除该错误码元对除法电路的影响。
8. 域上多项式的根 (BCH码先验理论)
BCH码是一类纠正随机错误的线性分组码，它是用发明者Bose，Chaudhuri和Hocquenghem的名字命名的
- RS码（Reed-Solomon码）则是一种非二进制BCH码
- 严格地说，BCH码和RS码都是循环码的范畴，它们的共同特点是用域上多项式的根来定义的一类循环码
-
8.1 有限域（Fields）性质：
有限域是满足加法和乘法两种运算的元素集合F。如果
8.2 有限域元素的阶（order）：
- 由于有限域上的非0元素构成一个循环群（乘法自闭性）
- 所以，如果a是有限域GF(q)上的一个非0元素，那么，就有
- 例如：{0, 1, 2, 3, 4, 5, 6}就是一个GF(7)，q-1=6
- 元素的阶：使下式成立的最小的正整数s，记为ord(a)。
- 例如：
- 并且有：
8.3 有限域的本原元（primitive element）
- a是有限域GF(q)上的一个非0元素，如果a的阶等于q-1，a称为本原元
- 例如：{0, 1, 2, 3, 4, 5, 6}在模7运算下是一个GF(7)，q-1=6
- a=3是一个本原元，它的乘法运算可生成所有非零元素，而其的元素不是本原元。
- 还可以验证，其他元素的阶一定是q-1的因数
- 并不是所有的模运算都能形成一个域，{0,1,2,3}在模4运算下就不是一个域
8.4 有限域上多项式的根（零点） ：
- 对于任意一个正整数m>1，可以将一个素数域
扩展成一个扩展域
，
就是二元扩展域 - 对于一个正整数m>1，
，一定存在至少一个GF(2)上的m次不可约多项式p(x)，并且是
的因式 - 二元域上n次多项式
有n个根，这些根就是扩展域
的非零元素，并且这些非0元素构成一个乘法循环群。所谓循环群就是每个元素可以由一个元素的整数次幂循环构成，这个元素就是扩展域的本原元 对于一个正整数m>1，
，如果
的因式中的m次不可约多项式p(x)是以
上的本原元为根，这个p(x)称为本原多项式例如：二元域上的7次多项式多项式，有7个根，x=1是一个根(m=3, n=7)
- 查表确定其中的
是一个本原多项式
- x=1是(x+1)的根，
是
的三个根，
是
的三个根
8.5 本原多项式（primitive polynomials）：
- 本原多项式：对于m>1，
，本原多项式是一个m次多项式，是
的因式，本原多项式的根是
上的本原元 - 对于一个正整数m，一个m次不可约多项式p(x)，如果它是
的
的因式，而不是任何
的
的因式，那么，这个m次多项式就一定是
的本原多项式 - 本原多项式可能是不唯一的
- 如果
是一个素数，那么所有m次不可约多项式都是本原多项式 - 例如：m=5，n=2^5-1=31为素数，m=4，n=15就不是素数
- m次本原多项式和最小多项式
8.6 扩展域
的构成：
- 第一步：选定一个m次本原多项式；
- 第二步：设α为本原多项式的根，计算出
个的整数幂元素（模
），得到一个循环群，再加上0元素就构成一个扩展域
；
- 第三步：利用p(α)=0的基本关系，表示扩展域中的所有元素
- 例如：m=3，n=7，本原多项式为
，扩展域
元素的表示：
- 本原多项式可能不唯一，不同的本原多项式构成不同的
扩展域
- 同样，也可以用
构成一个
扩展域
- 例如：m=4，n=15，本原多项式为
，扩展域
元素的表示：
8.7 最小多项式（minimal polynomials）：
- 定理表明：
- f(x)为GF(2)上的多项式，如果β是f(x)的根，那么，β^2是也一定是f(x)的根，β^4是也一定是f(x)的根…，这一组根称为共轭根
- 如果φ(x)是GF(2)上满足φ(β)=0的最低次数多项式，则称φ(x)为GF(2)上对应于β的最小多项式
- 最小多项式φ(x)一定是不可约多项式
- 如何确定最小多项式？(以m=3为例)
- 根据相关定理：如果φ(x)是以β为根的最小多项式，则对于最小正整数（e≤m），一定有：
- 例如，我们取β=ɑ，根据这个定理，我们就可以确定所有最小多项式
- 确定最小多项式的度（次数）；（ 可见β的度等于3）
- 计算：
- 从下表快速计算
- 再例如，取
，我们可以确定- 确定最小多项式的度（次数）；（ 可见β的度也等于3）
- 计算：
8.8 GF(2)上多项式x^n+1的分解算法
- 输入：选择一个奇数n
- Step1：找出模n的分元陪集
- Step2：找出陪集C1中元素的个数m
- Step3：构造有限扩展域
，选择一个本原元α，并且令
- Step4：计算或查表
- 输出：
的因式
- 例题
- 分解多项式
- Step1：构造模15的分元陪集（Cosets）
- Sept2：找出陪集C1中元素的个数（共轭根的个数）m=4，说明本原多项式是一个4次多项式
- Step3：根据m=4，n=15，计算
，本原多项式的根为β=α - Step4：查最小多项式表
- 例题
- 分解多项式
- 理论上讲，任何的二元域上
多项式都可以利用这个算法进行分解，可以查表 - 但是，不同的n值，多项式的周期不一样，但是周期或者等于
，或者周期是
的因数 当m为正数，
时周期是最长的，也就是为什么我们总是举例为n=7、15、31这些数的原因
9. BCH码
是一种循环码，它的纠错能力（最小汉明距离）与其生成多项式的根存在某种关系
9.1 本原和非本原BCH码
对于任意给定的正整数m≥3，
，一定存在有下列参数可纠正t位码元错误的二元本原BCH码
- 且其生成多项式g(x)是GF(2)上以
为根的最低次数多项式，α为
上的本原元 - 如果
是以
为根的最小多项式，并且为
的因式，则有
公式中LCM表示取最小公倍式
循环码的最小码距dmin一定大于其生成多项式g(x)的最大相邻根的个数。如果循环码生成多项式g(x)的最大相邻根的个数为N，则有
- 根据有限域上多项式的基本关系可知，对于二元BCH码，生成多项式g(x)和
均为GF(2)上的多项式 - 在二元有限域上，有
，所以有
，即如果
为
的根，则
也为
的根
- 如果q进制循环码的生成多项式为g(x)，并且g(x)包含有2t个连续根，
，则由g(x)生成的(n, k)循环码称为q进制BCH码。这时，BCH码的生成多项式记为
是以
为根的最小多项式。如果生成多项式g(x)的根包含有限扩展域
中的本原元，则码长一定为
，我们将这类码称为本原BCH码如果生成多项式g(x)的根不包含有限扩展域
中的本原元，则码长一定为小于
，并且为
的因子，这类码称为非本原BCH码总结
- 二元域GF(2)上生成多项式的根在二元扩展域
上 - 可以纠正t位错误的BCH码的生成多项式有2t个连续根
中有一个本原元，由它可以生成
上其他元素- 本原BCH码的生成多项式以本原元为根，码长较长
- 非本原BCH码的生成多项式为非本原元为根，码长较短
- 生成多项式为最小多项式的最小公倍式
- 例题
- 对于任意给定的正整数m≥3，
，一定存在有下列参数可纠正t位码元错误的二元BCH码
- 且其生成多项式g(x)是GF(2)上以
为根的最低次数多项式。其中
为
上的元素。如果
是以
为根的最小多项式，并为
的因式 
，则有
- 如果
，即i=1，且α为
中的本原元，则码长
，产生的BCH码为本原BCH码 - 如果
，即i≠1，
不是
中的本原元，并为一个阶数为
的元素，则n一定为
的因数，产生的BCH码为一个码长为n的非本原BCH码 - 例题
9.2 RS码（Reed-Solomon Code）
- RS码（Reed-Solomon Code）是BCH码的一个重要的子类
- 它的最小汉明距离可以达到dmin=r+1（辛克莱顿界）
- 如果码元取值和生成多项式g(x)的根都在扩展域
上，则这类BCH码称为RS码 - 因为RS码的码元和生成多项式的根在同一个扩展域中，所以，
上多项式
一定可以分解为一次多项式，即
- 其中最小多项式为
- 令α为
的本原元，如果求设计距离为d的RS码，由RS码的定义可知，RS码生成多项式为
是
在
上的最小多项式。如果取j=1，则有
- g(x)为r=d-1次多项式，则
- 可以看到：RS码的最小汉明码距为d=r+1。达到了（n,k）线性分组码的辛格尔顿界（Singleton bound）
- 例题
- 在实际使用中，多进制编码不是很方便，通常是用二进制的m重向量来表示扩展域
中的元素 - 这时，
上的
多进制RS码，实际上，就变成了
二进制RS码 例如，上面的（7,3）八进制RS码变成了（21,9）二进制RS码
9.3 BCH码的监督矩阵
BCH码也是一种(n,k)循环码，只不过他的生成多项式g(x)是我们通过了解到根的分布后确定的。知道了生成多项式，就可以进行编码和译码
- 一个BCH码的码字多项式也表示为：
- 已知BCH码有连续的2t个相邻根，如果一个纠正t位错的本原BCH码的生成多项式的2t个相邻根为：
- 因为码字多项式都是生成多项式的倍式，所以些根一定也是码字多项式的根
- 例题
9.4 BCH码的校验子译码
- 与循环码的译码类似，译码过程分为三个步骤：
- 根据码字多项式r(x)计算校验子多项式s(x);
- 根据校验子多项式s(x)确定错误图样多项式e(x)；
- 利用c(x)=r(x)-e(x)得到发送码子的估计值。
BCH码的译码相对循环码来说，其错误图样的确定更加复杂一些，但是其基本原理是一样的
10. 卷积码
10.1 卷积码编码
在卷积码的编码过程中，每个码字的监督元不仅与当前码字的信息元有关，而且与前m个码字的信息元有关
- 即卷积码的编码器是一个有记忆的时序电路
- 卷积码由于更充分地利用码字之间的相关性，可以减少码字长度，简化编译码电路并得到较好的差错控制性能
- 因此，卷积码在移动通信、卫星通信等领域得到广泛的应用
- 卷积码（Convolutional code）记为：(n, k, m)卷积码；m称为卷积码的约束长度
- 卷积码的码率：R=k/n，卷积码的码率一般比较低，比如(2,1,3)、(2,1,6)和(2,1,7)卷积码等等，但它的纠错能力也是比较强的
- 卷积码也分系统码和非系统码
- 卷积码的数学描述：可以用多项式描述，也可以用矩阵描述，用多项式描述更为方便
- 卷积码的图描述：状态图、树图、栅格图
卷积码的译码具有很好的统计特性，使其应用广泛
以（3，2，2）系统卷积码为例
- n=3, k=2, m=2
- 卷积码的约束关系：约束长度m=2（表示与前两个码字有关联）
- 卷积码一个码字中的码元个数为n，码字中信息元个数为k
- 如果由m级移位寄存器构成的编码器，则称m为卷积码的编码约束长度，称(m+1)n为卷积码的码元约束长度，这种卷积码记为（n, k, m）卷积码，R=k/n为码率(Code rate)
- 当某一时刻i，编码器输入并行一个信息码字为
，编码器并行输出由三个码元组成的卷积码的码字，
。
称为一个码字。
为信息元，
为监督元。可以看出卷积码的输入输出关系为：
- 卷积码同样有系统卷积码和非系统卷积码之分
- 系统卷积码的码字中明显的包含着k位信息码元，而非系统卷积码的信息码元是隐含在码字中的
- 例如（2，1，2）非系统卷积码编码器
- 从这个非系统卷积码的例子可以看到，非系统卷积码编码器输出的码字序列中，没有明确地区分信息码元和监督码元，即约束关系使信息码元和监督码元完全融合在一起，形成了一个整体的卷积码序列
10.2 卷积码监督矩阵
- 考察（3，1，2）系统卷积码
- 从编码器原理图可以看到，n=3，k=1，m=2。编码器输入信息序列为
，输出码字为
- 可以看出其监督关系为
- 考察编码器一个约束长度的监督关系：
- 监督方程写成矩阵形式为：
- 约束长度的卷积码C(N=n*(m+1)=9)为截短卷积码（正常卷积码是无限长度的）
- 卷积码一个约束长度的监督方程的系数矩阵称为截短卷积码的基本监督矩阵，用小h表示
- 在卷积码编码器初始状态为零时，初始输入m+1个信息码字时编码器输出的卷积码序列称为初始截短卷积码
- 以（3，1，2）系统卷积码为例
- 以（3，2，2）系统卷积码为例
- 因此归纳
- 一个(n,k,m)系统卷积码的初始截短卷积码监督矩阵为：
- 实际上卷积码的监督矩阵应该是一个有头无尾的半无限矩阵，它对应的基本监督关系为：
- 一个(n,k,m)系统卷积码的监督矩阵的一般形式为：
- 对于系统卷积码的编码器，我们可以方便地写出监督矩阵，但是对于非系统卷积码不行
以(2,1,2)非系统卷积码编码器为例：
-
10.3 卷积码的生成矩阵
已知监督矩阵求生成矩阵（对于系统卷积码）
- 基本生成矩阵：
- 初始截断码生成矩阵：
- 卷积码生成矩阵
- 已知生成多项式求生成矩阵
- 有一些卷积码编码器可以用编码器输出支路的冲击相应函数来描述。
- 以 (3,1,2)系统卷积码举例
- 编码器的三个输出支路的逻辑关系可以由三个生成多项式来确定（支路多项式）
- 一般(n,k,m)卷积码（包括系统卷积码和非系统卷积码）可以写出明确的支路多项式：
- (n,k,m)卷积码的编码器有n个支路多项式
- 每个之路多项式都是一个小于m次的多项式
- 每个多项式有m+1个系数
- 第i支路多项式向量表示为：
- 通过支路多项式的向量表示，我们就可以得到卷积码的生成矩阵。其基本生成矩阵：
- 有了基本生成矩阵就可以得到生成矩阵和初始码的生成矩阵
- 需要注意
- 对于系统卷积码，我们可以得到标准型的监督矩阵与生成矩阵
- 例如(3,1,2)系统卷积码
- 对于非系统卷积码，我们只能通过支路多项式得到生成矩阵
- 例如(2,1,2)非系统卷积码
- 例如(3,1,2)非系统卷积码
10.4 卷积码编码过程
- 矩阵计算方法
- 时域卷积方法
多项式计算方法
矩阵计算方法
- 例如(2,1,3)非系统卷积码
- 基本生成矩阵
- 当编码器输入码字序列为m=[10111]时，编码器输出的卷积码序列
- 在上面计算矩阵乘法时，实际上假设信息序列的后续为m个零状态（三个0）
即认为编码器输入的信息序列为m=[10111000]
时域卷积方法
- 还可以用时域卷积方法计算两个支路的输出序列，然后再交织输出
- 输入序列m=[10111]
- 支路的卷积输出
- 线性系统时间序列分析
- 交织输出
- 多项式计算方法
- 线性系统的时域卷积就等于多项式的乘积
- 输入序列m=[10111]
- 两个支路的输出：
- 交织输出：
- 对应的码字向量：
- 其中交织输出的多项式表示
- 两个支路的输出：
- n个之路的输出：
- 利用复合多项式计算编码器输出序列
- 对于(n,1,m)卷积码编码器，复合生成多项式为：
- 编码器输出序列：
- 总结
- 对于一个卷积码，无论是系统码还是非系统码，是要能写出支路生成多项式（支路传递函数）
- 我们就可以写出生成矩阵[G]
- 支路多项式是一个最大为m次多项式（m是编码器寄存器的个数）
- 支路多项式的个数等于输出支路的个数（也就是码字的Block长度n）
- 具体方法：支路多形式→基本生成矩阵→生成矩阵
- 基本生成矩阵是一个块矩阵(m+1个块，每个块长度为n)
- 特殊情况
- 举例（3，2，2）卷积编码器
- 以(3,2,2)系统卷积码为例，这种两个输入信息码元的卷积码编码器，它的支路多项式就很难直接写出来
- 可以用类似于信号系统分析方法，考虑逐个输入的传递函数（生成多项式）
- 按信息位区分的支路多项式：每一路输入都对应一组支路多项式
- 得到的多项式生成矩阵：
- 多项式矩阵G(x)的行数=编码器输入的路数
- 例题
- 用系统传递函数描述方法
- 卷积码的编码过程就是将消息数据流输入输入一个线性滤波器，卷积码编码器就是一个线性滤波的运算
- 不同的滤波器特性可以得到不同的卷积码。大多数编码器的操作都是在二元域F2上进行的，也就是二元卷积码。可以是单输入的也可以是多输入的。可以是系统的也可以是非系统的
- 前面介绍的卷积码编码器（滤波器）都是前馈（feed-forward）方式的，也称为非递归的（recursive）
- 还有一类卷积码的编码器是带有反馈（feedback）路径的，称为递归编码器（recursive encoder）
- 对于递归式的卷积码编码器，我们就需要用传递函数描述
- (2,1,2)系统递归卷积码编码器，它的校验位支路传递函数就是它的支路多项式
- 多项式生成矩阵
- Turbo码编码器
- 在3G移动通信的UMTS标准中，定义了一种m=3的Turbo码，其中就使用了递归卷积码编码器
- 其生成矩阵（多项式）为：
10.5 卷积码维特比译码
- 卷积码状态图 （state transition diagram）
- 卷积码编码器的状态图=编码器移位寄存器的（最大）级数
- （2,1,3）非系统卷积码编码器，码率R=1/2，编码器有m=3位移位寄存器组成
- 其状态图共有2^m=2^3=8个不同状态
- 其状态可以表示为Si=[D2,D1,D0]，分别为
- S0=[000]，S1=[001]，S2=[010]，S3=[011]，S4=[100]，S5=[101]，S6=[110]，S7=[111]
- 如果编码器初始状态为S0时，输入信息序列为m=[10111]，则输出为c=[11 01 00 01 01 01 00 11]
- 与例题计算结果相同。注意输入信息序列后面补三个0，这时编码器状态变化路经为
- 卷积码的树图（tree diagram）
- 如果（n,k,m）卷积码的输入信息序列是一个有头无尾的半无限序列，则输出也是一个半无限序列，而且对于任意可能的输入序列，编码过程及输出序列可以用一个树形图来描述
- 把这种图称为卷积码的树图
- 如(2,1,2)卷积码
- 在码树图中，节点处的符号Si表示编码器的状态，分支路径上的数字表示编码器输出符号，
- 上分支表示输入信息0，下分支表示输入信息1。设编码器初始状态为S0=00
- 卷积码的网格图（trellis diagram）
- 卷积码的网格图又称为篱笆图，它综合了状态图和码树图的特点，结构简单并且时序关系清楚
- 从码树图的可以看出，从某一阶节点开始码树图具有周期的重复性
- 卷积码的网格图就是将这种重复性简化后得到的
- （2,1,2）卷积码编码器有四个状态，网格图就有四行，每行节点分别表示编码器处于S0，S1，S2，S3四个状态
- 网格图从左到右按时间展开，在每一级节点到下一级节点有两个（2^k）输出分支，偏上的分支表示编码器输入为0，偏下的分支表示编码器输入为1，分支上标出的n为数字表示编码器的输出码字
- 信息序列长度L=5的(2,1,2)卷积码的网格图
- 网格图中第0级节点表示编码器初始状态为S0，经过m=2次输入后编码器可能处于四种不同状态
- 从第m级节点到第L=5级节点，编码器处于稳定的状态转移中，各节点的网络结构是一样的
- 在第L级节点后网格图画出了编码器输入m个0后又回到了初始状态S0
- 对于L=5的网格图，一共有有L+m+1级节点，为0-7级。除了初始状态和后面m=2个状态外，长度为L+m的2^L个码字，每个码字都对应于格子图上的唯一一条路径
初始状态为S0，输入信息序列为m=[11101]时，输出为C=[111，010，001，110，100，101，011]，编码器状态变化路径为S0→S1→S3→S3→S2→S1→S2→S0
10.6 译码度量
卷积码的译码准则
- 根据卷积码网格图，假设卷积码编码器输入为长度为L的信息码序列，对于（n,1,m）卷积码则可以表示为：
- 编码器输入序列：
- 编码器输出序列：
- 译码器输入序列：
- 译码器输出序列：
- 本质上讲，维特比算法(Viterbi Algorithm)就是根据ML估计准则，寻找最佳的发送编码序列，也就是找到一个最可能的编码序列c，使得信道转移概率达到最大。
- 所以维特比译码算法也叫做最大似然译码算法
- 1967年由维特比提出，在栅格图上找到与接收的码字序列距离最近的发送码字的估计序列。维特比算法的思想在后来的语音识别技术得到应用。
- 维特比算法是种动态编程（dynamic programming）思想，所谓动态编程就是为了减少运行时间而优化子程序结构，子程序的最优可以带来整个程序的最优。也就是通过局部最优寻找全局最优，进而提高算法速度问题。
- 对于离散无记忆二元对称信道（BSC），最大似然准则就等同于最小汉明距离准则。首先选择对数似然函数为logP(r/c)，对于离散无记忆信道，一个(n,k,m)卷积码，Frame长度为L，则码字序列的似然函数为：
- 其中，L+m为截断卷积码的Block个数，N=n(L+m)为截断卷积码的码元长度。
- 则对数似然函数为：
在ML估计的实际应用中，较多地使用对数似然函数，主要是为了计算的便利。
译码量度（Metric）
- 这个对数似然函数logP(r/c)是一个与卷积码网格图上的路径有关的参数
- 在维特比译码算法中称其为译码路径量度：
- M(r/c)为路径量度(Path metric)，M(ri/ci)为分支量度(也叫Block metric)，M(ri/ci)为比特量度(Bit metric)
- 定义：在网格图上一条译码路径的前 j 个分支的量度为部分路径量度，表示为：
- 对于BSC信道，最小汉明距离就等价于最大似然准则
10.7 维特比算法
- 维特比算法是对于一个有限长度的接收码字序列r与网格图上的所有路径进行比较，这种比较就是计算路径量度
- 这种计算是一种迭代计算，在每一级节点处，译码器都要计算一下已经走过所有可能路径的路径量度
- 保存一部分较大量度的路径作为幸存路径，而放弃一部分几乎不可能的路径以减少计算量，避免Brute force
- 由初始状态经过m个时间单位，从时间j=m开始，计算进入每一个状态的每一条路径的部分路径量度。对于每一个状态，比较进入它的各条路径的部分量度，其中量度最大（汉明距离最小）的路径及其量度被保存下来，称为进入这个状态的幸存路径。
- 进入下一个单位时间j+1，计算进入某一个状态的分支量度，并与前一个时间的有关幸存路径的量度相加，比较此时的部分量度，选出最大者，作为进入此状态的幸存路径，存储幸存路径及其量度，删除其它路径和量度。如果一个状态的两个路径量度相等，可以都保留（也可以删除一个）
- 如果j<L+m，则重复（2）步，否则就停止计算，输出最大量度的幸存路径对应的码字序列
- 举例
- （3,1,2）非系统卷积码，n=3，k=2，m=2，L=5，N=21；
- 也就是所编码器输入为：m=[11001]
- 发送序列为：c=[111, 010, 110, 011, 111, 101, 011]
- 接收序列为：r=[110, 110, 110, 111, 010, 101, 101]
- 利用维特比算法求出发送码字序列的估计值
- 详细步骤
- 算法表述
10.8 卷积码的序列译码
- 维特比算法是一种最大似然译码算法，译码器选择的输出总是使接收序列似然函数最大的码字，因此说，维特比译码是最大似然译码准则下的最佳译码方法。然而，维特比译码法存在两方面缺点：
- 维特比算法的运算复杂度与编码约束长度密切相关。对于一个（n,1,m）卷积码，总的状态数为
，随着m的增加，译码运算量急剧增加。因此，编码约束长度不会太大，译码性能也很难达到理论上的极限值。维特比算法适合于较小的编码约束长度，m=8是维特比算法的极限（计算量比较大）。 - 维特比算法的译码计算量不能动态地适应信道条件的变化。我们注意到维特比算法所需的固定计算量有时是不必要的，即便噪声比较小时，每一个Frame的码字序列，要做的计算量仍然差不多是
次。
- 维特比算法的运算复杂度与编码约束长度密切相关。对于一个（n,1,m）卷积码，总的状态数为
相对于维特比算法而言，序列译码(Sequential Decoding)算法通常被认为是一种卷积码的次优译码方法。
基本思想
- 序列译码算法利用码树图来进行译码。卷积码的编码过程相当于在码树上“行走”。每一个发送序列对应于码树上的一条路径，该路径始于码树图的根节点（出发点），终止于树梢节点（叶节点），即深度为L+m的节点。
- 编码后的码字序列经信道传输，相当于发送序列路径受到了噪声污染，从而使译码器的接收序列为“发送序列+错误图样”。译码器的任务就是由接收序列推测出编码序列在码树图上行走过的路径。
序列译码算法也是一种最大似然算法。与维特比算法类似，我们定义另一种量度来表征接收码字序列与码树图上的路径之间的差异，差异越小，该路径就越可能是真实的发送序列。序列译码的过程就是对一个接收码字序列在码树图上寻找最大似然路径的过程。
算法步骤
- 对一个接收码字序列，确定码树图的一个子集，对子集的要求是：
- ①子集包含有编码序列的各种可能路径，避免真实路径漏掉；
- ②子集包含的路径尽可能少，以减小译码计算量。
- 从子集中拿出一条路径，依照定义好的量度比较，判断是否为发送路径，若是则继续保持；若不是则放弃
重复上述过程，直至最终确定发送码字序列路径的估计值
序列译码利用码树图进行译码，译码工作量只与码字序列长度L有关，而与编码约束长度m无关，因而可以增大编码约束长度以提高译码性能。而且序列译码有适应信道干扰的能力，其译码复杂度与信道噪声强度匹配，是个随机变量。当信道干扰较小时，它的译码速度很快，仅当信道干扰较大时，译码速度才变慢。
序列译码的堆栈算法
- 在讨论序列译码时，通常用（n,k,m）卷积码编码器的截断码字序列的长度为N=L+m，其码树图有
个码字路径，例如，（3,1,2）卷积码L=5的截断卷积码的码树图有
个码字路径 - （3,1,2）卷积码的树图共有4个状态节点S0=00，S1=01，S2=10，S3=11
在这个树图中，编码器初始状态为S0=00。我们确定，当输入信息码元为0时，由树根出发走下支路路径，寄存器右移一位，状态仍然为S0，输出码字为c0=000。当输入信息码元为1时，则由树根出发走上分支路径，寄存器右移一位，状态转为S1=10，输出码字为c0=111。以此类推，输入无限长的信息序列，就会得到一个无限延伸的码树图。经过L个Block之后，码字序列截断
红线表示输入为[1110100]时编码路径
- 这里使用一种所谓码元度量（Fano度量）为：
- 其中P(ri/ci)是信道转移概率（似然），P(ri)是信道输出符号概率，R是码率
- 码树图上一条路径c的前t个分支的部分路径度量为：
- 通常可以使用一种简化的码元度量（加权），对于R=1/3，p=0.1：
- 码元相同量度为+1，码元不同量度为-5
- 举例
- 详细分析将发现，在信道条件较好时，序列译码会比维特比译码需要更少的译码步骤。可以验证，此例中序列译码需要10次基本计算，而维特比译码算法则需要15次基本计算。
- 实际上，这个例题中发送序列与接收序列只有2个码元的错误，错误率为2/21=0.095，粗略等于信道转移概率p=0.1。进一步分析还可以发现，如果信道条件变差，即码元错误概率增加，序列译码算法的步骤会随之增加。
因此，序列译码还有一些改进的算法，如Fano序列译码算法等。
10.9 软判决译码介绍
软判决译码(Soft-decision decoding)的基本思路
- 前述都是硬判决译码，认为接收机解调器输出的就是0/1码元（或者-1/+1码元），对应着编码的码字序列
- 忽略了信道传输的一部分信息。因为，目前为止，绝大多数无线通信系统，信道传输的无线媒体还是模拟信号。也就是说，在信道上受到噪声干扰的是模拟的电磁波（正弦波的载波调制信号）
信道传输的原始信号携带的所有信息，是否对译码器有用呢。如果将信道传输的原始信号不量化，或者多电平量化，就可能把这些信息提取出来。这是软判决译码的基本思路
欧几里得距离
- 假设一个BPSK调制信号经过WAGN信道，在调制解调器中，我们将0/1码字序列映射为+1和‒1的双极性脉冲信号。变换的关系为：
- 发送码字序列变换为：
- 接收码字序列变换为：
- 在WAGN信道上，假设信道是无记忆的，这时的最大似然准则为
- 在WAGN信道上有：
- 对于分析译码量度，可以忽略常数项，译码准则为
- 如果选用对数似然函数，进一步忽略常数项，则为
- 其中定义欧几里得平方距离：
- 汉明距离与欧几里得距离比较
对于硬判决译码，我们很清楚其比特量度M(rj/cj)为： | M(rj/cj) | r=0 | r=1 | | —- | —- | —- | | c=0 | 0 | 1 | | c=1 | 1 | 0 |
对于软判决译码，接收机的比特判决电路可以给我们提供“边缘信息”
- 这时，我们可以根据接收信号做出更准确的判决，例如强1（清晰的1），弱1（模糊的1），强0，弱0等等
- 分析表明，在WAGN信道上，卷积码的软判决维特比译码至少可以提供2-3dB的译码增益
- 实际上这是我们用译码器的计算复杂度换取了编码增益
假设一个WAGN信道上，卷积码软判决译码的似然函数为： | p(rj/cj) | r=强0 | r=弱0 | r=弱1 | r=强1 | | —- | —- | —- | —- | —- | | c=0 | 0.50 | 0.25 | 0.15 | 0.05 | | c=1 | 0.05 | 0.15 | 0.25 | 0.50 |
对数似然函数为： | log2p(rj/cj) | r=强0 | r=弱0 | r=弱1 | r=强1 | | —- | —- | —- | —- | —- | | c=0 | -0.73 | -2 | -2.73 | 0.05 | | c=1 | -0.43 | -2.73 | -2 | -0.73 |
然后，再做一个加权变换（距离放大），其中的变换公式为
这样得到软判决的比特量度为 | Ms(rj/cj) | r=强0 | r=弱0 | r=弱1 | r=强1 | | —- | —- | —- | —- | —- | | c=0 | 5 | 6 | 2 | 0 | | c=1 | 0 | 2 | 6 | 5 |
可以验证，在同样的WAGN的无记忆信道情况下，软判决译码可以有更强的纠错能力
若有收获，就点个赞吧
0 人点赞
