COA-2019-第十章 Error Correction

lecture10 Error Correction

1. 错误(Error)

1. A semiconductor memory system is subject to errors(半导体系统容易导致错误)
2. Type(类型)
   1. Hard failure(硬件错误)
      • A permanent physical defect so that the memory cell or cells become stuck at 0 or 1 or switch erratically between 0 and 1(一种永久性的物理损坏，导致一个或多个存储单元卡在0或1上，或在0和1之间不稳定地切换)
      • Caused by harsh environmental abuse and manufacturing defects(由恶劣的环境滥用和制造缺陷造成硬件损坏)
   2. Soft failure(软件错误)
      • A random, nondestructive event that alters the contents of one or more memory cells without damaging the memory(一个随机的、非破坏性的事件可能改变一个或者更多的存储单元，而并不是破坏这些存储单元)
      • Caused by power supply problems or alpha particles(可能是由于电脑的电量问题或者alpha粒子等导致的问题)
3. 是发现哪一位错误更加困难，还是改正一个错误困难
   • 发现错误更难，因为改正错误取反即可(因为只有0和1这两种状态)。

2. 错误修正(Error Correction)

1. Basic idea(基本观点)
   • Add some bits to store additional information for correction(添加一些位的数据来存储一些用于判断数据正误的额外信息)
2. Process(过程)
   • Data in(输入): produce a ?? bits code ?? on the ?? bits data ?? with a function ??(原始数据D，其长度M，对其应用方法f生成额外信息C,其长度为K位，然后我们存储D和C)
   • Data out(输出): produce a new ?? bits code ??′′ on the data ??′ with function ??, and compare with the obtained ?? bits code ??′(根据新的取出来的D’，再次对其应用方法f得到新的额外信息C’’，和拿出来的C’进行比较。)
     • No error detected: send ??′
     • An error detected which can be corrected: correct it and send ??’’
     • An error detected which cannot be corrected: report
   • 注:我们可以认为方法f是不会出错的，为什么为如果f出错，作为一个程序，是无法正常运行的。
3. 额外信息C作为一个信息也可能是有可能出错的。
   • 存储的额外的信息不能够太大，不然成本太高。
4. 一旦存入C，拿出来的数据就是C’，而原来的C已经永远的消失了
   • 为什么为如果能拿到原来的C，那么以上所有的事情都没有意义。
5. 一切的假设前提:数据出错的频率是很低的
   • 也就是C和D同时出错是极小概率的。

2.1. 过程

3. 为什么我们不能让汉明码特别长
   • 因为一旦太长了，数据两位出错的概率会增加，二者就不符合之前的假设了。

2.3.2. 故障字的意义

1. Map each value of syndrome word to one possible situation(每一个故障字的值对应着一种情况)
2. Rule(规则)
   • All 0s: no error has been detected(如果故障字全是0:我们认为没有发生错误)
   • One bit is 1: an error has occurred in one of the check bits, and no correction is needed(如果故障字有一位为1:我们认为大概率是因为校验码出问题，并且我们不需要进行修改数据，为什么为数据出现问题影响的不止一位)
   • More than one bit is 1: the numerical value of the syndrome indicates the position of the data bit in error, and invert this data bit for correction(如果故障字超过1位为1:我们认为数据出现了问题，需要修正)
3. C’和C’’生成故障字。

2.3.3. 数据划分

1. Dada bits division(数据位数的划分)
   • Assume the 8 bits data is ?? = ??₈…??₂??₁, the 4 bits check code is ?? = ??₄??₃??₂??₁(我们假设数据一共8位，根据之前我们可以知道故障字的长度为4)
   • Relationship of data bit / check code and syndrome word(数据/检查字和故障字之间的关系)

1. case1:正常情况下的S的值为0000
2. case2:第九位(1为基)出错，那么我们算得S为1001
3. case3:第八位(1为基)出错，那么我们算得S为1000

2.3.5. 汉明码的扩展

1. SEC
   • Single-Error-Correcting
   • Can find and correct one bit error(可以发现一位的错误，并且确定一位的错误的位置)
2. SEC-DED
   • Single-Error-Correcting, Double-Error-Detecting
   • Can find two bits error and check one bit error(我们可以发现两位的错误，并且确定一位的错误位置)
   • Add one additional bit
     • ??5 = ??1 ⊕ ??2 ⊕ ??3 ⊕ ??5 ⊕ ??6 ⊕ ??8
   • If an error occurs in one bit data, three bits check code will be changed(如果一个错误出现在一位的数据中，那么三位的检查码会被改变)
   • 理论上不要求

SEC-DED的判断

1. All 0s: no error has been detected(如果故障字全为0，那么我们没有发现错误)
2. One bit is 1: an error has occurred in one of the 5 check bits, and no correction is needed(如果错误发生在5个检查位之一，那么我们认为是故障字出错，而并不是数据出现问题)
3. Two bits are 1: errors have occurred in two of data and check bits, but the positions of errors cannot be found(如果故障字中出现两个1，那么我们知道有两个位置发生了错误，但是无法定位)
4. Three bits are 1: an error has occurred in one of the 8 data bits, and the error can be corrected(如果故障字有三个1，那么我们知道在8位数据中出现了错误，并且我们可以获得错误的位置)
5. More than three bits are 1: serious situation, examine the hardware(如果有超过3个1，那么我们认为发生了很严重的情况，检查硬件状况)
6. 本部分中所有的位置均值数据和检查位的错误位之和。

SEC-DED的特点

1. An error-correcting code enhances the reliability of the memory at the cost of added complexity(纠错码以增加复杂度为代价提高了存储器的可靠性。)
2. The size of main memory is actually larger than is apparent to the user(主存储器的大小实际上比用户看到的要大得多)

3. 最后存储的结果为100011 + 111

文章知识点与官方知识档案匹配，可进一步学习相关知识CS入门技能树Linux入门初识Linux25035 人正在系统学习中