可适应性范式哈夫曼解码器及其方法与图像解码器

摘要

可适应性范式哈夫曼解码器及其方法与图像解码器。该可适应性范式哈夫曼解码器，包括符号索引值产生器、内容选择器与符号表缓冲存储电路。内容选择器用以输出内容选择信号，而符号表缓冲存储电路根据内容选择信号自外部存储器所存储的多个符号表中读取一个对应符号表并存储此对应符号表。符号索引值产生器用以存储多个编码表的解码信息，并根据内容选择信号自此多个解码信息中选择一个对应解码信息。接着，符号索引值产生器接收比特流，并根据对应解码信息对比特流解码，以解得符号索引值。之后，符号表缓冲存储电路根据符号索引值自对应符号表中解得输出符号。

说明书

技术领域

本发明涉及一种熵解码器(entropy decoder)，且特别涉及一种可适应性范式哈夫曼解码器(adaptive canonical Huffman decoder)及其方法，以及使用此适应性范式哈夫曼解码器或其方法的图像解码器。

背景技术

哈夫曼编码(Huffman coding)是一种常用于图像压缩(image or video compression)中的熵编码(entropy coding)，且哈夫曼编码是一种存在已久的无失真压缩(lossless compression)方法。然而，在使用哈夫曼编码时，解码器需要知道哈夫曼编码树的结构，因此编码器必须在比特流(bit stream)中将哈夫曼编码树传送给解码器，或者解码器必须使用其与编码器事先约定好的哈夫曼编码树。

然而，随着时代的进步，所需要压缩的数据量愈来愈庞大，因此若是在比特流中传送哈夫曼编码树，则数据的压缩率会被大大地降低。虽然，在解码器中预先存储庞大的哈夫曼编码树可以解决压缩率被降低的问题，但是，预先将庞大的哈夫曼编码树存储于解码器中则会大量地占据整个解码器或图像解码器的硬件资源。

为了解决上述的问题，范式哈夫曼编码(canonical Huffman coding)是由Schwartz[1964]所提出，范式哈夫曼编码跟哈夫曼编码同样属于最佳化前置编码(optimal prefix coding)及非等长编码(variable length coding)。范式哈夫曼编码是哈夫曼编码的一个子集，其主要的特征是在哈夫曼编码中加入一些强制的约定，使得解码器只需要知道很少的信息便能重建出整个哈夫曼编码树。

范式哈夫曼编码最重要的约定就是数字序列属性(numerical sequence property)的约定，此约定规范所有相同长度的码字(codeword)是连续的二进制的数字。举例来说，如果码字长度为4的第一码(first code)为0010，则其他码字长度为4的码字必然为0011、0100、0101、...等。除了数字序列属性的约定之外，范式哈夫曼编码还外加了其他的约定。根据这些约定，范式哈夫曼编码可分成两种类，其中一种为种类1的范式哈夫曼编码，另一种则为种类2的范式哈夫曼编码。

传统范式哈夫曼编码的解码方式多半采用软件解码的方式，然而，在决定码字长度时是采用循序的作法，因此，在码字长度较长时，采用软件解码的方式会因为效率太低，而不能应用于一些有速度需求的系统下，例如：实时系统(real-time system)。

在美国第5,173,695号专利中，Ming-Ting Sun使用硬件架构来对非等长码(Variable Length Code)进行解码。由于范式哈夫曼编码亦属于非等长码的一种，故此解码器也可使用于范式哈夫曼编码的解码上。请参照图1A，图1A是美国第5,173,695号专利所提供的非等长码解码器10的系统方块图。此传统的解码器10包括寄存器101、102、桶状(barrel)寄存器103、加法器104与查找表(lookup table)11。其中，查找表11包括了码字表110、解码符号表(decoded symbol table)111与码字长度表112。范式哈夫曼解码器10中的各元件的耦接关系如同图1A所示，在此便不赘述。

此传统的解码器10利用码字表110去平行比对输入的比特流，然后再将比对所得到的码字长度及解码符号输出。码字表110、码字长度表112与解码符号表111都是由可编程逻辑阵列(programmable logic array)所存储，因此传统的解码器10的解码的速度非常快。此传统的解码器10在每一个时钟周期内可解出一个符号(1 symbol/cycle)，因此能符合许多实时系统的需求。

但随着编码演算法的进步，有人提出了内容可适应性(content adaptive)的概念，此概念主要的诉求是在不同的编码环境底下，各种符号的机率分布应有所不同。因此，在不同的环境下，编码器会采用不同的编码表来进行编码，而解码器则必须选择对应的编码表来进行解码。例如在VC-1的规格中，总共会有8个交流(AC)编码表，且VC-1会根据量化参数(quantization parameter，简称QP)或画面间与画面内(inter/intra)的差异性来决定使用那一个AC编码表来编码。

一些近期的图像编码标准(video coding standard)，例如H.264及VC-1都有使用到这个概念。如果要用美国第5,173,695号专利的概念来实作一个具有内容可适应性的解码器，则必须加入了一个编码表选择信号及两个多工器来选择正确的解码符号。

请参照图1B，图1B是利用美国第5,173,695号专利的概念所实作的一个具有内容可适应性的解码器20的系统方块图。解码器20包括寄存器201、202、桶状寄存器203、加法器204、第一查找表21、第二查找表22、第三查找表23、第四查找表24与多工器205、206。其中，第一至第四查找表21～24存储了其对应的不同编码表的内容，例如，第一查找表21包括了其对应的编码表中的码字表、解码符号表与码字长度表。解码器20中的各元件的耦接关系如同图1B所示，在此便不赘述。

