CN102783036A - 使用辅码字指示符的编码和解码方法和设备 - Google Patents

Abstract

本发明描述了一种用于将输入符号序列编码为包括主码字和辅码字的多个码字的方法，以及一种用于对多个码字进行解码的方法。所述码字输出作为包括相关联码字类型指示符的比特流，码字类型指示符指定其相关联的多个连续码字是否包括至少一个辅码字以及在其相关联的多个连续码字包括至少一个辅码字的情况下，所述至少一个辅码字中的第一个辅码字的位置。解码器在主码字解码树与辅码字解码树之间进行选择，并使用所选解码树来解码所述多个码字之一。

Description

使用辅码字指示符的编码和解码方法和设备

相关申请的交叉引用

本申请要求2010年2月26日提交的题为“ENCODING ANDDECODING METHODS AND DEVICES USING A SECONDARYCODEWORD INDICATOR”的欧洲专利申请No.10154962.4的优先权。

上述专利申请的内容通过引入明确并入这里的详细描述中。

技术领域

本申请总体涉及数据压缩，具体地涉及编码器、解码器和熵编码和熵解码的方法。

背景技术

不论有损还是无损，数据压缩通常使用熵编码来将解相关信号编码为比特序列，即比特流。高效数据压缩具有广泛应用，如图像、音频和视频编码。视频编码的当前最新技术是ITU-T H.264/MPEG AVC视频编码标准。该标准定义了针对不同应用的多个不同简档，包括主简档、基线简档等等。

存在用于编码/解码图像和视频的多个标准(包括H.264)采用有损压缩过程来产生二进制数据。例如，H.264包括预测操作以获得残差数据，接着进行DCT变换和DCT系数的量化。然后，对得到的数据(包括量化系数，运动矢量、编码模式和其他相关数据)进行熵编码，以产生数据比特流，从而发送或存储在计算机可读介质上。

已经开发了多个编码方案来编码二进制数据。例如，可以使用Huffman码来编码JPEG。H.264标准允许两种可能的熵编码过程：上下文自适应可变长度编码(CAVLC)或上下文自适应二进制算术编码(CABAC)。CABAC得到比CAVLC更大的压缩，但是CABAC计算要求更高。

有利地，提供一种改进的编码器、解码器和熵编码和解码方法。

发明内容

一方面，本申请描述了一种用于对输入序号序列进行编码的方法。所述方法包括：基于根据上下文模型确定的估计概率，选择编码树；以及基于输入符号序列来遍历编码树，直至到达任一叶节点，并作为响应，输出与所述叶节点相关联的主码字，或者直至在编码树的内部节点处时发生转储清除事件，并作为响应，输出与所述内部节点相关联的辅码字。

另一方面，本申请描述了一种用于对编码数据的比特流进行解码以产生重构二进制序列的方法，所述比特流包含多个码字。所述方法包括：基于上下文模型，确定与重构二进制序列中的下一比特相关联的估计概率；以及确定在从先前解码的码字获得的比特序列中，与该估计概率相关联的比特是否可用，如果可用，则将该比特添加至重构二进制序列。如果没有这种比特可用，则解析比特流以提取下一码字，解码下一码字以获得与该估计概率相关联的新比特序列；以及将来自新比特序列的比特添加至重构二进制序列。

在另一方面，本申请描述了一种用于对输入符号序列进行编码的方法。所述方法包括：将输入符号序列编码为多个码字，其中所述码字包括主码字和辅码字；以及产生包括多个连续码字的比特流，其中所述多个连续码字之前有相关联的码字类型指示符，其中码字类型指示符指定其相关联的多个连续码字是否包括至少一个辅码字，以及在其相关联的多个连续码字包括至少一个辅码字的情况下，进一步指定所述至少一个辅码字中的第一个辅码字的位置。

在另一方面，本申请描述了一种用于对包含多个码字的编码比特流进行解码的方法，所述多个码字包括主码字和辅码字。所述方法包括：读取比特流中的码字类型指示符；以及基于码字类型指示符，在主码字解码树与辅码字解码树之间进行选择，并使用所选解码树来解码所述多个码字之一。

另一方面，本申请描述了一种用于对输入符号序列进行编码的方法。所述方法包括：对于输入符号序列中的每个符号，基于上下文模型，依次确定该符号的估计概率；使用与该估计概率相关联的编码树，标识与通过将该符号附加至与该估计概率相关联的先前符号序列而获得的符号序列相关联的码字；以及将所述码字存储在先进先出缓冲器的缓冲单元中，其中，所述缓冲单元与估计概率相关联；以及以先进先出的顺序，从缓冲器输出存储的码字。

在其他方面，本申请描述了一种用于实现上述方法的编码器。所述编码器包括：存储器；处理器；以及编码应用，存储在存储器中并具有用于将处理器配置为执行这里描述的方法的操作的计算机可读指令。

在其他方面，本申请描述了一种用于实现上述方法的解码器。所述解码器包括：存储器；处理器；以及解码应用，存储在存储器中并具有用于将处理器配置为执行这里描述的方法的操作的计算机可读指令。

本申请还描述了计算机可读介质，其上编码有用于将处理器配置为执行这里描述的一个或多个方法的计算机可执行指令。

结合附图，通过阅读以下示例的描述，本领域普通技术人员将理解本申请的其他方面和特征。

附图说明

现在参照附图作为示例，附图示出了本申请的示例实施例，其中：

图1以框图形式示出了用于对视频进行编码的编码器；

图2以框图形式示出了用于对视频进行解码的解码器；

图3示出了编码过程的框图；

图4示出了用于编码输入序列的示例方法；

图5以流程图形式示出了用于编码输入序列的另一示例方法；

图6以流程图形式示出了对编码数据的比特流进行熵解码的示例方法；

