赞
踩
ps: 在上午考试中一般占到6分
R
R
R进制转十进制使用按权展开法。其具体操作方式为 : 将
R
R
R进制数的每一位数值用
R
k
R^{k}
Rk形式表示,即幂的底数是
R
R
R,指数为
k
k
k,
k
k
k与该位和小数点之间的距离有关。当该位位于小数点左边,
k
k
k值是该位和小数点之间数码的个数,而当该位位于小数点右边,
k
k
k值是负值,其绝对值是该位和小数点之间数码的个数加
1
1
1。
例如: 二进制
10100.01
=
1
×
2
4
+
1
×
2
2
+
1
×
2
−
2
10100.01 = 1 \times 2^{4} + 1 \times 2^{2} + 1 \times 2^{-2}
10100.01=1×24+1×22+1×2−2
例如: 七进制
604.01
=
6
×
7
2
+
4
×
7
0
+
1
×
7
−
2
604.01 = 6 \times 7^{2} + 4 \times 7^{0} + 1 \times 7^{-2}
604.01=6×72+4×70+1×7−2
十进制转
R
R
R进制使用短除法。其具体操作方式为: 将
R
R
R作为除数,十进制数作为被除数,即将十进制数除以
R
R
R再取余,直到商等于0为止,然后将余数由下往上按顺序排列。
例如: 将94转换为二进制数。
2
94
余
0
2
47
1
2
23
1
2
11
1
2
5
1
2
2
0
2
1
1
0
得到结果为
1011110
二进制转八进制与十六进制。其具体操作方式为: 将二进制数以小数点为界向左及向右每三个一组(转八进制),或者每四个一组(转十六进制),缺的数用零来补充,然后依次通过按权展开法转化为相应的进制数然后按顺序排列即可。
10
001
110
2
1
6
1000
1110
8
E
10{\color{Blue} 001} {\color{Red} 110} \\ 2 \quad 1 \quad 6 \\ 1000{\color{Red} 1110} \\ 8 \quad E
10001110216100011108E
原码: ①将一个数转换为二进制的表达形式 ②如果该二进制不足8位就在其左方进行补零。其中首位为符号位,0表示正,1表示负,故首位需要根据正负进行填充。③我们将1和-1的原码相加后得到的原码不是0,说明原码的操作方式是不能直接运用到计算机中进行运算的,故提出了其它编码方式。
反码: ①正数的反码与原码一致;负数的反码是符号位不变,然后将后面所有位按位取反(1变0、0变1)。②1和-1的反码的运算是正确的,就是看起来有些怪异,结果为-0。
补码: ①正数的补码与原码、反码一致;负数的补码是在反码的基础上加一。②我们将1和-1的补码相加后得到的补码结果为0,说明补码的操作方式是可以直接运用到计算机中进行运算的。
移码: ①通常用于表示浮点运算中的阶码 ②正负数的移码都只是将补码的首位按位取反即可。③为什么会存在移码呢? 如果我们使用补码在竖轴(y轴)上进行表示感觉不好理解,上方为正数但是首位为0,而将符号位改变就比较好理解。同时移码进行相关操作也能够得到正确的值,但就是看起来有些怪异,结果为+0。
数值1
数值-1
1-1
原码
00000001
10000001
10000010
反码
00000001
11111110
11111111
补码
00000001
11111111
00000000
移码
10000001
01111111
10000000
整数
原码
−
(
2
n
−
1
−
1
)
∼
2
n
−
1
−
1
反码
−
(
2
n
−
1
−
1
)
∼
2
n
−
1
−
1
补码
−
2
n
−
1
∼
2
n
−
1
−
1
浮点数表示:
N
=
M
∗
R
e
其中
M
M
M称为尾数,
e
e
e是指数,
R
R
R为基数。
浮点数之间的计算操作:
对阶
⟶
尾数计算
⟶
结果格式化
\text { 对阶 } \longrightarrow \text { 尾数计算 } \longrightarrow \text { 结果格式化 }
对阶 ⟶ 尾数计算 ⟶ 结果格式化
对阶: 让低的指数向高的指数看齐。
尾数计算: 对尾数计算即可。
结果格式化: 确保小数点左边不能为0且为个位数。
例如:
1000
+
119
1000 + 119
1000+119的浮点计算过程
1000
+
119
=
1.0
×
1
0
3
+
1.19
×
1
0
2
对
阶
:
1.0
×
1
0
3
+
0.119
×
1
0
3
尾
数
计
算
:
1.119
×
1
0
3
结
果
格
式
化
:
1.119
×
1
0
3
就
是
最
终
结
果
。
主机是计算机结构的核心部分,它并不是我们日常说的主机箱。
主机包括CPU和主存储器。CPU包括运算器和控制器。
像硬盘,声卡,显卡都归为外设。
考试中运算器和控制器的构成是很重要的考点。
运行程序时,需要调取相应的指令内容,需要控制,因此和指令有关的往往是控制相关的。
Flynn分类法是一种计算机体系结构分类方式。将计算机分为四大类。
分类依据有两个指标 :指令流,数据流。
计算机的指令集(系统),考点: 两者的特点需要区分开。
例 : 若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的时间分别 是取指2ns,分析2ns,执行1ns。那么,流水线周期是多少 ? 100条指令全部执行 完毕需要的时间是多少?
答案: 流水线周期是2ns,100条指令全部执行 完毕需要的时间是203ns或者204ns。
理论公式:5 + (100 - 1) * 2 = 203ns
实际公式:(3 + 100 - 1) * 2 = 204ns
T
P
=
100
203
TP = \frac{\text { 100 }}{\text { 203 }}
TP= 203 100
T
P
max
=
1
2
T P_{\max } = \frac{\text { 1 }}{\text { 2 }}
TPmax= 2 1
根据概念的图片可知,不使用流水线执行时间为
100
×
(
2
+
2
+
1
)
=
500
n
s
100 \times (2 + 2 + 1) = 500ns
100×(2+2+1)=500ns
使用流水线执行时间为203ns。
S
=
500
203
S=\frac{\text { 500 }}{\text { 203 }}
S= 203 500
流 水 线 的 吞 吐 率 ( T h o u g h P u t r a t e , T P ) 是 指 在 单 位 时 间 内 流 水 线 所 完 成 的 任 务 数 量 或 输 出 的 结 果 数 量 。 计 算 流 水 线 吞 吐 率 的 最 基 本 的 公 式 如 下 : 流水线的吞吐率 (Though Put rate, TP) 是指在单位时间内流水线所完成的 任务数量或输出的结果数量。计算流水线吞吐率的最基本的公式如下: 流水线的吞吐率(ThoughPutrate,TP)是指在单位时间内流水线所完成的任务数量或输出的结果数量。计算流水线吞吐率的最基本的公式如下:
T P = 指令条数 流水线执行时间 T P = \frac{\text { 指令条数 }}{\text { 流水线执行时间 }} TP= 流水线执行时间 指令条数
流 水 线 最 大 吞 吐 率 : 流水线最大吞吐率: 流水线最大吞吐率:
T P max = Lim n → ∞ n ( k + n − 1 ) Δ t = 1 Δ t ( Δ t 是 流 水 线 周 期 ) T P_{\max } = \operatorname{Lim}_{n \rightarrow \infty} \frac{n}{(k+n-1) \Delta t} = \frac{1}{\Delta t}(\Delta t是流水线周期) TPmax=Limn→∞(k+n−1)Δtn=Δt1(Δt是流水线周期)
完 成 同 样 一 批 任 务 , 不 使 用 流 水 线 所 用 的 时 间 与 使 用 流 水 线 所 用 的 时 间 之 比 称 为 流 水 线 的 加 速 比 。 计 算 流 水 线 加 速 比 的 基 本 公 式 如 下 : 完成同样一批任务, 不使用流水线所用的时间与使用流水线所用的时 间之比称为流水线的加速比。计算流水线加速比的基本公式如下: 完成同样一批任务,不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。计算流水线加速比的基本公式如下:
S = 不使用流水线执行时间 使用流水线执行时间 S=\frac{\text { 不使用流水线执行时间 }}{\text { 使用流水线执行时间 }} S= 使用流水线执行时间 不使用流水线执行时间
流 水 线 的 效 率 是 指 流 水 线 的 设 备 利 用 率 。 在 时 空 图 上 , 流 水 线 的 效 率 定 义 为 n 个 任 务 占 用 的 时 空 区 与 k 个 流 水 段 总 的 时 空 区 之 比 流水线的效率是指流水线的设备利用率。在时空图上, 流水线的效率定义为 \mathrm{n} 个任务 占用的时空区与 \mathrm{k} 个流水段总的时空区之比 流水线的效率是指流水线的设备利用率。在时空图上,流水线的效率定义为n个任务占用的时空区与k个流水段总的时空区之比
计 算 流 水 线 效 率 的 公 式 为 : 计算流水线效率的公式为: 计算流水线效率的公式为:
E
=
n
个任务占用的时空区
k
个流水段的总的时空区
=
T
0
k
T
k
E=\frac{n \text { 个任务占用的时空区 }}{k \text { 个流水段的总的时空区 }}=\frac{T_{0}}{k T_{k}}
E=k 个流水段的总的时空区 n 个任务占用的时空区 =kTkT0
上图分析,
S
n
S_{n}
Sn表示指令中的每个任务,
S
1
、
S
2
、
S
3
、
S
4
S_{1}、S_{2}、S_{3}、S_{4}
S1、S2、S3、S4表示一个完整的指令,时空区就是方格的面积。
故流水周期为
3
Δ
t
3\Delta t
3Δt
n个任务占用的时空区:
(
Δ
t
+
Δ
t
+
Δ
t
+
3
Δ
t
)
×
4
(\Delta t + \Delta t + \Delta t + 3\Delta t) \times 4
(Δt+Δt+Δt+3Δt)×4(阴影部分)
k个流水段的总的时空区:
15
Δ
×
4
15\Delta \times 4
15Δ×4(总共的时间区)
要如何设计流水线使流水线的效率提高,什么时候流水线的效率最高呢?也就是指令的每个任务执行时间相同时,流水线效率最高。
考点:存储的整体的结构、cache相关的知识、内存需要掌握的一些知识
总结: 内存存储外存的部分内容,cache存储内存的部分内容,CPU只处理cache中的指令,cache的作用是精简内存中重复出现的指令,提高CPU的执行效率,使得计算机的运算速度得到极大的提升;此外,该结构中由上至下,存取速度越来越慢,但容量越来越大。
✓ C a c h e 的 功 能 : 提 高 C P U 数 据 输 入 输 出 的 速 率 , 突 破 冯 − 诺 依 曼 瓶 颈 , 即 C P U 与 存 储 系 统 间 数 据 传 送 带 宽 限 制 。 ✓ 在 计 算 机 的 存 储 系 统 体 系 中 , C a c h e 是 访 问 速 度 最 快 的 层 次 。 ( 而 非 存 取 速 度 ) ✓ 使 用 C a c h e 改 善 系 统 性 能 的 依 据 是 程 序 的 局 部 性 原 理 。 \checkmark Cache的功能: 提高CPU数据输入输出的速率, 突破冯 - 诺依曼瓶颈, 即CPU与存储 系统间数据传送带宽限制。\\ \checkmark 在计算机的存储系统体系中, Cache是访问速度最快的层次。(而非存取速度)\\ \checkmark 使用Cache改善系统性能的依据是程序的局部性原理。 ✓Cache的功能:提高CPU数据输入输出的速率,突破冯−诺依曼瓶颈,即CPU与存储系统间数据传送带宽限制。✓在计算机的存储系统体系中,Cache是访问速度最快的层次。(而非存取速度)✓使用Cache改善系统性能的依据是程序的局部性原理。
如
果
以
h
代
表
对
C
a
c
h
e
的
访
问
命
中
率
,
t
1
表
示
C
a
c
h
e
的
周
期
时
间
,
t
2
表示主存储器周期
时
间
,
以
读
操
作
为
例
,
使
用
“
C
a
c
h
e
+
主
存
储
器
”
的
系
统
的
平
均
周
期
为
t
3
,
则
:
如果以 h 代表对Cache的访问命中率, t_{1} 表示Cache的周期时间, t_{2}^{\text {表示主存储器周期 }} 时间, 以读操作为例, 使用 “Cache+主存储器” 的系统的平均周期为 t_{3} , 则:
如果以h代表对Cache的访问命中率,t1表示Cache的周期时间,t2表示主存储器周期 时间,以读操作为例,使用“Cache+主存储器”的系统的平均周期为t3,则:
t
3
=
h
×
t
1
+
(
1
−
h
)
×
t
2
t_{3}=h \times t_{1}+(1-h) \times t_{2}
t3=h×t1+(1−h)×t2
其
中
,
(
1
−
h
)
又
称
为
失
效
率
(
末
命
中
率
)
。
其中, (1-h) 又称为失效率 (末命中率)。
其中,(1−h)又称为失效率(末命中率)。
注: CPU会在cache中寻找它需要的数据,如果不能找到,CPU就将前往内存中寻找,而cache的访问命中率就是CPU需要的数据在cache中被找到的比例,未能找到的数据CPU将前往内存中进行再次寻找。
cache与内存的地址映像方式有三种,分别是直接映像(cache的区号与内存的区号一一对应)、全相连映像(cache的一个块号可以对应多个内存的块号,内存的一个块号也可以对应cache的多个块号),组相连映像(即两种方式相结合的方法)
全相联映像块冲突最小,欺为组相联映像,直接映像块冲突最大。
注:这三种映射方式都是计算机硬件自动完成的,不是软件
替换算法的目的是使cache获得尽可能高的命中率,有以下四种:随机替换算法、先进先出算法、近期最少使用算法、优化替换算法
注:现代的计算机cache系统是分为了三个级别的,访问时先从第一层开始访问,直至三个级别的cache都被访问完全时才会访问内存
即cpu在给出需要访问的内存地址时,给出的并不是真正的物理地址,而是物理地址的抽象,虚拟存储器是由主存-辅存两级存储器组成
百度百科
✓
时
间
局
部
性
✓
空
间
局
部
性
✓
顺
序
局
部
性
✓
工
作
集
理
论
:
工
作
集
是
进
程
运
行
时
被
频
繁
访
问
的
页
面
集
合
\checkmark 时间局部性 \\ \checkmark 空间局部性 \\ \checkmark 顺序局部性 \\ \checkmark 工作集理论: 工作集是进程运行时被频繁访问的页面集合
✓时间局部性✓空间局部性✓顺序局部性✓工作集理论:工作集是进程运行时被频繁访问的页面集合
1.随机存取存储器:简称RAM,断电后所有数据都将清除,有两类RAM:静态的(SRAM)和动态的(DRAM),SRAM比DRAM速度更快,但价格也更贵。SRAM用来作为高速缓冲存储器(Cache),DRAM用来作为主存及图形系统的帧缓冲区。SRAM将每个位存储在一个双隐态的存储器单元中,DRAM将每个位存储为对一个电容的充电,由于电容非常小,在10~100ms时间内会失去电荷,所以需要周期性地刷新充电以保持信息
2.只读存储器:简称ROM,断电后仍然能够存储信息
1.概念:主存的编址就是把许多块芯片组成相应的存储器
注:上方图解从左至右,第一张图是该存储器为八个地址单元,每个地址空间存储4位信息。第二张图和第三张图都是两个第一张图的合并。
2.编址相关计算
注:H结尾表示16进制,K表示
2
10
2^{10}
210 ,也就是1024;存储单元数量等于大的内存地址减去小的内存地址再加上一。地址单元就是存储单元。
题目分析,给出一段内存地址,我们将其转换为以K为单位的地址单元。然后该内存地址就是一个由28个芯片构成的存储器,每个芯片可以存储16K个地址单元,问每个芯片每个存储单元存储多少位。内存地址的地址单位就是该存储器的地址单位,两者是1:1的。
(1) B.112
(2) A. 4
112
K
×
16
28
×
16
K
×
x
=
1
\frac{112K \times 16}{28 \times 16K \times x} = 1
28×16K×x112K×16=1;
x
=
4
x=4
x=4
掌握:磁盘的基本运作的原理(读取一次数据的过程中,磁盘要做哪些动作,会有消耗哪些方面的时间)
之前的软盘,现在的普通的机械硬盘(硬盘),都属于磁盘,不包含固态硬盘。磁盘的结构是一个环形的盘片,上面涂上特殊的材质用于保存数据,磁盘的结构中盘面保存数据,读取数据要用到专业的设备–磁头,读取时磁头定位移动到相应的磁道(存信息时是存到磁道是上面 )上,这过程消耗的时间称为寻道时间。然后是旋转延迟时间,也称为等待时间(等待读写的扇区转到磁头下方所用的时间)。
存
取
时
间
=
寻
道
时
间
+
等
待
时
间
(
平
均
定
位
时
间
+
旋
转
延
迟
时
间
)
存取时间 = 寻道时间 + 等待时间(平均定位时间 + 旋转延迟时间)
存取时间=寻道时间+等待时间(平均定位时间+旋转延迟时间)
平均定位时间一般是磁盘转一圈的时间。
例题:
解答: 磁盘画图如下:
图1
(1)磁头从R0开始,经过3ms就把数据读取出来,数据存入单缓冲区中,就开始对这一数据的处理(3ms),单缓冲区面临的问题是把R0读取到缓冲区之后,磁头到达了R1的开始位置,注意此时不能把R1中的数据读取到缓冲区中,因为此时缓冲区中还存着R0,R0需要3ms的处理时间,它还没处理完所以新的记录进不来,但是磁盘还会继续往前转动(磁盘在处理时不会停,会一直按匀速转动),等到把R0处理完,磁头已经转动一圈之后,又回到R1的开始位置,这时单缓存区处于空闲状态,然后开始读取R1的信息,所以磁盘会继续转动一直到R2开始位置,又继续了之前处理R0的步骤:读取–处理–转动,后面的数据除了最后一个都是这样的步骤,由此可以总结到规律:把R0处理完,并且把磁头转到下一个要读取的位置,总共要花 转一圈(33ms)加处理一条记录(3ms)的时间,即33+3=36ms,就是说36ms就完成了把一条记录读取、处理,并且把磁头定位到下一个要处理的记录的开始位置。以此类推,从R0到R9都是这么处理的,所以要乘以10,即36*10=360ms,加上R10的读取(3ms)+处理(3ms)(因为后面没有要处理的记录,就无须加上定位时间) 即6ms。所以总共要花的时间为360+6=366ms, 故(1)选C。
(2)若对信息存储进行优化分布,就是我们最希望的状态,即处理完R0(此时磁头在图1 R2开始位置),磁头就能立即到达R1的开始位置。以此类推得到图2 的分布图,这样就没有任何的时间浪费,总共(3+3)*11=66ms,故选B。
图2
考察总线最基础的分类和概念。
1.概念:总线是连接计算机有关部件的一组信号线,是计算机中用来传送信息代码的公共通道。
根据总线所处的位置不同,总线通常被分成三种类型
2.内部总线:微机内部的,各个外围芯片与处理器之间的总线,属于芯片级别
3.系统总线:系统总线即为各个插线板和系统板之间的总线;包括(1)数据总线:用来阐述数据的,如32位,64位等一次性能够传输的位(2)地址总线:假设该计算机的地址总线为32位,那就代表它的地址空间为 2 32 2^{32} 232个字节(3)控制总线:发送相应的控制信号的总线
4.外部总线:即微机和外部设备的总线
注:总线上的多个部件之间只能分时向总线发送数据,但可以同时从总线接收数据。
串联和并联的可靠性的计算以及串联和并联混合的情况。
1.串联系统的结构: 只要一个子系统失效,则整个系统都将失效
2.串联系统可靠性的计算:即各个串联子系统可靠性相乘,如上图,其中R为可靠性,此外,1-可靠性即为失效率,而总的失效率即为串联各个部件的失效率作和(近似计算)
1.并联系统的结构 注:少数子系统的失效将不会影响整个系统。
2.并联系统可靠性的计算:通过计算失效率来求得可靠性,即各个子系统的失效率相乘,再由1减去它,即可得到系统可靠性。上图所示,
μ
\mu
μ表示可靠率,但是我们一般不使用这种方式求,而是使用1减可靠率即可。
1.该模型软硬界都有应用。面向一些高可靠性系统的要求时,需要提高系统的可靠性,我们就可以使用N模冗余系统的方式。
2.结构
图片解释:数据输入m个子系统中,它们各自得出自己的结果,然后汇总到表决器,表决器将遵循少数服从多数的原则,输出大多数子系统得到的那个答案然后进行输出。
注 : 近 年 来 该 模 型 不 再 考 察 。 \color{red}{注:近年来该模型不再考察。} 注:近年来该模型不再考察。
图片解释:求该混合系统的可靠度。
主要是了解校验码的作用,各自的运算特点以及编码解码的过程又是怎么样的。
CRC与海明校验码的基本原理和操作流程是要求掌握的。
1.码距的概念:指整个编码系统中任意两个码字的最小距离。
如A变化X个位得到B,则X就为码距,如:若使用2位长度的二进制编码,若以A=11,B=00为例,A,B之间的最小码距为2
2.码距的作用:增大码距能够起到检错的作用,因为数据在传输的过程中如果链路出现了
问题,那么将会使得接收到的二进制数发生变化,若码距过小,则很可能造成信息的混淆,增大码距就使得被改变的二进制数混淆信息的概率极大的降低;若码距再进行增大,则能够起到纠错的作用,因为数据链路出错的概率比较低,只能造成传输中极少二进制数的改变,我们可以根据该传输失真的二进制数中大部分二进制数的构成来进行推断,推断出结果就达到了纠错的目的。
例:
若用
1
位长度的二进制编码。若
A
=
1
,
B
=
0
。这样
A
,
B
之间的最小码距为
1
。
若用
2
位长度的二进制编码, 若以
A
=
11
,
B
=
00
为例,
A
、
B
之间的最小码距为
2
。
若用
3
位长度的二进制编码, 可选用
111
,
000
作为合法编码。
A
,
B
之间的最小码距为
3
。
什么是模2除法, 它和普通的除法有何区别?
模2除法是指在做除法运算的过程中不计其进位的除法。也就是进行异或操作。
例如, 10111对110进行模2除法为:
这是一种可以检错但不能纠错的编码。
CRC的原理:在原始报文后面添加校验信息,然后让其与循环校验码的生成多项式进行模2运算,余数添加到原始报文后面,这时的原始报文就是CRC。然后拿循环校验码的生成多项式与CRC进行模2运算余数为零,说明传输过程不会出现错误。若不为零则说明传输过程出现了错误。
注:生成多项式是一个二进制数,如"X4+X3+X+1",这个生成多项式实际上就是二进制数11011;在与原始报文相除时,需在原码后方添加一些0,添加的0的个数等于生成多项式的二进制位数减去1,增加的0即为校验信息。
例
:
原
始
报
文
为
“
11001010101
”
,
其
生
成
多
项
式
为
:
"
x
4
+
x
3
+
x
+
1
"
。
对
其
进
行
C
R
C
编
码
后
的
结
果
为
?
例: 原始报文为 “ 11001010101 ”, 其生成 多项式为: " x^{4}+x^{3}+x+1 "。对其进行CRC编 码后的结果为?
例:原始报文为“11001010101”,其生成多项式为:"x4+x3+x+1"。对其进行CRC编码后的结果为? 110010101010011
奇偶校验码参考这篇文章(传送门)
定义:奇偶码(Parity Check)跟前面提到过的CRC校验码一样,奇偶校验码也是一种校验码,它用来检测数据传输过程中是否发生错误,是众多校验码中最为简单的一种。
顾名思义,它有两种验证方法:奇校验和偶校验。
跟CRC类似,也是在原始码流后面,加上校验位。不同的是,它的校验位只有一位,要么是0,要么是1。并且它的校验码还可以放在码流的前面。
例如下图有5组原始码,校验位的计算方法如下。红色代表校验位。补充0或者1将校验码满足奇数个1或者偶数个1。
例如:我们存在一套原始码为:00,01,10,11,在这套编码中至少有一个数字不相同,我们称这套编码的码距为1。
如果采用奇偶校验的方法,我们至多可以将一组编码的码距提升1,如上的例子就可以将码距提升为2。
以偶验证为例:上述编码可以写成:000,011,101,110,这样做的主要目的是将原来可以表示十进制0~ 3的数,扩大到0~ 7。而在0~ 7这8个数中只有4个数是正确的,那么就是说只要出现了另外的4个数就说明数据出错了。
但是奇偶校验只能检测出数据是否出错,而不能检测出哪一位出错,例如收到数据111,我们无法判断究竟是由011,101,110,这三者中的哪一个变来的,为了解决这一问题,就提出海明校验码。
定义:海明码(Hamming Code)是利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的确定位置插入k个校验位,通过扩大码距来实现检错和纠错。对于数据位n的数据,加入k位的校验码,它应满足:
2
k
−
1
≥
n
+
k
2^{k} - 1 \ge n + k
2k−1≥n+k
这个式子的意思是,可以用来检验错误的数据个数
(
2
k
−
1
)
(2^{k} - 1)
(2k−1)要大于或者等于原数据位数(n)和校验位数(k)的和。显然在
2
k
2^{k}
2k中我们要留出一个数表示数据正确,所以我们用
2
k
−
1
2^{k} - 1
2k−1来代表出错的位数。
理解了公式之后我们通过一个例子来学习一下海明码到底怎么用。
例:求信息1011的海明码。
(1)
2
r
≥
4
+
r
+
1
\color{red}{2^{r} \ge 4 + r + 1}
2r≥4+r+1,确定校验码为3位:
2
3
≥
4
+
3
+
1
2^{3} \ge 4 + 3 + 1
23≥4+3+1。分别放在
2
0
=
1
、
2
1
=
2
、
2
2
=
4
位
2^{0}=1、2^{1} = 2、2^{2}=4位
20=1、21=2、22=4位。
(2)列出校验位公式。
7
=
2
2
+
2
1
+
2
0
,
6
=
2
2
+
2
1
,
5
=
2
2
+
2
0
,
3
=
2
1
+
2
0
r
2
=
I
4
⊕
I
3
⊕
I
2
;
(
将
包
含
2
2
的
数
写
上
)
r
1
=
I
4
⊕
I
3
⊕
I
1
;
(
将
包
含
2
1
的
数
写
上
)
r
0
=
I
4
⊕
I
2
⊕
I
1
;
(
将
包
含
2
0
的
数
写
上
)
(3)根据公式得
r
2
=
0
,
r
1
=
0
,
r
0
=
1
r_{2}=0, r_{1}=0, r_{0}=1
r2=0,r1=0,r0=1。
(4)将数据加入表格, 如表所示。
海明码即为1010101
有了海明码之后我们如何判断错误并纠正呢?假如我们收到这样的信息:1011101
则:
r
2
⊕
I
4
⊕
I
3
⊕
I
2
=
1
⊕
1
⊕
0
⊕
1
=
1
r
1
⊕
I
4
⊕
I
3
⊕
I
1
=
0
⊕
1
⊕
0
⊕
1
=
0
r
0
⊕
I
4
⊕
I
2
⊕
I
1
=
1
⊕
1
⊕
1
⊕
1
=
0
\mathrm{r}_{2} \oplus \mathrm{I}_{4} \oplus \mathrm{I}_{3} \oplus \mathrm{I}_{2}=1 \oplus 1 \oplus 0 \oplus 1=1 \\ \mathrm{r}_{1} \oplus \mathrm{I}_{4} \oplus \mathrm{I}_{3} \oplus \mathrm{I}_{1}=0 \oplus 1 \oplus 0 \oplus 1=0 \\ \mathrm{r}_{0} \oplus \mathrm{I}_{4} \oplus \mathrm{I}_{2} \oplus \mathrm{I}_{1}=1 \oplus 1 \oplus 1 \oplus 1=0
r2⊕I4⊕I3⊕I2=1⊕1⊕0⊕1=1r1⊕I4⊕I3⊕I1=0⊕1⊕0⊕1=0r0⊕I4⊕I2⊕I1=1⊕1⊕1⊕1=0
综上所述,二进制100的十进制就是4,故说明第4位错误。那么我们将第4位取反即可得到正确的数据。
注 : 其 实 就 是 拿 算 好 的 海 明 码 中 的 校 验 码 与 收 到 信 息 的 校 验 码 的 位 数 做 异 或 操 作 。 \color{red}{注:其实就是拿算好的海明码中的校验码与收到信息的校验码的位数做异或操作。} 注:其实就是拿算好的海明码中的校验码与收到信息的校验码的位数做异或操作。
可用性是指在给定的时间点上,一个系统能够正确运作的效率。
可靠性是指系统在给定的时间间隔内,给定条件下无失效运作的概率。
MTBF为平均失效间隔时间,则可用性用
M
T
B
F
(
1
+
M
T
B
F
)
MTBF(1 + MTBF)
MTBF(1+MTBF)表示。
MTTF为平均无故障时间,则可靠性用
M
T
T
F
(
1
+
M
T
T
F
)
MTTF(1 + MTTF)
MTTF(1+MTTF)表示。
注:在《软件设计师(第5版)》中,平均无故障时间定义为MTBF。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。