计算机组成原理-第4章 存储器-5(校验)

计算机组成原理第四章 存储器llxx@ wjluo@随机存储器（RAM）掩模式ROM 可编程式PROM 可擦写式EPROM 电擦写式EEPROM2. 主存储器 （半导体存储器）静态RAM 动态RAM内容只读存储器（ROM）3. 存储器与CPU的连接4. 存储器的校验—海明码5. 提高访存速度的措施1. 主存储器的基本组成和技术指标Google：数据存储设备可靠性• DRAM错误率超出人们预想 – “可能成为系统宕机和服务中断的罪魁祸首” • DIMM中有约8.2%受到了可修正错误的影响 • 平均一个DIMM每年发生3700次可修正错误 – 错误类型：软错误、硬错误 • 由电磁干扰或者硬件故障所导致 • 软错误：很少损坏字位，但是并不会避免物理损坏 ，这是可修正的； • 硬错误：会损坏DRAM中的字位而成为物理缺陷， 从而造成数据错误的反复发生 • 硬盘：数据失效率高达6%（厂商：2%） – 错误类型：位跳变（可由ECC纠错），物理损坏容错计算容错计算FAULT-TOLERANT COMPUTING• Failure(失效/故障): When a component is not living up to its specifications, a failure occurs • Error(错误): The part of a component's state that can lead to a failure • Fault(缺陷): The cause of an error. Types: – Transient(偶发): occur once, then disappear – Intermittent(间歇): occur, then vanish, then reappear – Permanent(持久): continues to exist • 容错计算系统：在出现一定限度的失效的情况下， 依旧能够提供所需要的服务. – “难于消除，只能掩盖(使之不影响系统的正常使用)” – 检错（是否错，哪里错），纠错Fault Tolerance：RedundancyMain approach: mask failures using redundancy• 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奇偶编码校验（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 • 为什么能容错？具有什么容错能力？00000001001000110100010101100111100010011010101111001101111011114位表示16个状态不能检出错误！00000001001000110100010101100111100010011010101111001101111011114位表示8个状态可能检出错误！合法编码非法编码码距：海明（Hamming）距 离两个等长码字之间对应位不 同的个数相邻两个合法代码之间的不 相同位数相邻两个合法代码之间的不 相同位数编码纠错理论• 任何一种编码是否具有检测能力或纠错能力，都与 编码的最小距离有关 • 根据纠错律论：L-1＝D+C 且 D>=C – 即编码最小距离L越大，则其检测错误的位数D也越大， 纠正错误位数C也越大，且纠错能力恒小于或等于检测 能力。

•例如，L＝3，则D＝2，C＝0；或D=1，C=1 – 增大L，提高检错和纠错能力 • 应用 – 数据通信：奇偶校验（串行），CRC（网络） – 硬盘：CRC – 内存：ECC（错误检查和纠正）校验奇偶编码校验• 在被传送的n位代码(bn-1bn-2...b1b0)上增加一位 校验位P，将原数据和得到的奇（偶）校验位 一起进行存取或传送(即传送Pbn-1bn-2...b1b0)• 可以发现奇数个错 – 只能检错，不能纠错（？） – 一位出错的概率高奇偶校验的实现＝10R(7)＝1R(6)＝1R(5)＝1R(4)＝1R(3)＝1R(2)＝1R(1)＝1R(0)P＝1R(6)R(7)＝1R(4)R(5)＝1R(2)R(3)＝1R(0)R(1)＝1＝1＝1 P验证电路？奇偶校验的实现（续）entity IPAR isgeneric(PROP_DEL: time);port(R: in Std_logic_vector( 7 down to 0); P: out Std_logic);end IPAR;architecture LOOP4 of IPAR issignal CLOCK: Std_logic := ‘0’;beginOPAR: process(R)variable X: Std_logic;beginX := ‘0’;for I in 7 downto 0 loopX := X xor R(I);end loop;P <= X after PROP_DEL;end process;end LOOP4;对数据块的横向和纵向都有奇偶校验位。

例如：A7A6A5A4A3A2A1A0横向校验位 第横向校验位 第1字节字节11001011 → 1 第第2字节字节01111100 → 1 第第3字节字节10011010 → 0 第第4字节字节10010101 → 0 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 纵向校验位纵向校验位 10111000交叉奇偶校验能够发现两个位同时出错交叉奇偶校验能够发现两个位同时出错交叉奇偶校验（ECC）1位纠错 Hamming码校验码(校验位数)–海明码需要几位校验码？ 数据位k 校验位r 总位数n 1 2 3 2~4 3 5~7 5~11 4 9~15 12~26 5 17~31 27~57 6 33~63 58~120 7 65~127• 设有k位数据，r位校验位。

