线性分组码的生成矩阵已知ppt课件.ppt
1,3 线性分组码,线性分组码是指分组码中信息元和校验元是用线性方程联系起来的一种差错控制码。线性分组码是纠错码中最重要的一类码，是研究纠错码的基础。,2,把信息序列按一定长度分成若干信息码组，每组由 k 位组成；编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成 n 长 (nk) 码字，其中 (nk) 个附加码元是由信息码元的线性运算产生的。信息码组长为 k 位，若有 2k 个不同的信息码组，则有 2k 个码字与它们一一对应。,一个 n 长的码字可以用矢量来表示C = (Cn1 ,Cn2 ,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个码字如表。,1.线性分组码的一致校验矩阵,3.1 一致校验矩阵和生成矩阵,3 线性分组码,6,为了运算方便，将式(9.1)监督方程写成矩阵形式，得式(9.2)可写成 H CT=0T或 C HT=0 CT、HT、0T分别表示C、H、0的转置矩阵。,1.线性分组码的一致校验矩阵,3.1 一致校验矩阵和生成矩阵,3 线性分组码,7,系数矩阵 H 的后四列组成一个 (44) 阶单位子阵，用 I4 表示，H 的其余部分用 P 表示,1.线性分组码的一致校验矩阵,3.1 一致校验矩阵和生成矩阵,3 线性分组码,8,推广到一般情况：对 (n,k) 线性分组码，每个码字中的 r (=n-k) 个监督元与信息元之间的关系可由下面的线性方程组确定,1.线性分组码的一致校验矩阵,3.1 一致校验矩阵和生成矩阵,3 线性分组码,9,令上式的系数矩阵为 H，码字矩阵（行阵列）为 C,1.线性分组码的一致校验矩阵,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 也是 C I 中的一个码字。证明：由于 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 线性分组码,14,G 中每一行 gi = ( gi 1, gi 2, , gi n ) 都是一个码字；对每一个信息码元m来说，都可以通过矩阵G求得其对应的码字。生成矩阵的定义：由于矩阵 G 生成了 (n,k) 线性码中的任何一个码字，称矩阵 G 为 (n,k) 线性码的生成矩阵。(n,k) 线性码的每一个码字都是生成矩阵 G 的行的线性组合。,2 线性分组码的生成矩阵,3 线性分组码,3.1 一致校验矩阵和生成矩阵,15,标准生成矩阵： 通过行初等变换，将 G 化为前 k 行和k 列是单位子阵的标准形式,2 线性分组码的生成矩阵,3.1 一致校验矩阵和生成矩阵,3 线性分组码,16,线性系统分组码：用标准生成矩阵 Gkn 编成的码字，前面 k 位为信息数字，后面 r=nk 位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。当生成矩阵 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=0,2 线性分组码的生成矩阵,结论：线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接转换。,3 线性分组码,19,2 线性分组码的生成矩阵,已知 ( 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,码字最小距离为: 4,根据产生监督码的方法，写出监督方程为：,2 线性分组码的生成矩阵,3 线性分组码,21,汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。汉明码的结构特点：纠一个错误的线性码，其最小距离 dmin=3 ；监督矩阵任意两列线性无关/ 即H 中任两列互不相同；没有全0的列，监督元个数 nk=r ，即H 阵中每列有 r 个元素，至多可构成 2r1种互不相同的非0列。,3.2 汉明码,3 线性分组码,22,汉明码的结构参数： （对于任意正整数 m3）监督位数： nk=m码长： n=2m1信息位数： k=2mm1码的最小距离：dmin= 3 ( t =1 ),3.2 汉明码,3 线性分组码,23,汉明码监督矩阵构成的两种方式构成 H 阵的标准形式，H=Q Im，其中 Im 为 m 阶单位子阵，子阵 Q 是构造 Im 后剩下的列任意排列。用这种形式的 H 阵编出的汉明码是系统码。按m重表示的二进制顺序排列。按这种形式 H 阵编出的码是非系统码。当发生可纠的单个错误时，伴随式S为H 阵中对应的列，所以伴随式的二进制数值就是错误位置号，有时这种码译码比较方便。,3.2 汉明码,3 线性分组码,24,汉明码可纠的错误图样数为,3.2 汉明码,3 线性分组码,