图7以流程图形式示出了在比特流中信号通知码选择的示例方法；

图8示出了编码器的示例实施例的简化框图；以及

图9示出了解码器的示例实施例的简化框图。

在不同图中可以使用相似参考标号来表示相似组件。

具体实施方式

以下描述总体涉及数据压缩，具体地，涉及有限字母表源(如二进制源)的高效并行编码。在以下给出的许多示例中，给出这种编码和解码方案的特定应用。例如，以下许多示意参照视频编码。可以认识到，本申请不限于视频编码或图像编码。

在以下描述中，参照H.264标准来描述示例实施例。本领域技术人员将理解，本申请不限于H.264，而是可以适用于其他视频编码/解码标准。还可以认识到，本申请不必限于视频编码/解码，可以适用于任何二进制源的编码/解码。

在以下描述中，在视频应用的上下文中，在某种程度上可互换地使用术语帧和片(slice)。本领域技术人员将认识到，在H.264标准的情况下，帧可以包含一个或多个片。还将认识到，取决于适用的视频编码标准的特定要求，特定编码/解码操作是逐帧执行的，一些编码/解码操作是逐片执行的。在任何特定实施例中，适用的视频编码标准可以确定是否关于帧和/或片来执行以下描述的操作，视情况而定。相应地，根据本公开，本领域技术人员将理解这里描述的特定操作或过程以及对帧、片或两者的特定引用对于给定实施例是否适用于帧、片或两者。

现在参照图1，图1以框图形式示出了用于对视频进行编码的编码器10。还参照图2，图2示出了用于对视频进行解码的解码器50的框图。可以认识到，这里描述的编码器10和解码器50均可以在专用或通用计算设备(包含一个或多个处理单元和存储器)上实现。编码器10或解码器50执行的操作可以通过例如专用集成电路或通过通用处理器可执行的存储程序指令来实现，视情况而定。设备可以包括附加软件，包括例如用于控制基本设备功能的操作系统。关于以下描述，本领域技术人员可以认识到在其中可以实现编码器10或解码器50的设备和平台的范围。

编码器10接收视频源12并产生编码比特流14。解码器50接收编码比特流14并输出解码视频帧16。编码器10和解码器50可以被配置为符合多个视频压缩标准来操作。例如，编码器10和解码器50可以符合H.264/AVC。在其他实施例中，编码器10和解码器50可以符合其他视频压缩标准，包括H.264/AVC标准的演进。

编码器10包括空间预测器21、编码模式选择器20、变换处理器22、量化器24和熵编码器24。本领域技术人员可以认识到，编码模式选择器20确定视频源的适合编码模式，例如对象帧/片是I、P还是B类型，帧/片内的特定宏块是帧间还是帧内编码。变换处理器22对空间域数据执行变换。具体地，变换处理器22应用基于块的变换来将空间域数据转换为频谱分量。例如，在许多实施例中，使用离散余弦变换(DCT)。在一些实例中，可以使用其他变换，如离散正弦变换等等。将基于块的变换应用于像素数据块得到变换域系数的集合。量化器24对变换域系数的集合进行量化。然后，熵编码器26对量化系数和相关联信息(如运动矢量、量化参数等等)进行编码。

帧内编码的帧/片(即，类型I)不参照其他帧/片进行编码。换言之，它们不采用时间预测。然而，帧内编码的帧依赖于帧/片内的空间预测，如图1中通过空间预测器21进行说明。即，在对特定块编码时，可以将块中的数据与针对该帧/片已经编码的块内邻近像素的数据进行比较。使用预测算法，可以将块的源数据转换为残差数据。然后，变换处理器22对残差数据进行编码。例如，H.264规定了4x4变换块的9种空间预测模式。在一些实施例中，这9种模式中的每一种可以用于独立处理块，然后使用速率失真优化来选择最佳模式。

H.264标准还规定了使用运动预测/补偿来利用时间预测。相应地，编码器10具有反馈环路，反馈环路包括：解量化器28、反变换处理器30和解块处理器32。这些单元反映了解码器50实现以再现帧/片的解码过程。帧存储器34用于存储再现帧。按照这种方式，运动预测基于在解码器50处重构帧是什么，而不基于原始帧，由于编码/解码中涉及的有损压缩，原始帧可能不同于重构帧。运动预测器36使用帧存储器34中存储的帧/片作为源帧/片，来与当前帧进行比较，以标识相似块。相应地，对于应用运动预测的宏块，变换处理器22编码的“源数据”是出自运动预测过程的残差数据。残差数据是表示参考块与当前块之间的差异(如果存在)的像素数据。关于参考帧和/或运动矢量的信息可以不由变换处理器22和/或量化器24处理，而是可以提供给熵编码器26，作为比特流的一部分与量化系数一起编码。

本领域技术人员将认识到用于实现H.264编码器的细节和可能变型。

解码器50包括：熵解码器52、解量化器54、反变换处理器56、空间补偿器57和解块处理器60。帧缓冲器58提供重构帧以便应用运动补偿的运动补偿器62使用。空间补偿器57表示根据先前解码块来恢复特定帧内编码块的视频数据的操作。

熵解码器52接收并解码比特流14，以恢复量化系数。在熵解码过程中，还可以恢复辅助信息，如果适用，一些辅助信息可以提供给运动补偿环路，以用于运动补偿。例如，熵解码器52可以恢复运动矢量和/或针对帧间编码宏块的参考帧信息。