解码器20是利用可编程逻辑阵列来平行比对输入的比特流，每一个查找表21～24皆会输出一个解码符号与码字长度，而编码表选择信号Table_sel则用以控制多工器205与206选择一个正确的解码符号与码字长度。然而，随着编码表的增加，此种实施方式的硬件成本也会等比例成长。虽然此种实施方式可适用于所有的非等长码解码(variable length decoding)且易于实作，不过在内容可适应性编码(content adaptive coding)的应用下，其硬件成本会增大许多。

虽然，美国第5,173,695号专利所提供的解码器的解码时间快速，其硬件易于实作，且用途广泛，甚至可用来实作所有非等长码的解码器。但是，在范式哈夫曼编码的解码器的实作上，由于没有好好地利用到范式哈夫曼编码不需要存储整个编码二元树的特性，所以，使用美国第5,173,695号专利所提供的解码器来实作范式哈夫曼解码器时，会有硬件成本过高的问题。

因此，在美国第6,657,569号专利中，Mark L.Barnett提出了一个利用硬件加速解码的范式哈夫曼解码器。请参照图2，图2是美国第6,657,569号专利所提供的范式哈夫曼解码器30的系统方块图。范式哈夫曼解码器30包括了第一码寄存器301、符号指标寄存器302、比较器330～33N、减法器350～35N、加法器340～34N与多工器312。其中，范式哈夫曼解码器30中各元件之间的耦接关系如同图2所示，便不再赘述。

外部的存储器会记录多个不同的编码表，而每一个编码表有其对应的第一码表(first code table)、符号指标表(symbol pointer table)与符号表(symbol table)。第一码寄存器301会自外部的存储器所存储的多个第一码表中选择一个与目前编码表对应的第一码表，其中，所选择的第一码表中记录了码字长度为1至N+1的第一码FIRSTCODE[0]～FIRSTCODE[N]。指标寄存器302自外部的存储器所存储的多个符号指标表中选择一个与目前编码表对应的符号指标表，其中，指标寄存器302仅存储与第一码寄存器301所对应的多个第一码的符号指标SYM_PTR[0]～SYM_PTR[N]，其中，SYM_PTR[i]表示码字长度为i+1的第一码的符号指标，i为0至N的整数。

范式哈夫曼解码器30是利用范式哈夫曼编码的特性，去平行比较所有的第一码以及输入的比特流，然后利用多工器312去选择出正确的码字长度以及地址信号。最后，以所得到的地址信号到外部存储器中读取正确的解码符号。

由于范式哈夫曼解码器30的输入及输出都必须对外部的存储器进行存取，所以在使用范式哈夫曼解码器30的系统中，所有的存储器存取都必须通过仲裁器(arbiter)的仲裁来决定存取存储器的权力，因此速度上会比较慢。因此，在一些实时系统中，范式哈夫曼解码器30可能达不到速度的需求。另外，范式哈夫曼解码器30只能对种类2的范式哈夫曼编码作解码，而且当范式哈夫曼解码器30运用于图像解码器时，为了速度上的考量，一般都仅会在解完一个画面后才允许更新对应的编码表的解码信息。因此，范式哈夫曼解码器30在应用与使用上比较不具有通用性。

综上所述，传统的范式哈夫曼解码器无法兼顾硬件成本与解码效率，而且也无法使其具有通用性。

发明内容

本发明的示范实施例提供一种可适应性范式哈夫曼解码器，此可适应性范式哈夫曼解码器包括符号索引值产生器、内容选择器与符号表缓冲存储电路。其中，内容选择器耦接于符号索引值产生器，符号表缓冲存储电路耦接于符号索引值产生器与内容选择器。内容选择器用以输出内容选择信号。符号索引值产生器用以存储多个编码表的解码信息，并且根据内容选择信号自此多个解码信息中选择对应解码信息。符号表缓冲存储电路根据内容选择信号自外部存储器所存储的多个符号表中读取对应符号表，并存储此对应符号表。之后，符号索引值产生器接收比特流，并根据对应解码信息对比特流解码，以解得符号索引值。接着，符号表缓冲存储电路根据符号索引值自对应符号表中解得输出符号。

根据本发明的示范实施例，上述的符号索引值产生器包括比较器电路、多工器、符号索引值计算电路与解码信息产生器。其中，多工器耦接于比较器电路，符号索引值计算电路耦接于多工器，而解码信息产生器耦接于内容选择器。解码信息产生器用以存储多个编码表的解码信息，并根据内容选择信号自多个解码信息中选择对应解码信息。比较器电路具有1至N个位的N个比较器，用以比较比特流与N个第一码的大小，以产生N个选择信号。多工器根据N个选择信号与N个识别信号自N个第一码中选择码字长度为L的第一码与自N个第一码索引值中选择码字长度为L的第一码索引值，其中，N大于等于2，L为小于等于N的自然数，且N个识别信号用以指示码字长度为1至N的N个第一码是否存在。符号索引值计算电路根据码字长度为L的第一码索引值、码字长度为L的第一码与比特流中的L个位所形成的码字计算出符号索引值。

本发明的示范实施例提供一种图像解码器，此图像解码器包括可适应性范式哈夫曼解码器与解码控制器。其中，可适应性范式哈夫曼解码器包括符号索引值产生器、内容选择器与符号表缓冲存储电路。其中，内容选择器耦接于符号索引值产生器，符号表缓冲存储电路耦接于符号索引值产生器与内容选择器，而解码控制器耦接于符号索引值产生器与符号表缓冲存储电路。内容选择器用以输出内容选择信号。符号索引值产生器用以存储多个编码表的解码信息，并根据内容选择信号自多个解码信息中选择对应解码信息。符号索引值产生器更用以接收比特流，并根据对应解码信息对比特流进行解码，以解得符号索引值。符号表缓冲存储电路根据内容选择信号自外部存储器所存储的多个符号表中读取对应符号表，存储对应符号表，并根据符号索引值自对应符号表中解得输出符号。解码控制器用以控制符号索引值产生器与符号表缓冲存储电路。

