著录项信息
专利名称 | 生成与读出可变长度代码字数据流的方法和设备 |
申请号 | CN00805534.3 | 申请日期 | 2000-01-17 |
法律状态 | 权利终止 | 申报国家 | 中国 |
公开/公告日 | 2002-04-17 | 公开/公告号 | CN1345484 |
优先权 | 暂无 | 优先权号 | 暂无 |
主分类号 | H03M7/40 | IPC分类号 | H;0;3;M;7;/;4;0;;;H;0;4;B;1;/;6;6查看分类表>
|
申请人 | 弗兰霍菲尔运输应用研究公司 | 申请人地址 | 德国慕尼黑
变更
专利地址、主体等相关变化,请及时变更,防止失效 |
权利人 | 弗劳恩霍夫应用研究促进协会 | 当前权利人 | 弗劳恩霍夫应用研究促进协会 |
发明人 | 拉尔夫·斯伯奇内德;马丁·迪尔兹;皮埃尔·劳伯;米歇尔·舒格 |
代理机构 | 中国国际贸易促进委员会专利商标事务所 | 代理人 | 冯赓宣 |
摘要
本发明涉及从被分成多个代码字集的可变长度代码字生成数据流的方法,其中为该数据流确定一个包含多个节的栅格,其中两个相邻的栅格点(41,42)定义一个节(40)。第一集的代码字(1-6)从这些栅格点开始被写入该数据流。接着,第二集的代码字依照一个预定的分配规则被写入该数据流,其中第二集的每个代码字被分配到一个不同的节。不能根据其分配被写入的完整的代码字或代码字的部分被储存起来并在后面的写入尝试中被送入该数据流,其中对按照预定规则进行的分配,每一次尝试都是变化的。对于任何接下来会出现的集,该过程被类似地重复进行。这样,第二集的代码字的终点就与后接的第二集的代码字的起点分开,因为一个集的相应的代码字是逐节写入的。这就减小了差错扩散。
1.一种用于生成一个可变长度代码字数据流的方法,其中该数 据流被分成多个代码字集,一个具有用于该数据流的多个栅格点的栅 格,两个相邻的栅格点(41,42)定义一个节(40),并且该栅格含 有多个节,该方法包括以下步骤:
a1)写入(16)第一集的代码字(1-6)使得代码字的起点位于 不同节的栅格点上;
b1)如果各代码字适合于各节,把第二集的每个代码字(7-12) 写入(18)依照一个预定的分配规则分配给各个代码字的节中,其中 由于该预定的分配规则,第二集的每个代码字被分配给不同的节;
b2)如果仅各代码字(7)的一部分(7a)适合于所分配的节, 或者把第二集的各代码字(7)的该部分(7a)写入所分配的节(1) 并把代码字(7)的余下部分(7b)储存起来,或者,如果所分配的节 是满的,则把被分配给该满节的整个代码字(13)储存起来;
b3)依照第二个预定规则,把在步骤b1)、b2)中不适合于各 自的节的所储存的余下部分(7b)或者所储存的整个代码字(13)写 入在步骤b1)与b2)之后未在上面写入信息的栅格的一个区,直至第 二集的所有的代码字被写入该栅格为止。
2.如权利要求1所要求的方法,在该方法中,第一集的代码字 按照一个顺序出现,其中这些代码字被按照它们的顺序写入相邻的节 中。
3.如权利要求1所要求的方法,如果第一集的一个代码字比一 个节长,依照第一个预定规则,把代码字的余下部分写入该栅格的在 步骤a1)之后未在上面写信息的一个区,直至第一集的所有代码字均 被写入该栅格为止,第一个预定规则如下:
i)把第一集的一个代码字的余下部分的至少一部分写入跟随在其 中出现该代码字的起始段的节的后面的节中,如果在该节中存在供该 余下部分的至少一部分使用的空间的话,并且
ii)如果这样的代码字存在的话,对第一集的所有其他代码字的 余下部分执行步骤(i);并且
iii)执行步骤(i)、(ii),其中对于每个余下部分一个余下部 分用一个节执行,直至第一集的所有代码字均被写入该数据流(31) 为止。
4.如权利要求1所要求的方法,在该方法中,第二集的代码字 按照一个顺序出现,并且预定的分配规则把第二集的第一个代码字分 配给第一集的第一个代码字的起点所在的节,把第二集的第二个代码 字分配给第一集的第二个代码字的起点所在的节并且,如果存在的话, 把第一集的每个其他的代码字分配给其第一集的相对应的代码字起点 所在的节。
5.如权利要求1所要求的方法,其中的第二个预定规则等同于 第一个预定规则。
6.如权利要求1所要求的方法,其中,依照第一或第二个预定 规则,如果在紧随于所分配的仍然留有余下部分的节的后面的各节中 仅有这么多空间的话,不能完全装入所分配给的节的相应的集的一个 代码字要分成三个或三个以上的部分。
7.如权利要求1所要求的方法,其中的栅格点被等间隔分开, 以此获得除最后一个节之外的等长节,其中的等长节要长于或等长于 第一个集的最长的代码字,以使第一集的每个代码字适合于相应的节。
8.如权利要求1所要求的方法,其中第一集的代码字以第一写 方向分别从各节的第一个栅格点开始写入,而其中第二集的代码字以 与第一写方向相反的第二写方向分别从各节的第二个栅格点开始写 入。
9.如权利要求8所要求的方法,其中存在代码字的第三集,其 中在第二集的所有代码字写入该栅格后,第三集的代码字再以第一写 入方向写入该栅格。
10.如权利要求1所要求的方法,其中的代码字是霍夫曼代码字。
11.如权利要求1所要求的方法,其中的代码字代表信息符号, 而其中第一集的代码字代表比第二集的或者此外的其他集的代码字更 重要的信息符号。
12.如权利要求11中要求的方法,其中的信息符号是一个音频 信号的频谱值,而第一集的代码字是从心理听觉的观点来看更为重要 的频谱值,其受到保护以免于由于数据流中的一个传输差错而引起的 任何差错的扩散。
13.如权利要求1所要求的方法,其中所形成的数据流的长度等 于可变长度代码字的长度之和。
14.如权利要求1所要求的方法,其中存在两个以上的代码字集, 该方法还包括以下步骤:
对代码字的其他更多的集的代码字执行步骤b1)、b2)和b3), 其中的第二个预定规则与步骤b2)的第二个预定规则对应,并且其中 该预定分配规则与步骤b1)的预定分配规则相对应。
15.如权利要求1所要求的方法,其中,如果第一集的一个代码 字长于一个节,则依照第一个预定规则把该代码字的余下部分写入该 栅格的在步骤a1)之后未在上面写信息的一个区,直至第一集的所有 代码字均被写入该栅格为止。
16.一种用于读取一个可变长度代码字数据流的方法,其中数据 流包括多个代码字集的代码字,其中一个栅格被指定用于该数据流 (38),该栅格包括栅格点(41,42),其中两个相邻的栅格点(41, 42)定义一个节(40),其中该数据流包括至少两个节,该方法包括 以下步骤:
a)通过以下各步骤从数据流(38)提取第一集的代码字:
a1)对于每个节,跳至一个栅格点并读取在那里开始的一个 代码字;
b)通过以下各步骤从在步骤(a)之后留下的数据流(50) 中提取第二个代码字集的代码字:
b1)对于每个余下的节,根据在形成该数据流时使用一个预 定的分配规则跳至该节的一个栅格点,并读取在那里开始的代码字, 以便获得第二集的代码字;
b2)如果第二集的一个代码字在一个相应的节的终点并未结 束,把读取的第二集的该代码字的段储存起来;
b3)根据在形成该数据流时使用的第二个预定规则,确定该 代码字的余下部分或者在一个栅格点未出现的代码字。
17.如权利要求16所要求的方法,其中的数据流包括多个两个 集的代码字,该方法还包括以下步骤:
通过重复步骤b1)、b2)和b3)来提取第三集的代码字,其中 第二预定规则等同于步骤b3)的第二预定规则,并且其中的分配规则 等同于步骤1)的分配规则。
18.如权利要求16所要求的方法,其中在形成数据流时所使用 的分配规则把第二集的第一个代码字分配给在其中第一集的第一个代 码字开始的一个节,其中,在步骤b1),解码器跳至第一个栅格点(41) 以获取第二集的第一个代码字,解码器跳至第二个栅格点(42)以获 取第二集的第二个代码字,以此类推,其中,如果没有或者只有第二 集的一个代码字的一部分在第一栅格点(41)开始,在根据第二预定 规则确定一个丢失了的代码字或者一个代码字的一个丢失了的部分之 前,解码器一开始从所有的栅格点开始读取。
19.如权利要求16所要求的方法,其中如果从一个栅格点开始 的第一集的一个代码字在该节的终点并未结束,把该代码字的已读取 的段储存起来,并且根据在形成该数据流时使用的第一个预定规则确 定该代码字的余下部分,第一个预定规则如下:
对于一个读取的代码字的每个存储段,跳至在步骤a1)之后余留 的数据流中的下一个栅格点,以确定该代码字的余下部分;
如果一个代码字能被读至终点,把已被读至终点的该代码字与所 储存的段连接起来,以完整地获得第一集的代码字,否则,则储存已 被读取的一个段并重复跳至下一个栅格点的步骤,直至第一集所有的 代码字出现。
20.如权利要求16所要求的方法,其中在第一个代码字集中存 在的代码字与在该数据流中存在的节一样多,而且其中在其他的一个 集或多个集中的代码字的数量等于或小于第一集中的代码字的数量, 以使第一集中所有的代码字均被写至栅格点。
21.如权利要求16所要求的方法,其中如果在一个栅格点开始 的第一集的一个代码字未能在该节的终点结束,把该代码字的所读取 的段储存起来,根据在形成该数据流时使用的第一预定规则确定该代 码字的余下部分。
22.一种用于生成可变长度代码字的数据流的设备(10),该数 据流被分成多个代码字集,其中存在一个具有用于该数据流的多个栅 格点的栅格,其中两个相邻的栅格点(41,42)定义一个节(40), 该栅格包括多个节,该设备包括:
a)用于写入第一集的代码字(1-6)以使各代码字的起点在各 不同节的栅格点的设备(16);
b)用于把第二集的每个代码字写入按照一个预定的分配规则被 分配每个单个代码字的一个节中的装置(18),其中如果相应的代码 字适合于该节的话,第二集的每个代码字依照该预定的分配规则被分 配给一个不同的节,其中装置(18)是这样配置的:
如果相应的代码字只有一部分适合于所分配的节,则把第二集的 该相应的代码字(7)的该部分(7a)写入所分配的节(1)并储存该 代码字的余下部分(7b)或者,如果所分配的节是满的,则把分配给 该满节的整个代码字(13)储存起来;
把在步骤b1)、b2)中不适合于相应的节的所存的余下部分(7b) 和所存的整个代码字(13)按照第二预定规则写入该栅格的在步骤b1) 和b2)之后未在上面写信息的一个区,直至第二集的所有代码字均被 写入该栅格为止。
23.如权利要求22所要求的设备,其中用于写入第一集的代码 字的设备是可操作的,如果一个代码字长于一个节,则依照第一个预 定规则把该代码字的余下部分写入该栅格的在步骤a1)之后未在上面 写信息的一个区,直至第一集的所有代码字均被写入该栅格为止。
24.一种用于读取一个可变长度代码字数据流的设备(22),其 中该数据流包括多个代码字集的代码字,其中为该数据流(38)指定 一个包括栅格点(41,42)的栅格,其中两个相邻的栅格点(41,42) 定义一个节(40),其中该数据流至少包括两个节,该设备包括:
a)用于从数据流(38)提取第一集的代码字的一个装置(28), 该装置被如此配置使之:
对于每个节,跳至一个栅格点并在那里开始读取一个代码字;和
b)用于从在步骤a)之后余下的数据流(50)中提取第二代码字 集的代码字的一个装置(30),该装置被如此配置使之:
对于每个余下的节,根据在形成该数据流时使用的一个预定的分 配规则跳至该节的一个栅格点,并读取在那里开始的代码字,以便获 得第二节的代码字,
如果第二集的一个代码字未能在一个相应的节的终点结束,则把 第二集的该代码字的所读取的段储存起来;
根据在形成该数据流时使用的第二预定规则确定该代码字的余 下部分或未在一个栅格点出现的该代码字。
25.如权利要求24所要求的设备,其中用于提取第一集的代码 字的设备是可操作的,如果在一个栅格点开始的代码字未能在该节的 终点结束,把该代码字的所读取的段储存起来,并且根据在形成该数 据流时使用的第一预定规则确定该代码字的余下部分。
本发明涉及用可变长度代码字进行的编码,具体地说,是涉及生 成与读取传输中抗差错能力强的具有可变长度代码字的数据流。\n例如,按照MPEG层3标准工作的现代音频编码或解码方法能 够对音频信号的数据率压缩例如因数12,而不会使其质量明显下降。 为实现这种高数据率的缩减,对一个音频信号进行采样,以获得一个 时间离散的采样值序列。如业内所知的,对该时间离散的采样值序列 取一窗口以便获得有界的时间采样值组。然后,一个时间窗采样值组 通过滤波器组(filter bank)、修正余弦离散变换(MDCT)或其他适 合的设备被转换成频率范围,以便获得整体上表示音频信号的频谱值, 即在该频率范围内由时间离散的采样值组确定的时间段。通常,通过 MDCT生成相互间重迭50%的时间组值,并且该时间值组被转换成频 率范围,由于MDCT的特性,例如1024个时间离散的采样值总是产 生1024个频谱值。\n众所周知,人的听力取决于音频信号本身的瞬间频谱。这种依赖 性属于所谓的心理听觉模式,通过该模式,在相当长的时间里依据该 瞬间频谱对掩蔽阈值进行计算一直是可行的。掩蔽(masking)意指在 例如相邻的频谱范围,具有相对较高的能量的情况下,一个特定的单 音或一个频谱分量被掩蔽起来。为了尽可能接近地量化转换之后出现 的频谱值,掩蔽的这一作法得到了应用。因此该目的一方面在于避免 重新编码的音频信号中的可听见的干扰,另一方面在于使用尽可能少 的位来编码或者,在这一情况下,来量化音频信号。由量化引起的干 扰,即量化噪声,应当低于掩蔽阈值,因此,是听不见的。根据已知 的方法,对所谓的比例系数频带(scale factor bands)中的频谱值进 行分类,这种分类应与人耳的临界频带,即频率组相符。一个比例系 数组中的频谱值乘以一个比例系数以便对一个比例系数频带中的频谱 值进行整体换算。经比例系数换算的比例系数频带则被量化,以此生 成经过量化的频谱值。可以理解,比例系数频带的分组并非关键性的。 然而,它却在MPEG层3标准或者在MPEG 2AAC标准(AAC=先 进音频编码)中得到应用。\n数据缩减的一个根本的方面在于量化之后的平均信息量编码。 Huffman(霍夫曼)编码通常用于平均信息量编码。Huffman编码被 理解为它意味着用一个可变长度来进行编码,即被编码的值的代码字 的长度取决于它出现的概率。从逻辑上讲,概率最大的字符被分配给 最短的代码,即最短的代码字,以便通过Huffman编码实现良好的冗 余缩减。一个公知的用一般长度进行编码的例子是Morse代码。\n在音频编码领域,Huffman代码用于对经过量化的频谱值进行编 码。现代的音频编码器,例如根据MPEG 2AAC标准工作的编码器, 使用不同的Huffman代码表对量化的频谱值进行编码,而该代码表是 以逐段进行为基础按照某些条件分配给该频谱的。在这一过程中,总 是把2个或4个频谱值一起编码于一个代码字中。\n根据MPEG 2AAC的方法与根据MPEG层3的方法之间的一个 差别是不同的比例系数频带,即不同的频谱值,被分组归入任意数量 的频谱段。对于AAC,一个频谱段包括至少4个频谱值,但最好是多 于4个频谱值。这些频谱值的整个频率范围因此而被分成相临的频段, 一个频段表示一个频带,这样,所有的频段就共同覆盖了由经转换后 的频谱值合成的整个频率范围。\n比如在MPEG层3方法中,一个频段被分配给一个选自多个这 种表格的所谓的“Huffman表”,以便实现最大的冗余缩减。在AAC 方法的通常含有1024个频谱值的位流中,现在是按照频率的上升顺序 排列的频谱值的Huffman代码字。每个频段中使用的表上的信息以从 属信息的形式传送。这种情形在图6中示出。\n图6示出了位流包括10个Huffman代码字的示例。在一个代码 字总是由一个频谱值形成的情况下,这里就可以对10个频谱值进行编 码。然而,通常总是2个或4个频谱值用一个代码字共同编码,这就 是图6示出包括20或40个频谱值的一部分编码位流的原因。在每个 Huffman代码字包括2个频谱值的情况下,数字1标定的代码字表示 前2个频谱值,第一个代码字的长度比较短,这意味着前两个频谱值 的值,即两个最小的频率系数,出现的比较频繁。而带有数字2的代 码字却有较长的长度,这意味着已编码的音频信号中第3和第4个频 谱系数的量值较少,这就是它们被用一个较多的位来编码的原因。还 有,从图6中可以清晰地看出,具有数字3、4和5的代码字也出现得 较频繁,因为各代码字的长度较小,数字3、4和5表示频谱系数5与 6或7与8或9与10。同样的分析合适于带有数字6至10的代码字。\n正如已经提到的,从图6中显然可以清晰地看出,在考虑用已知 的编码设备生成位流的情况下,用于对频谱值编码的Huffman代码字 以与频率相关的线性增长方式被安排在位流中。\n在信道出现故障的情况下,Huffman代码的一个主要的缺陷是差 错的扩散。例如,可以假定图6中的第二个代码字受到干扰。存在某 一个不低的概率,即该差错的第二个代码字的长度也会被改变。因此 它就不同于正确的长度。如果,在图6的例子中,第二个代码字的长 度由于一个干扰而被改变,对于一个编码器而言就不再可能确定代码 字3至10的起点,即所表示的几乎整个音频信号的起点。这就意味着 跟随在已被干扰的代码字后面的所有其他代码字就不能再被正确编 码,因为不知道这些代码字从哪里开始,并且因为由于该差错而选择 了一个不正确的起点。\n作为对该差错扩散问题的一个解决方法,欧洲专利0612156号建 议将可变长度的代码字的一部分安排在一个栅格(raster)中,并把余 下的代码字分散于余下的空隙中,以便安排在一个栅格点(raster point) 的一个代码字的起点能在不进行全面解码的情况下或者在不正确传输 的情况下更容易找到。\n确实,该已知的方法通过重新安排代码字的方式对差错的扩散提 供了一些补救。对于某些代码字而言,在位流中确定一个固定位置, 余下的空隙供余下的代码字使用。这并不耗费任何附加的位,却能防 止在出现差错的情况下差错在重新安排的代码字之间扩散。\n然而,该已知方法的效率上的一个决定性的参数取决于在实际应 用中确定栅格的方式,即必须使用多少个栅格点,以及该栅格所必须 具有的间隔等除了使用一个栅格来抑制差错扩散的一般性建议之外, 欧洲专利0612156号并未给出有关如何有效地设计该栅格以便一方面 能够进行耐差错的编码另一方面又能够高效编码的任何更为详细的信 息。\n在本申请提交日之后发布的德国1947119.631号专利申请建议, 不是把任何代码字都定位于栅格点上,而是把那些从心里听觉 (psycho-acoustic)的角度来看具有特殊意义的代码字,即那些能够 对音频信号起重要作用频率值的代码字定位于栅格点上。在图5中示 出了由这样的一个编码器生成的一个具有可变长度代码字的数据流。 和图6中一样,该数据流也包括10个代码字,画影线的为具有优先权 的代码字。第一优先权代码字被定位于在第一栅格点100开始,第二 个优先权代码字被定位于在第二个栅格点101开始,第三个优先权代 码字被定位于在第三个栅格点102开始,第四个优先权代码字被定位 于在第四个栅格点103开始而第五个优先权代码字被定位于在第五个 栅格点104开始。第一节(segment)105由栅格点100和101定义。 以同样的方式,对第二节106,第三节107,第四节108以及最后一节 109进行定义。图5中示出,前两节105和106的长度与107和108 两节的长度不同,而且还与最后一节109的长度不同。可以说,无优 先权的代码字6,7,8,9与10则在优先权代码字之后被插入该数据 流中,以使数据流被填满。如图5中所示,在该后公布的方法中,无 优先权的代码字接在被写入的优先权代了之后被连续插入该栅格中。 具体地讲,无优先权的第6个代码字跟在无优先权代码字1的后面被 写入。105节中剩下的空隔被后随的无优先权代码字7填入,而无优 先权代码字7的剩余部分即7b,则紧随在优先权代码字3的后面被写 入下一空隔即107节中。无优先权代码字8至10执行同样的过程。\n在图5中示出的该后公布的方法的优点是优先权代码字1至5受 到保护而免于差错扩散的影响,因为它们的起点与栅格点重合并因此 而被知晓。\n例如,如果优先权代码字2在传输中受到破坏,则在图6中所示 的现有技术中很可能解码器将不能对余下的任何代码字3至10正确地 进行解码。然而在图5所示的方法中,下一个代码字,即优先权代码 字3,在栅格点102开始,这样,该解码器总会找到代码字3的正确 起点。因此,在图5所示的方法中,不会有什么系列差错出现,而只 是优先权代码字2将被破坏。因此,该方法对定位于栅格点的优先权 代码提供了有效的保护。\n然而,对于无优先权代码字没有有效的保护。参见图5,破坏无 优先权代码字6,以至解码器把短了一位的一个代码字设想为不正确 的代码字6,这将导致不再能够正确地对代码字7进行解码,因为正 确的代码字6的最后一位被解释为下一个代码字7的开始。因此,代 码字6中的一个差错将导致由于序列差错而非常可能不再能够对跟随 在它后面的任何代码字进行正确解码,即使它们并未受到传输差错的 影响。\n美国5579430号专利公开了一种用于数字编码的方法,在该方法 中将被写入一个位流的众代码字是这样被安排在该位流中的,即代码字的 一部分一开始就被安排在一个栅格中。这样,在该段代码字中就不会出现 差错扩散。余下的代码字被分散于余下的间隔中。\n本发明的目的是找出一种写入与读出可变长度代码字数据流的 基本原理,以提供防止由于不理想的数据流传输而引起的序列差错的 具体保护方法。\n通过根据权利要求1的生成一个数据流的方法,及通过根据权利 要求15的读出一个数据流的方法,并通过根据权利要求20的生成一 个数据流的设备以及根据权利要求21的读出一个数据流的设备,该目 的得以实现。\n本发明的是基于认识到具有可变长度代码字的一个数据流必须 如此配置使得于该数据流中的连续的代码字必须被尽快分开以使解码 器不会由于一个传输差错而生成数量非常大的序列差错。为此,将被 传输的可变长度的代码字被分成多个集(set)。第一个集可以包括优 先权代码字,而第二个集可以包括无优先权代码字。为了也对无优先 权代码字提供保护使之免受传输差错的破坏,它们不能像在现有技术 中那样被简单地写入未被占用的栅格,而是要被分散于各分立的节中。 在对接收器进行已知的固定的分配之后,无优先权代码字被如此地分 配到各节,以致每个无优先权代码字即来自第二个集的每个代码字被 分配到该数据流的一个不同的节。为使这一做法奏效,每个集只能具 有与供该数据流使用的节的数量相同的代码字。因此,第一集的代码 字被写入栅格,使第一集的每个代码字从一个栅格点开始。然后进行 尝试,把第二个集的每个代码字如此地写入数据流,使第二个集的每 个代码字被分配到一个不同的节。由于这种分配,即第二个集的每个 代码字被写入一个不同的节,解码器将不再仅连续地对第二个集的代 码字进行解码,而是转至在该栅格中为第二个集的每个代码字设置的 相应的节以便从该节中提取第二个集的相应的代码字。\n如果,第一个集的代码字已被写入一个节之后,该节已满到只有 部分空间可供分配给该节的第二集的代码字使用或者根本就没有空间 了,则仍有空间的第二集的代码字的那部分被写入所分配的该节,余 下部分被储存起来。如果对该代码字已完全没有空间,则该代码字被 整个地储存起来,直至第二集的每个代码字的分配已被尝试。只有当 此时才进行第二次尝试,把第二个集的被储存的部分的或被储存的完 整的代码字按照预定的规则写入仍未被占用的节的部分中。\n在栅格的配置使第一个集的代码字中有比该节的长度要长的代 码字的情况下,可以尽早地采用相同的方法来写入第一个集的代码字。\n一旦一个解码器从数据流中提取了从栅格点开始的第一个集的 代码字,它将继续提取第二个集的代码字。在解码器只找到第二集代 码字的一部分的代码字的情况下,该部分将被存储起来而该处理则继 续在一个不同的节中寻找第二集的下一个代码字。仅在所有的节均在 这种第一次尝试中被搜索之后,第二个集的一个代码字的缺失部分将 在第二次或以后尝试中被确定,或者其所分配的节已被第一集的代码 字占用的第二集的一个代码字被确定。\n参见图5,代码字6中的一个差错将因此而不再会导致代码字7 中的一个差错,因为代码字7会在一个与节105不同的节中开始,而 且代码字6的后面将是一个完全不同的不与其相邻的代码字。\n为了进一步地说明,可以使用一个简单的例子。该例子是基于假 设存在第一集的两个代码字和第二集的两个代码字,也就是说总共四 个可变长度的代码字。为了与现有技术比较,进一步假定代码字1与 3加在一起的长度足以填入第一个节,而代码字2与4加在一起的长 度,足够完全填入第二个节。在这种情况下,根据现有技术的一个设 备与根据本发明的一个设备一样对相同的数据进行写操作。根据现有 技术的设备首先会把优先权代码字1与2写入两个栅格点,然后在代 码字1的后面写入代码字3并把代码字4写入栅格中未被占用的下一 个空隔,也就是说写在代码字2的后面。纯粹是巧合,代码字4因此 而不再(至少是部分地)位于第一节中,而是完全位于第二节中。\n根据本发明的一个设备一开始将把第一集的代码字写至相应的 栅格点并且然后将把第二集的第一个代码字写入第一节中并把第二集 的第二个代码字写入第二节中,而无论在第一节中是否仍有空间。根 据该发明的该设备无论如何都要因此而尝试把第二集的每个代码字写 入不同的节中。\n即使由于巧合两个数据流看起来相同,对于将从该数据流中提取 可变长度代码字以便根据解码器要求的顺序安放它们的接收器而言仍 将出现明显的差别。在现有技术中,一个用于提取的设备一开始将读 出第一个栅格点的代码字1和第二个栅格点的代码字2,以便获得第 一集的代码字。然后,根据现有技术的一个设备将转至余下的数据流 的开端并在那里读取代码字3,并接着读取代码字4。\n根据本发明的一个设备,在读取第一集的代码字1与2之后,也 将转至余下的数据流的开始端并在那里读取代码字3。然而,根据该 发明的设备将在此后跳至下一节以便读取第四个代码字的开始端,即 第二集的第二个代码字。\n下面,将假设第三个代码字,即在假定的数据流中将被写在第一 集的第一个代码字后面的第二集的第一个代码字,已经受到干扰,以 致解码器将把这同一个代码字理解为比其实际长度要短的一个代码 字。在这种情况下用于读取数据流的该已知设备将读取第三个代码字 并将由于该传输差错而非常快地停止并判定实际上属于第三个代码字 的余下的一位或多位是第四个代码字的开始端。然而,根据本发明的 设备将跳至在第三个代码字被终止后的下一节,并将因此而正确地确 定第四个代码字的开端。\n通过使用这一简单的例子,从中可以清楚地看出本发明的最重要 的优点,即由于把第二集的代码字分到独立的节,而在第二集的代码 字,比如说也可以是无优先权代码字中防止序列差错。然而,在现有 技术中,正如参照图5所描述的,即使由现有技术以及由本发明生成 的可变长度代码字的数据流由于巧合而可能是相同的,序列差错也会 出现。\n下面将参照附图对本发明的优选实施例进行详细解释,其中:\n图1示出了所发明的用于生成一个可变长度代码字数据流的设 备;\n图2示出了所发明的用于读取具有可变长度代码字的数据流的设 备;\n图3通过可变长度代码字的三个集示出了所发明的方法的一个程 序图;\n图4示出了用于说明所发明的读取根据图3生成的一个数据流的 方法的一个程序图;\n图5示出了由一个已知设备生成的并且其中的优先权代码字受到 差错扩散影响的一个数据流;\n图6示出了已在其中按照优先权代码字与无优先权代码字进行分 类的一个数据流。\n在对图1进行更为详细的描述之前,应该注意,在技术上对于可 变长度代码字的编码也称作平均信息量编码。平均信息量编码的一个 典型例子是所谓的Huffman编码。原则上,在Huffman编码中,对 被编码的信息符号进行统计分析以便确定用于比不大频繁出现的信息 符号更频繁出现的信号符号的较短的代码字。在一个完整的Huffman 代码中,所有的代码字均终止于一棵代码树的端点或分枝。例如,一 个Huffman解码器连续地读入一个具有Huffman代码字的数据流, 并通过图解的方法,跳至具有它额外读入的每一位的该指定的代码树 的一个分枝,在经过一定数量的跳转,即与该代码字的位数亦即该代 码字的长度相对应的数量的跳转之后,它到达不再具有进一步分枝的、 并因此而是一个代码字的一个枝端。该解码器于是获知一个新的代码 字从下一位开始。每有要求,该处理即重复一次,直至该数据流被完 全读入为止。每次当Huffman编码器跳回起始点,即该树的根部时, 一个代码字即在其始点出现。由于代码字的长度是由代码字自身或由 编码器及解码器中已知的代码树默定的,可以看出,数据流中导致一 个位错位的一个干扰会在代码树中对解码器产生误导,可以说这将使 解码器结束于一个不同的代码字,即可能具有与正确的代码字不同长 度的一个错误的代码字。在这种情况下,一旦到达错误的代码字,解 码器将向回跳转,而且由于后随的位,再次从代码树中的一个分枝点 向另一个分枝点运动。然而,对于该解码器而言,避免序列差错是不 可能的,除非其巧合地结束于“正确的跟踪目标”。\n因此,差错防护,比如由本发明提供的差错防护,必须进行,以 保证耐差错的传输。因此,可以说,根据本发明的用于生成一个可变 长度代码字数据流的设备可以作为Huffman编码器的发送或输出级, 而用于读取可变长度代码字数据流的设备则可以作为Huffman编码器 的接收或输入级。由此可以看出,本发明不仅适用于Huffman编码器, 而且也适用于易于出现序列差错的具有可变长度代码字的任何代码。\n图1示出了一个所发明的用于生成一个可变长度代码字数据流的 设备10,该设备具有一个输入端口和一个输出端14。在输入端12, 可变长度代码字生成,而在输出端14,耐差错的数据流被输出。最好 设备10的输入端12处的可变长度代码字事先已进行了预分类,使得 优先权代码字处于第一集,较不重要的代码字处于第二集而更不重要 的代码字处于第三集,等等。\n该可变长度代码字被输入到用于把第一集的代码字写入数据流 的一个设备16中,这就使第一集的代码字各自从栅格点开始。\n此外,该可变长度代码字被输入到用于把第二集的代码字写入数 据流的一个设备18中,并为第二集的每个代码字分配一个不同的节。 因此,在两个设备16与18之间的数据流中,只有第一集的所有代码 字被送至栅格点。在可变长度代码字仅由两个集的代码字组成的情况 下,则耐差错的数据流已经出现在设备18的输出端。在存在多于两个 集的可变长度代码字的情况下,还有用于把相应集的代码字写入数据 流的其他设备,用标号20以符号形式示出。\n图2示出了所发明的用于读取在输出端14(图1)输出的耐差错 数据流的一个设备22,其具有一个输入端24和一个输出端26。在输 入端24输入耐差错的数据流,以便在输出端26输出其顺序与在输入 端12(图1)形成的顺序相对应的可变长度代码字。用于读取数据流 的设备22包括用于通过跳至栅格点的方式提取第一集的代码字的一 个设备28,用于通过跳至余下的数据流的栅格点的方式提取第二集的 代码字的一个下游设备30以及,如果必要,用于提取和其他的集一致 的代码字的其他设备32,如果存在这样的集的话。\n在以图3为基础,通过一个例子对由设备10(图1)实现的方法 进行详细解释之前,首先将给出该方法的概要。可用的代码字被分成 多个集。除了最后一个之外,每个集包括与所存在的可用的节一样多 的代码字。在最佳的情况下,一个集含有与所存在的可用的节一样多 的代码字。然而,一个集也可以含有更多或者更少的代码字,正如对 于最后一个集而言几乎必将是这种情况,因为可变长度代码字的预定 数量必须假定。如果存在M个节而且如果一个集有N个代码字,则被 写至栅格点的代码字的数量与M和N中的最小者一致,而在根据该发 明的栅格中存放该N个代码字的尝试的次数则与M和N中的最大者 一致。\n最好是,第一集有最重要的代码字,即表示与其他的信息符号相 比更为重要的信息符号的优先权代码字。接下来的集中含有按照由一 个预选算法提供的顺序排列的较不重要的代码字,最好是该算法还对 优先权代码字和无优先权代码字进行分类。这些集由设备10连续地写 入。写入一个集需要几次尝试。在第一次尝试中,当前集的第一个代 码字被写入第一节,以此类推,直至当前集的最后一个代码字被写入 最后一个节为止。当然,一个代码字可以按照某一确定的规则从第二 个,从第三个或从任何其他的节开始继而写入每个节中。\n如果一个代码字不能填入一个节,该代码字的余下部分则被储存 起来。在第二次尝试中,第一个代码字的余下部分,如果存在的话, 则被优先写入第二个节,以此类推,直至最后一个代码字的余下部分 被优先地写入第一个节。这样的一种算法还被称为模数位移(modulo shift)。显然,在下一轮,即下一次尝试中,有关一个代码字的余下部 分是写入后随的第一个节还是后随的第三个节的预定规则是可以任选 的。\n一旦一个集被全部写入,就开始写下一个集。为了防止扩散差错, 还要根据该发明的一个优选实施例,改变在一个节内的集与集之间的 写操作方向。例如,第一集的代码字从左向右写,而第二集的代码字 从右向左写,等等。因此,通过本发明,也可以说,根据该优选的实 施例,一个栅格点的第二侧端被用于绝对的差错防护。\n上面简要概述的系统应用能够非常有力地降低对一个特定代码字 的差错扩散概率的值。随着集被连续写入以及随着一个集的每个代码 字被赋分配到一个特定的节并被写入该节,如果在该节中仍有空间, 那么没有差错从一个集中的一个代码字向该集中的下一个代码字扩散 就是可能的,因为一个解码器在解码时总是从一个节跳至一个节而且 并不认为一个代码字的开端位于前一个代码字结束的地方,在现有技 术中的事实就是如此。如果由于可用的空间不足以完整送入一个代码 字该代码字只是部分地被写入该节中,则至少差错扩散的可能性降低 了。\n根据本发明的一个优选实施例,节宽的选择使优先权代码字完全 填入这些节。因此,写第一集只需要一次尝试。然而,这是任意的。 通常,由于目的在于大量的栅格点用于一个数据流,即一个节长要尽 可能的小,第一集的代码字要长于该节长的情况也可以出现。然而, 这种情况会像写第二个集一样对待,即,也按照一个必须为编码器以 及为解码器所知的预定规则。\n图3通过一个例子解释了所发明的用于写入可变长度代码字的方 法。在该例中,有15个可变长度代码字30,被事先分成具有6个代 码字1至6的第一集,也有6个代码字7至12的第二集以及具有余下 的3个代码字13至15的第三集。如图3中所示,代码字30具有可变 长度。\n根据本发明的一个优选实施例,节长,即该节的长度,要长于第 一集的最长的代码字的长度。第一集的代码字被安置于栅格点41至 46,其中,对于最后的一个节6,一个未被使用的栅格点由一条点划 线指明,然而,由于该数据流的端点47可以说也能被认为是一个栅格 点,于是由一条点划线指明的该栅格点就是多余的了。第一节6因此 而长于其他节,然而这与本发明完全无关。一般来讲,节可以有在数 据流内变化的任意长度,因为可以理解,一个节的当前长度必须为解 码器所知,以便该发明的优点能够得到利用。\n首先,第一集的代码字在步骤a)中被写入数据流,这将形成由31 标明的不连贯的数据流,其中第一集的代码字如在整个图3中表示写 操作的方向的箭头48所指明的那样,从左向右被写入各自相应的节 中。由于选择的节长长于第一集的代码字的最大长度,在步骤a)中只 要一次尝试。如果节较短,则相应地要求较多的尝试。\n现在在步骤b)中把第二集的代码字写入数据流31。为了实现高耐 差错,第二集的代码字最好不要像第一集的代码字那样从左向右写, 而是如由写方向的相应箭头指明的那样,相应地从第二个栅格点,例 如第一个节的栅格点42开始从右向左写。第二集的代码字的写入要按 照一个预定的分配法则进行,比如说在选定的例子中,第二集的第一 个代码字将被写入第一集的第一个代码字的同一个节中,然而,总是 要以在该节中仍有空间为条件。从第一次尝试中形成的数据流32表 明,在第一个节中只有供写入代码字7的起始段的空间。\n和把代码字第7的第二部分写入第二节的现有技术相比,代码字 第7的第二部分,即7b)被储存起来以供在第二次尝试中按照一个预定 规则,即按照一个也必须为解码器所知的规则将其写入数据流。图3 清晰地显示出,在第二节中,在代码字第2与第8之间仍有足够的空 间供代码字第7的最后部分进入。如果没有足够的空间,该代码字的 第三部分将被送入第三节。这样,在图3中,用于把代码字第7送入 数据流的预定规则就在于在所有的情况下均由一个节进行处理。当然, 也可以由两个节或者三个或更多的节进行,这样作的结果,就能使第 二个节7b)在下一次尝试中被写入第三个节,被写入第五个节,等等, 而不是第二个节。被用于在某个地方接收段7的第二部分的节的顺序 是任意的。然而,该顺序对解码器必须是透明的,以便被重新分类的 数据流能被重新读取。\n现在,第三集的代码字13至15被送入所形成的仍然不连贯的数 据流33。从步骤b)类推,这最好按照同一分配规则执行,使第三集的 第一个代码字被分配到第一节,第三集的第二个代码字被分配到第二 节,第三集的第三个代码字被分配给第三节,等等。对于第三集而言 该分配规则完全是任意的并且也可以与用于第二集的分配规则不同, 即根据该发明,一个集的每个代码字被分配给一个不同的节。\n步骤c)中的第一次尝试仅在把代码字第15的第一段送入,形成一 个不连贯的数据流34这一点上是成功的。代码字13,14与代码字15 的第二段即15b)被储存起来以供在第二、第三、第四、第五以及第六 次尝试中被接纳,其中第二段15b)会在第二次尝试中被接纳于第四节 (数据流35),其中在第三次尝试中没有任何东西被接纳,其中代码 字14的开始段会在第四次尝试中被接纳(数据流36),其中代码字 14的最后一段即14b会在第五次尝试中被接纳(数据流37)而其中, 最后,第三集的第一个代码字会在第六次并且是最后一次的尝试中被 送入第六节,为在此图示的例子形成耐差错的数据流38。利用图3描 述的方法保证该耐差错数据流的长度完全相等于这些可变长度代码字 的长度之和,对于用于数据缩减的平均信息量编码而言这是不言而喻 的。然而,本发明并不局限于具有最小长度的耐差错数据流,因为耐 差错是不受可能出现的任何填充位的影响的。\n对于图3中所示的增强型数据流,可以看出代码字8的起点即栅 格点43完全独立于代码字7的终点。还有,代码字9的起点即栅格点 44完全独立于代码字第8的终点。另外,应该注意到,由于写顺序相 反,第一节中代码字第1中的一个数据差错,比如说将由于该数据差 错而导致不正确的代码字比正确的代码字第1短一位的数据差错,不 会导致代码字7a的起始段的破坏,因为后者是从右向左而不是从左向 右写的。如果它从左向右写,解码器会把从一开始的正确代码字第1 余下的一位看作是代码字第7的起始位,这将导致从1至7的序列差 错。然而,该序列差错不会扩散至8,因为由于代码字8所选的写顺 序是从右向左因而它还是完全独立于代码字7的。如果代码字第8的 写顺序与第一集的代码字的写顺序相同,差错就不会从7向8扩散并 且,因为代码字8会由于分配规则而挨着代码字2写在第二部分7b的 前面,并且因此而不受不正确段7b的影响。\n通过一个恰当的例子,图4示出了用于读取耐差错数据流38的设 备的运行状况。一开始,在步骤a)从耐差错的数据流提取第一集的代 码字。为此,可以与Huffman解码器配对使用的所发明的该设备从第 一个栅格点41开始读取第一集的代码字,从第二个栅格点42开始读 取第一集的代码字第2,等等,直至第一集的所有代码字1至6被读 入为止。用于读取数据流的设备选择与用于生成数据流的设备所使用 的方向相同的方向,这是不言而喻的。\n接着,在步骤b)从余下的数据流50提取第二集的代码字。这里, 解码器跳至第一节的第二个栅格点42获取第二集的代码字7的起始 段,随后,它并不读入第二段7b,而是首先储存7a,以便接着从第二 节的第二个栅格点开始读入第二集的第二个代码字,等等。其结果是 一个残余的数据流51,其中的第一节已被完全腾空。由于该解码器现 在并不连续读取代码字7,而总是根据用于生成该数据流的设备的分 配规则逐节地读取,则已被描述的能够有力地降低序列差错扩散的耐 差错就得到了保证。\n在提取第二集代码字的第二次尝试中,代码字7b的第二部分根据 现有的写方向被读入第二节中,于是,仅有第三集的代码字余留于由 此产生的数据流52中。(第二节现在是空的。)这些代码字是在步骤 c)中提取的,其中代码字15的起始段一开始已在第一次尝试中被确定, 然而并不必储存,因为在第三节中未曾发现代码字15是完整的。第三 节现在也是空的,然而,栅格点仍然存在,以便解码器能够用它们为 自己定向。在第二次尝试中,能够发现代码字15是完整的。然而,通 过数据流54可以看出,在节3中对代码字14以及在节14中对代码字 15的搜索仍未成功。尽管如此,在第四次尝试中,在第5节中对代码 字14的搜索产生肯定的结果。然而,代码字14是不完整的,这就是 起始段14a被储存以便在第五次尝试中对余下的数据55进行检查,并 且在最后的第六次尝试中全部地读入数据流56的原因,现在数据56 仅由第六节并和代码字13组成。\n虽然在前面的例子中,通过举例,仅对把代码字分成起始段与结 束段的一个方法进行了说明,但是原则上讲,任何类型的方法均是可 行的。只要解码器遵循把第二集的或者第三级的以及其他集的代码字 分别地分配给不同的节,耐差错的编码就会得到保证。而且,进入数 据流的代码字的结束段的分类是任意的,只要解码器或者解码器的上 游读入电路确知在编码器中执行了哪一个预定规则。
法律信息
- 2020-02-18
专利权有效期届满
IPC(主分类): H03M 7/40
专利号: ZL 00805534.3
申请日: 2000.01.17
授权公告日: 2009.01.14
- 2017-11-07
专利权人的姓名或者名称、地址的变更
专利权人由弗兰霍菲尔运输应用研究公司变更为弗劳恩霍夫应用研究促进协会
地址由德国慕尼黑变更为德国慕尼黑
- 2014-10-08
专利实施许可合同备案的生效
IPC(主分类): H03M 7/40
合同备案号: 2014990000616
专利号: ZL 00805534.3
申请日: 2000.01.17
让与人: Via许可公司
受让人: 广州华多网络科技有限公司
发明名称: 生成与读出可变长度代码字数据流的方法和设备
申请公布日: 2002.04.17
授权公告日: 2009.01.14
许可种类: 普通许可
备案日期: 2014.08.04
- 2009-01-14
- 2002-04-17
- 2002-04-03
引用专利(该专利引用了哪些专利)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 |
1
| | 暂无 |
1995-01-26
| | |
被引用专利(该专利被哪些专利引用)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 该专利没有被任何外部专利所引用! |