§6纠错码基本概念.ppt

§7 Cyclic codes Step: 1、 Computing the syndrome S by R 2、 getting E by S 3、 §7.2.2 Encoder for cyclic codes input m output V 1～k ticks k+1～n ticks D0 D1 Dr-1 g1 g2 gr-1 g0＝1 A B §7.2.2 Encoder for cyclic codes Example 7.2.2 Constructing encoder for (7,4)cyclic codes with generator polynomial g(x)= x3+ x+1. Let M=(1101)，V=? input m D0 D1 D2 Output V 1～4 ticks A B 5～7 ticks §7.2.2 Encoder for cyclic codes 0 0 0 0 0 0 1 2 3 4 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 1 5 6 7 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 M=(1101) D0 D1 D2 V 1～4 ticks A B 5～7 ticks M=(1101) D0 D1 D2 V 1～4 ticks A B 5～7 ticks § 7.2 Encoders for cyclic codes § 7.3 Decoders for cyclic codes § 7.1 Concept of cyclic codes §7.3 Decoders for cyclic codes 1. Syndrome for cyclic codes For systematic cyclic codes there exist that: Where, Example 7.3.1： (7,4)cyclic codes：g(x)=x3+x+1，and R=(0110100) ，S=? S=RHT S=RH0T S(x)=Rg(x) [R(x)] calculation circuit D0 D1 D2 R CP＝7，D0D1D2=101 §7.3 Decoders for cyclic codes 1. Syndrome for cyclic codes ＝（101） =x2+1 Theorem 7.3 For j≥0 define Sj(x) = [xjR(x)]n mod g(x), i.e., Sj(x) is the remainder syndrome of the jth cyclic shift of R(x). Then for j ≥ 0, Sj+1(x) = [xSj(x)] mod g(x). (p217 Theorem 8.15 in textbook) Let：R(x)=rn-1xn-1+ rn-2xn-2+…+ r1x+ r0 corresponding syndrome：S(x)=Rg(x)[R(x)] xjR(x)= R(j)(x)＋(rn-1xj-1+…+rn-j)(xn+1) Then：R（j）(x)＝xjR(x)＋(rn-1xj-1+…+rn-j)(xn+1) ＝xjR(x) mod g(x) ＝xjS(x) mod g(x) Sj(x)＝R（j）(x) mod g(x) ∴ Sj(x)＝xjS(x) mod g(x) S(x) R(x) Sj(x)=xjS(x) R(j)(x) §7.3 Decoders for cyclic codes Sj+1(x)=xSj (x) R(j+1)(x) Theorem 7.3 For j≥0 define Sj(x) = [xjR(x)]n mod g(x), i.e., Sj(x) is the remainder syndrome of the jth cyclic shift of R(x). Then for j ≥ 0, Sj+1(x) = [xSj(x)] mod g(x). S(x) E(x) Si(x)=xiS(x) E(i)(x) §7.3 Decoders for cycli