然后，解量化器54对量化系数进行解量化，以产生变换域系数，然后，反变换处理器56对变换域系数进行反变换，以重建“视频数据”。可以认识到，在一些情况下，如对于帧内编码宏块，重建的“视频数据”是相对于帧内先前解码块的、用于相对于帧内先前解码块的空间补偿的残差数据。空间补偿器57根据残差数据和来自先前解码块的像素数据来产生视频数据。在其他情况下，如对于帧间编码宏块，来自反变换处理器56的重建“视频数据”是相对于来自不同帧的参考块的、用于运动补偿的残差数据。这里，空间和运动补偿均可以称为“预测操作”。

运动补偿器62在帧缓冲器58内定位专用于特定帧间编码宏块的参考块。运动补偿器62基于专用于帧间编码宏块的参考帧信息和运动矢量来进行该操作。然后，运动补偿器62提供参考块像素数据，以与残差数据组合，得到针对该宏块的重建视频数据。

然后，可以对重构帧/片应用解块过程，如解块处理器60所示。在解块之后，输出帧/片作为解码视频帧16，例如以在显示设备上显示。可以理解，视频回放机(如计算机、机顶盒、DVD或蓝光播放器和/或移动手持设备)可以在输出设备上显示之前将解码帧缓冲在存储器中。

熵编码是所有无损和有损压缩方案(包括上述视频压缩)的基本部分。熵编码的目的是表示通常由独立但是不同分布过程建模为比特序列的假定解相关信号。用于实现该操作的技术必须不依赖于解相关信号如何产生，但是可以依赖于每个即将到来符号的相关概率估计。

实际中使用两种常见熵编码方法：第一种是可变长度编码，利用码字来标识输入符号或输入序列；第二种是范围(或算术)编码，对[0，1)区间的子区间序列进行封装，以得到单一区间，根据该单一区间，使用定义这些区间的概率分布，可以重构原始序列。典型地，范围编码方法往往提供更好的压缩，而VLC方法有可能更快。在任一情况下，输入序列的符号来自有限字母表。

熵编码的特殊情况是输入字母表限于二进制符号时。这里，VLC方案必须将输入符号组合在一起以具有任何压缩可能，但是由于概率分布可以在每个比特之后改变，难以进行高效的码重构。相应地，范围编码由于其更大的灵活性而被认为具有更大的压缩，但是算术码的较高计算要求妨碍了实际应用。

在一些重要的实际应用中，如高质量视频解码，熵解码器必须实现非常高的输出速度，对于具有有限处理能力或速度的设备而言这可能成为问题。对于许多这种设备，CABAC的计算要求过高。

在一些熵编码方案(如CAVLC和CABAC，两者均在H.264/HAV中使用)中使用的技术之一是上下文建模。对于上下文建模，输入序列的每个比特具有上下文，其中上下文由该比特之前的比特给出。在一阶上下文模型中，上下文可以完全依赖于先前比特(符号)。在许多情况下，上下文模型可以是自适应的，使得在处理序列的其他比特时，可以改变与给定上下文的符号相关联的概率。

参照图3，图3示出了编码过程100的框图。编码过程100包括上下文建模组件104和熵编码器108。上下文建模组件104接收输入序列x 102，在本示例中，x是比特序列(b₀，b₁，...b_n)。上下文建模组件104基于序列中的一个或多个先前比特来确定每个比特b_i的上下文，并基于自适应上下文模型来确定与该比特b_i相关联的概率p_i，其中该概率是该比特将是最小可能符号(LPS)的概率。在二进制实施例中，根据习惯或应用，LPS可以是“0”或“1”。上下文建模组件输出输入序列(即比特(b₀，b₁，...b_n))以及其相应概率(p₀，p₁，...p_n)。这些概率是利用上下文模型确定的估计概率。然后，将该数据输入熵编码器106，熵编码器106使用概率信息对输入序列进行编码。例如，熵编码器106可以是二进制算术编码器。熵编码器106输出编码数据的比特流108。本领域技术人员可以认识到，在许多实现中，上下文建模组件104可以接收更高阶数据，如系数和运动矢量等等，根据这些更高阶数据，上下文建模组件104产生输入比特序列及其相应概率。

在以下描述中，参照用于对二进制序列进行熵编码的实施例。可以理解，所描述的过程可以推广至有限字母表的符号，二进制序列是一种特殊情况。本领域技术人员可以认识到对以下描述的一些方面的合适修改，以并入多于两个符号。

码字产生

一方面，本申请描述了采用编码树来解析码字的熵编码和解码过程。树的每个叶节点与来自主码字集合的码字相关联，树的内部节点与辅码字集合的码字相关联。编码树和码字的产生可以离线执行。

输入序列可以理解为任意交织的n个输入源，其中n个源中的每一个与估计概率值相关联。

考虑概率的有限集合P＝{p_k|1≤k≤n，0＜p_k≤0.5}。p_k值被认为是最小可能符号(LPS)的概率值；其补具有1-p_k的形式并且属于最大可能符号(MPS)。实际上，根据上下文来确定对p_k(或等效地索引k)的选择以编码下一比特，上下文本身是根据编码历史来确定的。在上下文自适应或有状态编码中，概率p_k取决于输入序列的当前状态。概率的数目n可以根据多种因素来设置，包括期望复杂度。在H.264/AVC CABAC中，例如，数目n为64。

对于P的每个p_k，产生全二进制树，其中树中的每个路径定义比特序列，该路径中的每个节点(包括叶节点)表示具有p_k ^u·(1-P_k)^v形式的值，其中u是路径中LPS的数目，v是路径中MPS的数目。

为了产生二进制树，对于P的每个p_k，将符号(比特)组合为服从特定约束的序列S_k的集合。示例约束可以包括：

1.没有序列概率低于阈值。

2.序列的数目小于限制值。

3.对于S_k，存在有效码字集合。

4.序列S_k的集合能够以给定实施例的结构来方便或有效地表示。

在一个示例实施例中，这些约束可以指定为：

1.没有序列概率低于2^-16。

2.序列|S_k|的数目小于4096。

