信息科学第五章2课件

差错率：差错率是衡量传输质量的重要指标之一，它有以下几种不同的定义。码元差错率：指在传输的码元总数中发生差错的码元数所占的比例（平均值），简称误码率。比特差错率

/比特误码率：指在传输的比特总数中发生差错的比特数所占的比例（平均值）。在二进制传输系统中，码元差错率就是比特差错率。码组差错率：指在传输的码组总数中发生差错的码组数所占的比例（平均值）。第五节纠错编码的基本思想根据不同的应用场合对差错率有不同的要求。在电报传送时，允许的比特差错率约为10－4～10－5；计算机数据传输，一般要求比特差错率小于10－8～10－9；在遥控指令和武器系统的指令系统中，要求有更小的误比特率或码组差错率。采用信道编码的数字通信系统在某些情况下，信道的改善可能较困难或者不经济，这就要求采用信道编码，以便满足系统差错率的技术指标要求。信道编码为系统设计者提供了一个降低系统差错率的措施。采用信道编码后的数字通信系统可用图6.1.2所示。二进制编码信道模型：

R=C+E

(mod2)E：随机变量；差错图案：随机序列(Ei)；称E=(E0,E1,…,En-1)中Ei=1为第i位上的一个随机错误；第i至第j位之间有很多错误时，称为一个j－i+1长的突发错误。(2)信道编码的基本思想信道编码的对象：是信源编码器输出的信息序列m。通常是二元符号1、0组成的序列。信道编码的基本思想按一定规则给数字序列m增加一些多余的码元，使不具有规律性的信息序列m变换为具有某种规律性的数码序列C；码序列中的信息序列码元与多余码元之间是相关的；信道译码器利用这种预知的编码规则译码。检验接收到的数字序列R是否符合既定的规则，从而发现R中是否有错，或者纠正其中的差错；码元的组成及其它们之间的关系信息码组：数字序列m总是以k个码元为一组传输，称这k个码元的码组为信息码组。例如遥控系统中的每个指令字，计算机中的每个字节。码组/码字：信道编码器按一定的规则对每个信息码组附加一些多余的码元，构成了n个码元的码组。监督码元/监督元：附加的(n－k)

个码元称为该码组的监督码元或监督元。是否可用线性方程组来表示线性码：编码规则可以用线性方程表示；非线性码：编码规则不能用线性方程表示；按码字的结构分系统码：前k个码元与信息码组一致；非系统码：没有系统码的特性。按纠正差错的类型可分为纠正随机错误的码和纠正突发错误的码；按码字中每个码元的取值可分为二进制码和多进制码。(1)偶（或奇）校验方法p为偶校验位m0+m1+m2+…+mk－1+p=0(mod2)则C=(m0,m1,m2,…,mk－1,p)为一个偶校验码字。C中一定有偶数个“1”当差错图案E中有奇数个“1”，即R

