第8讲 信道编码：循环码编码电路、CRC、BCH、卷积码

信道编码
循环码的非系统码： 循环码的非系统码： c(x) = u(x)g(x) 循环码的系统码： 循环码的系统码： c(x) = xn-k u(x) + [xn-k u(x)]mod g(x) [x
x n −1 + [ x n −1 ]mod g ( x ) x n −1 + [ x n −1 ]mod g ( x ) n − 2 n−2 n−2 x + [ x ]mod g ( x ) n−2 x + [ x ]mod g ( x ) = G = [ I k MQ] = M M n − k −1 n − k −1 n−k x + [x ]mod g ( x ) n−k x + [ x ]mod g ( x ) g ( x)
g n − k −1 L
则有： 则有：
G·HT = g0 hi + g1 hi-1 + …+ gn-k hi-n+k = 0, ( i = 1, 2, …, n - 1 ) 对于任一循环码有：C = U · G 对于任一循环码有： 则 ： C · HT = U · G · HT = 0 因此矩阵H 因此矩阵H被称为循环码的监督矩阵
u' = 0 ×3 = 0 u' = 1 ×3 = 1
wk.baidu.com1 0 0
0 1 11 1 0 c ' 0d 0 0 a 0 0 bc ' c d ' e 0 c ' 1d 1 1 +1
c ' bd ' c e a + u0 2 d × '' b ' c e
1 0 1 1 × '' b ' ce × d
特点： 特点： 1）进行编码的信息位长度无限制； 进行编码的信息位长度无限制； 2）不具有循环性，因此不是循环码，只是一个线性分组码； 不具有循环性，因此不是循环码，只是一个线性分组码； 3）编码电路与循环码相同； 编码电路与循环码相同； 4）译码电路只需检查是否能被整除 检错能力： 检错能力： 1）n长的码组，k个信息位r个校验位，可能的错误总数2k+r； 长的码组， 个信息位r个校验位，可能的错误总数2 2）所有错误中能够整除g(x)的占2k个，其中除全零表示无错外， 所有错误中能够整除g 的占2 其中除全零表示无错外， 其余均可能漏检，则可能漏检的错误有2 其余均可能漏检，则可能漏检的错误有2k – 1个； 3）则漏检率（误检率）为： (2k – 1) / 2k+r ≈ 1/2r 则漏检率（误检率）
电路根据等式进行设计（ 电路根据等式进行设计（ g(x) = x3 + x +1 ） [x3u(x)]mod g(x)= r(x) [ x { x ( x[ u3 x3 ]mod g(x) + u2x3 )mod g(x) + u1x3 }mod g(x) + u0x3 ]mod g(x)
u3u2u1u0c2 c1c0
a
b
c
u3u2u1u0
u3u2u1u0 c2 c1c0
a
b
c
除法过程： 除法过程：
u3u2u1u0
[ x { x ( x[ u3 x3 ]mod g(x) + u2x3 )mod g(x) + u1x3 }mod g(x) + u0x3 ]mod g(x)
1 0 u 0 1 0 1 1 ×3' c ' 0d 0 0
监督多项式与监督矩阵
因为生成多项式g 因为生成多项式g(x)是xn + 1的一个因子，因此：xn + 1 = g(x)h(x) 1的一个因子 因此： 的一个因子， g( g(x) = gn-kxn-k + …+ g1x + g0 h(x) = hk xk + …+ h1x + h0 xn + 1 = g(x)h(x) = (gn-kxn-k + …+ g1x + g0)(hk xk + …+ h1x + h0) g( (g )(h 则： g0 hi + g1 hi-1 + …+ gn-k hi-n+k = 0, ( i = 1, 2, …, n - 1 )
有y = c + e，即y(x) = c(x) + e(x) ，则： e， e(
CRC码 CRC码
即循环冗余校验码，广泛用于数据通信和移动通信中，进行数据的校验，具有 即循环冗余校验码，广泛用于数据通信和移动通信中，进行数据的校验， 实现简单，检错能力强。其原理为： 实现简单，检错能力强。其原理为： 然后除以生成多项式g 1）任意长的信息位向左移动r位，即xru(x)，然后除以生成多项式g(x)得到的 任意长的信息位向左移动r 余数附加在信息码之后形成码组c 然后进行发送； 余数附加在信息码之后形成码组c(x)，然后进行发送； 2）接收端接收到码组y(x)，然后除以g(x)，如果能整除则表示无错发生，否 接收端接收到码组y 然后除以g 如果能整除则表示无错发生， 则表示有错 详细过程： 详细过程： 1）信息位为u(x)，先向左移动r位，即xru(x)。求余式[xru(x)]mod g(x)= r(x) 信息位为u 先向左移动r 求余式[ 2）则将c(x) = xru(x) + r(x)发送出去 则将c 3）若用e(x)表示可能的错误，则接收到 y(x) = c(x) + e(x) = xru(x) + r(x)+e(x)， 若用e 表示可能的错误， )+e 那么校验方法： 那么校验方法： [y(x)]mod g(x)=[xru(x) + r(x) + e(x) ]mod g(x) = r(x) + r(x) + [ e(x) ]mod g(x) =[x
例如：有(7, 4)循环码， g(x) = ( x3 + x2 + 1 ) 4)循环码 循环码， 例如： 因为： g( 因为： xn + 1 = g(x)h(x) 则：h(x) = (xn + 1) / g(x) = x4 + x3 + x2 + 1 ( 11101 ) (x g( 根据监督矩阵H的构造方法可知： 根据监督矩阵H的构造方法可知： 监督多项式为： h*(x) = ( 10111 ) = x4 + x2 + x + 1 监督多项式为：
1 5 即： 5 x + [ x ]mod g ( x ) = 0 G = [ I 4Q ] = 4 x + [ x 4 ]mod g ( x ) 0 3 3 x + [ x ]mod g ( x ) 0
mod g ( x )
0 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1
2）求解[xn-i]mod g(x) ( i = 1, 2, …, k – 1 ) 求解[
x n −1 x 6 n−2 5 x = x I4 = M x4 n−k 3 x x
[x [x [x [x6]mod g(x)=x2 + 1, [x5]mod g(x)=x5 + x2 + x+ 1, [x4]mod g(x)=x4 + x2 + x, [x3]mod g(x)=x3 + x + 1 x6 + [ x6 ]
那么对于生成多项式所构成的生成矩阵G 那么对于生成多项式所构成的生成矩阵G
g n−k 0 G= M 0 g n − k −1 gn −k M L L g n − k −1 M 0 g1 L M g n−k g0 g1 M 0 L g0 L M M g1 0 0 M g0
BCH码 BCH码
是一类能纠正多个随机错误的循环码 其生成多项式为： 其生成多项式为：
g ( x) = LCM [ m1 ( x), m3 ( x),L , m2t −1 ( x) ]
其中m 为素多项式， 为纠错个数，LCM表示取最小公倍数 其中mi(x)为素多项式，t为纠错个数，LCM表示取最小公倍数，最 表示取最小公倍数， 小码距d 2t 小码距d ≥ 2t+1 BCH码分为两种： BCH码分为两种： 码分为两种 1）本原BCH码：码长n = 2m - 1 本原BCH码 码长n 2）非本原BCH码：码长n为2m - 1的因子 非本原BCH码 码长n 其中m 其中m表示素多项式的次数
例如：( 7, 4 )循环码的生成多项式为：g(x)=( x3 + x + 1 )，求其系统码的生成矩阵 )循环码的生成多项式为 循环码的生成多项式为： )， 例如： 1）n = 7，k = 4，因此生成矩阵阶数：4×7。其中单位阵Ik为4×4，Q矩阵4×3 7， 4，因此生成矩阵阶数： 其中单位阵I 矩阵4
1 0 1 1 1 0 0 H = 0 1 0 1 1 1 0 0 0 1 0 1 1 1
循环码的编码
编码：(n,k)循环码的编码包括非系统码的编码和系统码的编码： 循环码的编码包括非系统码的编码和系统码的编码： 编码： 1）非系统码编码：c(x) = u(x)g(x)，采用乘法电路进行编码 非系统码编码： 2）系统码编码：c(x) = xn-ku(x) ＋ [xn-ku(x)]mod g(x) ，采用除法电路进行编码 系统码编码： 以( 7 , 4 )码为例，其生成矩阵为 g(x) = x3 + x +1 )码为例 码为例， 对于信息位：u(x) = u3 x3 + u2 x2 + u1 x + u0 对于信息位： 则 ： x 3 u( x ) = u3 x 6 + u2 x 5 + u1 x 4 + u0 x 3 = x { x ( x [ u3 x 3 ] + u2 x 3 ) + u1 x 3 } + u0 x 3 [x3u(x)]mod g(x) = [ x{ x( x[ u3 x3 ] + u2 x3 ) + u1 x3 } + u0x3 ]mod g(x) 有等式成立： u( {x 有等式成立： [x u(x) + f(x)]mod g(x) = {x [u(x)] mod g(x) + f(x) }mod g(x) 所以： 所以： [x3u(x)]mod g(x)= [ x { x ( x[ u3 x3 ]mod g(x) + u2x3 )mod g(x) + u1x3 }mod g(x) + u0x3 ]mod g(x)
× '' = 0 × =0
0 0
1 1 0 0
× ''== 1 × 1
1 1 0 e c 0 0 d ' 0 b ' ce ' d f 0 d ' c e + 1 1 1 0 b +1
0 0 d' b
监督位
b u1
c' d +
×' c ' d
循环码的译码
系统码生成矩阵生成的码组为： 系统码生成矩阵生成的码组为： c = [u · r] = u · G = u [Ik · Q]，另外 r = u · Q [u 若收到的码组为y 若收到的码组为y，则： s = y · HT = [u · r] · [QT · Ik]T = u · Q + r [u [Q 则s即为校正子（伴随式），其对应的多项式为： 即为校正子（伴随式），其对应的多项式为： ），其对应的多项式为 s(x) = [xn-k u(x)]mod g(x) +说明s(x)与错误图样x)]mod g(x) ，所以 [x r( r(x) = [x与错误图样e(x)有关 [xn-k u(x) + r( e 有关， r( 说明s 即： 同线性分组码一样，可以通过伴随 同线性分组码一样， 与错误图样e s(x) = 式s()]) 与错误图样e(x)纠正错误 [y [y(x x mod g(x) s(x) = [y(x)]mod g(x) = [e(x)]mod g(x) [y [e
4k +1 8 64 744 h0 h1 L hk 0 L 0 H = 0 h0 h1 L hk 0 L 0 M M M M M M M M 0 L 0 h0 h1 L hk ( n − k )×n
g 0 h 0 + g n -k h k = 0