根据本发明的示范实施例，上述的图像解码器还包括主要控制器。主要控制器耦接于解码控制器，主要控制器自外部存储器读取比特流的标头，并对标头进行解码，以获得初始信号。其中，内容选择器接收初始信号，并根据初始信号决定内容选择信号。

根据本发明的示范实施例，其中，主要控制器在对标头进行解码后，还输出起始信号给解码控制器，解码控制器在收到起始信号后，解码控制器告知符号索引值产生器选择对应解码信息与告知符号表缓冲存储电路自外部存储器中读取及存储对应符号表。

根据本发明的示范实施例，其中，当符号索引值产生器选择对应解码信息与符号表缓冲存储电路自外部存储器中读取及存储对应符号表后，解码控制器告知符号索引值产生器开始对比特流进行解码，以获得符号索引值，解码控制器还告知符号表缓冲存储电路根据符号索引值自其所存储的对应符号表中找出输出符号。

根据本发明的示范实施例，其中，如果比特流解码完毕或者对应符号表及对应解码信息的其中之一需要更新时，解码控制器更送出结束信号给主要控制器。主要控制器在收到结束信号后，主要控制器自外部存储器读取一个新的标头。

本发明的示范实施例提供一种可适应性范式哈夫曼解码方法。首先，提供第一快取空间存储多个编码表的解码信息。之后，根据内容选择信号自多个解码信息中选择对应解码信息。接着，根据内容选择信号自外部存储器所存储的多个符号表中选择对应符号表，并将对应符号表存储于第二快取空间。之后，接收比特流，并根据对应解码信息对比特流解码，以解得符号索引值。接着，根据符号索引值自对应符号表中解得输出符号。

综上所述，与传统的可适应性范式哈夫曼解码器及其方法与图像解码器相比，本发明的示范实施例所提供的可适应性范式哈夫曼解码器及其方法与图像解码器比较具有通用性，而且，其速度可以达到许多实时系统的需求。另外，本发明的示范实施例所提供的可适应性范式哈夫曼解码器及其方法与图像解码器可以随着内容选择信号的变化选择适当的编码表的对应解码信息来解码，且不会随着编码表增多而需增加硬件的成本。

为让本发明的上述特征和优点能更明显易懂，下文特举示范实施例，并配合附图，作详细说明如下。

附图说明

图1A是美国第5,173,695号专利所提供的范式哈夫曼解码器10的系统方块图。

图1B是利用美国第5,173,695号专利的概念所实作的一个具有内容可适应性的解码器20的系统方块图。

图2是美国第6,657,569号专利所提供的范式哈夫曼解码器30的系统方块图。

图3是本发明的示范实施例所提供的一个可适应性范式哈夫曼解码器40的系统方块图。

图4是本发明的示范实施例所提供的一个图像解码器50的系统方块图。

图5是本发明的示范实施例所提供的一个图像解码方法的流程图。

图6是本发明的示范实施例所提供的一个可适应性范式哈夫曼解码方法的流程图。

图7是图6的步骤S74的流程图。

【主要元件符号说明】

10：范式哈夫曼解码器

101、102：寄存器

103：桶状寄存器

104：加法器104

11：查找表

110：码字表

111：解码符号表

112：码字长度表

20：解码器

201、202：寄存器

203：桶状寄存器

204：加法器

21：第一查找表

22：第二查找表

23：第三查找表

24：第四查找表

205、206：多工器

30：范式哈夫曼解码器

301：第一码寄存器

302：符号指标寄存器

330～33N：比较器

340～34N：加法器

350～35N：减法器

312：多工器

40：可适应性范式哈夫曼解码器

41：符号索引值产生器

42：内容选择器

43：符号表缓冲存储电路

440：外部存储器

410：比较器电路

411：比特流寄存器

412：多工器

413：符号索引值计算电路

414：解码信息产生器

CMP_1～CMP_N：比较器

SUB_1：减法器

ADD_1：加法器

50：图像解码器

51：可适应性范哈夫曼解码器

52：解码控制器

53：主要控制器

510：符号索引值产生器

511：内容选择器

512：符号表缓冲存储电路

599：外部存储器

S60～S65：步骤流程

S70～S76：步骤流程

S741～S743：步骤流程

具体实施方式

在介绍本发明的示范实施例所提供的可适应性范式哈夫曼解码器及其方法与图像解码器之前，在此先介绍种类1与种类2的范式哈夫曼编码。

种类1的范式哈夫曼编码除了数字序列属性的约定外，还有额外的两个约定。第一个约定是从码字长度最小的第一个符号开始编码，且此码字的数值必须为0。第二个约定是为了尽可能地利用编码空间而规范的约定，其约定是码字长度为L的第一码可以从码字长度为L-n的最后一码得出。其中，码字长度为L-1、L-2、...、L-n+1的码字为不存在于哈夫曼编码树的码字，n为1至L-1的整数的其中之一。

若假设码字长度为L-1的码字存在于哈夫曼编码树中，则码字长度为L的第一码等于码字长度为L-1的最后一码加1之后再左移一位所形成的码字。此时，码字长度为L的第一码可用数学公式可以表示如下：

FIRSTCODE[L]＝(LASTCODE[L-1]+1)＜＜1

其中，FIRSTCODE[L]表示码字长度为L的第一码，LASTCODE[L-1]表示码字长度为L-1的最后一码，“＜＜1”表示左移一位的运算子。

