2线性分组码的生成矩阵已知

信息论电子信息工程学院13线性分组码线性分组码是指分组码中信息元和校验元是用线性方程联系起来的一种差错控制码。线性分组码是纠错码中最重要的一类码，是研究纠错码的基础。信息论电子信息工程学院2把信息序列按一定长度分成若干信息码组，每组由k位组成；编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成n长(nk)码字，其中(n－k)个附加码元是由信息码元的线性运算产生的。信息码组长为k位，若有2k个不同的信息码组，则有2k个码字与它们一一对应。一个n长的码字可以用矢量来表示C=(Cn－1,Cn－2,…,C1,C0)1.线性分组码的一致校验矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院3举例：k=3,r=4，构成(7,3)线性分组码。设码字为(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”监督元可按下面方程组计算1.线性分组码的一致校验矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院4一致校验方程：按规则通过已知的信息元得到校验元的一组方程称为校验方程。由于所有码字都按同一规则确定，又称为一致校验方程。由于校验方程是线性的，即校验元和信息元之间是线性运算关系，所以由线性校验方程所确定的分组码是线性分组码。1.线性分组码的一致校验矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院5若已知信息码组为(101)，即C6=1,C5=0,C4=1代入方程(9.1)得：C3=0,C2=0,C1=1,C0=1由信息码组(101)编出的码字为(1010011)。其它7个码字如表。表5.1(7,3)分组码编码表信息组对应码字0000000000001001110101001001110110111010100100111010110100111101101001111111010000000000000000000000451562456346CCCCCCCCCCCCC1.线性分组码的一致校验矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院6为了运算方便，将式(9.1)监督方程写成矩阵形式，得式(9.2)可写成HCT=0T或CHT=0CT、HT、0T分别表示C、H、0的转置矩阵。1.线性分组码的一致校验矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院7系数矩阵H的后四列组成一个(4×4)阶单位子阵，用I4表示，H的其余部分用P表示1.线性分组码的一致校验矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院8推广到一般情况：对(n,k)线性分组码，每个码字中的r(=n-k)个监督元与信息元之间的关系可由下面的线性方程组确定1.线性分组码的一致校验矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院9令上式的系数矩阵为H，码字矩阵（行阵列）为C1.线性分组码的一致校验矩阵9.3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院10H阵的每一行都代表一个监督方程，即H阵的r行代表了r个监督方程，也表示由H所确定的码字有r个监督元。3.1一致校验矩阵和生成矩阵1.线性分组码的一致校验矩阵3线性分组码行变换监督矩阵H为标准形式：即后面r列是一单位子阵的监督矩阵H。对H各行实行初等变换，将后面r列化为单位子阵，于是得到下面矩阵：信息论电子信息工程学院11H的标准形式还说明了相应的监督元是由哪些信息元决定的。例如(7,3)码的H阵的第一行为(1011000)，说明此码的第一个监督元等于第一个和第三个信息元的模2和，依此类推。1.线性分组码的一致校验矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院12(1)线性码的封闭性线性码的封闭性：线性码任意两个码字之和仍是一个码字。定理：设二元线性分组码CI(CI表示码字集合)是由监督矩阵H所定义的，若U和V为其中的任意两个码字，则U+V也是CI中的一个码字。[证明]：由于U和V是码CI中的两个码字，故有UT=0T，HVT=0T那么H(U+V)T=H(UT+VT)=HUT+HVT=0T即U+V满足监督方程，所以U+V一定是码字集合CI中的一个码字。2线性分组码的生成矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院13(2)生成矩阵的由来：在由(n,k)线性码构成的线性空间Vn的k维子空间中，一定存在k个线性独立的码字：g1,g2,…,gk。2线性分组码的生成矩阵码字集合CI中，其它任何码字C都可以用这k个码字的某种线性组合来表示，即3线性分组码信息论电子信息工程学院14G中每一行gi=(gi1,gi2,…,gin)都是一个码字；对每一个信息码元m来说，都可以通过矩阵G求得其对应的码字。生成矩阵的定义：由于矩阵G生成了(n,k)线性码中的任何一个码字，称矩阵G为(n,k)线性码的生成矩阵。(n,k)线性码的每一个码字都是生成矩阵G的行的线性组合。2线性分组码的生成矩阵3线性分组码3.1一致校验矩阵和生成矩阵信息论电子信息工程学院15标准生成矩阵：通过行初等变换，将G化为前k行和k列是单位子阵的标准形式2线性分组码的生成矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院16线性系统分组码：用标准生成矩阵Gk×n编成的码字，前面k位为信息数字，后面r=n－k位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。当生成矩阵G确定之后，(n,k)线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。2线性分组码的生成矩阵3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院17(3)举例：已知一个(7,4)线性码的生成矩阵G如下图示，当输入信息码元为1010时，试求输出的码字。2线性分组码的生成矩阵由矩阵乘法规则可知：C=mG的结果，就是矩阵G中，与m中为“1”的元素相对应的行按位模2加的结果。3.1一致校验矩阵和生成矩阵3线性分组码信息论电子信息工程学院18(4)生成矩阵与监督矩阵的关系由于生成矩阵G的每一行都是一个码字，所以G的每行都满足HCT=0T，则有HGT=0T或GHT=02线性分组码的生成矩阵结论：线性系统码的监督矩阵H和生成矩阵G之间可以直接转换。3线性分组码GIQHPI(P)GHIQPIIQ(P)Q0IQ(P)(Q)PGIQ(9.14)H(Q)ISkkrSrkrTTTTrkSSkkrrkrkkrrkkrkrrTTkrrkkrrkSkkrTSkrr所以，或信息论电子信息工程学院192线性分组码的生成矩阵已知(7,3)线性分组码,其码字表示为:C=(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为三位信息元，C3,C2,C1,C0为四位监督元，可由下列方法产生:试求：（1）生成矩阵G和监督矩阵H；（2）写出其全部的码字，码字间的最小距离dmin是多少？3线性分组码例题：3.1一致校验矩阵和生成矩阵信息论电子信息工程学院201000110010001100101110001101H101110011100100111001G码字最小距离为:4根据产生监督码的方法，写出监督方程为：表5.1(7,3)分组码编码表信息组对应码字0000000000001001110101001001110110111010100100111010110100111101101001111111010000000000000000000000451562456346CCCCCCCCCCCCC2线性分组码的生成矩阵3线性分组码信息论电子信息工程学院21汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。汉明码的结构特点：纠一个错误的线性码，其最小距离dmin=3；监督矩阵任意两列线性无关/即H中任两列互不相同；没有全0的列，监督元个数n－k=r，即H阵中每列有r个元素，至多可构成2r－1种互不相同的非0列。3.2汉明码3线性分组码信息论电子信息工程学院22汉明码的结构参数：（对于任意正整数m≥3）监督位数：n－k=m码长：n=2m－1信息位数：k=2m－m－1码的最小距离：dmin=3(t=1)3.2汉明码3线性分组码信息论电子信息工程学院23汉明码监督矩阵构成的两种方式构成H阵的标准形式，H=[QIm]，其中Im为m阶单位子阵，子阵Q是构造Im后剩下的列任意排列。用这种形式的H阵编出的汉明码是系统码。按m重表示的二进制顺序排列。按这种形式H阵编出的码是非系统码。当发生可纠的单个错误时，伴随式S为H阵中对应的列，所以伴随式的二进制数值就是错误位置号，有时这种码译码比较方便。3.2汉明码3线性分组码信息论电子信息工程学院24汉明码可纠的错误图样数为3.2汉明码3线性分组码