一般概念一致监督方程和一致监督矩阵线性分组码市公开课一等奖百校联赛特等奖课件.pptx

5.1 普通概念5.2 一致监督方程和一致监督矩阵5.3 线性分组码生成矩阵5.4 线性分组码编码5.5 线性分组码最小距离、检错和纠错能力5.6 线性分组码译码5.7 线性分组码性能5.8 汉明码5.9 由已知码结构新码方法5.10 线性分组码码限第5章 线性分组码1第1页l线性分组码编码线性分组码编码：线性分组码编码过程分为两步：l把信息序列按一定长度分成若干信息码组，每组由 k 位组成；l编码器按照预定线性规则线性规则(可由线性方程组要求)，把信息码组变换成 n 重(nk)码字，其中(nk)个附加码元是由信息码元线性运算线性运算产生。l信息码组长 k 位，有 2k 个不一样信息码组，则有 2k 个码字与它们一一对应。5.1 普通概念2第2页l名词解释l线性分组码：经过预定线性运算将长为 k 位信息码组变换成 n 重码字(nk)。由 2k 个信息码组所编成 2k个码字集合，称为线性分组码线性分组码。l码矢码矢：一个 n 重码字能够用矢量来表示C=(Cn1,Cn1,C1,C0)所以码字又称为码矢。l(n,k)线性码线性码：信息位长为 k，码长为 n 线性码。l编码效率编码效率/编码速率编码速率/码率码率/传信率传信率：R=k/n。它说明了信道利用效率，R是衡量码性能一个主要参数是衡量码性能一个主要参数。5.1 普通概念3第3页(1)一致监督方程l编码就是给已知信息码组按预定规则添加监督码元，以组成码字。l在 k 个信息码元之后附加 r(r=nk)个监督码元，使每个监督元是其中一些信息元模2和。l举例：k=3,r=4，组成(7,3)线性分组码。设码字为l(C6,C5,C4,C3,C2,C1,C0)lC6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”l监督元可按下面方程组计算5.2 一致监督方程和一致监督矩阵4第4页l一致监督方程一致监督方程/一致校验方程一致校验方程：确定信息元得到监督元规则一组方程称为监督方程/校验方程。因为全部码字都按同一规则确定，又称为一致监督方程/一致校验方程。l因为一致监督方程是线性线性，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定分组码是线性线性分组码分组码。5.2 一致监督方程和一致监督矩阵5第5页(2)举例l信息码组(101)，即C6=1,C5=0,C4=1l代入(5.1)得：C3=0,C2=0,C1=1,C0=1l由信息码组(101)编出码字为 (1010011)。其它7个码字如表5.1。6.2 一致监督方程和一致监督矩阵6第6页(3)一致监督矩阵l为了运算方便，将式(5.1)监督方程写成矩阵形式，得l式(5.2)可写成 H CT=0T或 C HT=0 CT、HT、0T分别表示C、H、0转置矩阵。5.2 一致监督方程和一致监督矩阵7第7页l系数矩阵 H 后四列组成一个(44)阶单位子阵，用 I4 表示，H 其余部分用 P 表示5.2 一致监督方程和一致监督矩阵8第8页l推广到普通情况：对(n,k)线性分组码，每个码字中 r(r=nk)个监督元与信息元之间关系可由下面线性方程组确定5.2 一致监督方程和一致监督矩阵9第9页l令上式系数矩阵为 H，码字行阵列为 C5.2 一致监督方程和一致监督矩阵10第10页(4)一致监督矩阵特征l对H 各行实施初等变换，将后面 r 列化为单位子阵，于是得到下面矩阵，行变换所得方程组与原方程组同解。l监督矩阵监督矩阵H 标准形式标准形式：后面 r 列是一单位子阵监督矩阵H。lH 阵每一行都代表一个监督方程，它表示与该行中“1”相对应码元模2和为0。5.2 一致监督方程和一致监督矩阵11第11页lH 标准形式还说明了对应监督元是由哪些信息元决定。比如(7,3)码H 阵第一行为(1011000)，说明此码第一个监督元等于第一个和第三个信息元模2和，依这类推。lH 阵 r 行代表了 r 个监督方程，也表示由H 所确定码字有 r 个监督元。l为了得到确定码，r 个监督方程（或H 阵r 行）必须是线性独立，这要求H 阵秩为 r。l若把H 阵化成标准形式，只要检验单位子阵秩，就能方便地确定H 阵本身秩。5.2 一致监督方程和一致监督矩阵12第12页(1)线性码封闭性l线性码封闭性：线性码任意两个码字之和仍是一个码字。l定理5.1：设二元线性分组码 CI(CI表示码字集合)是由监督矩阵H所定义，若 U 和 V 为其中任意两个码字，则 U+V 也是 CI中一个码字。l证实：因为 U 和 V 是码 CI 中两个码字，故有HUT=0T，HVT=0T 那么 H(U+V)T=H(UT+VT)=HUT+HVT=0T 即 U+V 满足监督方程，所以 U+V 一定是一个码字。l一个长为 n 二元序列能够看作是GF(2)(二元域)上 n 维线性空间中一点。长为 n 全部 2n 个矢量集合组成了GF(2)上 n 维线性空间Vn。把线性码放入线性空间中进行研究，将使许多问题简化而比较轻易处理。l(n,k)线性码是 n 维线性空间Vn中一个 k 维子空间 Vk。5.3 线性分组码生成矩阵13第13页(2)线性分组码生成矩阵l在由(n,k)线性码组成线性空间 Vn k 维子空间中，一定存在 k 个线性独立码字：g1,g2,gk,。码 CI 中其它任何码字C都能够表为这 k 个码字一个线性组合，即5.3 线性分组码生成矩阵14第14页lG中每一行 gi=(gi1,gi2,gin)都是一个码字；l对每一个信息组m，由矩阵G都能够求得(n,k)线性码对应码字。l生成矩阵生成矩阵：因为矩阵 G 生成了(n,k)线性码，称矩阵 G 为(n,k)线性码生成矩阵。l(n,k)线性码每一个码字都是生成矩阵 G 行矢量线性组合，所以它 2k 个码字组成了由 G 行张成 n 维空间一个 k 维子空间 Vk。5.3 线性分组码生成矩阵15第15页l线性系统分组码 经过行初等变换，将 G 化为前 k 列是单位子阵标准形式 5.3 线性分组码生成矩阵16第16页l线性系统分组码：用标准生成矩阵 Gkn 编成码字，前面 k 位为信息数字，后面 r=nk 位为校验字，这种信息数字在前校验数字在后线性分组码称为线性系统分组码。l当生成矩阵 G 确定之后，(n,k)线性码也就完全被确定了，只要找到码生成矩阵，编码问题也一样被处理了。5.3 线性分组码生成矩阵17第17页(3)举例 (7,4)线性码生成矩阵为5.3 线性分组码生成矩阵18第18页(4)生成矩阵与一致监督矩阵关系l因为生成矩阵G每一行都是一个码字，所以G 每行都满足HrnCTn1=0Tr1，则有HrnGTnk=0Trk 或 GknHTnr=0krl线性系统码监督矩阵 H 和生成矩阵 G 之间能够直接交换。5.3 线性分组码生成矩阵19第19页l举例 已知(7,4)线性系统码监督矩阵为5.3 线性分组码生成矩阵20第20页(5)对偶码l对偶码：对一个(n,k)线性码 CI，因为HrnGTnk=0Trk，假如以G 作监督矩阵，而以H 作生成矩阵，可结构另一个码CId，码CId是一个(n,nk)线性码，称码CId为原码对偶码。l比如：(7,4)线性码对偶码是(7,3)码：l(7,3)码监督矩阵H(7,3)是(7,4)码生成矩阵G(7,4)5.3 线性分组码生成矩阵21第21页l(7,3)码生成矩阵 G(7,3)是(7,4)码监督矩阵 H(7,4)5.3 线性分组码生成矩阵22第22页l(n,k)线性码编码就是依据线性码监督矩阵或生成矩阵将长为将长为 k 信息组变换成长为信息组变换成长为 n(nk)码字码字。l利用监督矩阵结构(7,3)线性分组码编码电路：l设码字矢量为C=(C6 C5C4C3C2C1C0)l码监督矩阵为5.4 线性分组码编码23第23页l依据方程组可直接画出(7,3)码并行编码电路行串行编码电路，如图5.2。5.4 线性分组码编码24第24页(1)汉明距离、汉明重量和汉明球l汉明距离汉明距离/距离距离：在(n,k)线性码中，两个码字 U、V 之间对应码元位上符号取值不一样个数，称为码字 U、V 之间汉明距离。l比如：(7,3)码两个码字 U=0011101,V=0100111，它们之间第2、3、4和6位不一样。所以，码字 U 和 V 距离为4。l线性分组码一个码字对应于 n 维线性空间中一点，码字间距离即为空间中两对应点距离。所以，码字间距离满足普通距离公理：5.5 线性分组码最小距离、检错和纠错能力25第25页l最小距离/dmin：在(n,k)线性码码字集合中，任意两个码字间距离最小值，叫做码最小距离。若C(i)和C(j)是任意两个码字，则码最小距离表示为l码最小距离是衡量码抗干扰能力（检、纠错能力）主要参数。码最小距离越大，码抗干扰能力就越强。码最小距离越大，码抗干扰能力就越强。l汉明球：以码字C为中心，半径为 t 汉明球是与 C 汉明距离 t 向量全体 SC(t)任意两个汉明球不相交最大程度取决于任意两个码字之间最小汉任意两个汉明球不相交最大程度取决于任意两个码字之间最小汉明距离明距离dmin。5.5 线性分组码最小距离、检错和纠错能力26第26页 5.5 线性分组码最小距离、检错和纠错能力27第27页l汉明重量/码字重量/W：码字中非0码元符号个数，称为该码字汉明重量。l在二元线性码中，码字重量就是码字中含“1”个数。l最小重量/Wmin：线性分组码CI中，非0码字重量最小值，叫做码CI最小重量：Wmin=minW(V),VCI,V0l最小距离最小距离与最小重量最小重量关系：线性分组码最小距离等于它最小重量。证实：设线性码CI，且UCI,VCI，又设UV=Z，由线性码封闭性知，ZCI。所以，d(U,V)=W(Z)，由此可推知，线性分组码最小距离必等于非0码字最小重量。5.5 线性分组码最小距离、检错和纠错能力28第28页(2)最小距离与检、纠错能力l普通地说，线性码最小距离越大，意味着任意码字间差异越大，则码检、纠错能力越强。l检错能力：假如一个线性码能检出长度l 个码元任何任何错误图样错误图样，称码检错能力为 l。l纠错能力：假如线性码能纠正长度t 个码元任意错误任意错误图样图样，称码纠错能力为 t。5.5 线性分组码最小距离、检错和纠错能力29第29页l最小距离与纠错能力：(n,k)线性码能纠 t 个错误充要条件是码最小距离为 证实：设：发送码字为V；接收码字为R；U为任意其它码字；则：矢量V、R、U间满足距离三角不等式，d(R,V)+d(R,U)d(U,V)(5.16)设：信道干扰使码字中码元发生错误实际个数为 t，且tt d(R,V)tt (5.17)因为d(U,V)dmin=2t+1，代入式(5.16)得 d(R,U)d(U,V)d(R,V)=2t+1tt (5.18)5.5 线性分组码最小距离、检错和纠错能力30第30页 上式表明：假如接收字 R 中错误个数 tt，那么接收字 R 和发送字 V 间距离t，而与其它任何码字间距离都大于 t，按最小距离译码把R译为V。此时译码正确，码字中错误被纠正。几何意义：5.5 线性分组码最小距离、检错和纠错能力31第31页l最小距离与检错能力：(n,k)线性码能够发觉 l 个错误充要条件是码最小距离为 dmin=l+1 或 l=dmin1 (5.19)证实：设：发送码字为 V；接收码字为 R；U 为任意其它码字；则：矢量V、R、U间满足距离三角不等式，d(R,V)+d(R,U)d(U,V)(5.20)设：信道干扰使码字中码元发生错误实际个数为 l，且ll d(R,V)ll (5.21)因为d(U,V)dmin=l+1，代入式(6.2.20)得 d(R,U)d(U,V)d(R,V)=l+1l0 (5.22)5.5 线性分组码最小距离、检错和纠错能力32第32页 上式表明：因为接收字 R 与其它任何码字 U 距离都大于0，则说明接收字 R 不会因发生 l 个错误变为其它码字，因而必能发觉错误。几何意义：5.5 线性分组码最小距离、检错和纠错能力33第33页l最小距离与检、纠错能力：(n,k)线性码能纠 t 个错误，并能发觉 l 个错误(lt)充要条件是码最小距离为 dmin=t+l+1 或 t+l=dmin1 (5.23)证实：因为dmin2t+1，依据最小距离与纠错能力定理，该码可纠 t 个错误。因为dminl+1，依据最小距离与检错能力定理，该码有检 l 个错误能力。纠错和检错不会发生混同：设发送码字为 V，接收字为 R，实际错误数为 l，且 tt+1t (5.24)因而不会把 R 误纠为 U。5.5 线性分组码最小距离、检错和纠错能力34第34页 几何意义：5.5 线性分组码最小距离、检错和纠错能力35第35页5.5 线性分组码最小距离、检错和纠错能力36第36页l当(n,k)线性码最小距离 dmin 给定后，可按实际需要灵活安排纠错数目。比如，对 dmin=8 码，可用来纠3检4错，或纠2检5错，或纠1检6错，或者只用于检7个错误。5.5 线性分组码最小距离、检错和纠错能力37第37页(3)线性码最小距离与监督矩阵关系l定理5.2：设 H 为(n,k)线性码一致监督矩阵，若 H 中任意 S 列线性无关，而 H 中存在(S+1)列线性相关，则码最小距离为(S+1)。（矩阵 H 秩为S）l定理5.3：若码最小距离为(S+1)，则该码监督矩阵任意 S 列线性无关，而必存在有相关(S+1)列。l定理5.4：在二元线性码监督矩阵 H 中，假如任一列都不是全“0”，且任两列都不相等，则该码能纠一个错误。5.5 线性分组码最小距离、检错和纠错能力38第38页(1)伴随式和错误检测 用监督矩阵编码，也用监督矩阵译码：接收到一个接收字 R 后，校验 HRT=0T 是否成立：l若关系成立，则认为 R 是一个码字；l不然判为码字在传输中发生了错误；lHRT值是否为0是校验码字犯错是否依据。伴随式/监督子/校验子：S=RHT或ST=HRT。怎样纠错？l设发送码矢 C=(Cn1,Cn2,C0)l信道错误图样为 E=(En1,En2,E0)，l其中Ei=0，表示第i位无错；lEi=1，表示第i位有错。i=n1,n2,0。5.6 线性分组码译码39第39页l接收字 R 为R=(Rn1,Rn2,R0)=C+E =(Cn1+En1,Cn2+En2,C0+E0)l求接收字伴随式（接收字用监督矩阵进行检验）ST=HRT=H(C+E)T=HCT+HET (5.25)l因为HCT=0T，所以 ST=HETl设H=(h1,h2,hn)，其中hi表示H列。代入式(5.25)得到5.6 线性分组码译码40第40页 总结l伴随式仅与错误图样相关，而与发送详细码字无关，即伴随式仅由错误图样决定；l伴随式是错误判别式：l若S=0，则判为没有犯错，接收字是一个码字；l若S0，则判为有错。l不一样错误图样含有不一样伴随式，它们是一一对应。对二元码，伴随式是H 阵中与错误码元对应列之和。5.6 线性分组码译码41第41页 举例：(7,3)码接收矢量 R 伴随式计算l设发送码矢C=1010011，接收码字R1010011，R与C相同。5.6 线性分组码译码42第42页l若接收字中有一位错误5.6 线性分组码译码43第43页l当码元错误多于1个时5.6 线性分组码译码44第44页 伴随式计算电路l伴随式计算可用电路来实现。l以(7,3)码为例：设接收字为R=(R6R5R4R3R2R1R0)，伴随式为l依据上式可画出伴随式计算电路，如图5.7所表示。5.6 线性分组码译码45第45页l依据上式可画出伴随式计算电路，如图5.7所表示。5.6 线性分组码译码46第46页1：设 H 为一个(n,k)线性码 CI 一致监督矩阵，且有奇数最小距离为 d。作一个新码 CI，它监督矩阵为 证实(1)CI是一个(n+1,k)码；(2)CI中每个码字重 量为偶数；(3)CI最小重量为d+1。2：已知(7,4)汉明码生成矩阵为 (1)求该码全部码字；(2)求该码监督矩阵；(3)若接收码字为1101101，计算伴随式。课外思索题47第47页3：已知(8,4)系统线性码监督方程为 式中m=(m3,m2,m1,m0)为信息矢量，C3,C2,C1,C0为编码监督数字，求这个码监督矩阵和生成矩阵，证实该码最小距离为4。作 业48第48页