信道编码的基本概念以及汉明码编码错误图样

1、信道编码的基本概念以及汉明码编码 错误图样 信道编码的几个基本概念 1）码重：码字中非零位的数目定义为该码组的重量，即所含“1” 的个数简称码重，记为Wc。如“10011”码组的码重为3 2）码距：两个码组中对应码位上具有不同二进制码元的位数被 定义为两码组的距离，称为汉明（Hamming）距离，简称码 距，记为d( ci, cj )。如两码组“10011”与“11010”间码距为2 3）编码效率：指一个码组中信息位所占比重，用 表示 = k/n 其中k为信息码元的数目，n为码长。 值越大表明信息位所 占的比重越大，码组传输信息的有效性越高 信道编码的基本概念以及汉明码编码 错误图样 信道编码

2、的基本概念以及汉明码编码 错误图样 有上述分析可知：假设一个码能检测e个独立错误，则要求其最 小码距 dmine + 1 反之，若码的最小距离为dmin，则最多能检测dmin-1个错码 信道编码的基本概念以及汉明码编码 错误图样 信道编码的基本概念以及汉明码编码 错误图样 信道编码的基本概念以及汉明码编码 错误图样 由上述分析可知：一个码能纠正t个错码，则要求其最小码距 dmin 2t+1 反之，若码的最小距离为dmin ，则最多能纠正 (dmin-1)/2个错码 信道编码的基本概念以及汉明码编码 错误图样 一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmine+t+1 (et

3、) 纠正t个错码，同时能检测e个错码，称为纠检结合，错码数较少 时执行纠错方式，错码数较多时执行检错方式 信道编码的基本概念以及汉明码编码 错误图样 有限域的简单知识 所谓有限域是指包含有限个元素的集合，按照所规定的运算规则 运算后的结果仍为集合中的元素 编码理论中有限域为0, 1二元集合，记为GF(2) GF(2)的加法与乘法： 1）加法：相同为0，相异为1； 2）乘法：除了11 = 1，其他均为0 二元扩展域，记为GF(2n) ：由GF(2)中的元素构成的长为n的序列的 集合，若 1）加法 2）乘法 112200 (, ) nnnn XXxxxxxx 112200 (, ) nnnn X

4、Xxxxxxx 120 (,)(2 )GF n nn X xxx 信道编码的基本概念以及汉明码编码 错误图样 二、线性分组码 线性分组码的数学定义： 信道编码可表示为由编码前的信息码元空间Uk到编码后的码字 空间Cn的一个映射f，即： f： Uk Cn 其中( n k ) 若f进一步满足线性关系： 则称f为线性编码映射，若f为一一对应映射，则称f为唯一可译线 性编码，由f编写的码c = (cn-1cn-2c0)称为线性分组码，u = (un- 1un-2 u0 )为编码前的信息分组，其中k为信息位数，n为码长， 其编码效率为= k/n ()()(),(2)0,1, GF k fuufufuu

5、uU 信道编码的基本概念以及汉明码编码 错误图样 数学定义的解释： 1）“线性”是指码组中码元之间的约束关系为线性； 2）“分组”是在编码时将每k个信息位分为一组进行独立处理； 3）将其变换成长度为n（nk）的二进制码组，一般称为（n, k） 线性分组码 线性分组码的特征： 1）加法封闭性：码组集合中任意两个码组相加仍为集合中的一 个许用码组； 2）全零序列是线性分组码中的一个码字； 3）码组集合中码组之间的最小码距等于某非零码字的最小码重 信道编码的基本概念以及汉明码编码 错误图样 偶监督偶校验码 发送端编码：将一位监督码元附加在信息码元后，使得码组中“1” 码元个数为偶数（偶监督） 接收端

