第 1章 图灵机模型及数据编码
? 图灵机模型理论是计算学科最核心的理
论之一
? 图灵机模型为计算机设计指明了方向
? 图灵机模型是算法分析和程序语言设计
的基础理论 。
本章主要内容
? 1.1 图灵机
? 1.2 位的存储
? 1.3 存储器
? 1.4 数据在计算机中的表示
? 1.5 数据压缩
? 1.6 数据传输误码及对策
图灵机的直观描述
? 3个部件：有穷控制器、无穷带和读写头
? 3个动作：改写当前格、左移或右移一格
读写头
有穷控制器
存储带
…… ……
图灵机模型
图灵机的形式化描述
? 图灵机是一个五元组（ K,∑,δ,s,H），
其中,
? K 是有穷个状态的集合；
? ∑ 是字母表，即符号的集合；
? s ∈ K是初始状态；
? H∈ K 是停机状态的集合，当控制器内部状态
为停机状态时图灵机结束计算；
? δ是转移函数，即控制器的规则集合。
计算, x+1”的图灵机
? 目标：利用二进制来设计一个专门计算
,x+1”的图灵机，要求计算完成时，读
写头要回归原位
? 状态集合 K,{start,add,carry，
noncarry,overflow,return,halt}；
? 字母表 ∑,{0,1,*}；
? 初始状态 s,start；
? 停机状态集合 H,{halt}；
计算, x+1”的图灵机
? 规则集合 δ,
,5＋ 1” 的计算过程（ 1）
,5＋ 1” 的计算过程（ 2）
,5＋ 1” 的计算过程（ 3）
,5＋ 1” 的计算过程（ 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）
? 二进制与十六进制的转换
161＝ 24,4位二进制数刚好可以表示 0－ F这 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）
? 整数和实数
? 实数
pdN ???? 2
数值的表示（ 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）
? 汉字编码
? 汉字国标码
? 全称是 GB2312－ 80,信息交换用汉字编码字符集 ——基
本集》,1980年发布，是中文信息处理的国家标准，也
称汉字交换码，简称 GB码。根据统计，把最常用的
6763个汉字分成两级：一级汉字有 3755个，按汉语拼
音排列；二级汉字有 3008个，按偏旁部首排列。为了编
码，将汉字分成若干个区，每个区中 94个汉字。由区号
和位号（区中的位置）构成了区位码。例如，“中”位
于第 54区 48位，区位码为 5448。区号和位号各加 32就
构成了国标码，这是为了与 ASCII码兼容，每个字节值
大于 32（ 0～ 32为非图形字符码值）。所以，“中”的
国标码为 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 7…… 7 7 1 1 1…… 1 1 1
（ 8个 0） （ 6个 1） （ 30个 7） （ 50个 1）
0 0 0…… 0 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-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位出错（单错），
那么方程组必然有一个或几个不满足，并
且各位出单错时，不满足的方程各不相同
? 图灵机模型理论是计算学科最核心的理
论之一
? 图灵机模型为计算机设计指明了方向
? 图灵机模型是算法分析和程序语言设计
的基础理论 。
本章主要内容
? 1.1 图灵机
? 1.2 位的存储
? 1.3 存储器
? 1.4 数据在计算机中的表示
? 1.5 数据压缩
? 1.6 数据传输误码及对策
图灵机的直观描述
? 3个部件：有穷控制器、无穷带和读写头
? 3个动作：改写当前格、左移或右移一格
读写头
有穷控制器
存储带
…… ……
图灵机模型
图灵机的形式化描述
? 图灵机是一个五元组（ K,∑,δ,s,H），
其中,
? K 是有穷个状态的集合；
? ∑ 是字母表，即符号的集合；
? s ∈ K是初始状态；
? H∈ K 是停机状态的集合，当控制器内部状态
为停机状态时图灵机结束计算；
? δ是转移函数，即控制器的规则集合。
计算, x+1”的图灵机
? 目标：利用二进制来设计一个专门计算
,x+1”的图灵机，要求计算完成时，读
写头要回归原位
? 状态集合 K,{start,add,carry，
noncarry,overflow,return,halt}；
? 字母表 ∑,{0,1,*}；
? 初始状态 s,start；
? 停机状态集合 H,{halt}；
计算, x+1”的图灵机
? 规则集合 δ,
,5＋ 1” 的计算过程（ 1）
,5＋ 1” 的计算过程（ 2）
,5＋ 1” 的计算过程（ 3）
,5＋ 1” 的计算过程（ 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）
? 二进制与十六进制的转换
161＝ 24,4位二进制数刚好可以表示 0－ F这 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）
? 整数和实数
? 实数
pdN ???? 2
数值的表示（ 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）
? 汉字编码
? 汉字国标码
? 全称是 GB2312－ 80,信息交换用汉字编码字符集 ——基
本集》,1980年发布，是中文信息处理的国家标准，也
称汉字交换码，简称 GB码。根据统计，把最常用的
6763个汉字分成两级：一级汉字有 3755个，按汉语拼
音排列；二级汉字有 3008个，按偏旁部首排列。为了编
码，将汉字分成若干个区，每个区中 94个汉字。由区号
和位号（区中的位置）构成了区位码。例如，“中”位
于第 54区 48位，区位码为 5448。区号和位号各加 32就
构成了国标码，这是为了与 ASCII码兼容，每个字节值
大于 32（ 0～ 32为非图形字符码值）。所以，“中”的
国标码为 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 7…… 7 7 1 1 1…… 1 1 1
（ 8个 0） （ 6个 1） （ 30个 7） （ 50个 1）
0 0 0…… 0 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-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位出错（单错），
那么方程组必然有一个或几个不满足，并
且各位出单错时，不满足的方程各不相同
