信息论第六章 信道编码(2)

1、第六章信道编码思维世界的发展，在某种意义上说，就是对惊奇的不断摆脱。-爱因斯坦（美国）第六章信道编码6.2.16.2.26.2.36.2.46.2.56.2.66.2.76.2.86.2.96.2.10一般概念一致监督方程和一致监督矩阵线性分组码的生成矩阵线性分组码的编码线性分组码的最小距离、检错和纠错能力线性分组码的译码线性分组码的性能汉明码由已知码构造新码的方法线性分组码的码限6.2 线性分组码第六章信道编码线性分组码的编码：线性分组码的编码过程分为两步：把信息序列按一定长度分成若干信息码组，每组由 k 位组成；编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成 n 重 (n

2、k) 码字，其中 (nk) 个附加码元是由信息码元的线性运算产生的。信息码组长 k 位，有 2k 个不同的信息码组，则有 2k 个码字与它们一一对应。6.2.1 一般概念6.2线性分组码第六章信道编码名词解释线性分组码：通过预定的线性运算将长为 k 位的信息码组变换成 n 重的码字 (nk)。由 2k 个信息码组所编成的 2k个码字集合，称为线性分组码。码矢：一个 n 重的码字可以用矢量来表示C=(Cn1,Cn2,C1,C0 )所以码字又称为码矢。(n,k) 线性码：信息位长为 k，码长为 n 的线性码。编码效率/编码速率/码率/传信率：R=k /n。它说明了信道的利用效率，R是衡量码性能的一

