第6章 63-4几种重要码.pptVIP

第6章 信道编码 6.1 信道编码的概念 6.2 线性分组码 6.3 循环码 6.4 卷积码 6.3 循环码 线性分组码对码的选取做了线性约束，使得计算量变小。 译码算法是一种通用译码算法，效率不高。 循环码是1957年由一个叫Prange的科学家开始研究。 循环码在线性约束的基础上增加了约束条件，是目前研究最为成熟的一类码，大多数有实用价值的纠错码都属于循环码的范畴。 定义 定义：对于一个（n，k）线性分组码， 若某一码字为 C=[c1 ,c2 , ... ,cn] 该码字向左循环 1 位后为 C(1)=[c2 ,c3 , ... ,cn ,c1] 该码字向左循环 i 位后为 C(i)=[ci+1 ,ci+2 , ... ,cn ,c1 , ... ,ci] 直至向左循环 n－1 位为 C(n-1)=[cn ,cn-1 , ... ,c1] 若 C(i) , i = 1, 2, ... , n－1 均为码字，则称这个（n，k）线性分组码为循环码。 循环码一般也记为（n，k）码，其中 n 为码字的长度， k 为信息位的长度。 循环码的码多项式 循环码的特点是，若 C 是一个码字，那么它的循环移位所形成的新序列同样也是一个码字。 循环码是线性分组码的一个重要子类，它具有完整的代数结构，其编码和译码相对比较简单，易于实现。 循环码也是线性分组码，因此可用校验矩阵或生成矩阵来构成。但由于循环码具有循环移位特性，且是自封闭的，故采用多项式的方法描述更为方便。 n 长的循环码字 C = [c1 , c2 , ... , cn] 可以用一个 xn-1 次多项式来表示，称为码多项式，表示为 　 C(x)=c1 xn-1 + c2 xn-2 + ... + cn-1 x+ cn 　　　　　　　　 　　　　 码多项式的运算 一元多项式 多项式的次数定义为： 零次多项式：　　　　　　零多项式： 多项式加法： 多项式乘法： 码多项式的运算 码多项式的模运算和整数的模运算类似：长除法。 例如： 码多项式的运算 因式和倍式： 余式： 码多项式的运算 循环码的循环特性可由多项式的模运算来表示 当码字向左移 1 位，相当于乘以 x 后的模 (xn+1) 运算，即 C(1)(x) = x C(x) mod (xn+1) C(1)(x) = c1 xn + c2 xn-1+ ... +cn-1 x2+ cn x mod (xn+1) C(1)(x) = c2 xn-1+ c3 xn-2+ ... + cn x + c1 如果码字向左移 i 位，相当于乘以 xi 后的模(xn+1)运算，即 C(i)(x) = xi C(x) mod (xn+1) C(i)(x) = c1 xn+i-1 + c2 xn+i-2+ ... +cn-1 xi+1+ cn xi mod (xn+1) C(i)(x) = ci+1 xn-1 + ci+2 xn-2 + ... + ci-1 x + ci 例子： 例如： 其中：CA是线性循环码，CB是非循环线性分组码，而CC是非线性循环码。 CA的码字可用多项式：0,x2+x,x+1,x2+1表示。n=3 循环码仍是线性码，由循环码构成的线性子空间为循环子空间。将码表示成C或C(x)。 生成多项式g(x)的两个定理 定理一 (n,k) 循环码C(x)中存在唯一的一个非零的、首一的和最低次数为r ( r n ) 的码多项式 g(x) 满足 并且，c(x)是码式当且仅当c(x)是g(x)的倍式。 定理一证明 唯一性： g0证明:若g0=0，则　　 即g(x)是另一个更底的码式g’(x)的循环移位，矛盾。 码式是g(x)的倍式： 　　由循环移位特性知： xi g(x) ，i=1,2…n-1-r均是码式。 定理一证明（续） 由码的线性分组特性： an-1-rg(x)xn-1-r+…+a1g(x)x+a0g(x)=a(x)g(x) (1) 也是码式。故g(x)的倍式若次数小于n则是码式。 反之：f(x)若是码式，则可表示为： f(x)=a(x)g(x)+r(x)，r(x)的次数小于g(x)的次数，或　r(x)=0。 若r(x) 0，则r(x)＝ f(x)－a(x)g(x)也是码式，但 r(x)的次数r，矛盾。所以r(x)＝０= f(x)是g(x)的倍式。 r=n-k证明：由码式必是g(x)的倍式及(1)式知a0 ， a1 … an-1-r有n-r个，故可组成2n-r个码式，而(n，k)码的码字个数为2k