CN1187716C - 用于编码和解码关键字数据的装置和方法 - Google Patents

Abstract

提供一种用于编码解码关键字数据的装置和方法。用于编码关键字数据的DPCM的差分数据的装置包括：DND操作器，用于对输入的差分数据执行预定次数的DND操作，其中对输入的差分数据执行一分开操作以便平分属于正数区域的差分数据并且以便转换与另一半相比较属于上界的差分数据的一半为负值，或者在分开操作的结果上根据该分开操作结果的范围有选择地执行一上分操作或者下分操作以便缩小分别属于一负数区域或者正数区域的差分数据的范围，对DND操作的结果执行上移位操作的上移位操作器以便改变已经过DND操作的差分数据为正或者负数区域，差分数据选择器，有选择地输出或者已经过DND操作的差分数据或者已经过上移位操作的差分数据，以及熵编码器，通过差分数据选择器熵编码所选择的差分数据。

Description

用于编码和解码关键字数据的装置和方法

技术领域

本发明涉及一种编码和解码关键字数据(key data)的方法和装置，具体地说，涉及一种用于编码关键字数据的装置和方法，该装置和方法能够通过对关键字数据执行差分脉码调制(DPCM)产生差分数据以及通过执行预先确定的操作缩小要编码的差分数据的范围，来增加编码关键字数据的效率，还涉及解码所编码的关键字数据的装置和方法。

背景技术

三维(3D)表示已经广泛用于计算机系统中的三维电子游戏或者虚拟现实环境。虚拟现实模拟语言(VRML)用来表示三维动画。

用于场景(BIFS)的VRML和MPEG-4二进制格式提供一种以关键字成帧(keyframing)为基础的生动的表示方法。在该动画表示方法中，预定的关键字帧安排在任意时间轴上，并且关键字帧(key frame)之间的动画数据通过线性插值填充。该关键字帧由内插器(interpolator)节点定义，并且每个内插器结点由预定的范围以内的一浮点数代表，例如，从-∞到+∞变动。每个内插器结点构成由关键字数据组成的每个域，关键字数据表示某一关键字帧在该时间轴上的位置，并且关键字值数据表示相应于该关键字数据在该关键字数据上的特征以及运动信息。

为了通过使用分段线性插值的关键字成帧与实物运动一样自然流畅地表示活动性，必须通过每个内插器结点提供大量关键字帧信息，就计算费用和效率而言该事实产生严重的问题。结果，关键字成帧用于一种脱机环境，需要大容量的存储器存储大量三维动画数据。另外，当用于在线环境时，关键字帧也不仅要求这样的大容量存储器还要求高速数据传输线路，用于每次以高速传送大量数据以便从一服务器向一终端传送三维动画信息。在该情况下，因为在数据传输期间发生误差的可能性增加，数据的可靠性降低。因此，要求一种用于压缩和解码数据以便减少内插器结点数据量的有效方法。

MPEG-4 BIFS提供用于编码动画数据的两种不同的方法。一种是用于编码动画数据的BIFS-Q，另一是用于编码数据之间的差值的差分脉码调制(DPCM)。DPCM也叫做预测MF编码(PMFC)。BIFS-Q仅使用量化，因此不被认为有效。PMFC被认为比BIFS-Q更有效，因为在PMFC中，在执行DPCM之后执行熵编码以便取消冗余数据。用于关键字数据的PMFC编码器和PMFC解码器图示在图1中。如上所述，在编码动画数据时，PMFC不太有效，因为它仅在熵编码以前执行DPCM，而没有考虑到关键字的特征和关键字之间的相关性。

参考图1，输入的关键字数据105被输入到编码器100之内。量化器110接收输入的关键字数据105，并且将其量化为整数。DPCM处理器115接收所量化的关键字数据并且产生差分数据。熵编码器120接收该差分数据，根据发生符号的概率消除存在于比特(bits)之间的冗余，并且产生压缩的比特流125。由图1中所示的编码器100产生的比特流125输入到解码器150的熵解码器155中并进行熵解码(entropy-decode)。熵解码差分数据作为量化的差分数据输入到反向DPCM处理器160中，并且反向量化器165对从反向DPCM处理器160输入的量化的关键字数据执行反向量化，并输出所解码的关键字数据。

然而，编码器100仅在熵编码之前执行DPCM而不考虑键的特征，因此它很难实现显示高压缩比率的有效编码。

发明内容

为解决上述等问题，本发明的第一方面提供一种用于编码数据的装置和方法，当消除关键字数据的比特之间的冗余时，用于能够考虑关键字数据的特征以高效率压缩动画的关键字数据。

本发明的第二方面是提供一种用于解码比特流的装置和方法，该比特流由上面描述的编码数据的装置和方法编码。

为了实现本发明的上述和其他方面，提供一种用于编码关键字数据的DPCM的差分数据的装置。用于编码关键字数据的DPCM的差分数据的装置包括：DND(divide-and-divide，反复分开)操作器，用于对输入的差分数据执行预定次数的DND操作，在其中对输入的差分数据执行分开操作(divideoperation)以便二等分属于正数区域的差分数据，并转换属于区域上部的差分数据成为负值，或者根据该分开操作结果的范围，对分开操作的结果有选择地执行上分(divide up)操作或者下分(divide-down)操作，以便缩小分别属于负数区域或者正数区域的差分数据的范围；上移位操作器(shift-upoperator)，用于对DND操作的结果执行上移位(shift up)操作以便转移已经通过DND操作的差分数据到正数或者负数区域；差分数据选择器，用于有选择地输出已经通过DND操作的差分数据或者已经通过上移位操作的差分数据；以及熵编码器，用于熵编码(entropy-encode)被差分数据选择器所选择的差分数据。

为了实现本发明的上述和其他方面，提供一种用于编码关键字数据的DPCM的差分数据的装置。用于编码关键字数据的DPCM的差分数据的装置包括：移位器，用于获得在这些差分数据中具有最高频率的差分数据(模)，并且从每个差分数据中减去该模；折叠(fold)处理器，用于转换差分数据为正数区域或者负数区域；DND处理器，用于在考虑到所转换的差分数据以及它们中间的最大和最小值之间的关系的情况下，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，从移位器输入的差分数据、从该折叠处理器输入的差分数据、已经通过DND操作的差分数据、已经通过上移位操作以及DND操作的差分数据中选择之一，并且输出所选择的差分数据；以及熵编码器，用于熵编码从DND处理器输入的差分数据。

为了实现本发明上述和其他方面，提供一种用于编码关键字数据的装置，该关键字数据是关于时间轴上的关键字帧的位置的信息。用于编码关键字数据的该装置包括：量化器，用于以量化比特量化输入的差分数据；DPCM处理器，用于产生所量化的关键字数据的差分数据；移位器，用于获得在差分数据中间具有最高频率的差分数据(模)，并且从每个差分数据中减去该模；折叠处理器，用于转换差分数据为正数区域或者负数区域；DND处理器，用于在考虑到转换的差分数据以及它们中的最大和最小值之间的关系的情况下，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，从量化器输入的差分数据、从该折叠处理器输入的差分数据、已经通过DND操作的差分数据和已经通过上移位操作以及DND操作的差分数据中选择之一，并输出所选择的差分数据；以及熵编码器，用于熵编码从DND处理器输入的差分数据。

为了实现本发明上述和其他方面，提供一种用于编码关键字数据的装置，该关键字数据是关于时间轴上的关键字帧的位置的信息。用于编码关键字数据的该装置包括：量化器，用于以量化比特量化输入的差分数据；DPCM处理器，用于产生所量化的关键字数据的差分数据；移位器，用于获得差分数据中具有最高频率的差分数据(模)并从每个差分数据中减去该模；DND处理器，用于在考虑到所转换的差分数据以及它们中的最大和最小值之间的关系的情况下，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，从量化器输入的差分数据、从该折叠处理器输入的差分数据、已经通过DND操作的差分数据和已经通过上移位操作以及DND操作的差分数据中选择之一，并输出所选择的差分数据；以及熵编码器，用于熵编码从DND处理器输入的差分数据。

为了实现本发明上述和其他方面，提供一种用于编码关键字数据的装置，所述关键字数据是关于时间轴上的关键字帧位置的信息。用于编码关键字数据的装置包括：线性关键字编码器，用于在输入的关键字数据中识别在其中关键字数据线性地增加的区域，并且编码该线性关键字数据区域；量化误差最小化器；用于调整输入的关键字数据中的最大和最小值以便量化误差能够被最小化，并且输出调整的最大和最小值；量化器，用于利用从量化误差最小化器输入的最大和最小值，以预定的量化比特量化输入的关键字数据；浮点数换算器，用于转换表示从线性关键字编码器输入的线性关键字数据区域的首尾关键字数据的二进制数和表示从量化误差最小化器输入的最大和最小值为十进制数；DPCM处理器，用于产生所量化的关键字数据的差分数据；移位器，用于获得在差分数据中具有最高频率的差分数据(模)以及从每个差分数据减去该模；折叠处理器，用于转换该差分数据为正数区域或者负数区域；DND处理器，用于对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，从移位器输入的差分数据、从折叠处理器输入的差分数据、已经通过DND操作的差分数据和已经通过上移位操作以及DND操作的差分数据中选择之一，并且输出所选择的差分数据；熵编码器，用于熵编码从DND处理器输入的差分数据；以及关键字头编码器，用于使用编码所需数据产生关键字头数据，其中该数据是从线性关键字编码器、量化器(数字转换器)、浮点数换算器、DPCM处理器、移位器、折叠处理器、DND处理器以及熵编码器中至少之一输入的。

为了实现本发明的上述和其他方面，提供一种用于编码关键字数据的DPCM的差分数据的方法，其中，关键字数据是关于时间轴上关键字帧的位置的信息。该方法包括：对输入的差分数据执行预定次数的DND处理，在其中对输入的差分数据执行一分开操作，以便二等分属于正数区域的差分数据并转换属于上部范围的差分数据成为负值，或者根据分开操作结果的范围，对分开操作的结果有选择地执行上分操作或者下分操作以便缩小分别属于负数区域或者正数区域的差分数据的范围，对DND操作的结果执行上移位操作以便转移已经通过DND操作的差分数据到正数或者负数区域，选择已经通过DND操作的差分数据或者已经通过上移位操作的差分数据，并且熵编码该所选择的差分数据。

为了实现本发明的上述和其他方面，提供一种用于编码关键字数据的DPCM的差分数据的方法，其中，关键字数据是关于关键字帧在时间轴上的位置的信息。该方法包括：执行移位操作，其中具有最高频率的差分数据(模)从差分数据中处获得并且被从每个差分数据中减去，在已经通过移位操作的差分数据上执行折叠操作以便该差分数据转换成一正数区域或者一负数区域，执行一DND处理，其中，在考虑到已经通过该折叠操作的差分数据和它们中的最大和最小值之间的关系的情况下，对已经通过折叠操作的差分数据执行DND操作以便缩小它们的范围，并且选择已经通过该移位操作的差分数据、已经通过折叠操作的差分数据、已经通过DND操作的差分数据以及已经通过上移位操作以及DND操作的差分数据之一，并且熵编码该所选择的差分数据。

为了实现本发明的上述和其他方面，提供一种用于编码关键字数据的方法，该关键字数据是关于关键字帧在时间轴上的位置的信息。该方法包括：以量化比特来量化要编码的关键字数据，执行DPCM处理以便产生所量化的关键字数据的差分数据，执行移位操作，其中具有最高频率的差异数据(模)从差分数据中获得并且从每个差分数据中减去，转换该差分数据为一正数区域或者一负数区域，执行一DND处理，其中，在考虑到已经通过折叠操作的差分数据和它们中的最大和最小值之间的关系的情况下，对已经通过该折叠操作的差分数据执行DND操作以便缩小它们的范围，并且从已经通过该移位操作的差分数据、已经通过折叠操作的差分数据和已经通过DND操作的差分数据中选择之一，并且熵编码该所选择的差分数据。

