通信原理第7章信道编码和差错控制.ppt

第第7 7章章 信道编码和差错控制信道编码和差错控制7.1 概述概述7.2 纠错编码的基本原理纠错编码的基本原理7.3 纠错编码系统的性能纠错编码系统的性能7.4 奇偶监督码奇偶监督码7.5 线性分组码线性分组码7.6 循环码循环码 信源编码与信道编码信源编码与信道编码信源编码与信道编码信源编码与信道编码 信源编码信源编码信源编码信源编码(有效性编码有效性编码有效性编码有效性编码)去除冗余去除冗余去除冗余去除冗余 提高数字信号的有效性提高数字信号的有效性提高数字信号的有效性提高数字信号的有效性 模拟信号数字化模拟信号数字化模拟信号数字化模拟信号数字化 信道编码信道编码信道编码信道编码(可靠性编码可靠性编码可靠性编码可靠性编码)添加冗余添加冗余添加冗余添加冗余 降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性降低差错率：牺牲通信的有效性（信息传输速率）来提高可靠性 差错控制：包括信道编码在内的一切纠正错误手段差错控制：包括信道编码在内的一切纠正错误手段差错控制：包括信道编码在内的一切纠正错误手段差错控制：包括信道编码在内的一切纠正错误手段 差错控制技术的种类差错控制技术的种类差错控制技术的种类差错控制技术的种类 检错重发检错重发检错重发检错重发 能发现错码，但是不能确定错码的位置能发现错码，但是不能确定错码的位置能发现错码，但是不能确定错码的位置能发现错码，但是不能确定错码的位置 通信系统需要有双向信道通信系统需要有双向信道通信系统需要有双向信道通信系统需要有双向信道 前向纠错前向纠错前向纠错前向纠错(FEC)(FEC)：利用加入的差错控制码元，不但能够发现错码，利用加入的差错控制码元，不但能够发现错码，利用加入的差错控制码元，不但能够发现错码，利用加入的差错控制码元，不但能够发现错码，还能纠正错码还能纠正错码还能纠正错码还能纠正错码 反馈校验反馈校验反馈校验反馈校验 将收到的码元转发回发送端，将它和原发送码元比较将收到的码元转发回发送端，将它和原发送码元比较将收到的码元转发回发送端，将它和原发送码元比较将收到的码元转发回发送端，将它和原发送码元比较 缺点：需要双向信道，传输效率也较低缺点：需要双向信道，传输效率也较低缺点：需要双向信道，传输效率也较低缺点：需要双向信道，传输效率也较低 检错删除检错删除检错删除检错删除 在接收端发现错码后，立即将其删除在接收端发现错码后，立即将其删除在接收端发现错码后，立即将其删除在接收端发现错码后，立即将其删除 适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处 7.1 7.1 概述概述概述概述发送端发送端接收端接收端信信 源源信信道道编编码码调调 制制信信 道道压压缩缩编编码码解解 调调信信 宿宿保保密密解解码码信信道道解解码码压压缩缩解解码码保保密密编编码码噪噪 声声信信 源源 编编码码信信 源源 解解码码 自动要求重发自动要求重发自动要求重发自动要求重发(ARQ)(ARQ)系统系统系统系统 停止等待停止等待停止等待停止等待ARQARQ系统系统系统系统 拉后拉后拉后拉后ARQARQ系统系统系统系统 7.1 7.1 概述概述概述概述 接收数据ACKACKNAKACKACKNAKACK1233455t发送数据12334556t有错码组有错码组214365798接收数据有错码组有错码组910 1110 11 12576ACK1NAK5NAK9ACK55769521436798发送数据10 1110 11 12重发码组重发码组 自动要求重发自动要求重发自动要求重发自动要求重发(ARQ)(ARQ)系统系统系统系统 选择重发选择重发选择重发选择重发ARQARQ系统系统系统系统7.1 7.1 概述概述概述概述选择重发ARQ系统9接收数据有错码组有错码组214365759810 11131412发送数据9958521436710 1113 1412重发码组重发码组NAK9ACK1NAK5ACK5ACK9 ARQARQ和前向纠错比较和前向纠错比较和前向纠错比较和前向纠错比较 优点优点优点优点 监督码元较少，即码率较高监督码元较少，即码率较高监督码元较少，即码率较高监督码元较少，即码率较高 检错的计算复杂度较低检错的计算复杂度较低检错的计算复杂度较低检错的计算复杂度较低 能适应不同特性的信道能适应不同特性的信道能适应不同特性的信道能适应不同特性的信道 缺点缺点缺点缺点 需要双向信道需要双向信道需要双向信道需要双向信道 不适用于一点到多点的通信系统或广播系统不适用于一点到多点的通信系统或广播系统不适用于一点到多点的通信系统或广播系统不适用于一点到多点的通信系统或广播系统 传输效率降低，可能因反复重发而造成事实上的通信中断传输效率降低，可能因反复重发而造成事实上的通信中断传输效率降低，可能因反复重发而造成事实上的通信中断传输效率降低，可能因反复重发而造成事实上的通信中断 产生错码的原因产生错码的原因产生错码的原因产生错码的原因 乘性干扰引起的码间串扰乘性干扰引起的码间串扰乘性干扰引起的码间串扰乘性干扰引起的码间串扰 加性干扰引起的信噪比降低加性干扰引起的信噪比降低加性干扰引起的信噪比降低加性干扰引起的信噪比降低 信道分类：按照加性干扰造成错码的统计特性不同划分信道分类：按照加性干扰造成错码的统计特性不同划分信道分类：按照加性干扰造成错码的统计特性不同划分信道分类：按照加性干扰造成错码的统计特性不同划分 随机信道：错码随机出现，例如由白噪声引起的错码随机信道：错码随机出现，例如由白噪声引起的错码随机信道：错码随机出现，例如由白噪声引起的错码随机信道：错码随机出现，例如由白噪声引起的错码 突发信道：错码相对集中出现，例如由脉冲干扰引起的突发信道：错码相对集中出现，例如由脉冲干扰引起的突发信道：错码相对集中出现，例如由脉冲干扰引起的突发信道：错码相对集中出现，例如由脉冲干扰引起的 错码错码错码错码 混合信道混合信道混合信道混合信道 编码序列的参数编码序列的参数编码序列的参数编码序列的参数 n n 编码序列中总码元数量编码序列中总码元数量编码序列中总码元数量编码序列中总码元数量 k k 编码序列中信息码元数量编码序列中信息码元数量编码序列中信息码元数量编码序列中信息码元数量 r r 编码序列中差错控制码元数量编码序列中差错控制码元数量编码序列中差错控制码元数量编码序列中差错控制码元数量 （差错控制码元，以后称为监督码元或监督位（差错控制码元，以后称为监督码元或监督位（差错控制码元，以后称为监督码元或监督位（差错控制码元，以后称为监督码元或监督位 ）k/nk/n码率码率码率码率 (n-k)/k=r/k(n-k)/k=r/k冗余度冗余度冗余度冗余度 7.1 7.1 概述概述概述概述7.2 7.2 纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理 差错控制编码差错控制编码差错控制编码差错控制编码 理论依据：香农信道编码定理理论依据：香农信道编码定理理论依据：香农信道编码定理理论依据：香农信道编码定理对于一给定的有干扰信道，若其信道容量为对于一给定的有干扰信道，若其信道容量为对于一给定的有干扰信道，若其信道容量为对于一给定的有干扰信道，若其信道容量为C C，只要发送端以低于，只要发送端以低于，只要发送端以低于，只要发送端以低于C C的速率的速率的速率的速率R R发送信息，则一定存在一种编码方法，使编码错误概率发送信息，则一定存在一种编码方法，使编码错误概率发送信息，则一定存在一种编码方法，使编码错误概率发送信息，则一定存在一种编码方法，使编码错误概率P P随随随随着码长着码长着码长着码长n n的增加，按指数下降到任意小的值的增加，按指数下降到任意小的值的增加，按指数下降到任意小的值的增加，按指数下降到任意小的值 基本思想基本思想基本思想基本思想通过对信息码元序列作某种变换通过对信息码元序列作某种变换通过对信息码元序列作某种变换通过对信息码元序列作某种变换,使原来彼此相互独立使原来彼此相互独立使原来彼此相互独立使原来彼此相互独立,没有关联的信没有关联的信没有关联的信没有关联的信息码元序列息码元序列息码元序列息码元序列,经过这种变换后经过这种变换后经过这种变换后经过这种变换后,产生某种规律性或相关性产生某种规律性或相关性产生某种规律性或相关性产生某种规律性或相关性,使在接收端可使在接收端可使在接收端可使在接收端可根据这种规律性来检查根据这种规律性来检查根据这种规律性来检查根据这种规律性来检查,以至纠正传输序列中的差错以至纠正传输序列中的差错以至纠正传输序列中的差错以至纠正传输序列中的差错 实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按实现：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系照同一规则检查两者间关系照同一规则检查两者间关系照同一规则检查两者间关系 7.2 7.2 纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理 差错控制编码差错控制编码差错控制编码差错控制编码 简单例子简单例子简单例子简单例子 假如要传送假如要传送假如要传送假如要传送A A、B B两个消息，消息两个消息，消息两个消息，消息两个消息，消息A-“0”A-“0”；消息；消息；消息；消息B-“1”B-“1”若传输中产生错码（若传输中产生错码（若传输中产生错码（若传输中产生错码（“0”0”错成错成错成错成“1”1”或或或或“1”1”错成错成错成错成“0”0”）收端无法发）收端无法发）收端无法发）收端无法发现，该编码无检错纠错能力现，该编码无检错纠错能力现，该编码无检错纠错能力现，该编码无检错纠错能力 消息消息消息消息A-“00”A-“00”；消息；消息；消息；消息B-“11”B-“11”若传输中产生一位错码，则变成若传输中产生一位错码，则变成若传输中产生一位错码，则变成若传输中产生一位错码，则变成“01”01”或或或或“10”10”，收端判决为有错，收端判决为有错，收端判决为有错，收端判决为有错（因（因（因（因“01”“10”01”“10”为禁用码组），但无法确定错码位置，不能纠为禁用码组），但无法确定错码位置，不能纠为禁用码组），但无法确定错码位置，不能纠为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码正，该编码具有检出一位错码的能力。这表明增加一位冗余码正，该编码具有检出一位错码的能力。这表明增加一位冗余码正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力元后码具有检出一位错码的能力元后码具有检出一位错码的能力元后码具有检出一位错码的能力 消息消息消息消息A-“000”A-“000”；消息；消息；消息；消息B-“111”B-“111”传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输中产生一位即使两位错码，都将变成禁用码组，收端判决 传输有错。该编码具有检出两位错码的能力。传输有错。该编码具有检出两位错码的能力。传输有错。该编码具有检出两位错码的能力。传输有错。该编码具有检出两位错码的能力。在产生一位错码情况下，收端可进行正确判决，能够纠正这一在产生一位错码情况下，收端可进行正确判决，能够纠正这一在产生一位错码情况下，收端可进行正确判决，能够纠正这一在产生一位错码情况下，收端可进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。这表明增加两位冗位错码。该编码具有纠正一位错码的能力。这表明增加两位冗位错码。该编码具有纠正一位错码的能力。这表明增加两位冗位错码。该编码具有纠正一位错码的能力。这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。余码元后码具有检出两位错码及纠正一位错码的能力。余码元后码具有检出两位错码及纠正一位错码的能力。余码元后码具有检出两位错码及纠正一位错码的能力。可见，纠错编码之所以具有检错和纠错能力，确实是因为在信息码可见，纠错编码之所以具有检错和纠错能力，确实是因为在信息码可见，纠错编码之所以具有检错和纠错能力，确实是因为在信息码可见，纠错编码之所以具有检错和纠错能力，确实是因为在信息码 元外添加了冗余码元（监督码元）。元外添加了冗余码元（监督码元）。元外添加了冗余码元（监督码元）。元外添加了冗余码元（监督码元）。一般说来，添加的冗余越多，一般说来，添加的冗余越多，一般说来，添加的冗余越多，一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。码的检错、纠错能力越强，但信道的传输效率下降也越多。码的检错、纠错能力越强，但信道的传输效率下降也越多。码的检错、纠错能力越强，但信道的传输效率下降也越多。7.2 7.2 纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理 差错控制能力与编码效率差错控制能力与编码效率差错控制能力与编码效率差错控制能力与编码效率 设：有一种由设：有一种由设：有一种由设：有一种由3 3个二进制码元构成的编码，它共有个二进制码元构成的编码，它共有个二进制码元构成的编码，它共有个二进制码元构成的编码，它共有2 23 3=8=8种不同的可种不同的可种不同的可种不同的可 能码组：能码组：能码组：能码组：000 000 晴晴晴晴 001 001 云云云云 010 010 阴阴阴阴 011 011 雨雨雨雨 100 100 雪雪雪雪 101 101 霜霜霜霜 110 110 雾雾雾雾 111 111 雹雹雹雹 这时，若一个码组中发生错码，则将收到错误信息这时，若一个码组中发生错码，则将收到错误信息这时，若一个码组中发生错码，则将收到错误信息这时，若一个码组中发生错码，则将收到错误信息 若在此若在此若在此若在此8 8种码组中仅允许使用种码组中仅允许使用种码组中仅允许使用种码组中仅允许使用4 4种来传送天气，例如：令种来传送天气，例如：令种来传送天气，例如：令种来传送天气，例如：令 000 000 晴晴晴晴 011 011 云云云云 101 101 阴阴阴阴 110 110 雨雨雨雨 为为为为许用码组许用码组许用码组许用码组，其他，其他，其他，其他4 4种不允许使用，称为种不允许使用，称为种不允许使用，称为种不允许使用，称为禁用码组禁用码组禁用码组禁用码组 这时，接收端有可能发现（检测到）码组中的一个错码。这时，接收端有可能发现（检测到）码组中的一个错码。这时，接收端有可能发现（检测到）码组中的一个错码。这时，接收端有可能发现（检测到）码组中的一个错码。这种编码只能检测错码，不能纠正错码这种编码只能检测错码，不能纠正错码这种编码只能检测错码，不能纠正错码这种编码只能检测错码，不能纠正错码 若规定只许用两个码组：若规定只许用两个码组：若规定只许用两个码组：若规定只许用两个码组：例如例如例如例如 000 000 晴晴晴晴 111 111 雨雨雨雨 就能检测两个以下错码，或纠正一个错码就能检测两个以下错码，或纠正一个错码就能检测两个以下错码，或纠正一个错码就能检测两个以下错码，或纠正一个错码 分组码概念分组码概念分组码概念分组码概念 分组码分组码分组码分组码 信息位信息位信息位信息位 监督位监督位监督位监督位 分组码符号：分组码符号：分组码符号：分组码符号：(n,k)(n,k)其中，其中，其中，其中，n n 码组总长度码组总长度码组总长度码组总长度 k k 信息码元数目信息码元数目信息码元数目信息码元数目 r=n k r=n k 监督码元数目监督码元数目监督码元数目监督码元数目 右表中的码组为右表中的码组为右表中的码组为右表中的码组为(3,2)(3,2)码码码码 分组码的一般结构：分组码的一般结构：分组码的一般结构：分组码的一般结构：信息信息位位监监督督位位晴晴000云云011阴阴101雨雨110k个信息位r个监督位an-1an-2.arar-1an-2.a0t码长 n=k+r7.2 7.2 纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理 码重码重码重码重 码字中非零码元的数目码字中非零码元的数目码字中非零码元的数目码字中非零码元的数目 码距码距码距码距 两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，两个码字中对应码位上具有不同二进制码元的位数定义两码字的距离，称为汉明（称为汉明（称为汉明（称为汉明（HammingHamming）距离）距离）距离）距离,简称码距简称码距简称码距简称码距 最小码距最小码距最小码距最小码距 在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素在一个码中，任意两个码字间距离的最小值，即码字集合中任意两元素 间的最小距离，记为间的最小距离，记为间的最小距离，记为间的最小距离，记为d d0 0 码距的几何意义：以码距的几何意义：以码距的几何意义：以码距的几何意义：以n=3n=3的编码为例的编码为例的编码为例的编码为例 一般而言，码距是一般而言，码距是一般而言，码距是一般而言，码距是 n n 维空间中单位维空间中单位维空间中单位维空间中单位 正多面体顶点之间的汉明距离正多面体顶点之间的汉明距离正多面体顶点之间的汉明距离正多面体顶点之间的汉明距离 7.2 7.2 纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1 最小码距与检、纠错能力关系最小码距与检、纠错能力关系最小码距与检、纠错能力关系最小码距与检、纠错能力关系 一个码能检测一个码能检测一个码能检测一个码能检测e e个错码，则要求其最小码距个错码，则要求其最小码距个错码，则要求其最小码距个错码，则要求其最小码距 d d0 0e+1e+1反之，若码的最小距离为反之，若码的最小距离为反之，若码的最小距离为反之，若码的最小距离为d d0 0，则最多能检测则最多能检测则最多能检测则最多能检测d d0 0-1-1个错码个错码个错码个错码 一个码能纠正一个码能纠正一个码能纠正一个码能纠正t t个错码，则要求其最小码距个错码，则要求其最小码距个错码，则要求其最小码距个错码，则要求其最小码距 d d0 02t+12t+1反之，若码的最小距离为反之，若码的最小距离为反之，若码的最小距离为反之，若码的最小距离为d d0 0，则最多能纠正则最多能纠正则最多能纠正则最多能纠正(d(d0 0-1)/2-1)/2个错码个错码个错码个错码 7.2 7.2 纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理0123BA汉明距离ed0码距等于3的两个码组BtA汉明距离012345td0码距等于5的两个码组 最小码距与检、纠错能力关系最小码距与检、纠错能力关系最小码距与检、纠错能力关系最小码距与检、纠错能力关系 一个码能纠正一个码能纠正一个码能纠正一个码能纠正t t个错码，同时能检测个错码，同时能检测个错码，同时能检测个错码，同时能检测e e个错码，则要求其最小码距个错码，则要求其最小码距个错码，则要求其最小码距个错码，则要求其最小码距 d d0 0e+t+1 (et)e+t+1 (et)7.2 7.2 纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理纠错编码的基本原理 误码率性能和带宽的关系误码率性能和带宽的关系误码率性能和带宽的关系误码率性能和带宽的关系 采用编码降低误码率所付出的采用编码降低误码率所付出的采用编码降低误码率所付出的采用编码降低误码率所付出的 代价是带宽的增大代价是带宽的增大代价是带宽的增大代价是带宽的增大10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3 7.3 纠错编码系统的性能纠错编码系统的性能纠错编码系统的性能纠错编码系统的性能 功率和带宽的关系功率和带宽的关系功率和带宽的关系功率和带宽的关系 采用编码以节省功率，并保持误码率采用编码以节省功率，并保持误码率采用编码以节省功率，并保持误码率采用编码以节省功率，并保持误码率 不变，付出的代价也是带宽增大。不变，付出的代价也是带宽增大。不变，付出的代价也是带宽增大。不变，付出的代价也是带宽增大。10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3 7.3 纠错编码系统的性能纠错编码系统的性能纠错编码系统的性能纠错编码系统的性能 传输速率和带宽的关系传输速率和带宽的关系传输速率和带宽的关系传输速率和带宽的关系对于给定的传输系统，其传输速率对于给定的传输系统，其传输速率对于给定的传输系统，其传输速率对于给定的传输系统，其传输速率 和和和和E Eb b/n/n0 0的关系：的关系：的关系：的关系：式中，式中，式中，式中，R RB B 码元速率。码元速率。码元速率。码元速率。提高传输速率，采用编提高传输速率，采用编提高传输速率，采用编提高传输速率，采用编码以保持误码率不变；付出码以保持误码率不变；付出码以保持误码率不变；付出码以保持误码率不变；付出的代价仍是带宽增大的代价仍是带宽增大的代价仍是带宽增大的代价仍是带宽增大10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK7.3 7.3 纠错编码系统的性能纠错编码系统的性能纠错编码系统的性能纠错编码系统的性能 编码增益编码增益编码增益编码增益定义：在保持误码率恒定条件下，定义：在保持误码率恒定条件下，定义：在保持误码率恒定条件下，定义：在保持误码率恒定条件下，采用纠错编码所节省的信采用纠错编码所节省的信采用纠错编码所节省的信采用纠错编码所节省的信 噪比噪比噪比噪比E Eb b/n/n0 0 称为编码增益：称为编码增益：称为编码增益：称为编码增益：式中，式中，式中，式中，(E(Eb b/n/n0 0)u u 未编码时的信噪比未编码时的信噪比未编码时的信噪比未编码时的信噪比(dB)(dB)(E(Eb b/n/n0 0)c c 编码后所需的信噪比编码后所需的信噪比编码后所需的信噪比编码后所需的信噪比(dB)(dB)7.3 7.3 纠错编码系统的性能纠错编码系统的性能纠错编码系统的性能纠错编码系统的性能10-610-510-410-310-210-1编码后Eb/n0(dB)编码和误码率关系PeCDEAB2PSK 一维奇偶监督码一维奇偶监督码一维奇偶监督码一维奇偶监督码 在信息码元后附加一位监督位，使得码组中在信息码元后附加一位监督位，使得码组中在信息码元后附加一位监督位，使得码组中在信息码元后附加一位监督位，使得码组中“1”1”的个数为偶数或的个数为偶数或的个数为偶数或的个数为偶数或奇奇奇奇 数数数数,按照奇偶数分为奇数监督码和偶数监督码两类按照奇偶数分为奇数监督码和偶数监督码两类按照奇偶数分为奇数监督码和偶数监督码两类按照奇偶数分为奇数监督码和偶数监督码两类 (n,n-1)(n,n-1)分组码，码率为分组码，码率为分组码，码率为分组码，码率为(n-1)/n(n-1)/n（或（或（或（或k/(k+1)k/(k+1)奇数监督码中，此监督位使码组中奇数监督码中，此监督位使码组中奇数监督码中，此监督位使码组中奇数监督码中，此监督位使码组中“1”1”的个数为奇数：的个数为奇数：的个数为奇数：的个数为奇数：式中，式中，式中，式中，a a0 0为监督位，其他位为信息位为监督位，其他位为信息位为监督位，其他位为信息位为监督位，其他位为信息位 偶数监督码中，此监督位使码组中偶数监督码中，此监督位使码组中偶数监督码中，此监督位使码组中偶数监督码中，此监督位使码组中“1”1”的个数为偶数：的个数为偶数：的个数为偶数：的个数为偶数：式中，式中，式中，式中，a a0 0为监督位，其他位为信息位为监督位，其他位为信息位为监督位，其他位为信息位为监督位，其他位为信息位 检错能力检错能力检错能力检错能力 能够检测奇数个错码能够检测奇数个错码能够检测奇数个错码能够检测奇数个错码 应用：以随机错误为主的计算机通信系统，难于对付突发错误应用：以随机错误为主的计算机通信系统，难于对付突发错误应用：以随机错误为主的计算机通信系统，难于对付突发错误应用：以随机错误为主的计算机通信系统，难于对付突发错误,计计计计 算机内部的数据传送，就是采用这种码算机内部的数据传送，就是采用这种码算机内部的数据传送，就是采用这种码算机内部的数据传送，就是采用这种码7.4 7.4 奇偶监督码奇偶监督码奇偶监督码奇偶监督码信息位信息位监监督位督位晴晴000云云011阴阴101雨雨110 二维奇偶监督码二维奇偶监督码二维奇偶监督码二维奇偶监督码 有可能检测偶数个错码，但当偶数个错误刚好分布在矩阵的四个顶点有可能检测偶数个错码，但当偶数个错误刚好分布在矩阵的四个顶点有可能检测偶数个错码，但当偶数个错误刚好分布在矩阵的四个顶点有可能检测偶数个错码，但当偶数个错误刚好分布在矩阵的四个顶点 时，则检测不出时，则检测不出时，则检测不出时，则检测不出 适合检测突发错码适合检测突发错码适合检测突发错码适合检测突发错码 能够纠正部分错码能够纠正部分错码能够纠正部分错码能够纠正部分错码 7.4 7.4 奇偶监督码奇偶监督码奇偶监督码奇偶监督码 基本概念基本概念基本概念基本概念 代数码代数码代数码代数码 利用代数关系式产生监督位的编码利用代数关系式产生监督位的编码利用代数关系式产生监督位的编码利用代数关系式产生监督位的编码 线性分组码线性分组码线性分组码线性分组码 代数码的一种，其代数码的一种，其代数码的一种，其代数码的一种，其 督位和信息位的关系由线性代数方督位和信息位的关系由线性代数方督位和信息位的关系由线性代数方督位和信息位的关系由线性代数方 程决定程决定程决定程决定 汉明码汉明码汉明码汉明码 一种能够纠正一个错码的线性分组码一种能够纠正一个错码的线性分组码一种能够纠正一个错码的线性分组码一种能够纠正一个错码的线性分组码 汉明码汉明码汉明码汉明码 发送端编码：将一位监督码元附加在信息码元后，使得码元中发送端编码：将一位监督码元附加在信息码元后，使得码元中发送端编码：将一位监督码元附加在信息码元后，使得码元中发送端编码：将一位监督码元附加在信息码元后，使得码元中“1 1 1 1”码元个数为偶数码元个数为偶数码元个数为偶数码元个数为偶数 接收端译码：接收端译码：接收端译码：接收端译码：计数接收码组中计数接收码组中计数接收码组中计数接收码组中“1 1 1 1”码元个数是否为偶数，即计算：码元个数是否为偶数，即计算：码元个数是否为偶数，即计算：码元个数是否为偶数，即计算：S=aS=an-1n-1+a+an-2n-2+a+a0 0 （1 1）S=0S=0S=0S=0认为没错，认为没错，认为没错，认为没错，S=1S=1S=1S=1认为有错认为有错认为有错认为有错（1 1 1 1）式称为监督方程）式称为监督方程）式称为监督方程）式称为监督方程/监督关系式，监督关系式，监督关系式，监督关系式，S S S S称为校正子称为校正子称为校正子称为校正子/校验子校验子校验子校验子/伴随式伴随式伴随式伴随式7.5 7.5 线性分组码线性分组码线性分组码线性分组码 汉明码汉明码汉明码汉明码 监督位增加到监督位增加到监督位增加到监督位增加到2 2 2 2位：有两个监督方程，两个伴随式；两个伴随式组合有位：有两个监督方程，两个伴随式；两个伴随式组合有位：有两个监督方程，两个伴随式；两个伴随式组合有位：有两个监督方程，两个伴随式；两个伴随式组合有 四种（四种（四种（四种（00000000表示无错，表示无错，表示无错，表示无错，01010101、10101010、11111111表示一位错码的三种可能位置）表示一位错码的三种可能位置）表示一位错码的三种可能位置）表示一位错码的三种可能位置）监督位增加到监督位增加到监督位增加到监督位增加到r r r r位：可指示一位错码的（位：可指示一位错码的（位：可指示一位错码的（位：可指示一位错码的（2 2 2 2r r r r-1-1-1-1）个可能位置）个可能位置）个可能位置）个可能位置 一般说来，对于（一般说来，对于（一般说来，对于（一般说来，对于（n n n n，k)k)k)k)分组码，若希望用分组码，若希望用分组码，若希望用分组码，若希望用r=n-kr=n-kr=n-kr=n-k个监督位构造出的个监督位构造出的个监督位构造出的个监督位构造出的r r r r个个个个 监督关系式来指示一位错码的监督关系式来指示一位错码的监督关系式来指示一位错码的监督关系式来指示一位错码的n n n n种可能位置，则要求：种可能位置，则要求：种可能位置，则要求：种可能位置，则要求：2 2 2 2r r r r-1n-1n-1n-1n 即即即即 2 2 2 2r r r r k+r+1 k+r+1 k+r+1 k+r+1 （2 2 2 2）举例：构造一（举例：构造一（举例：构造一（举例：构造一（n n n n，k)k)k)k)分组码，分组码，分组码，分组码，k=4k=4k=4k=4并能纠正一位错码并能纠正一位错码并能纠正一位错码并能纠正一位错码 欲纠正一位错码，由（欲纠正一位错码，由（欲纠正一位错码，由（欲纠正一位错码，由（2 2 2 2）式知）式知）式知）式知r 3r 3r 3r 3，取取取取r=3r=3r=3r=3，则则则则n=k+r=7n=k+r=7n=k+r=7n=k+r=7 设设设设7 7 7 7位码元为：位码元为：位码元为：位码元为：a a a a6 6 6 6a a a a5 5 5 5 a a a a0 0 0 0；三个伴随式：三个伴随式：三个伴随式：三个伴随式：S S S S1 1 1 1、S S S S2 2 2 2、S S S S3 3 3 3；则可规定则可规定则可规定则可规定S S S S1 1 1 1S S S S2 2 2 2S S S S3 3 3 3的的的的 八种组合与一位错码的对应关系如下（也可规定为另一种对应关八种组合与一位错码的对应关系如下（也可规定为另一种对应关八种组合与一位错码的对应关系如下（也可规定为另一种对应关八种组合与一位错码的对应关系如下（也可规定为另一种对应关 系）：系）：系）：系）：7.5 7.5 线性分组码线性分组码线性分组码线性分组码7.5 7.5 线性分组码线性分组码线性分组码线性分组码 汉明码汉明码汉明码汉明码 举例：构造一（举例：构造一（举例：构造一（举例：构造一（n n，k)k)分组码，分组码，分组码，分组码，k=4k=4并能纠正一位错码并能纠正一位错码并能纠正一位错码并能纠正一位错码 从上表可见：从上表可见：从上表可见：从上表可见：当一位错码发生在当一位错码发生在当一位错码发生在当一位错码发生在a a2 2、a a4 4、a a5 5或或或或a a6 6上时，上时，上时，上时，S S1 1为为为为1 1；否则为；否则为；否则为；否则为0 0。即即即即a a2 2、a a4 4、a a5 5和和和和a a6 6构成偶监督关系：构成偶监督关系：构成偶监督关系：构成偶监督关系：S S1 1=a=a2 2+a+a4 4+a+a5 5+a+a6 6 同理，同理，同理，同理，a a1 1、a a3 3、a a5 5和和和和a a6 6构成偶监督关系：构成偶监督关系：构成偶监督关系：构成偶监督关系：S S2 2=a=a1 1+a+a3 3+a+a5 5+a+a6 6 a a0 0、a a3 3、a a4 4和和和和a a6 6构成偶监督关系：构成偶监督关系：构成偶监督关系：构成偶监督关系：S S3 3=a=a0 0+a+a3 3+a+a4 4+a+a6 67.5 7.5 线性分组码线性分组码线性分组码线性分组码 汉明码汉明码汉明码汉明码 发端编码原则发端编码原则发端编码原则发端编码原则 信息码元信息码元信息码元信息码元a a6 6 、a a5 5 、a a4 4、a a3 3来源于待编码的信息序列；来源于待编码的信息序列；来源于待编码的信息序列；来源于待编码的信息序列；监督码元监督码元监督码元监督码元 a a2 2 、a a1 1、a a0 0的取值应的取值应的取值应的取值应根据信息码元按监督关系式来决定，根据信息码元按监督关系式来决定，根据信息码元按监督关系式来决定，根据信息码元按监督关系式来决定，即使上面三式中的即使上面三式中的即使上面三式中的即使上面三式中的S S1 1、S S2 2、S S3 3均为均为均为均为0 0：a a2 2+a+a4 4+a+a5 5+a+a6 6=0=0 a a1 1+a+a3 3+a+a5 5+a+a6 6=0 =0 （3 3）a a0 0+a+a3 3+a+a4 4+a+a6 6=0=0 a a2 2=a=a4 4+a+a5 5+a+a6 6 a a1 1=a=a3 3+a+a5 5+a+a6 6 （4 4）a a0 0=a=a3 3+a+a4 4+a+a6 6 于是，给定信息位后，根据上式算出各监督位，于是该编码的所有于是，给定信息位后，根据上式算出各监督位，于是该编码的所有于是，给定信息位后，根据上式算出各监督位，于是该编码的所有于是，给定信息位后，根据上式算出各监督位，于是该编码的所有 码组如下表：码组如下表：码组如下表：码组如下表：汉明码的编码效率较高，其编码效率：汉明码的编码效率较高，其编码效率：汉明码的编码效率较高，其编码效率：汉明码的编码效率较高，其编码效率：该汉明码的码率较高：该汉明码的码率较高：该汉明码的码率较高：该汉明码的码率较高：k/n=4/757%k/n=4/757%。与相同码长、能纠正。与相同码长、能纠正。与相同码长、能纠正。与相同码长、能纠正 一位错码的其他分组码相比，该码效率最高，且实现简单。一位错码的其他分组码相比，该码效率最高，且实现简单。一位错码的其他分组码相比，该码效率最高，且实现简单。一位错码的其他分组码相比，该码效率最高，且实现简单。1 1 1 1 a a a a6 6 6 6+1+1+1+1 a a a a5 5 5 5+1+1+1+1 a a a a4 4 4 4+0 +0 +0 +0 a a a a3 3 3 3+1+1+1+1 a a a a2 2 2 2+0 +0 +0 +0 a a a a1 1 1 1+0+0+0+0 a a a a0 0 0 0=0=0=0=01 1 1 1 a a a a6 6 6 6+1+1+1+1 a a a a5 5 5 5+0+0+0+0 a a a a4 4 4 4+1 +1 +1 +1 a a a a3 3 3 3+0+0+0+0 a a a a2 2 2 2+1 +1 +1 +1 a a a a1 1 1 1+0+0+0+0 a a a a0 0 0 0=0=0=0=01 1 1 1 a a a a6 6 6 6+0+0+0+0 a a a a5 5 5 5+1+1+1+1 a a a a4 4 4 4+1 +1 +1 +1 a a a a3 3 3 3+0+0+0+0 a a a a2 2 2 2+0 +0 +0 +0 a a a a1 1 1 1+1+1+1+1 a a a a0