3.对于S_k，存在有效Huffman码字集合。

4.S_k的元素具有能够以30比特表示的特殊形式。

可以采用各种算法来平衡产生适合二进制树和相应码字的相关约束。

二进制树产生过程得到针对每个索引k的两个Huffman码集：主Huffman码集HL_k和辅Huffman码集HN_k。主Huffman码集HL_k中的主Huffman码字与针对k的二进制树的叶相关联；而辅Huffman码集HN_k中的辅Huffman码字与二进制树的内部节点相关联。换言之，每个主码字与序列S_k之一相关联；而每个辅Huffman码字与序列S_k的前缀之一相关联。以下将进一步解释，在特定环境下，输入序列可以在完成序列S_k之前终止，因此可以使用辅码字来编码前缀(S_k的部分完成序列)。

得到的码集是可变-可变长度码集。

码集写为两种形式：对于源k，一种指定编码器树，另一种指定解码器树。编码器树的每个叶节点具有与其相关联的特定概率：p_k ^u·(1-p_k)^v。因此，基于这些概率，可以使用前缀树码来对解析字进行编码。这形成了解码器树的基础。

在一个实施例中，每个源k的编码器树可以包括例如链表中的主和辅码字，使用整数码用于每个节点以保存码字。在一个实施例中，每个节点的比特字段可以构造如下：

0...15：该节点的Huffman码(主或辅)

16...19：Huffman码的长度减1

20...31：左子节点的索引；对于叶节点为0

在二进制树中，例如可以使用以下惯例：左子节点对应于0比特。可以将表构造为使得右子节点在表中紧随左子节点之后。按照这种方式，编码器能够使用二进制输入序列，逐比特导航表。当编码器到达叶节点(如字段的索引部分所示)时，编码器知道Huffman码是主码字，并且可以针对该序列S_k输出该主码字。以下提供关于编码过程的示例实施例的进一步细节。

在下表中阐述主码字的示例集合。针对p_k＝0.20来产生下表，其中概率阈值设为0.13(当序列概率达到小于0.13的值时结束解析)。得到的树包含14个叶节点。总体而言，这实现了估计源熵0.7250，仅比理论极限(p_k*log(p_k)+(1-p_k)*log(1-P_k))＝0.7219高0.42％。

表1：示例主码集

编码过程

如上所述，编码器包括针对每个源k的主码集HL_k和针对每个源k的辅码集HN_k。可以将每个码集的码字并入编码表中，如上所述。在这种实施例中，编码器将在存储器中存储k个编码表，以表示k个编码树和与树的每个节点相关联的码字。

现在参照图4，图4示出了用于编码输入序列的示例方法200。在本实施例中，序列是二进制序列。在本示例方法200中，假定单一源序列。以下进一步描述处理交织源的其他实施例。

方法200从步骤202中接收二进制序列以及步骤204中基于与二进制序列相关联的概率估计p_k来选择编码表或树开始。如上所述，假定方法200应用于固定概率估计p_k的单一源序列。例如，二进制序列可以是从输入序列x中提取的与概率估计p_k相关联的二进制比特序列。

使用所选编码树，在步骤206，使用二进制序列来遍历树(或在一些实现中为表)。在步骤208，在每个比特处，编码器评估序列目前是否得到树(或表)中的叶节点。如果是，则在步骤210中，输出主码字。然后，在步骤216，编码器返回树根，继续在步骤206处理二进制序列。

如果在步骤208比特未得到完成的主码字，则在步骤212，编码器可以评估是否发生转储清除事件。可能的转储清除事件在以下进一步讨论；然而，示例转储清除事件包括输入序列的结束或缓冲器满条件。如果在编码器在树的内部节点处时发生转储清除事件，则在步骤214，输出与该内部节点相关联的辅码字。如果未发生转储清除事件，则编码器返回步骤206，继续二进制序列的逐比特处理。

如上所述，对于输入二进制序列x，编码器基于每个比特的上下文来估计每个比特的估计概率值p_i。使用估计概率值p_i来将比特分类为属于n个源之一，其中每个源与P中的概率值p_k之一相关联。使用源的相应编码树和HL_k和HN_k码字来对源进行独立编码。编码器产生包含n个源的码字在内的编码数据的比特流。

解码器接收比特流并提取码字。基于上下文，解码器标识每个码字与哪个源相关联，并基于此，根据码字来重新产生比特序列。然后，解码器再次使用与编码器所采用的上下文模型相同的上下文模型，基于逐比特地评估的估计概率来对各个序列的重新产生的比特进行交织。

可以认识到，在交织源实施例中，各个源的主码字不需要以与其初始开始顺序相同的顺序来解析。例如，在处理比特序列时，编码器可以初始遇到与概率p₁相关联的比特，并开始遍历与概率p₁相关联的编码树。然而，在编码树到达叶节点之前，输入序列可能提供与概率p₂相关联的比特。编码器可能将到达叶节点，从而在其到达与p₁相关联的源的叶节点之前到达针对与p₂相关联的源的主码字。为了确保解码器能够确定哪些码字与哪些源相关联，编码器确保码字以每个码字开始的顺序输出，而不论哪个码字首先完成。

根据本申请的一方面，编码器使用先进先出缓冲器来确保码字以正确顺序输出。该缓冲器可以是循环缓冲器。

现在参照图5，图5以流程图形式示出了用于编码输入序列的方法300。在该示例实施例中，输入序列假定为二进制序列。方法300从步骤302中接收输入序列开始。在步骤304，对于输入序列中的每个比特，编码器使用上下文来确定与该比特相关联的估计概率p_k。在许多实施例中，估计概率p_k基于上下文模型和序列中的一个或多个先前比特。序列中的第一比特可以分配有缺省估计概率。在步骤306中，基于与比特相关联的估计概率p_k，将比特添加至与估计概率p_k(即与该源k)相关联的缓冲器单元。