为了实现本发明的上述和其他方面，提供一种用于在基于图形动画的键帧中编码关键字数据的方法，该关键字数据是关于关键字帧在时间轴上的位置的信息。该方法包括：量化要编码的关键字数据为量化比特；执行DPCM过程以便产生量化的关键字数据的差分数据；执行移位操作，其中从差分数据中获得具有最高频率的差分数据(模)，并且从每个差分数据中减去该模；执行一DND过程，其中在考虑到已经通过折叠操作的差分数据和它们中的最大和最小值之间的关系的情况下，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，选择从移位器输入的差分数据、从折叠处理器输入的差分数据、已经过DND操作的差分数据、已经过上移位操作和DND操作的差分数据其中之一；以及熵编码该所选择的差分数据。

为了实现本发明的上述和其他方面，提供一种在基于图形动画的关键字帧中用于编码关键字数据的方法，该关键字数据是关于时间轴上的关键字帧的位置的信息。该方法包括：执行线性关键字编码，在其中，关键字数据线性地增加的区域被确定并且被编码，执行浮点数换算以便将表示该线性关键字数据区域的首尾关键字数据的二进制数变为十进制数；执行量化误差最小化，在其中，调整要编码的关键字数据中的最大和最小值以便量化误差可以最小化并且表示调整最大和最小值的二进制数变为十进制数；执行量化，在其中，要编码的关键字数据以预定的量化比特使用已调整的最大和最小值量化；执行DPCM处理以便产生所量化的关键字数据的差分数据；执行移位操作，其中具有最高频率的差分数据(模)从差分数据中获得，并且被从每个差分数据中减去，执行折叠操作以便已经通过该移位操作的差分数据转送到一正数区域或者一负数区域；执行一DND处理，在其中，对已经通过折叠操作的差分数据执行DND操作以便缩小它们的范围，并且选择已经通过该移位操作的差分数据、已经通过折叠处理器的差分数据和已经通过上移位操作以及DND操作的差分数据之一，熵编码该所选择的差分数据；执行关键字头编码，在其中，量化、浮点数换算、DPCM处理、移位操作、折叠操作、DND处理和熵编码之一所产生的解码所需要的数据，作为关键字头产生。

在本发明中，为了很好地利用关键字数据的特征，首先在编码关键字数据期间计算关键字数据的分散度(degree of dispersion)。如上所述，关键字数据表示时间轴上的关键字帧的位置，并由此关键字数据值按照顺序从表示第一关键字帧的关键字数据到表示最后关键字帧的阶单调地增加。相应地，由第一DPCM操作获得的差分数据应该具有正值，如果对差分数据执行的第二DPCM操作，第二DPCM操作的结果应该具有或者正值或者负值。

通常，关键字数据中最大和最小值之间的差值越小，存在的冗余值越多，存在的冗余值越多，熵编码器具有越高的压缩率。相应地，在本发明中，熵编码在关键字数据范围缩小之后执行。DPCM的阶和DND的阶可以通过一最小分散度获得，并且DPCM和DND的每个周期的结果用来缩小关键字数据的范围。当关键字数据的密集度降低时，关键字数据的冗余增加。

附图说明

本发明的上述和其他方面和优点，参考附图通过详细描写最佳实施例将要变成更明显，其中：

图1是一传统的关键字数据编码器和关键字数据解码器的方框图；

图2A是按照本发明一最佳实施例的编码器的方框图；

图2B是图2A中所示的反复分开(divide-and-divide，DND)处理器的方框图；

图2C到2G是按照本发明的编码器例子的方框图；

图3A和3B是按照本发明最佳实施例的一用于编码关键字数据的方法的流程图；

图4A和4B是按照本发明最佳实施例的浮点数转化过程的流程图；

图5是按照本发明最佳实施例的量化处理的一流程图；

图6是按照本发明最佳实施例DPCM处理的一流程图；

图7是按照本发明的最佳实施例DND操作处理的一流程图；

图8是按照本发明最佳实施例的说明熵编码的一图表；

图9A到9J是表示按照本发明的最佳实施例已经通过不同操作的关键字数据的图表；

图10A和10B是说明使用关键字数据和关键字值数据编码动画数据的处理的图表；

图11A是按照本发明最佳实施例的一关键字数据解码器的方框图；

图11B 11E是按照本发明的关键字数据解码器的例子的方框图；

图12是按照本发明一最佳实施例用于解码关键字数据的方法的流程图；

图13是按照本发明最佳实施例反向DND操作处理的一流程图；

图14A到14E是显示解码需要的比特流语法和变量的例子的图表；以及

图15A到15C是显示实现程序代码的例子的图表，其中列举了解码关键字数据需要的操作。

具体实施方式

图2A是按照本发明一最佳实施例的编码器的一方框图。

按照本发明最佳实施例的一种用于编码关键字数据的方法将要参考图3A和3B进行描述。图3A和3B是用于编码关键字数据的方法的流程图。参考图3A和3B，如果关键字数据被输入一编码器，则关于例如关键字数据的数目和每个关键字数据的数字的数目的消息将被输入关键字头编码器270，并且被解码。线性关键字编码器200在输入的关键字数据中搜索存在于某些时间区间上关键字帧的区域，关键字数据具有相同差值，并且该关键字数据线性地变化，搜索到的线性区域首先在步骤S3000编码。

著名的3D应用软件，例如3Dmax Maya，在具体区域中基于动画使用具有预定时间隙的键产生关键字帧。在该情况下，有可能容易地使用线性关键字数据区域的首尾关键字数据以及存在于它们之间的关键字帧的数目，来编码关键字数据。相应地，线性预测对在某一区域中使用内插器编码关键字非常有用。

下列等式用于线性预测。

$t\left(i\right)=\frac{t_E-t_S}{E-S}+t_S(0\&le;i\&le;E-S,S<E)...\left(1\right)$

在这里t_s表示部分线性的区域开始的关键字的数据，t_E表示部分线性的区域结束的关键字的数据，S表示t_s的索引，E表示t_E的索引。从第S个关键字数据到第E个关键字数据之间的具体区域中的实数关键字数据之间的误差和线性地预示下列方程式(1)的关键字数据可以使用下列等式计算。

$e_i=t\left(i\right)-t_{i+S}=\frac{t_E-t_s}{E-S}i+t_s-t_{i+s}...\left(2\right)$

如果使用等式(2)所计算的误差中的最大值不大于一预定的临界值，则t_j可以被认为在区域[t_s，t_E]中互线性或者在某一误差范围里面。极限误差值t_i是否与具体区域互线性由下列等式(3)确定。

$E_p=\underset{i=0,\&CenterDot;\&CenterDot;\&CenterDot;(E-S)}{\mathrm{MAX}}\left|e_i\right|=\underset{i=0,\&CenterDot;\&CenterDot;\&CenterDot;(E-S)}{\mathrm{MAX}}|\frac{t_E-t_S}{E-S}i+t_S-t_{i+S}|...\left(3\right)$

如果 $E_p\&le;\frac{1}{2^{\mathrm{nBits}+1}}$ 与区域[t_s、t_E]互线性。在这里，nBits表示用于编码的比特的数目。

如果线性关键字编码器200搜索部分地线性区域，则首尾部分线性的关键字数据区域的该首尾关键字数据输出到该浮点数换算器205。包括在线性关键字数据区域内的关键字的数目输出到关键字头编码器270并且被编码。它有可能使用线性编码显著地减少编码的数据的数值。

开始关键字数据和结尾关键字数据使用后面描述的浮点数换算编码。为了编码开始关键字数据和结尾关键字数据，该浮点数换算器205转换表示为二进制的关键字数据成十进制数据。

计算机存储该浮点数为32位二进制数。如果表示为二进制的浮点数是给定的，则该浮点数换算器205转换该浮点数成十进制的尾数和指数，并且该过程通过下列等式表示。

例如，浮点数12.34可以通过计算机变为二进制数，如下列所示的。

$\frac{0}{1}\frac{10001010111000010100011}{2}\frac{10000010}{3}$

1：符号

2：二进制的尾数

3：二进制的指数

该二进制数可以变为下列方程式(4)的十进位数，如下列所示。

$\frac{0}{1}\frac{1234}{2}\frac{2}{3}$

1：符号

2：十进制的尾数

3：十进制的指数

为了在比特流中包含十进制的尾数和指数，必须计算要求用于表示尾数和指数的比特的数目。该指数具有-38和38之间的值，因此可以使用7比特表示它及其符号。要求用于表示尾数的比特的数目依赖于数字的数目。该尾数的值和要求用于表示该尾数的比特数在下列图表中所示。

表1

尾数的值	尾数的数字	所需要的比特数
			0	0	0
1-9	1	4
			10-99	2	7
100-999	3	10
			1000-9999	4	14
10000-99999	5	17
			100000-999999	6	20
1000000-9999999	7	24

那些已经搜索并且使用上述的过程转换的线性关键字数据区域的首尾关键字数据按照图4A和4B中所示的编码过程编码，然后输出到关键字头编码器270，并且保存在该比特流中。

图4A和4B表明浮点数换算器205编码两个输入浮点数。浮点数换算器205编码浮点数的方法将要参考图4A和4B进行描述。

浮点数换算器205接收原始的关键字数据的数位Kd、开始关键字数据S和结束关键字数据E，并且在步骤S3040以下列方程式(4)转换它们。

浮点数换算器205首先编码S。具体地说，浮点数换算器205检查S的数位是否不同于Kd。如果S的数位不同于Kd，则在步骤S3042获得S的数位并且输出到关键字头编码器270。浮点数换算器205使用函数Digit()获得S的数位。

如果S的数位大于7，则在步骤3043使用预定的位数(在本发明中，遵循IEEE标准754的浮点数方式使用下列32比特)将S输出到关键字头编码器270，以便S的数位可以被包括在该比特流中。

如果S的数位不是0并且小于7，则在步骤3044中，浮点数换算器205输出S的符号给关键字头编码器270。编码S尾数绝对值要求的比特数使用图表1获得。接下来，在步骤3045，S尾数的绝对值使用图表1获得的比特数输出到关键字头编码器270。在步骤S3046，浮点数换算器205计算S的指数，输出S的符号给关键字头编码器270，并且作为预定的位数，例如，6比特，输出该指数给关键字头编码器270。这样的关键字数据转换使显著地减少包括在比特流内的比特数成为可能。

如果S的数位是0，则开始关键字数据的编码结束，并且该方法转到转换结尾关键字数据E的步骤，原因是当S的数位是0时，相应的浮点数也是不要求编码的0。

在转换并编码开始关键字数据S之后，浮点数换算器205转换结尾关键字数据E。E的转换几乎与S的转换相同。具体地说，在步骤S3047，检查E的指数是否与S的指数相同。如果E的指数与S的指数相同，则只有指出E的指数与S的指数相同的标志位输出到关键字头编码器270。在步骤S3048，如果E的指数与S的指数不相同，则E的指数像标志位一样以与已经输出到关键字头编码器270的S指数同样的方式输出到关键字头编码器270。

不属于线性区域的输入的关键字数据中的关键字数据输入到量化器210并按照预定的量化比特长度，即nKeyQBit，进行量化。

然而，在使用解码器解码量化的关键字数据的情况下，由于原始的关键字数据之间的误差以及量化的关键字数据不可能完整地恢复原始的关键字数据。因此，本发明的量化器210获得输入的关键字数据中的最大值和最小值，并使用最大值和最小值量化输入的关键字数据。另外，本发明包含一量化误差最小化器215以便原始的关键字数据之间的误差和它们的量化的关键字数据可以使用输入的关键字数据中的最大值和最小值进行最小化。

在步骤S3100，量化误差最小化器215预先使用一用于控制量化范围的方法量化或者反向地量化该输入的关键字数据以便量化误差可以最小化。

具体地说，如果用于量化的混合最大值由Max表示，用于量化的被控制的最小值由Min代表，输入值由X_i代表，用于量化的比特数由nQuantBit代表，则量化的输入值

反向地量化值

和误差e_i利用下列等式获得。

${\tilde{X}}_i=\mathrm{floor}\left(\frac{X_i-\mathrm{Min}}{\mathrm{Max}-\mathrm{Min}}\right)*(2^{\mathrm{nQuantBit}}-1)+0.5...\left(5\right)$

${\hat{X}}_i=\frac{{\tilde{X}}_i*(\mathrm{Max}-\mathrm{Min})}{2^{\mathrm{nQuantBit}}-1}+\mathrm{Min}$

$e_i=X_i-{\hat{X}}_i$

有两个用于减少误差的和∑e_i的方法。一是通过连续地控制Min直到误差的和最小的方法。另一方法如下。

