第11章差错控制编玛 码距和检纠错能力的关系 ▣一种编码的最小码距d的大小直接关系着这种编码的检错 和纠错能力 口为检测e个错码，要求最小码距d≥e+1 【证】设一个码组A位于O点。若码组A中发生一个错码， 则我们可以认为A的位置将移动至以O点为圆心，以1为半 径的圆上某点，但其位置不会超出此圆。 若码组A中发生两位错码，则其位置不会超出以O点为圆 心，以2为半径的圆。因此，只要最小码距不小于3，码组 A发生两位以下错码时， 不可能变成另一个准用 码组，因而能检测错码 汉明距离 的位数等于2。 do 16
16 第11章差错控制编码 ◆ 码距和检纠错能力的关系 一种编码的最小码距d0的大小直接关系着这种编码的检错 和纠错能力 为检测e个错码，要求最小码距 d0 e + 1 【证】设一个码组A位于O点。若码组A中发生一个错码， 则我们可以认为A的位置将移动至以O点为圆心，以1为半 径的圆上某点，但其位置不会超出此圆。 若码组A中发生两位错码，则其位置不会超出以O点为圆 心，以2为半径的圆。因此，只要最小码距不小于3，码组 A发生两位以下错码时， 不可能变成另一个准用 码组，因而能检测错码 的位数等于2。 0 1 2 3 A B 汉明距离 e d0
第11章差错控制编玛 同理，若一种编码的最小码距为do,则将能检测(d,-1)个错 码。反之，若要求检测个错码，则最小码距d,至少应不小于 (e+1)。 ▣为了纠正个错码，要求最小码距d,≥2t+1 【证】图中画出码组A和B的距离为5。码组4或B若发生不多于 两位错码，则其位置均不会超出半径为2以原位置为圆心的 圆。这两个圆是不重叠的。判决规则为：若接收码组落于以 A为圆心的圆上就判决收到的是码组A,若落于以B为圆心的 圆上就判决为码组B。 这样，就能够纠 正两位错码。 汉明距离
17 第11章差错控制编码 同理，若一种编码的最小码距为d0，则将能检测(d0 - 1)个错 码。反之，若要求检测e个错码，则最小码距d0至少应不小于 ( e + 1)。 为了纠正t个错码，要求最小码距d0 2t + 1 【证】图中画出码组A和B的距离为5。码组A或B若发生不多于 两位错码，则其位置均不会超出半径为2以原位置为圆心的 圆。这两个圆是不重叠的。判决规则为：若接收码组落于以 A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的 圆上就判决为码组B。 这样，就能够纠 正两位错码。 B t A 汉明距离 0 1 2 3 4 5 t d0
第11章差错控制编玛 若这种编码中除码组A和B外，还有许多种不同码组，但任两 码组之间的码距均不小于5，则以各码组的位置为中心以2为 半径画出之圆都不会互相重叠。这样，每种码组如果发生不 超过两位错码都将能被纠正。因此，当最小码距d,=5时，能 够纠正2个错码，且最多能纠正2个。若错码达到3个，就将 落入另一圆上，从而发生错判。故一般说来，为纠正个错码 最小码距应不小于(2t+1)。 18
18 第11章差错控制编码 若这种编码中除码组A和B外，还有许多种不同码组，但任两 码组之间的码距均不小于5，则以各码组的位置为中心以2为 半径画出之圆都不会互相重叠。这样，每种码组如果发生不 超过两位错码都将能被纠正。因此，当最小码距d0＝5时，能 够纠正2个错码，且最多能纠正2个。若错码达到3个，就将 落入另一圆上，从而发生错判。故一般说来，为纠正t个错码， 最小码距应不小于(2t + 1)
第11章差错控制编马 ▣为纠正个错码，同时检测个错码，要求最小码距 d,≥e+t+1 (e>t) 例图中码组4和B之间距离为5。按照检错能力公式，最多能 检测4个错码，即e=d-1=5-1=4,按照纠错能力公式纠 错时，能纠正2个错码。但是，不能同时作到两者，因为当 错码位数超过纠错能力时，该码组立即进入另一码组的圆内 而被错误地“纠正”了。例如，码组4若错了3位，就会被误 认为码组B错了2位造成的结果，从而被 错"纠”为B。这就 是说，检错和纠错 公式不能同时成立 汉明距离 或同时运用。 19
19 第11章差错控制编码 为纠正t个错码，同时检测e个错码，要求最小码距 例图中码组A和B之间距离为5。按照检错能力公式，最多能 检测4个错码，即e = d0 – 1 = 5 – 1 = 4，按照纠错能力公式纠 错时，能纠正2个错码。但是，不能同时作到两者，因为当 错码位数超过纠错能力时，该码组立即进入另一码组的圆内 而被错误地“纠正”了。例如，码组A若错了3位，就会被误 认为码组B错了2位造成的结果，从而被 错“纠”为B。这就 是说，检错和纠错 公式不能同时成立 或同时运用。 1 ( ) 0 d e +t + e t B t A 汉明距离 0 1 2 3 4 5 t d0
第1】章差错控制编玛 为了在可以纠正t个错码的同时，能够检测个错码，就需 要像下图所示那样，使某一码组（譬如码组A)发生个错 误之后所处的位置，与其他码组（譬如码组B)的纠错圆 圈至少距离等于1，不然将落在该纠错圆上从而发生错误 地“纠正”。因此，由此图可以直观看出，要求最小码距 d≥e+t+1 (e>t) 汉明距离 这种纠错和检错结合的工作方式简称纠检结合。 20
20 第11章差错控制编码 为了在可以纠正t个错码的同时，能够检测e个错码，就需 要像下图所示那样，使某一码组（譬如码组A）发生e个错 误之后所处的位置，与其他码组（譬如码组B）的纠错圆 圈至少距离等于1，不然将落在该纠错圆上从而发生错误 地“纠正”。因此，由此图可以直观看出，要求最小码距 这种纠错和检错结合的工作方式简称纠检结合。 A B e 1 t t 汉明距离 1 ( ) 0 d e +t + e t