在采用先进先出(FIFO)缓冲器的实施例中，在步骤306，编码器可以评估缓冲器中是否存在包含针对源k的未完成序列S_k的缓冲单元。如果是，则在该缓冲单元中，将比特附加至该序列。如果否，则编码器针对源k分配新的缓冲单元。以FIFO的方式分配缓冲单元，以确保从缓冲器输出的第一个完成码字是第一开始序列的码字。

在使用编码表来存储编码树的实施例中，其中每个节点由其辅或主码字加上对左子节点的索引或指示其为叶节点的指示符来表示，比特序列本身可以不保持在缓冲单元中。而是，编码器可以在缓冲单元中存储编码树节点整数值。例如，编码树节点整数值指示与给定前缀相关联的辅Huffman码字和对左子节点的索引。针对源k接收的下一比特将编码器引至编码器表中的子节点之一，并基于此，利用与编码器表的相关子节点相关联的编码器树节点整数来盖写缓冲单元。一旦编码器表到达叶节点，节点整数的索引部分信号通知该码字完成，即已经到达叶节点并且整数的码字部分的值是主码字。

在另一实施例中，缓冲单元可以不用于存储符号或存储辅码字。单独的数组或其他存储器结构可以用于跟踪与每个估计概率相关联的符号序列和/或跟踪所使用的每个编码树中的当前节点。在这种实施例中，一旦过程到达叶节点，则将主码字)写入缓冲单元，或者一旦发生转储清除事件，则将辅码字写入缓冲单元。

在步骤308，编码器评估比特刚刚附加至的序列S_k现在是否完成。换言之，编码器可以评估，在源k的编码树中该序列是否已经到达叶节点。如上所述，在一些实施例中，可以将来自相关编码树的节点整数本身存储在缓冲单元中，而不是存储序列S_k的比特，在这种情况下，步骤308涉及评估节点整数的索引部分是否指示叶节点。在另一实施例中，序列的比特或节点整数均不存储在缓冲单元中，而是存储在单独的数组中。

如果已经到达叶节点，并且因此将来自HL_k的主码字存储在源k的缓冲单元中，则编码器在步骤310评估第一缓冲单元是否包含主码字。如果不包含，则在缓冲器中将源k的完成码字保持在其位置，编码器返回步骤304处理下一比特。如果刚刚处理的比特已经使得第一缓冲单元中的码字完成，则在步骤312，编码器可以从第一缓冲单元中输出主码字，以及在后续连续缓冲单元中存在尽可能多的主码字，直至到达不存在主码字的缓冲单元，即直至到达处于其相应编码树的内部节点处的缓冲单元。然后，该缓冲单元变为循环缓冲器中的第一缓冲单元，编码器返回步骤304处理输入序列中的下一比特。

在另一实施例中，编码器可以将完成码字保持在其相应缓冲单元中，直至在连续缓冲单元中存储一定数目的完成码字，然后将其输出。如以下所述，在一个实施例中，码字类型指示符基于预测数目的连续主码字是真还是假；在这种实现中，有利地，可以将完成码字保持在缓冲器中，以评估是否达到预测数目。在这种实现中，缓冲器可以在达到预测数目的连续主码字时或者发生转储清除事件(得到至少一个辅码字)时输出完成码字。关于码字指示符的进一步细节在本说明书的以下部分给出。

如果在步骤308比特未得到完成的主码字，则在步骤314，编码器确定是否发生转储清除事件。如果没有发生，则编码器返回步骤304，继续处理输入序列中的下一比特。如果发生转储清除事件，则在步骤316，编码器通过针对未完成序列输出辅码字，来对一个或多个缓冲单元进行转储清除(按照FIFO方式)。

转储清除事件是变为必须针对未完成序列S_k输出码字的事件。一个示例转储清除事件是输入序列的结束。例如，这可能发生在视频、帧、片的结束处，或者在二进制序列的其他这种中断处。这种性质的转储清除事件导致对整个缓冲器进行转储清除，使得在比特流中输出编码序列的整个其余部分。

另一示例转储清除事件是在缓冲器变满时。例如，如果缓冲器的第一单元包含针对源k的未完成码字，并且其余缓冲单元已被分配，如果变为必须在第一单元的码字完成之前针对特定源分配附加缓冲单元，则可能需要在第一单元完成之前对第一单元进行转储清除。可以理解，这类转储清除事件仅需要对第一单元进行转储清除，而不需要对整个缓冲器进行转储清除。

本描述相关领域的普通技术人员可以认识到其他示例转储清除事件。

现在给出简化示例来示意编码过程的方面。在该简化示例中，将仅假定两个源A和B。为了示意目的，针对源A和B均使用在表1的示例码集中以上所示的码字(可以认识到，在实际实现中，每个源具有其自身编码树和主和辅码集)。示例输入序列以及针对输入序列的每个比特的上下文(以及从而其源分配)如下所述：

A	A	B	B	B	B	B	B	A	A	A
											1	0	1	1	1	0	1	0	0	1	1

编码器始于将缓冲单元(第一缓冲单元)分配给源A，并在源A的编码器树中从根开始，行进至由1表示的内部节点，该内部节点与特定辅码字相关联。然后，编码器移至序列10表示的内部节点。在一些实施例中，现在可以将与10相关联的辅码字写至第一缓冲单元，或者在存储器中跟踪或存储。上下文指示下一比特与源B相关联，因此编码器针对源B分配新缓冲单元，并开始按照1，1，1，0的序列顺序遍历源B的编码树，从而到达序列1110的叶节点。相应地，将码字011写至缓冲单元。然而，此时不将其输出至比特流，因为源A的第一单元包含未完成序列。

