当前位置:首页 >> 其它课程 >> Lect

Lect


Chapter 2 数据表示及逻辑基础

CS, ZJU 8/15/2013

Overview
?
? ? ? ?

数制 数、码 编码与文本 多媒体数据 逻辑基础

概述
?

计算就需要数
? ? ?

计算机中

的数的表示是一个基础性的问题 表示各种现实世界对象的?数据?, 数的表示也延伸到了数据的表示 计算(数据操作) 表示实体对象(范围) 基本形态是二进制

?

不同应用需要不同的数据类型,数据类型约定了
? ?

?

统一的数据表示方法
?

2.2
?

数制

Number System
? ?

?计数(或记数)体制? 多位数中每一位的构成方法以及实现从低位到 高位的进位规则,也叫做进制

? ?

数学家们研究数制的规则和规律 计算机科学中
?

将数制规则和规律通过电路实现

?

常用进制
?

二、十、八、十六

二进制起源于中国——八卦

数制 常用进制
?

R进制
? ?

?

R个数码,数码从0到R-1 数:每位数码和该位的权系数的乘积 权系数也叫做幂次或叫做权重(Power Weight) 计数规则 0~9,逢十进一

?

逢R进1
?

?

十进制 Decimal System
?

二进制
?

Binary System
?
?

?

位(比特,bit)是计算机处理的最小单位 0和1两个数码,被组合成各种序列以适应计 算机的运算和处理的数据类型 选择二进制的一个最简单也是最实际的理由 是它容易被物理器件实现 101011012= 1×27+0×26+1×25+0×24+1×23+1×22+ 0×21+1×20 = 128+32+8+4+1 = 173

?

多项式表示一个二进制数:
?

八进制 and 十六进制
?

Octal System
? ?

八个数码:0、1、2、3、4、5、6、7 8 = 23 一位八进制对应于三位二进制

?

Hexadecimal System
? ? ?

16个数码:0?9 ,A、B、C、D、E、F 字节(Byte,8个二进制位)= 两位十六进制 16 = 24:4位二进制和1位十六进制对应

二进制的基本运算
?

二进制加法
? ? ? ?

0+0=0 0+1=1 1+0=1 1+1=0
0?0=0 0?1=0 1?0=0 1?1=1

Here Carry 1

?

二进制乘法
? ? ? ?

二进制和十进制转换
?

1.二进制转换为十进制
?
?

被转换的二进制数按幂次展开,然后相加
1101.01 2 = 1?23+1?22+0?21+1?20+0?2-1+1?2-2

= 8 + 4 + 0 + 1 + 0 + 0.25
= 13.25 10
?

2. 十进制转换为二进制
? ?

整数部分(除2取余,低位先产生) 小数部分(乘2取整,高位先产生)

十进制整数转换为二进制数
173 10 = 10101101 2

十进制小数转换为二进制


2

二进制与八进制转换
?
?

从小数点出发,3位二进制对应1位八进制
例:10110101.00101

?

257.0648 = 010 101 111 . 000 110 1002

二进制、十六进数转换
? ?

从小数点出发,4位二进制对应1位十六进制 例:转换 10110101.00101 成十六进制

?

10110101.001012 = B5.2816
See Table 2-1

?

常用数制转换方法
小结 ? 二进制(八进制、十六进制)?十进制 :求幂相加法 ? 十进制?二进制(八进制、十六进制)
整数部分: 除2(8、16)取余; 小数部分: 乘2(8、16)取整

? ? ?

八进制?二进制: 1位八进制对应3位二进制

十六进制?二进制: 1位十六进制对应4位二进制 十六进制 ? 二进制 ? 八进制

2.4 计算机中的数
? ?

整数的表示 正负:符号位,0表示正数,1表示负数
? ? ?

+1011 00…01011 (前面加‘0’调整位数) -1011 10…01011(不会混淆时,可以不加‘0’ ) 真值 机器数(原码) 原码(Original Code) 反码(One’s Complement) 补码(Two’s Complement) 为了数据表示的唯一性和运算方便,采用补码表示

?

三种表示方法:
? ? ? ?

原码
?

原码即上述的机器数——
?

n位二进制数,最高位被设置为符号位,其后的 n-1位表示真值。(需要时加?0?调整位数)
简单、直观 ?0?的表示不唯一:00 (正0?) 10(负0?) 尾数相乘 符号位简单相加法就可以得到乘积的符号

?

原码的特点
? ?

?

用原码可以比较方便地进行乘法运算:
? ?

反码
?

?

?