首先，假定X_i＝(i+n)Δx+ε_i，其中X_i表示一输入的关键字数据序列，Δx表示一输入数据基本步长，n是一任意整数，ε_i表示零均值随机噪声。

接下来，当d_i＝X_i-X_i-1＝Δx+(ε_i-ε_i-1)，Δ’x＝E[d_i]并且Min＝Max-Δ’x*(2^nQuantBit-1)。

Min可以使最小化一量化误差成为可能，Max输入到量化器210并且用于关键字数据的量化。量化器210接收最大和最小值Max和Min，Min可以最小化量化误差并且在步骤S3200中按照下列方程式(6)量化关键字数据fKeyi。

${\mathrm{nQKey}}_i=\mathrm{floor}(\frac{f{\mathrm{Key}}_i-\mathrm{fKeyMin}}{\mathrm{fKeyMax}-\mathrm{fKeyMin}}(2^{\mathrm{nKeyQBit}}-1)+0.5)...\left(6\right)$

这里，i表示一量化的关键字数据的索引，nQKey_i表示量化的关键字数据的整数阵列，fKey_i表示量化的关键字数据的浮点数阵列，fKeyMax表示从量化误差最小化器(minimizer)215输入的最大值，fKeyMin表示从量化误差最小化器215输入的最小值，以及nKeyQBit表示量化比特大小。在等式(6)中，函数floor(v)是输出一不大于某一浮点值v的最大整数的函数。

本发明的量化器210可以不使用这样的算法来减少量化误差，在这样情况下仅仅利用输入的关键字数据中的最大和最小值fKeyMax和fKeyMin执行量化。

本发明的量化过程将参考图5更完全地描述。

量化器210在步骤S3210接收关键字数据并且在步骤3220中检测最大和最小值MAX和MIN是否从量化误差最小化器215输入。

如果输入MAX和MIN，量化器210在步骤3230分别设置最大和最小值fKeyMax和fKeyMin作为MAX和MIN量化，并且输出最近设置的最大和最小值fKeyMax和fKeyMin给浮点数换算器205。最大和最小值fKeyMax和fKeyMin通过上述的浮点数转化过程转换并编码，并且输出到关键字头编码器270以便它们可以被包括在一用于解码的关键字头中。

如果没有值从量化误差最小化器215输入，则量化器210在步骤S3240分别设置第一关键字数据fKey0和最终密钥数据fKeyN-1作为最小值fKeyMin和最大值fKeyMax。

接下来，在步骤S3250量化器210中检查最大值fKeyMax是否小于1但是大于0以及最小值fKeyMin是否大于0。如果最大值fKeyMax不小于1或非大于0，则最大和最小值fKeyMax和fKeyMin输出到浮点数换算器205，并且通过上述的浮点数换算转换并编码。接下来，在步骤S3260已经转换并编码的最大和最小值fKeyMax和fKeyMin被包括在关键字头中以便它们可被用于解码。

另一方面，如果最大值fKeyMax小于1并且最小值fKeyMin大于0，则在步骤S3270检查表示最大和最小值fKeyMax和fKeyMin是否将包括在用于解码的关键字头内的标志。如果该标志建立以便最大和最小值fKeyMax和fKeyMin可以被包括在该关键字头中，则执行步骤S3260以便将最大和最小值fKeyMax和fKeyMin输出到该关键字头编码器270。如果该标志没有建立，则量化器210不许最大和最小值fKeyMax和fKeyMin包括在该关键字头中。

在最大和最小值fKeyMax和fKeyMin没有包括在该关键字头内的情况下，建议关键字数据编码器和关键字数据解码器分别执行编码和解码，分别设置最大和最小值fKeyMax和fKeyMin在1和0上。在这种情况下，在步骤S3280中，分量化器210别设置最大和最小值fKeyMax和fKeyMin在1和0上。最大和最小值fkeymax和fKeyMin对关键字数据解码器来说是已知的，以便它们不需要被包括在该关键字头中。

量化器210通过替代那些已经通过上述的过程建立的最大和最小值fKeyMax和fKeyMin，量化该输入的关键字数据成等式(6)，并且在步骤S3290输出量化的关键字数据给DPCM处理器220。

DPCM处理器220接收量化的关键字数据，并且对量化的关键字数据执行预定的次数的DPCM。接下来，DPCM处理器220输出DPCM的阶和在每个DPCM周期中的内部关键字数据给关键字头编码器270，其中通过DPCM的阶可以获得在分散度中的最小值和。在步骤S3300，DPCM处理器220输出由DPCM产生的差分数据给移位器230。

参考图6，在步骤S3310，DPCM处理器220对输入的关键字数据执行预定的次数，并且存储DPCM的周期数作为DPCM的阶。在本发明一最佳实施例中，DPCM可以执行三个次。

这以后，在步骤S3320，DPCM处理器220计算DPCM每个周期的结果的分散度，该分散度可以由密集度、标准偏差或者四分位偏差表示，并且在本发明的最佳实施例中，可以使用四分位偏差。

接下来，DPCM处理器220选择一DPCM周期，其中在分散度中可以获得一最小值，并且输出选择的DPCM的阶的结果给该移位器230。在步骤S3330选择的DPCM的周期、每个DPCM周期的内部关键字数据及DPCM需要的其他信息单元输出到关键字头编码器270。然而，在本发明的一最佳实施例中，如果键数目小于5，则DPCM只执行一次。例如，DPCM的第一周期按下列方程式(7)执行。

                 4＝nQKey_i+1-nQKey_i…(7)

这里i表示量化的关键字数据的索引，nQKey_i表示整数阵列，Δ_i表示差分数据。在步骤S3340，DPCM处理器220计算要求编码选择的DPCM周期的比特数和已经由DPCM在预定的存储器(nQStep_DPCM)中产生的关键字数据的差分数据。编码所需要的比特数的计算可以随后在被编码的选择关键字数据随后的步骤中同时执行，该事实对本领域的技术人员来说是明显的。

移位器230选择一差分数据(在下文中，称为一模)，用于具有从DPCM处理器220输入的差分数据之中的最高频率。则在步骤S3400移位器230从全部差分数据减去该模以便大多数被编码的数据安排0，并且编码所需要的比特数可以减少。

执行这样的移位操作从全部量化的关键字数据减去模，由下列等式表示。

              shift(nQKey_i)＝nQKey_i-nKeyShift…(8)

这里，i表示量化的关键字数据的索引，nQKeyi表示整数阵列，nKeyShift表示一模值。作为移位操作的结果，具有最高频率的差分数据变成0以便编码所需要的比特数可以显著地减少。

已经通过移位操作的关键字数据输出到一折叠处理器240和DND处理器250，并且模值nKeyShift输出到关键字头编码器270以便被包括在该关键字头中。

在步骤S3500，折叠处理器240对移位器230的输出执行一折叠操作，并且输出折叠操作的结果给DND处理器250。

折叠操作通过集中它们在正数或者负数区域中，来缩小广泛的分散于正数区域和负数区域的差分数据的范围。在本实施例中，折叠操作按照下列方程式(9)执行以便集中差分数据在该正数区域中。

fold(nQKey_i)＝2·nQKey_i(if nQKey_i≥0)…(9)

＝2|nQKey_i|-1(if nQKey_i＜0)

这里，i表示量化的关键字数据的索引，nQKeyi表示整数阵列。作为折叠操作的结果，正差分数据变为偶数，负差分数据变为奇数。

折叠处理器240计算编码已经通过折叠操作的差分数据所需要的比特数，并且存储它在预定的存储器nQStep_fold中。在这步骤中，编码所需要的比特数的计算可以在选择被熵编码的差分数据的随后的步骤中执行，该事实对于本领域技术人员来说是明显的。在折叠处理器240中由折叠操作产生的数据输出到DND处理器250。

为了提高熵编码的效率，DND处理器250在关键字数据的输入的差分数据上执行预定次数，因此缩小在S3600中差分数据的范围。

参考图2B，DND处理器250包含：对差分数据执行DND操作的DND操作器252；第一差分数据选择器254，用于以用于编码的比特数为基础选择熵编码的差分数据；移位向上操作器256，用于在已经通过DND操作的差分数据上执行上移位操作；以及第二差分数据选择器258，用于从已经仅仅通过DND操作的差分数据和已经通过上移位操作的差分数据之间选出具有一较低分散度的差分数据，并且输出所选择的差分数据到熵编码器260。

在DND操作器252中执行的DND操作将要在下文中描述。

当已经通过折叠处理器240中的折叠操作的差分数据输入到DND操作器252时，它们分成两个组，具有比另一组差分数据范围大的一组差分数据由一分开函数移到正数区域。该分开函数由下列等式定义。

$\mathrm{div}\mathrm{ide}({\mathrm{nQKey}}_j,\mathrm{nKeyMax})...\left(10\right)$

$={\mathrm{nQKey}}_j-(\mathrm{nKeyMax}+1)({\mathrm{if\; nQKey}}_j>\frac{\mathrm{nKeyMax}}{2})$

$={\mathrm{nQKey}}_j({\mathrm{if\; nQKey}}_j\&le;\frac{\mathrm{nKeyMax}}{2})$

这里，j表示输入的差分数据的索引，nQKey_j表示整数阵列，nKeyMax表示已经通过折叠操作的差分数据中的最大值。尤其，在大多数差分数据密集地沿着由全部差分数据占据的全部区域边界提供的情况下，利用该分开操作有可能显著地缩小在所有差分数据中全部的区域。

在分开操作之后，在编码所需要的比特长度被用作该分散度的度量以便可以选择在用于编码的比特长度中的最小值的情况下，计算该分散度。

在DND操作之后，进一步执行不同类型的DND操作，即，上分操作或者下分操作。上分操作或者下分操作是否将要进一步执行将由差分数据的正范围长度和差分数据的负范围长度确定。

如果具有正值的差分数据的范围大于具有负值的差分数据的范围，则由下列等式定义的下分操作被执行。

$\mathrm{div}\mathrm{ide}-\mathrm{down}({\mathrm{nQKey}}_j,\mathrm{nKeyMax})...\left(11\right)$

