编码理论第3章

1、v分组码：分组码：将消息序列分组进行编码将消息序列分组进行编码v在分组码中，二元信息序列被分成长度固定的一在分组码中，二元信息序列被分成长度固定的一组组消息；每组组组消息；每组消息消息u有有k个信息位，共有个信息位，共有2k个不个不同的消息同的消息v编码器按照一定规则将每个输入消息编码器按照一定规则将每个输入消息u变换成二变换成二元元n重重v，nk，这个二元，这个二元n重重v称作消息称作消息u的的码字码字或码矢。所有或码矢。所有2k个码字组成的集合称作是分组码个码字组成的集合称作是分组码v线性分组码：线性分组码：具有线性性质的分组码具有线性性质的分组码v定义：定义：长为长为n，有，有2k个码字

2、的分组码，当且仅当个码字的分组码，当且仅当其其2k个码字构成个码字构成GF(2)上所有上所有n重矢量空间的一个重矢量空间的一个k维子空间时，称作维子空间时，称作线性线性(n,k)分组码分组码message（0 0 0 0）（1 0 0 0）（0 1 0 0）（1 1 0 0）（0 0 1 0）（1 0 1 0）（0 1 1 0）（1 1 1 0）（0 0 0 1）（1 0 0 1）（0 1 0 1）（1 1 0 1）（0 0 1 1）（0 1 1 1）（1 1 1 1）Code words（0 0 0 0 0 0 0）（1 1 0 1 0 0 0）（0 1 1 0 1 0 0）（1 0 1 1

3、 1 0 0）（1 1 1 0 0 1 0）（0 0 1 1 0 1 0）（1 0 0 0 1 1 0）（0 1 0 1 1 1 0）（1 0 1 0 0 0 1）（0 1 1 1 0 0 1）（1 1 0 0 1 0 1）（0 0 0 1 1 0 1）（0 1 0 0 0 1 1）（0 0 1 0 1 1 1）（1 1 1 1 1 1 1）v因为线性因为线性(n,k)分组码分组码C是一个是一个k维子空间，所以在码维子空间，所以在码C中中能找到能找到k个线性独立的码字个线性独立的码字g0, g1, gk-1,使得使得C中的每个中的每个码字码字v都是这都是这k个码字的一种线性组合，即个码字的一种

4、线性组合，即v=u0g0+u1g1+uk-1gk-1v将这将这k个线性独立的码字作为行，得到个线性独立的码字作为行，得到kn阶矩阵阶矩阵v此矩阵称为码此矩阵称为码C的的生成矩阵生成矩阵。线性线性(n,k)分组码任何分组码任何k个线个线性独立的码字都可以用来构成性独立的码字都可以用来构成码码C的生成矩阵的生成矩阵111110111110100100110nkkknnkggggggggggggGv如果本章如果本章PPT第第3页的表格所表示的线性分页的表格所表示的线性分组码，有如下的生成矩阵组码，有如下的生成矩阵10001010100111001011000010113210ggggG)000110