3、个重要参数。6.2.1 一般概念6.2线性分组码第六章信道编码(1) 一致监督方程编码就是给已知信息码组按预定规则添加监督码元，以构成码字。在 k 个信息码元之后附加 r(r=nk) 个监督码元，使每个监督元是其中某些信息元的模2和。举例：k=3, r=4，构成 (7,3) 线性分组码。设码字为(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”监督元可按下面方程组计算6.2.2 一致监督方程和一致监督矩阵6.2线性分组码(6.2.1)3642654165054c= c+ cc= c+ c+ cc= c+ cc=c+ c

4、第六章信道编码一致监督方程/一致校验方程：确定由信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所 有 码 字 都 按 同 一 规则确定，又称为一致监督方程/一致校验方程。由于一致监督方程是线性的，即监督元和新信源之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。6.2线性分组码6.2.2 一致监督方程和一致监督矩阵信息组对应码字00000000000010011101010010011101101110101001001110101101001111011010011111110100第六章信道编码(2) 举例信息码组 (101)，即C6=1, C5=0, C4=1

5、代入 (6.2.1) 得： C3=0, C2=0, C1=1, C0=1由信息码组 (101) 编出的码字为(1010011)。其它7个码字如表6.2.1。表 6.2.1(7,3)分组码编码表6.2线性分组码6.2.2 一致监督方程和一致监督矩阵(6.2.1)3642654165054c= c+ cc= c+ c+ cc = c+ cc=c+ c1000000000000000006436546554ccc=ccc=ccc=ccc =第六章信道编码(3) 一致监督矩阵为了运算方便，将式(6.2.1)监督方程写成矩阵形式，得式(6.2.2)可写成H.CT=0T或C.HT=0CT、HT、0T分别表

6、示C、H、0的转置矩阵。6.2.2 一致监督方程和一致监督矩阵6.2线性分组码654321010110000111010001100010001100010ccccccc 654321000001 0 1 10001 1 1 01001 1 000100 1 1 0001cccccccc0H令I4 第六章信道编码系数矩阵 H 的后四列组成一个 (44) 阶单位子阵，用 I4表示，H 的其余部分用 P 表示(6.2.5)P43H( 7 ,3 ) P43 I4 所以6.2.2 一致监督方程和一致监督矩阵6.2线性分组码101111=1100111000010000100001第六章信道编码推广到一

7、般情况：对 (n,k) 线性分组码，每个码字中的r(r=nk) 个监督元与信息元之间的关系可由下面的线性方程组确定6.2.2 一致监督方程和一致监督矩阵6.2线性分组码(6.2.6)111122102112222011220hhh0hhh0hhh0nnnnnnrnrnrnCCCCCCCCC第六章信道编码令上式的系数矩阵为 H，码字行阵列为 C6.2.2 一致监督方程和一致监督矩阵6.2线性分组码或(6.2.8)式(6.2.6)可写成(6.2.7)C0 称H为(n, k )线性分组码的一致监督矩阵，简称监督矩阵。HrnC1n Cn 1 Cn 2111212122212nnrrrnhhhhhhhh

8、h11TTrnnrHC011TTnnrrCH0 第六章信道编码(4) 一致监督矩阵特性对H 各行实行初等变换，将后面 r 列化为单位子阵，于是得到下面矩阵，行变换所得方程组与原方程组同解。监督矩阵H 的标准形式：后面 r 列是一单位子阵的监督矩阵H。H 阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码元的模2和为0。6.2.2 一致监督方程和一致监督矩阵6.2线性分组码(6.2.9)Hr n111212122212100010001kkrrrkppppppppp 第六章信道编码H 的标准形式还说明了相应的监督元是由哪些信息元决定的。例如 (7,3) 码的H 阵的第一行为 (1011

9、000)，说明此码的第一个监督元等于第一个和第三个信息元的模2和，依此类推。H 阵的 r 行代表了 r 个监督方程，也表示由H 所 确 定的码字有 r 个监督元。为了得到确定的码，r 个监督方程（或H 阵的r 行）必须是线性独立的，这要求H 阵的秩为 r。若把H 阵化成标准形式，只要检查单位子阵的秩，就能方便地确定H 阵本身的秩。6.2线性分组码6.2.2 一致监督方程和一致监督矩阵第六章信道编码(1) 线性码的封闭性线性码的封闭性：线性码任意两个码字之和仍是一个码字。定理6.2.1：设二元线性分组码 CI (CI表示码字集合) 是由监督矩阵H所定义的，若 U 和 V 为其中的任意两个码字，则

10、 U+V 也是CI中的一个码字。证明：由于 U 和 V 是码 CI 中的两个码字，故有HUT=0T，HVT=0T那么 H(U+V)T T=H(UT+VT)=HUT+HVT=0T即 U+V 满足监督方程，所以 U+V 一定是一个码字。一个长为 n 的二元序列可以看作是GF(2)(二元域)上的 n 维线性空间中的一点。长为 n 的所有 2n 个矢量集合构成了GF(2)上的 n 维线性空间Vn。把线性码放入线性空间中进行研究，将使许多问题简化而比较容易解决。(n,k) 线性码是 n 维线性空间Vn中的一个 k 维子空间 Vk。6.2.3 线性分组码的生成矩阵6.2线性分组码第六章信道编码(2) 线性

11、分组码的生成矩阵在由 (n,k) 线性码构成的线性空间 Vn 的 k 维子空间中，一定存在 k 个线性独立的码字：g1,g2, gk,。码CI 中其它任何码字C都可以表示为这 k 个码字的一种6.2.3 线性分组码的生成矩阵6.2线性分组码G是一个k n阶矩阵。线性组合，即C mk-1g1 mk-2 g2 m0 gkmi GF (2), i 0,1, k 1。写成矩阵形式得m mk-1mk-2 m0 是待编码的信息组（6.2.10）(6.2.11)1211201nkkkk nkmmmggCmGg第六章信道编码G中每一行 gi=(gi1,gi2, gin ) 都是一个码字；对每一个信息组m，由矩

12、阵G都可以求得 (n,k) 线性码对应的码字。生成矩阵：由于矩阵 G 生成了 (n,k) 线性码，称矩阵 G 为 (n,k)线性码的生成矩阵。(n,k) 线性码的每一个码字都是生成矩阵 G 的行矢量的线性组合，所以它的 2k 个码字构成了由 G 的行张成的 n 维空间的一个 k 维子空间 Vk。6.2.3 线性分组码的生成矩阵6.2线性分组码(6.2.11)11112122122212nnk nkkkkngggggggggggGg 第六章信道编码线性系统分组码通过行初等变换，将 G 化为前 k 列是单位子阵的标准形式6.2.3 线性分组码的生成矩阵6.2线性分组码(6.2.13)(6.2.12

13、)j 1,2, n ki 1,2, , k, ,C0 ) (mk-1 , mk-2 , , m0 )Gk n ,得将上式代入C1n (Cn 1 , Cn 2 IkQ k r Gk n11121()21222()12()1 000 100 01n kn kkkk n kqqqqqqqqq()1 1220n ik inkjkjkjkjCmCm qmqm q第六章信道编码线性系统分组码：用标准生成矩阵 Gkn 编成的码字，前面 k位为信息数字，后面 r=nk 位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。当生成矩阵 G 确定之后，(n,k) 线性码也就完全被确定了，只要找到

14、码的生成矩阵，编码问题也同样被解决了。6.2线性分组码6.2.3 线性分组码的生成矩阵第六章信道编码(3) 举例6.2.3 线性分组码的生成矩阵6.2线性分组码 (1010011)C17 m14G47(7,4) 线性码的生成矩阵为G47 若m14 (1010)，则1 0 0 010 10 1 0 011 10 0 1 011 00 0 0 101 11 0 0 010 10 1 0 011 11 0 1 00 0 1 011 00 0 0 101 1 rTrkSrkkSkrTrkTkrrkrkrkTkrrTkrrkkTrkrrkkTSSrkrSrkkSI)Q(HQIGP)Q()P(Q0Q)P(

15、I)P(QIIPQIHGIPHQIG或所以，l由于生成矩阵由于生成矩阵GG的每一行都是一个码字，所以的每一行都是一个码字，所以G G 的每的每行都满足行都满足HHrnC CTn1=0 0Tr1，则有，则有HHrnGGTnk=0 0Trk 或或 GGknHHTnr=0 0krl线性系统码的监督矩阵线性系统码的监督矩阵 H H 和生成矩阵和生成矩阵 G G 之间可以直接之间可以直接互换互换。(4) 生成矩阵与一致监督矩阵的关系6.2.3 线性分组码的生成矩阵例例: 已知已知(7,4)线性系统码的监督矩阵为线性系统码的监督矩阵为1101000011010011100101010001G1001011

16、01011100010111H)4,7()4,7(阵可直接写出它的生成矩l对偶码对偶码：一个：一个(n,k)线性码线性码 C CI，如果以，如果以G G 作监督矩阵，作监督矩阵，而以而以H H 作生成矩阵，可构造另一个作生成矩阵，可构造另一个 (n,nk)线性码线性码C CId ，称码称码C CId为原码的对偶码。为原码的对偶码。l(7,3)码的监督矩阵码的监督矩阵HH(7,3)是是(7,4)码的生成矩阵码的生成矩阵GG(7,4) l(7,4) 码的监督矩阵码的监督矩阵 HH(7,4)是是(7,3) 码的生成矩阵码的生成矩阵 GG(7,3) 3 , 7()4 , 7(G101110011100

17、100111001100101101011100010111H标准形式)3 ,7()4,7(H10001100100011001011100011011101000011010011100101010001G标准形式l(n,k) 线性码的编码就是根据线性码的线性码的编码就是根据线性码的监督矩阵监督矩阵或或生成矩生成矩阵阵将长为将长为 k 的信息组变换成长为的信息组变换成长为 n(nk) 的码字的码字。l利用监督矩阵构造利用监督矩阵构造 (7,3) 线性分组码的编码电路：线性分组码的编码电路：l设码字矢量为设码字矢量为C C=(C6 C5C4C3C2C1C0)l码的监督矩阵为码的监督矩阵为线性分

18、组码的编码线性分组码的编码4505614562463)3,7(1000110010001100101110001101CCCCCCCCCCCCCTT得由0HCHl根据方程组可直接画出根据方程组可直接画出 (7,3) 码的并行和串行编码电路。码的并行和串行编码电路。m0m1m2C6C5C4C3C2C1C0C0C1C2C3C4C5C6mC(a)并行编码电路 （b）串行编码电路 (7,3)线性编码电路汉明距离、汉明重量和汉明球汉明距离、汉明重量和汉明球l汉明距离汉明距离：在：在 (n,k)线性码中，两个码字线性码中，两个码字 UU、V V 之间对应码之间对应码元位上符号取值不同的个数，称为码字元位上

19、符号取值不同的个数，称为码字 UU、V V 的汉明距离。的汉明距离。l例例：(7,3) 码的两个码字码的两个码字 UU=0011101,V V=0100111之间第之间第2、3、4和和6位不同。因此，码字位不同。因此，码字 U U 和和 V V 的距离为的距离为4。l线性分组码的一个码字对应于线性分组码的一个码字对应于 n 维线性空间中的一点，码维线性空间中的一点，码字间的距离即为空间中两字间的距离即为空间中两对应点的距离。因此，码字间的对应点的距离。因此，码字间的距离满足一般距离公理：距离满足一般距离公理：10)(),(niiivudVU线性分组码的最小距离、检错和纠错能力线性分组码的最小距

20、离、检错和纠错能力三角不等式对称性非负性),(),(),(),(),(0),(WUWVVUUVVUVUddddddl最小距离最小距离dmin：在：在 (n,k) 线性码的码字集合中，任意两个码字线性码的码字集合中，任意两个码字间距离的最小值，叫做码的最小距离。若间距离的最小值，叫做码的最小距离。若C C(i)和和C C(j) 是任意两是任意两个码字，则码的最小距离表示为个码字，则码的最小距离表示为 码的最小距离是衡量码的抗干扰能力（检、纠错能力）的码的最小距离是衡量码的抗干扰能力（检、纠错能力）的重要参数。码的最小距离越大，码的抗干扰能力就越强。重要参数。码的最小距离越大，码的抗干扰能力就越强

21、。l汉明球汉明球：以码字：以码字C C为中心，半径为为中心，半径为 t 的汉明球是与的汉明球是与 C C 的汉明的汉明距离距离 t 的向量全体集合的向量全体集合 S SC C(t) 任意两个汉明球不相交最大程度取决于任意两个码字之间任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离的最小汉明距离dmin。12 , 1 , 0,),(min)()(minkjijijiddCCtdt),()(RCRSC tVUdmindmin=5,码距和纠错能力关系示意图l汉明重量汉明重量W：码字中非：码字中非0码元符号的个数，称为该码字的汉码元符号的个数，称为该码字的汉明重量。明重量。l在二元线性

22、码中，码字重量就是码字中在二元线性码中，码字重量就是码字中“1”的个数。的个数。l最小重量最小重量Wmin ：线性分组码：线性分组码C CI中，非中，非0 0码字重量的最小码字重量的最小值，叫做码值，叫做码C CI的最小重量：的最小重量：Wmin =minW(V V),V VC CI ,V V0 0l最小距离与最小重量的关系最小距离与最小重量的关系：线性分组码的最小距离等于：线性分组码的最小距离等于它的最小重量。它的最小重量。 证明证明：设线性码设线性码C CI，且，且UUC CI, V VC CI，又设，又设UUV V=Z Z，由线性码的封闭性知，由线性码的封闭性知，Z ZC CI 。因此，

23、。因此，d(UU,V V)=W(Z Z)，由，由此可推知，线性分组码的最小距离必等于非此可推知，线性分组码的最小距离必等于非0 0码字的最小重码字的最小重量。量。第六章信道编码(2) 最小距离与检、纠错能力一般地说，线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。检错能力：如果一个线性码能检出长度l 个码元的任何错误图样，称码的检错能力为 l。纠错能力：如果线性码能纠正长度t 个码元的任 意 错误图样，称码的纠错能力为 t。6.2线性分组码6.2.5 线性分组码的最小距离、检错和纠错能力l最小距离与纠错能力最小距离与纠错能力：(n,k) 线性码能纠线性码能纠 t 个错

24、误的充要条件个错误的充要条件是码的最小距离为是码的最小距离为 证明证明： 设发送的码字为设发送的码字为V V；接收的码字为；接收的码字为R R；UU为任意其它码字；为任意其它码字； 则矢量则矢量V V、R R、UU间满足距离的三角不等式，间满足距离的三角不等式， d(R R,V V)+d(R R,UU)d(UU,V V) 又设信道干扰使码字中码元发生错误的实际个数为又设信道干扰使码字中码元发生错误的实际个数为 t，且，且tt d(R R,V V)tt 由于由于d(UU,V V)dmin=2t+1，代入上式得：，代入上式得： d(R R,UU) d(UU,V V)d(R R,V V)= 2t+1

25、tt 47 . 42112minmin的最大整数，例表示取实数其中或XXdttd第六章信道编码上式表明：如果接收字 R 中错误个数 tt，那么接收字 R 和发送字 V 间距离t ，而与其它任何码字间距离都大于 t，按最小距离译码把R译为V。此时译码正确，码字中的错误被纠正。几何意义：6.2.5 线性分组码的最小距离、检错和纠错能力6.2线性分组码tdmin图6.2.3 dmin=5,码距和纠错能力关系示意图l最小距离与检错能力最小距离与检错能力：(n,k) 线性码能够发现线性码能够发现 l 个错误的充个错误的充要条件是码的最小距离为要条件是码的最小距离为 dmin=l+1 或或 l=dmin1

26、 证明证明： 设发送的码字为设发送的码字为 V V；接收的码字为；接收的码字为 R R；U U 为任意其它码字；为任意其它码字； 则矢量则矢量V V、R R、UU间满足距离的三角不等式，间满足距离的三角不等式， d(R R,V V)+d(R R,UU)d(UU,V V) 又设信道干扰使码字中码元发生错误的实际个数为又设信道干扰使码字中码元发生错误的实际个数为 l，且，且ll d(R R,V V)ll 由于由于d(UU,V V)dmin=l+1，代入上式得：，代入上式得： d(R R,UU) d(UU,V V)d(R R,V V)=l+1l0第六章信道编码上式表明：由于接收字 R 与其它任何码字

27、 U 的距离都大于0，则说明接收字 R 不会因发生 l 个错误变为其它码字，因而必能发现错误。几何意义：6.2.5 线性分组码的最小距离、检错和纠错能力6.2线性分组码ldmin图6.2.4 dmin=4,码距和检错能力关系示意图第六章信道编码最小距离与检、纠错能力：(n,k) 线性码能纠 t 个错误，并能发现 l 个错误 (lt) 的充要条件是码的最小距离为dmin=t+l+1 或 t+l=dmin1 (6.2.23)证明：因为dmin2t+1，根据最小距离与纠错能力定理，该码可纠 t 个错误。因为dminl+1，根据最小距离与检错能力定理，该码有检 l 个错误的能力。纠错和检错不会发生混淆

28、：设发送码字为 V，接收字为 R，实际错误数为 l，且 tt+1t因而不会把 R 误纠为 U。6.2线性分组码6.2.5 线性分组码的最小距离、检错和纠错能力 几何意义几何意义：ldmindmin=5,t=1,l=3时码距和检错能力关系示意图tVUdminldmintdmintl最小码距与检纠错能力l当当 (n,k) 线性码的最小线性码的最小距离距离 dmin 给定后，可给定后，可按实际需要灵活安排按实际需要灵活安排纠错的数目。例如，纠错的数目。例如，对对 dmin=8 的码，可用的码，可用来纠来纠3检检4错，或纠错，或纠2检检5错，或纠错，或纠1检检6错，或错，或者只用于检者只用于检7个错误

29、。个错误。第六章信道编码(3) 线性码的最小距离与监督矩阵的关系定理6.2.2：设 H 为 (n,k) 线性码的一致监督矩阵，若H 中任意 S 列线性无关，而 H 中存在 (S+1) 列线性相关，则码的最小距离为 (S+1)。（矩阵 H 的秩为S）定理6.2.3：若码的最小距离为 (S+1)，则该码的监督矩阵的任意 S 列线性无关，而必存在有相关的 (S+1)列。定理6.2.4：在二元线性码的监督矩阵 H 中，如果任一列都不是全“0”，且任两列都不相等，则该码能纠一个错误。6.2线性分组码6.2.5 线性分组码的最小距离、检错和纠错能力第六章信道编码(1) 伴随式和错误检测 用监督矩阵编码，也

30、用监督矩阵译码：接收到一个接收字 R 后，校验 H.RT=0T 是否成立：若关系成立，则认为 R 是一个码字；否则判为码字在传输中发生了错误；H.RT的值是否为0是校验码字出错与否的依据。 伴随式/监督子/校验子：S=R.HT或ST=H.RT。 如何纠错？设发送码矢 C=(Cn1,Cn2,C0)信道错误图样为 E=(En1,En2,E0) ，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。i=n1,n2,0。6.2.6 线性分组码的译码6.2线性分组码l接收码字接收码字 R R =(Rn1,Rn2,R0)=C C+E E =(Cn1+En1, Cn2+En2, , C0 +E0)l求接收码字的伴随式（接收码字用监督矩阵进行检验）求接收码字的伴随式（接收码字用监督矩阵进行检验） S ST=