图灵机模型及数据编码.ppt_第1页
图灵机模型及数据编码.ppt_第2页
图灵机模型及数据编码.ppt_第3页
图灵机模型及数据编码.ppt_第4页
图灵机模型及数据编码.ppt_第5页
已阅读5页,还剩51页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第1章 图灵机模型及数据编码,图灵机模型理论是计算学科最核心的理论之一 图灵机模型为计算机设计指明了方向 图灵机模型是算法分析和程序语言设计的基础理论。,本章主要内容,1.1 图灵机 1.2 位的存储 1.3 存储器 1.4 数据在计算机中的表示 1.5 数据压缩 1.6 数据传输误码及对策,图灵机的直观描述,3个部件:有穷控制器、无穷带和读写头 3个动作:改写当前格、左移或右移一格,图灵机的形式化描述,图灵机是一个五元组(K,s,H),其中: K 是有穷个状态的集合; 是字母表,即符号的集合; s K是初始状态; HK 是停机状态的集合,当控制器内部状态为停机状态时图灵机结束计算; 是转移函数,即控制器的规则集合。,计算“x+1”的图灵机,目标:利用二进制来设计一个专门计算“x+1”的图灵机,要求计算完成时,读写头要回归原位 状态集合K:start,add,carry,noncarry,overflow,return,halt; 字母表:0,1,*; 初始状态s:start; 停机状态集合H:halt;,计算“x+1”的图灵机,规则集合:,“51”的计算过程(1),“51”的计算过程(2),“51”的计算过程(3),“51”的计算过程(4),通用图灵机(1),编码方案:,通用图灵机(2),通用图灵机蕴含的计算思想,“x+1”图灵机功能是固定的,相当于一个程序 通用的图灵机功能根据输入编码的不同而变化 程序也是数据 存储程序和程序控制 通用图灵机模型是计算机的计算能力的极限 计算机系统应该有存储器(相当于存储带)、中央处理器(控制器及其状态),并且其字母表可以仅有0和1两个符号;为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户,计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。,1.2 位的存储,如果用0-1作为编码的基本元素的话,那么存储的最小单位为1位(bit),要么是0要么是1。可见只要存储装置有两种不同的稳定状态就能可以表示和存储这两个元素,其中一个状态表示1,则另一种状态就表示0,逻辑运算,门,可以设计出进行逻辑运算的装置,比如用继电器或者齿轮等,把这种能完成逻辑运算的装置称为门(Gate)。现代电子计算机中的门是用电子线路实现的,其中1和0分别用电平的高和低来表示。,触发器,其他存储技术,磁芯 电容 磁介质 有机玻璃或聚酯树酯等材料制作的介质,1.3 存储器,1 Byte 8 Bit 1 KB(kilobyte) 1024 Byte 1 MB(megabyte) 1024 KB 1 GB(gigabyte) 1024 MB 1 TB(terabyte) 1024 GB,存储器,主存储器 地址 辅助存储器 软盘、硬盘和光盘等,1.4 数据在计算机中的表示,二进制 数值的表示 字符的表示 图形和图象的表示 音频数据的表示,数制,进位计数的方法即数制 在采用进位计数的数字系统中,如果只用r个数码,则称其为基r数制(Radix-r Number System)或 r 进制,r 便称为该数制的“基数”(Radix) 二进制:B(Binary),如 (11101)B; 八进制:O(Octal),如 (35)O; 十进制:D(Decimal),如 (29)D; 十六进制:H(Hexadecimal),如 (1D)H;,二进制与其他数制的转换(1),二进制与十进制的转换 十进制转换成二进制:将整数部分和小数部分分别转换,然后再拼接起来 整数部分,采用除2取余法; 小数部分,采用乘2取整法。 二进制转换为十进制:直接按权展开即可 小数点后的权分别为2的-1、-2、-3、次幂,二进制与其他数制的转换(2),十进制转换成二进制:,二进制与其他数制的转换(3),二进制转换为十进制:,二进制与其他数制的转换(4),二进制与十六进制的转换 16124,4位二进制数刚好可以表示0F这16个数码,也就是说二进制的4位数正好可以用1位十六进制数表示 将二进制数 10110101111011.011101 转换为十六进制: (0010 1101 0111 1011.0111 0100)B(2 D 7 B.7 4)H 将十六进制数 2C1D.A1 转换为二进制: (2 C 1 D. A 1)H(0010 1100 0001 1101.1010 0001)B 二进制与八进制的转换类似,数值的表示(1),机器数 把在机器内存放的正负号数码化的数称为机器数,把机器外部由正负表示的数称为真值数 若一个数占8位,真值数(0101100)B的机器数为10101100,数值的表示(2),整数和实数 整数,数值的表示(3),整数和实数 实数,数值的表示(4),若要考虑符号位的处理,则运算变得复杂:,为了解决此类问题,在机器数中,负数有三种表示法:原码、反码和补码。,数值的表示(5),原码: 数符位以0表示正1表示负,数值部分就是绝对值的二进制表示,不便于加减运算 反码: 对于正数与原码相同;对于负数,数符位为1,其数值部分为绝对值取反 补码: 对于正数与原码相同;对于负数,数符位为1,其数值部分为绝对值取反最右加1,即为反码加1 可方便地实现正负数的加法运算,符号位如同数值一样参加运算,也允许产生最高位的进位,字符的表示(1),西文字符 最常用的是ASCII字符编码,即American Standard Code for Information Interchange (美国信息交换标准代码),用7位二进制编码,它可以表示27 即128个字符 EBCDIC码,即Extended Binary Coded Decimal Interchange Code(扩展的二-十进制交换码),主要用在大型机器中,采用8位二进制编码,有256个编码状态,但只选用其中一部分 存放和使用数据的软件会以其他方式保存有关类型的信息,指明这个数据是何类型,不致引起混淆,字符的表示(2),汉字编码 用户用输入码输入汉字,输入码比较容易学习和记忆;系统由输入码找到相应的内码,内码是计算机内部对汉字的表示;要在显示器上显示或在打印机上打印出用户所输入的汉字,需要汉字的字形码,系统由内码找到相应的字形码,字符的表示(3),汉字编码 汉字国标码 全称是GB231280信息交换用汉字编码字符集基本集,1980年发布,是中文信息处理的国家标准,也称汉字交换码,简称GB码。根据统计,把最常用的6763个汉字分成两级:一级汉字有3755个,按汉语拼音排列;二级汉字有3008个,按偏旁部首排列。为了编码,将汉字分成若干个区,每个区中94个汉字。由区号和位号(区中的位置)构成了区位码。例如,“中”位于第54区48位,区位码为5448。区号和位号各加32就构成了国标码,这是为了与ASCII码兼容,每个字节值大于32(032为非图形字符码值)。所以,“中”的国标码为8650。,字符的表示(4),汉字编码 汉字机内码 一个国标码占两个字节,每个字节最高位仍为“0”;英文字符的机内码是7位ASCII码,最高位也是“0”。因为西文字符和汉字都是字符,为了在计算机内部能够区分是汉字编码还是ASCII码,将国标码的每个字节的最高位由“0”变为“1”,变换后的国标码称为汉字机内码。由此可知汉字机内码的每个字节都大于128,而每个西文字符的ASCII码值均小于128。,字符的表示(5),汉字编码 汉字的输入编码 目的:进行汉字的输入 要求:编码要尽可能的短,重码要尽量少,容易学容易上手 最常用的输入码:五笔字型、智能拼音等。,字符的表示(6),汉字编码 汉字字形码 点阵方式 矢量方式,图形和图象的表示(1),基本概念 图形 一般是指通过绘图软件绘制的由直线、圆、圆弧、任意曲线等组成的画面,即图形是由计算机产生的,且以矢量形式存储; 图像 是由扫描仪、数字照相机、摄像机等输入的画面,即图像是由真实的场景或现实存在的图片输入计算机产生的,图像以位图形式存储。,图形和图象的表示(2),基本概念 动画 每一副画面通过一些工具软件对图像素材进行编辑制作而成;动画是用人工合成的方法对真实世界的一种模拟 视频 对视频信号源(如电视机、摄像机等)经过采样和数字化后保存;而视频影像则是对真实世界的记录,图形和图象的表示(3),一副图像可认为是由若干行和若干列的像素(Pixels)点组成的阵列,每个像素点用若干个二进制进行编码,表示图像的颜色,这就是图像的数字化。 图像分辨率 颜色深度 即每一个像素点表示颜色的二进制位数,音频数据的表示,采样频率 采样频率即每秒钟的采样次数。 采样点精度 即存放每一个采样点振幅值的二进制位数 声道数,1.5 数据压缩,在保留原数据表达的信息不变或者在稍有变动但不致于影响使用的同时尽量减少表达这些信息的数据量就是数据压缩 数据压缩有利于节省存储空间,而且可有效提高数据传输效率 无损压缩(熵编码) 有损压缩,无损压缩(1),行程编码法(Run-length Encoding,RLE),0 0 0 0 0 0 0 0 1 1 1 1 1 1 7 7 77 7 1 1 11 1 1 (8个0) (6个1) (30个7) (50个1) 0 0 00 0 8 8 8 8 (30个0) (4个8) 可以编码为: 8A0A6A1A30A7A50A1A30A0A4A8,无损压缩(2),霍夫曼编码 (1)根据符号出现的概率大小按由小到大的次序排序; (2)把概率最小的两个符号组成一个节点P1; (3)重复步骤(2),依次得到节点P2,P3,P4,构成了如图1.17所示的一棵倒立的“树”;其中,P4为树根,称为根节点;P1、P2、P3为树枝,称为枝节点;A、B、C、D和E为树叶; (4)从根节点P4开始到对应于每个符号的树叶,左分支标上“0”,右分支标上“1”; (5)从根节点P4开始顺着树枝到每个叶子分别写出每个符号的代码,无损压缩(3),霍夫曼编码,无损压缩(4),LZW算法 LZW算法是一种词典编码法,其根据是待编码的数据中总包含有重复代码即词 LZW算法先编制一个基本词典,该词典由待压缩数据当中出现过的每个字符构成,然后,在不断编码的待压缩数据的过程中不断扩充,词典中的每个词都有一个编号即码 数据经过LZW算法压缩的结果是一系列的码,无损压缩(4),LZW算法 假设待压缩数据为:ABBABABAC,有损压缩(1),对声音、图像等多媒体信息来说,忽略一些微小的细节信息不会严重影响视听质量。因此,可以通过有意丢弃一些对视听效果相对不太重要的细节数据来压缩数据,这类压缩方法就称为有损压缩。 经有损压缩的数据,进行数据重构,重构后的数据与原始数据有所不同,但不影响人对原始数据表达的信息的理解 JPEG:Joint Photographic Experts Group MPEG:Moving Picture Experts Group,有损压缩(2),JPEG:由国际标准化组织(ISO)和国际电工技术委员会(International Electrotechnical Commission)联合组成的一个专家组,负责制订静态的数字图像数据压缩标准 以离散余弦变换(Discrete Cosine Transform,DCT)为基础的有损压缩算法, 采用以预测技术为基础的无损压缩算法 以离散小波变换(Discrete Wavelet Transform,DWT)为基础的有损压缩算法(JPEG2000),有损压缩(3),MPEG:1988年由ISO和IEC成立的联合专家组,负责开发电视图像数据和声音数据的编码、解码和它们的同步等标准 标准包括:MPEG视频、MPEG音频和MPEG系统三个部分的多个标准 方法:先利用动态预测及差分编码方式去除相邻两张图像的相关性,然后用一般量化或向量量化的方式舍去一些画质而提高压缩比,最后再经过一个可变长度的不失真型压缩算法如霍夫曼编码而得到最少位数的结果 可以得到50:1到100:1的压缩比,1.6 数据传输误码及对策,两种策略: 检测传输错误,发现误码则重新传输或者发出错误警告,如奇偶校验 检测并纠正误码,如海明(纠错)码,奇偶校验,以单字节编码为例,可以在8位编码的最左端增加1位,校验位(Parity Bit) 奇校验(Ood Parity) 校验位总保持使整个9位序列里有奇数个1 偶校验(Even Parity) 校验位总使得编码序列含有偶数个1,纠错码(Error-c

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论