若假设码字长度为L-1、L-2、...、L-n+1的码字不存在于哈夫曼编码树中，而码字长度为L-n的码字有存在于哈夫曼编码树中，则码字长度为L的第一码为码字长度等于L-n的最后一码加1之后再右移n位所形成的码字。此时，码字长度为L的第一码可用数学公式可以表示如下：

FIRSTCODE[L]＝(LASTCODE[L-n]+1)＜＜n

其中，FIRSTCODE[L]表示码字长度为L的第一码，LASTCODE[L-n]表示码字长度为L-n的最后一码，“＜＜n”表示左移n位的运算子。

种类2的范式哈夫曼编码和种类1的范式哈夫曼编码主要的差别是在于开始编码的起点不同，种类2的范式哈夫曼编码除了数字序列属性的约定外，还有额外的两个约定。第一个约定是从码字长度最大的第一个符号开始编码，且此码字的数值必须为0。第二个约定是为了尽可能地利用编码空间而规范的约定，其约定是码字长度为L的第一码可以从码字长度为L+n的最后一码得出。其中，码字长度为L+1、L+2、...、L+n-1的码字为不存在于哈夫曼编码树的码字，n为自然数。

如果假设码字长度为L+1的码字存在于哈夫曼编码树中，则码字长度为L的第一码等于码字长度为L+1的最后一码右移一位后再加1所形成的码字。此时，码字长度为L的第一码可用数学公式可以表示如下：

FIRSTCODE[L]＝(LASTCODE[L+1]＞＞1)+1

其中，FIRSTCODE[L]表示码字长度为L的第一码，LASTCODE[L+1]表示码字长度为L+1的最后一码，“＞＞1”表示右移一位的运算子。

若假设码字长度为L+1、L+2、...、L+n-1的码字不存在于哈夫曼编码树中，而码字长度为L+n的码字有存在于哈夫曼编码树中，则码字长度为L的第一码为码字长度等于L+n的最后一码右移n位后再加1所形成的码字。此时，码字长度为L的第一码可用数学公式可以表示如下：

FIRSTCODE[L]＝(LASTCODE[L+n]＞＞n)+1

其中，FIRSTCODE[L]表示码字长度为L的第一码，LASTCODE[L+n]表示码字长度为L+n的最后一码，“＞＞n”表示右移n位的运算子。

接着，请参照图3，图3是本发明的示范实施例所提供的一个可适应性范式哈夫曼解码器40的系统方块图。此可适应性范式哈夫曼解码器40包括符号索引值产生器41、内容选择器42与符号表缓冲存储电路43，其中，内容选择器42耦接于符号索引值产生器41，符号表缓冲存储电路43耦接于符号索引值产生器41与内容选择器42。

内容选择器42可以根据量化参数(quantization parameter，简称QP)或画面间与画面内(inter/intra)的差异性等来决定内容选择信号，并在决定内容选择信号之后，将此内容选择信号输出给符号索引值产生器41与符号表缓冲存储电路43。符号索引值产生器41在收到内容选择信号之后，会根据内容选择信号自其存储多个编码表的解码信息中选择一个对应解码信息来使用，此对应解码信息对应于比特流在编码时所使用的编码表；同时，符号表缓冲存储电路43会根据内容选择信号自外部存储器440所存储的多个符号表中读取一个对应符号表，并存储此对应符号表。例如，符号表缓冲存储电路43根据内容选择信号所读取到的对应符号表为第二符号表，则符号表缓冲存储电路43会存储此第二符号表。

在图3的示范实施例中，所选择到的编码表的对应解码信息包括码字长度为1～N的N个第一码FIRSTCODE[1]～FIRSTCODE[N]、N个第一码索引值FCODE_INDX[1]～FCODE_INDEX[N]与N个识别信号VALID[1]～VALID[N]。其中，N个识别信号VALID[1]～VALID[N]用以指示码字长度为1至N的N个第一码FIRSTCODE[1]～FIRSTCODE[N]是否存在，而N个第一码索引值FCODE_INDX[1]～FCODE_INDEX[N]分别表示的N个第一码FIRSTCODE[1]～FIRSTCODE[N]的索引值。

在符号索引值产生器41选择完对应解码信息与符号表缓冲存储电路43存储完对应符号表之后，符号索引值产生器41会接收比特流，并根据对应解码信息对比特流解码，以解得符号索引值SYMBOL_INDEX。接着，符号表缓冲存储电路43会根据符号索引值SYMNOL_INDEX自对应符号表中解得输出符号。

另外，值得注意的是，由于数字序列属性的约定与种类1或种类2的范式哈夫曼编码的其他约定，符号索引值产生器41不需要存储每一个编码表的所有信息，符号索引值产生器41仅需存储每一个编码表的解码信息即可。外部存储器440所存储的多个符号表中的每一个符号表存储了多个符号与其多个对应的索引值，因此，符号表缓冲存储电路43可以根据符号索引值SYMBOL_INDEX自其存储的对应符号表中找到对应的输出符号。其中，符号表缓冲存储电路43事实上是一个可以根据内容选择信号进行更新的查找表。

接着，在此介绍符号索引值产生器41的详细结构。符号索引值产生器41包括比较器电路410、比特流寄存器411、多工器412、符号索引值计算电路413与解码信息产生器414。其中，比特流寄存器411耦接于比较器电路410、多工器412与符号索引值计算电路413。解码信息产生器414耦接于内容选择器42与多工器412，而多工器择耦接于比较器电路410。

