错误修正

本文最后更新于：2020年12月24日 上午

错误修正

  • 半导体存储系统是很容易出错的

  • 错误类型：

    • 硬故障
      • 永久性的物理故障，以至于影响存储单元不能可靠的存储数据，称为固定的“1”或“0”或其之间跳转的故障
    • 软差错
      • 随即非破坏性事件，改变了存储单元的内容，但是不破坏存储器
      • 可以是电源问题或$a$粒子引起

  • 基本思想：增加一些额外的位用来存储纠错信息

  • 过程：

    • 输入的数据：M位的数据D和映射函数$f$产生的K位纠错码C

    • 输出的数据：一个新的数据$D{'}$和映射函数$f$产生的K位纠错码$C{‘’}$，并且和已经存在的K位纠错码$C^{'}$进行比较

      • 没有检测出错误：传送数据$D^{'}$
      • 检测出一个可以修改的错误：纠正错误然后发送纠正后的数据
      • 检测出一个不可修改的错误：报告错误
      • Error Correction

    奇偶校验

    • 基础思想：通过增加一位来确定数字1在数据中出现的是奇数词或偶数次
    • 过程：
      • 假设数据$D=D_{M}…D_{2}D_{1}$
      • 输入的数据：
        • 奇校验位：$C=D_{M} \bigoplus … \bigoplus D_{2} \bigoplus D_{1} \bigoplus 1$；
        • 偶校验位：$C=D_{M} \bigoplus … \bigoplus D_{2} \bigoplus D_{1}$；
      • 输出的数据：
        • 奇校验位：$C=D^{‘}{M} \bigoplus … \bigoplus D^{'}{2} \bigoplus D^{’}_{1} \bigoplus 1$；
        • 偶校验位：$C=D^{‘}{M} \bigoplus … \bigoplus D^{'}{2} \bigoplus D^{’}_{1}$；
      • 检查：$S=C^{‘’} \bigoplus C^{'}$
        • S = 1: 出错的位数是奇数个
        • S = 0：正确或出错的位数的偶数个
    • 简单说明：奇偶校验位，其中0的出现对结果没有影响，所以只考虑1，如果出现了偶数个1，定义奇数位是0，这个是定义的，偶数位必然和奇数位相反。
    • 优点：消耗少
    • 缺点：出错位数是奇数个时，不能找出具体出错的地方；也不能用来进行纠错
    • comment：比较是用于一个字节的数据的检验

海明码/汉明码

  • 基本思想：把数据位分成不同的组，然后使用奇偶校验码来对每组进行纠错和检验
  • 步骤：
    • 将M位分成K组
    • 输入的数据：用一位来指示一组，生成K位的校验码
    • 输出的数据：用一位来指示一组，生成一个新的K位的校验码
    • 校验：对获取的数据，重新计算出一个K位的校验码，把这个重新计算出的校验码和同数据一同传过来的数据中含有的校验码进行异或，获得一个K位的故障字。
  • 校验码的长度
    • 前提假设：最多的错误是数据中只有1位出现错误
    • 可能的错误：
      • 1位数据位出错：M
      • 一位校验码错误：K
      • 没有错误：1
    • 校验码长度：$2^{k} \geq M + K + 1$
  • 对于故障字的值
    • 把故障字的值映射到可能出错或需要的环境
    • 规则：
      • 全0：没有检测出错误
      • 全1：检查位中出现了一位错误，但是不需要纠正，因为传输出去的时候会重新计算校验码
      • 其他位：将这些位用来一一对应一个错误（或者闲置），并且用来进行纠错
  • 数据位的划分
    • 假设8位的数据$D=D_{8}…D_{2}D_{1}$，4位校验码是$C=C_{4}C_{3}C_{2}C_{1}$
    • 数据位+校验码与故障字的关系：
  • SEC（single_error_correcting）:可以找到并修正1位的错误
  • SEC-DED（single_error_correcting, double_error_detecting）:可以找到2位错误，并修正1位错误
    • 增加额外的一位：$C_{5} = D_{1} \bigoplus D_{2} \bigoplus D_{3} \bigoplus D_{5} \bigoplus D_{6} \bigoplus D_{8}$
    • 一位的错误出现了，三位的校验码会被改变

Cyclic Redundancy Check

  • 奇偶校验码的问题
    • 额外的消耗太大
    • 需要将数据划分成字节
  • CRC
    • 适用于存储和传输以流的形式的大容量的数据
    • 通过数据函数生成数据的校验码
  • 基本思想
    • 假设数据N位，左移后与K+1位的生成多项式进行模二除法
    • 使用K位的余数作为校验码
    • 把校验码放在数据的后面
  • Check
    • 如果N+K位数据同生成多项式进行模二除法能够进整除，没有错误出现
    • 否则，出现错误
  • 例子：
  • 编程算法：
    • 数据D，生成多项式Pol，长度分别为N，K+1
    • 在数据D后面加上K+1位0，同Pol进行模二除法（取异或）
    • 最后获取的K位余数即为校验码
    • Check同理