5、1(10113210ggggvv若若u=(1101)，则，则v线性系统分组码：线性系统分组码：若若(n,k)线性分组码线性分组码C的生成矩的生成矩阵形如阵形如G=P Ik( (或或G=Ik P) )，此时称，此时称C为线性系为线性系统分组码。此时，每个码字都可以被分成两个部统分组码。此时，每个码字都可以被分成两个部分，即消息部分和冗余部分分，即消息部分和冗余部分10000100001000011, 11 , 10 , 11, 221121, 111101, 00100110knkkkknknknkkppppppppppppIPgggGv关于线性系统分组码，对应于消息关于线性系统分组码，对应于消

6、息u=(u0, u1, uk-1)的码的码字是字是v=(v0, v1, vn-1)=uG=uP Ik，即，即 vn-k+i=ui , 0ik-1, vj=u0P0j+u1P1j+uk-1Pk-1j, 0jn-k-1 上面两个式子正好反映系统的组成特性，最后这上面两个式子正好反映系统的组成特性，最后这n-k个方个方程称为码程称为码C的的一致校验方程一致校验方程1000010000100001,1, 11 , 10 , 11, 221121, 111101, 00100110knkkkknknknkppppppppppppuuuGuvv定义：定义：与与(n,k)线性分组码线性分组码C的生成矩阵的生

7、成矩阵G相对应相对应有一个有一个(n-k)n阶矩阵阶矩阵H，它的，它的n-k个行是码个行是码C的的对偶空间的一组基底，该矩阵对偶空间的一组基底，该矩阵H称为码称为码C的的一致一致校验矩阵校验矩阵v因此，一个因此，一个n重重v是由是由G生成的码中的码字，当且生成的码中的码字，当且仅当仅当vHT=0v对偶码：对偶码：以以H为生成矩阵得到的为生成矩阵得到的(n,n-k)码称为码码称为码C的的对偶码对偶码，记为，记为Cdv若码若码C的生成矩阵具有系统形式的生成矩阵具有系统形式G=P Ik，则其，则其一致校验矩阵形如一致校验矩阵形如H=In-k PTv定理：定理：如果线性码如果线性码C是是H矩阵的零化空

8、间，矩阵的零化空间，则对每一个重量为则对每一个重量为w的码矢，的码矢，H中有相应中有相应的的w列线性相关。反之，列线性相关。反之，H中若有中若有w列线性列线性相关，那么就有相应的重量为相关，那么就有相应的重量为w的一个码的一个码矢矢0,12121niiiTnnThvhhhvvvvHv(7,4)线性码的生成矩阵和一致校验矩阵线性码的生成矩阵和一致校验矩阵100111001001110011101,1011000111010011000100110001HGv设设(n,k)线性分组码线性分组码C的生成矩阵为的生成矩阵为G，其校验矩，其校验矩阵为阵为H，令，令v=(v0, v1, vn-1)是经有扰

9、信道传送的是经有扰信道传送的码字，码字，r=(r0, r1, rn-1)是信道输出端的接收矢量。是信道输出端的接收矢量。称矢量和称矢量和e=v+r=( (e0, e1, en-1) )为为错误矢量错误矢量v伴随式：伴随式：当接收到当接收到r后，译码器计算下述后，译码器计算下述n-k重重S=rHT =(s0, s1, sn-k-1)，称，称S为为r的伴随式的伴随式v当且仅当是一个码字当且仅当是一个码字(即无传输错误即无传输错误)时有时有S=0，否则错误矢量本身就是一个码字，此时出现了不否则错误矢量本身就是一个码字，此时出现了不可检错误。只要码可检错误。只要码C设计适当，就几乎不会出现设计适当，就

10、几乎不会出现不可检错误。不可检错误。v根据根据伴随式定义，伴随式定义， S=rHT =(v+e)HT=vHT+eHT=eHT，展开后，有，展开后，有v从上式容易看出，从上式容易看出，伴随式是错误图样的组合伴随式是错误图样的组合，即伴随式包含了一定程度的错误图样信息，因即伴随式包含了一定程度的错误图样信息，因而可以用来纠错而可以用来纠错伴随式纠错伴随式纠错1, 111, 111,0111 , 1111101110, 111010000knknknknknknknknknknknknknknpepepeespepepeespepepeesv上述方程有上述方程有2k个解，即，对同一个伴随式，个解，即

11、，对同一个伴随式，存在存在2k个可能的错误图样，因此上述方程个可能的错误图样，因此上述方程虽然包含错误图样的信息，但是实际应用虽然包含错误图样的信息，但是实际应用起来纠错困难。实际中的纠错，都是如何起来纠错困难。实际中的纠错，都是如何有效地从这些错误图样中选取真正的错误有效地从这些错误图样中选取真正的错误图样，从而得到正确的发送矢量。图样，从而得到正确的发送矢量。对于对于BSC信道，最可能的错误图样是非零数字信道，最可能的错误图样是非零数字最少的那个最少的那个v考虑某考虑某(7,4)码，令码，令v=(1001011)是发送码字，是发送码字，r=(1001001)是接收矢量，收到是接收矢量，收到

12、r后首先计算后首先计算S=rHT =(111)，由伴随式和错误图样的关，由伴随式和错误图样的关系方程有：系方程有：1=e0+e3+e5+e6, 1=e1+e3+e4+e5, 1=e2+e4+e5+e6, 则得到则得到24=16个错误图样个错误图样(0000010), (1010011), (0111011),其中其中(0000010)是非零分量最少的图样，考虑是非零分量最少的图样，考虑BSC信道，则信道，则(0000010)是最为可能的错误是最为可能的错误矢量，因而确定矢量，因而确定v=r+e=(1001001)+ (0000010)=(1001011)v汉明重量：汉明重量：令令v=(v0,

13、v1, vn-1)是二元是二元n重，重，v的汉明重量的汉明重量w(v)定义为定义为v中非零分量的个中非零分量的个数数v汉明距离汉明距离：令令u=(u0, u1, un-1)和和v=(v0, v1, vn-1)是两个二元是两个二元n重，重，u和和v之间的汉之间的汉明距离明距离d(u, v)定义为定义为u+v的汉明重量。的汉明重量。v汉明距离的性质：汉明距离的性质：1)非负性，非负性，d(u, v)0；2) d(u, v)=0，当且仅当，当且仅当u=v的时候；的时候；3)对称性：对称性： d(u, v) =d(v, u) ；4)三角不等式：三角不等式： d(u, v)+d(v, w)d(u, w)

