考研笔记-计算机之计算机组成原理:存储器(编码检错纠错方法)

表-编码纠错理论

编码最小距离

是指在一种编码系统中，任意两组合法代码之间的最少二进制位数的差异。

编码纠错原理

任何一种编码是否具有检错能力和纠错能力，都与编码的最小距离有关。

根据纠错理论得，，即编码最小距离L越大，则其检测错误的位数D越大，纠正错误的位数C也越大，且纠正错误的能力恒小于等于检错能力。

表-汉明码

汉明码的定义

具有一位纠错能力的编码。设欲检测的二进制代码为n位，为使其具有纠错能力，需增添k位检测位，组成n+k位的代码，为了能准确对错误定位以及指出代码没错，新增添的检测位数k应满足：（汉明码需满足的条件。因出错位是校验出错的各小组共有的位，其位序号为，i为校验出错的小组的序号，故为能区分所有的出错位，应保证出错位的最大位序号大于等于n+k，即）（若在纠正1位错的同时还要能发现2位错，则应满足）。

汉明码小组分配原理

设n+k位代码自左至右依次编为第1，2，3，…，n+k位，将k位检测位记作（），分别安插在n+k位代码编号的第位上。这些检测位的位置设置是为了保证它们能分别承担n+k位信息中不同数位所组成的“小组”（共有k个）的奇偶检测任务，使检测位和它所负责检测的小组中1的个数为奇数或偶数。汉明码的实现原理实际是：通过添加校验位，使码距比较均匀地拉大，并把汉明码的每一个二进制位同时分配到几个奇偶校验组中，当某一位出错后，就会引起有关的几个校验位的值发生变化。

汉明码小组分配方法

每组（）的首位（即该组的检测位）序号为，组内每块的连续位数为，组内各块之间的间隔为。

汉明码小组分配特点：

① 每一个小组有且仅有一位（该组的检测位）为它所独有，这一位是其他小组所没有的，即小组独占第位（）；

② 每两个小组和有且仅有一位为它们共同独有，这一位是其他小组所没有的，即每两个小组和共同独占第位（）；

③ 每三个小组、和有且仅有一位为它们共同独有，这一位是其他小组所没有的，即每三个小组、和共同独占第位（）；

依次类推，便可确定每组所包含的各位。

汉明码检测位的计算

计算依据

偶数个1异或得0。

配偶原则

每组的检测位为该组内除检测位外其它各位的异或（因为若异或结果为0（1），则说明该组中除检测位外已含有偶（奇）数个1，故检测位应为0（1））。

配奇原则

每组的检测位为该组内除检测位外其它各位的异或结果取反（因为若异或结果为0（1），则说明该组中除检测位外已含有偶（奇）数个1，故检测位应为1（0））。

汉明码的纠错

汉明码的纠错过程实际是对采用汉明码编码后的代码形成新的检测位（），根据的状态，便可直接指出错误的位置。的状态是由原检测位所在小组内“1”的个数确定的。按配偶原则配置的汉明码，其对采用汉明码编码后的代码形成的新检测位应为0，否则说明数据有错，且出错位的位置序号为由所有新检测位（）所形成的二进制值（因为，①出错位由的各个小组所共有，且该出错位在汉明码中的序号为的各个的序号之和；②各检测位在汉明码中的序号恰为各对应的新检测位在它们所形成的二进制值中所在位的权值。）

汉明码的配置步骤

步骤：①计算要添加的检测位的位数；②确定各个检测位的位置；③按奇或偶原则配置各个检测位的值。（奇数配置原则下，①各配置位的取值，②用于判断是否出错的新检测位的取值，③用于确定出错位的序号的二进制值，均为偶数配置原则下相应的数值取反。）

表-CRC码

CRC码的编码原理

CRC码是基于模2运算而建立编码规律的校验码。模2运算是不考虑进位和借位的运算，其特点如下：

① 模2加和模2减的结果是相等的，即0±1=1，1±0=1，0±0=0，1±1=0，即为异或运算；

② 模2乘是按模2加求部分积之和；

③ 模2除是按模2减求部分余数，每求一位商应使部分余数（高位或首位）减少一位。上商的原则是：当部分余数的首位为1时，上商1；当部分余数的首位为0时，上商0。当部分余数的位数小于除数的位数时，该余数即为最后余数。

CRC码的编码方法

设待编的信息码组为D_n-1D_n-2…D₂D₁D₀，共n位，它可用多项式M(x)表示：M(x) = D_n-1x^n-1+D_n-2x^n-2+…D₂x²+D₁x¹+D₀x⁰，将信息码左移k位，得M(x)·x^k，即成n+k位信息码组：D_n-1+kD_n-2+k…D_2+kD_1+kD_0+k0_k-10_k-2…0₂0₁0₀，空出的k位用来拼接k位校验位。CRC码就是用多项式M(x)·x^k除以生成多项式G(x)（即产生校验码的多项式），所得余数作为校验位。为了得到k位余数（校验位），G(x)必须是k+1位，即G(x)必须是k次幂的。设所得的余数为R(x)，商为Q(x)，则有M(x)·x^k =   Q(x)·G(x)+R(x)，将校验位余数R(x)拼接在左移了k位后的信息位后面，就构成了有效信息的CRC码，这个CRC码用多项式表示为M(x)·x^k+R(x) = (Q(x)·G(x)+R(x))+R(x) = Q(x)·G(x)+(R(x)+R(x)) = Q(x)·G(x)（R(x)+R(x) = 0(模2加)），因此CRC码是一个可以被生成多项式G(x)除尽的数码（实际上M(x)·x^k+R(x)   = M(x)·x^k-R(x) (模2加与模2减)，因而CRC码必定可被被生成多项式G(x)除尽）。CRC码在传输中若不出错，则余数必为0，若出错，则余数不为0。总信息位为m位，有效信息位为n位的CRC码称为（m，n）码，（m，n）码即为CRC码的码制。（信息码左移的位数即为生成多项式的G(x)的次幂数，因为信息码左移的原因是必须容下生成的余数，而余数的位数为G(x)的位数减1，即G(x)的次幂数k）

CRC码的译码

将收到的CRC码用约定的生成多项式G(x)去除，若无错，则余数应为0，若某一位出错，则除数不为0。不同的出错位其余数不同。余数和出错位的对应关系只与码制和生成多项式有关，与具体的CRC码无关。

CRC码的纠错

当CRC码出错时，如果对不为0的余数末位补0继续除下去，将发现各次所得的余数按CRC码从当前出错位开始按从低位到高位的方向各位单独出错时所得的余数顺序循环，此即“循环码”名称的由来。这个特点正好用来纠错，即当出现不为0的余数后，一方面对余数末位补0继续作模2除，另一方面将被检测的CRC码循环左移，当余数变为CRC码的最高位出错时对应的余数时，将此时循环左移得到的CRC码的最高位取反，这样当移满一个循环（对（m，n）码共m次）后，就得到一个纠正后的CRC码。

CRC码的生成多项式

CRC码的生成多项式应满足的条件：

① 任何一位发生错误都应使余数不为零；

② 不同位发生错误应使余数不同；

③ 对余数继续作模2除应使余数循环。

表-奇偶校验码

奇偶校验码定义

奇偶校验码种类

包括奇偶校验位在内的所有位中1的个数为奇数或偶数

奇校验码

包括奇偶校验位在内的所有位中1的个数为奇数

偶校验码

包括奇偶校验位在内的所有位中1的个数为偶数