6、译码校验： 1）计数接收码组中“1”码元个数是否为偶数，即计算 S = an-1+ an-2+ a0 2）S = 0认为没错，S = 1认为有错 3）上式称为监督方程（监督关系式），其中S 称为校正子（校 验子、伴随式） 4）S只能判断有错无措，而不能纠错 汉明码的构造 信道编码的基本概念以及汉明码编码 错误图样 假设有1个信息码组由4位二进制位组成，在其后添加3位二进制位 作为监督码元，最后所组成的码组表示为： c = (u6u5u4u3c2c1c0) 并且令： 1）c2监督u6 u5 u4，即 2）c1监督u6 u5 u3，即 3）c0监督u6 u4 u3，即 接收端译码校验，得到监督方程

7、： 6531 0uuuc 6542 0uuuc 6430 0uuuc 65422 65311 64300 uuucS uuucS uuucS 6542 uuuc 6531 uuuc 6430 uuuc 信道编码的基本概念以及汉明码编码 错误图样 对于上式，若无错误发生，三个校验子均为0；假设传输过程中有且仅有一位 发生错误： 1）若c0发生错误，观察监督方程，则三个校验子S2 S1 S0的组合为001； 2）若c1发生错误， S2 S1 S0 = 010； 3）若c2发生错误， S2 S1 S0 = 100； 4）若u3发生错误， S2 S1 S0 = 011； 5）若u4发生错误， S2 S

8、1 S0 = 101； 6）若u5发生错误， S2 S1 S0 = 110； 7）若u6发生错误， S2 S1 S0 = 111； 65422 65311 64300 uuucS uuucS uuucS 信道编码的基本概念以及汉明码编码 错误图样 因此依据监督关系式 就可计算出所有4位二进制信息位u6u5u4u3的监督位c2c1c0，这 一过程即为( 7, 4 )线性码的构造过程，其码组空间为： 6542 6531 6430 0 0 0 uuuc uuuc uuuc 信道编码的基本概念以及汉明码编码 错误图样 监督矩阵的推导 将监督关系式进行变换 观察发现上式即为一个线性方程组，因此可 用矩阵

9、方程来表示： 6542 6531 6430 0 0 0 uuuc uuuc uuuc 6543210 6543210 6543210 11101000 11010100 10110010 uuuuccc uuuuccc uuuuccc 6 5 4 3 2 1 0 11101000 11010100 10110010 u u u u c c c 信道编码的基本概念以及汉明码编码 错误图样 对于上面的矩阵方程，令： 则矩阵方程可化简为：HCT=OT 或 CHT=O 那么H称为线性码监督矩阵，rn 阶的矩阵，由r（监督位个数）个线性独立方 程组的系数组成，每一行代表了监督位与信息位间的监督关系。观察

10、矩阵H： 把具有(PIr)形式的H矩阵称为典型形式的监督矩阵，其中P矩阵为rk 阶矩阵, Ir 矩阵为rr 阶单位方阵 H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关 1110100 1101010 1011001 H 6543210 Cuuuuccc 1110100 1101010 1011001 r HP I 0 0 0 O 信道编码的基本概念以及汉明码编码 错误图样 生成矩阵的推导 对监督关系式进行移项变换（移动红色部分）： 6543210 6543210 6543210 1110100 1101010 1011001 uuuuccc uuuuccc uuuuccc

11、210 2 6543 6543 6543 10 210 100 0 11100 1101010 10110001 ccuuc cc uu uuuc cc u uuuuc 65432 65431 65430 11101 11011 10111 uuuuc uuuuc uuuuc 6 2 5 1 4 0 3 1110 1101 1011 u c u c u c u 信道编码的基本概念以及汉明码编码 错误图样 观察上面的矩阵方程： 其中系数矩阵与监督矩阵H中的P矩阵一样，对此矩阵方程两边做转置变换： 其中Q = PT，为kr 阶矩阵；U矩阵表示信息位 由上面的矩阵方程可知，只要用信息位与矩阵Q相乘就