序列中的下一比特是源B的1。由于与源B相关联的单元包含完成序列Sk，编码器将下一空闲缓冲单元分配给源B，并从根开始遍历源B的编码树，到达与比特1相关联的子节点。下一比特是也与源B相关联的0，给出序列10。

序列中的下一比特是源A的0，将其分配给第一缓冲单元。相应地，编码器从与10相关联的内部节点行进至序列100的子节点，该子节点是与主码字11100相对应的叶节点。将该主码字写至第一单元。

在本实施例中，现在输出第一单元(包含码字1110)、第二单元(包含码字11100)以产生比特流(如上所述，在一些情况下，可以将多个连续主码字保持在缓冲器中，以评估预测)。现在，包含源B的未完成序列10的第三缓冲单元变为第一缓冲单元。然而，序列中的下一比特是源A的1，因此，编码器针对源A分配新缓冲单元，并从根开始遍历源A的编码树，到达与比特1相关联的内部节点。序列的最后比特包含源1的1。相应地，在序列结束处，缓冲器包含两个未完成单元：源B具有包含10的单元，源A具有包含序列11的单元。因此，将源B序列10和源A序列11的辅码字输出至比特流。

可以认识到，如果主和辅码字重叠，即不互斥，则解码器需要一种机制来确定比特流中的码字是主码字还是辅码字。一种可能的机制是主码集中的显式“转义(escape)”码字，指示该转义码之后的码字是辅码字。可以认识到，这种性质的“转义”码字适用于序列结束类型的转储清除事件。

解码过程

解码器将每个源k的码集存储在解码器树/表结构中。例如，每个源k可以包括：主解码树，用于解析主码字并重新产生对应比特序列；以及辅解码树，用于解析辅码字并重新产生对应部分比特序列。源k的每个解码树可以包含针对每个节点的整数，用于解析码字。内节点可以包括对一个或多个子节点的索引。叶节点可以包含与解析码字相对应的序列。

在一个示例中，码语法可以包括针对特定序列的特殊码。例如，序列“111....111”和“111....110”可以具有特殊码。以下结构(其中针对解码树的每个节点使用32比特整数)使用两个比特来指示节点类型。在本示例实施例中，比特30∶31用于指示节点类型：

解码器遍历解码树以将比特流中的码字解析为比特序列。为了加速解码，可以以贪婪方式配置解码器，以从读出最小剩余码字长度开始。例如，使用上表1中所列的码字，最小码字长度为3比特，这意味着解码器可以从评估码字的前3个比特开始，以索引解码表中的位置，从而快速标识开始遍历树的叶节点或内部节点。

可以认识到，解码器基于由上下文模型给出的估计概率，对从码字解码的比特序列中的比特进行交织。

现在参照图6，图6以流程图形式示出了用于对编码数据的比特流进行熵解码的示例方法400。方法400采用在编码器处用于产生编码数据的比特流的相同上下文模型。比特流包括在编码器处的熵编码器产生的码字。解码器产生与码字相对应的比特序列，并根据上下文模型，对比特序列中的比特进行交织。方法400得到重构二进制序列的输出。

具体地，在步骤402，解码器基于当前上下文来确定比特的估计概率。一开始估计概率可以是缺省概率。

然后，使用估计概率来确定下一比特所来自的源，即与估计概率相关联的源k。在步骤404，解码器确定是否有来自该源k的解码比特可用。如果没有，则在步骤406，解码器解析输入比特流以提取下一码字。解码器通过以下操作来实现这一点：使用源k的解码器树(或表)，以标识码字并标识对应比特序列。比特序列可以存储在与源k相关联的字段或缓冲器中，如步骤408所示。然后，在步骤410，将该比特序列的第一比特添加至重构二进制序列。

在步骤412，解码器可以评估其是否已经到达重构二进制序列的结尾，这种情况可能发生在对于任一源不存在其他未消耗的比特序列以及在比特流中不存在其他码字时。在该情况下，方法400以在步骤414中输出二进制序列结束。否则，方法400返回步骤402以更新上下文，并确定重构二进制序列的下一比特的源。如果步骤404中确定重构二进制序列的下一比特可用，则立即继续至步骤410以消耗该比特(例如从存储该比特的字段、寄存器或缓冲器中)，并将其添加至重构二进制序列。如果该下一比特不可用(由于该源先前未被参考，或者由于针对该源上次解码的比特序列已经被消耗)，则在步骤406，解码器解析比特流以标识下一码字，以此类推。

可以认识到，对解码过程的以上描述涉及源k的解码树，而未涉及其是主树还是辅树。由于主码字的使用比辅码字经常得多，并且使用辅码字是突发的，可以使用适合的机制来通知解码器何时使用辅码字。如上所述，可以在主码集中使用“转义”码字来信号通知后续码字是辅码字。利用这种实现，解码器假定其使用主解码树，直至检测到转义码字，在这种情况下，其切换至使用辅解码树用于后续码字。如上所述，“转义”码字机制适于序列结束转储清除事件。如果转储清除事件以预期间隔发生而不是序列结束事件(如在缓冲器满事件期间)，则其他机制可能更加合适。

另一适合机制的实施例在接下来的部分中描述。在转到该机制之前描述备选编码和解码实施例。

