信息论与编码原理（第九章）──────────────循环码Department of Electronics and Information, NCUTSong Peng第1页第9章 循环码9
.1 循环码的多项式描述 9.2 循环码的生成多项式 9.3 系统循环码 9.4 多项式运算电路 9.5 循环码的编码电路9.6 循环码的译码9.7 循环汉明码 9.8 缩短循环码 9.9 循环码的其它译码方法 9.10 BCH 码和 RS 码Department of Electronics and Information, NCUT Song Peng 第2页9.1 循环码的多项式描述(1) 循环码的性质 (2) 循环码的定义 (3) 码多项式 (4) 举例Department of Electronics and Information, NCUTSong Peng第3页9.1 循环码的多项式描述(1) 循环码的性质? 循环码是线性分组码的一个重要子类；? 由于循环码具有优良的代数结构，可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而 有效的译码方法；? 循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。返回目录Department of Electronics and Information, NCUTSong Peng第4页9.1 循环码的多项式描述(2) 循环码的定义循环码：如果 (n,k) 线性分组码的任意码字：C=(cn－1,cn－2,…,c0)的 i 次循环移位，所得矢量：C(i)=(cn－1－i,cn－2－i,…,c0,cn－1,…,cn－i)仍是一个码字，则称此线性码为 (n,k) 循环码。返回目录Department of Electronics and Information, NCUTSong Peng第5页9.1 循环码的多项式描述(3) 码多项式? 码多项式：为了运算的方便，将码字的各分量作为多项式的系数，把码字表示成多项式，称为码多项式。其一般表示式为：C(x)=cn－1xn－1+cn－2xn－2+…+c0? 码多项式 i 次循环移位的表示方法记码多项式 C(x) 的一次左移循环为 C(1)(x) ，i 次左移循环为 C(i)(x)?C ( x )? cn?1 x n?1 ? cn? 2 x n? 2 ? ? ? c1 ? c0 ? (1) C ( x ) ? cn? 2 x n?1 ? cn? 3 x n? 2 ? ? ? c1 x 2 ? c0 x ? cn?1 ? ? (i ) C ( x ) ? cn?1? i x n?1 ? cn? 2? i x n? 2 ? ? ? c1 x i ?1 ? c0 x i ? cn?1 x i ?1 ? ? ? cn? i ?Department of Electronics and Information, NCUT Song Peng 第6页9.1 循环码的多项式描述(3) 码多项式? 码多项式的模 (xn+1) 运算? 0 和 1 两个元素模 2 运算下构成域。? 若 p 为素数，则整数全体在模 p 运算下的剩余类全体?0, 1, 2, 3,?, p ? 1?在模 p 下构成域。Song Peng 第7页Department of Electronics and Information, NCUT9.1 循环码的多项式描述(3) 码多项式? 码多项式的模 (xn+1) 运算? 以 p=3 为模的剩余类全体? 模 3 运算的规则如下：? 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1? 0 1 20 0 0 01 0 1 22 0 2 1Department of Electronics and Information, NCUTSong Peng第8页9.1 循环码的多项式描述(3) 码多项式? 码多项式的模 (xn+1) 运算? 码字 C 循环 i 次所得码字的码多项式：C ( x ) ? c n ?1 x n ?1 ? c n ? 2 x n ? 2 ? ? ? c0 C ( i ) ( x ) ? c n ? 1? i x n ? 1 ? c n ? 2 ? i x n ? 2 ? ? ? c 0 x i ? c n ? 1 x i ? 1 ? ? ? c n ? i? C(x) 乘以 x，再除以 (xn+1)，得：cn? 2 x n?1 ? cn? 3 x n? 2 ? ? ? c1 x 2 ? c0 x ? cn?1 xC( x ) ? c n ?1 ? n x ?1 xn ? 1 C (1) ( x ) ? c n ?1 ? n x ?1Department of Electronics and Information, NCUT Song Peng 第9页9.1 循环码的多项式描述(3) 码多项式? 码多项式的模 (xn+1) 运算? 上式表明：码字循环一次的码多项式 C(1)(x) 是原码多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作：C (1) ( x) ? x ? C ( x) （模x n ? 1 ）? C(x) 的 i 次循环移位 C(i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即：C ( i ) ( x) ? x i ? C ( x) （模x n ? 1 ）? 结论：循环码的码字的 i 次循环移位等效于将码多项式乘 xi 后再模 (xn+1)。Department of Electronics and Information, NCUT Song Peng返回目录第10页9.1 循环码的多项式描述(4) 举例：(7,3) 循环码? 可由任一个码字，比如 (0011101) 经过循环移位，得到其它 6 个非 0 码字；? 可由相应的码多项式 (x4+x3+x2+1)，乘以 xi(i=1,2,…,6)，再模 (x7+1) 运算得到其它 6 个非 0 码多项式。移位过 程和相应的多项式运算如表8.1所示。Department of Electronics and Information, NCUTSong Peng第11页9.1 循环码的多项式描述(4) 举例：(7,3) 循环码表 8.1.1 循环码的循环移位 移位次数 码 字 0 1 2 3 4 5 6码多项式 (模 x7+1) (模 x7+1)+x3+x2+1 0111010 x(x4+x3+x2+1)≡x5+x4+x3+x(x4+x3+x2+1)≡x6+x5+x4+x2 (模 x7+1) (x4+x3+x2+1)≡x6+x5+x3+1 (x4+x3+x2+1)≡x6+x4+x+1 (x4+x3+x2+1)≡x5+x2+x+1 (x4+x3+x2+1)≡x6+x3+x2+x (模 x7+1) (模 x7+1) (模 x7+1) (模 x7+1)返回目录Department of Electronics and Information, NCUTSong Peng第12页9.2 循环码的生成多项式(1) 循环码的生成矩阵 (2) 循环码的生成多项式 (3) 生成多项式和码多项式的关系 (4) 如何寻找一个合适的生成多项式 (5) 循环码的监督多项式和监督矩阵Department of Electronics and Information, NCUTSong Peng第13页9.2 循环码的生成多项式(1) 循环码的生成矩阵? 循环码的循环特性：可由一个码字的循环移位得到其它的非 0 码字。在 (n,k) 循环码的 2k 个码字中，取前 (k－1) 位皆为 0 的码字g(x)（次数 r=n－k），再经 (k－1) 次循环移位，共得到 k 个码字： g(x), xg(x), …, xk－1g(x)? 这 k 个码字是相互独立的，可作为码生成矩阵的 k 行，得到循环码的生成矩阵 G(x)。矩阵中的元素是多项式：? x k ?1 g ( x ) ? ? g n? k x n?1 ? ? ? g1 x k ? g0 x k ?1 ? ? k ?2 ? ? x g ( x )? ? ? ? ? ? ? ??? G( x ) ? ? ? ? ? ? g n? k x n? k ?1 ? ? ? g1 x 2 ? g0 x ? ? ? xg( x ) ? ? n? k ? ? ? ? g1 x ? g0 ? ? ? g( x ) ? ? gn? k x ? ?Department of Electronics and Information, NCUT Song Peng 第14页9.2 循环码的生成多项式(1) 循环码的生成矩阵? 将矩阵中的多项式改写成对应的 n 重矢量形式：k? ??1个? ?0?? ? g n? k ? g1 g0 0 ? ?0 g n? k ? g1 g0 0 ? G ? ?? ? ?? ? ?0 ? 0 g n ? k ? g1 g0 ?0 ? 0 0 g n ? k ? g1 ?0 ?? ?? 0 ?? ? k ? 1个 0 ? ?? ?? 0 ?? g0 ? ?返回目录Department of Electronics and Information, NCUTSong Peng第15页9.2 循环码的生成多项式(2) 循环码的生成多项式? 码的生成矩阵一旦确定，码就确定了；? (n,k) 循环码可由它的一个 (n－k) 次码多项式 g(x) 来确定；? g(x) 生成了 (n,k) 循环码，称 g(x) 为码的生成多项式。g( x ) ? x n? k ? gn? k ?1 x n? k ?1 ? ? ? g1 x ? g0g(x)是一个(n－k)次首1多项式返回目录Department of Electronics and Information, NCUTSong Peng第16页9.2 循环码的生成多项式(3) 生成多项式和码多项式的关系定理8.2.1：在 (n,k) 循环码中，生成多项式 g(x)是惟一的(n－k)次码多 项式,且次数是最低的。 [证明]：? 先证在 (n,k) 循环码系统中存在 (n－k) 次码多项式。因为在 2k 个信息组中有一个信息组为 00?01 ，它的对应码多项式的次数为： ? ? ?k ?1个n－1－(k－1)=n－k? (n－k) 次码多项式是最低次码多项式。 ? 若 g(x) 不是最低次码多项式，那么设更低次的码多项式为 g'(x) ，其次数为 (n－k－1)。 g'(x) 的前面 k 位为 0，即 k 个信息位全为 0， 而监督位不为 0，这对线性码来说是不可能的，因此 g(x) 是最低 次的码多项式，即 gn－k 必为 1。Department of Electronics and Information, NCUT Song Peng 第17页9.2 循环码的生成多项式(3) 生成多项式和码多项式的关系定理8.2.1：在 (n,k) 循环码中，生成多项式 g(x)是惟一的(n－k)次码多项式,且次数是最低的。[证明]：? (n－k) 次码多项式是最低次码多项式。? g0=1，否则经 (n－1) 次左移循环后将得到低于 (n－k) 次的码多项式。? g(x) 是惟一的 (n－k) 次多项式。如果存在另一个 (n－k) 次码多项式，设为 g''(x) ，根据线性码的封闭性，则 g(x) + g''(x) 也必为一个码多项式。 由于 g(x)和 g''(x) 的次数相同，它们的和式的 (n－k) 次项系数为0，那么 g(x) + g''(x) 是一个次数低于 (n－k) 次的码多项式，前面已证明 g(x) 的次 数是最低的，因此 g''(x) 不能存在，所以 g(x) 是惟一的 (n－k) 次码多项 式。Department of Electronics and Information, NCUTSong Peng第18页9.2 循环码的生成多项式(3) 生成多项式和码多项式的关系定理8.2.2：在 (n,k) 循环码中，每个码多项式 C(x) 都是 g(x) 的倍式；而每个为 g(x) 倍式且次数小于或等于 (n－1) 的多项式，必是一个码多项式。 [证明]：? 设 m=(mk－1,mk－2,…,m0) 为任一信息组，G(x) 为该 (n,k) 循环码的生成矩阵，则相应的码多项式为：C(x)=m?G(x)：? x k ?1 g ( x ) ? ? k ?2 ? x g ( x )? ? ? ? ( m k ?1 x k ?1 ? m k ? 2 x k ? 2 ? ? ? m 0 ) g ( x ) C ( x ) ? ( m k ?1 , m k ? 2 , ? , m 0 ) ? ? ? ? ? xg( x ) ? ? g( x ) ? ? ?Department of Electronics and Information, NCUT Song Peng 第19页9.2 循环码的生成多项式(3) 生成多项式和码多项式的关系定理8.2.2：在 (n,k) 循环码中，每个码多项式 C(x) 都是 g(x) 的倍式；而每个为 g(x) 倍式且次数小于或等于 (n－1) 的多项式，必是一个码多项式。 [证明]：? 循环码的任一码多项式为 g(x) 的倍式。? 凡是为 g(x) 的倍式且次数小于或等于 (n－1) 的多项式，一定能分解成上式的形式，因而它就是信息多项式：m(x)=(mk－1xk－1+mk－2 1xk－2+…+m0)并由生成矩阵 G(x) 所生成的码多项式。Department of Electronics and Information, NCUTSong Peng第20页9.2 循环码的生成多项式(3) 生成多项式和码多项式的关系定理8.2.3(定理8.2.2的逆定理)：在一个 (n,k) 线性码中，如果全部码多项式都是最低次的 (n－k) 次码多项式的倍式，则此线性码为一个 (n,k) 循环码。注：一般说来，这种循环码仍具有把 (n,k) 线性码码中任一非 0 码字循环移位必为一码字的循环特性，但从一个 非 0 码字出发，进行循环移位，就未必能得到码的所有 非 0 码字了。所以称这种循环码为推广循环码。Department of Electronics and Information, NCUTSong Peng第21页9.2 循环码的生成多项式(3) 生成多项式和码多项式的关系? 码字循环关系图? 单纯循环码的码字循环图：(7,3)循环码 101110111001001图8.2 (7,3)循环码的循环关系图Department of Electronics and Information, NCUT Song Peng 第22页9.2 循环码的生成多项式(3) 生成多项式和码多项式的关系? 码字循环关系图100100? 推广循环码的码字循环图：001001(6,3)循环码010 011 000000 图8.2.2 (6,3)循环码的循码字环关系图返回目录Department of Electronics and Information, NCUTSong Peng第23页9.2 循环码的生成多项式(4) 如何寻找一个合适的生成多项式? 循环码的码多项式等于信息多项式乘以生成多项式：? x k ?1 g ( x ) ? ? k ?2 ? x g ( x )? ? ? ? ( m k ?1 x k ?1 ? m k ? 2 x k ? 2 ? ? ? m 0 ) g ( x ) C ( x ) ? ( m k ?1 , m k ? 2 , ? , m 0 ) ? ? ? ? xg( x ) ? ? ? g( x ) ? ? ?? 对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。? 作一循环码的关键，就在于寻找一个适当的生成多项式。Department of Electronics and Information, NCUT Song Peng 第24页9.2 循环码的生成多项式(4) 如何寻找一个合适的生成多项式定理8.2.4： (n,k) 循环码的生成多项式 g(x) 是 (xn+1)的因式，即：xn+1=h(x)?g(x)。[证明]：欧几里德除法：设 b 是正整数，则任 意正整数 a &b 皆可惟一地表示成： a=q?b+r 0≤r & b? 由于 xk g(x) 是 n 次多项式，可表示为：xk g(x)=1?(xn+1)+ g(k)(x)(8.2.1)? 式中 g(k)(x) 是多项式 g(x) 乘以 xk 除以 (xn+1) 的余式。 ? 根据循环码的移位关系，它是 g(x) 循环移位 k 次所得到的多项式，因而 g(k)(x) 是 g(x) 的倍式。? 设：g(k)(x)=m(x)g(x)代入式(8.2.1)得：(xn+1)=[xk+m(x)]g(x)Song Peng 第25页? 即：g(x) 是 (xn+1) 的因式。Department of Electronics and Information, NCUT9.2 循环码的生成多项式(4) 如何寻找一个合适的生成多项式定理8.2.5：若 g(x) 是一个 (n－k) 次 多项式，且为(xn+1) 的因式，则g(x) 生成一个 (n,k) 循环码。[证明]：? 由于 g(x) 是一个 (n－k) 次多项式，且为 (xn+1) 的因式，所以：g(x), x?g(x),…, xk－1 ? g(x) 是 k 个次数小于 n，并且彼此独立的多项式； ? 将此多项式用作码的生成矩阵的 k 行，得到 (n,k) 线性码的生成矩阵；? x k ?1 g ( x ) ? ? k ?2 ? x g ( x )? ? ? G( x ) ? ? ? ? ? ? xg( x ) ? ? g( x ) ? ? ?Song Peng 第26页Department of Electronics and Information, NCUT9.2 循环码的生成多项式(4) 如何寻找一个合适的生成多项式定理8.2.5：若 g(x) 是一个 (n－k) 次 多项式，且为(xn+1) 的因式，则 g(x) 生成一个 (n,k) 循环码。[证明]：? 设信息组 m=(mk－1,mk－2,…,m0)，则相应的码字为：C(x)=m ?G(x)=(mk－1xk－1+mk－2 1xk－2+…+m0)?g(x)= m(x)?g(x)? C(x) 的次数≤n－1； ? m(x) 是 2k 个信息多项式的表示式； ? 所以：C(x) 即为相应 2k 个码多项式的表示式。 ? 因此：g(x) 生成一个 (n,k) 线性码。 ? C(x) 是 (n－k) 次多项式 g(x) 的倍式，所以 g(x) 生成一个 (n,k)循环码。Department of Electronics and Information, NCUT Song Peng 第27页9.2 循环码的生成多项式(4) 如何寻找一个合适的生成多项式定理8.2.5：若 g(x) 是一个 (n－k) 次 多项式，且为(xn+1) 的因式，则 g(x)生成一个 (n,k) 循环码。? 结论：求作一个 (n,k) 循环码时，只要分解多项式(xn+1) ，从中取出(n－k)次因式作生成多项式即可。? 例：求 (7,3) 循环码的生成多项式。[解]：? 分解多项式 x7+1，取其 4 次因式作生成多项式：x7+1= (x+1) (x3+x2+1) (x3+x+1)? 可将一次和任一个三次因式的乘积作为生成多项式，可取：g1(x)= (x+1) (x3+x2+1) = x4+x2+x+1 或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1返回目录Department of Electronics and Information, NCUTSong Peng第28页9.2 循环码的生成多项式(5) 循环码的监督多项式和监督矩阵① 循环码的监督多项式：设 g(x) 为 (n,k) 循环码的生成多项式，必为(xn+1) 的因式，则有：xn+1=h(x)?g(x)，式中 h(x) 为 k 次多项式，称为 (n,k) 循环码的监督多项式。? (n,k) 循环码也可由其监督多项式完全确定。? 举例：(7,3) 循环码：x7+1= (x3+x+1)(x4+x2+x+1)? 4 次多项式为生成多项式：g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0? 3 次多项式是监督多项式：h(x)=x3+x+1=h3x3+h2x2+h1x+h0Department of Electronics and Information, NCUTSong Peng第29页9.2 循环码的生成多项式(5) 循环码的监督多项式和监督矩阵② 循环码的监督矩阵? 由等式 x7+1= h(x)?g(x) 两g( x ) ? x 4 ? x 2 ? x ? 1 ? g4 x 4 ? g3 x 3 ? g2 x 2 ? g1 x ? g0? x 3的 系 数 ： 3 h0 ? g2 h1 ? g1h2 ? g0 h3 ? 0 g ? 4 g ? x 的 系 数 ： 4 h0 ? g 3 h1 ? g 2 h2 ? g1h3 ? 0 ? 5 g ? x 的 系 数 ： 4 h1 ? g 3 h2 ? g 2 h3 ? 0 ? x 6的 系 数 ： h ? g h ? 0 g4 2 3 3 ??0? ?0? h3 ? ? ? ? g4 ? 0 ?? ? ? g ?0T 3 0 ?? ? ? ? g2 ? 0 ?? ? ? g1 ? ?g ? ? 0?第30页端同次项系数相等得：? 将上面的方程组写成矩阵形式：h( x ) ? x 3 ? x ? 1 ? h3 x 3 ? h2 x 2 ? h1 x ? h0?0 ?0 ? ?0 ? ? h00 0 h0 h10 h0 h1 h2h0 h1 h2 h3h1 h2 h3 0h2 h3 0 0Department of Electronics and Information, NCUTSong Peng9.2 循环码的生成多项式(5) 循环码的监督多项式和监督矩阵② 循环码的监督矩阵? 上式中，列阵的元素是生成多项式 g(x) 的系数，是一个码字，那么第一个矩阵则为 (7,3) 循环码的监督矩阵，即：H (7,3)? 0 0 0 h0 h1 h2 h3 ? ?0 0 h h h h 0? 0 1 2 3 ? ?? ? 0 h0 h1 h2 h3 0 0 ? ? ? ? h0 h1 h2 h3 0 0 0 ?(8.2.2)Department of Electronics and Information, NCUTSong Peng第31页9.2 循环码的生成多项式(5) 循环码的监督多项式和监督矩阵③ 循环码监督矩阵的构成? 由式 (8.2.2) 可见，监督矩阵的第一行是码的监督多项式 h(x) 的系数的反序排列，第二、三、四行是第一行的移位；? 可用监督多项式的系数来构成监督矩阵：H (7,3)? h* ( x ) ? ?0 ? * ? ? xh ( x ) ? ?0 ?? 2 * ? ? x h ( x )? ? 0 ? 3 * ? ? ? x h ( x )? ? 1 ? ?0 0 1 1 0 1? 0 1 1 0 1 0? ? 1 1 0 1 0 0? ? 1 0 1 0 0 0?(8.2.3)其中h*(x) 表示 h(x) 的反多项式Department of Electronics and Information, NCUT Song Peng 第32页9.2 循环码的生成多项式(5) 循环码的监督多项式和监督矩阵③ 循环码监督矩阵的构成? (n,k) 循环码的监督矩阵：H ( n ,k )? h* ( x ) ? ?0 ? ? ? xh* ( x ) ? ?0 ?? ? ? ? ?? ? ? n ? k ?1 * ? ? h ( x )? ? 1 ?x ? ?? 0 ? 1 ? h11 h1 ?h1?? hk ?1 hk ?1 1 1 0h1 ? hk ?1hk ?1 1? 1 0? ? ? ?? ? ? 0?Department of Electronics and Information, NCUTSong Peng第33页9.2 循环码的生成多项式(5) 循环码的监督多项式和监督矩阵④ 对偶问题? 如果 xn+1=h(x)?g(x)，其中 g(x) 为 (n－k) 次多项式，以 g(x)为生成多项式，则生成一个 (n,k) 循环码；? 以 h(x) 为生成多项式，则生成 (n,n－k) 循环码；? 这两个循环码互为对偶码。返回目录Department of Electronics and Information, NCUTSong Peng第34页9.3 系统循环码(1) 系统循环码构成? 信息向量：m=(mk－1,mk－2,…,m0)? 信息多项式：m(x)=mk－1xk－1+mk－2 xk－2+…+m0? 码多项式的高次幂部分等于 m(x)，即：C(x)=cn－1xn－1+…+ cn－kxn－k+ cn－k－1xn－k－1 …+c1x +c0 =xn－k m(x)+q(x)? 校验位多项式：q(x) ? 由于码多项式是生成多项式的倍式，所以：（q(x)的次数&n－k）C(x)= xn－km(x)+q(x)=a(x)g(x)≡0 （mod g(x)） q(x)=C(x)+ xn－km(x)≡xn－km(x) （mod g(x)）Department of Electronics and Information, NCUT Song Peng 第35页9.3 系统循环码(1) 系统循环码构成? 循环码的系统码形式为：C(x)= xn－km(x)+ (xn－km(x) mod g(x))? 系统循环码构造过程步骤? 信息多项式乘 xn－k： xn－km(x) ? 对 xn－km(x) 求余式：q(x)≡xn－km(x) (mod g(x)) ? 求码多项式：C(x)=xn－km(x)+ ( xn－km(x) mod g(x))=xn－km(x)+ q(x)Department of Electronics and Information, NCUTSong Peng第36页9.3 系统循环码(2) 举例[例6.3.5]：在由 g(x)=x4+x3+x2+1生成的 (7,3) 循环码中，求信息组m=(101)的对应码多项式。x 7? 3 m( x ) ? x 4 ( x 2 ? 1) ? x 6 ? x 4，除以 ( x )得到余式： g r( x) ? x ? 1于是码多项式为：( x ) ? x 4 m( x ) ? r ( x ) C? x6 ? x4 ? x ? 1返回目录Department of Electronics and Information, NCUTSong Peng第37页9.4 多项式运算电路(1) 多项式加法电路 (2) 多项式乘法电路 (3) 多项式除法电路Department of Electronics and Information, NCUTSong Peng第38页9.4 多项式运算电路(1) 多项式加法电路? 多项式 a(x)=anxn+an－1xn－1+…+a1x+a0 表示的是时间序列a=(an,an－1,…,a1,a0)，因此多项式的计算表现为对时间序列的操作；? 对二进制多项式系数的基代表一个寄存器本操作为模 2 加和模 2 乘；? 电路图运算符号的意义：代表模2加代表2个输入端与门代表乘法器Department of Electronics and Information, NCUTSong Peng第39页9.4 多项式运算电路(1) 多项式加法电路? A(x) 与 B(x) 的相加电路a0 a1 … an－1 an …c0 …c1cn-1cnb0b1bn-1bnA(x)C(x)图8.4.1 多项式相加C(x)=A(x)+B(x)B(x)返回目录Department of Electronics and Information, NCUTSong Peng第40页9.4 多项式运算电路(2) 多项式乘法电路? 多项式乘以 x 等价为时间序列 a 延迟一位；? 多项式 a(x) 与多项式 g(x) 的乘等价为 a(x) 的不同位移后的相加：a(x)g(x)=a(x)(g1(x)+ g2(x))= a(x)g1(x)+ a(x)g2(x)? 多项式乘法电路：设多项式的低位在前，电路中所有寄存器初态为 0。a(x) (1) g(x)=1a(x)a(x) (2) g(x)=xxa(x)a(x) (3) g(x)=x2x2a(x)(x+1)a(x)(x2+1)a(x)(x2+x)a(x)a(x) (4) g(x)=x+1a(x) (5) g(x)=x2+1a(x) (6) g(x)=x2+x=x(x+1)图8.4.2 多项式乘法电路Department of Electronics and Information, NCUTSong Peng第41页9.4 多项式运算电路(2) 多项式乘法电路? 多项式乘法电路：a(x)g(x)g0g1g2gr－1gr1 a(x)2 g(x)=g0+g1x+…+gr－1xr－1+grxrr图8.4.3 多项式乘法电路返回目录Department of Electronics and Information, NCUTSong Peng第42页9.4 多项式运算电路(3) 多项式除法电路? 当 g(x) =1，多项式 a(x) 模 g(x) 的余式为 0，电路如图所示。a(x) g(x)=1a(x)≡0 (mod g(x)=1)图8.4.4 多项式模g(x)=1的运算电路Department of Electronics and Information, NCUTSong Peng第43页9.4 多项式运算电路(3) 多项式除法电路? 当 g(x)是单向式 g(x)=xk， a(x) 模 g(x) 的余式的次数小于 k，进入电路的输入顺序为 an,an－1,…,a1,a0。a(x)≡ak－1xk－1+ak－2xk－2+…+a 1x+a0(mod xk)运算电路如图所示。a(x)≡a0 (mod x) a(x) a0 (1) g(x)=xa(x)a0a1 (2) g(x)=x2a(x)≡a1x＋a0 (mod x2)图8.4.5 多项式模运算电路Department of Electronics and Information, NCUT Song Peng 第44页9.4 多项式运算电路(3) 多项式除法电路? 由于 xk≡1 mod(x+1), k=0,1,2,…。若 a(x) 的次数为 n，则：a(x) = an－1+an－2+…+a1+a0（mod(x+1)）≡ q0（mod 2）运算电路如图所示：KA a(x) q0 g(x)=x+1 KB a(x) (mod x+1)图8.4.6 多项式模(x+1)运算电路Department of Electronics and Information, NCUTSong Peng第45页9.4 多项式运算电路(3) 多项式除法电路? 同样由长除法得：a( x ) ?i ? 0 , 2 , 4? i?n? ai ?i ?1, 3 , 5? i?n? ai ? q0 ? q1q1 ?i i ?1, 3 , 5? i?n(mod(x 2 ? 1))其中： 0 ? qi i ? 0 , 2 , 4? i?n?a?a运算电路如图所示：KA KB q0 q1 g(x)=x2+1 a(x) (mod x2+1)a(x)图8.4.7 多项式模(x2+1)运算电路Department of Electronics and Information, NCUTSong Peng第46页9.4 多项式运算电路(3) 多项式除法电路? 多项式 a(x) 模 (x2+x+1) 的运算电路如图所示：KA KB a(x) (mod x2+x+1) q0 g(x)=x2+x+1 q1a(x)图8.4.8 多项式模(x2+x+1)运算电路Department of Electronics and Information, NCUTSong Peng第47页9.4 多项式运算电路(3) 多项式除法电路? 一般的多项式模 g(x)=grxr+gr－1xr－1+…+g1x+g0 的运算电路如图所示。? 移位寄存器初态全为0； ? 当 a(x) 输入完后，移位寄存器内容 (qr－1, …, q1, q0) 就是余式：q(x)=qr－1xr－1+ qr－2xr－2+ …+q1x+q0≡ a(x) (mod g(x))KAg0=1g1g2gr－1gr=1 KB a(x) (mod g(x))q0 a(x)q1qr－2qr－1图8.4.9 多项式模g(x)=grxr+gr－1xr－1+…+g1x+g0)运算电路Department of Electronics and Information, NCUTSong Peng第48页9.4 多项式运算电路(3) 多项式除法电路? 多项式除法电路的构造? 多项式除法电路是一个由除式（这里就是生成多项式 g(x)）g(x)=gn－kxn－k+gn－k－1xn－k－1+…+g1x+g0 所确定的反馈移位寄存器。? 除法电路的构造方法 ① 移位寄存器的级数等于除式的次数 n－k； ② 移位寄存器的反馈抽头，由除式的各项系数 gi(i=0,1,…,n－k) 决定： ? 当某个抽头=0时，对应的反馈断开； ? 当某个抽头=1时，对应的反馈接通。 ③ 完成除法所需的移位次数等于被除式的次数加1。Department of Electronics and Information, NCUT Song Peng 第49页9.4 多项式运算电路(3) 多项式除法电路? 多项式除法电路举例? 利用除法电路完成两个多项式除法运算，求其余式的过程和将两个多项式进行长除运算是完全一致的；? (x5+x2)÷(x4+x3+x +1) 的长除运算过程：x ?1 x4 ? x3 ? x ? 1 x5 (除 式) x5 ? x4 x4 x4 ? x3 x3(商 式) ? x2 ? x2 ? x(被 除 式 )? x (第 一 余 式 ) ? x ?1 ? 1 (第 二 余 式 )Song Peng 第50页Department of Electronics and Information, NCUT9.4 多项式运算电路(3) 多项式除法电路? 多项式除法电路举例? (x5+x2)÷(x4+x3+x +1) 的长除运算过程：① 每做一次除法运算，被除式（或前次除法的余式）的首项被抵消，因而除法电路中每做一次除法运算，最高项就移到寄存器之外而丢掉；② 除式除首项外的其它各项系数都要加到被除式或前次运算的余式中去，而除法电路的反馈正是按除式的规律连接的，恰好完成所需的加法运算。Department of Electronics and Information, NCUTSong Peng第51页9.4 多项式运算电路(3) 多项式除法电路? 多项式除法电路举例? (x5+x2)÷(x4+x3+x +1) 运算电路工作过程：① 各级预先清零，被除式系数由移位寄存器第一级输入，经 4 次 移位后，最高项的系数到达移位寄存器右端出现反馈信号；② 第一次对被除式作除法，下一个移位脉冲加入时，被除式首项x5 移出寄存器，相当于首项被抵消，反馈信号按除式规律与被除 式相应项进行模 2 加，移位寄存器新的内容即为第一余式；KA 1 输入a(x) D0 x D1 D2 x3 D3 x4 KB商输出q(x)图8.4.10 以x4+x3+x+1为除式的除法(求余)电路Department of Electronics and Information, NCUT Song Peng 第52页9.4 多项式运算电路(3) 多项式除法电路? 多项式除法电路举例? (x5+x2)÷(x4+x3+x +1) 运算电路工作过程：③ 第一余式的首项 x4 的系数到达电路的末级，出现反馈信号，准 备作第二次除法，当下一个移位脉冲加入时，第一余式的首项移 出寄存器被丢掉，反馈信号又把除式(除首项外)加到第一余式，得 到第二余式（即所求余式）； ④ 为了使被除式全部移入寄存器，除法求余所需要的移位次数等 于被除式次数加 1。 KA1 输入a(x) D0 x D1 D2 x3 D3 x4 KB 商输出q(x)图8.4.10 以x4+x3+x+1为除式的除法(求余)电路Department of Electronics and Information, NCUT Song Peng 第53页9.4 多项式运算电路(3) 多项式除法电路? 多项式除法电路举例? 表 8.4.1 列出了电路的运算过程表 8.4.1 x5+x2 除以 x4+x3+x+1 的运算过程表 节拍 输入 移位寄存器内容 输出 D0(x0) D1(x1) D2(x2) D3(x3) 0 0 0 0 0 0 0 1 1(x5) 1 0 0 0 0 2 0(x4) 0 1 0 0 0 3 0(x3) 0 0 1 0 0 4 1(x2) 1 0 0 1 0 5 0(x1) 1 0 0 1 1(x1) 6 0(x0) 1 0 0 1 1(x0) 余式 商式Department of Electronics and Information, NCUT Song Peng 第54页9.5 循环码的编码电路9.5.1 非系统码编码电路 9.5.2 系统码编码电路(1) 系统码编码的基本原理 (2) 用 (n－k) 级移位寄存器实现的编码电路(3) 用 k 级移位寄存器实现的编码电路Department of Electronics and Information, NCUTSong Peng第55页9.5.1 非系统码编码电路9.5 循 环 码 的 编 码 电 路? 循环码码多项式是生成多项式的倍式。 ? 非系统编码电路/循环码乘法编码电路 ? 输入 a(x)=m(x)， m(x)的次数 &k ? 输出 a(x)g(x)=C(x)即是码式，C(x)的次数 &na(x)g(x)g0g1g2gr－1gr1 a(x)2 g(x)=g0+g1x+…+gr－1xr－1+grxrr图8.5.1 多项式乘法电路Department of Electronics and Information, NCUTSong Peng第56页9.5.1 非系统码编码电路9.5 循 环 码 的 编 码 电 路? 举例：生成 (7,4) 汉明码的生成多项式为 g(x)=x3+ x2+1，非系统编码电路如图所示。电路共工作 7 个时钟节拍。C(x) g0=1D2 D1g2=1g3=1D0(c0 ,c1 ,c2 ,c3 ,c4 ,c5 ,c6)m(x) (m0 ,m1 ,m2 ,m3) 图8.5.2 (7,4)汉明码非系统编码电路(低位在前)Department of Electronics and Information, NCUTSong Peng第57页9.5.1 非系统码编码电路9.5 循 环 码 的 编 码 电 路? 举例：生成 (7,4) 汉明码的生成多项式为 g(x)=x3+ x2+1，非系统编码电路如图所示。电路共工作 7 个时钟节拍。表 8.5.1 (7,4)非系统循环码编码电路工作过程 状态方程与 时钟 消息 移位寄存器内容 码字 输出方程 T M(X) D3 D2 D1 C(X) 1 m0 0 0 0 0 0 C0 D3=m D2=D3 2 m1 1 0 0 0 1 C1 D1=D2 3 m2 0 1 0 0 0 C2 4 m3 1 0 1 0 0 C3 C=m+ D1+D2 5 m4 0 1 0 1 1 C4 6 m5 0 0 1 0 1 C5 7 m6 0 0 0 1 1 C6? 由表可见，当 m(x)=x3 + x时，非系统码字 C(x) 为：C(x)= x6 + x5 +x4 + x =(x3+x)(x3 + x2 +1)Department of Electronics and Information, NCUT Song Peng返回目录第58页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(1) 系统码编码的基本原理? 求生成多项式 g(x)：分解多项式 (xn+1)，取 (n－k)次 因式作生成多项式 g(x)，一般可通过查表完成。? 利用 g(x) 实现编码 ? 设信息多项式为：m(x)=mk－1xk－1+mk－2 xk－2+…+m0? 设监督多项式为：q(x)=qr－1xr－1+qr－2 xr－2+…+q0? (n,k) 循环码的码多项式为：C(x)=cn－1xn－1+cn－2xn－2+…+cn－kxn－k +cn－k－1xn－k－1+…+c1x+c0前 k 项系数为信息位，后 r= n－k 项为校验位。? 所以：cn－1xn－1+…+cn－kxn－k=xn－k(mk－1xk－1+…+m0)=xn－km(x)cn－k－1xn－k－1+…+c0=qr－1xr－1+…+q0=q(x)Department of Electronics and Information, NCUT Song Peng返回目录第59页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(2) 用 (n－k) 级移位寄存器实现的编码电路? 循环码编码电路结构和工作原理 ? 工作原理：二元 (n,k) 循环码的编码是将信息多项式 m(x) 乘 xn－k 后再除以生成多项式g(x) 求出它的余式，即为监督位多项式 q(x)。C(x)= xn－km(x)+（xn－km(x) mod g(x)）? 二元 (n,k) 循环码的编码电路就是以 g(x) 为除式的除法电路，而输入的被除式为 xn－km(x) 。? 实际的编码电路如图 8.5.3 所示。 其级数等于 g(x) 的次数 (n－k) ；参见图 反馈连接决定于 g(x) 的系数? 当 gi=0 时 (i=0,1,2,…, n－k)，反馈断开； ? 当 gi=1 时，对应级加入反馈。Department of Electronics and Information, NCUT Song Peng 第60页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(2) 用 (n－k) 级移位寄存器实现的编码电路? 循环码编码电路结构和工作原理? 由于被除式中含有因子 xn－k ，使被除式各项的次数都 ≥g(x) 的次数，所以被除式输入端可由第一级移到末级之后，使移位次数减少 (n－k) 次。这样编一个码字求监督位所需的移位次数只要 k 次。控制门 时序控制g1g2gn－k－1 2 K 1 m(x) 输出D0D1D2Dn-k-1图8.5.3 用g(x)构造的编码电路(n－k)级返回Department of Electronics and Information, NCUTSong Peng第61页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(2) 用 (n－k) 级移位寄存器实现的编码电路? 工作过程? 各级移位寄存器清“0”，控制门开，开关K设置为位置1；? k 位信息位 mk－1, mk－2,…,m1, m0 依次从末端输入编码电路；同时送入信道，在每加入一位信息位时，各级移位寄存器移位一次。当 k 位信息位都输入移位寄存器后，移位寄存器中 (n－k) 位数字即为监督位；? 控制门关，断开反馈，开关 K 由位置 1转到位置 2，寄存器中的存数（监督位）依次移出，送入信道。k 位信息位和 (n－k) 位监督位组成一个码字。参见图Department of Electronics and Information, NCUTSong Peng第62页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(2) 用 (n－k) 级移位寄存器实现的编码电路? 举例? 由 g(x)=(x3+x +1) 作生成多项式所生成的 (7,4) 循环码的编码电路如图8.5.4所示。? 它包括 3 级寄存器g1=1，第一级反馈接通； g2=0，到第二级的反馈断开。g1 2D0 D1 D2控制门 时序控制? 每经四次移位，输入一个四K 输出位信息组；寄存器中的内容即 为监督位； ? 监督位跟在信息位之后，便 构成一个码字。1 m(x) 图8.5.4 g(x)=x3+x+1生成的(7,4)循环码的编码电路返回目录Department of Electronics and Information, NCUTSong Peng第63页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(3) 用 k 级移位寄存器实现的编码电路? 循环码的监督方程? 在 (n,k) 循环码中，若 k &(1/2)n，即信息位比监督位少时，可采用 k 级移位寄存器的编码电路。? 根据线性码的监督方程：HCT=0T式中：C ? (cn?1 , cn? 2 , ? , cn? k cn? k ?1 , cn? k ? 2 , ? , c0 )为任意码字 ??????? ??? ???? ? ?k位信息位 n ? k位监督位将 H ( n? k )?n?0 ?0 ?? ?? ? ?1?01 h1 ?h1 ? hk ?1 1? hk ?1 1 0? 1 ? h1h1 ? hk ?1hk ?1 1? 1 0? ? 代入上式 ? ?? ? ? 0?Song Peng 第64页Department of Electronics and Information, NCUT9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(3) 用 k 级移位寄存器实现的编码电路? 循环码的监督方程? c n ?1 ? ??? ???? ? ? ? ? 1 h11 ? hk ?1 1 1 ? ? ? ? ? hk ? 1 ?0 ? 0 1 h ?0 ? 1 h ? hk ?1 1 0? ?cn? k ? 1 T ?? 得：? ? ?0 ? ? ? h1 ? hk ?1 1 ? ? ? ? c n ? k ?1 ? ? ?? 0 ? 0? ? ? ?1 h1 ? hk ?1 1 ? ? ? c0 ? ? ?k ?1位Department of Electronics and Information, NCUTSong Peng第65页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(3) 用 k 级移位寄存器实现的编码电路? 循环码的监督方程? 由此得到 (n－k) 个监督方程，进而得到 (n－k) 个监督位的表示式：? cn? k ?1 ? cn?1 ? h1cn? 2 ? ? ? hk ?1cn? k ?c ? n? k ? 2 ? cn? 2 ? h1cn? 3 ? ? ? hk ?1cn? k ?1 ? ? ? ? c0 ? ck ? h1ck ?1 ? ? ? hk ?1c1 ?Department of Electronics and Information, NCUTSong Peng第66页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(3) 用 k 级移位寄存器实现的编码电路? 循环码的监督方程? 每个监督码元都是由它前面的 k 个码元按同一规律确定的；? 第一个监督元 cn－k－1 是 k 个信息元与 h(x) 的系数决定的； ? 第二个监督元是前面 (k－1) 个信息元和第一个监督元与 h(x) 的系数决定的；? …，如此类推； ? 最后一个监督元 c0 都按同一 规律决定。? cn? k ?1 ? cn?1 ? h1cn? 2 ? ? ? hk ?1cn? k ?c ? n? k ? 2 ? cn? 2 ? h1cn? 3 ? ? ? hk ?1cn? k ?1 ? ? ? ? c0 ? ck ? h1ck ?1 ? ? ? hk ?1c1 ?Song Peng 第67页Department of Electronics and Information, NCUT9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(3) 用 k 级移位寄存器实现的编码电路? 监督位表示式特点：电路如图所示控制门2hk－1 cn-k-1Dk-1h k－ 2h2 cn-2D2h1 cn-1D1控制 m(x)cn-kDk门1 输出图8.5.5 用h(x)构造的编码电路(k 级)返回Department of Electronics and Information, NCUTSong Peng第68页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(3) 用 k 级移位寄存器实现的编码电路? 工作过程：? 门1开，门2关，k 位信息串行送入 k级移位寄存器，并同时送入信道;? 门1关，门2开，每移位一次输出一位监督位，并同时送入信道，经 (n－k) 次移位，就在 k 位信息位之后附加上 (n－k) 位监督位，构成了一个码字。? 举例：利用监督多项式构造 (7,3) 循环码的编码电路。参见图? x7+1=(x+1)(x3+x+1)(x3+x2+1)? 任取一个三次因式为监督多项式：h(x)=x3+x+1 ? 得：h3=1, h2=0, h1=1, h0=1Department of Electronics and Information, NCUT Song Peng 第69页9.5.2 系统码编码电路9.5 循 环 码 的 编 码 电 路(3) 用 k 级移位寄存器实现的编码电路? 举例：利用监督多项式构造 (7,3) 循环码的编码电路。? 由三级移位寄存器构成的 (7,3) 循环码的编码电路如图所示。控制门2 控制 m(x) c4D3h1 c5D2c6D1门1 输出图8.5.6 用h(x)构造的(7,3)编码电路返回目录Department of Electronics and Information, NCUTSong Peng第70页9.6 循环码的译码9.6.1 接收矢量伴随式计算 9.6.2 循环码的通用译码法Department of Electronics and Information, NCUTSong Peng第71页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(1) 根据伴随式定义 ST=HRT 计算伴随式 S (2) 用 k 级移位寄存器的伴随式计算电路 (3) 用 n－k 级移位寄存器的伴随式计算电路 (4) 接收字循环移位的伴随式与伴随式循环移位的 关系Department of Electronics and Information, NCUTSong Peng第72页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(1) 根据伴随式定义 ST=HRT 计算伴随式 S? 设：? h n ? k ?1 ? ? ? ? h n? k ? 2 ? H ?? ? ? ? ? ?h ? ? 0 ?其中h i ( i ? n ? k ? 1, n ? k ? 2,? ,0) 表示H的行矢量。? 设：S ? ( sn? k ?1 , sn? k ? 2 ,? , s0 )，得到伴随式各分量的 表示式 S T ? HR T? h n ? k ?1 R T ? ? sn ? k ?1 ? ? h n ? k ?1 ? ? ? ? ? ? ? T ? sn ? k ? 2 ? ? h n ? k ? 2 ? T ? h n ? k ? 2 R ? T S ?? ? ? ? ?? ?R ? ? ? ? ? ? ? ? ? ? ?s ? ?h ? ? h RT ? ? 0 ? ? 0 ? ? 0 ?Department of Electronics and Information, NCUT Song Peng 第73页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(1) 根据伴随式定义 ST=HRT 计算伴随式 S输入R0R1R2R3R4R5R6输出? sn? k ?1 ? h n? k ?1R T ? T ? sn? k ? 2 ? h n? k ? 2R 所以： ? ? ? ? s0 ? h 0R T ?S0S1S2S3图8.6.1 (7,3)码伴随式计算电路? 这是前面介绍过的由接收矢量相应分量直接求和计算伴随式的方法，对所有线性码都适用。? 电路是 (n－k) 个多输入的奇偶校验器，每个奇偶校验器的输入端由 H 阵的相应行 hi 中的 1 决定（参看图8.6.1）Department of Electronics and Information, NCUT Song Peng 第74页9.6.1 接收矢量伴随式计算8.6 循 环 码 的 译 码(1) 根据伴随式定义 ST=HRT 计算伴随式 S?1 0 1 ?1 1 1 T T S ? H ?R ? ? ?1 1 0 ? ?0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 ?r6 ? ?r ? 5 0? ? ? ? r6 ? r4 ? r3 ? ? s3 ? ?r4 ? ? 0? ? ? ?r6 ? r5 ? r4 ? r3 ? ? s2 ? ??? ? ? r3 ? ? ? ?r ? r ? r ? ? s1 ? 0? 6 5 1 ? ? ? ? ?r2 ? ? 1? ? ? ? r5 ? r4 ? r0 ? ? s0 ? r1 ? ? ?r ? ? 0?C1?n ? m1?kG k ?nG k?n ? ?I k Q k?r ?G S ? ?I k Q k ?r ? Q k ?r ? (Pr?k )T(8.6.1)(8.6.2)H S ? ?Pr?k I r ?或 (Q k ?r )T ? Pr?kSong Peng返回目录Department of Electronics and Information, NCUT第75页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(2) 用 k 级移位寄存器的伴随式计算电路? 定理8.6.1：二元线性系统码中，接收矢量 R 的伴随式 S 等于对 R的信息部分所计算的监督位（相当于对 R 的信息部分重新编码）与接收的监督位的矢量和。 [证明]：? 设接收矢量 R=(RI RP)? RI 是 R 的信息部分，长度为 k 的矢量 ? RP 是 R 的监督位部分，长为 r=(n－k) 的矢量 ? 监督矩阵为 Hr×n=(Pr×k Ir)Department of Electronics and Information, NCUTSong Peng第76页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(2) 用 k 级移位寄存器的伴随式计算电路? 定理8.6.1：二元线性系统码中，接收矢量 R 的伴随式 S 等于对 R的信息部分所计算的监督位（相当于对 R 的信息部分重新编码）与接收的监督位的矢量和。 S1?r ? R1?n ?H T ?n?r [证明]：? 由伴随式的定义：? R I1?k R P1?r ?Pr?k I r ? ? R I1?k R P1?rT????? ?? PT ? ? I ? rk ?r? R I1?k ? P T ? R I1?kT? ? ? ?P ?? ? ? ?k ?r k ?r? R P1?r ? I r ? R P1?r返回? R I1?k ?Q k?r ? R P1?r把 R I 作信息元重新编码计算 的监督元。Department of Electronics and Information, NCUT Song PengT 到 ( ? 注意： Pr ?k 是H 阵除单位子阵外的 r ? k )阶子阵，所以R I1?k P? ?k ?r是第77页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码G k ?n?1 ?0 ?? ?? ? ?0 ?0 ? 0 1 ? 0 ? ? ? 0 ? 1q11 q21 ? qk 1q12 q22 ? qk 2? q1( n? k ) ? ? q2 ( n ? k ) ? ? ? ?I k ? ? ? ? ? qk ( n ? k ) ? ?Q k ?r ?(8.6.3)将上式代入C 1?n ? (cn ?1 , cn ? 2 , ? , c0 ) ? ( m k ?1 , m k ? 2 , ? , m0 )G k ?n ,得： ? mk ? i i ? 1,2, ? , k ?cn ? i ? ?cn ? ( k ? j ) ? m k ?1q1 j ? m k ? 2 q2 j ? ? ? m0 qkj j ? 1,2, ? , n ? k? q11 ? c n ? k ?1 ? ? ? ? ? q21 ? cn? k ? 2 ? ? ? ? ? ?mk ?1 mk ? 2 ? m0 ?? ? ? ? ? ?c ? ?q ? 0 ? ? k1 ? ?mk ?1 mk ? 2 ? m0 ?Q k ?r q12 q22 ? qk 2 ? q1( n? k ) ? ? ? q2 ( n ? k ) ? ? ? ? ? ? qk ( n ? k ) ? ?(8.6.4)参见? ?mk ?1 mk ? 2 ? m0 ?PkT r ?Song Peng 第78页Department of Electronics and Information, NCUT9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(2) 用 k 级移位寄存器的伴随式计算电路? 电路的工作步骤? 门1通，门2、3、4关，接收字R 的 k 位信息部分输入编码器；? 门1关，门2、3、4通，接收信息编码所得的监督位与接收监督位逐位模2和，得到伴随式。但这种伴随式计算方法只适用于线性系统码。门2门 1k 级编码器门4接收字输入门 3输出图8.6.2 用k级移位寄存器的伴随式计算电路返回目录Department of Electronics and Information, NCUTSong Peng第79页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(3) 用 (n－k) 级移位寄存器的伴随式计算电路? 设接收多项式为R(x)，它的信息部分表示为RI(x)，监督部分表示为RP(x);? 由定理8.6.1知 S(x)=r'(x)+RP(x)，其中 r'(x) 是对 RI(x) 重新编码的监督位多项式；? 若码的生成多项式为：g(x)，则：r'(x)≡RI(x)（mod g(x)）C(x)= xn－km(x)+q(x)=a(x)g(x)≡0（mod g(x)） q(x)=C(x)+ xn－km(x)≡xn－km(x)（mod g(x)）? 又因为：??RP ( x) ? ??g( x)，所以：S ( x ) ? RI ( x ) ? RP ( x) ? R( x )（modg( x ) ）(8.6.5)? 循环码接收多项式的伴随式是接收多项式 R(x) 除以 g(x) 的余式。Department of Electronics and Information, NCUT Song Peng 第80页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(3) 用 (n－k) 级移位寄存器的伴随式计算电路? 设：E(x) 为 R(x) 的错误图样，那么 R(x)=C(x)+E(x)，由于 C(x)为g(x) 的倍式，所以：S(x)≡C(x)+E(x)≡E(x) (mod g(x))? 上式表明：伴随式是由错误图样决定的，与具体码字无关。? 说明：循环码伴随式的表示式 (8.6.5) 是由系统码推出的，但由于伴随式仅与错误图样有关，因而对非系统码也是适用的。Department of Electronics and Information, NCUTSong Peng第81页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(3) 用 (n－k) 级移位寄存器的伴随式计算电路? 由式 (8.6.5) 可画出用 (n－k) 级移位寄存器计算循环码伴随式的电路，如图所示。门 1控制g1g2gn－k－1D0D1D2Dn-k-1接收字输入门 2伴随式输出控制图8.6.3 (n－k)级移位寄存器的伴随式计算电路? 这是一个 (n－k) 级除法求余电路，它与编码除法电路的区别是：由于被除式 R(x)不含 x 的幂的因子，所以接收矢量（被除式）应由第 一级前加入。Department of Electronics and Information, NCUT Song Peng返回目录第82页9.6.1 接收矢量伴随式计算9.6 循 环 码 的 译 码(4) 接收字循环移位的伴随式与伴随式循环移位的关系定理8.6.2：设 S(x) 为接收矢量 R(x) 的伴随式，则 R(x) 的循环移位 xR(x) (mod (xn+1) ) 的伴随式 S(1)(x) 等于伴随式 S(x) 的循环移位 xS(x) (mod g(x) )，即： S(1)(x)≡xS(x)（mod g(x)）[证明]：? 由伴随式计算式(8.6.5)知：S(x)≡R(x)（mod g(x)） ? 对上式两边作同余运算得：xS(x)≡xR(x)（mod g(x)）(8.6.6)? 令：R(1)(x)≡xR(x)（mod (xn+1) ）(8.6.7)? 即用 R(1)(x) 表示 R(x) 循环移位一次（mod (xn+1) ）的码多项式。Department of Electronics and Information, NCUTSong Peng第83页8.6.1 接收矢量伴随式计算8.6 循 环 码 的 译 码(4) 接收字循环移位的伴随式与伴随式循环移位的关系定理8.6.2：设 S(x) 为接收矢量 R(x) 的伴随式，则 R(x) 的循环移位 xR(x) (mod (xn+1) ) 的伴随式 S(1)(x) 等于伴随式 S(x) 的循环移位 xS(x) (mod g(x) )，即： S(1)(x)≡xS(x)（mod g(x)）[证明]：? 对式 (8.6.7) 进行模 g(x) 运算，得到 R(x) 循环移位 xR(x) 的伴随式： xS ( x) ? xR( x)（ modg ( x)） (8.6.6) (1)S (x)≡xR(x)（mod g(x)）? 考虑到式(8.6.6)，则有：S(1)(x)≡xS(x)（mod g(x)）R(1) ( x) ? xR( x)（mod(xn ? 1)） (8.6.7)? 上式说明：接收矢量的循环移位（mod (xn+1) 运算下）与伴随式在模g(x) 运算下（即在除以 g(x) 的伴随式计算电路中）的循环移位是一一对 应的。Department of Electronics and Information, NCUT Song Peng返回目录第84页9.6.2 循环码的通用译码法9.6 循 环 码 的 译 码(1) 循环码的译码器的组成（梅吉特译码法）? 循环码的译码基本上按线性分组码的译码步骤进行，不过由于码的循环移位特性使译码电路大为简化。? 通用的循环码译码器如图所示。反馈…伴随式寄存器…错误图样检测器 输入 输出缓冲寄存器 图8.6.4 循环码通用译码器返回Department of Electronics and Information, NCUTSong Peng第85页9.6.2 循环码的通用译码法9.6 循 环 码 的 译 码(1) 循环码的译码器的组成（梅吉特译码法）? 循环码通用译码器三个组成部分① 伴随式计算电路：可根据实际情况选取不同的伴随式电路。② 错误图样检测器：是一个组合逻辑电路，其作用是将伴随式译 为错误图样。它的工作原理为： 当且仅当错误图样是一个可纠的错误图样，并且此错误图样包含最高阶位上的一个错误时，伴随式计算电路计算得到的伴 随式才使检测电路输出为“1”。? 即如果错误图样检测器输出为“1”，则认为最高阶位上接收符号是错误的，应该给以纠正；? 即如果检测器输出为“0”，则认为最高阶位上接收符号是正确的，不必纠正。Department of Electronics and Information, NCUT Song Peng 第86页9.6.2 循环码的通用译码法9.6 循 环 码 的 译 码(1) 循环码的译码器的组成（梅吉特译码法）? 循环码通用译码器三个组成部分① 伴随式计算电路：可根据实际情况选取不同的伴随式电路。② 错误图样检测器：是一个组合逻辑电路，其作用是将伴随式译 为错误图样。它的工作原理为： 对于码组中任何位置上的错误，通过码组和伴随式同时循环移位，当错误符号移到最高阶位上时，伴随式则使检测器输出 为“1” ，将其错误纠正。 通过循环移位后，能使可纠错误图样中的全部错误都得到纠正。 ③ 接收矢量缓存器和模 2和纠错电路。Song Peng 第87页Department of Electronics and Information, NCUT9.6.2 循环码的通用译码法9.6 循 环 码 的 译 码(2) 循环码译码电路工作过程时将接收矢量移入缓存器。参见图? 将接收矢量移入伴随式计算电路，计算出伴随式；同? 伴随式写入错误图样检测器，并在检测器中循环移位(mod g(x))，同时将接收矢量移出缓存器。? 当检测器输出“1”时，表示缓存器此时输出符号是错误的，并将错误纠正；同时检测器输出反馈到伴随式计算电路的输入端，去修改伴随式，从而消除错误对伴随式所产生的影响。Department of Electronics and Information, NCUT Song Peng 第88页9.6.2 循环码的通用译码法9.6 循 环 码 的 译 码(2) 循环码译码电路工作过程参见图? 直到接收矢量全部移出缓存器，该接收矢量纠错完毕。? 若最后伴随式寄存器中为全“0”，则表示错误全部被纠正，否则检出了不可纠的错误图样。 说明：随着码长 n 和纠错能力 t 的增加，错误图样检测器 的组合逻辑电路变得很复杂，甚至难以实现。返回目录Department of Electronics and Information, NCUTSong Peng第89页9.7 循环汉明码(1) 循环汉明码的性能 (2) (7,4)循环汉明码的译码 (3) (15,11)循环汉明码的译码Department of Electronics and Information, NCUTSong Peng第90页9.7 循环汉明码(1) 循环汉明码的性能? 既约多项式：设 f(x) 是次数大于零的多项式，若除了常数和常数与本身的乘积以外，再不能被域 Fp 上的其它多项式除尽，则称 f(x)为域 Fp 上的既约多项式。? 本原多项式：GF(2)上的 m 次既约多项式有两大类。一类是能够被(xn+1) 整除，但不能被(xs+1) 整除（n=2m－1,s&n），它的根是GF(2m) 扩域中的本原元素，这一类称为本原多项式。另一类多项 式，它不仅能被 (xn+1) 整除，也能整除(xs+1)，它的根不是扩域GF(2m) 中的本原元素，称这类既约多项式为非原多项式。? 循环汉明码：以 m (n= 2m－1) 次本原多项式为生成多项式的循环码，称为循环汉明码。Department of Electronics and Information, NCUT Song Peng 第91页9.7 循环汉明码(1) 循环汉明码的性能? 循环汉明码的参数? 码长：? 监督位数：n= 2m－1n－k = m= g(x) 的次数? 信息元数目：k= 2m－m－1? 码的最小距离： dmin=3(t=1)Department of Electronics and Information, NCUTSong Peng第92页9.7 循环汉明码(1) 循环汉明码的性能? 汉明码的纠错能力? 以 g(x)=x3+x+1 为例，m=3, n=7, k=4? 该码的监督矩阵为：?1 1 1 0 1 0 0? H ? ?0 1 1 1 0 1 0 ? ? ? ?1 1 0 1 0 0 1? ? ?? H 矩阵共有 n= 2m－1 列，每列都是 m 维向量，但没有全 0 的列，而且各列均不相同。? H 矩阵中已包含了所有的 (2m－1) 个非 0 列，它们任意两列之和不为 0，而三列之和可以为 0。说明由 H 矩阵所确定的循环汉 明码的最小距离为 3，可以纠正一个随机错误。Department of Electronics and Information, NCUT Song Peng 第93页9.7 循环汉明码(1) 循环汉明码的性能? 汉明码是完备码，因而是高效码。? 在构造汉明码时，只要选择不同的本原多项式（可查表）作为生成多项式，就可以得到不同的 (n,k) 循环汉明码。 例如 (7,4)、(15,11)、(31,26) 等等。? 循环汉明码的编码、译码与一般循环码相同。不过由于它是纠正一个错误的循环码，所以译码电路特别简单。返回目录Department of Electronics and Information, NCUTSong Peng第94页9.7 循环汉明码(2) (7,4)循环汉明码的译码? (7,4)循环码是纠一个错误的循环汉明码；? 由于码字和伴随式的循环移位特性，可将译码电路设计成纠正最高阶位上的一个错误；? 当实际错误不在最高阶而在其它位上时，接收矢量和伴随式（在 g(x) 除法运算电路中）同时进行移位，一旦 错误到达最高阶位上，就将产生确定的伴随式；? 只需要一个简单的组合逻辑电路对这一确定的伴随式进行检测就可完成纠错。Department of Electronics and Information, NCUT Song Peng 第95页9.7 循环汉明码(2) (7,4)循环汉明码的译码? 由 g(x)=x3+x+1 生成的 (7,4) 循环汉明码的译码电路如图所示。R(x)D0 D1 D2门控制信号 门 门 门D0D1D2输出7级移位寄存器返回图8.7.1 (7,4)循环码的译码电路Department of Electronics and Information, NCUTSong Peng第96页9.7 循环汉明码(2) (7,4)循环汉明码的译码? (7,4) 循环汉明码的译码电路工作过程① 接收矢量送入伴随式计算电路，经 7 次移位得到伴随式，同时接收矢量移入缓存器； ② 将前一步所计算的伴随式转入伴随式自发运算电路，当错误恰好在最高阶位上时，伴随式为 (101)，与门检测此状态并输出“1”，而当最高阶位移出缓存器时即被纠正；若错误不在最高阶位上而 在其它位上，比如在 x4 位上时，错误图样经过两次移位变成x2?x4=x6，经两次移位后的伴随式为 S2(x)=x2+1(mod g(x))，检测到此状态时与门输出“1”，而对应的接收符号也正好移到最高阶位 上，因而错误得到纠正；x6 ? x2 ?1 x3 ? x ? 1Song Peng参见图Department of Electronics and Information, NCUT第97页9.7 循环汉明码(2) (7,4)循环汉明码的译码? (7,4) 循环汉明码的译码电路工作过程③ 当接收矢量全部移出缓存器后，完成一个码组的译码。在接收矢量开始移出缓存器时，下一个接收矢量紧跟着移入伴随式计算 电路和缓存器，重复第②步的的过程，可实现连续对接收矢量进行纠错。参见图返回目录Department of Electronics and Information, NCUTSong Peng第98页9.7 循环汉明码(3) (15,11) 循环汉明码译码电路设计? 设计由 g(x)=x4+x+1 生成的 (15,11) 循环汉明码的译码电路；? (15,11) 循环汉明码是纠一个错误的循环汉明码，所以把译码器设计成纠正最高阶位 x14 上的一个错误；? 错误图样 x14 的伴随式为 S(x)≡x14≡x3+1（mod g(x)），因而伴随式输出状态为 (1001) 时，应使错误图样检测器输出“1”。Department of Electronics and Information, NCUTSong Peng第99页9.7 循环汉明码(3) (15,11) 循环汉明码译码电路设计? (15,11) 循环汉明码的译码电路如图8.7.2所示。输入 15级移位寄存器门输出D0D1D2D3E 组合逻辑电路图8.7.2 (15,11)循环码译码电路Department of Electronics and Information, NCUTSong Peng第100页9.7 循环汉明码(3) (15,11) 循环汉明码译码电路设计? 电路说明：工作原理与 (7,4) 循环汉明码译码电路的工作原理相同。但未加自发运算电路，在每接收完一个接收矢量后,伴随式还需要在伴随式计算电路循环一周， 以纠正所有码元位上可能的错误。所以这种电路所需译 码时间较长，不能进行连续译码。采用哪种形式的电路 要由信号的要求来决定。返回目录Department of Electronics and Information, NCUTSong Peng第101页9.8 缩短循环码(1) 为什么要用缩短循环码 (2) 缩短循环码的构造 (3) 缩短循环码的性能 (4) 举例Department of Electronics and Information, NCUTSong Peng第102页9.8 缩短循环码(1) 为什么要用缩短循环码在系统设计中，如果不能找到一种合适自然长度或合适信息位数目的码，则需要将码组缩短，以满足系统的要求。(2) 缩短循环码的构造将码组缩短的基本方法：设法使满足前面若干个码元符号为 0，且不发送这些符号。对 (n,k) 系统循环码，只要令前 l 个信息位为0 (l&k)，就可将 (n,k) 循环码缩短为 (n－l,k－l) 线性码。称这种码组长度缩短了的循环码为缩短循环码。返回目录Department of Electronics and Information, NCUTSong Peng第103页9.8 缩短循环码(3) 缩短循环码的性能? 一般情况下，删去前 l 个 0 之后的缩短码，就失去了循环特性。在纠错能力上缩短码至少与原码相同。? 由于删去前面 l 个 0 信息元并不影响监督位和伴随式的计算，可用原循环码的编译码电路来完成缩短码的编译码。? 若用原循环码译码电路来译缩短循环码，则应修改错误图样检测电路，使原来对包含最高阶位 xn－1上的一个错误图样进行检测，修改为对包含xn －l－1 位上的一个错误图样进行检测。? 错误图样检测电路的输出是和包含 xn－l－1 位上的错误相对应的，即当xn－l－1 位上的接收符号是错误的时，检测电路输出为“1”，否则为“0”。? 当 xn－l－1 位上错误被纠正时，还应消除 en－l－1 对伴随式的影响。在检测到 xn－l－1 位上有错时,将 g(x) 除 xn－l－1 的余式加入此时的伴随式即可消除。Department of Electronics and Information, NCUT Song Peng返回目录第104页9.8 缩短循环码(4) 举例：设计(15,11)循环码的缩短码 (8,4) 码的译码器。[解]： (15,11) 循环汉明码是纠一个错误的码，它的 (8,4) 缩短码译码电路如图所示。输入 输出 8 级移位寄存器D0D1D2D3E 组合逻辑电路 图8.8.1 (8,4)循环码译码电路Department of Electronics and Information, NCUTSong Peng第105页9.8 缩短循环码(4) 举例：设计(15,11)循环码的缩短码 (8,4) 码的译码器。图中包含三个部分：?八位缓冲移位寄存器；?由本原多项式 g(x)=x4+x+1 决定的伴随式计算电路。 ?当 x7 位上发生错误时的错误图样检测电路。错误图样 x7 的伴随式为：S(x)≡x7≡x3+x+1 (mod g(x))，当伴随式输出状态为 (1011) 时，检测电路 应输出“1”。注：随着码长 n 和纠错能力 t 的增加，错误图样检测器的组合逻辑电路变得很复杂，甚至难以实现。但纠单个错误的循环汉明码，译码器中的 组合逻辑电路却很简单，因而汉明码在实际中得到了广泛的应用。返回目录Department of Electronics and Information, NCUTSong Peng第106页9.9 循环码的其它译码方法? 循环码的捕错译码 ? 一般适用于短码或低码率的译码；? 用于纠突发错误的译码是很有效的。? 循环码的大数逻辑译码? 从码的结构出发，可导出大数逻辑译码法；? 具有译码设备简单、速度快的优点，因而应用相当广泛。返回目录Department of Electronics and Information, NCUTSong Peng第107页9.10 BCH 码和 RS 码? BCH码：由 Hocgenghem 和 Bose 及 Chaudhuri 分别提出的纠正多个随机错误的循环码。? 多元BCH码：多元 BCH 码的生成多项式是以 GF(q)的扩域GF(qr)上的元素为根的多项式。? RS码：当 r=1 时的 q 元 BCH 码是多元 BCH 码的特殊子类,称为 Reed-Solomon码，简称 RS 码。Department of Electronics and Information, NCUTSong Peng第108页Department of Electronics and Information, NCUTSong Peng第109页
信息论与编码原理―汇集和整理大量word文档,专业文献,应用文书,考试资料,教学教材,办公文档,教程攻略,文档搜索下载下载,拥有海量中文文档库,关注高价值的实用信息,我们一直在努力,争取提供更多下载资源。}