纠一位错的汉明码

,4.4纠一位错的汉明码(一),4.4纠一位错的汉明码(一),前面介绍的一致监督检错码、简单重复纠错码以及正反码,都属于线性分组码。,信息元的线性组合生成监督元，从而构成相应的码字。,汉明码的主要工作是由RichardW.Hamming在1950年,完成的。,最广泛的一类纠错码。,它们有一个共同的特点，即通过若干,由于其编码和译码容易实现，因此至今仍是应用,一、基本原理,通常将信息位记为,监督位记为,相应地，系统码则记为,一、基本原理,1.生成监督元,k位信息元,长度为的码字,以()系统码为例：,即,方法,一、基本原理,1.生成监督元,方法,令,则,一、基本原理,注(1)为了表述简洁，下面提到的“加”通常都指“模2加”；,1.生成监督元,方法,(2)对k和r有何要求?,(2)在此意义下，一般不需要使用“减法”。,一、基本原理,2.监督矩阵,分析,由,有,一、基本原理,2.监督矩阵,分析,注意到矩阵的大小为。,一、基本原理,2.监督矩阵,定义,对于某代数分组码集合V，若存在矩阵，满足：,对所有的允许码字，有,对所有的禁用码字，有,则称矩阵为码字集合V的监督矩阵。,则称为标准监督矩阵。,一、基本原理,2.监督矩阵,意义,(1)给出了码集合中码字的生成规则。,监督矩阵是汉明码中一个重要的概念，其作用为：,一、基本原理,2.监督矩阵,意义,监督矩阵是汉明码中一个重要的概念，其作用为：,(2)用于检错。,若则码字一定有错；,若则“认为”码字无错。,记再由s与的关系完成纠错。,其中,或者,(信息元),解,若收到的码字为011，,若收到的码字为101，,若收到的码字为110，,则有,则有,则有,则有,(有错),(有错),(有错),其中,将上式进一步改写为矩阵形式，即得：,即：,例,给出正反码的监督矩阵。,由此即得监督矩阵为：,解,例,给出正反码的监督矩阵。,解,由此即得监督矩阵为,若收到的码字为，,(认为无错),若收到的码字为，,(有错),(有错),则有,则有,有,二、译码纠错,译码纠错的一般准则,从而将译为码字。,直接使用最小距离准则的缺点,计算量较大,距离，并进行比较。,最小距离准则,需要计算收到的码字与所有允许码字的汉明,下面将介绍如何利用监督矩阵进行纠错译码。,回顾,二、译码纠错,设收到的码字为,令，,(1)监督矩阵是一个大小为的矩阵。,其中，n为码长，k为信息元的长度。,(2)监督矩阵用来对码字进行监督(即检错)。,下面进一步看看向量与码字中码元出错的关系。,1.错误图样,二、译码纠错,收到的码字为记,令,称为错误图样。,错误图样反映了码字中各码元的错误情况：,推导,故,1.错误图样,二、译码纠错,向量与错误图样的关系,有,因此有,2.纠(一位)错,二、译码纠错,分析,根据关系式有,(矩阵的第j列),则,则,2.纠(一位)错,二、译码纠错,方法,(1)对于收到的码字，计算,(2)若则“认为”码字无错；,则“认为”码字的第j个码元有错。,若即s正好等于矩阵的第j列，,(2)对监督矩阵有何要求？,故该汉明码是一个(6,3)码，,设其码字为,长度为6的码字。,因此有,即每3位信息元对应到一个,则有,解,因此，以为信息位，为监督位，,即,则可由上述生成关系得到相应的系统码。,例,已知某汉明码的监督矩阵为,(1)求序列的汉明码；,(2)若收到的码字为，问该码字是否有错？,设其码字为则有,解,先将其按每3位分段，再分别进行编码：,即得输出的编码序列为,例,已知某汉明码的监督矩阵为,(1)求序列的汉明码；,(2)若收到的码字为，问该码字是否有错？,(1)对于输入的消息序列，,解,事实上，可以事先编好所有的码字，得到码字集合。,例,已知某汉明码的监督矩阵为,(1)求序列的汉明码；,(2)若收到的码字为，问该码字是否有错？,(2)对于收到的码字，,解,例,已知某汉明码的监督矩阵为,(1)求序列的汉明码；,(2)若收到的码字为，问该码字是否有错？,故码字的第二位有错，应纠正为,故该汉明码是一个(5,2)码，,长度为5的码字。,设其码字为则有,因此有,即每两位信息元对应到一个,解,设其码字为则有,因此，以为信息位，为监督位，,即,则可由上述生成关系得到相应的非系统码。,(1)求序列的汉明码；,例,已知某汉明码的监督矩阵为,(2)若收到的码字为，问该码字是否有错？,解,先将其按每两位分段，再分别进行编码：,即得输出的编码序列为:,(1)求序列的汉明码；,例,已知某汉明码的监督矩阵为,(2)若收到的码字为，问该码字是否有错？,(1)对于输入的序列，,解,(2)对于收到的码字，,故码字的第四位有错，应纠正为,(1)求序列的汉明码；,例,已知某汉明码的监督矩阵为,(2)若收到的码字为，问该码字是否有错？,附：关于监督矩阵的初等变换。,不改变方程的解。,而初等行变换,以第2,4位为信息位：,以第1,2位为信息位：,事实上，信息位(即自由变量)的选取并不是规定的，,其选取原则是能够很容易地得到监督位。,关于监督矩阵的初等