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