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