14、v重量分布：重量分布：对于一个分组码而言，每个码对于一个分组码而言，每个码字都有一个字都有一个汉明重量，不同的码字可能具汉明重量，不同的码字可能具有相同的汉明重量，若记有相同的汉明重量，若记Ai为码中汉明重为码中汉明重量为量为i的码字个数，则称的码字个数，则称A0, A1, An是该是该码的重量分布，其中码的重量分布，其中n是码长是码长v两个码字两个码字0100,1111, ,它们的汉明重量它们的汉明重量w(0100)=1, w(1111)=4, 其汉明距离其汉明距离d(0100, 1111)=3v若将若将(n,k)线性分组码线性分组码C与其对偶码与其对偶码Cd的重量分布的重量分布分别记为分别

15、记为A0, A1, An和和B0, B1, Bn ，又记，又记多项式多项式v那么多项式那么多项式A(z)和和B(z)之间满足如下关系之间满足如下关系 niiiniiizBzBzAzA00, zzBzzAnkn1112v定理定理：令令C是一致校验矩阵为是一致校验矩阵为H的的(n,k)线性线性码，对于汉明重量为码，对于汉明重量为l的每个码矢，在的每个码矢，在H中中都有都有l列，使得这列，使得这l列的矢量和为列的矢量和为0，反之，反之，若若H中存在中存在l列，其矢量和为列，其矢量和为0，则，则C中必有中必有一个汉明重量为一个汉明重量为l的码矢。的码矢。v定义：定义：在在(n,k)码中，任意两个码字之

16、间都有一个码中，任意两个码字之间都有一个汉明距离，两组不同码字之间可能有相同的汉明汉明距离，两组不同码字之间可能有相同的汉明距离。若记距离。若记Di(0in)为距离为为距离为i的码字组数，那的码字组数，那么称么称D0, D1, Dn为此分组码的为此分组码的距离分布距离分布，并，并且称能够使且称能够使Di0的那个最小整数的那个最小整数i为该码的为该码的最小最小码间距离码间距离。v对线性分组码而言，重量分布与距离分布是一回对线性分组码而言，重量分布与距离分布是一回事。特别的，有如下定理事。特别的，有如下定理v定理：定理：(n,k)线性码的最小码间距离等于非零码字线性码的最小码间距离等于非零码字的最

17、小汉明重量的最小汉明重量v线性分组码线性分组码C=0000, 1010, 0101, 1111, 其中分组其中分组长度为长度为n=4，计算码字之间的汉明距离计算码字之间的汉明距离 d(0000, 1010) = 2, d(0000, 0101) = 2, d(0000, 1111) = 4, d(1010, 0101) = 4, d(1010, 1111) = 2, d(0101, 1111) = 2. 该码的最小距离是该码的最小距离是2, , 并且该码的最小重量也是并且该码的最小重量也是2 所以最小距离和最小重量是相等的。所以最小距离和最小重量是相等的。v分组码的最小码间距离是决定该码纠错和