比特流寄存器411用以暂存比特流，并输出比特流的第一至第N个位给比较器电路410。在多工器412决定比特流的码字长度L后，多工器412会告知比特流寄存器411输出比特流的第一至第L个位所形成的码字NEXTBIT[L]给符号索引值计算电路413。其中，要注意的是，在多工器412告知比特流寄存器411输出比特流的第一至第L个位所形成的码字NEXTBIT[L]给符号索引值计算电路413后，会将其暂存的比特流移位L个位，以等待下一次的解码。换句话说，就是此次输出的码字NEXTBIT[L]将不会继续存在于比特流寄存器411。

解码信息产生器414用以存储多个编码表的解码信息，并根据内容选择信号自此多个编码表的解码信息中选择对应解码信息。解码信息产生器414所选到的对应解码信息包括码字长度为1～N的N个第一码FIRSTCODE[1]～FIRSTCODE[N]、N个第一码索引值FCODE_INDX[1]～FCODE_INDEX[N]与N个识别信号VALID[1]～VALID[N]，解码信息产生器414会将所选到的对应解码信息提供给多工器412。

比较器电路410具有1至N个位的N个比较器CMP_1～CMP_N，比较器电路410用以比较比特流与N个第一码FIRSTCODE[1]～FIRSTCODE[N]的大小，以产生N个选择信号，其中，N大于等于2。比较器CMP_1会比较比特流中第一个位所形成的码字与码字长度为1的第一码FIRSTCODE[1]的大小，并输出一个选择信号给多工器412。比较器CMP_N会比较比特流中第一至第N个位所形成的码字与码字长度为N的第一码FIRSTCODE[N]的大小，并输出一个选择信号给多工器412。其他的比较器CMP_2～CMP_N-1则可以依此类推，在此便不多说明。

在图3的示范实施例中，这N个选择信号事实上仅是0或1的信号，这N个选择信号用以表示比较后的结果，并藉此告知多工器412以决定码字长度L。多工器412根据N个选择信号与N个识别信号VALID[1]～VALID[N]自N个第一码FIRSTCDE[1]～FIRSTCODE[N]中选择码字长度为L的第一码FIRSTCODE[L]与自N个第一码索引值中FCODE_INDEX[1]～FCODE_INDEX[N]选择码字长度为L的第一码索引值FCODE_INDEX[L]，其中，L为小于等于N的自然数。

另外，值得注意的是，在有些编码的情况下，有些长度的码字并不存在，此时某一些比较器所输出的选择信号并没有任何意义，但却会影响解码的结果。因此在解码信息产生器414中会产生N个识别信号VALID[1]～VALID[N]。例如，如果在一个编码表中，并没有码字长度为3跟5的码字，此时识别信号VALID[3]与VALID[5]会等于1，其余的则会等于0。有了这些识别信号VALID[1]～VALID[N]之后，多工器412会根据每一个比较器CMP_1～CMP_N产生的选择信号与识别信号VALID[1]～VALID[N]来决定码字的长度L。当识别信号VALID[i]等于1时，则多工器412会无视(ignore)比较器CMP_i所输出的选择信号，而此码字长度i将不可能被决定为码字的码字长度。

符号索引值计算电路413根据码字长度为L的第一码索引值FCODE_INDEX[L]、码字长度为L的第一码FIRSTCODE[L]与比特流中的L个位所形成的码字NEXTBIT[L]计算出符号索引值SYMBOL_INDEX。其中，要注意的是不管是采用种类1或种类2的范式哈夫曼编码，在解码时，该符号索引值SYMBOL_INDEX皆等于第一码索引值FCODE_INDEX[L]与码字NEXTBIT[L]的总和减去第一码FIRSTCODE[L]的值，亦即SYMBOL_INDEX＝NEXTBIT[L]+FCODE_INDEX[L]-FIRSTCODE[L]。

因此，符号索引值计算电路413包括减法器SUB_1与加法器ADD_1。其中，减法器SUB_1用以将码字NEXTBIT[L]减去第一码FIRSTCODE[L]，而加法器ADD_1则用以将减法器SUB_1的输出加上第一码索引值FCODE_INDEX[L]。当然，上述的符号索引值计算电路413的实施方式仅是本发明之一种示范实施例，并非用以限定本发明，根据上述SYMBOL_INDEX＝NEXTBIT[L]+FCODE_INDEX[L]-FIRSTCODE[L]的结论，本领域技术人员可以采用其他的方式来实施符号索引值计算电路413，或者仅对图3的符号索引值计算电路413做适当的修改。

接着，请参照表一与表二，表一是多个符号使用种类1的范式哈夫曼编码的一个编码表，而表二表示对应表一的编码表所需存储的解码信息。其中，表二的码字长度为L的第一码FIRSTCODE[L]是用十进位表示。另外，虽然码字为1的第一码FIRSTCODE[1]不存在于哈夫曼编码树中，但因为有识别信号VALID[1]的指示，在此可以将码字长度为1的第一码FIRSTCODE[1]设为0，而其第一码索引值FCODE_INDEX[1]则设为0。

表一

  符号  索引  值  0  1  2  3  4  5  6  7  8  9  10  码字  长度  2  3  3  3  4  4  4  4  4  5  5  码字  00  010  011  100  1010  1011  1100  1101  1110  11110  11111  符号  a  b  c  d  e  f  g  h  i  j  k

表二

  码字长度(L)  1  2  3  4  5  FIRSTCODE[L]  0  0  2  10  30  FCODE_INDEX[L]  0  0  1  4  9

