免费智能真题库 > 历年试卷 > 多媒体应用设计师 > 2016年上半年 多媒体应用设计师 上午试卷 综合知识
  第43题      
  知识点:   算法   编码   数据压缩
  关键词:   编码方法   数据压缩   编码   数据        章/节:   统计编码       

 
下列数据压缩编码方法中(43)编码属于词典编码
 
 
  A.  ADPCM
 
  B.  Huffman
 
  C.  DCT
 
  D.  LZW
 
 
 

 
  第46题    2020年下半年  
   38%
字典编码技术中的字典编码器使用的是(46)算法。
 
   知识点讲解    
   · 算法    · 编码    · 数据压缩
 
       算法
        隐式字典的典型压缩算法有LZ77和LZSS。显式字典的典型压缩算法有LZ78和LZW。下面介绍LZ77算法和LZSS算法。
               LZ77算法
               为了更好地说明LZ77算法的原理,首先介绍该算法中的几个术语。
               . 输入流:要被压缩的字符序列。
               . 字符:输入流中的基本数据单元。
               . 编码位置:输入流中当前要编码的字符位置,指前向缓冲存储器中的开始字符。
               . 前向缓存:存放从编码位置到输入流结束的字符序列。
               . 窗口:包含W个字符的窗口,字符是从编码位置开始往后数的,也就是最后处理的字符数。
               . 指针:指向窗口中的匹配串并包含长度的指针。
               LZ77算法的核心是查找从前向缓冲存储器开始的最长的匹配串。该算法的具体执行步骤如下。
               步骤1:把编码位置设置到输入流的开始位置。
               步骤2:查找窗口中最长的匹配串。
               步骤3:以(Pointer, Length)Characters的格式输出。其中Pointer是指向窗口中匹配串的指针,Length表示匹配字符的长度,Characters是前向缓存中不匹配的第1个字符。
               步骤4:如果前向缓冲存储器不是空的,则把编码位置和窗口向前移(Length+1)个字符,然后返回步骤2。
               LZSS算法
               LZSS算法通过输出真实字符解决了在窗口中出现没有匹配串的问题,但这种解决方案包含冗余信息,冗余信息表现在两个方面:一是编码器的输出可能包含空指针;二是编码器可能输出额外字符,即可能包含下一个匹配串中的字符。LZSS算法以比较有效的方法解决了这个问题,它的思想是如果匹配串的长度比指针本身的长度长,就输出指针,否则就输出真实字符。由于输出数据流中包含指针和字符本身,因此为了区分它们就需要有额外的标志位,即ID位。
               LZSS算法的具体执行步骤如下。
               步骤1:把编码位置置于输入流的开始位置。
               步骤2:在前向缓冲存储器中查找窗口中最长的匹配串。
               ①Pointe:匹配串指针。
               ②Length:匹配串长度。
               步骤3:判断匹配串长度Length是否大于或等于最小匹配串长度(Length≥MIN_ LENGTH)。
               是:输出指针,然后把编码位置向前移动Length个字符。
               否:输出前向缓冲存储器中的第1个字符,然后把编码位置向前移动1个字符。
               步骤4:如果前向缓冲存储器不是空的,则返回步骤2。
               在相同的计算环境下,LZSS算法比LZ77可获得更高的压缩比,而译码同样简单。这也就是为什么这种算法成为开发新算法的基础,许多后来开发的文档压缩程序都使用了LZSS的思想,如PKZip、ARJ、LHArc和ZOO等,其差别仅仅是指针的长短和窗口的大小有所不同。
               LZSS同样可以和熵编码联合使用,如ARJ就与霍夫曼编码联用,而PKZip则与Shannon-Fano联用,它的后续版本也采用霍夫曼编码。
 
       编码
               编码过程
               在给定了软件设计规格说明书后,下一步的工作就是编写代码。一般来说,编码工作可以分为四个步骤:
               (1)确定源程序的标准格式,制订编程规范。
               (2)准备编程环境,包括软硬件平台的选择,包括操作系统、编程语言、集成开发环境等。
               (3)编写代码。
               (4)进行代码审查,以提高编码质量。为提高审查的效率,在代码审查前需要准备一份检查清单,并设定此次审查须找到的bug数量。在审查时,要检查软件规格说明书与编码内容是否一致;代码对硬件和操作系统资源的访问是否正确;中断控制模块是否正确等。
               编码准则
               在嵌入式系统中,由于资源有限,且实时性和可靠性要求较高,因此,在开发嵌入式软件时,要注意对执行时间、存储空间和开发/维护时间这三种资源的使用进行优化。也就是说,代码的执行速度要越快越好,系统占用的存储空间要越小越好,软件开发和维护的时间要越少越好。
               具体来说,在编写代码时,需要做到以下几点:
               .保持函数短小精悍。一个函数应该只实现一个功能,如果函数的代码过于复杂,将多个功能混杂在一起,就很难具备可靠性和可维护性。另外,要限制函数的长度,一般来说,一个函数的长度最好不要超过100行。
               .封装代码。将数据以及对其进行操作的代码封装在一个实体中,其他代码不能直接访问这些数据。例如,全局变量必须在使用该变量的函数或模块内定义。对代码进行封装的结果就是消除了代码之间的依赖性,提高了对象的内聚性,使封装后的代码对其他行为的依赖性较小。
               .消除冗余代码。例如,将一个变量赋给它自己,初始化或设置一个变量后却从不使用它,等等。研究表明,即使是无害的冗余也往往和程序的缺陷高度关联。
               .减少实时代码。实时代码不但容易出错、编写成本较高,而且调试成本可能更高。如果可能,最好将对执行时间要求严格的代码转移到一个单独的任务或者程序段中。
               .编写优雅流畅的代码。
               .遵守代码编写标准并借助检查工具。用自动检验工具寻找缺陷比人工调试便宜,而且能捕捉到通过传统测试检查不到的各种问题。
               编码技术
                      编程规范
                      在嵌入式软件开发过程中,遵守编程规范,养成良好的编程习惯,这是非常重要的,将直接影响到所编写代码的质量。
                      编程规范主要涉及的三方面内容:
                      .命名规则。从编译器的角度,一个合法的变量名由字母、数字和下画线三种字符组成,且第一个字符必须为字母或下画线。但是从程序员的角度,一个好的名字不仅要合法,还要载有足够的信息,做到“见名知意”,并且在语意清晰、不含歧义的前提下,尽可能地简短。
                      .编码格式。在程序布局时,要使用缩进规则,例如变量的定义和可执行语句要缩进一级,当函数的参数过长时,也要缩进。另外,括弧的使用要整齐配对,要善于使用空格和空行来美化代码。例如,在二元运算符与其运算对象之间,要留有空格;在变量定义和代码之间要留有空行;在不同功能的代码段之间也要用空行隔开。
                      .注释的书写。注释的典型内容包括:函数的功能描述;设计过程中的决策,如数据结构和算法的选择;错误的处理方式;复杂代码的设计思想等。在书写注释时要注意,注释的内容应该与相应的代码保持一致,同时要避免不必要的注释,过犹不及。
                      性能优化
                      由于嵌入式系统对实时性的要求较高,因此一般要求对代码的性能进行优化,使代码的执行速度越快越好。以算术运算为例,在编写代码时,需要仔细地选择和使用算术运算符。一般来说,整数的算术运算最快,其次是带有硬件支持的浮点运算,而用软件来实现的浮点运算是非常慢的。因此,在编码时要遵守以下准则:
                      .尽量使用整数(char、short、int和long)的加法和减法。
                      .如果没有硬件支持,尽量避免使用乘法。
                      .尽量避免使用除法。
                      .如果没有硬件支持,尽量避免使用浮点数。
                      下图是一个例子,其中两段代码的功能完全一样,都是对一个结构体数组的各个元素进行初始化,但采用两种不同的方法来实现。下图(a)采用数组下标的方法,在定位第i个数组元素时,需要将i乘以结构体元素的大小,再加上数组的起始地址。下图(b)采用的是指针访问的方法,先把指针fp初始化为数组的起始地址,然后每访问完一个数组元素,就把fp加1,指向下一个元素。在一个奔腾4的PC上,将这两段代码分别重复10 700次,右边这段代码需要1ms,而左边这段代码需要2.13ms。
                      
                      算术运算性能优化的例子
 
       数据压缩
        多媒体数据特别是音频、视频数据量很大,需要很大的存储空间。特别是在现代通信中,基于因特网上的各种应用,图像传输速度是一项非常重要的指标。例如,以使用拨号接入因特网的家庭用户为例,若数据传输速度为56 Kb/s,则理想情况下,传输一幅分辨率为640×480的6.5万色的未经压缩的图像大约需要1~2分钟。因此,需要采用压缩编码技术,减少音频、视频数据量,提高网络传输速度。
        目前常用的数据压缩编码方法分为两种类型:一种是冗余压缩法,也称为无损压缩法;另一种是有损压缩法。
        无损压缩利用数据的统计冗余进行压缩,可以保证在数据压缩和还原过程中,图像信息没有损耗或失真,图像还原(解压缩)时可完全恢复,即重建后的图像与原始图像完全相同。一个常见的例子是磁盘文件的压缩存储,它要求解压缩后能保证百分之百地恢复原始数据。根据目前的技术水平,无损压缩可以将数据压缩到原来的1/2到1/4,压缩比较低。一些常用的无损压缩算法有哈夫曼(Huffman)算法和LZW压缩算法。
        有损压缩适用于重构信号不一定非要与原始信号完全相同的场合。例如,对于图像、视频影像和音频数据的压缩就可以采用有损压缩,这样可以大大提高压缩比(可达10:1甚至100:1),而人的感官仍不至于对原始信号产生误解。这种方法会减少信息量,而损失的信息是不能再恢复的,因此这种压缩是不可逆的。
        计算机中使用的图像压缩编码方法有多种国际标准和工业标准,目前使用广泛的编码及压缩标准有JPEG、MPEG和H.261。
        JPEG(Joint Photographic Experts Group)是制定静态和数字图像数据压缩编码标准,既可用于灰度图像,又可用于彩色图像。JPEG标准是由ISO和IEC两个组织机构联合组成的一个专家组负责制定的,目前已成为国际上通用的标准。
        MPEG(Moving Pictures Experts Group,动态图像压缩标准)是由ISO和IEC两个组织机构联合组成的一个活动图像专家组制定的标准草案,MPEG标准分成MPEG视频、MPEG音频和视频音频同步三个部分。MPEG-1是针对传输率为1~1.5Mb/s的普通电视质量的视频信号的压缩。MPEG-2是对每秒30帧的720×572分辨率的视频信号进行压缩,在扩展模式下,可以对分辨率达1440×1152的高清晰度电视(HDTV)信号进行压缩。MPEG-4是多媒体应用标准。MPEG-7是多媒体内容描述接口标准等。
        H.261视频通信编码标准也称为PX64K标准,是由国际电话电报咨询委员会(ITTCC)于1998年提出的电话/会议电视的建议标准。其中P是取值为1~30的可变参数,P=1或2时支持1/4通用中间格式(Quarter Common Intermediate Format,QCIF)的帧率较低的视频电话传输;P≤6时支持通用中间格式(Common Intermediate Format,CIF)的帧率较高的电视会议数据传输。PX64K视频压缩算法也是一种混合编码方案,即基于DCT的变换编码和带有运动预测差分脉冲编码调制(DPCM)的预测编码方法的混合。
   题号导航      2016年上半年 多媒体应用设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第43题    在手机中做本题