反码的定义是:一个正数的反码就是它的机器数, 负数的反码其最高位(符号位)为1,其余各位按 位求反 ? 例如,+1010010 反码为 01010010 - 1010010 反码为 1 0101101 负数的反码和原数相加:结果为所有位都是1 ? 对1互补 ? 专业术语:One’s Complement 反码本身不用,只是为了定义补码

补码
?

?

? ?

补码的定义是:正数的补码等于它的原码,负数 的补码等于它的反码加1(最低位加1,进位不改 变符号位) ? 例如,+1010010 的补码为 01010010 - 1010010 的补码为 10101110 补码一个有意思的特性是:补码的补码将还原为 原码 补码用于减法运算会很方便。 ?0?就是 00……0,而10……0表示负值最大的数

负数在计算机内表示
补码表示法(16位字长机器) 0000000000000000 = 0 0000000000000001 = 1 (32767+1 = -32768!) …… 0111111111111111 = 32767(215-1) 1000000000000000 = -32768(-215) 1000000000000001 = -32767 …… 0000000000000001 ( 1) 1111111111111111 = -1 +)1111 1111 11111111(-1) 0000000000000000 = 0 0000000000000000 ( 0)
?

实数的浮点数表示
? ?

实数的表示——两种格式:定点数和浮点数 计算机中保存数
?
? ? ? ?

二进制 固定长度 定点数:16位或32位 小数点固定在某一个位置 定点纯小数、定点纯整数

?

浮点数——小数点位置是浮动的

浮点数表示实数
?

浮点表示法
123. 4567 = 0.1234567 ? 103 0. 001234567 = 0.1234567 ? 10-2

小数点后第一位不能是0: 规范化表示,保证唯一性

32位

23位二进制数大约有 7位十进制有效数

浮点数表示实数
?

浮点数系 x = 0.t1t2…tn ? 10±e

? 尾数部分的位数n(即有效位数)决定了精度 ? 阶码部分e决定了取值范围:
如:Xmax = ±0.9999999 ? 10+38 , Xmin = ±0.1000000 ? 10-38

? 浮点数表示实数只是近似表示—计算会产生误差并传播 ? 一方面可以增加字长提高精度,另一方面要研究误差传播规律

用浮点数表示实数
?

浮点数是有限而稀疏的:
0
(

x

) (

x1

)

……

xmax

浮点数:x=1234567.0 = 0.1234567 ? 107 , 比它大的下一个浮点数是: x1=0.1234568 ? 107 即x1= 12345678.0,所以 区间(x-0.5, x+0.5]中的所有实数用x近似表示, 区间(x1-0.5, x1+0.5)中的所有实数用x1近似表示。

? 超过xmax太多的实数将会溢出。

2.5 编码和文本
? ? ?

?

数还有另外一种功用:码(Code) 编码的目的是为了便于标记特定的对象 设计编码时需要按照一定的规则—— ?码制(Code System)? 重要概念
?

?

位模式 常用编码:ASCII、汉字编码、多媒体数据

位模式
? ?

?

用于计算的数:用二进制位的多位组合表示定点 数、浮点数 更多的数据类型,就需要有更多的二进制位的组 合规则——位模式 bit pattern
?
? ?

用0和1组成的二进制位序列及其规则
是一种数据表示方法 要由计算机程序去理解它们

?

位模式要求:
?

用户、程序设计者按某种规则形成、存储和处理数据

?

位模式的二进制位序列长度取决于被编码对象的数 量

文本和文档
?

文本(Text)——编码来表示
?

?

文本中的每一个符号包括字母、标点,都以一个唯 一的二进制位序列表示 在计算机中,文本就是位模式的二进制数据长串
American Standard Code for Information Interchange 基于English

?

基础的文本编码就是ASCII
?

?

?

文本编码是计算机进行数据交换的基础

ASCII码
?

ANSI制定,后为ISO 646
?

适用于英文,两种形式:7位码和8位码 单字节字符编码方案,基本的文本数据

?

7位二进制ASCII码
?

?

8位码是扩展ASCII码,See Appendix A

Unicode编码
?

通用多文种字符集
?

?

表示几乎世界上所有书写语言的字符编码标 准——统一码、单一码、万国码 可支持超过百万个字符的编码
国际标准ISO 10646 ISO采用的是32位模式 用于世界范围各种语言文字的文本形式的字符 集,也收集了汉字

?

Unicode编码
? ?

?

汉字编码
? ?

汉字编码的目的是为了计算机能够处理、显示、 打印、交换汉字字符 国家汉字编码标准GB2312-1980
? ?

简化汉字6763个,7445个字符 港澳台地区使用繁体汉字BIG5码
GB2312-1980的扩展 收录了2.1万多个汉字 GBK支持ISO 10646中的全部中、日、韩汉字