在此，以种类1的范式哈夫曼编码的一个编码表为例，说明可适应性范式哈夫曼解码器40如何对所接收到的比特流进行解码。假设可适应性范式哈夫曼解码器40中的比较器电路410具有1至5位的5个比较器，内容选择信号指示符号表缓冲存储电路43所存储的符号表包括表一的符号与符号索引值的全部，而解码信息产生器414所选择到的对应解码信息则包括表二的第一码FIRSTCODE[1]～FIRSTCODE[5]、第一码索引值FCODE_INDEX[1]～FCODE_INDEX[5]以及5个识别信号VALID[1]～VALID[5]。其中，识别信号VALID[2]～VALID[5]为0，用以表示码字长度为2～5的第一码FIRSTCODE[2]～FIRSTCODE[5]存在于哈夫曼编码树中，而识别信号VALID[1]为1，用以表示码字长度为1的第一码FIRSTCODE[1]不存在于哈夫曼编码树中。

如果接收到的比特流为{001001101}，则比较器电路410会接收比特流中的前5个位{01101}，并输出5个选择信号给多工器412。比较器CMP_1比较第一码FIRSTCODE[1]与比特流中第一个位{1}，并输出选择信号，其选择信号为1。比较器CMP_2比较第一码FIRSTCODE[2]与比特流中前两个位{01}，并输出选择信号，其选择信号为1。比较器CMP_3比较第一码FIRSTCODE[3]与比特流中前3个位{101}，并输出选择信号，其选择信号为1。比较器CMP_4比较第一码FIRSTCODE[4]与比特流中前4个位{1101}，并输出选择信号，其选择信号为1。比较器CMP_5比较第一码FIRSTCODE[5]与比特流中前两个位{01101}，并输出选择信号，其选择信号为0。

根据比较器电路410所输出的5个选择信号，多工器412可以得知目前所要解码的符号的码字长度为4。因为识别信号VAILD[4]为0，且多工器412知道目前所要解码的符号的码字长度为4，所以此多工器412会选择第一码FIRSTCODE[4]与第一码索引值FCODE_INDEX[4]作为输出。接着，符号索引值计算电路413会根据择第一码FIRSTCODE[4]、第一码索引值FCODE_INDEX[4]与接收比特流中前4个位所形成的码字NEXTBIT[4]计算出符号索引值SYMBOL_INDEX。

此时，码字NEXTBIT[4]的十进位值是13，而第一码FIRSTCODE[4]、第一码索引值FCODE_INDEX[4]分别为10与4，因此，符号索引值SYMBOL_INDEX＝13+4-10＝7。接着，符号表缓冲存储电路43根据符号索引值SYMBOL_INDEX在其存储的对应符号表中找出输出符号，以顺利地完成比特流中前4个位的解码。在这个示范实施例中，符号索引值SYMBOL_INDEX为7时，输出符号为h(参照表二)。

在解完比特流中前4个位{1101}后，这4个位{1101}就不会继续存在比特流寄存器411。因此，接下来的比特流仅剩下5个位{00100}。接着，可适应性范式哈夫曼解码器40会针对之后的5个位{00100}进行解码，而可适应性范式哈夫曼解码器40针对5个位{00100}进行解码的解码方式，可以从前面的叙述得知，因此在此便不多赘述。

接着，请参照表三与表四，表三是多个符号使用种类2的范式哈夫曼编码的一个编码表，而表四表示对应表三的编码表所需存储的解码信息。其中，表四的码字长度为L的第一码FIRSTCODE[L]是用十进位表示。另外，虽然码字为1的第一码FIRSTCODE[1]不存在于哈夫曼编码树中，但因为有识别信号VALID[1]的指示，在此可以将码字长度为1的第一码FIRSTCODE[1]设为30，其第一码索引值FCODE_INDEX[1]则设为12。

表三

  符号  索引  值  0  1  2  3  4  5  6  7  8  9  10  码字  长度  5  5  4  4  4  4  4  3  3  3  2  码字  00000  00001  0001  0010  0011  0100  0101  011  110  101  11  符号  a  b  c  d  e  f  g  h  i  j  k

表四

  码字长度(L)  5  4  3  2  1  FIRSTCODE[L]  0  0  2  10  30  FCODE_INDEX[L]  0  2  7  10  12

在此，以种类2的范式哈夫曼编码的一个编码表为例，说明可适应性范式哈夫曼解码器40如何对所接收到的比特流进行解码。假设可适应性范式哈夫曼解码器40中的比较器电路410具有1至5位的5个比较器，内容选择信号指示符号表缓冲存储电路43所存储的符号表包括表一的符号与符号索引值的全部，而解码信息产生器414所选择到的对应解码信息则包括表二的第一码FIRSTCODE[1]～FIRSTCODE[5]、第一码索引值FCODE_INDEX[1]～FCODE_INDEX[5]以及5个识别信号VALID[1]～VALID[5]。其中，识别信号VALID[2]～VALID[5]为0，用以表示码字长度为2～5的第一码FIRSTCODE[2]～FIRSTCODE[5]存在于哈夫曼编码树中，而识别信号VALID[1]为1，用以表示码字长度为1的第一码FIRSTCODE[1]不存在于哈夫曼编码树中。

如果接收到的比特流为{1101100001}，则比较器电路410会接收比特流中的前5个位{00001}，并输出5个选择信号给多工器412。比较器CMP_1比较第一码FIRSTCODE[1]与比特流中第一个位{1}，并输出选择信号，其选择信号为0。比较器CMP_2比较第一码FIRSTCODE[2]与比特流中前两个位{01}，并输出选择信号，其选择信号为0。比较器CMP_3比较第一码FIRSTCODE[3]与比特流中前3个位{001}，并输出选择信号，其选择信号为0。比较器CMP_4比较第一码FIRSTCODE[4]与比特流中前4个位{0001}，并输出选择信号，其选择信号为0。比较器CMP_5比较第一码FIRSTCODE[5]与比特流中前两个位{00001}，并输出选择信号，其选择信号为1。

