《计算机组成原理》课堂笔记(2):数据表示及检错纠错

数据表示的需求

计算机是什么?

  • 一种高速运行的电子设备
  • 用于进行数据的计算
  • 可接受输入信息
  • 根据用户要求对信息进行加工
  • 输出结果

计算机运行机制

  • Datapath:完成算术和逻辑运算,通常包括其中的寄存器。
  • Control:CPU的组成部分,它根据程序指令来指挥datapath,memory以及I/O运行,共同完成程序功能。
  • Memory:存放运行时程序及其所需要的数据的场所。
  • Input:信息进入计算机的设备,如键盘、鼠标等。
  • Output:将计算结果展示给用户的设备,如显示器、磁盘、打印机、喇叭等。

数据编码与表示

需要在计算机中表示的对象:程序、整数、浮点数、字符(串)、逻辑值
表示方式:数字电路的两个状态;由上一层的抽象计算机识别不同内容
编码原则:

  • 少量简单的基本符号
  • 一定的规则
  • 表示大量复杂的信息
  • 计算性能/存储空间

编码表示

基本元素:0,1
字符:

  • 26字母=5位
  • 大小写+其他符号:7位(in 8)
  • 世界上其它语言的文字:16位(unicode)

无符号整数
逻辑值
颜色
位置/地址/指令

逻辑型数据表示

True:真(1)
False:假(0)
数据运算:与、或、非

字符的表示

重要的人机界面

  • 由符号组成
  • 为每个符号进行编码,由输入/输出设备进行转换
  • 一般以字符串的形式在计算机存储器中存放

字符集编码标准:主机和设备、主机之间进行信息交互的基础

  • ASCII
  • UNICODE
  • UTF-8

ASCII字符编码

American Standard Code for Information Interchange
7位二进制编码,占用一个字节
表示128个西文字符

UNICODE编码

16位表示一个字符,可以表示65536个字符
将整个编码空间划分为块,每块为16的整数倍,按块进行分配
保留6400个码点供本地化使用
依然无法覆盖所有字符

UTF-8编码

字符位数 字节1 字节2 字节3 字节4 字节5 字节6
7 0ddddddd
11 110ddddd 10dddddd
16 1110dddd 10dddddd 10dddddd
21 11110ddd 10dddddd 10dddddd 10dddddd
26 111110dd 10dddddd 10dddddd 10dddddd 10dddddd
31 1111110d 10dddddd 10dddddd 10dddddd 10dddddd 10dddddd

变长字符编码,提高存储空间利用率
字符长度由首字节确定
字符首字节外,均以10开始,可自同步
可扩展性强
成为互联网上占统治地位的字符集

整数的表示

数值型数据表示

定点数:整数,定点小数
浮点数:小数点位置浮动

数值范围和数据精度

数值范围:一种类型的数据所能表示的最大值和最小值
数据精度:实数所能给出的有效数字位数
机内处理:数值范围 != 数据精度

整数的二进制表示

二进制的两个状态0和1
n位可得到2^n种组合,可表示2^n个整数
无符号数:直观,便于算术运算的实现
有符号数:正负数平衡,便于算术运算的实现
进位计数法:$N= \sum_{i=m}^{-k} D_i r^i$

数制转换

二进制转换到十进制数:累加二进制数中全部数值为1的位的位权
二进制转换到八或16进制数:从小数点向左和向右每3或者4个二进制位分成一组,直接写出每一组代表的数值,小数点后不足位数补0.
十进制转换为二进制:整数部分除2取余数,小数部分乘2取整数。

原码、反码、补码的表示

正数的原码、反码、补码表示均相同,符号位为0,数值位同数的真值。
零的原码和反码均有2个编码,补码只有1个码。
负数的原码、反码、补码表示均不同:符号位为1,数值位:原码为数的绝对值;反码为每一位均取反码;补码为反码再在最低位+1
由[X]补求[-X]补:每一位取反后再在最低位+1

检错纠错码

数据或编码在存储、传输等过程中可能出错
如何判断是否已经出错?
判断方法:与所有正确的编码进行比较;检验是否存在某些特征特征
如何自动纠正?

码距

码距(最小码距)的概念:任意两个合法码之间至少有几个二进制位不相同。
合理增大码距,能提高发现错误的能力,但表示一定数量的合法码所使用的二进制位数要变多,增加了电子线路的复杂性和数据存储、数据传送的数量
奇偶校验码的码距为2,海明码的码距为4

常用检错纠错码

三种常用的检错纠错码:

  • 奇偶校验码:用于并行数据传送
  • 海明校验码:用于并行数据传送
  • 循环冗余校验码:用于串行数据传送

奇偶校验码

用于并行码检错
原理:在k位数据码之外增加1位校验位,使k+1位码字中取值为1的位数总保持为偶数(偶校验)或奇数(奇校验)。
例:0001 + 1 0001(偶校验)/0 0001(奇校验)

海明校验码

用于多位并行数据检错纠错处理
实现:为k个数据位设立r个校验位,使k+r位的码字同时具有这样两个特性:

  1. 能发现并改正k+r位中任何一位出错
  2. 能发现k+r位中任何二位出错,但已无法改正

k与r之间应该满足什么样的关系?

海明码的编码方法

合理地用k位数据位形成r个校验位的值,即保证用k个数据位中不同的数据位组合来形成每个校验位的值,使任何一个数据位出错时,将影响r个校验位中不同的校验位组合起变化。这样一来,就可以通过检查是哪种校验位组合起了变化,来推断是哪个数据位错造成的,对该位求反则实现纠错。
有时两位出错与某种情况的一位出错对校验位组合的影响相同,必须加以区分和解决。

位数r和k的关系:
2^r>=k+r+1,即用2^r个编码分别表示k个数据位、r个校验位中哪一位错。
2^(r-1)>=k+r,用r-1位校验码为出错位编码,再单独设一位用于区分1位还是2位同时出错。

海明码的实现方案

例:k=3,r=4
编码方案:
P1 = D2 ⊕ D1
P2 = D3 ⊕ D1
P3 = D3 ⊕ D2
P4 = P3 ⊕ P2 ⊕ P1 ⊕ D3 ⊕ D2⊕ D1
译码方案:
S1 = P1 ⊕ D2 ⊕ D1
S2 = P2 ⊕ D3 ⊕ D1
S3 = P3 ⊕ D3 ⊕ D2
S4 = P3 ⊕ P2 ⊕ P1 ⊕ D3 ⊕ D2⊕ D1
(一)准备工作
(1)将校验位P1、P2、P3依次安排在2的幂次方位(1、2、4),P4为总校验位,暂不考虑。
(二)为各校验位分配数据位组合
(1)看数据位的编号分别为3、5、6,它们是校验码编号的组合:3=1+2,5=1+4,6=2+4
(2)1出现在3和5中,则P1负责对D1和D2进行校验。
(3)2出现在3和6中,则P2负责对D1和D3进行校验。
(4)4出现在5和6中,则P3负责对D2和D3进行校验。
(三)写出各校验位的编码逻辑表达式
(1)结果:P1 = D2 ⊕ D1;P2 = D3 ⊕ D1;P3 = D3 ⊕ D2
(2)用其他各校验位及各数据位进行异或运算求校验位P4的值,用于区分无错、奇数位错、偶数位错3种情况。总校验位P4 = P3 ⊕ P2 ⊕ P1 ⊕ D3 ⊕ D2⊕ D1
译码方案:排查是哪一位错了,看S4-S1的编码值。


新增一则回应

除非特别注明,本页内容采用以下授权方式: Creative Commons Attribution-ShareAlike 3.0 License