Fault Tolerance:Redundancy 提高MTTF:避免，容忍，预测 -故障“难以消除(eliminate),只能掩盖(mask) 。 容错计算系统：出现一定限度的失效时，依然能够提供所 需要的服务. 一服务降级：使之不影响系统的正常使用 冗余 Information redundancy Eg,a Hamming code can be added to transmitted data to recover from noise on the tansmission line. Time redundancy is especially helpful for transient or intermittent faults. ·Eg,using transactions(▣滚，rollback) Physical redundancy Eg,747s have four engines but can fly on three ·RAID 容错能力：检错（发现，定位），纠错
Fault Tolerance：Redundancy • 提高MTTF：避免，容忍，预测 – 故障“难以消除（eliminate），只能掩盖（mask）” • 容错计算系统：出现一定限度的失效时，依然能够提供所 需要的服务. – 服务降级：使之不影响系统的正常使用 • 冗余 – Information redundancy • Eg, a Hamming code can be added to transmitted data to recover from noise on the tansmission line. – Time redundancy • is especially helpful for transient or intermittent faults. • Eg, using transactions(回滚，rollback) – Physical redundancy • Eg, 747s have four engines but can fly on three • RAID • 容错能力：检错（发现，定位），纠错
Error Checking and Correcting Two major types of data errors can occur in data transmission: -hard errors,which are permanent,arise from broken interconnects,internal shorts,or open leads - soft errors,which are transient,are caused by system noise,power surges,and alpha particles. The processor (MIPS R4000)verifies data correctness by using either the parity or the SECDED code as it passes data from the System interface to the secondary cache,or it moves data from the secondary cache to the primary caches or to the System interface
Error Checking and Correcting • Two major types of data errors can occur in data transmission: – hard errors, which are permanent, arise from broken interconnects, internal shorts, or open leads – soft errors, which are transient, are caused by system noise, power surges, and alpha particles. • The processor（MIPS R4000）verifies data correctness by using either the parity or the SECDED code as it passes data from the System interface to the secondary cache, or it moves data from the secondary cache to the primary caches or to the System interface
奇偶编码校验 (Parity Check Code) ·编码规则 在被传送的n位代码(bn.bn2bbo）上（最后）增加一位校 验位P(Parity),将原数据与奇（偶）校验位（生成 算法)一起进行存取或传送（即传送Pbn.bn-2bb）)。 奇校验：使“1”的个数为奇数 ·00000000->000000001 ·00000001->000000010 一 偶校验：使“1”的个数为偶数 ·00000000->000000000 ·00000001->000000011 ·为什么能容错？具有什么容错能力？
奇偶编码校验（Parity Check Code） • 编码规则 – 在被传送的n位代码(bn-1bn-2 ...b1b0 )上（最后）增加一位校 验位P（Parity），将原数据与奇（偶）校验位（生成 算法）一起进行存取或传送(即传送Pbn-1bn-2 ...b1b0 ) 。 – 奇校验：使“1”的个数为奇数 • 0000 0000－>0000 0000 1 • 0000 0001－>0000 0001 0 – 偶校验：使“1”的个数为偶数 • 0000 0000－>0000 0000 0 • 0000 0001－>0000 0001 1 • 为什么能容错？具有什么容错能力？
0000 0000 0001 0001 0010 0010 合法编码 0011 0011 0100 0100 0101 0101k 非法编码 4位表示 0110 4位表示 0110 16个状态 0111 8个状态 0111 《通信原理》 不能检出错误！ 1000 可能检出错误！ 1000 码距：海明(Hamming)距离 1001 1001 两个等长码字之间对应位 1010 1010 不同的个数 1011 1011 相邻两个合法码字之间的不相 1100 1100 同位数 1101 1101 1110 1110 奇偶，格雷，海明，Reed Solomon? 1111 1111
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 4位表示 16个状态 不能检出错误！ 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 4位表示 8个状态 可能检出错误！ 合法编码 非法编码 《通信原理》 码距：海明（Hamming）距离 两个等长码字之间对应位 不同的个数 相邻两个合法码字之间的不相 同位数 奇偶，格雷，海明，ReedSolomon？
编码纠错理论 USTC 任何一种编码是否具有检测能力或纠错能力，都与 编码的最小距离有关。 根据纠错律论：L-1=D+C且D>=C 即编码最小距离L越大，则其检测错误的位数D也越大， 纠正错误位数C也越大，且纠错能力恒小于或等于检测 能力。 ·例如，L=3,则D=2,C=0;或D=1,C=1。 一增大L,提高检错和纠错能力。 应用 一内存：奇偶，ECC(错误检查和纠正)，SECDED 硬盘：CRC -通信：奇偶（串行，物理层），海明，CRC(网络层)
编码纠错理论 • 任何一种编码是否具有检测能力或纠错能力，都与 编码的最小距离有关。 • 根据纠错律论：L-1＝D+C 且 D>=C – 即编码最小距离L越大，则其检测错误的位数D也越大， 纠正错误位数C也越大，且纠错能力恒小于或等于检测 能力。 • 例如，L＝3，则D＝2，C＝0；或D=1，C=1。 – 增大L，提高检错和纠错能力。 • 应用 – 内存：奇偶，ECC（错误检查和纠正），SECDED – 硬盘：CRC – 通信：奇偶（串行，物理层），海明，CRC（网络层）