根据比较器电路410所输出的5个选择信号，多工器412可以得知目前所要解码的符号的码字长度为5。因为识别信号VAILD[5]为0，且多工器412知道目前所要解码的符号的码字长度为5，所以此多工器412会选择第一码FIRSTCODE[5]与第一码索引值FCODE_INDEX[5]作为输出。接着，符号索引值计算电路413会根据择第一码FIRSTCODE[5]、第一码索引值FCODE_INDEX[5]与接收比特流中前5个位所形成的码字NEXTBIT[5]计算出符号索引值SYMBOL_INDEX。

此时，码字NEXTBIT[5]的十进位值是1，而第一码FIRSTCODE[5]、第一码索引值FCODE_INDEX[5]皆为0，因此，符号索引值SYMBOL_INDEX＝1+0-0＝1。接着，符号表缓冲存储电路43根据符号索引值SYMBOL_INDEX在其存储的对应符号表中找出输出符号，以顺利地完成比特流中前4个位的解码。在这个示范实施例中，符号索引值SYMBOL_INDEX为1时，输出符号为b(参照表四)。

在解完比特流中前5个位{00001}后，这5个位{00001}就不会继续存在比特流寄存器411。因此，接下来的比特流仅剩下5个位{11011}。接着，可适应性范式哈夫曼解码器40会针对之后的5个位{11011}进行解码，而可适应性范式哈夫曼解码器40针对5个位{11011}进行解码的解码方式，可以从前面的叙述得知，因此在此便不多赘述。

综上所述，可以知道本发明的示范实施例所提供的可适应性范式哈夫曼解码器40具有通用性，可以用来对种类1或种类2的范式哈夫曼编码的比特流进行解码。另外，所有的符号表存在外部存储器414中，而且符号表缓冲存储电路43可以根据内容选择信号自外部存储器中读取一个对应符号表，因此本发明的示范实施例所提供的可适应性范式哈夫曼解码器40的硬件成本可以被大量减少，而且其速度可以符合一般实时系统的要求。

接着，请参照图4，图4是本发明的示范实施例所提供的一个图像解码器50的系统方块图。图像解码器50包括可适应性范式哈夫曼解码器51、解码控制器52与主要控制器53。其中，可适应性范式哈夫曼解码器51耦接于解码控制器52与主要控制器53，主要控制器53耦接于解码控制器52。可适应性范式哈夫曼解码器51包括符号索引值产生器510、内容选择器511与符号表缓冲存储电路512。其中，内容选择器511耦接于主要控制器53、符号索引值产生器510与符号表缓冲存储电路512，符号表缓冲存储电路512耦接于外部存储器599、解码控制器52与符号索引值产生器510，而符号索引值产生器510耦接于解码控制器52。

解码控制器52用以符号索引值产生器510与符号表缓冲存储电路512，解码控制器52利用一些控制信号向符号索引值产生器510与符号表缓冲存储电512路进行沟通，以藉此确认彼此间的状态，并指示符号索引值产生器510与符号表缓冲存储电路512所进行的工作。主要控制器53自外部存储器599读取标头，并对标头进行解码，以获得初始信号Content_set、起始信号Start_set。另外，主要控制器53更从解码控制器52接收结束信号Finish_signal。其中，标头可以是要进行解码的比特流的标头，标头可以是欲解码的比特流中的前面几个位，或者是独立传送的标头。

可适应性范式哈夫曼解码器51的功能与图3所提供的可适应性范式哈夫曼解码器40的功能相近，且其符号索引值产生器510、内容选择器511与符号表缓冲存储电路512的功能亦与图3所述的符号索引值产生器41、内容选择器42与符号表缓冲存储电路43的功能相近。其不同的地方仅在于，图5所述的符号索引值产生器510、内容选择器511与符号表缓冲存储电路512是建立在图像解码器50中，因此，符号索引值产生器510、内容选择器511与符号表缓冲存储电路512会受到主要控制器53与解码控制器52的控制。当然，符号索引值产生器510、内容选择器511与符号表缓冲存储电路512的实施方式可以参考图3所述的符号索引值产生器41、内容选择器42与符号表缓冲存储电路43的实施方式，只是，必须额外加入控制电路而已。

当主要控制器53自外部存储器599读取标头，并对标头进行解码后，会分别输出初始信号Content_set与起始信号Start_signal给内容选择器511及解码控制器52。内容选择器511在收到初始信号Content_set后，会根据初始信号Content_set产生内容选择信号给符号索引值产生器510及符号表缓冲存储电路512。其中，内容信号可能夹带了量化参数、画面间的差异性或画面内的差异性的信息，通过这些信息，符号索引值产生器510可以自多个编码表中的解码信息选择一个对应编码表的对应解码信息，而符号表缓冲存储电路512则可以自外部存储器599所存储的多个符号表中选择一个对应符号表。

解码控制器52在接收到起始信号Start_signal之后，才会允许可适应性范式哈夫曼解码器51对比特流进行解码。首先，解码控制器52会告知符号索引值产生器510根据内容选择信号选择对应解码信息，同时，解码控制器52亦会告知符号表缓冲存储电路512自外部存储器599中读取及存储对应符号表。

在符号索引值产生器510根据内容选择信号选择对应解码信息与符号表缓冲存储电路512自外部存储器599中读取及存储对应符号表之后，解码控制器52才会允许符号索引值产生器510开始对比特流进行解码，以获得符号索引值。接着，在符号索引值计算完毕后，解码控制器52会告知符号表缓冲存储电路512根据符号索引值自其所存储的对应符号表中找出输出符号。