• r位校验位有2r个组合 – 若用0表示无差错，则剩余2r-1个值表示有差错，并指出 错在第几位 • 由于差错可能发生在k个数据位中或r个校验位中， 因此有：2r–1r+k海明校验码(校验位置)– 校验位和数据位是如何排列的校验位排列在2i–1(i =0,1,2,…)的位置上例1：有一个4位数为D4D3D2D1,需要3位校验码P3P2P1， 由此生成一个海明码 7 6 5 4 3 2 1 D4 D3 D2 P3 D1 P2 P1 2221 20 例2：有一字节的信息需生成海明码12 11 10 9 8 7 6 5 4 3 2 1 D8 D7 D6 D5 P4D4 D3 D2 P3 D1 P2 P1 8 4 2 1校验位取值公式及计算举例• 海明码的校验位Pi和数值位Di的关系 – 设k位数据，r位校验码，把k+r=m个数据记为HmHm-1... H2H1(海明码）, 每个校验位Pi在海明码中被分配在2i-1位置上。

– Hi由多个校验位校验：每个海明码的位号要等于参与校验它的几个检验 位的位号之和得：H3由P1和P2校验，H5由P1和P4校验， H6由P2和P4校验，H7由 P1、P2和P4校验， 即：Pi参与第j1、j2、…、jx个校验位的计算(P1参与H3、H5、H7、…))...(2...222121 xjjjjjjix分解分解例：每个数据位至少出现在两个每个数据位至少出现在两个Pi值的形成关系中当任一数 据位发生变化时，必将引起二或三个值的形成关系中当任一数 据位发生变化时，必将引起二或三个Pi值跟着变化数据位为值跟着变化数据位为1011（偶校验）（偶校验）P3= D4⊕⊕D3 ⊕⊕D20 = 1 ⊕⊕ 0 ⊕⊕ 1P2= D4 ⊕⊕D3 ⊕⊕D10 = 1 ⊕⊕ 0 ⊕⊕ 1P1 = D4 ⊕⊕D2 ⊕⊕D11 = 1 ⊕⊕ 1 ⊕⊕ 1最后，海明码为最后，海明码为1010101H 7654321 D4D3D2P3D1P2P122D4D3D2P321D4D3D1P220D4D2D1P1海明码的纠错原理• 海明码的接收端的公式: – S3= P3⊕ D4⊕D3⊕D2 S2=P2⊕D4⊕D3⊕D1 S1= P1⊕D4⊕D2⊕D1 – 假定 海明码1010101在传送中变成了1000101 S3= P3⊕ D4⊕D3⊕D2=0⊕1⊕0 ⊕0=1 S2=P2⊕D4⊕D3⊕D1=0⊕1⊕ 0 ⊕1=0 S1= P1⊕D4⊕D2⊕D1=1⊕1⊕ 0 ⊕1=1 因此,由S3S2S1= 101,指出第5位错,应由0变11位纠错海明码的应用• 上述海明码称为单纠错码（SEC） – 是否可以发现多位错？奇数位错？偶数位错？ • 通常半导体存储器采用SEC-DED（单纠错- 双检错码）。

– SEC-DED与SEC相比需要增加1个附加位 • 在IBM3000系列中，主存64位数据采用8位SEC- DED码进行校验； • VAX计算机中32位字长机器，采用7位SED-DED码CRC校验码CRC（Cyclic Redundancy Check）• CRC：各类介质存储器、数据通信• 基于模2运算：不考虑进位和借位• 模2加减运算：异或（相同为“0”，不同为“1”） • 模2乘：按模2加求部分积之和 • 模2除：按模2减求部分余数 –部分余数首位为1，商1 –部分余数首位为0，商0 –每上商一次，部分余数减少一位 –部分余数位数少于除数位数时，结束模2运算举例011101000110        1010X 10110100000 1010 10001010000101101101 0010 000 0100 101 001余数＝01CRC校验步骤• CRC生成 – 将n位数据Dn-1,…D0用n-1次多项式M(x)表示，即 M(x)＝ Dn-1xn-1+ Dn-2xn-2+…+ D1x1+ D0x0 – 将M(x)左移k位（补0），即得：M(x)*xk – 将M(x)*xk除以k+1位的生成多项式G(x。