12、可得到监督位，然后拼 接在信息位之后就是一个（n, k）线性分组码集合中的一个码字 6 2 5 1 4 0 3 1110 1101 1011 u c u c u c u 2106543 6543 111 110 101 011 T cccuuuu uuuuPUQ 信道编码的基本概念以及汉明码编码 错误图样 虽然通过Q矩阵可以产生线性分组码，但需要分为两步，如果对Q矩阵做 变换： 在Q矩阵的左边加上一个kk阶单位阵，即： 则一个（n, k）线性分组码可以通过下面的矩阵方程产生 65436543 6543 6543210 1000111 0100110 0010101 0001011 k uuuu

13、 GuuuuIQ uuuu uuuuccc 1000111 0100110 0010101 0001011 k GIQ 信道编码的基本概念以及汉明码编码 错误图样 对于生成矩阵G： 1）kn阶矩阵； 2）编码方法完全由生成矩阵G确定； 3）把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中Ik为kk阶单 位方阵，Q为k r阶矩阵； 4）由典型生成矩阵产生的分组码一定是系统码； 5）若某生成矩阵G不具有典型形式，则产生的线性分组码为非系统码； 若将G进行线性初等矩阵变换，使其具有典型形式，则产生的码组与 不变换产生的码组有同样的纠检能力，即系统码与非系统码的纠检 能力相同； 6）H = PIr

14、 = QTIr G = IkQ = IkPT 7）生成矩阵G的各行线性无关 信道编码的基本概念以及汉明码编码 错误图样 对于监督矩阵H： 1）H矩阵rn 阶的矩阵 2）H矩阵中每行和其码组集合中的任一码字的内积为0； 3）任意一个( n, k )线性分组码的H矩阵行线性无关； 4）一个( n, k, d )线性分组码，若要至多纠正t个错误，则其充要条 件是H矩阵中任何一个2t列线性无关，由于最小距离d = 2t + 1， 所以也相当于要求H矩阵中任意(d 1)列线性无关 6543210 6543210 6543210 11101000 11010100 10110010 ccccccc ccc

15、cccc ccccccc 信道编码的基本概念以及汉明码编码 错误图样 生成矩阵G与监督矩阵H的关系： 因为信息位不会全零，因此： 再由： H = PIr，G = IkQ，代入上式，得： 上式中矩阵的下标为其阶数 T TTk r kk r r P G HIQPQO I TT TT H CO C HOU G HO CU G T G HO 信道编码的基本概念以及汉明码编码 错误图样 例：设（7, 4）线性码的生成矩阵G为： 当信息位为0001时，试求其后的监督位。 1101000 1010100 0110010 1110001 信道编码的基本概念以及汉明码编码 错误图样 例：试求上例的监督矩阵H 解

16、：根据生成矩阵和监督矩阵的关系： G = IkQ，H=PIr 可得监督矩阵H为： 1001101 0101011 0010111 信道编码的基本概念以及汉明码编码 错误图样 对偶码 定义：对于线性分组码： 1）将( n, k ) 码的监督矩阵H作为( n, n k )码 的生成矩阵G； 2）将( n, k ) 码的生成矩阵G作为( n, n k )码 的监督矩阵H 这样的( n, k ) 码与( n, n k )码互为对偶码 信道编码的基本概念以及汉明码编码 错误图样 编码过程 观察(7, 4)码的监督关系式： 可设计出相应的编码电路： 6542 6531 6430 uuuc uuuc uuu

17、c 信道编码的基本概念以及汉明码编码 错误图样 译码纠、检过程 错误矩阵/错误图样E：设发送码组为c，接收码组为y，则 对于二元有限域，上式中的减法等价于加法，即： 对于二元有限域的加法的具有确定两个码组中不同比特位的特性，例如： 假设长度为n的码组A和B分别为： 假设这两个码组的第k位不同，其他位相同，根据加法规则： 因此接收端可以利用这种特性进行纠错，即若能确定错误图样就可以进行纠错： 120nn ecyeee 120nn ecyeee 10 () nnk a aaa 10 () nnk b bbb 10 10 () (0010) () nnk nnk a aaa b bbb c ey 信道编码的基本概念以及汉明码编码 错误图样 因此利用等式 及2