$=-2(\mathrm{nKeyMax}-{\mathrm{nQKey}}_j+1)+1---({\mathrm{if\; nQKey}}_j>\frac{\mathrm{nKeyMax}}{2}>$

$={\mathrm{nQKey}}_j---(\mathrm{if}0\&le;{\mathrm{nQKey}}_j\&le;\frac{\mathrm{nKeyMax}}{2})$

$=2\&CenterDot;n{\mathrm{QKey}}_j---(\mathrm{if\; n}{\mathrm{QKey}}_j<0)$

另一方面，如果具有正值的差分数据的范围大于具有负值的差分数据的范围，由下列等式定义的上分操作被执行。

$\mathrm{div}\mathrm{ide}-\mathrm{up}(n{\mathrm{QKey}}_j,\mathrm{nKeyMin})...\left(12\right)$

$=n{\mathrm{QKey}}_j---(n{\mathrm{QKey}}_j\&GreaterEqual;0)$

$=2\&CenterDot;n{\mathrm{QKey}}_j---(\frac{\mathrm{nKeyMin}}{2}\&le;n{\mathrm{QKey}}_j\&le;0)$

$=2(\mathrm{nKeyMin}-n{\mathrm{QKey}}_j-1)+1---(n{\mathrm{QKey}}_j<\frac{\mathrm{nKeyMin}}{2})$

等式(11)和(12)中，j表示量化的关键字数据的索引，nQKey_j表示整数阵列，nKeyMax表示nQKey_j的最大值，nKeyMin表示nQKey_j的最小值。

DND操作器252的操作将要参考图7在下文中进行描述。

当输入的关键字数据的差分数据从该折叠处理器240输入时，DND操作器252在步骤S3610输入的差分数据中的获得最大值nKeyMax和最小值nKeyMin。然后，DND操作器252在步骤S3620比较nKeyMin和nKeyMax的绝对值。如果nKeyMax不小于nKeyMin的绝对值，在则步骤S3622种，DND操作器252在DND操作的当前周期中设置nKeyMax作为一最大值。

在步骤S3624，DND操作器252检测DND操作的阶是否是1，换言之，DND操作的阶是否为1，如果是，DND操作器252在步骤S3630中对输入的差分数据执行一分开操作，替代等式(10)中的最大值nKeyMax。

此后，在步骤S3640，DND操作器252利用函数getQBit()测量编码该差分数据范围需要的比特长度，该差分数据范围已经利用分开操作缩小了。如果在步骤S3650，DND操作的阶是1，则将编码所需要的比特长度存储为一表示用于编码的比特最小长度的值nQBitDND，并且在步骤S3655中将DND操作的阶数增加1。

接下来，DND处理器252再次通过S3622执行步骤S3610。在步骤S3624，如果DND操作的阶不是1，则DND操作器252在步骤S3634执行下分操作替代等式(11)中的最大值nKeyMax。在步骤S3640，DND操作器252计算编码已经通过下分操作的差分数据所需要的比特数。如果该数小于在上一DND操作周期中所存储的最小值nQBitDND，则在步骤S3658它替换在DND操作之后编码所需要的比特的最小长度。

在步骤S3620，如果最小值nKeyMin的绝对值大于最大值nKeyMax的绝对值，则将DND操作的当前周期中的最大值作为一最小值在步骤S3623更新，然后在步骤S3628执行一上分操作，替代等式(12)中的用于nKeyMin的最小值。此后，在步骤S3640，DND操作器252计算用于编码已经通过上分操作的差分数据的比特数。在步骤S3652，如果计算的结果小于已经保存在上一DND操作周期中的nQBitDND，则在步骤S3658中它替换在DND操作之后编码所需要的比特的最小数nQBitDND。

DND处理器252执行预定次数的DND操作，并且DND操作的性能数目可以变化。例如，在当前实施例中，DND操作执行7次。DND操作器252输出nQBitDND和相应于nQBitDND的差分数据给第一差分数据选择器254。DND操作器252输出产生相应的差分数据的DND阶给关键字头编码器270，并且允许将它们包括在该比特流中。

第一差分数据选择器254接收已经通过移位操作的差分数据，已经通过该折叠操作的差分数据和已经通过DND操作的差分数据，并且确定三个中将要被熵编码的差分数据。

参考图3A和3B，如果在步骤S3700，在DND操作之后编码所需要的比特最小数nQBitDND不小于在DPCM操作之后编码的比特长度nQStep-DPCM，则在步骤S3710，第一差分数据选择器254选择DPCM的结果并且对差分数据执行一移位操作。接下来，第一差分数据选择器254输出移位操作的结果给该熵编码器260，并且允许它们在步骤S3710被熵编码。在该情况下，DND操作的阶设置为-1，被输出到关键字头编码器270，并且被包括在该关键字头中。

然而，如果在步骤S3720，结果是nQBitDND小于nQStep-DPCM，并且不小于用于在折叠操作之后编码的比特长度，则在步骤S3730，第一差分数据选择器254输出已经通过该折叠操作的差分数据给熵编码器260，并且允许将它们熵编码，而在这样情况下DND操作的阶设置在0上，被输出到该关键字头编码器270，并由此被包括在该关键字头中。

如果在DND操作之后用于编码差分数据比特数最小，则在步骤S3740，第一差分数据选择器254输出已经通过DND操作的差分数据到上移位操作器256，然后该上移位操作器256计算从第一差分数据选择器254输入的差分数据的第一分散度。接下来，在步骤S3800上移位操作器256对已经通过DND操作的差分数据执行由下列等式定义的上移位操作，并且在步骤S3810计算上移位操作结果的第二分散度。

              shift-up(nQKey_j，nKeyMax)   …(13)

              ＝nQKey_j           (if nQKey_j≥0)

              ＝nKeyMax-nQKey_j   (if nQKey_j＜0)

这里，j表示量化的关键字数据的差分数据的索引，nQKey_j表示整数阵列，并且nKeyMax表示差分数据中的最大值。

当已经通过DND操作的差分数据和已经通过上移位操作的差分数据被输入时，在步骤S3900第二差分数据选择器258比较第一分散度和第二分散度。如果第二分散度小于第一分散度，第二差分数据选择器258输出已经通过上移位操作的差分数据给该熵编码器260，并且允许它们在步骤S3910被熵编码。第二差分数据选择器258输出用于DND操作的最大和最小值，用于上移位操作的最大值nKeyMax给该关键字头编码器270，并且允许将它们包括在该关键字头中。

然而，如果第一分散度小于第二分散度，第二差分数据选择器258输出已经通过DND操作的差分数据给该熵编码器260，并且允许它们在步骤S3920被熵编码。然后，第二差分数据选择器258仅输出用于DND操作的最大和最小值nKeyMax和nKeyMin给该关键字头编码器270。在本发明的一最佳实施例中，标准偏差可以用作第一和第二分散度的度量。

熵编码器260对根据差分数据的特征的差分数据执行两个不同函数。例如，已经通过DPCM操作的差分数据和已经通过兼备正和负的值的分开操作的差分数据，因此执行编码每个差分数据的符号以及差分数据自身的过程是必要的。另一方面，因为已经通过折叠操作的差分数据仅具有正值，因此执行仅编码差分数据的过程。

在本发明的一最佳实施例中，函数encodeSignedAAC用于编码该差分数据和它们的符号，而函数encodeUnsignedAAC用于仅仅编码差分数据。

图8是函数encodeSignedAAC例子的一图表。参考图8，当输入值是74并且用于编码该输入值的比特数是8时，它的符号是0，与二进制数1001010相同。符号和全部位平面用下列方式编码：

第一步：二进制数按照从它的最高有效位(MSB)到它的最低位(LSB)的次序在每个位平面上编码；

第二步：检测当前被编码的比特是否是0；

第三步：如果当前被编码的比特不是0，该二进制数的符号接下来被编码；

第四步：二进制数的剩余比特被编码。

函数encodeUnsignedAAC利用关于该值的范围编码不具有符号的值作为一自适应的算术编码比特流。该函数与函数encodeSignedAAC除了存在一符号范围几乎相同。

图9A到9J是显示按照本发明的一最佳实施例已经经受操作的关键字数据的图表。在图9A到9J中，X轴表示每个关键字数据的索引，Y轴表示关键字数据的值。

图9A是一显示输入到本发明的编码器中的原始的关键字数据的图表。图9A中所示的关键字数据输出到量化器210，然后利用9量化比特量化以便获得图9B中所示的量化的关键字数据。如果DPCM在图9B中所示的量化的关键字数据上执行，则获得图9C中所示的差分数据。

接下来，量化的关键字数据的差分数据利用一大约7的模值移位，以便获得图9D中所示的差分数据。此后，如果在移位的差分数据上执行一折叠操作，可以获得如图9E中所示的仅仅具有正值的数据。

对图9E中所示的折叠数据执行DND操作的结果示出在图9F到9H中。具体地说，对折叠数据执行一分开操作的结果在图9F中所示。如图9F中所示，正关键字数据值从0到28变动，负关键字数据值从-29到0变动，其中负关键字数据值的范围大于正关键字数据值的范围。相应地，用于要求在图9F中所示的数据上执行一上分操作，并且该上分操作的结果在图9G中所示。

作为上分操作的结果，负关键字数据值的范围显著地缩小以致它远小于正关键字数据值的范围。在随后的DND操作的周期中，在上分操作的结果上执行下分操作。图9H是显示对图9G中所示的差分数据执行下分操作的结果的图表。对图9H中所示的关键字数据执行上移位操作的结果示出在图9I中。

如图9A到9G中所示，关键字数据和差分数据的范围逐渐地减小。然而，如图9H和9I中所示，差分数据的范围在上移位操作之后和以前相比显著的增加，表明该差分数据已经通过图9H中所示的下分操作是如图9J中所示最后编码的数据。

在关键字头编码器270中编码的信息和保存在关键字头的信息将要在下文中描述。

当输入要编码的关键字数据时，关键字头编码器270编码关键字数据的数位和被编码的键数目。接下来，关键字头编码器270接收有关是否存在在线性关键字数据区域上的信息，该信息已经通过在输入的关键字数据中线性关键字编码，接收在线性关键字数据区域中来自线性关键字编码器200的关键字数据的数目，以及接收已经通过来自浮点数换算器205的浮点数换算的线性关键字数据区域的首尾关键字数据。

在浮点数换算器205接收可以导致最小值量化误差的最大和最小值并且转换它们成为浮点数的情况下，转换的最大和最小值从浮点数换算器205输入到关键字头编码器270中，以便它们能被再次使用于反向量化。另外，量化比特的长度也输入关键字头编码器270，并且被包括在该关键字头中。

关键字头编码器270接收DPCM的阶以及来自DPCM处理器220的DPCM每个周期中的内部关键字数据，并且接收已经用于来自移位器230的移位操作的一模值。另外，关键字头编码器270从DND处理器250得到的关于上移位操作是否已经执行的信息，通过DND的阶差分数据的分散度可以被最小化，并且最大和最小化在DND操作的每个周期中的值。

最后，关键字头编码器270从熵编码器260接收用于编码的比特数，并且作为一关键字头编码它。

按照本发明的最佳实施例，关键字数据编码器的一例子已经在上面描述了。很明显，对于本领域的普通技术人员，本发明可以概括在不同方式中。在下文中，按照本发明的其它最佳实施例的能够增加编码关键字数据效率的关键字数据编码器的其它例子将要参考图2C到2G更充分地描述。在图2A到2G中，相同标号数字表示相同元件。

参考图2C，按照本发明的另一最佳实施例的关键字数据编码器包含一量化器210、一DPCM处理器220、一移位器230、一折叠处理器240、一DND处理器250以及一熵编码器260。

输入到关键字数据编码器中的关键字数据首先输入到量化器210中，然后量化成预定的量化比特。量化的关键字数据输入到DPCM处理器220中。然后，DPCM处理器220执行关于量化的关键字数据的DPCM操作，并且输出DPCM操作的结果即差分数据到该移位器230。移位器230获得一具有差分数据中最高频率的差分数据(一模)并且执行从每个差分数据中减去该模的移位操作。接下来，移位器230输出移位操作的结果到该折叠处理器240。该折叠处理器240转换从移位器230输入的差分数据到正或者负数区域中，并且输出该转换的结果到DND处理器250。DND处理器250对从折叠处理器240输入的差分数据执行DND操作。接下来，DND处理器250从已经通过移位操作的差分数据、已经通过折叠操作的差分数据和已经通过DND操作的差分数据中选出可以最小化用于编码的比特数的差分数据，并且输出所选择的差分数据到熵编码器260，以便关键字数据可以是编码。这里，DND处理器250不必对已经通过DND操作的差分数据执行上移位操作，并且该关键字数据编码器显示一比传统的关键字数据编码器高得多的编码效率。

参考图2D，按照本发明另一最佳实施例的关键字数据编码器包含一量化器210、一DPCM处理器220、一移位器230、一折叠处理器240、一DND处理器250以及一熵编码器260。

关键字数据首先输入到量化器210中，并利用预定的量化比特量化。量化的关键字数据输入到DPCM处理器220中。然后，DPCM处理器220对量化的关键字数据执行一DPCM操作，并且输出DPCM操作的结果即差分数据到该移位器230。移位器230获得一差分数据中具有最高频率的差分数据(一模)并且执行从每个差分数据中减去该模的移位操作。接下来，移位器230输出移位操作的结果到DND处理器250。DND处理器250在从移位器230输入的移位的差分数据上执行DND操作。接下来，DND处理器250算出在已经通过移位操作的差分数据和已经通过DND操作的差分数据之间编码需要的少量比特数的差分数据。如果已经通过DND操作的差分数据变为具有编码需要的小数量，DND处理器250在其上执行上移位操作。接下来，DND处理器250从已经通过上移位操作的差分数据和已经通过DND操作的差分数据中选出来具有编码需要的小数量比特的差分数据。则DND处理器250输出所选择的差分数据到该熵编码器260。熵编码器在从DND处理器250输入的差分数据上执行熵编码，由此产生一比特流。在当前实施例中的关键字数据编码器显示比传统的关键字数据编码器更高的编码效率即使它不执行一折叠操作。

参考图2E，当关键字数据的差分数据输入时，按照本发明另一最佳实施例的关键字数据编码器编码差分数据并且输出它们。

关键字数据编码器包含一移位器230、一折叠处理器240、一DND处理器250、以及一熵编码器260。

具有输入的差分数据中最高频率的差分数据从移位器230中的输入的差分数据中减去，并且减的结果输出到折叠处理器240。折叠处理器240转换从折叠处理器240输出的差分数据成为正数或者负数区域并且输出转换的结果到DND处理器250。DND处理器250在从折叠处理器240输入的差分数据上执行DND操作，并且算出可以最小化在已经通过该移位操作的差分数据、已经通过折叠操作的差分数据和已经通过DND操作的差分数据中编码所需要的比特数的差分数据。如果已经通过移位操作或者折叠操作的差分数据认为能够最小化编码所需要的比特数，DND处理器250输出它们到熵编码器260以便关键字数据可以被编码。另一方面，在已经通过DND操作的差分数据选择的情况下，DND处理器250对差分数据执行上移位操作。接下来，DND处理器250从已经通过DND操作和已经通过上移位操作的差分数据中选出来具有编码需要的小数量比特的差分数据。接下来，所选择的差分数据输出到熵编码器260。熵编码器260编码DND操作250的输出，因此产生一比特流。在当前实施例中的关键字数据编码器也显示一传统的关键字数据编码器更高的编码效率。

图2F是按照本发明另一最佳实施例的关键字数据编码器的方框图。参考图2F，关键字数据编码器包含DND操作器252、上移位操作器256、一差分数据选择器258b、和一熵编码器260。

DND操作器在输入其中的关键字数据的差分数据上执行上面描述的DND操作，并且输出DND的差分数据到上移位操作器256和差分数据选择器258b。上移位操作器256在从DND操作器252输入的差分数据上执行一上面描述的上移位操作，然后输出上移位操作的结果到该差分数据选择器258b。差分数据选择器258b比较编码从DND操作器252输入的DND的差分数据所需要的比特数和编码从上移位操作器256输入的差分数据所需要的比特数并且输出编码需要的小数量比特的差分数据到该熵编码器260以便使关键字数据比特流输出。在当前实施例中的关键字数据编码器也显示一比传统的关键字数据编码器更高的编码效率。

在图2G中，显示按照本发明另一最佳实施例的关键字数据编码器，通过确设置为输入的差分数据中的线性关键字数据区域增加编码关键字数据的效率。关键字数据编码器包含线性关键字编码器200、浮点数换算器205、量化器210、熵编码器280和关键字头编码器270。

当关键字数据输入到图2G中所示的关键字数据编码器中时，线性关键字编码器200在输入的关键字数据中搜索关键字数据线性地增加的区域，即，线性关键字数据区域，并且输出线性关键字数据区域的该首尾关键字数据到浮点数换算器205。输入的关键字数据除线性关键字数据区域外输入到量化器210。输入到量化器210中的关键字数据利用预定的量化比特量化，并且输出到该熵编码器280。熵编码器280通过执行预定的操作在它们上编码从量化器210输入的量化的关键字数据，并由此作为比特流输出该操作的结果。

浮点数换算器205转换线性关键字数据区域的由二进制数表示的首尾关键字数据成为十进制并且输出转换的结果到该关键字头编码器270，以便它们可以被包括在该比特流中。在当前实施例中的关键字数据编码器可以进一步包含一量化误差最小化器215。

利用关键字数据和关键字值数据编码动画数据的过程参考图10A和10B将要更充分地描述。

关键字值动画路径中，关键字值编码器搜索表示几乎与关键字值的动画路径相同的一组点，而在这样情况下可以缩小大量关键字值并且其余通过键选择标志表示。例如，假定给定关键字值表示图10A中所示的一曲线并且选择四个点，键选择标志具有如图10B中所示的一些值。这样的键选择标志通过熵编码器260编码以便只有相应于键选择标志的关键字值数据被编码。

SDL程序代码的一例子和已经用于上述的编码过程的变量将要参考图14A到14E更充分地描述。

类(class)关键字头的程序代码示出在图14A中。首先描述用于程序代码的变量。

关键字头数据是解码关键字数据所需要的信息单元。关键字头的主要信息包含关键字的数目、量化比特、内部关键字(intra key)数据、DND头和解码所需要的比特数。nKeyQBit表示用于反向量化的量化比特，用于恢复浮点数关键字值，nNumKeyCodingBit表示代表关键字数据数目的nNumberOfKey的比特量，而nKeyDigit表示原始关键字数据的有效数字的最大数，并且用于舍入所解码的值。在线性关键字数据区域上的信息包括在该关键字头中的情况下，标志blsLinearKeySubRegion设置为1，在这样情况下，包括在关键字的整个范围内部的预定子区域内的一些关键字可以利用跟随标志blsLinearKeySubRegion的解码的标题信息进行计算。BRangeFlag代表关键字数据的范围是否在0和1之间。如果关键字数据不在0到1之间，则从类KeyMinMax解码最小值和最大值。最大和最小值中的每个可以被分成尾数和指数。nBitSize表示bQIntraKey的比特大小，nKeyShift表示nKeyMax原始的比特大小。nQIntraKey表示首先量化的内部数据的大小，与表示nQIntraKey符号的nQIntraKeySign联合，并被用作恢复其它量化的关键字数据的基础。在用于内插器压缩的符号比特之中，0表示正值，1表示负值。nKDPCMOrder与从DPCM的阶减去1的结果相同。DPCM的阶在1到3之间变动，并且与内部数据的数目相同。

nkeyShift与符号位nKeyShiftSign一起是代表关键字数据解码器中的移位总量的整数。当bShiftFlag设置为1时，解码nKeyShift和nKeyShiftSign。nDNDOrder是DND的阶。DND将在随后按照本发明一最佳实施例的关键字数据解码器详细描述。如果nDNDOrder是7，则解码bNoDND。布尔值nDNDOrder表示反向DND是否被执行的信息。nKeyMax和nKeyMin分别表示用在DND操作的相邻周期中的最大和最小值。nKeyCodingBit是用于编码关键字数据的比特。bSignedAACFlag显示该解码方法将要用于AAC解码。If bSignedAACFlag是0，执行unsignedAAC解码，否则执行signedAAC解码。bKeylnvertDownFlag是表示nKeylnvertDown是否要使用的信息的布尔值。nKeylnvertDown是一整数，并且基于该整数转换量化的关键字数据，以便量化的关键字数据变为不大于-1的自然(native)值。如果nKeylnvertDown是-1，则不执行下移位操作。

图14B是显示类LinearKey的程序代码的图表。在图14B中，nNumLinearKeyCodingBit是表示编码预定数目的关键字所需要的比特数，其中预定数目的关键字可以线性预测。

图14C是显示类KeySelectionFlag的程序代码的图表。在图14C中，keyFlag是一布尔阵列，表示第i个关键字值是否已经解码的信息。nNumOfKeyValue是表示要解码的关键字值的数目的整数。

图14D是显示类KeyMinMax程序代码的图表。在图14D中，bMinKeyDigitSame表示在所有关键字中最高有效位的数目是否与这些关键字中的最大值的最高有效位数目相同。nMinKeyDigit表示这些关键字中的最大值最高位比特的数目。nMinKeyMantissaSign表示nMinKeyMantissa的符号。NMinKeyMantissa表示这些关键字中的最小值的尾数。

nMinKeyExponentSign指的是nMinKeyExponent的符号。nMinKeyExponent表示这些关键字中的最小值的指数。

fKeyMin表示这些关键字中的最小值。nMaxKeyDigitSame表示全部关键字的最高有效位的数目nKeyDigit是否与这些关键字中的最大值的最高有效位的数目相同。nMaxKeyDigit表示这些关键字中的最大值的最高有效位数目。nMaxKeyMantissaSign表示nMaxKeyMantissa的符号。nMaxKeyMantissa表示这些关键字中的最大值的尾数。

bSameExponent表示这些关键字中的最大值的指数是否与nMinKeyExponent相同。nMaxKeyExponentSign表示nMaxKeyExponent的符号。nMaxKeyExponent表示这些关键字中的最大值的指数。fKeyMax表示这些关键字中的最大值。

图14E是显示类Key程序代码的图表。在图14E中，nQKey表示从比特流解码的量化的关键字数据阵列。KeyContext表示用于读出nQKey大小的某一范围。KeySignContext表示用于读出nQKey符号的一范围。

decodeUnsignedAAC是用于利用一给定范围执行无符号的解码的函数，将要在下文中更充分地描述，而decodeSignedAAC是一利用另一给定范围执行符号解码的函数，将在随后进行描述。

在下文中，将要参考图11和12描述按照本发明的一最佳实施例的、用于解码关键字数据的装置和方法。

图11A是按照本发明的一最佳实施例的解码关键字数据的装置。用于解码关键字数据的该装置接收一编码的比特流，并且通过解码将其重建成关键字数据。

用于解码关键字数据的装置包括：关键字头解码器370和关键字数据解码器。该关键字数据解码器包含熵解码器360、反向DND处理器350、反向折叠处理器340、反向移位器330、反向DPCM处理器320、反向量化器310、线性关键字解码器300和浮点数逆换算器305。

图12是按照本发明的一最佳实施例的、用于解码关键字数据的方法的流程图。参考图11A和12，由关键字数据压缩成的比特流被输入到关键字头解码器370和熵解码器360中。

在步骤S4000，关键字头解码器370解码解码每步所需要的信息单元，并且将他们提供到它们的相应的解码步骤。由关键字头解码器370解码的信息将随每个解码步骤进行描述。

熵解码器360从关键字头解码器370接收解码的差分数据的数目和已经用于编码的比特数，即，用于解码的比特数，并且在步骤S4100，解码输入的比特流。差分数据的数目等于从关键字数据的数目减去通过执行DPCM获得的内部关键字数据的数目的结果。

熵解码器360以包括在该比特流内预定的信息为基础确定被解码的差分数据是否具有负值或者正值，例如，在当前实施例中的bSignedAACFlag。如果编码的差分数据具有负值，则熵解码器360利用函数decodeSignedAAC()解码它们。另一方面，如果编码差分数据只具有正值，则熵解码器360利用函数decodeUnsignedAAC()解码它们。此后，解码的差分数据被传输到反向DND处理器350。

随后描述按照本发明的一最佳实施例的、用于实现这样的用于解码比特流的函数的程序代码的例子。

反向DND处理器350从解码器370接收DND的阶和DND每个周期中的最大值nKeyMax。

如果DND的阶是-1，这意味着被解码的编码差分数据已经通过DPCM操作而不是经历DND的移位操作进行了熵解码，并且该方法直接转移到执行反向移位操作的步骤上。如果DND的阶是0，这意味着被解码的编码差分数据已经经历一折叠操作而不是经历DND进行了熵解码，因此该方法直接转移到执行反向折叠操作的步骤上。

反向DND处理器350确定被解码的编码差分数据是否已经通过上移位操作在步骤S4170被编码。在本发明的一最佳实施例中，通过检查包括在一比特流内的nKeylnvertDown是否大于0来确定被解码的编码差分数据是否已经经历上移位操作进行了编码。

如果解码的编码差分数据没有经过上移位操作，该方法转移到执行反向DND的步骤上。另一方面，如果被解码的编码差分数据已经过上移位操作，则在步骤S4200，将通过执行上移位操作从正数区域转移到一负数区域的差分数据移回到该负数区域。在本发明的一最佳实施例中，已经过上移位操作的差分数据通过执行一下移位操作(向下倒置(invert-down)操作)进行恢复，该操作由下列等式表示。

       invert-down(v)                             …(14)

       ＝v                      (if v≤nKeyInvertDown)

       ＝nKeyInvertDown-v       (if v＞nKeyInvertDown)

这里，nKeylnvertDown具有与用于上移位操作的最大值nKeyMax一样的值。作为下移位操作的结果，具有基于nKeylnvertDown的值的差分数据变为-1以下的负值。

根据DND的每个周期中的最大值有选择地对已经过下移位操作的差分数据执行反下分操作或者上分操作。

参考图13，反向DND处理器350执行与在编码期间已经过DND操作的差分数据同样多次的反向DND操作。换句话说，反向DND处理器350设置一等于DND的阶的反向DND的阶的初始值。接下来，每当反向DND处理器350执行一反向DND操作，反向DND处理器350就从反向DND的阶的初始值中减去1，并且反向DND处理器350保持执行反向DND操作直到反向DND的阶变成1。在步骤S4310，反向DND处理器350在DND每个周期中搜索nKeyMax并且检查每个nKeyMax是否不小于0。

如果nKeyMax小于0，这意味着上分操作已经在编码过程中执行了，并由此在步骤S4320，反向DND处理器350通过执行一上分操作扩展被解码的差分数据的范围到负数区域。在本发明的一最佳实施例中，可以使用由等式(15)定义的反上分操作。

$\mathrm{inverse}-\mathrm{div}\mathrm{ide}-\mathrm{up}\left(v\right)...\left(15\right)$

$=v---(\mathrm{if\; v}\&GreaterEqual;0)$

$=(n{\mathrm{KeyMax}}_i-1)-\frac{v-1}{2}---(\mathrm{if\; v}<0,v\mathrm{mod}2\&NotEqual;0)$

$=\frac{v}{2}---(\mathrm{if\; v}<0,v\mathrm{mod}2\&NotEqual;0)$

然而，如果nKeyMax不小于0，则反向DND处理器350检测反向DND的阶是否是1。如果反向DND的阶不是1，这意味着在编码过程中已经对被解码的差分数据执行了下分操作，并由此在步骤S4340，反向DND处理器350通过执行一反下分操作扩展差分数据的范围到一正数区域。

$\mathrm{inverse}-\mathrm{div}\mathrm{ide}-\mathrm{down}\left(v\right)...\left(16\right)$

$=v---(\mathrm{if\; v}\&GreaterEqual;0)$

$=(n{\mathrm{KeyMax}}_i+1)+\frac{v-1}{2}---(\mathrm{if\; v}<0,v\mathrm{mod}2\&NotEqual;0)$

$=\frac{v}{2}---(\mathrm{if\; v}<0,v\mathrm{mod}2=0)$

如果nKeyMax不小于0，并且反向DND的阶是1，则在步骤S4350，反向DND处理器350在执行一反向分开操作之后结束整个反向DND操作。在本发明的一最佳实施例中，可以使用根据方程式(17)定义的反向分开操作。

                   inverse-divide(v)       …(17)

                   ＝v                 (if v≥0)

                   ＝v+(nKeyMax₀+1)   (if v＜0)

已经过反向DND操作的关键字数据的差分数据输入到反向折叠处理器340中，并且在步骤S4400，反向折叠处理器340对差分数据执行一反向折叠操作，以便曾经是仅用在正数区域中的差分数据被分成正值和负值。在本发明的一最佳实施例中，可以使用根据方程式(18)定义的一反向折叠操作。

$\mathrm{inverse}-\mathrm{fold}\left(v\right)=\frac{(v+1)}{2}---(\mathrm{if\; v}\mathrm{mod}2\&NotEqual;0)...\left(18\right)$

$=\frac{v}{2}---(\mathrm{if\; v}\mathrm{mod}2=0)$

$=0---(\mathrm{if\; v}=0)$

已经过反向折叠操作的差分数据输出到该反向移位器330，该反向移位器330添加一已经被用于编码过程并且从关键字头解码器370输入的模nKeyShift到该从反向折叠处理器340输入的差分数据，在步骤S4500。这操作通过下列等式表示。

inverse-shift(v)＝v+nKeyShift          …(19)

在步骤S4600，反向DPCM处理器320利用从关键字头编码器370输入的DPCM的阶，恢复从反向移位器330输入的差分数据成为量化的关键字数据。反向移位器330执行与下列方程式(20)DPCM的阶同样多次的反向DPCM操作。

                 v(i+1)＝v(i)+delta(i)    …(20)

这里，i表示差分数据和关键字数据的索引，v表示整数阵列，delta(i)表示差分数据。

已经过反向DPCM操作的量化的关键字数据输入到反向量化器310中。然后，反向量化器310从关键字头解码器370接收关于量化比特的大小nKeyQBit和用于反向量化的最大和最小值是否通过浮点数换算器205编码的信息，并且在步骤S4700，利用下列等式转换量化的关键字数据成为反向地量化的关键字数据。

$\mathrm{inverse}-\mathrm{quantize}\left(v\right)=\mathrm{fKeyMin}+\frac{v}{2^{\mathrm{nKeyQBit}}-1}\&times;(\mathrm{fKeyMax}-\mathrm{fKeyMin})...\left(21\right)$

如果用于量化的最大和最小值在编码关键字数据过程中没有通过浮点数换算器205转换，则等式(21)中所示的fKeyMin和fKeyMax分别设置为0和1。然而，如果用于量化的最大和最小值已经通过浮点数换算器205转换，则通过该浮点数逆换算器305反向地转换的最大和最小值分别被用作反向量化的最大和最小值。

随后描述实现针对反向量化的反向DND操作的程序代码的例子。

从反向量化器310输出的解码的关键字数据被添加到在线性关键字解码器300中解码的关键字数据，因此构造解码的关键字数据。

在下文中，将描述一线性关键字译码过程。

关键字头解码器370从一比特流解码关键字头信息。如果线性关键字数据区域上的信息存在于该比特流中，则关键字头解码器370输出解码线性关键字数据区域的首尾关键字所需要的信息到浮点数换算器305，并且输出作为线性关键字编码的关键字数目到该线性关键字解码器300。

浮点数逆换算器305反向地转换通过十进制数表示的线性关键字数据区域的首尾关键字成为二进制数，并且输出二进制数到线性关键字解码器300。

假定两个被解码的浮点数被认为是fKeyMin和fKeyMax，则解码fKeyMin的过程如下。

关键字头解码器370从比特流读出fKeyMin数位。如果fKeyMin的数位是0，fKeyMin设置0，并且为了解码fKeyMax，从该比特流的数位中读出fKeyMax。如果fKeyMax的数位(digit number)不小于8，这意味着fKeyMax已经按照IEEE标准754编码。因此，浮点数fKeyMax在它的32比特读出之后被解码。

然而，如果fKeyMax数位在1和7之间，则关键字头解码器370从该比特流读出一符号位。在本发明的一最佳实施例中，如果该符号位是1，则将MinKeyMantissaSign设置为-1。另一方面，如果该符号位是0，则将MinKeyMantissaSign设置为1。此后，解码所需要的比特数参考图表1获得，图表1显示尾数的数位和编码所需要的比特数之间的关系。接下来，与编码所需要的比特数同样多的比特流的比特被读出，并且保存在nMinKeyMantissa中。然后，比特流的下一位被读出，并且以与尾数的符号保存在MinKeyMantissaSign中同样的方式，将其保存在MinKeyExponentSign。相应于指数值的该比特流的随后6比特被读出，并且保存在nMinKeyExponent中。

浮点数逆换算器305通过替代从关键字头解码器370输入的值成为等式(22)来恢复fKeyMax。

$\mathrm{fKeyMin}=\frac{\mathrm{MinKeyMantissaSign}*\mathrm{nMinKeyMantissa}}{{10}^{\mathrm{MinKeyExponentSign}*\mathrm{nMinKeyExponent}}}...\left(22\right)$

恢复fKeyMax的过程与恢复fKeyMin的过程相同。具体地说，在从该比特流读出fKeyMax的指数以前，它确定是否与fKeyMin的指数一样的值被用作fKeyMax的指数。如果没有将与fKeyMin的指数一样的值用作fKeyMin的指数，则以从比特流读出的fKeyMin的指数同样的方法，从该比特流读出fKeyMax的指数。

线性关键字解码器300从浮点数逆换算器305接收线性关键字数据区域的首尾关键字，并且按照下列方程式(23)解码线性关键字数据区域。

${\mathrm{Key}}_i=\mathrm{fKeyMin}+\frac{(\mathrm{fKeyMax}-\mathrm{fKeyMin})*i}{(\mathrm{nNumberOfLinearKey}-1)}...\left(23\right)$

$(i=0,\&CenterDot;\&CenterDot;\&CenterDot;,\mathrm{nNumberOfLinearKey}-1)$

这里，fKeyMin和fKeyMax分别表示线性关键字数据区域的该首尾关键字数据。

使用上述的方法，将在线性关键字数据区域中解码的关键字数据添加到从反向量化器310输出的关键字数据上，然后将添加后的结果作为最终的关键字数据输出。

已经在上面描述了按照本发明一最佳实施例的、用于解码关键字数据的装置的一例子。很明显，对于本领域的普通技术人员来说，本发明可以以不同方式实现。在下文中，将参考图11B到11E描述用于解码关键字数据本装置的不同实施例。图11A到11E中相同标号数字表示相同元件。

参考图11B，用于按照本发明另一最佳实施例的、解码关键字数据的装置包括：熵解码器360、反向DND操作器352、反向折叠处理器340、反向移位器330、反向DPCM处理器320和反向量化器310。

当由关键字数据编码成的比特流输入到用于解码关键字数据的装置中时，熵解码器360熵解码输入的比特流，并且输出熵解码的结果，即，解码的差分数据到反向DND操作器352。反向DND操作器352确定输入的差分数据是否已经过基于关于该输入的差分数据的DND的阶的DND操作。如果差分数据已经过DND操作，则反向DND操作器352对差分数据执行一反向DND操作，并且输出反向DND操作的结果。如果差分数据没有经过DND操作，则反向DND操作器352将其分流。

反向折叠处理器340检测从反向DND操作器352输入的差分数据是否已经经过了使用DND的阶的折叠操作，如果该差分数据已经过折叠操作，则对差分数据执行一反向折叠操作。如果该差分数据没有经过折叠操作，则该反向DND操作器352将它们分流到该反向移位器330。

反向移位器330对从反向折叠处理器340输入的差分数据执行一反向移位操作，并且输出反向移位操作的结果到反向DPCM处理器320。反向DPCM处理器320转换从反向移位器330输入的差分数据到量化的关键字数据中，并且输出量化的关键字数据到反向量化器310。反向量化器310反向地量化所量化的关键字数据并且输出所解码的关键字数据。

参考图11C，按照本发明另一最佳实施例的、用于解码关键字数据的装置包括：熵解码器360、反向DND处理器350、反向移位器330、反向DPCM处理器320和反向量化器310。

当由关键字数据编码而成的比特流输入到用于解码关键字数据的装置中时，熵解码器360熵解码输入的比特流，并且输出所解码的差分数据到反向DND处理器350。反向DND处理器350检测从熵解码器360输入的差分数据在编码关键字数据的过程中是否已经过上移位操作。如果输入的差分数据已经过上移位操作，则反向DND处理器350在该差分数据上顺序地执行一下移位操作和一反向DND操作，并且输出反向DND操作的结果。如果该输入的差分数据没有经过上移位操作，则反向DND处理器350对差分数据执行一反向DND操作，并且输出反向DND操作的结果到该反向移位器330。

反向移位器330对从反向DND处理器350输入的差分数据执行一反向移位操作，并且输出反向移位操作的结果到反向DPCM处理器320。反向DPCM处理器320转换从反向移位器330输入的差分数据成量化的关键字数据，并且输出量化的关键字数据到反向量化器310。反向量化器310反向地量化所量化的关键字数据，并且输出所解码的关键字数据。

参考图11D，按照本发明另一最佳实施例的、用于解码关键字数据的装置包括：熵解码器360、反向上移位操作器356和反向DND操作器352。

所输入的比特流在熵解码器360中解码，在差分数据中转换并且输入到反向上移位操作器356中。该反向上移位操作器356对输入的差分数据执行一下移位操作，并且输出下移位操作的结果到反向DND操作器352。反向DND操作器352对从上移位操作器356输入的差分数据执行一反向DND操作，并且输出所解码的关键字数据的差分数据。解码的关键字数据的差分数据可以使用一通用的解码器输出。

参考图11E，按照本发明另一最佳实施例的、用于解码关键字数据的装置解码一比特流，该比特流已经在用于编码关键字数据的装置中使用线性关键字编码器中进行了编码。用于解码关键字数据的装置包括：熵解码器380、关键字头解码器370、反向量化器310和浮点数逆换算器305。

所输入的比特流输入到熵解码器380和关键字头解码器370中。熵解码器380熵解码相应于关键字数据的一部分比特流，在其上执行预定的操作，并且输出预定操作的结果到反向量化器310。关键字头解码器370解码相应于关键字头的另一部分比特流，并且输出包括在线性关键字数据区域内的关键字数据数目到一线性关键字解码器。另外，关键字头解码器370输出线性关键字数据区域的首尾关键字数据上的信息到该浮点数逆换算器305。

反向量化器310反向地量化所量化的关键字数据，并且输出反向量化的结果。线性关键字解码器使用线性关键字数据区域的该首尾关键字数据解码线性关键字数据区域，该首尾关键字数据是从该浮点数逆换算器305输入的。接下来，线性关键字解码器添加解码的线性关键字数据到从反向量化器310输出的关键字数据并且输出所解码的关键字数据。

下文将参考图15A到15C描述实现用于解码关键字数据的操作的程序代码的例子。

图15A图解的是实现函数decodeSignedAAC()的程序代码的例子，该函数用于借助有关于值和它们的符号的范围(context)，解码没有来自已经过自适应的算术编码的比特流的符号的值。

图15B是一说明程序代码例子的图表，该程序代码实现函数decodeUnsignedAAC()，该函数借助于有关于值和它们的符号的范围(context)，编码不具有来自已经过自适应的算术编码的比特流的标志的值。在图15B中，qf_decode()表示用于读出来自比特流的一位的函数。

图15C是说明程序代码一例子的图表，该程序代码实现上面已经描述的、针对反向量化的反向DND操作。

本发明可以作为记录在计算机可读记录介质上的计算机可读代码实现。这里，计算机可读记录媒体包含可以通过计算机系统阅读的任何种类的记录媒体。例如，计算机可读记录媒体包含ROM、RAM、CD-ROM、磁带、软盘、光数据存储器、载波(经过国际互联网络传输的)。计算机可读记录媒体可以分散到基于网络连接的计算机系统，并且计算机可以以分散的方式访问该记录媒体。

不同于用于编码解码关键字数据的传统装置，按照本发明用于编码解码关键字数据的方法和装置可以通过执行移位操作、折叠操作、针对通过执行DPCM操作获得的差分数据的DND操作，显著地提高编码关键字数据的效率，并且编码可以最小化编码所需要的比特数的操作中至少之一的结果。因此，按照本发明，可以显著地减少用于存储三维动画的空间并且以高速传输动画数据。

虽然本发明是参考其最佳实施例进行具体显示和描述的，但本领域的技术人员可以理解，可以在其中作出形式和细节上的不同变化，只要它们不背离附属的权利要求书所限定的发明的精神和范围。

Claims (54)

1、一种用于编码关键字数据的DPCM的差分数据的装置，其中，关键字数据是关于关键字帧在时间轴上的位置的信息，该装置包括：

DND操作器，用于对输入的差分数据执行预定次数的DND操作，在其中对输入的差分数据执行一分开操作，以便二等分属于正数区域的差分数据并且转换属于区域上部的差分数据成为负值，或者根据分开操作结果，对分开操作的结果有选择地执行上分操作或者下分操作，以便缩小分别属于负数区域或者正数区域的差分数据的范围；

上移位操作器，用于对DND操作的结果执行上移位操作以便转移已经过DND操作的差分数据到正数或者负数区域；

差分数据选择器，用于有选择地输出已经过DND操作的差分数据或者已经过上移位操作的差分数据；以及

熵编码器，用于通过差分数据选择器熵编码所选择的差分数据。

2、如权利要求1的装置，其中，差分数据选择器度量已经过DND操作的差分数据的分散度和已经过上移位操作的差分数据的分散度，并且输出具有低分散度的那个差分数据。

3、一种用于编码关键字数据的DPCM的差分数据的装置，其中，关键字数据是关于关键字帧在时间轴上的位置的信息，该装置包括：

移位器，用于获得差分数据中具有最高频率的差分数据，并且从每个差分数据中减去该模；

折叠处理器，用于将该差分数据转换到正数区域或者负数区域；

DND处理器，根据转换的差分数据以及它们中的最大和最小值之间的关系，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，从移位器输入的差分数据、从折叠处理器输入的差分数据、已经过DND操作的差分数据、已经过上移位操作和DND操作的差分数据中选择一，并且输出所选择的差分数据；以及

熵编码器，用于熵编码从DND处理器输入的差分数据。

4、如权利要求3的装置，其中，如果从移位器输入的差分数据大于预定的基准值，则折叠处理器以一第一常数乘该差分数据，如果差分数据小于预定的基准值，折叠处理器以第一常数乘每个差分数据的绝对值，并且从每个乘积中减去一第二常数。

5、如权利要求3的装置，其中，DND处理器包括：

DND操作器，用于对从折叠处理器输入的差分数据执行DND操作；

第一差分数据选择器，用于在已经过移位操作的差分数据、已经过折叠操作的差分数据和已经过DND操作的差分数据中选择之一，并且输出所选择的差分数据；

上移位操作器，如果已经过DND操作的差分数据从第一差分数据选择器输入，则对差分数据执行上移位操作；

第二差分数据选择器，用于有选择地输出已经过DND操作的差分数据或者已经过上移位操作的差分数据。

6、如权利要求5的装置，其中，DND操作器对从折叠处理器输入的差分数据执行DND操作以便缩小编码的差分数据的范围，具体地说，在DND操作中，对差分数据执行一分开操作，以便二等分属于正数区域的差分数据并转换属于上部范围的差分数据成为负值，或者根据分开操作结果，对分开操作的结果有选择地执行上分操作或者下分操作以便缩小分别属于负数区域或者正数区域的差分数据的范围。

7、如权利要求6的装置，其中，在分开操作中，如果输入的差分数据大于nKeyMax/2，则从每个输入的差分数据中减去在输入的差分数据中的最大值nKeyMax和一预定常数。

8、如权利要求6的装置，其中，在上分操作中，如果属于负数区域的差分数据的范围大于属于正数区域的差分数据的范围，并且输入的差分数据小于预定的基准值而不小于nKeyMin/2，则将输入的差分数据乘以第一常数，如果属于负数区域的差分数据的范围大于属于正数区域的差分数据的范围并且差分数据小于nKeyMin/2，则从最小值nKeyMin中减去每个输入的差分数据，该减法的结果乘以该第一常数，并且从乘积中减去第二常数。

9、如权利要求6的装置，其中，在下分操作中，如果具有正值的输入的差分数据的范围大于具有负值的输入的差分数据的范围，并且输入的差分数据中的最大值nKeyMax大于nKeyMax/2，则从每个输入的差分数据中减去最大值nKeyMax，该减法的结果乘以第一常数，并且从乘积中减去第二常数，而如果输入的差分数据小于预定的基准值，则将它们中的每个乘以第一常数。

10、如权利要求5的装置，其中，DND操作器对差分数据执行预定次数的DND操作以便输出DND操作的某一周期的结果，其中编码所需要的比特数可以最小化。

11、如权利要求5的装置，其中，如果每个差分数据都小于预定的基准值，则上移位操作器从它们中的最大值nKeyMax中减去已经过DND操作的每个差分数据。

12、如权利要求5的装置，其中，第一差分数据选择器从分别由该移位器、折叠处理器、DND操作器输入的差分数据中选择具有编码需要的最少比特的差分数据，并且输出所选择的差分数据。

13、如权利要求5的装置，其中，如果从移位器或者折叠处理器输入的差分数据被选择，则第一差分数据选择器输出所选择的差分数据到该熵编码器。

14、如权利要求5的装置，其中，第二差分数据选择器度量已经过DND操作的差分数据的分散度和已经过上移位操作的差分数据的分散度，并且输出具有低分散度的差分数据。

15、一种用于编码关键字数据的装置，其中，关键字数据是关于关键字帧在时间轴上的位置的信息，该装置包括：

量化器，用于利用量化比特量化输入的差分数据；

DPCM处理器，用于产生所量化的关键字数据的差分数据；

移位器，用于获得差分数据中具有最高频率的差分数据(模)并且从每个差分数据减去该模；

折叠处理器，用于将该差分数据转换到一正数区域或者一负数区域；

DND处理器，用于在考虑到转换的差分数据以及它们中的最大和最小值之间的关系的情况下，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，从移位器输入的差分数据、从折叠处理器输入的差分数据、已经过DND操作的差分数据、已经过上移位操作和DND操作的差分数据中选择之一，并且输出所选择的差分数据；以及

熵编码器，用于熵编码从DND处理器输入的差分数据。

16、如权利要求15的装置，其中，DND处理器包括：

DND操作器，用于对从输入的差分数据执行DND操作；

差分数据选择器，用于选择已经过移位操作的差分数据、已经过折叠操作的差分数据和已经过DND操作的差分数据其中之一，并且输出所选择的差分数据。

17、如权利要求16的装置，其中，DND操作器对输入的差分数据执行预定次数的DND操作，并且在DND操作中，对输入的差分数据执行一分开操作，以便二等分属于正数区域的差分数据并转换属于上部范围的差分数据成为负值，或者根据分开操作结果的范围，对分开操作的结果有选择地执行上分操作或者下分操作以便缩小分别属于负数区域或者正数区域的差分数据的范围。

18、一种用于编码关键字数据的装置，该关键字数据是关于时间轴上的关键字帧的位置的信息，该装置包括：

量化器，用于量化输入的差分数据为量化比特；

DPCM处理器，用于产生所量化的关键字数据的差分数据；

移位器，用于获得差分数据中具有最高频率的差分数据(模)并从每个差分数据中减去该模；

DND处理器，用于在考虑到所转换的差分数据以及它们中的最大和最小值之间的关系的情况下，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，从移位器输入的差分数据、已经过DND操作的差分数据、已经过上移位操作和DND操作的差分数据中选择之一，并且输出所选择的差分数据；以及

熵编码器，用于熵编码从DND处理器输入的差分数据。

19、一种用于编码关键字数据的装置，其中，关键字数据是关于关键字帧在时间轴上的位置的信息，该装置包括：

线性关键字编码器，用于在输入的关键字数据中识别一区域，在该区域中关键字数据线性地增加，该线性关键字编码器还用于编码线性关键字数据区域；

量化误差最小化器，用于调整输入的关键字数据中的最大和最小值以便量化误差能够被最小化，并且输出调整的最大和最小值；

量化器，用于使用从量化误差最小化器输入的最大和最小值、利用预定的量化比特量化输入的关键字数据；

浮点数换算器，用于将表示从线性关键字编码器输入的线性关键字数据区域的首尾关键字数据的二进制数以及表示从量化误差最小化器输入的最大和最小值的二进制数转换为十进制数；

DPCM处理器，用于产生所量化的关键字数据的差分数据；

移位器，用于获得一在差分数据中具有最高频率的差分数据(模)并且从每个差分数据中减去该模；

折叠处理器，用于将差分数据转换为一正数区域或者一负数区域；

DND处理器，用于对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，从移位器输入的差分数据、从折叠处理器输入的差分数据、已经过DND操作的差分数据和已经过上移位操作和DND操作的差分数据中选择之一，并且输出该所选择的差分数据；

熵编码器，用于熵编码从DND处理器输入的差分数据；以及

关键字头编码器，用于使用编码所需数据产生关键字头数据，其中该数据从线性关键字编码器量化器、浮点数换算器、DPCM处理器、移位器、折叠处理器、DND处理器以及熵编码器中至少之一输入。

20、如权利要求19的装置，其中，如果线性关键字数据区域中的关键字数据和任意关键字数据区域中的线性预测的关键字数据之间的最大误差不大于预定临界值，则线性关键字编码器判定线性关键字数据区域是互线性的。

21、如权利要求19的装置，其中，量化器使用输入的关键字数据中的最大和最小值转换输入的关键字数据为预先确定范围的值，并且利用预先确决定的量化比特量化该值。

22、如权利要求19的装置，其中，量化误差最小化器使用任意最大和最小值转换转换输入的关键字数据为预先确定范围的值，利用预定量化比特量化该值，反向地量化该量化的关键字数据，并且获得和输出能够最小化输入的关键字数据与反向地量化的关键字数据之间误差之和的最大和最小值。

23、如权利要求19的装置，其中，浮点数换算器将以mantissa_binary*2^{exponent_binary}形式表示的二进制转换到以mantissa*10^exponent形式表示的十进制数。

24、如权利要求19的装置，其中，如果从移位器输入的差分数据大于预定基准值，则折叠处理器以一第一常数乘它们，如果它们小于预定基准值，则折叠处理器以第一常数乘它们的绝对值，然后从乘积中减去一第二常数。

25、如权利要求19的装置，其中，DND处理器包括：

DND操作器，用于对从折叠处理器输入的差分数据执行DND操作；

第一差分数据选择器，用于选择已经过移位操作的差分数据、已经过折叠操作的差分数据和已经过DND操作的差分数据其中之一，并且输出所选择的差分数据；

上移位操作器，如果已经过DND操作的差分数据从第一差分数据选择器输入，则对该差分数据执行上移位操作；以及

第二差分数据选择器，用于有选择地输出已经过DND操作的差分数据或者已经过上移位操作的差分数据。

26、如权利要求25的装置，其中，DND操作器对从折叠处理器输入的差分数据执行DND操作以便缩小被编码的差分数据的范围，具体地说，在DND操作中，对差分数据执行一分开操作，以便二等分属于正数区域的差分数据并转换属于上部范围的差分数据成为负值，或者根据分开操作结果的范围，对分开操作的结果有选择地执行上分操作或者下分操作以便缩小分别属于负数区域或者正数区域的差分数据的范围。

27、如权利要求19的装置，其中，关键字头编码器接收要编码的关键字数据的数目和关键字数据的数位，从量化器接收量化比特的大小和已经用于量化的最大和最小值，从线性关键字编码器接收已经过线性关键字编码的区域上是否存在一线性关键字的信息和线性关键字数据的数目，从浮点数换算器接收线性关键字区域的首尾关键字数据，从DPCM处理器接收DPCM特性数目，即，DPCM的阶，以及DPCM每个周期中的内部关键字数据，从移位器接收模，接收DND特性数目，即，DND的阶，以及已经用于DND操作的最大和最小值，并允许全部输入包括在一关键字头中。

28、一种用于编码关键字数据的DPCM的差分数据的方法，其中，关键字数据是关于关键字帧在时间轴上的位置的信息，该方法包括：

对输入的差分数据执行预定次数的DND过程，其中，对输入的差分数据执行分开操作，以便二等分属于正数区域的差分数据并且转换属于区域上部的差分数据成为负值，或者根据分开操作结果的范围，对分开操作的结果有选择地执行上分操作或者下分操作以便缩小分别属于负数区域或者正数区域的差分数据的范围；

对DND操作的结果执行上移位操作以便转移已经过DND操作的该差分数据到或者正数或者负数区域；

选择已经过DND操作的差分数据，或者已经过上移位操作的差分数据；以及

熵解码所选择的差分数据。

29、如权利要求28的方法，其中，在差分数据的选择中，度量已经过DND操作的差分数据的分散度和已经过上移位操作的差分数据的分散度，并且选择具有较低分散度的那个差分数据。

30、一种用于编码关键字数据的DPCM的差分数据的方法，其中，关键字数据是关于关键字帧在时间轴上的位置的信息，该方法包括：

执行移位操作，其中从差分数据中获得具有最高频率的差分数据(模)，并且从每个差分数据中减去该摸；

执行折叠操作以便将已经通过该移位操作的差分数据转送到一正数区域或者一负数区域；

执行一DND过程，其中在考虑到已经通过折叠操作的差分数据和它们中的最大和最小值之间的关系的情况下，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，选择从移位器输入的差分数据、从折叠处理器输入的差分数据、已经过DND操作的差分数据、已经过上移位操作和DND操作的差分数据其中之一，并且输出所选择的差分数据；以及

熵编码所选择的差分数据。

31、如权利要求30的方法，其中，在折叠操作中，如果已经过移位操作的差分数据大于预定的基准值，则该差分数据乘以一第一常数，如果该差分数据小于该预定的基准值，则每个差分数据的绝对值乘以第一常数并且从每个乘积中减去一第二常数。

32、如权利要求30的方法，其中，执行DND过程包括：

对已经过折叠操作的差分数据执行DND操作；

首先，选择已经过移位操作的差分数据、已经过折叠操作的差分数据和已经过DND操作的差分数据其中之一；

如果已经过DND操作的差分数据被选择，则对已经过DND操作的差分数据执行上移位操作；以及

接下来，选择已经过DND操作的差分数据或者已经过上移位操作的差分数据。

33、如权利要求32的方法，其中，在DND操作中，对输入的差分数据执行一分开操作，以便二等分属于正数区域的差分数据并转换属于上部范围的差分数据成为负值，或者根据分开操作结果的范围，对分开操作的结果有选择地执行上分操作或者下分操作以便缩小分别属于负数区域或者正数区域的差分数据的范围。

34、如权利要求33的方法，其中，在分开操作中，如果输入的差分数据大于nKeyMax/2，则从每个输入的差分数据中减去输入的差分数据和预定常数中的最大值nKeyMax。

35、如权利要求28或者32的方法，其中，在上分操作中，如果具有负值的差分数据的范围大于具有正值的差分数据的范围并且输入的差分数据小于预定的基准值而不小于nKeyMin/2，则将输入的差分数据中的最小值nKeyMin乘以第一常数，如果属于负范围的差分数据的范围大于属于正数区域的差分数据的范围并且差分数据小于nKeyMin/2，则从最小值nKeyMin中减去每个输入的差分数据，减法的结果乘以第一常数，并从乘积中减去第二常数。

36、如权利要求33的方法，其中，在下分操作中，如果具有正值的输入的差分数据的范围大于具有负值的输入的差分数据的范围，并且输入的差分数据中最大值nKeyMax大于nKeyMax/2，则从每个输入的差分数据中减去最大值nKeyMax，减法的结果乘以第一常数，从乘积中减去第二常数，如果输入的差分数据小于预定的基准值，则将它们每个都乘以第一常数。

37、如权利要求32的方法，其中，DND操作执行预定的次数，当编码所需要的比特数可以最小化时，在DND预定周期中获得的差分数据作为DND操作的结果来确定。

38、如权利要求32的方法，其中，在上移位操作中，如果差分数据小于预定的基准值，则上移位操作器从它们中的最大值nKeyMax减去已经过DND操作的每个差分数据。

39、如权利要求32的方法，其中，在差分数据的第一选择中，从已经过移位操作的差分数据、已经过折叠操作的差分数据、已经过DND操作的差分数据中，选择具有编码需要的少量比特的差分数据。

40、如权利要求32的方法，其中，在差分数据的第一选择中，如果已经过移位操作或者折叠操作的差分数据被选择，则所选择的差分数据在熵编码步骤中编码。

41、如权利要求32的方法，其中，在差分数据的第二选择中，度量已经过DND操作的差分数据的分散度和已经过上移位操作的差分数据的分散度，并且选择具有较低分散度的那个差分数据。

42、一种用于编码关键字数据的方法，其中，关键字数据是关于关键字帧在时间轴上的位置的信息，该方法包括：

以量化比特来量化要编码的关键字数据；

执行DPCM过程以便产生所量化的关键字数据的差分数据；

执行移位操作，其中从差分数据中获得具有最高频率的差分数据(模)，并且从每个差分数据中减去该模；

转换该差分数据为一正数区域或者一负数区域；

执行一DND过程，其中在考虑到已经通过折叠操作的差分数据和它们中的最大和最小值之间的关系的情况下，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，选择从移位器输入的差分数据、从折叠处理器输入的差分数据、已经过DND操作的差分数据、已经过上移位操作和DND操作的差分数据其中之一，并且输出所选择的差分数据；以及

熵编码该所选择的差分数据。

43、如权利要求42的方法，其中，执行DND过程包括：

对已经过折叠操作的差分数据执行DND操作；

选择已经过移位操作的差分数据、已经过折叠操作的差分数据和已经过DND操作的差分数据其中之一。

44、一种用于在基于图形动画的键帧中编码关键字数据的方法，该关键字数据是关于关键字帧在时间轴上的位置的信息，该方法包括：

量化要编码的关键字数据为量化比特；

执行DPCM过程以便产生量化的关键字数据的差分数据；

执行移位操作，其中从差分数据中获得具有最高频率的差分数据(模)，并且从每个差分数据中减去该模；

执行一DND过程，其中在考虑到已经通过折叠操作的差分数据和它们中的最大和最小值之间的关系的情况下，对已经通过折叠的差分数据执行DND操作以便缩小它们的范围，选择从移位器输入的差分数据、从折叠处理器输入的差分数据、已经过DND操作的差分数据、已经过上移位操作和DND操作的差分数据其中之一；以及

熵编码该所选择的差分数据。

45、如权利要求43的方法，其中，在DND操作中，对差分数据执行一分开操作，以便二等分属于正数区域的差分数据并转换属于上部范围的差分数据成为负值，或者根据分开操作结果的范围，对分开操作的结果有选择地执行上分操作或下分操作以便缩小分别属于负数区域，或者正数区域的差分数据的范围。

46、一种用于在基于图形动画的键帧中编码关键字数据的方法，该关键字数据是关于关键字帧在时间轴上的位置的信息，该方法包括：

执行线性关键字编码，在其中确定并且编码关键字数据线性增加的区域；

执行浮点数换算，以便表示该线性关键字数据区域的首尾关键字数据的二进制数变为十进制数；

执行量化误差最小化，在其中调整要编码的关键字数据中的最大和最小值以便量化误差可以最小化，并且表示调整的最大和最小值的二进制数变为十进制数；

执行量化，其中要要编码的关键字数据是以预定的量化比特、使用已调整的最大和最小值量化的；

执行DPCM过程以便产生所量化的关键字数据的差分数据；

执行移位操作，其中从差分数据中获得具有最高频率的差分数据(模)，并且从每个差分数据中减去该模；

执行折叠操作，以便已经过移位操作的差分数据转入一正数区域或者一负数区域；

执行一DND过程，其中对已经过折叠操作的差分数据执行DND操作以便缩小它们的范围、并且选择已经过移位操作的差分数据、已经过折叠处理器的差分数据、已经过DND操作的差分数据、已经过上移位操作和DND操作的差分数据其中之一；

熵编码所选择的差分数据；以及

执行关键字头编码，其中在线性关键字编码、量化、浮点数换算、DPCM过程、移位操作、折叠操作、DND过程和熵编码的至少之一中产生的数据作为一关键字头产生。

47、如权利要求46的方法，在线性关键字编码中，如果线性关键字数据区域中的关键字数据和任意关键字数据区域中的线性预测的关键字数据之间的最大误差不大于预定临界值，则线性关键字编码器决定线性关键字数据区域是互线性的。

48、如权利要求46的方法，其中，在量化中，利用要被量化的关键字数据中的最大和最小值，将要被量化的关键字数据转换成为预定范围内的值，并且所转换的值以预定量化比特量化。

49、如权利要求46的方法，其中，在量化误差最小化中，利用任意最大和最小值，将要被量化的关键字数据转换成为预定的范围的值，该值以预定的量化比特量化，所量化的关键字数据被反向量化，并且获得可以最小化要量化的关键字数据和被反向量化的关键字数据之间误差之和的任意最大和最小值。

50、如权利要求46的方法，其中，在浮点数换算中，将以mantissa_binary*2^{exponent_binary}形式表示的二进制转换到以mantissa*10^exponent形式表示的十进制数。

51、如权利要求46的方法，其中，在折叠操作中，如果已经过移位操作的差分数据不小于预定的基准值，则该差分数据乘以一第一常数，如果该差分数据小于该预定的基准值，则每个差分数据的绝对值乘以第一常数并且从每个乘积中减去一第二常数。

52、如权利要求46的方法，其中，执行DND过程包括：

对已经过折叠操作的差分数据执行DND操作；

选择已经过移位操作的差分数据、已经过折叠操作的差分数据和已经过DND操作的差分数据其中之一；

如果该差分数据已经过DND操作，则选择在已经过DND操作的差分数据上执行的上移位操作；以及

选择已经过DND操作的差分数据或者已经过上移位操作的差分数据。

53、如权利要求52的方法，其中，执行预定次数的DND操作，并且在DND操作中，对差分数据执行一分开操作，以便二等分属于正数区域的差分数据并转换属于上部范围的差分数据成为负值，或者根据分开操作结果的范围，对分开操作的结果有选择地执行上分操作或者下分操作以便缩小分别属于负数区域或者正数区域的差分数据的范围。

54、如权利要求46的方法，其中，在关键字头编码中，要编码的关键字数据的数目、关键字数据的数位、量化比特的大小、已经用于量化的最大和最小值、已经过线性关键字编码的区域是否存在一线性关键字的信息、线性关键字数据的数目、线性关键字区域的首尾关键字数据、DPCM特性数目即DPCM的阶、DPCM每个周期中的内部关键字数据、模、DND特性数目即IDND的阶以及已经用于DND的最大和最小值中的至少之一被包括在关键字头中。

Images