State Key Laboratory of Integrated Services Networks
第六章 循环码的译码
循环码的译码
一般译码原理 捕错译码 大数逻辑译码
State Key Laboratory of Integrated Services Networks
一、一般译码原理
基本思想与线性分组码类似
~x 0 T modgx
非门
输入R(x) 门
与门 七级缓存
循环汉明码译码电路 (需要14移位)
Example：设计一个由g(x)=x4+x3+1 生成的[15,11]循环汉明码译码电路。
基本要求：需要一个除法电路和一个逻辑电路
要设计逻辑电路，须知道该码可纠正的错误图样及伴随式
汉明码可纠一个错误，只需知道一个错误图样的伴随式
x5 x 2 x 1 mod x3 x 1
循环汉明码译码电路
[7,4,3]循环汉明码的生成多项式为x3+x+1
H ~x 6 T
~x 5 T ~x 4 T
1 1
0 1
1
1
~x 3 T ~x 2 T ~x1 T
1 0 1 0 0 1 1 0 1 0 0 1 0 0 1
伴随式又可由校验矩阵H得到
扩展汉明码的译码 缩短循环码的译码
扩展汉明码的译码
扩展汉明码的码长是8的整数倍。 扩展汉明码d=4，能纠正一个错误同时发现两个错 误。 译码电路主要部分与循环汉明码译码器相同，需 要加上检错电路。
State Key Laboratory of Integrated Services Networks
wSi x t
其中w(Si(x))是伴随式Si(x)的重量
E x en1 x n1 enk x nk enk 1 x nk 1 e0
若前面k位没有错误，则可用捕错译码实现 若前面k位也有错误，此时伴随式S(x)为：
Sx EP x EI xmodgx EP x SI x
二、捕错译码
基本原理
Sx Rx Ex EI x EP x modgx EI x en1x n1 en2 x n2 enk x nk EP x enk1x nk1 enk2 x nk2 e0
基本原理
若错误集中在校验元的n-k位上，即EI(x)=0, E(x)=EP(x)
N1
t j1
(q
1)
j
n j
11
使得循环码译码器的错误图样识别电路大为简 化， 由原来识别N2个图样减少到N1个
N2
t j1
n j
(q
1)
j
Example:循环码生成多项式g(x)=x3+x+1， 计算E(x)=x6和E(x)=x5的伴随式
x6 x2 1 mod x3 x 1
系统循环码的一致校验矩阵H
H
~x n1
T
,
~x n2
T
,
~x 1
T
,
~x 0
T
(mod g(x))
S
RH T
rn1, rn2 ,
r0
~x ~x
n1 n2
mod
g
x
~x 0
cn1 , cn2 ,
~x ~x
n1 n2
c0
mod gx
en1 , en2 ,
~x ~x
n1 n2
若EI(x)和SI(x)已知，可由此得到EP(x)， 进而确定E(x)= EI(x) +EP(x)，即是修正捕错译码
修正的捕错译码
当循环码的信息比特数k等于n/t或比n/t稍大时，可 采用某种方法，将大部分错误集中在n-k位上，而 把个别错误集中在固定的某几位上，即可实现修正 的捕错译码
固定几位错误
覆盖多项式的数目
对于纠正t个错误的GF(q)上的[n, k]循环码， 当且仅当R<2/t时，覆盖多项式集合必存在。 对于t=2，覆盖多项式{Qj(x)}中，最少的多 项式数目为
j n /(2(n k))
State Key Laboratory of Integrated Services Networks
S1x xSx modgx
循环码计算伴随式电路的特点
推论：xjR(x)的伴随式Sj(x)≡xjS(x) (mod g(x))， j=0， 1， …， n-1。
而任意多项式a(x)乘R(x)所对应的伴随式 Sa(x)≡a(x)S(x) (mod g(x))
在q进制时， 若码要纠正≤t个错误，
则错误图样代表共有
Sx Ex EP x modgx
此时，伴随式就是错误图样，C’(x)=R(x)-S(x)
可用捕错译码循环码必须满足
1、错误必须集中在任意连续的n-k位上 可利用循环码的特点将错误移到后n-k位上 2、k < n/t 或 t < n/k 或 R < 1/t
பைடு நூலகம்
错误集中在n-k个校验元上的条件
纠正t个错误的GF(q)上的[n,k]循环码，捕错译码 过程中，已把t个错误集中在Ri(x)的最低次n-k 位 以内的充要条件是：
e0
mod
gx
~x 0
~x 0
0
S 如何用多项式表示？
循环码伴随式 可用除法电路实现
Sx Cx Ex Rx Ex modgx
由此可知：循环码的检错电路易于实现。
循环码计算伴随式电路的特点
定理：若S(x)是R(x)的伴随式，R(x)的循环移位 xR(x)的伴随式为S1(x)，则S1(x)是伴随式计算电 路中无输入时右移一位的结果。
大部分错误
修正捕错译码原理
E I x en1 x n1 enk x nk
x nk ek 1 x k 1 enk
x nk Qx SI j x xnk Qxmodgx
修正捕错译码原理
因此，如果能找到一个k-1次多项式Q(x) ，使 错误图样E(x)或E(x)的循环移位在前k位码段 内与Q(x)一致，即可找到最终的错误图样
1、根据接收序列R计算伴随式S=RHT(n-k维向量) 2、根据伴随式S寻找错误图样E 3、根据错误图样E估计码向量C’，
进而计算信息序列
伴随式计算的多项式表示
R R x rn1x n1 rn2 x n2 r0
C C x cn1x n1 cn2 x n2 c0 E E x en1 x n1 en2 x n2 e0 S S x snk 1 x nk 1 snk 2 x nk 2 s0