通信原理-chapter9.part第九章差错控制编码

ErrorControl 特别感谢 教1PreviouslyonPrinciplesof

）‘信道编码’在系统中的位置(对比sourcecoding去冗余分类：分组码，卷积码2PreviouslyonPrinciplesofFEC参数(nk,k信息码元数量r—差错控制(冗余)码元数量n—k+kn—编码效率（码速Codekn 码重：非零码元的数 码距：两个等长码组之间相应位取值不同的3PreviouslyonPrinciplesof最小码距d0：决定分组码的纠错和检错能力纠纠错：d0≥2t+1检错：d0≥e1纠检结合：d0≥te+14LinearBlock59.3.0线性分组码(nkr):线性：其监督位r和信息位k的关系由线性代数方程决定例：码(n,n-A1

12[an1,an2, a12k线性线性分组码性质MinimumDistance等价于MinimumWeight（证明稍后）‘最小码距’不易求 0例，(7，43)线性分组码，7个码 0输出码元里面含有信息码的称为：系统码Systematic监督码元：线性组合（仅限于模二和）7例，这种线性生成关系为（可随意设计，但BER性能会不同a2a6a5aa

a3a0a6a4a3写成矩阵形

111110a2a1a0a6a5a4a3 101 011 Q矩阵Q：监督位的生成关 0001G a6a5

a3

a1

a6a5a4AA1k 具有[IkQ]形式典型生成矩阵Generatormatrix:唯一的n[IkQkr910001111000111010011000101010001 IkQ011a6a5

a3

a1

a6a5a4生成矩

Gk

[IkQkr‘各行’独立：单独每个信息位的检校位，其他 可以通它组合（告诉我们单独每个字母怎么用，就可以组合所有反之，如果有k个‘独立’的码组，则有生成矩阵G 接收端检测方法：再编码一次应该有a6a5a4a3a2a1再编码一次a2a6a5a4a a 即

S1a6a5a4a2 aaaa

a6

a3a0检校子 S1a6a5a4a2 aaaa

a6a4a3a0写成矩阵形

a6a a 50a4

0 0a0 3

1a2 a1A1A1 nHT01

S检校矩阵检校矩阵 0 0r r

或者接收码字A无错条件：H矩阵与码字A的转置乘积为零 rrHnHnIra6a 10100 5a40 01010a0 3 11001a2 a1右边点乘：对一个矩阵的列操监督矩阵性质P为rk阶矩阵；Irrr阶单位方阵；将具有[PIr形式的H矩称为典型监督矩阵H矩阵的各行应该是线性‘独立’G和H 在都写成‘典型矩阵’的条件

a6a5

a3

a1

a6a5a4

PTQGPTQ

Gk

[IkQk r接收

a6a a11010110100a40101010a0 3

r [ I H

1a2 a1

S

写成此形式，对应硬件实现。其实两者本质相同 MinimumWeight==Minimum封封闭性：若A1和A2是一种线性码中的两个码组，则(A1+A2)[证

若A1和A2是两个码组，则有：A1HT=两式相加A1HTA2HT(A1A2HT

A2HT=所以，(A1A2)也是一个码 那么，A1和A2距离（,）是另一个码组(A1+A2)的重量（即“1）。因此，线性码的最小距离就是码（全“0”码组除外）的最小重量样我们知道，传输正确S1a6a5a4a2 aaaa

a6a4a3a0AAT1 nH01

有错误发生（假设只有一位错误发生）如

S1a6a5a4a2 aaaa

a6

a3a0（6430）都是对的因此，是a5错了；下表列出所有可S1S2S1S2无错样 给出‘错误图样’，等价于给出‘监督矩阵（生成矩阵样S1S2S1S2无错例，当S1=1时，与a2a4a5a6有关S1a6a5a4a2 aaaa

a6a4a3a0发送码组A是一个n列的行矩Aan1an2a1a0接收码组B是一个n列的行矩B=A+E就是错码的行矩 若接收码组中无错码BHT=BHT=BHT=SST1S2 r当接收码组有错时（在未超过检错能力时校正子S和错误图样E之间有确定的一一对应线性变换关S1S1S2S1S2无错汉明要求：能‘纠正’任意一个错码的线性分组码2r1n 例 称此分组码(n,k)为能纠t=1个错误的‘完备推广：能纠任意2个错误的‘完备码’条件2r2r1C1nn汉明码的码率k1rnn当n很大时，上式趋近于1。所以汉明码是一纠正t=1个随机错误，则汉明码的 检错能力 可知，可知，此码能够检测2个错码，或纠正1个错码 【例】已知（7，3，4）分组码的监督关系a6a3a2a1 a a a1 aa

a a 求其监督矩阵、生成矩阵、全部9.3.29.3.2线性分组码例监督关系 写成监督矩阵

a6a

1001110

5

a4 0a

a

a

0100111

a

0 1100010

3 a6a5a1

a2

0110001 a

1

（检校矩阵写成‘典型监督矩1001110 101 10000100111 111 0100H 1100010 110 0010

（码字 [PIr9.3.2线性分组码 生成矩阵满足关系

a6a5a4a3a2a1其中，Q

a6a5a4[Ik生成矩阵

100 1110 G[IPT] 0011101（7，3）分组码的全部码字如下表所码码1最小码距d0=4，可纠错119.3.3—循环码 组循环一位后仍然是该编码中的一个码组主要用于【例】：一种(7,3，4)循环码的全部码组码码码15263748—若(an-1an-2…a0)是循环码的一个码组，则循环移位后的码左循环2…

(an-2an-3…a0an-1)(an-3an-4…an-1an-左循环n-1位(a0an-1a2仍是可用码组注注：一种循环码可能有多个循环分组，只在每个分组内满足循环—单码.循环码的多项式表示法(为何用多项式，而不用生成矩TT(x)xn1xn2ax10例：码组1100101可以表示T(x)1x61x50x40x31x20xx6x5x2多项式乘法，左移“i”xiT(x)右侧添加i个 9.3.3—多项式除法，右移“i”位（码分为2部分，放在商和余项里T(例，右移“i=3x4x21(10101)

商Nx余数R

x2

x21TTxR 模—循环码 组循环一位后仍然是该编码中的一个码组这件事情用多项式描设T(x)是一个长度为n的码则，循环左移‘i’位之后T(x)也是一个码组xxiT(x)T 模xn—xxiT(x)T 模xn【例】一循环码（n=4）abcd，求循环左