18、分组码的最小码间距离是决定该码纠错和检错能力的重要指标检错能力的重要指标v定理：定理：设设(n,k)线性码线性码C的最小码间距离为的最小码间距离为d，则则1)若若dt+1，则码，则码C能检测能检测t个随机错误；个随机错误；2)若若d2t+1，则码，则码C能纠正能纠正t个随机错误；个随机错误；3)若若dt+e+1，则码，则码C能纠正能纠正t(te)个随机错误，个随机错误，同时还能检测同时还能检测e个随机错误。个随机错误。v因此，若码因此，若码C的最小汉明距离的最小汉明距离d越大，则该越大，则该码的纠错和检错能力就越强码的纠错和检错能力就越强v例例1：码码C1=000,111，码的最小距离是，码的

19、最小距离是3，因此重量为因此重量为1和和2个错误图样可以被检测出个错误图样可以被检测出来，即错误图样如果为来，即错误图样如果为011,101,110,001, 010,100，就可以被检测出来。，就可以被检测出来。v例例2：对于码对于码C2=001,110,101，码的最小，码的最小距离是距离是1，由于，由于d-1=0，所以我们什么都不，所以我们什么都不能说。重量为能说。重量为1的错误图样的错误图样010可以被检测可以被检测出来，但是该码不能检测所有重量为出来，但是该码不能检测所有重量为1的的错误图样，比如错误图样错误图样，比如错误图样100就不能被检测就不能被检测出来。出来。v定理：定理：

20、(n,k)线性码线性码C的最小码间距离的最小码间距离d满足满足dn-k+1。该定理给出了。该定理给出了d的上界。的上界。v最大距离可分码：最大距离可分码：若若(n,k)线性码的最小码线性码的最小码间距离间距离d满足满足d=n-k+1 ，那么称此种码为，那么称此种码为最大距离可分码，简称最大距离可分码，简称MDS码。码。v令令C是一致校验矩阵为是一致校验矩阵为H的的(n,k)线性码：线性码： 1) 若若H中没有中没有d-1列或者更少的列矢量和为列或者更少的列矢量和为0，则则C的最小码间距离至少为的最小码间距离至少为d 2) C的最小码间距离等于的最小码间距离等于H中和为中和为0的最小的最小列数列

21、数v令令(n,k)线性码线性码C的所有码字是的所有码字是 接收矢量接收矢量r是一个是一个n重，则按如下的方式构造码重，则按如下的方式构造码C的标准阵：的标准阵：kvv21,.,kknknknknkkkveveveeveveveeveveveevvvviiii2222222332332222222210v步骤步骤1：在第一行写下所有合法的在第一行写下所有合法的2k个码字个码字v=v1, v2k，第一个码字为全零码字；，第一个码字为全零码字；v步骤步骤2：选择一个第一行没有出现的矢量作选择一个第一行没有出现的矢量作为为e2，标准阵第，标准阵第2行写行写e2+v；v步骤步骤3：继续选择一个第一行和第

22、二行都没继续选择一个第一行和第二行都没有出现的矢量有出现的矢量e3 ，标准阵第，标准阵第3行写行写e3+v；v步骤步骤4：依次类推，直到依次类推，直到GF(2n)中所有的矢中所有的矢量都被列出来一次。量都被列出来一次。v考虑码考虑码C=0000,1011,0101,1110，对应的标准，对应的标准阵就是阵就是1100011110010010101000011111010001101101001110001110010110110000码字码字陪集首陪集首v性质性质1：同一行中任意两个同一行中任意两个n重之和为一个码字重之和为一个码字v性质性质2：在标准阵中，同一行没有两个在标准阵中，同一行没有