在一个备选实施例中，每个码字不按照其开始的顺序输出(即先进先出)，而是将码字组合。该实施例解决了解码器处可能的处理器高速缓存速度限制。在上述实施例中，编码器产生码字的比特流，其中相邻码字可以与不同估计概率相关联。因此，在解码器处，在解码码字时，在许多实施例中，解码器将根据基于上下文的估计概率来确定适用的相关联解码树(在许多情况下为表)，并将适用的相关联解码树加载入快速存取存储器，如高速缓存存储器，例如处理器高速缓存存储器。然而，这类快速存取存储器通常大小有限，在一些实施例中，这意味着在可以将与不同估计概率相关联的不同解码树/表加载至高速缓存之前，必须将每个表从高速缓存中转储清除。在比特流被构造为使得每个连续码字可能与不同解码树相关联的实施例中，这可以意味着必须将新的解码树/表加载至高速缓存存储器以解码每个码字。解码树/表的重复转储清除和加载至存储器可能对解码过程施加硬件相关的速度限制。

为了解决该问题，在编码器侧，FIFO缓冲器可以使用被配置为针对相关联估计概率保存多于一个码字的缓冲单元。这种缓冲器仍以FIFO操作，然而，仅当第一单元中的所需码字数目完成时，才输出第一单元。在一个这种示例实施例中，缓冲单元的大小可以保存8个码字。换言之，不是每次FIFO缓冲器的第一单元包含完成码字时以FIFO输出与估计概率相关联的码字，而是每次FIFO缓冲器的第一单元包含预定数目的完成码字时以FIFO输出码字。可以认识到，这不必然意味着所有8个(或者任意多个)码字物理上存储在缓冲器的第一单元中，只要提供与相同估计概率相关联的缓冲单元之间的合适链接即可。

在解码器处，在对交织码字进行解码时，解码器知道在比特流中将连续存在与相同估计概率相关联的预定数目的码字。相应地，在解码与估计概率相关联的码字时，解码器使用相同的解码树/表来解码预定数目的码字。这允许解码器使用相同解码树/表来完成多于一个码字的解码，而不必针对每个码字清除高速缓存并加载新的解码树/表。

码选择

以下阐述被设计为容纳码选择信令的比特流结构的一个示例实施例。比特流包含来自主码集或辅码集的码字，其中主码集的使用比辅码集频繁得多，辅码字往往突发地出现。在该示例中，将码字类型指示符置于比特流中。为了避免与插入该码字类型指示符相关联的过多开销，以下示例依赖于辅码字的使用不太频繁的事实。

形成辅码字的概率的估计p_s。根据该估计，产生预测数目的连续主码字L(p_s)。如果预测为真，即如果接下来L(p_s)个连续码字为主码字，则在比特流中输出“真”标记(如“0”比特)，然后将L(p_s)个码字写至比特流。然后再次进行预测。真标记是码字类型指示符的一个示例。

如果预测为假，即如果接下来L(p_s)个连续码字中存在辅码字，则在比特流中该辅码字的位置之前输出“假”标记(如“1”比特)，例如该辅码字的位置在相对于“假”标记的比特位置。在另一实施例中，该位置可以给出作为辅码字之前的一定数目的码字。直至并包括辅码字的连续码字输出至比特流。然后，在辅码字之后，解码器返回进行新的预测。假标记和位置信息是码字类型指示符的另一示例。

现在参照图7，图7以流程图形式示出了用于在比特流中信号通知码选择的方法500。方法500始于步骤502，估计辅码字的概率p_s。可以使用任何适合的算法来估计该概率。在一个实施例中，该估计可以是静态的。在另一实施例中，估计可以是自适应的，并依赖于最近遇到辅码字的频率。这种算法可以反映辅码字使用的突发性。

在一个示例中，对辅码字的概率p_s的估计依赖于紧接在前的码字是主码字还是辅码字。如果是辅码字，并且该辅码字本身之前是N个主码字，则概率估计p_s可以依赖于由p＝1/(N+1)给出的最大似然估计。如果在前码字是主码字，则：如果从上次辅码字起已经出现M个主码字，则可以使用Krichevsky-Trofimov估计器来给出p_s＝1/(2M+2)。选择辅码字的估计概率p_s的这些方法是示例。还可以使用其他方法。

在步骤504，使用概率估计p_s来预测连续主码字的数目。通过数学推导，可以使用表达式L＝ln2/p_s来计算连续主码字的数目。这意味着，基于上一码字是主码字还是辅码字，连续主码字的数目的良好近似估计是在两个先前辅码字之间观察到的主码字数目的0.7倍，或者是从上一辅码字起看到的主码字数目的1.4倍。

在步骤506，编码器评估其对L(p_s)个连续主码字的预测是否正确。如果是，则在步骤508，编码器输出码字类型指示符，例如“真”标记，在这种情况下为0比特，然后在步骤510，编码器将L(p_s)个主码字输出至比特流。然后，方法500返回步骤502以进行新的估计。

如果连续主码字的预测错误，则在步骤512，编码器在比特流中输出码字类型指示符，例如“假”标记，其后接着是接下来L(p_s)个码字内第一个辅码字的位置的索引(步骤514)。然后，在步骤516，编码器输出直至并包括在步骤514中引用的第一个辅码字在内的所有码字，然后返回步骤502进行新的估计。

在解码器处，通过进行相同的预测，对所构造的比特流进行解码。如果在比特流中的标记为“0”，则解码器知道接下来L(p_s)个连续码字为主码字。如果标记为“1”，则解码器提取索引信息，并且能够定位比特流中的辅码字。下一预测标记紧接在辅码字之后。

相应地，解码器读取码字类型指示符，如果该指示符指示预测为真(即接下来L个码字为主码字)，则解码器使用主解码树来处理这些连续码字。如果解码器读取码字类型指示符并发现预测为真，则解码器读取位置信息，并使用主编码树来处理直至该位置的连续码字，并使用辅解码树来处理该位置处的码字。

编码器和解码器