之后，解码控制器52会判断比特流解码是否完毕或者对应符号表及对应解码信息是否需要更新。如果比特流解码完毕，或者应符号表及对应解码信息其中之一需要更新时，则解码控制器52会送出结束信号Finish_signal给主要控制器53。主要控制器53在收到结束信号Finish_signal后，主要控制器53会从外部存储器读取一个新的标头，并产生新的初始信号Content_set与起始信号Start_signal。接着，可适应性范式哈夫曼解码器51便能够开始对之后比特流进行解码。

接着，请参照图5，图5是本发明的示范实施例所提供的一个图像解码方法的流程图。此示范实施例所提供的图像解码方法是根据图4的图像解码器50所得到的，然而，图5的图像解码方法仅是本发明的一个示范实施例，并非用以限定本发明。

首先，在步骤S60中，主要控制器53自外部存储器599中读取比特流并对比特流的标头进行解码。接着，在步骤S61中，内容选择器511根据标头解码后所挟带的信息设定内容选择信号。接着，在步骤S62中，主要控制器53送出起始信号Start_signal给解码控制器52，解码控制器52接着告知第一快取空间(也就是前述的符号索引值产生器510内的解码信息产生器)选择对应解码信息与告知第二快取空间(也就是前述的符号表缓冲存储电路512)自外部存储器599选择对应符号表。

接着，在步骤S63中，解码控制器52告知符号索引值产生器510根据对应解码信息对比特流进行解码，以获得符号索引值。之后，在步骤S64中，解码控制器52告知符号表缓冲存储电路512根据符号索引值自对应符号表中找出输出符号。之后，在步骤S65中，解码控制器52判断比特流是否解码完毕或对应解码信息与对应符号表其中之一是否需要更新。如果比特流解码完毕，或者，对应解码信息与对应符号表其中之一需要更新，则解码控制器52会送出结束信号Finish_signal给主要控制器53，之后，便进行步骤S60。如果比特流尚未解码完毕，且对应解码信息与对应符号表皆不需要更新时，则回到步骤S63。

之后，请参照图6，图6是本发明的示范实施例所提供的一个可适应性范式哈夫曼解码方法的流程图。此示范实施例所提供的图像解码方法是根据图3的可适应性范式哈夫曼解码器40加上图4的图像解码器50的观点所产生的，然而，图4的图像解码方法仅是本发明的一个示范实施例，并非用以限定本发明。

首先，在步骤S70中，根据量化参数、画面间的差异性或画面内的差异性来决定内容选择信号。之后，在步骤S71中，提供第一快取空间存储多个编码表的解码信息。其中，第一快取空间可以是图3中的解码信息产生器414。在步骤S72中，根据内容选择信号自多个解码信息中选择对应解码信息。换句话说，就是自多个编码表中选择一个对应编码表，并存储此对应编码表的对应解码信息。

在步骤S73中，根据内容选择信号自外部存储器所存储的多个符号表中选择对应符号表，并将对应符号表存储于第二快取空间。其中，第二快取空间可以是图3中的符号表缓冲存储电路43。接着，在步骤S74中，接收比特流，并根据对应解码信息对比特流解码，以解得符号索引值。在步骤S75中，根据符号索引值自对应符号表中解得输出符号。接着，在步骤S76中，判断比特流解码完毕或者对应符号表及对应解码信息的其中之一需要更新。如果比特流解码完毕，或者对应符号表及对应解码信息的其中之一需要更新，则回到步骤S70；若比特流尚未解码完毕且对应符号表及对应解码信息皆不需要更新，则回到步骤S74。

接着，请参照图7，图7是图6的步骤S74的流程图。图6的步骤S74可以用步骤S741～S743来实现，然而，图7流程图并非用以限定步骤S74。在步骤S741中，比较比特流中前i个位所形成的码字与码字长度为i的第一码的大小，以产生选择信号，其中，i为1至N的整数。执行步骤S741所产生的功能相当于图3的比较器电路410的功能，因此，在步骤S741中，总共会产生N个选择信号。

接着，在步骤S742中，根据N个选择信号与N个识别信号自N个第一码中选择码字长度为L的第一码与自N个第一码索引值中选择码字长度为L的第一码索引值，其中，L为小于等于N的自然数。执行步骤S741所产生的功能相当于图3的多工器412的功能。之后，在步骤S743中，根据码字长度为L的第一码索引值、码字长度为L的第一码与比特流中的L个位所形成的码字计算出符号索引值。执行步骤S743所产生的功能相当于图3的符号索引值计算电路413的功能。通过图7所提供的详细流程，符号索引值便能被正确地计算出来，接着，便可以根据符号索引值来解得正确的输出符号。

综上所述，与传统的可适应性范式哈夫曼解码器及其方法与图像解码器相比，本发明的示范实施例所提供的可适应性范式哈夫曼解码器及其方法与图像解码器比较具有通用性，能够对经过种类1或种类2的范式哈夫曼编码的比特流进行解码。

除此之外，示范实施例所提供的可适应性范式哈夫曼解码器利用快取的概念，根据内容选择信号来选择对应解码信息与对应符号表，使得其解码的速度较传统的可适应性范式哈夫曼解码器来得快，因此能够达到许多实时系统的需求。

另外，本发明的示范实施例所提供的可适应性范式哈夫曼解码器及其方法与图像解码器可以随着内容选择信号的变化选择适当的编码表的对应解码信息来解码，且不会随着编码表增多而需增加硬件的成本。

虽然本发明已以示范实施例公开如上，然其并非用以限定本发明，本领域技术人员，在不脱离本发明的精神和范围内，当可作些许的更动与润饰，因此本发明的保护范围当视所附权利要求书所界定者为准。