23、两个n重是相同重是相同的，每个的，每个n重在且仅在一行中出现重在且仅在一行中出现v性质性质2的证明：的证明：1)假设第假设第l行有行有2个个n重是相同的，重是相同的，如对如对ij有有el+vi=el+vj，即，即vi=vj，这与标准阵的构造，这与标准阵的构造相矛盾，故性质相矛盾，故性质2的第一行得证。的第一行得证。2)首先由定义知首先由定义知每个每个n重至少出现一次，假设一个重至少出现一次，假设一个n重在第重在第l行和第行和第m行行(lm)都出现，则必存在都出现，则必存在i，使得该，使得该n重等于重等于el+vi，且存在，且存在j，使得该，使得该n重等于重等于em+vj，即有，即有em=el+

24、(vi+vj)=el+vs，这意味着，这意味着em在第在第l行，这与标行，这与标准阵的构造定义相矛盾。准阵的构造定义相矛盾。v陪集：陪集：标准阵中共有标准阵中共有2n-k行，它们称为码行，它们称为码C的陪集的陪集v陪集首：陪集首：每个陪集中的第一个每个陪集中的第一个n重重ei称为陪集首。称为陪集首。陪集中的任何一个元素都可以作为陪集首，需要陪集中的任何一个元素都可以作为陪集首，需要做置换操作做置换操作v对于一个码字对于一个码字vi，如果信道造成的错误图样是陪，如果信道造成的错误图样是陪集首，则接收矢量集首，则接收矢量r在陪集中，此时，可以将接收在陪集中，此时，可以将接收矢量正确的译码为矢量正确

25、的译码为vi；否则，若信道造成的错误；否则，若信道造成的错误图样不是陪集首，则会造成错误译码。当且仅当图样不是陪集首，则会造成错误译码。当且仅当错误图样为陪集首时，译码正确。错误图样为陪集首时，译码正确。v定理：定理：陪集首是可纠正的错误图样，共有陪集首是可纠正的错误图样，共有2n-k个可个可纠正的错误图样纠正的错误图样v基于标准阵的译码策略：基于标准阵的译码策略：如果接收矢量如果接收矢量r落落在标准阵中的第在标准阵中的第i行第行第j列，那么就将列，那么就将r译码译码为为vj，同时错误图样为，同时错误图样为ei，即，即r=ei+vjv最小距离译码策略：最小距离译码策略：如果出现了不可纠正如果出

26、现了不可纠正错误图样，就出现了译码错误。对错误图样，就出现了译码错误。对BSC信信道，为了使译码错误概率最小，可以选择道，为了使译码错误概率最小，可以选择汉明重量最小的汉明重量最小的n重做为陪集首，由此导出重做为陪集首，由此导出了最小距离译码策略，即将接收矢量了最小距离译码策略，即将接收矢量r译码译码为与为与r的汉明距离最小的那个码字的汉明距离最小的那个码字v考虑码考虑码C=0000,1011,0101,1110，对应的标准，对应的标准阵就是阵就是1100011110010010101000011111010001101101001110001110010110110000码字码字陪集首陪集首

27、v如果接收矢量是如果接收矢量是1101，在标准阵中找到这个矢，在标准阵中找到这个矢量的位置，那一列最上面的码字是量的位置，那一列最上面的码字是0101，所以，所以估计的码字是估计的码字是0101，那一行最左边的矢量是，那一行最左边的矢量是1000，所以错误图样就是，所以错误图样就是1000v考虑码考虑码C=00000,01010,10101,11111，该码的最，该码的最小距离是小距离是2。如果传输的码字是。如果传输的码字是11111，接收的矢，接收的矢量是量是11110，那么，那么，d(11110, 00000)=4, d(11110, 01010)=2, d(11110, 10101)=3

28、, d(11110, 11111)=1, 用最小距离译码策略，可以得出传输的码字就是用最小距离译码策略，可以得出传输的码字就是11111这样的结论。但因为这样的结论。但因为d2t+1, 23,该码并不该码并不能纠正所有能纠正所有t=1的错误图样，比如，若传输的码的错误图样，比如，若传输的码字是字是00000，接收矢量是，接收矢量是01000，那么，那么， d(01000, 00000)=1, d(01000, 01010)=1, d(01000, 10101)=4, d(01000, 11111)=4, 此时根据最小距离译码策略就此时根据最小距离译码策略就无法清楚地进行唯一的判决无法清楚地进行