?

1995年的GBK扩展汉字编码标准
?

?
?

?

2001年GB18030——GBK的升级
?

160万码位,目前汉字约为2.6万个

2.6 多媒体数据
?

多媒体
? ?

文本,图形、音频、视频等 多种数据表现形式,并使之在逻辑上建立联系 计算机和网络都支持多媒体数据处理 相比文本……

?

今天
? ?

图形和图像
?

?

图形(Graphics)——几何线条、几何符 号等形式表示物体的轮廓 在数据表达上
?
?

?

图形和图像也被认为是同类 例如,Windows的?画笔?程序,既可以画几 何图形,也可以对图形着色使之成为图像 (Picture,Image) 两种技术:位图和矢量图

位图技术
?

微软公司提出的
? ?

?

?

又称光栅图(Raster Graphics) 使用像素(Pixel)阵列,每一个像素是一个点 (Dot),点数据的大小取决于分辨率 位模式有1、4、8、16、24及32位等

?
?

灰度图像——每一个像素需要更多的二进制位 彩色图形、图像——RGB

矢量图技术
?

任何图像、图形
? ? ?

可以分解为曲线和直线的组合 直线和曲线度都可以使用数学公式表示 直线、曲线公式的组合作为图形数据存储起来, 画图的公式被重新执行 并根据给定的大小画出(重现)图形图像 矢量图看上去更加平滑,不会产生纹波误差

?

需要显示或者打印图形图像数据时
? ? ?

音频
?

音频(Audio)包含了
? ?

声音(Voice)和 音乐(Music)

?

计算机音频就是研究在计算机中表示和处 理声音与音乐数据,目前没有?数字音频 标准?

视频
?

视频(Video)是图像的动态过程
?

? ?

一幅幅(Frame)图像数据连续播放,就成为 了动态图像 也是一种位模式数据 压缩处理后存储,播放时需要解压
音频/视频的MPEG-1到MPEG-4 MPEG是ISO指定的标准研究组织,它的最新工 作是MPEG-21

?

MPEG制定的一系列视频编码和压缩标准
?

?

2.7 逻辑运算和门电路
?

用数学的方法研究关于推理、证明等问题的学科
?
?

数理逻辑,也叫做符号逻辑 英国数学家布尔——建立了布尔代数(逻辑代数)——计 算机重要的科学基础
?因?是条件 条件之间的关系用逻辑连接词进行组合 根据不同的条件得到?结果?

?

逻辑关系可以被解释为因果关系
? ? ?

?
?

逻辑运算对应的实现电路,叫做门电路 基本逻辑(运算)关系
?

与(AND),或(OR),非(NOT)

逻辑关系 “与”
?

?

只有决定结果的条件 全部满足,结果才成 立,这种逻辑关系叫 做逻辑与 表示
? ? ?

?

把变量和逻辑关系的 取值列表,就得出了 真值表(True Table)

A AND B A ●B AB

A 0 0 1 1

B 0 1 0 1

AB 0 0 0 1

逻辑”或”
?

?

决定结果的条件中只 要任何一个满足,结 果就成立。这种逻辑 关系叫做逻辑或 表示
? ?

A

B

A+B

0 0 1 1

0 1 0 1

0 1 1 1

A OR B A+B

?

表2-3逻辑或真值表

逻辑”非”
?

?

。最简单的描述 就是结果对条件 的?否定? 表示
?

A 1
0

A
0 1

Not A: A

?

逻辑非的真值表

逻辑代数
? ?

通过代数学的方法研究逻辑关系,通过变换、 简化或组合等方法进行逻辑设计 逻辑表达式
? ?

?

逻辑函数
?

A + A· B A + AB

? ? ?

AB=A+B 反演定律 A+BC=(A+B)(A+C) 分配律 A+AB=A+B 吸收律

F = f(A,B,C,…)

门电路
?

?

实现基本逻辑关系的 电路是逻辑电路中的 单元电路——Gate 基本的门电路有:
? ? ? ?

与门 或门 非门 异或门

?

门电路的基本特点

基本门电路
A B F A B F F

A

(a)与门 F=AB (b)或门 F = A+B

(c)非门 F = A

?

用基本门电路可以组合成多种复合门电路

与非门
A B 图 A 2.9 B 与 非 门 F F

0 0 1 1

0 1 0 1

1 1 1 0

或非门
A B F 或 非F 门

A图 2.10 B
0 0 1 1 0 1 0 1

1 0 0 0

异或门
A F B

F 图 A ? B ? AB ? AB ? 2.10 异 或 门
A F B

2.8 逻辑设计基础
?