现在参照图8，图8示出了编码器900的示例实施例的简化框图。编码器900包括：处理器902、存储器904和编码应用906。编码应用906可以包括存储在存储器904中并包含指令的计算机程序或应用，所述指令用于将处理器902配置为执行这里描述的步骤或操作。编码应用906可以包括：熵编码器26，被配置为使用这里描述的一个或多个过程，对输入序列进行熵编码，并输出比特流。存储器904可以包括这里描述的缓冲存储器和存储器单元。存储器904可以存储针对每个源k的主和辅码字。如这里描述的，码字可以存储为针对每个源k的编码表。可以理解，编码应用906可以存储在计算机可读介质上，如致密光盘、闪存设备、随机存取存储器、硬盘等等。

现在还参照图9，图9示出了解码器1000的示例实施例的简化框图。解码器1000包括：处理器1002、存储器1004和解码应用1006。解码应用1006可以包括存储在存储器1004中并包含指令的计算机程序或应用，所述指令用于将处理器1002配置为执行这里描述的步骤或操作。解码应用1006可以包括：熵解码器52，被配置为接收根据这里描述的过程来编码的比特流，并如这里描述的，根据编码数据的比特流来重构二进制序列。解码应用1006可以将处理器配置为遍历所存储的解码树/表，以解析比特流中的码字，从而标识对应的比特序列。可以理解，解码应用1006可以存储在计算机可读介质上，如致密光盘、闪存设备、随机存取存储器、硬盘等等。

可以认识到，根据本申请的解码器和/或编码器可以在多个计算设备中实现，包括但不限于服务器、合适编程的通用计算机、电视机顶盒、电视广播设备和移动设备。可以通过包含指令的软件来实现解码器或编码器，所述指令用于将处理器配置为执行这里描述的功能。软件指令可以存储在任何合适的计算机可读存储器上，包括CD、RAM、ROM、闪存等等。

可以理解，这里描述的编码器和解码器以及实现所描述的用于配置编码器的方法/过程的模块、例程、进程、线程或其他软件组件可以使用标准计算机编程技术和语言来实现。本申请不限于特定处理器、计算机语言、计算机编程惯例、数据结构、其他这种实现细节。本领域技术人员将认识到，可以将所描述的过程实现为存储在易失性或非易失性存储器中的计算机可执行代码的一部分、专用集成芯片(ASIC)的一部分等。

可以对所描述的实施例进行特定适配和修改。因此，上述实施例被认为是示意性而非限制性。

Claims (17)

1.一种用于对输入符号序列进行编码的方法，所述方法包括以下步骤：

将输入序列编码为多个码字，其中所述码字包括主码字和辅码字；以及

产生包括多个连续码字的比特流，其中关联码字类型指示符位于所述多个连续码字之前，其中码字类型指示符指定与其相关联的多个连续码字是否包括至少一个辅码字，以及在与其相关联的多个连续码字包括至少一个辅码字的情况下，进一步指定所述至少一个辅码字中的第一个辅码字的位置。

2.根据权利要求1所述的方法，其中，产生步骤包括：预测连续主码字的数目，所述多个连续码字包含预测数目的码字，码字类型指示符指示所述预测是真还是假。

3.根据权利要求2所述的方法，其中，预测连续主码字的数目包括：确定两个最新近辅码字之间的连续主码字的数目L，并将连续主码字的数目预测为近似0.7L。

4.根据权利要求2或3所述的方法，其中，码字类型指示符包括指示所述预测是真还是假的标记，在假的情况下，码字类型指示符还包括所述位置。

5.根据权利要求4所述的方法，其中，如果标记指示预测为假，则在所述至少一个辅码字中的第一个辅码字之后插入下一码字类型指示符。

6.根据权利要求4或5所述的方法，其中，如果标记指示预测为真，则在所述多个连续码字之后插入下一码字类型指示符。

7.根据权利要求1至6中任一项所述的方法，其中，产生步骤包括：在每个辅码字之后插入码字类型指示符。

8.一种用于对包含多个码字的编码比特流进行解码的方法，所述多个码字包括主码字和辅码字，所述方法包括以下步骤：

读取比特流中的码字类型指示符；以及

基于码字类型指示符，在主码字解码树与辅码字解码树之间进行选择，并使用所选解码树来解码所述多个码字之一。

9.根据权利要求8所述的方法，还包括：基于预定模型，预测连续主码字的数目，其中码字类型指示符包括指示所述预测是真还是假的标记。

10.根据权利要求9所述的方法，其中，选择步骤包括：如果码字类型指示符指示所述预测为真，则针对预测数目的连续码字中的所有码字选择主解码树。

11.根据权利要求9或10所述的方法，其中，如果码字类型指示符指示所述预测为假，则码字类型指示符还包括预测数目的连续主码字内第一个辅码字的位置。

12.根据权利要求11所述的方法，其中，如果码字类型指示符指示所述预测为假，则选择步骤包括：针对预测数目的连续码字中在所述位置之前的所有码字，选择主解码树；而针对所述位置处的码字，选择辅解码树。

13.根据权利要求8至12中任一项所述的方法，其中，主码字和辅码字不互斥。

14.根据权利要求8至13中任一项所述的方法，其中，主解码树和辅解码树分别包括主码字表和辅码字表、及与其对应的解码比特序列。

15.一种计算机可读介质，存储计算机可执行指令，所述指令用于将处理器配置为实现根据权利要求1至14中任一项所述的方法。

16.一种用于对输入符号序列进行编码的编码器，所述编码器包括：

处理器；

存储器；以及

存储在存储器中的编码应用，包含用于将处理器配置为使用根据权利要求1至7中任一项所述的方法来对输入序列进行编码的指令。

17.一种对编码数据的比特流进行解码以产生重构二进制序列的解码器，所述解码器包括：

处理器；

存储器；以及

存储在存储器中的解码应用，包含用于将处理器配置为使用根据权利要求8至14中任一项所述的方法来对比特流进行解码的指令。

Images