信息论与纠错编码题库

第八章线性分组码8.1什么是检错码？什么是纠错码？两者有什么不同？答：能发现错误但不能纠正错误的码称为检错码；不仅能发现错误而且还能纠正错误的码称为纠错码。8.2试述分组码的概念，并说明分组码的码率r的意义。答：分组码是把信息序列以每k个码元分组，即每k个码元组成一个信息组。n表示码长,k表示信息位的数目，码率r=k/n，它说明在一个码字中信息为所占的比重。8.3什么是码的生成矩阵和校验矩阵？一个（n，k）线性分组码的生产矩阵和校验矩阵各是几行几列的矩阵？答：线性分组码的2个码字将组成n维向量空间的一个k维子空间，而线性空间可由其基底张成，因此线性分组码的个码字完全可由k个独立的向量组成的基底张成。设k个向量为（7.3-2）将它们写成矩阵形式：（7.3-3）（n,k）码中的任何码字，均可由这组基底的线性组合生成。即C=MG=(mk-1,mk-2,m0)G式中M=(mk-1,mk-2,m0)是k个信息元组成的信息组。这就是说，每给定一个信息组，通过式（7.3-3）便可求得其相应的码字。故称这个由k个线性无关矢量组成的基底所构成的k×n阶矩阵G为码的生成矩阵（GeneratorMatrix）。校验矩阵H的每一行代表求某一个校验位的线性方程的系数(n-k)线性分组码有r=n-k个校验元，故须有r个独立的线性方程，因此H矩阵必由线性无关的r行组成，是一个(n-k)×n阶矩阵，一般形式为一个（n,k）线性分组码生成矩阵有k行n列校验矩阵有(n-k)行n列。8.4什么样的码成为系统码？系统码的生成矩阵和校验矩阵在形式上有何特点？答：若信息组为不变的形式，称在码字的任意k位中出现的码为系统码；一个系统码的生成矩阵G，其左边k行k列是一个k阶单位方阵，系统码的校验矩阵H，其右边r行r列组成一个r阶单位方阵。8.5什么是对偶码？试举例说明之。答：若把（n,k）码的H矩阵看成是(n,r)码的生成矩阵Gd,而（n,k）码的G矩阵就是（n,r），码的校验矩阵Hd,则称这两种码为互为对偶码。例如课本列举的（7，3）码8.6试述码的距离和重量的概念。线性分组码的最小距离有何实际意义？答：两个码字之间，对应位取值不同的个数，称为它们之间的汉明距离，简称距离用d(c1,c2)表示。码字中非零码元的个数，称为该码子的汉明重量，简称重量，用w(c)表示。一个线性分组码的最小距离是衡量码抗干扰能力的重要参数。码的最小距离愈大，其抗干扰能力愈强。8.7如果要构造一个能纠2个错的线性分组码，则其H矩阵中至少应保证多少列线性无关？答：4列根据定理8.2检测e个错，则要求码的最小距离d大于等于e+1纠正t个错，则要求码的最小距离d大于等于2t+1纠正t个错误同时检测e个错误，则要求d大于等于t+e+1而根据定理8.3（n,k）线性分组码有最小距离为d的重要条件是H矩阵中任意d-1列线性无关所以是4列8.8什么是接收序列y的伴随式s？为什么伴随式s只由错误图样e决定？答：令0,2,1,0,22,21,20,12,11,1..................,...knnknnknnnnnhhhhhhhhhH=1101000011010011100101010001Gd=H=TTeHyHs其中y为接收码字e为接收图样，称s为接收序列的伴随式。由式可知若e=0，则s=0;若e≠0,则s≠0,因此伴随式s只由错误图样e决定。8.9如何构造一个码的标准阵列？标准阵列有哪些性质？答：先把子群中的全部k2个码字1c,2c,```,k2c置于表的第一行，并把该子群的加法恒等元1e=1c=0(即全零码字放在行的首位)在余下的n2-k2个n重中，选择一个n重2e作为第二行得首位元素，意识第二行的元素是2e和每个码字ic（i=1,2,```,k2）相加，并把2e+ic置于ic的下面即同一列。第三行再从其余的n重中选择一个3e作为首位元素，同理将3e+ic置于ic的下面完成第三行。以此类推，一直将n重用完为止。如下表：许用码字1e=1c（陪集首）2c3c…k2c禁用码字2e3e…n-k2e2e+2c3e+2c…n-k2e+2c2e+3c3e+3c…n-k2e+3c2e+k2c3e+k2c…n-k2e+k2c标准阵列的性质有：如果把陪集看成是错误图样，则每一个陪集中具有相同的错误图样。每一个陪集中的k2个n重都有相同的伴随式而不同的陪集具有不同的伴随式。对于同一列的各子集1,2,…,k2来说，其中n-k2个n重得错误图样虽然不同，但全部对应于同一许用码字。8.10如何利用标准阵列译码？为什么说用标准阵列译码时，译码错误概率的大小与陪集首的选择有关？答：当输入译码的接收序列为y时，经查表总能确定y落在标准阵列的第j行第i列，译码器就能判定发送码字是第i列（即子集i）所对应的许用码字ic而粗我图样即第j行所在陪集的陪集首je用上述方法译码时，译码正确的概率大小与陪集首的选择有关。显然任意选择陪集首不是好的方法。根据最大似然译码准则，重量最轻得错误图样产生的可能性最大，所以应选优先择重量小的n重作为陪集首，这样构造的译码表，可使je+ic与ic之间的激励最小，从而使译码器以更大的概率正确译码，这就是最小译码距离。8.11什么是完备码？为什么说汉明码是完备码？答：如果某一（n，k）线性分组码能使n-k2=n0+n1+…+nt成立，即错误图样正好等于伴随式数目，则称这种码为完备码。显然，汉明码是t=1完备码。8.12某分组码的校验矩阵为H=000011010101001110求：（1）n=？k=？该码的码字有多少？（2）该码的生成矩阵；（3）矢量010111和100011是否为码字。解：（1）n=6,k=3,该码有8个码字。（2）由校验矩阵可得4c+3c+2c=05c+3c+1c=05c+4c+0c=0所以5c=5c4c=4c3c=3c2c=4c+3c1c=5c+3c0c=5c+4c由此可得生成矩阵为：011100101010110001G（3）经验证，010111不是码字，100011是码字。8.13某二元（n，k）系统线性分组码的全部码字如下00000010111011011101求：（1）n=？k=？（2）码的生成矩阵G和校验矩阵H。解：（1）n=5，k=2。根据码字可以得n=5，又因为总共4个码字，说明信息位有2位，即k=2。（2）码的生成矩阵G=1101001101，校验矩阵H=100100101100101。ic=im·G，且G=[kI:P],根据全部的码字可以得出P。进而可以得到G。又H=[TP:rI]，从而推出矩阵H。其中kI、rI为单位矩阵8.14已知一个线性分组码的校验矩阵为H=100101101011010011110试求其生成矩阵。当输入信息序列为100111001101时，求编码器输出的码字序列。解：生成矩阵G=1111000011010010100101100001输出的码字序列为：1001100,1100110,1101001。根据G=[kI:P]，H=[TP:rI]的关系，由H矩阵可以写出G矩阵。又由ic=im·G可以分别得出信息序列为1001,1100,1101的码字分别为：1001100,1100110,1101001。8.15设一个（7，4）分组码的生成矩阵为G=0111000110010010100101110001求：（1）该码的全部码字（2）码的标准序列（3）码的简化译码表答：(1)信息组码字00000000000000100011100010001001100110011101010001001010101010101101100110110011101110001000100011110011001001101010101001011101101011001100010110111011001110111000111111111111（2）标准矩阵列信息组m00000001001000110100010101100111许用码字c00000000001110001001100111010100101010101101101100111000有单错的n重00000010001111001001000111000100100010101001101110111001000001000011000010001001111101001110101001011010001110100000100000101000101110011001010000101011110110010011110000010000000110001101100101010101101010001101111100110000001000000111100000011000110101101010111011010011001010000100000010111001100110111101000010100010110010110001100010000001001110101001110111011100101110101111101101111000信息组m10001001101010111100110111101111许用码字c10001111001001101010010110101100010110110011100011111111有单1000110100100010101011011011110001111011011110000111111010001011001011101011010110001100000110111011100111111101错的n重1000011100110110100001011110110011011010001111001111101110011111000001101110010100101101010110010011100011110111101011110110011000100100101011100101111100110000111011111100111110100111101001111010100001010011001010001101111100001110001001001010000110100100010010110001100010111111（3）译码表伴随式s错误图样（陪集首）e000000000000100000010100000010100000010011000010000110010000101010000011110000008.16构造8.15题中（7,4）分组码的对偶码，构造其系统码形式的G矩阵和H矩阵，并写出全部码字。答：G矩阵100011101011010011011G1000110010001100101110001101H码字：信息组码字000000000000111100010101011010011010101110011011001010011101110011011011110001118.17某（5,2）线性分组码的H矩阵H=100110100100111求：（1）该码的G矩阵（2）该码的标准阵列（3）该码的简化译码表（4）说明该码是否为完备码答：（1）由H矩阵的形式可知，该线性分组码为系统码根据系统码可知H=[P:rI]G=[kI:TP]110111PkI、rI为单位矩阵所以可以求出G=1011011101（2）根据题意（5,2）的线性分组码可以知道信息组m=11011000然后根据c=mG可以求出c=11011000*1011011101=