逻辑设计——
? ?

?

根据问题,由真值表得到逻辑表达式 根据逻辑定律进行必要的化简、变换,设计出 最优的逻辑表达式 用逻辑电路实现 与设计相反 由电路得到功能

?

逻辑分析
? ?

设计加法器
?

用逻辑电路实现加 法运算的电路叫做 加法器(Adder)
?

?

设A、B分别为一位 二进制数 S为A与B之和,C为 A加B产生的进位

A 0 0 1 1

B 0 1 0 1

S 0 1 1 0

C 0 0 0 1

S ? AB ? AB
A B

C ? AB
S

?
?

加法的真值表 表达式

C

半加器/全加器
?

半加器
?

只考虑加数和被加数之间的加法运算,并产生了向高 位的进位——没有考虑可能来自低位的进位,所以它 并没有完成一位二进制的全部运算,半加器的意思是 它只完成了一半的加法运算

?

全加器
?

不但要考虑本位产生的进位,还要考虑来自低 位的进位

全 加 器

输入 Ci-1 Ai Bi Si

输出 Ci

0
0

0
0

0
1

0
1

0
0

0
0

1
1

0
1

1
0

0
1

1
1 1 1

0
0 1 1

0
1 0 1

1
0 0 1

0
1 1 1

S i ? A i B i C i ?1 ? A i B i C i ?1 ? A i B i C i ?1 ? A i B i C i ?1

全加器电路
S i ? Ai ? Bi ? Ci ?1
Ci ? Ai Bi ? Bi Ci ?1 ? Ai Ci ?1
Ai Bi Si Ci-1

Ci

S3 C3

S2

S1

S0

A3

B3

A2 B2

A1

B1

A0

B0

四位加法器电路逻辑示意图

存储单元电路

图2-14 门电路组成存储单元原理示意图

集成电路 IC
?

IC按电路内门电路的数目来划分其规模
?

?

?

?

小规模IC(SSIC,Small Scale IC)大约有10个 门电路。 超过100个门电路——中规模集成电路(MSIC, Middle Scale IC) 大规模IC(LSIC,Large Scale IC)集成的门电 路要超过1000个以上 超大规模IC(VLSIC,Very Large Scale IC)

?

超大规模集成电路的集成度已经超过了千万

思考题
?

数据表示也是一个社会问题
?

?

使用编码对各种对象进行标记,但必定会产生 某些有意无意的歪曲。 例如,对某一社会问题进行问卷调查,而问卷 中的答案使用等级,给每个等级赋值进行统计 分析,你认为这种?量化?是合适的吗?为什 么?

?
?

下音频数据格式有多少种,各有什么特点 数据压缩使用的技术


更多相关文档:

英美拼写区别

7) 英国英语中以 xion 结尾的词, 美国英语常以 tion 结尾, 例如: complexion/complection( 面色), connexion/connection ( 连接), flexion/flection(弯曲)等。...

c2i

B1.2 famille : Emplacement des fichiers Quand on sé lectionne un fichier et que l'on appuie sur la touche "SUPPR" ou "DEL", oùva le fichier ...

美式英式拼写区别

7) 英国英语中以 xion 结尾的词 , 美国英语常以 tion 结尾 , 例如 : complexion/complection( 面色), connexion/connection ( 连接), flexion/flection(弯曲)...

Worter

(语气词) 超级,棒极了 回头见 不久 会话,谈话 欢迎,问候 告别 学校 音乐 公园 花园 3 课文 机器 剧院,戏院 网球 国际的 足球 Lection 1 我们的 校园,学校...

系列讲座

“劳动”的历史 Lect.1 Words: The history of laodong (labor) 2013 年 11 月 8 日 15:00-17:00 北京大学英杰交流中心月光厅 主持、致辞 中文系系主任 ...

浅析性别方言

浅析性别方言产生的原因摘要:性别方言(sex dialect),又称性别语言差异( genderlect difference), 是指 男女两性由于在生理上的差别以及在社会化过程中差异产生的对语...

常见英式拼写与美式拼写的区别

7) 英国英语中以 xion 结尾的词 , 美国英语常以 tion 结尾 , 例如 : complexion/complection( 面色 ), connexion/connection ( 连接 ), flexion/flection(...

CAD中快速选择命令QSELECT的运用

CAD 中快速选择命令 QSELECT 的运用 2012-03-23 童凡凡整理 此命令可以帮助我们快速选择整个图形中或者是目标图形中, 颜色为 xxx 或者是图层为 xxx 的全部图元...
更多相关标签:
lecture | elect | select | lect词根 | neg | 乐村淘 | 有道词典 | lect2 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com