第六章 有噪信道编码15.ppt

第六章第六章 有噪信道编码有噪信道编码需要掌握的内容：需要掌握的内容：译码规则与错误概率的关系译码规则与错误概率的关系平均差错率与信道编码的关系平均差错率与信道编码的关系汉明距离汉明距离有噪信道编码定理有噪信道编码定理线性分组码线性分组码第一节第一节 译码规则与错误译码概率译码规则与错误译码概率0011信源信源（信源编码，信道编码）（信源编码，信道编码）译码译码（信源译码，信道译码）（信源译码，信道译码）信道信道信宿信宿一一.译码规则译码规则译码函数又称译码函数又称译码函数又称译码函数又称译码规则译码规则译码规则译码规则注意注意:译译码码规规则则是是人人为为定定的的,对对于于同同一一个个信信道道可可有有多多个个不同的译码规则不同的译码规则信信道道译译码码函函数数F F是是是是从从从从输输输输出出出出符符符符号号号号集集集集合合合合B B B B到到到到输输输输入入入入符符符符号号号号集集集集合合合合A A A A的映射的映射的映射的映射定义定义0.80.20.10.9a1a2b1b2例例如如：对对于于二二元元信信道道就就可可制制定定若若干干不不同同译译码码规规则则，如如图所示图所示。“好好”的译码规则的标准是的译码规则的标准是：错误译码概率错误译码概率小小译码正确译码正确-如果接收到如果接收到bj，按，按 译成译成aj*，而输入的刚好是而输入的刚好是aj*bj的译码正确概率为：的译码正确概率为：bj的译码错误概率为：的译码错误概率为：二二.错误译码概率错误译码概率 译码错误概率的统计平均称为译码错误概率的统计平均称为平均译码错误概率平均译码错误概率或或或或平平均差错率，均差错率，记为记为PePe与译码规则与译码规则与译码规则与译码规则F F有关有关有关有关 使使Pe小的译码规则小的译码规则小的译码规则小的译码规则F F是好的译码规则是好的译码规则是好的译码规则是好的译码规则简化简化简化简化Pe式式为下面的形式：为下面的形式：为下面的形式：为下面的形式：当输入等概当输入等概:上式可化为：上式可化为：例例例例6-16-16-16-1：参见下图，假设参见下图，假设P(a1)=0.4,分别求出分别求出4 4种译码规种译码规则所对应的平均差错率。则所对应的平均差错率。0.80.20.10.9a1a2b1b2解解解解：信道输入概率矩阵和转移矩阵分别为：信道输入概率矩阵和转移矩阵分别为：信道输入概率矩阵和转移矩阵分别为：信道输入概率矩阵和转移矩阵分别为：转移矩阵各行元素乘以对应的输入概率，得联合概率矩阵转移矩阵各行元素乘以对应的输入概率，得联合概率矩阵转移矩阵各行元素乘以对应的输入概率，得联合概率矩阵转移矩阵各行元素乘以对应的输入概率，得联合概率矩阵译码规则译码规则译码规则译码规则F F F F1 1 1 1对应的平均差错率为对应的平均差错率为对应的平均差错率为对应的平均差错率为 其它译码规则对应的平均差错率分别为其它译码规则对应的平均差错率分别为其它译码规则对应的平均差错率分别为其它译码规则对应的平均差错率分别为Pe(F2)=0.4 Pe(F2)=0.4 Pe(F2)=0.4 Pe(F2)=0.4 Pe(F3)=0.14Pe(F3)=0.14Pe(F3)=0.14Pe(F3)=0.14Pe(F4)=0.86Pe(F4)=0.86Pe(F4)=0.86Pe(F4)=0.86四种规则相比，四种规则相比，四种规则相比，四种规则相比，F3F3F3F3最好，最好，最好，最好，F4F4F4F4最差最差最差最差第二节第二节 两种典型的译码规则两种典型的译码规则 一一.最佳译码规则最佳译码规则 平均差错率平均差错率平均差错率平均差错率P Pe e与译码规则有关，使与译码规则有关，使与译码规则有关，使与译码规则有关，使Pe达到最小达到最小达到最小达到最小的译码规则的译码规则的译码规则的译码规则最佳译码规则最佳译码规则。可可以以看看出出：要要减减小小Pe，必必须须减减小小各各个个接接收收符符号号的的译译码码错错误误概概率率，或或者者增增大大各各个个接接收收符符号号的的译译码码正正确确概概率。率。确定最佳译码规则的方法：确定最佳译码规则的方法：该最佳译码规则称为该最佳译码规则称为该最佳译码规则称为该最佳译码规则称为最大后验概率译码规则最大后验概率译码规则最大后验概率条件最大后验概率条件最大后验概率条件最大后验概率条件可等价可等价可等价可等价为最大联合概率条件为最大联合概率条件为最大联合概率条件为最大联合概率条件,为什么呢为什么呢?则最佳译码规则又可表示为：则最佳译码规则又可表示为：则最佳译码规则又可表示为：则最佳译码规则又可表示为：最佳译码规则又称为最佳译码规则又称为最佳译码规则又称为最佳译码规则又称为最大联合概率译码规则最大联合概率译码规则例例6-26-2 参见下图，假设参见下图，假设参见下图，假设参见下图，假设P(aP(aP(aP(a1 1 1 1)=0.4)=0.4)=0.4)=0.4，求最佳译码规则，求最佳译码规则，求最佳译码规则，求最佳译码规则。0.80.20.10.9a1a2b1b2解：解：解：解：例例例例6-16-16-16-1已经求出联合概率矩阵，重写为已经求出联合概率矩阵，重写为已经求出联合概率矩阵，重写为已经求出联合概率矩阵，重写为则最大联合概率译码规则为：则最大联合概率译码规则为：则最大联合概率译码规则为：则最大联合概率译码规则为：对应的平均差错概率：对应的平均差错概率：对应的平均差错概率：对应的平均差错概率：按最大转移概率条件确定的译码规则按最大转移概率条件确定的译码规则按最大转移概率条件确定的译码规则按最大转移概率条件确定的译码规则例例例例6-36-36-36-3：已知信道转移矩阵，试确定译码规则。已知信道转移矩阵，试确定译码规则。已知信道转移矩阵，试确定译码规则。已知信道转移矩阵，试确定译码规则。解：按转移概率最大原则确定极大似然译码规则如下：解：按转移概率最大原则确定极大似然译码规则如下：二、极大似然译码规则二、极大似然译码规则原原原原因因因因是是是是：极极极极大大大大似似似似然然然然译译译译码码码码规规规规则则则则是是是是按按按按最最最最大大大大转转转转移移移移概概概概率率率率条条条条件件件件确确确确定定定定的，即的，即的，即的，即如果输入等概，则如果输入等概，则所以所以所以所以当信道输入等概率时，极大似然译码规则是当信道输入等概率时，极大似然译码规则是当信道输入等概率时，极大似然译码规则是当信道输入等概率时，极大似然译码规则是最佳的最佳的。提问提问:为什么为什么为什么为什么?第三节第三节 信道编码的编码原则信道编码的编码原则二元信源和二元对称信道的模型如下图所示二元信源和二元对称信道的模型如下图所示二元信源和二元对称信道的模型如下图所示二元信源和二元对称信道的模型如下图所示DMCXa1,a2Yb1,b2a1=0a2=1b1=0b2=11-p1-pp=0.01p=0.01DMSUu1,u2信源的熵信源的熵信源的熵信源的熵为：为：H H（U U）=logM=1=logM=1比特比特/符号符号信道容量为信道容量为信道容量为信道容量为：C=log2-H(0.99,0.01)=0.92C=log2-H(0.99,0.01)=0.92比特比特/符号符号由图可知：由图可知：信信源源与与信信道道之之间间不不加加信信道道编编码码，则则由由于于信信道道输输入入等等概概分分布布，则则极大似然译码规则就是最佳译码规则，根据信道转移矩阵极大似然译码规则就是最佳译码规则，根据信道转移矩阵确定极大似然译码规则为：确定极大似然译码规则为：平均差错率为：平均差错率为：提问：提问：传输系统的传输系统的传输系统的传输系统的P Pe e要求控制在要求控制在要求控制在要求控制在1010-6-6以下以下以下以下，而利用译而利用译而利用译而利用译码规则的码规则的码规则的码规则的Pe太高太高，如何降低平均差错率呢？如何降低平均差错率呢？如何降低平均差错率呢？如何降低平均差错率呢？信道编码信道编码一一.简单重复编码简单重复编码 对信源符号进行对信源符号进行“重复重复2 2次次”编码编码:信道编码信道编码信道编码信道编码f f f f信道译码信道译码信道译码信道译码F F F F“重复重复重复重复2 2 2 2次次次次”编码规则为编码规则为编码规则为编码规则为 求出求出求出求出3 3 3 3次扩展信道的转移矩阵次扩展信道的转移矩阵次扩展信道的转移矩阵次扩展信道的转移矩阵按极大似然译码规则得译码函数按极大似然译码规则得译码函数按极大似然译码规则得译码函数按极大似然译码规则得译码函数 即：即：译码差错率为译码差错率为译码差错率为译码差错率为：结论结论：信道编码信道编码降低降低平均错误率平均错误率提问：提问：信道编码对信息传输速率有什么影响呢？信道编码对信息传输速率有什么影响呢？信道编码对信息传输速率有什么影响呢？信道编码对信息传输速率有什么影响呢？信道编码，或称为信道编码，或称为信道编码，或称为信道编码，或称为纠错编码纠错编码纠错编码纠错编码，就是靠增加，就是靠增加，就是靠增加，就是靠增加“冗余冗余冗余冗余”码元来克服或减轻噪声影响的。码元来克服或减轻噪声影响的。码元来克服或减轻噪声影响的。码元来克服或减轻噪声影响的。结论结论：信道编码信道编码信道编码信道编码降低降低了信道的信息传输率了信道的信息传输率了信道的信息传输率了信道的信息传输率信道编码之后的信息率或信道待传的信息率为信道编码之后的信息率或信道待传的信息率为信道编码之后的信息率或信道待传的信息率为信道编码之后的信息率或信道待传的信息率为无信道编码的信息率或信道待传的信息率为无信道编码的信息率或信道待传的信息率为无信道编码的信息率或信道待传的信息率为无信道编码的信息率或信道待传的信息率为二二.对符号串编码对符号串编码(矢量编码）矢量编码）例例6-46-4：二二二二元元元元信信信信源源源源U U U U，若若若若取取取取二二二二元元元元符符符符号号号号串串串串“00000000，01010101，10101010，11111111”作作作作为为为为消消消消息息息息，则消息个数增加为则消息个数增加为则消息个数增加为则消息个数增加为M=4M=4M=4M=4。提问：提问：此时平均差错率又发生怎样的变化呢？此时平均差错率又发生怎样的变化呢？结论：结论：增加信源消息个数，可增加信源消息个数，可增加信源消息个数，可增加信源消息个数，可提高提高信道的信息传输率信道的信息传输率信道的信息传输率信道的信息传输率取码长取码长取码长取码长N=3N=3N=3N=3，则编码后的信息率为，则编码后的信息率为，则编码后的信息率为，则编码后的信息率为 R=(log4)/3=2/3 R=(log4)/3=2/3 比特比特比特比特/码元码元码元码元码长码长码长码长N=3N=3N=3N=3，可供选择的码字为，可供选择的码字为，可供选择的码字为，可供选择的码字为选择以下编码函数：选择以下编码函数：选择以下编码函数：选择以下编码函数：根据信道转移矩阵根据信道转移矩阵根据信道转移矩阵根据信道转移矩阵确定极大似然译码规则为确定极大似然译码规则为确定极大似然译码规则为确定极大似然译码规则为 则平均差错率为：则平均差错率为：则平均差错率为：则平均差错率为：结论：结论：增加消息个数增加消息个数增加消息个数增加消息个数M M M M与重复编码相比，在提高信息率的同与重复编码相比，在提高信息率的同与重复编码相比，在提高信息率的同与重复编码相比，在提高信息率的同时会使平均差错率增大时会使平均差错率增大时会使平均差错率增大时会使平均差错率增大。第四节第四节 汉明距离汉明距离 两两个个等等长长符符号号序序列列x和和y之之间间的的汉汉明明距距离离，记记为为D(x,y)，是是x与与y之间对应位置上不同符号的个数。之间对应位置上不同符号的个数。解：解：求汉明距离：求汉明距离：D(x,z)=z)=2;D(y,z)=3因此，因此，z与与x的相似程度的相似程度高于高于与与y的相似程度的相似程度一一.定义定义例例6-56-5：x=100111,=100111,y=111000,=111000,z=111111,=111111,比较比较z与与x和和y的相似的相似程度。程度。X X X X和和和和Y Y Y Y是二元序列，记为是二元序列，记为是二元序列，记为是二元序列，记为 是是是是等等等等长长长长码码码码，则则则则C C C C中中中中任任任任意意意意两两两两个个个个不不不不同同同同码码码码字之间的汉明距离或码间距离为字之间的汉明距离或码间距离为字之间的汉明距离或码间距离为字之间的汉明距离或码间距离为码码码码C C C C的最小码间距离的最小码间距离的最小码间距离的最小码间距离定义为定义为定义为定义为二元对称信道，可以二元对称信道，可以二元对称信道，可以二元对称信道，可以根据汉明距离来决定译码规则根据汉明距离来决定译码规则假如有一个信源有假如有一个信源有假如有一个信源有假如有一个信源有M M M M个消息个消息个消息个消息二二二二元元元元对对对对称称称称信信信信道道道道的的的的输输输输入入入入符符符符号号号号集集集集和和和和输输输输出出出出符符符符号号号号集集集集分分分分别别别别为为为为A=0A=0A=0A=0，1111和和和和B=0B=0B=0B=0，1111。其其其其N N N N次次次次扩扩扩扩展展展展信信信信道道道道的的的的输输输输入入入入符符符符号号号号集集集集和和和和输输输输出出出出符号集分别为：符号集分别为：符号集分别为：符号集分别为：经经经经N N次扩展信道传送之后，按次扩展信道传送之后，按次扩展信道传送之后，按次扩展信道传送之后，按极大似然译码规则进行译码极大似然译码规则进行译码极大似然译码规则进行译码极大似然译码规则进行译码记记记记N N N N长二元符号串为长二元符号串为长二元符号串为长二元符号串为 由信道无记忆可知转移概率为由信道无记忆可知转移概率为由信道无记忆可知转移概率为由信道无记忆可知转移概率为码元错误概率为码元错误概率为p，正确概率为，正确概率为 则有：则有：极大似然译码规则极大似然译码规则等价等价等价等价为最小汉明距离译码规则为最小汉明距离译码规则 最最小小距距离离译译码码规规则则可可在在一一般般信信道道中中采采用用，但但不不一一定定与与极极大大似似然然译译码码规规则则等等价价，只只有有对对于于二二元元对对称称信信道道，它它才才与与极极大大似似然然译译码码规规则则等等价价，并并且且当当输输入入等等概概时是最佳的时是最佳的。对于二元对称信道，若对于二元对称信道，若输入等概输入等概，无论用什么规则确定，无论用什么规则确定译码函数，与之对应的平均差错率都可用译码函数，与之对应的平均差错率都可用汉明距离汉明距离表示：表示：结论：结论：第五节第五节 有噪信道编码定理有噪信道编码定理一一.正定理（香农第二定理）正定理（香农第二定理）若若信信道道是是离离散散、无无记记忆忆、平平稳稳的的，且且信信道道容容量量为为C C，只只要要待待传传送送的的信信息息率率R=CRCRC，就一定，就一定找不到一种信道编码方法，使得码长足找不到一种信道编码方法，使得码长足够大时，平均差错率任意接近于零。够大时，平均差错率任意接近于零。信道编码定理告诉我们：信道编码定理告诉我们：R=CRCRC时，无论如何编码，都不时，无论如何编码，都不可能使平均差错率逼近零。因此，信道容量可能使平均差错率逼近零。因此，信道容量C C是确保可靠性传是确保可靠性传输的信息传输率的上限。输的信息传输率的上限。第六节第六节 纠错编码纠错编码 一一.纠错码分类纠错码分类（1 1 1 1）根据信道中的干扰类型，纠错码分为）根据信道中的干扰类型，纠错码分为）根据信道中的干扰类型，纠错码分为）根据信道中的干扰类型，纠错码分为：反向重传纠错反向重传纠错反向重传纠错反向重传纠错检错编码检错编码检错编码检错编码检错译码检错译码检错译码检错译码信道信道信道信道C CmmR R反馈反馈反馈反馈 前向纠错前向纠错前向纠错前向纠错纠错编码纠错编码纠错编码纠错编码纠错译码纠错译码纠错译码纠错译码信道信道信道信道C CmmR R 混合纠错混合纠错混合纠错混合纠错（2 2 2 2）根据不同的分组方式及随后的映射关系，）根据不同的分组方式及随后的映射关系，）根据不同的分组方式及随后的映射关系，）根据不同的分组方式及随后的映射关系，纠错码分为：纠错码分为：纠错码分为：纠错码分为：分组码分组码分组码分组码:先将信息序列分成先将信息序列分成先将信息序列分成先将信息序列分成K K个符号一组，称为信息组，个符号一组，称为信息组，个符号一组，称为信息组，个符号一组，称为信息组，然后在信息组中加入一些校验码元组成然后在信息组中加入一些校验码元组成然后在信息组中加入一些校验码元组成然后在信息组中加入一些校验码元组成N N N N长码字，长码字，长码字，长码字，该码称为该码称为该码称为该码称为（N N，K K）分组码。分组码。分组码。分组码。（N N，K K）分组码中的任一码字的码长为分组码中的任一码字的码长为分组码中的任一码字的码长为分组码中的任一码字的码长为N N，信息位数为信息位数为信息位数为信息位数为K K，校验位数为，校验位数为，校验位数为，校验位数为n-kn-k。树码树码树码树码:信息序列以每信息序列以每信息序列以每信息序列以每K K K K个码元分段，编码器输出该段的校个码元分段，编码器输出该段的校个码元分段，编码器输出该段的校个码元分段，编码器输出该段的校验码元不仅与本段的验码元不仅与本段的验码元不仅与本段的验码元不仅与本段的K K K K个信息码元有关，而且还与个信息码元有关，而且还与个信息码元有关，而且还与个信息码元有关，而且还与前面若干段的信息码元有关前面若干段的信息码元有关前面若干段的信息码元有关前面若干段的信息码元有关 (3)(3)(3)(3)根据信息码元与校验码元之间是否存在线性根据信息码元与校验码元之间是否存在线性根据信息码元与校验码元之间是否存在线性根据信息码元与校验码元之间是否存在线性 关系，纠错码分为：关系，纠错码分为：关系，纠错码分为：关系，纠错码分为：线性码线性码线性码线性码:非线性码非线性码非线性码非线性码:线性码的校验码元是若干信息码元的线性线性码的校验码元是若干信息码元的线性线性码的校验码元是若干信息码元的线性线性码的校验码元是若干信息码元的线性组合。线性码具有很好的数学结构，编译组合。线性码具有很好的数学结构，编译组合。线性码具有很好的数学结构，编译组合。线性码具有很好的数学结构，编译码比较简单，性能优于具有同样纠错能力码比较简单，性能优于具有同样纠错能力码比较简单，性能优于具有同样纠错能力码比较简单，性能优于具有同样纠错能力的非线性码的非线性码的非线性码的非线性码 非线性码的校验码元与信息码元不满足非线性码的校验码元与信息码元不满足非线性码的校验码元与信息码元不满足非线性码的校验码元与信息码元不满足线性关系线性关系线性关系线性关系 1.1.1.1.生成矩阵和校验矩阵生成矩阵和校验矩阵生成矩阵和校验矩阵生成矩阵和校验矩阵 二二.线性分组码线性分组码有（有（有（有（5 5 5 5，2 2 2 2）分组码）分组码）分组码）分组码,设设设设,其中其中其中其中为信息码元，为信息码元，为信息码元，为信息码元，为校验码元为校验码元为校验码元为校验码元 假设校验码元由下列方程组得到假设校验码元由下列方程组得到假设校验码元由下列方程组得到假设校验码元由下列方程组得到,其其其其中中中中 表示模表示模表示模表示模2 2 2 2加加加加.方程组改写成矩阵形式有方程组改写成矩阵形式有方程组改写成矩阵形式有方程组改写成矩阵形式有:令令令令则则则则:式中式中式中式中H H称为一致校验矩阵称为一致校验矩阵为为为为维的单位阵维的单位阵维的单位阵维的单位阵维的一般矩阵维的一般矩阵维的一般矩阵维的一般矩阵 为为为为校验矩阵与码字具有校验矩阵与码字具有校验矩阵与码字具有校验矩阵与码字具有正交性正交性可知可知可知可知:由由由由校验方程可改写为校验方程可改写为校验方程可改写为校验方程可改写为:令令令令，则上述方程组可用矩阵表示：，则上述方程组可用矩阵表示：，则上述方程组可用矩阵表示：，则上述方程组可用矩阵表示：为为为为维矢量，维矢量，维矢量，维矢量，为为为为维矢量，表示信息码元维矢量，表示信息码元维矢量，表示信息码元维矢量，表示信息码元为为为为维矢量，称为的维矢量，称为的维矢量，称为的维矢量，称为的生成矩阵生成矩阵式中式中式中式中 为为为为维的单位阵，维的单位阵，维的单位阵，维的单位阵，为为为为维的一般矩阵维的一般矩阵维的一般矩阵维的一般矩阵写成分块矩阵，即写成分块矩阵，即写成分块矩阵，即写成分块矩阵，即生成矩阵生成矩阵生成矩阵生成矩阵与校验矩阵与校验矩阵与校验矩阵与校验矩阵H H H H的关系为：的关系为：的关系为：的关系为：则有则有则有则有:例例6-66-6：已知一个线性分组码的生成矩阵为：已知一个线性分组码的生成矩阵为：已知一个线性分组码的生成矩阵为：已知一个线性分组码的生成矩阵为求生成的线性分组码以及校验矩阵求生成的线性分组码以及校验矩阵求生成的线性分组码以及校验矩阵求生成的线性分组码以及校验矩阵H.H.解：解：由生成矩阵由生成矩阵由生成矩阵由生成矩阵可知信息位有可知信息位有3 3位，则线性分组码为位，则线性分组码为（7，3）分组码，生成矩阵生成的码字为：分组码，生成矩阵生成的码字为：由由由由知知知知由由由由知知知知，2.2.线性分组码的纠、检错能力线性分组码的纠、检错能力 检错检错检错检错:译码器能检测到是否有错误发生。译码器能检测到是否有错误发生。译码器能检测到是否有错误发生。译码器能检测到是否有错误发生。码的检错能力用检测到的错误位数描述。码的检错能力用检测到的错误位数描述。码的检错能力用检测到的错误位数描述。码的检错能力用检测到的错误位数描述。纠错纠错纠错纠错:译码器不但能检测是否有错误发生，并能纠正错误。译码器不但能检测是否有错误发生，并能纠正错误。译码器不但能检测是否有错误发生，并能纠正错误。译码器不但能检测是否有错误发生，并能纠正错误。码的纠错能力用纠正错误的位数描述。码的纠错能力用纠正错误的位数描述。码的纠错能力用纠正错误的位数描述。码的纠错能力用纠正错误的位数描述。码的纠检错能力与码的最小汉明距离密切相关，具体结码的纠检错能力与码的最小汉明距离密切相关，具体结码的纠检错能力与码的最小汉明距离密切相关，具体结码的纠检错能力与码的最小汉明距离密切相关，具体结论如下：论如下：论如下：论如下：解解解解：因为因为因为因为d dminmin=3=2+1=3=2+1，所以能检出，所以能检出，所以能检出，所以能检出t td d=2 2个错误个错误个错误个错误译码方法为：译码方法为：译码方法为：译码方法为：000000译为译为译为译为0 0，111111译为译为译为译为1 1，其他置为，其他置为，其他置为，其他置为“错误错误错误错误”标志标志标志标志 因为因为因为因为d dminmin=3=2*1+1=3=2*1+1，所以能纠正，所以能纠正，所以能纠正，所以能纠正t tc c=1 1个错误个错误个错误个错误译码方法为：译码方法为：译码方法为：译码方法为：000000，001001，010010，100100译为译为译为译为0 0；011011，101101，110110，111111译为译为译为译为1 1但该码不能在纠正但该码不能在纠正但该码不能在纠正但该码不能在纠正tc=1tc=1个错误的同时又能检出个错误的同时又能检出个错误的同时又能检出个错误的同时又能检出td=2td=2个错误个错误个错误个错误例例6-76-7：简单重复简单重复简单重复简单重复2 2 2 2次编码，编码规则为次编码，编码规则为次编码，编码规则为次编码，编码规则为0000000000000000，1111111111111111，码，码，码，码C=c1,c2=000,111,dC=c1,c2=000,111,dC=c1,c2=000,111,dC=c1,c2=000,111,dminminminmin=3=3=3=3。试问该码纠检错能力如何？试问该码纠检错能力如何？试问该码纠检错能力如何？试问该码纠检错能力如何？例例6-86-8：简单重复：简单重复：简单重复：简单重复3 3 3 3次编码，编码规则为次编码，编码规则为次编码，编码规则为次编码，编码规则为00000000000000000000，11111111111111111111码码码码C=c1,c2=0000,1111,dC=c1,c2=0000,1111,dC=c1,c2=0000,1111,dC=c1,c2=0000,1111,dminminminmin=4=4=4=4。试问该码纠检错能力如何？试问该码纠检错能力如何？试问该码纠检错能力如何？试问该码纠检错能力如何？接收序列接收序列接收序列接收序列译码译码译码译码接收序列接收序列接收序列接收序列译码译码译码译码00000000000000000 0 0 010001000100010000 0 0 000010001000100010 0 0 01001100110011001ErrorErrorErrorError00100010001000100 0 0 01010101010101010ErrorErrorErrorError0011001100110011ErrorErrorErrorError10111011101110111 1 1 101000100010001000 0 0 01100110011001100ErrorErrorErrorError0101010101010101ErrorErrorErrorError11011101110111011 1 1 10110011001100110ErrorErrorErrorError11101110111011101 1 1 101110111011101111 1 1 111111111111111111 1 1 1解：由解：由解：由解：由d d d dminminminmin=4=3+1=4=3+1=4=3+1=4=3+1，知能检出，知能检出，知能检出，知能检出t t t td d d d=3 3 3 3个错误个错误个错误个错误 译码方法为译码方法为译码方法为译码方法为：0000000000000000译为译为译为译为0 0 0 0，1111111111111111译为译为译为译为1 1 1 1，其他置为，其他置为，其他置为，其他置为“错误错误错误错误”标标标标志志志志由由由由d d d dminminminmin=42*1+1=42*1+1=42*1+1=42*1+1和和和和d d d dminminminmin=4=1+2+1=4=1+2+1=4=1+2+1=4=1+2+1，知能，知能，知能，知能纠正纠正纠正纠正t t t tc c c c=1=1=1=1个错误，同时能检个错误，同时能检个错误，同时能检个错误，同时能检出出出出t t t td d d d=2=2=2=2个错误个错误个错误个错误，译码方法为：，译码方法为：，译码方法为：，译码方法为：例例6-96-9：比较（：比较（：比较（：比较（5 5 5 5，2 2 2 2）线性码和）线性码和）线性码和）线性码和“重复重复重复重复2 2 2 2次次次次”码的纠、检错能力和码的纠、检错能力和码的纠、检错能力和码的纠、检错能力和信息率。信息率。信息率。信息率。解：解：解：解：由例由例由例由例6-66-66-66-6和第三节的和第三节的和第三节的和第三节的“简单重复编码简单重复编码简单重复编码简单重复编码”可知：可知：可知：可知：“重复重复重复重复2 2 2 2次次次次”码的纠、检错能力和信息率为：码的纠、检错能力和信息率为：码的纠、检错能力和信息率为：码的纠、检错能力和信息率为：（1 1 1 1）d d d dminminminmin=3=3=3=3，能检出，能检出，能检出，能检出t t t td d d d=2=2=2=2个错误或纠正个错误或纠正个错误或纠正个错误或纠正t t t tc c c c=1=1=1=1个错误。个错误。个错误。个错误。（2 2 2 2）R=1/3(R=1/3(R=1/3(R=1/3(比特比特比特比特/码元码元码元码元)由码字生成式求出与各信息组对应的码字：由码字生成式求出与各信息组对应的码字：由码字生成式求出与各信息组对应的码字：由码字生成式求出与各信息组对应的码字：信息组信息组信息组信息组码字码字码字码字c c c c0000000000000000000000000000010101010110101101011010110110101010101111011110111101111111111111010110101101011010（5 5 5 5，2 2 2 2）线性码的生成矩阵为）线性码的生成矩阵为）线性码的生成矩阵为）线性码的生成矩阵为结论：结论：（5 5 5 5，2 2 2 2）的信息率比）的信息率比）的信息率比）的信息率比“重复重复重复重复2 2 2 2次次次次”码提高了一倍。码提高了一倍。码提高了一倍。码提高了一倍。码码码码C=cC=cC=cC=c的最小汉明距离为的最小汉明距离为的最小汉明距离为的最小汉明距离为d d d dminminminmin=3=3=3=3，纠、检错能力与，纠、检错能力与，纠、检错能力与，纠、检错能力与“重复重复重复重复2 2 2 2次次次次”码码码码相同，能检出相同，能检出相同，能检出相同，能检出t t t td d d d=2=2=2=2个错误或纠正个错误或纠正个错误或纠正个错误或纠正t t t tc c c c=1=1=1=1个错误。个错误。个错误。个错误。由第三节的由第三节的由第三节的由第三节的“简单重复编码简单重复编码简单重复编码简单重复编码”可知可知可知可知:R=2/3(R=2/3(R=2/3(R=2/3(比特比特比特比特/码元码元码元码元)两者的平均差错率处于同一数量级，原因是它们的最小汉明距两者的平均差错率处于同一数量级，原因是它们的最小汉明距两者的平均差错率处于同一数量级，原因是它们的最小汉明距两者的平均差错率处于同一数量级，原因是它们的最小汉明距离相同离相同离相同离相同3.伴随式和伴随式译码伴随式和伴随式译码若发送码字为若发送码字为若发送码字为若发送码字为,则由于在传输过程中受到则由于在传输过程中受到则由于在传输过程中受到则由于在传输过程中受到各种干扰，接收序列各种干扰，接收序列各种干扰，接收序列各种干扰，接收序列不一定等于发送的码字不一定等于发送的码字不一定等于发送的码字不一定等于发送的码字两者之间的差异即是出现的差错。差错是多样化的，定义差错两者之间的差异即是出现的差错。差错是多样化的，定义差错两者之间的差异即是出现的差错。差错是多样化的，定义差错两者之间的差异即是出现的差错。差错是多样化的，定义差错的式样为的式样为的式样为的式样为差错图样差错图样则有则有则有则有对于二元序列情形，模对于二元序列情形，模对于二元序列情形，模对于二元序列情形，模2 2 2 2减等同模减等同模减等同模减等同模2 2 2 2加，则有：加，则有：加，则有：加，则有：以及以及以及以及S S是传输是否出错的标志是传输是否出错的标志是传输是否出错的标志是传输是否出错的标志,称为称为称为称为伴随式伴随式.译码时，需由译码时，需由译码时，需由译码时，需由来确定发送码字来确定发送码字来确定发送码字来确定发送码字,若能确定差错图样若能确定差错图样若能确定差错图样若能确定差错图样，就可得到，就可得到，就可得到，就可得到码字的估计值码字的估计值码字的估计值码字的估计值为为为为译码的译码的译码的译码的关键问题关键问题关键问题关键问题是确定差错图样是确定差错图样是确定差错图样是确定差错图样 根据伴随式根据伴随式根据伴随式根据伴随式和校验矩阵确定差错图样和校验矩阵确定差错图样和校验矩阵确定差错图样和校验矩阵确定差错图样,再由上式得到码字的再由上式得到码字的再由上式得到码字的再由上式得到码字的估计值估计值估计值估计值,这种方法称为这种方法称为这种方法称为这种方法称为伴随式译码伴随式译码，具体步骤：，具体步骤：，具体步骤：，具体步骤：从伴随式计算差错图样具有随机性，从伴随式计算差错图样具有随机性，从伴随式计算差错图样具有随机性，从伴随式计算差错图样具有随机性，为什么？为什么？做法做法：在差错图样的多个解中，选汉明重量（码字中非零的：在差错图样的多个解中，选汉明重量（码字中非零的：在差错图样的多个解中，选汉明重量（码字中非零的：在差错图样的多个解中，选汉明重量（码字中非零的个数）最小者作为差错图样的估值个数）最小者作为差错图样的估值个数）最小者作为差错图样的估值个数）最小者作为差错图样的估值 例例6-106-10：某（：某（：某（：某（5 5 5 5，2 2 2 2）线性分组码的生成矩阵为）线性分组码的生成矩阵为）线性分组码的生成矩阵为）线性分组码的生成矩阵为设接收序列为设接收序列为设接收序列为设接收序列为，请译出发送码字的估计值，请译出发送码字的估计值，请译出发送码字的估计值，请译出发送码字的估计值解：解：由生成矩阵可知相应的码字由生成矩阵可知相应的码字由生成矩阵可知相应的码字由生成矩阵可知相应的码字求校验矩阵求校验矩阵求校验矩阵求校验矩阵H H H H，由由由由得：得：得：得：由由由由，则有，则有，则有，则有则：则：则：则：由由由由计算伴随式得计算伴随式得计算伴随式得计算伴随式得由由由由得：得：得：得：选择最小汉明重量的差错图样有选择最小汉明重量的差错图样有选择最小汉明重量的差错图样有选择最小汉明重量的差错图样有则有则有则有则有