中有奇数个位有错时，可以通过校验方程是否为0判断有无可能传输差错。(2)多个奇偶校验位一个校验位可以由信息位的部分或全部按校验方程产生；例如C是一个对阵列消息进行垂直与水平校验以及总校验的码字；其码率为当校验位数增加时，可以检测到差错图案种类数也增加，同时码率减小。(4)等重码/定比码设计码字中的非0符号个数恒为常数，即C由全体重量恒等于m的n重向量组成。5中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错。(1)差错控制的基本方式前向纠错(FEC)：发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，若传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。自动请求重发(ARQ)：用于检测的纠错码在译码器输出端只给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字全部或部分。混合纠错(HEC)：是FEC与ARQ方式的结合。发端发送同时具有自动纠错和检测能力的码组，收端收到码组后，检查差错情况，如果差错在码的纠错能力以内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。编码增益实际的通信系统，信号的传送需要一定的信噪比Eb/N0，它直接影响信道转移概率的大小，误码率pbe与信噪比Eb/N0的关系如图6.1.9所示，当采用纠错码之后，达到同样的误码率需要的信噪比减小量称为编码增益。(1)一致监督方程编码就是给已知信息码组按预定规则添加监督码元，以构成码字。在k个信息码元之后附加r(r=n－k)个监督码元，使每个监督元是其中某些信息元的模2和。举例：k=3,r=4，构成(7,3)线性分组码。设码字为(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”监督元可按下面方程组计算一致监督方程/一致校验方程：确定信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。由于一致监督方程是线性的，即监督元和新信源之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。(2)举例信息码组(101)，即C6=1,C5=0,C4=1代入监督方程得：C3=0,C2=0,C1=1,C0=1由信息码组(101)编出的码字为(1010011)。其它7个码字如表6.2.1。系数矩阵H的后四列组成一个(4×4)阶单位子阵，用I4表示，H的其余部分用P表示推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由下面的线性方程组确定令上式的系数矩阵为H，码字行阵列为CG中每一行gi=(gi1,gi2,…,gin)都是一个码字；对每一个信息组m，由矩阵G都可以求得(n,k)线性码对应的码字。(n,k)线性码的每一个码字都是生成矩阵G的行矢量的线性组合，所以它的2k个码字构成了由G的行张成的n维空间的一个k维子空间Vk。线性系统分组码通过行初等变换，将G化为前k列是单位子阵的标准形式

(4)生成矩阵与一致监督矩阵的关系由于生成矩阵G的每一行都是一个码字，所以G的每行都满足Hr×nCTn×1=0Tr×1，则有Hr×nGTn×k=0Tr×k

或Gk×nHTn×r=0k×r线性系统码的监督矩阵H和生成矩阵G之间可以直接互换。举例已知(7,4)线性系统码的监督矩阵为(5)对偶码对偶码：对一个(n,k)线性码CI，由于Hr×nGTn×k=0Tr×k，如果以G作监督矩阵，而以H作生成矩阵，可构造另一个码CId，码CId是一个(n,n－k)线性码，称码CId为原码的对偶码。例如：(7,4)线性码的对偶码是(7,3)码：(7,3)码的监督矩阵H(7,3)是(7,4)码生成矩阵G(7,4)

(7,3)码的生成矩阵G(7,3)是(7,4)码监督矩阵H(7,4)

(1)汉明重量和汉明球汉明距离/距离：在(n,k)线性码中，两个码字U、V之间对应码元位上符号取值不同的个数，称为码字U、V之间的汉明距离。例如：(7,3)码的两个码字U=0011101,V=0100111，它们之间第2、3、4和6位不同。因此，码字U和V的距离为4。线性分组码的一个码字对应于n维线性空间中的一点，码字间的距离即为空间中两对应点的距离。汉明重量和汉明球汉明球：以码字C为中心，半径为t的汉明球是与C的汉明距离≤

t的向量全体SC(t)

线性分组码的最小距离、检错和纠错能力汉明重量/码字重量/W：码字中非0码元符号的个数，称为该码字的汉明重量。在二元线性码中，码字重量就是码字中含“1”的个数。最小重量/Wmin：线性分组码CI中，非0码字重量最小值，叫做码CI的最小重量：Wmin=min{W(V),V∈CI,V≠0}最小距离与最小重量的关系：线性分组码的最小距离等于它的最小重量。

(2)最小距离与检、纠错能力一般地说，线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。检错能力：如果一个线性码能检出长度≤l个码元的任何错误图样，称码的检错能力为l。纠错能力：如果线性码能纠正长度≤t个码元的任意错误图样，称码的纠错能力为t。最小距离与纠错能力：(n,k)线性码能纠t个错误的充要条件是码的最小距离为

几何意义：最小距离与检错能力：(n,k)线性码能够发现l个错误的充要条件是码的最小距离为dmin=l+1或l=dmin－1最小距离与检、纠错能力：(n,k)线性码能纠t个错误，并能发现l个错误(l>t)的充要条件是码的最小距离为dmin=t+l+1或t+l=dmin－1(1)伴随式和错误检测①用监督矩阵编码，也用监督矩阵译码：接收到一个接收字R后，校验HRT=0T是否成立：若关系成立，则认为R是一个码字；否则判为码字在传输中发生了错误；②伴随式/监督子/校验子：S=RHT或ST=HRT。③如何纠错？设发送码矢C=(Cn－1,Cn－2,…,C0)信道错误图样为E=(En－1,En－2,…,E0)，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。i=n－1,n－2,…,0。接收字R为R=(Rn－1,Rn－2,…,R0)=C+E=(Cn－1+En－1,Cn－2+En－2,…,C0+E0)求接收字的伴随式（接收字用监督矩阵进行检验）ST=HRT=H(C+E)T=HCT+HET由于HCT=0T，所以ST=HET⑤举例：(7,3)码接收矢量R的伴随式计算设发送码矢C=1010011，接收码字R＝1010011，R与C相同。若接收字中有一位错误当码元错误多于1个时②标准阵列码矢参数发送码矢：取自于2k个码字集合{C}；接收矢量：可以是2n个n重中任一个矢量。译码方法把2n个n重矢量划分为2k个互不相交的子集，使得在每个子集中仅含一个码矢；根据码矢和子集间一一对应关系，若接收矢量Rl落在子集Dl中，就把Rl译为子集Dl含有的码字Cl；当接收矢量R与实际发送码矢在同一子集中时，译码就是正确的。标准阵列：是对给定的(n,k)线性码，将2n个n重划分为2k个子集的一种方法。标准阵列构造方法先将2k个码矢排成一行，作为标准阵列的第一行，并将全0码矢C1=(00…0)放在最左面的位置上；然后在剩下的(2n－2k)

个n重中选取一个重量最轻的n重E2放在全0码矢C1下面，再将E2分别和码矢相加，放在对应码矢下面构成阵列第二行在第二次剩下的n重中，选取重量最轻的n重E3，放在E2下面，并将E3分别加到第一行各码矢上，得到第三行；…，继续这样做下去，直到全部n重用完为止。得到(n,k)线性码的标准阵列。定理6.2.6(线性码纠错极限定理)：二元(n,k)线性码能纠2n－k个错误图样。这2n－k个可纠的错误图样，包括0矢量在内，即把无错的情况也看成一个可纠的错误图样。陪集：标准阵列的每一行叫做码的一个陪集。陪集首：每个陪集的第一个元素叫做陪集首。每一列包含2n－k个元素，最上面的是一个码矢，其它元素是陪集首和该码矢之和，例如第j列为若发送码矢为Cj，信道干扰的错误图样是陪集首，则接收矢量R必在Dj

中；若错误图样不是陪集首，则接收矢量R不在Dj

中，则译成其它码字，造成错误译码；当且仅当错误图样为陪集首时，译码才是正确的。可纠正的错误图样：这2n－k个陪集首称为可纠正的错误图样。线性码纠错能力与监督元数目的关系：一个可纠t个错误的线性码必须满足

上式中等式成立时的线性码称为完备码。即

定义：(n,k)线性码的所有2n－k个伴随式，在译码过程中若都用来纠正所有小于等于个随机错误，以及部分大于t的错误图样，则这种译码方法称为完备译码。限定距离译码：任一个(n,k)线性码，能纠正个随机错误，如果在译码时仅纠正t’<t个错误，而当错误个数大于t’时，译码器不进行纠错而仅指出发生了错误，称这种方法为限定距离译码。标准阵列译码=最小距离译码法=最佳译码法陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首；重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的n重作陪集首；这样，当错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码矢间的距离（等于陪集首）最小；因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码；所以标准阵列译码法也是最佳译码法。定理6.2.7：在标准阵列中，一个陪集的所有2k个n重有相同的伴随式，不同的陪集伴随式互不相同。

(1)不可检错误概率pud令Ai为码的重量分布，表示重量为i的码字个数，由于仅当错误图样与码矢集合中的非0码矢相同时，才不能检出错误，所以线性分组码的性能(2)译码错误概率pwe正确译码概率pwc：纠正小于等于t个差错的概率译码错误概率pwe为汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。汉明码的结构参数：纠一个错误的线性码，其最小距离dmin=3；监督矩阵任意两列线性无关/