29、唯一的判决v对转移概率为对转移概率为p的二元对称信道而言，陪的二元对称信道而言，陪集首的重量分布集首的重量分布A0, A1, An与译码错误与译码错误概率之间满足概率之间满足v定理：定理：对码间最小距离为对码间最小距离为d的的(n,k)线性码，线性码，重量重量w(d-1)/2=t的的n重都可以被用作标准阵重都可以被用作标准阵的陪集首，并且至少有一个重量为的陪集首，并且至少有一个重量为t+1的的n重不能作为陪集首重不能作为陪集首v注：注：此定理再次显示了码此定理再次显示了码C能纠正能纠正t个错误，个错误，但是不能纠正所有但是不能纠正所有t+1个错误个错误 niiniippAEP011v定理：定理

30、：若若C是是GF(q)上的一个上的一个(n,k)线性码，则线性码，则1)长长度为度为n的矢量的矢量b一定在码一定在码C的某个陪集中；的某个陪集中；2)每个每个陪集都包含陪集都包含qk个矢量；个矢量；3)两个陪集要么是不相交两个陪集要么是不相交的要么就是重合的的要么就是重合的(即相互部分重叠是不可能的即相互部分重叠是不可能的)；4)如果如果a+C是码是码C的一个陪集，且有的一个陪集，且有ba+C，那，那么一定有么一定有b+C=a+Cv证明：证明：1) b=b+0b+C；2) 对于所有的对于所有的xC, ,由由xa+x定义的映射定义的映射Ca+C是个一一映射，是个一一映射，所以陪集所以陪集a+C中

31、矢量的个数和码集中码矢中矢量的个数和码集中码矢的个数相等，即的个数相等，即qkv证明：证明：3) 反证法。假设陪集反证法。假设陪集a+C和和b+C是相是相交的，即它们至少有一个向量是相同的，交的，即它们至少有一个向量是相同的，令令v=(a+C)(b+C)，那么对于任意的，那么对于任意的x,yC，有有v=a+x=b+y, b=a+x+y=a+z,其中其中zC，这，这是根据码字集合的封闭性，两个码字之和是根据码字集合的封闭性，两个码字之和仍然是一个码字，因此仍然是一个码字，因此b+C=a+z+C=a+C+z或者或者 类似的，还可以得到类似的，还可以得到 所以所以( (b+C)=(a+C)CaCbC

32、bCav证明：证明：4) 由于由于ba+C表明对于某个表明对于某个xC, b=a+x。接下来，如果接下来，如果b+yb+C，那么，那么b+y=(a+x)+y =a+(x+y)a+C, ,即即v另一方面，类似的，如果另一方面，类似的，如果a+za+C，那么，那么a+z=(b+x)+z=b+(x+z)b+C , ,即即v因此因此b+C=a+CCaCbCbCav当所考虑的码当所考虑的码C的的n和和k的值都很大的时候，标准的值都很大的时候，标准阵列的长度就变得非常的巨大，此时，用标准阵阵列的长度就变得非常的巨大，此时，用标准阵来译码就变得不实用了来译码就变得不实用了v有办法来给标准阵降阶么？用伴随式译

33、码有办法来给标准阵降阶么？用伴随式译码v定理：定理：一个陪集的所有一个陪集的所有2k个个n重有同样的伴随式。重有同样的伴随式。不同陪集的伴随式不同不同陪集的伴随式不同 证明：证明：如果如果x,y属于同一个陪集，那么属于同一个陪集，那么)()(0ysxsyHxHHyxCyxCyCxTTTv考虑码考虑码C=0000,1011,0101,1110，对应的标准对应的标准阵就是阵就是100111001100011110010010101000011111010001101101001110001110010110110000码字码字陪集首陪集首伴随式伴随式v步骤步骤1：计算接收矢量计算接收矢量r的伴随式的伴随式rHTv步骤步骤2：确定伴随式等于确