CN109937537B - 编码可变长度符号以实现并行解码 - Google Patents

Abstract

提供了一种方法，其中源系统将多个符号集划分成多个固定宽度数据块。在划分期间，源系统创建相对固定宽度数据块的边界的对应于符号集中的符号的符号边界信息。反过来，源系统基于符号边界信息将固定宽度数据块组合成多路复用比特流，并将多路复用比特流提供给目的地系统。

Description

编码可变长度符号以实现并行解码

背景技术

本公开涉及在源系统上对符号流进行编码，该源系统具有可变长度符号以允许目标系统使用多个解码器来对符号流进行解码。

计算机系统使用压缩技术来减少存储在存储器中或通过计算机网络发送到其他计算机系统的比特数目。数据压缩是一种通过将多个比特“压缩”为较小数目的比特来减小数据文件大小的技术。源编码(coding)或编码(encoding)是一种压缩技术，其减少了通过计算机网络传输的比特量，例如数据流。

数据流压缩格式可以使用可变长度“符号”对数据进行编码。由于符号长度可变性，在目的地系统处解码符号的过程本质上是顺序的，因为目的地系统需要解码符号以便确定数据流中下一个符号的起始位置。

发明内容

根据本公开的一个实施例，提供了一种方法，其中源系统将多个符号集划分为多个固定宽度数据块。在划分期间，源系统创建相对于固定宽度数据块的边界的对应于符号集中的符号的符号边界信息。反过来，源系统基于符号边界信息将固定宽度数据块组合成多路复用比特流，并将多路复用比特流提供给目的地系统。

以上是概述，因此必然包含细节的简化、概括和省略；因此，本领域技术人员将理解，该概述仅是说明性的，并不旨在以任何方式进行限制。仅由权利要求限定的本公开的其他方面、发明特征和优点将在以下阐述的非限制性详细描述中变得明显。

附图简要说明

通过参考附图，可以更好地理解本公开，并且本公开的众多目的、特征和优点对于本领域技术人员而言是明显的，其中：

图1是数据处理系统的框图，其中可以实现本文描述的方法；

图2提供了图1中所示的信息处理系统环境的扩展，以说明本文描述的方法可以在网络环境中操作的多种信息处理系统上执行；

图3是描绘将初始符号流转换为多路复用的比特流的源符号编码器以及使用多个解码器将多路复用的比特流转换为解码的符号流的目的地符号解码器的图；

图4是表示利用图3所示的符号编码器和符号解码器的压缩器和解压缩器的高级别图；

图5是描述初始符号流被转换为多路复用比特流的阶段的详细图；

图6是描述将比特流划分为固定比特宽度数据块并产生拉取(pull)定时的流转换器的图；

图7是描述固定宽度多路复用器从多个比特流加载固定比特宽度数据块的方法的图，其顺序与固定比特宽度数据块将如何由目的地固定宽度符号解码器处理一致；

图8是示出源编码器的高级别流程图，该源编码器生成多路复用的比特流，该多路复用的比特流被发送到目的地符号解码器以进行并行解码；

图9是流程图，其示出了流转换器将符号子流转换为具有固定比特宽度数据块的比特流并产生对应于固定比特宽度数据块的拉取定时所采取的步骤；

图10是表示固定宽度多路复用器根据拉取定时信息将多个比特流的固定比特宽度数据块组合成多路复用比特流所采取的步骤的流程图；

图11是表示目的地系统对输入的多路复用比特流进行并行解码的步骤的流程图；以及

图12是示出与比特流划分器接口以请求和处理固定比特宽度数据块的多个固定宽度解码器的示例的图。

具体实施方式

这里使用的术语仅用于描述特定实施例的目的，并不旨在限制本公开。如这里所使用的，单数形式“一(a)”，“一(an)”和“该(the)”旨在也包括复数形式，除非上下文另有明确说明。将进一步理解，当在本说明书中使用时，术语“包括(comprises)”和/或“包含(comprising)”指定所描述的特征、整数、步骤、操作、元件、和/或组件的存在，但不排除存在或者添加一个或多个其他特征、整数、步骤、操作、元素、组件和/或其组合。

以下权利要求中的所有装置或步骤加功能元件的对应结构、材料、动作和等同物旨在包括用于结合具体要求保护的其他要求保护的元件执行功能的任何结构、材料或动作。已经出于说明和描述的目的给出了对本公开的描述，但是并不旨在穷举或将本公开限制于所公开的形式。在不脱离本公开的范围和精神的情况下，许多修改和变化对于本领域普通技术人员将是明显的。选择和描述实施例是为了最好地解释本公开的原理和实际应用，并且使本领域的其他普通技术人员能够理解具有适合于预期的特定用途的各种修改的本公开的各种实施例。

本发明可以是系统、方法和/或计算机程序产品。该计算机程序产品可以包括计算机可读存储介质medium(或介质media)，其上具有计算机可读程序指令，用于使处理器执行本发明的各方面。

计算机可读存储介质可以是可以保持和存储由指令执行设备使用的指令的有形设备。计算机可读存储介质例如可以是――但不限于――电存储设备、磁存储设备、光存储设备、电磁存储设备、半导体存储设备或者上述的任意合适的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：便携式计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、静态随机存取存储器(SRAM)、便携式压缩盘只读存储器(CD-ROM)、数字多功能盘(DVD)、记忆棒、软盘、机械编码设备、例如其上存储有指令的打孔卡或凹槽内凸起结构、以及上述的任意合适的组合。这里所使用的计算机可读存储介质不被解释为瞬时信号本身，诸如无线电波或者其他自由传播的电磁波、通过波导或其他传输媒介传播的电磁波(例如，通过光纤电缆的光脉冲)、或者通过电线传输的电信号。

这里所描述的计算机可读程序指令可以从计算机可读存储介质下载到各个计算/处理设备，或者通过网络、例如因特网、局域网、广域网和/或无线网下载到外部计算机或外部存储设备。网络可以包括铜传输电缆、光纤传输、无线传输、路由器、防火墙、交换机、网关计算机和/或边缘服务器。每个计算/处理设备中的网络适配卡或者网络接口从网络接收计算机可读程序指令，并转发该计算机可读程序指令，以供存储在各个计算/处理设备中的计算机可读存储介质中。

用于执行本发明操作的计算机程序指令可以是汇编指令、指令集架构(ISA)指令、机器指令、机器相关指令、微代码、固件指令、状态设置数据、集成电路配置数据或者以一种或多种编程语言的任意组合编写的源代码或目标代码，所述编程语言包括面向对象的编程语言—诸如Smalltalk、C++等，以及常规的过程式编程语言—诸如“C”语言或类似的编程语言。计算机可读程序指令可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络—包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。在一些实施例中，通过利用计算机可读程序指令的状态信息来个性化定制电子电路，例如可编程逻辑电路、现场可编程门阵列(FPGA)或可编程逻辑阵列(PLA)，该电子电路可以执行计算机可读程序指令，从而实现本发明的各个方面。

这里参照根据本发明实施例的方法、装置(系统)和计算机程序产品的流程图和/或框图描述了本发明的各个方面。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机可读程序指令实现。

这些计算机可读程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得这些指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。也可以把这些计算机可读程序指令存储在计算机可读存储介质中，这些指令使得计算机、可编程数据处理装置和/或其他设备以特定方式工作，从而，存储有指令的计算机可读介质则包括一个制造品，其包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的各个方面的指令。

也可以把计算机可读程序指令加载到计算机、其它可编程数据处理装置、或其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在计算机、其它可编程数据处理装置、或其它设备上执行的指令实现流程图和/或框图中的一个或多个方框中规定的功能/动作。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的架构、功能和操作。在这方面，流程图或框图中的每个框可以表示模块、段或指令的一部分，其包括用于实现指定的逻辑功能的一个或多个可执行指令。在一些替代实施方式中，框中提到的功能可以不按附图中所示的顺序发生。例如，连续示出的两个方框实际上可以基本上同时执行，或者这些方框有时可以以相反的顺序执行，这取决于所涉及的功能。还应注意，框图和/或流程图图示的每个框以及框图和/或流程图图示中的框的组合可以由执行特定功能或动作、或者执行专用硬件和计算机指令的组合的专用的基于硬件的系统来实现。如上所述，以下详细描述一般将遵循本公开的概述，在必要时进一步解释和扩展本公开的各个方面和实施例的定义。

图1示出了信息处理系统100，其是能够执行本文描述的计算操作的计算机系统的简化示例。信息处理系统100包括耦合到处理器接口总线112的一个或多个处理器110。处理器接口总线112将处理器110连接到北桥115，北桥115也称为存储器控制器集线器(MCH)。北桥115连接到系统存储器120，并为处理器110提供访问系统存储器的方式。图形控制器125也连接到北桥115。在一个实施例中，外围组件互连(PCI)快速(Express)总线118将北桥115连接到图形控制器125。图形控制器125连接到显示设备130，例如计算机监视器。

北桥115和南桥135使用总线119彼此连接。在一个实施例中，总线是直接媒体接口(Direct Media Interface，DMI)总线，其在北桥115和南桥135之间的每个方向上高速传输数据。在另一个实施例中，PCI总线连接北桥和南桥。南桥135，也称为输入/输出(I/O)控制器集线器(ICH)，是一种通常以低于北桥提供的功能的速度实现功能的芯片。南桥135通常提供用于连接多种组件的多种总线。这些总线包括例如PCI和PCI Express总线、ISA总线、系统管理总线(System Management Bus，SMBus或SMB)、和/或低引脚数(Low Pin Count，LPC)总线。LPC总线通常连接低带宽设备，例如引导ROM 196和“传统”I/O设备(使用“超级I/O”芯片)。“传统”I/O设备(198)可以包括例如串行和并行端口、键盘、鼠标、和/或软盘控制器。南桥135中经常包括的其他组件包括直接存储器存取(Direct Memory Access，DMA)控制器，可编程中断控制器(Programmable Interrupt Controller，PIC)、和存储设备控制器，其使用总线184将南桥135连接到非易失性存储设备185，例如硬盘驱动器。

快速卡(ExpressCard)155是将热插拔设备连接到信息处理系统的插槽。快速卡155支持PCI Express和通用串行总线(USB)连接，因为它使用USB和PCI Express总线连接到南桥135。南桥135包括USB控制器140，其为连接到USB的设备提供USB连接。这些设备包括网络摄像头(摄像头)150、红外(IR)接收器148、键盘和触控板144、以及蓝牙设备146，其提供无线个人区域网络(PAN)。USB控制器140还提供与其他各种USB连接设备142(例如鼠标、可移动非易失性存储设备145、调制解调器、网卡、综合业务数字网(ISDN)连接器、传真、打印机、USB集线器，以及很多其他类型的USB连接的设备)的USB连接。虽然可移动非易失性存储设备145被示为USB连接设备，但是可移动非易失性存储设备145可以使用不同的接口(例如Firewire接口等)连接。

无线局域网(LAN)设备175经由PCI或PCI Express总线172连接到南桥135。LAN设备175通常实现(所有使用相同协议的在信息处理系统100和另一计算机系统或设备之间进行无线通信的空口调制技术的)电气和电子工程师协会(IEEE).802.11标准之一。光存储设备190使用串行模拟电话适配器(ATA)(Serial Analog Telephone Adapter，SATA)总线188连接到南桥135。串行ATA适配器和设备通过高速串行链路通信。串行ATA总线还将南桥135连接到其他形式的存储设备，例如硬盘驱动器。诸如声卡的音频电路160经由总线158连接到南桥135。音频电路160还提供功能，例如音频输入和光纤数字音频输入端口162、光纤数字输出和耳机插孔164、内部扬声器166、以及内部麦克风168。以太网控制器170使用总线(例如PCI或PCI Express总线)连接到南桥135。以太网控制器170将信息处理系统100连接到计算机网络，例如局域网(LAN)、因特网、和其他公共和私人计算机网络。

虽然图1示出了一个信息处理系统，但是信息处理系统可以采用许多形式。例如，信息处理系统可以采用台式机、服务器、便携式计算机、膝上型计算机、笔记本、或其他形状因素的计算机或数据处理系统的形式。另外，信息处理系统可以采用其他形式因素，例如个人数字助理(PDA)、游戏设备、自动柜员机(ATM)、便携式电话设备、通信设备、或包括处理器和存储器的其他设备。

图2提供了图1中所示的信息处理系统环境的扩展，以说明本文描述的方法可以在网络环境中操作的多种信息处理系统上执行。信息处理系统的类型从小型手持设备(例如手持式计算机/移动电话210)到大型主机系统(例如大型计算机270)。手持式计算机210的示例包括个人数字助理(PDA)、个人娱乐设备，例如运动图像专家组Layer-3音频(MP3)播放器、便携式电视、和光盘播放器。信息处理系统的其他示例包括笔、或平板电脑、计算机220、膝上型计算机、或笔记本、计算机230、工作站240、个人计算机系统250和服务器260。图2中未单独示出的其他类型的信息处理系统表示为信息处理系统280。如图所述，可以使用计算机网络200将多种信息处理系统联网在一起。可以用于互连多种信息处理系统的计算机网络的类型包括局域网(LAN)、无线局域网络(WLAN)、因特网、公共交换电话网(PSTN)、其他无线网络、以及可用于互连信息处理系统的任何其他网络拓扑。许多信息处理系统包括非易失性数据存储，例如硬盘驱动器和/或非易失性存储器。图2中所示的一些信息处理系统描绘了单独的非易失性数据存储(服务器260利用非易失性数据存储265，主机计算机270利用非易失性数据存储275，并且信息处理系统280利用非易失性数据存储285)。非易失性数据存储可以是多种信息处理系统外部的组件，或者可以是其中一个信息处理系统的内部组件。另外，可以使用多种技术在两个或更多个信息处理系统之间共享可移动非易失性存储设备145，例如将可移动非易失性存储设备145连接到USB端口或信息处理系统的其他连接器。

图3到12描绘了一种信息处理系统，其对源系统上具有可变长度符号的符号流进行编码，以便目的地系统执行多路复用比特流的并行解码。如前所述，当前的压缩数据格式由可变长度符号流组成，因此，解码这些符号流的过程本质上是顺序的，并且难以并行化解码过程以提高性能。

为了缓解该挑战，源系统对输入符号流执行转换步骤以使目的地系统能够执行并行解码。初始符号流被解复用为n(例如4)个独立符号子流，然后将其划分为具有对应的拉取定时信息的固定比特宽度数据块，该拉取定时信息对应于相对固定比特宽度数据块的符号的边界的位置。然后，基于拉取定时信息将固定比特宽度数据块复用在一起并发送到目的地系统。

目的地系统使用比特流划分器，其将多路复用的比特流分成固定比特宽度数据块，并在解码器的请求下将固定比特宽度数据块馈送到多个解码器。多个解码器并行地解码符号并将解码的符号馈送到组合器中。组合器将符号组合成解码的符号流，并将解码的符号流发送到后处理。

图3是描绘将初始符号流转换为多路复用的比特流的源符号编码器以及使用多个解码器将多路复用的比特流转换为解码的符号流的目的地符号解码器的图。

符号编码器300接收初始比特流310，在一个实施例中，初始比特流310包括具有可变长度的符号(例如，霍夫曼Gzip流)。解复用器320将初始符号流310解复用为符号集，其是符号子流325和330。图3中的示例示出了两个解复用的符号子流325和330。在该示例中，解复用器320将来自初始符号流310的第一符号存储在符号子流325中，将来自初始符号流310的第二符号存储在符号子流330中，将第三符号从初始符号流310存储回符号子流325等(详见图5和相应的文字)。

流转换器A 335和流转换器B 340同时将它们对应的符号子流划分为固定比特宽度数据块，其存储在比特流A 337和比特流B 342中。固定比特宽度数据块的大小与目的地符号解码器360中的固定宽度解码器A 370和B 375所使用的缓冲器的大小(例如，16位)相匹配。流转换器A 335和流转换器B 340还生成拉取定时A 339和拉取定时B 344，其对应于相对固定比特宽度数据块的边界的符号的位置(参见图6和用于处理细节的相应文本)。固定宽度多路复用器350使用拉取定时信息，以将来自流转换器A 335和B 340的固定比特宽度数据块适当地组织成多路复用比特流355，以便匹配固定宽度解码器A 370和B 375将从下面讨论的比特流划分器365请求或“拉取(pull)”固定比特宽度数据块的时间。

符号解码器360的比特流划分器365将多路复用的比特流355分成固定比特宽度数据块(与由符号编码器300划分的固定比特宽度数据块的大小相同)。固定宽度解码器A 370和B 375首先从比特流划分器365请求固定比特宽度数据块以初始加载它们相应的缓冲器(例如，两个缓冲器)。然后，固定宽度解码器A 370和B 375开始同时解码其加载的固定比特宽度数据块中的符号。当固定宽度解码器A 370或B 375需要更多固定的比特宽度数据块时，例如当其中一个解码符号到达其第一缓冲器的边界时，解码器从比特流划分器365请求另一个固定比特宽度数据块(更多细节参见图11-12和相应的文字)。

固定宽度解码器产生解码符号流380和385，组合器390以循环方式将其组合成解码符号流395并准备好用于后处理。符号解码器360又通过使用多个固定宽度解码器来执行并行解码来提高解码性能。

图4是示出利用图3中所示的符号编码器和符号解码器的压缩器和解压缩器的高级图。压缩器400包括数据编码器420，其接收未压缩的字节流410并创建初始符号流310。初始符号流310馈入符号编码器300，其产生如上所述的多路复用比特流355。

解压缩器430包括符号解码器360，其生成如上所述的解码符号流395。数据解码器440又对解码符号流395中的符号进行解码以生成重构字节流450。

图5是描绘初始符号流被转换为多路复用比特流的的阶段的详细图。初始符号流310包括可变长度符号S1、S2、S3、S4、S5、S6、S7、S8、S9、S10、S11、S12、S13、S14、S15和S16。解复用器320按顺序将符号分离为符号子流A 325和符号子流B 330。可以看出，符号子流A325包括符号S1、S3、S5、S7、S9、S11、S13和S15，并且符号子流B 330包括符号S2、S4、S6、S8、S10、S12、S14和S16。

流转换器A 335将符号子流A 325划分为固定比特宽度数据块A1、A2、A3、A4和A5，并将固定比特宽度数据块存储到比特流A 337中。流转换器A 335还产生拉取定时A 339，其包括来自符号子流A 325的符号跨越固定比特宽度数据块的边界的时隙中的1(进一步细节参见图6和相应的文本)。

类似地，流转换器B 340将符号子流B 330划分为固定的比特宽度数据块B1、B2、B3、B4、B5和B6，并将固定的比特宽度数据块存储到比特流B 342中。流转换器B 340还生成拉取定时B 344，其包括来自符号子流B 330的符号跨越固定比特宽度数据块之一的边界的时隙中的1。

然后，固定宽度多路复用器350进行组合来自比特流A 337和比特流B 342的固定比特宽度数据块的过程。固定宽度多路复用器350首先加载固定比特宽度数据块A1，然后是B1，然后是A2、B2，因为固定宽度解码器A 370和B 375执行它们的两个缓冲器的初始加载。接下来，固定宽度多路复用器350分析拉取定时A 339和B 344以确定何时从比特流A 337或B 342加载固定比特宽度数据块(进一步的细节参见图7和相应的文本)。反过来，固定宽度多路复用器350通过计算机网络将多路复用比特流355发送到符号解码器360，以便后续解码。在一个实施例中，固定宽度多路复用器350将多路复用比特流355存储在存储区域中以供后续检索。

图6是描绘将比特流划分成固定比特宽度数据块并生成拉取定时的流转换器的图。流转换器A 335将比特流A 337分成固定的比特宽度数据块A1、A2、A3、A4和A5。固定比特宽度数据块对应于固定宽度解码器所使用的缓冲器的大小，因为固定宽度解码器将从比特流分区器365(下面讨论)请求相同大小的数据块。例如，如果固定宽度解码器A 370的缓冲器大小是16比特，则流转换器A 335使用16比特的固定比特宽度数据块大小。

然后，流转换器A 335相对于固定比特宽度数据块的边界分析符号S1、S3、S5、S7、S9、S11、S13和S15。当其中一个符号越过边界时，流转换器A 335将1加载到拉取定时A 339中，因为符号解码器360处的解码器将在那时请求另一个固定的比特宽度数据块，这是固定宽度多路复用器350基于拉取定时顺序加载固定比特宽度数据块的原因(更多细节参见图12和相应的文本)。基于图6中所示的示例，流转换器A 335分析符号并且对符号执行以下步骤：

S1不跨越边界，将0加载到拉取定时A 339；

S3越过边界610，负载1进入拉取动定时A 339；

S5不跨越边界，加载0进入拉取定时A 339；

S7不跨越边界，将0加载到拉取定时A 339；

S9越过边界615，加载1到拉取定时A 339；

S11越过边界620，加载1到拉取定时A 339；

S13不跨越边界，加载0到拉取定时A 339；以及

S15越过边界625，加载1到拉取定时A 339。

类似地，流转换器B 340将比特流B 342分成固定比特宽度数据块B1、B3、B3、B4、B5和B6。然后，流转换器B 340相对于固定比特宽度数据块边界分析符号S2、S4、S6、S8、S10、S12、S14和S16。基于图6中所示的示例，流转换器B 340分析符号并且对符号执行以下步骤：

S2不跨越边界，加载0到拉取定时B 344；

S4越过边界610，加载1到拉取定时B 344；

S6越过边界610，加载1到拉取定时B 344；

S8越过边界610，加载1到拉取定时B 344；

S10不跨越边界，加载0到拉取定时B 344；

S12越过边界620，加载1到拉取定时B 344；

S14越过边界610，加载1到拉取定时B 344；以及

S16不跨越边界，加载0到拉取定时B 344。

然后，固定宽度多路复用器350使用拉取定时以特定顺序从比特流A 337和比特流B 342插入固定比特宽度数据块(进一步的细节参见图7和相应的文本)。

图7是描绘固定宽度多路复用器350从多个比特流以与符号解码器360中的固定宽度解码器A 370和B 375将如何处理固定比特宽度数据块的顺序一致的顺序加载固定比特宽度数据块的方法的图。

如图11-12所示，固定宽度解码器首先按顺序执行其缓冲器的初始加载。这样，固定宽度多路复用器350在多路复用比特流355的时隙1、2、3和4中加载块A1，然后是B1，然后是A2，然后是B2。

接下来，固定宽度多路复用器350按顺序查看拉取定时A 339和B 344，以确定接下来要加载哪些固定位宽数据块。拉取定时A 339和拉取定时B 344在它们的第一时隙中都不包括1，因此固定宽度多路复用器350什么都不做。拉取定时A 339在第二时隙中包括1，因此固定宽度多路复用器350在多路复用比特流355的第五时隙中加载块A3。拉取定时B 344在第二时隙中也包括1，因此固定宽度多路复用器350在多路复用比特流355的第六时隙中加载块B3。拉取出定时A 339在第三个时隙中包括0，因此不加载任何内容。拉取定时B 344在第三时隙中包括1，因此固定宽度多路复用器350在多路复用比特流355的第7个时隙中加载B4。

继续，拉取定时A 339在第四时隙中包括0，因此不加载任何内容。拉取定时B 344在第四时隙中包括1，因此固定宽度多路复用器350在多路复用比特流355的第8个时隙中加载B5。拉取定时A 339在第五个时隙中包括1，因此固定宽度多路复用器350在多路复用比特流355的第9个时隙中加载A4。拉取出定时B 344在第五时隙中包括0，因此不加载任何内容。拉取定时A 339在第六时隙中包括1，因此固定宽度多路复用器350在多路复用比特流355的第10个时隙中加载A5。拉取定时B 344在第六个时隙中也包括1，因此固定宽度多路复用器350在多路复用比特流355的第11个中加载B6。在一个实施例中，例如图7中所示的实施例，由于如上所述的固定宽度数据块的初始加载，并不是所有的拉取定时都将被利用。

图8是示出源编码器的高层次流程图，该源编码器生成被发送到目的地符号解码器以进行并行解码的复用比特流。处理开始于800，在步骤810，该过程确定符号子流的数量(n)以对初始比特流进行解复用(例如，n＝2)。在步骤820，该过程识别初始比特流310中的第一符号，并将第一符号加载到第一符号子流(例如，符号子流325)中。

然后，该过程确定更多符号是否在初始符号流310中(判定830)。如果更多符号在初始符号流310中，则判定830分支到“是”分支，其循环返回以识别下一个符号并将下一个符号加载到下一个符号子流330中。该循环继续顺序地从初始比特流310加载符号到适当的符号子流(例如，325、330、325、330…)的方式，直到在初始符号流310中不再有符号为止，此时判定830分支到“否”分支退出循环。

在预定义过程840，对于每个符号子流，该过程将符号子流划分为固定比特宽度数据块，并将固定比特宽度数据块加载到它们对应的比特流337和342中。该过程还产生如本文所讨论的拉取定时信息，该拉取定时信息对应于相对固定比特宽度数据块的边界的符号的位置(参见图9和用于处理细节的相应文本)。

在预定义过程850，该过程基于拉取定时信息将来自多个比特流的固定比特宽度数据块组合成多路复用比特流(处理细节参见图10和相应文本)。然后，该过程在步骤860将多路复用比特流发送到符号解码器360，并且图8的处理此后在870结束。符号解码器360依次执行多路复用比特流335的并行解码(更多细节参见图11、12和相应的文本)。

图9是示出将符号子流转换为具有固定比特宽度数据块的比特流并且生成对应于固定比特宽度数据块的拉取定时的流转换过程所采取的步骤的流程图。图9中所示的示例示出了流转换器A 335处理符号子流A 325所采取的步骤。如本文所讨论的，转换多个符号子流的流转换器的数量基于解复用器320所生成的符号子流的数量，每个流转换器执行图9中所示的步骤。在一个实施例中，符号编码器300可以在转换过程期间使用比符号子流更少的流转换器，例如利用一个流转换器来转换多个符号子流。

处理开始于900，在步骤910，该过程将符号子流A 320划分成固定比特宽度数据块，例如16比特，并将固定的比特宽度数据块加载到比特流337中。在一个实施例中，该过程将固定比特宽度数据块加载到临时存储区域中，并标记每个固定比特宽度数据块的边界。在步骤915，该过程设置指向比特流的开始的指针，并且在步骤920，该过程将指针移动到第一符号的结尾。

然后，该过程确定指针是否越过固定比特宽度边界，例如图6中所示的边界615(判定930)。该过程执行这一确定步骤，因为在目的地系统处，当符号穿过缓冲器边界时，固定宽度解码器将从比特流划分器365请求另一固定比特宽度数据块，该缓冲器边界与固定比特宽度数据块的大小相同。

如果指针越过边界，则判定930分支到“是”分支，于是，在步骤950，该过程在拉取定时A 339的第一个时隙中存储“1”。另一方面，如果指针没有越过固定比特宽度边界，则判定930分支到“否”分支，在步骤940，该过程在拉取定时A399的第一个时隙中存储“0”。返回参考图6，图6中的示例示出了第一符号“S1”的末端不跨越边界610。

该过程确定在比特流A 337中是否还有更多符号要处理(判定960)。如果比特流A337中有更多符号要处理，则判定960分支到“是”分支，其循环返回以将指针移动到下一个符号的末端并评估指针是否越过边界。参考图6，该过程将指针移动到符号“S3”(其并不越过边界610)的末端。该循环继续直到在比特流A 337中不再有要处理的符号，此时判定960分支到'no'分支退出循环。在一个实施例中，此时，可能存在尚未发送的符号，因为它们的末端没有使指针移过固定宽度边界。在该实施例中，处理可以发送包括这些符号的另一固定宽度块。

在步骤970，该过程发送比特流A 337(包括固定比特宽度数据块)以及拉取定时A339到固定宽度多路复用器350。如图10所示，固定宽度多路复用器基于它们各自的拉取定时来组合来自多个流转换器的多个比特流。此后，图9处理返回到995处的调用例程(参见图8)。

图10是示出固定宽度多路复用器基于拉取定时信息将来自多个比特流的固定比特宽度数据块组合成多路复用比特流所采取的步骤的流程图。处理开始于1000，于是在步骤1010，该过程按顺序从比特流337，然后是比特流342，然后比特流337，然后比特流342，将初始数据块加载到多路复用比特流355。以这种方式处理执行初始加载以模拟目的地的固定宽度解码器A 370和B 375将如何执行初始加载(更多细节参见图12和相应的文本)。

该过程确定拉取定时A 339中的第一时隙是否包括“1”，其指示比特流A 337的符号之一越过边界，并且因此，目的地系统的固定宽度解码器A 370将请求另一个固定比特宽度数据块(判定1020)。如果拉取定时A 339中的第一时隙包括“1”，则判定1020分支到“是”分支，于是，在步骤1030，该过程从比特流A 337加载下一个固定比特宽度数据块。另一方面，拉取定时A 339中的第一时隙不包括“1”，则判定1020分支到“否”分支。

然后，该过程确定拉取定时B 344中的第一时隙是否包括“1”，其指示比特流B 342的符号之一越过边界，并且因此，目的地系统的固定宽度解码器B 375将请求另一个固定比特宽度数据块(判定1040)。如果拉取定时B 344中的第一时隙包括“1”，则判定1040分支到“是”分支，于是，在步骤1050，该过程从比特流B 342加载下一个固定比特宽度数据组块。另一方面，拉取定时B 344中的第一时隙不包括“1”，则判定1040分支到“否”分支。

然后，该过程确定比特流是否已经结束(决定1060)。如果比特流尚未结束，则判定1060分支到“否”分支，该分支循环返回以继续处理比特流。该循环继续直到比特流结束，此时决策1060分支到退出循环的“是”分支。在一个实施例中，处理还在此时将一个或多个“虚拟”块加载到多路复用比特流355中。此后，图10处理返回到1095处的调用例程(参见图8)。

图11是示出目的地系统执行输入多路复用比特流的并行解码的步骤的流程图。参考图3，符号解码器360包括固定宽度解码器A 370和固定宽度解码器B 375，它们同时解码多路复用比特流355中包括的符号。如前所述，比特流划分器365将多路复用比特流355分成固定比特宽度数据组块，并且提供固定宽度解码器A 370和固定宽度解码器B 375所要求的固定比特宽度数据组块。

固定宽度解码器A 110处理在1100开始，于是，在步骤1105，固定宽度解码器A 370从比特流划分器365请求第一固定比特宽度数据块并将第一固定比特宽度数据块加载到其缓冲器(详细信息参见图12和相应的文本)。固定宽度解码器B 375处理同时开始于1150，于是，在步骤1155，固定宽度解码器B 375从比特流划分器1165请求下一个固定比特宽度数据组块(第二块)并将第二固定比特宽度数据组块加载到其第一缓冲器。

在步骤1110，固定宽度解码器A 370请求下一个固定比特宽度数据块(第三块)并将其加载到其第二缓冲器中。同样地，在步骤1160，固定宽度解码器B 375请求下一个固定比特宽度数据块(第四块)并将其加载到其第二缓冲器中。此时，固定宽度解码器A 370的缓冲器和固定宽度解码器B 375的缓冲器都是满的。

在步骤1115，固定宽度解码器A 370将其指针设置为其第一缓冲器的开始，并且在步骤1120，固定宽度解码器A 370解码第一符号并将解码的符号加载到解码的符号流A 380中，并移动指针到下一个符号的开头。固定宽度解码器A 370确定指针是否越过第一缓冲器边界并到达第二缓冲器，指示应当从比特流划分器365请求另一个固定比特宽度数据块(判定1125)。如果指针没有越过第一缓冲器边界，则判定1125分支到“否”分支，该分支循环返回以处理下一个符号并移动指针。该循环继续直到指针越过第一缓冲器边界，此时判定1125分支到退出循环的“是”分支。

固定宽度解码器A 370确定比特流划分器365是否包括更多的固定比特宽度数据块(判定1130)。如果比特流划分器365包括更多的固定比特宽度数据块，则判定1130分支到“是”分支，该分支循环返回以将第二缓冲器的内容移位到第一缓冲器(步骤1135)并从比特流划分器365请求另一个固定比特宽度数据块，并将其加载到其第二缓冲器中(步骤1140)。该循环继续，直到不再有要处理的固定比特宽度数据块为止，此时判定1130分支到退出循环的“否”分支。此后，固定宽度解码器A 370处理在1145结束。

固定宽度解码器A 370确定在其缓冲器中是否还有更多的符号要解码(判定1142)。如果在其缓冲区中剩余更多的符号以解码，则判定1142分支到“是”分支，该分支循环返回以解码下一个符号。该循环继续直到在其缓冲器中不再有符号剩余以进行解码，此时判定1142分支到退出循环的“否”分支，并且固定宽度解码器A 370处理在1145结束。

固定宽度解码器B 375同时执行与固定宽度解码器A 370类似的步骤。固定宽度解码器B 375在步骤1165将其指针设置为其第一缓冲器的开始，并且在步骤1170，固定宽度解码器B 375解码第一符号并将解码后的符号加载到解码符号流B 385中，并将指针移动到下一个符号。固定宽度解码器B 375确定指针是否穿过第一缓冲器的边界并到达第二缓冲器，指示应当从比特流划分器365请求另一个固定比特宽度数据块(判定1175)。如果指针没有越过第一缓冲器边界，则判定1175分支到“否”分支，该分支循环返回以处理下一个符号并移动指针。该循环继续直到指针越过第一缓冲器的边界，此时判定1175分支到退出循环的“是”分支。

固定宽度解码器B 375确定比特流划分器365是否包括更多的固定比特宽度数据块(判定1180)。如果比特流划分器365包括更多的固定比特宽度数据块，则判定1180分支到“是”分支，该分支循环返回以将第二缓冲器的内容移位到第一缓冲器(步骤1185)并从比特流划分器1165请求另一个固定的比特宽度数据块，并将其加载到其第二缓冲器中(步骤1190)。该循环继续直到不再有要处理的固定比特宽度数据块为止，此时判定1180分支到退出循环的“否”分支。

固定宽度解码器B 375确定在其缓冲器中是否还有更多符号要解码(判定1192)。如果在其缓冲器中剩余更多符号以解码，则判定1192分支到“是”分支，该分支循环返回以解码下一个符号。该循环继续直到在其缓冲器中不再有符号剩余以解码，此时判定1192分支到退出循环的“否”分支，并且固定宽度解码器B 375处理在1195结束。

图12是示出与比特流划分器接口以请求和处理固定比特宽度数据块的多个固定宽度解码器的示例的图。

固定宽度解码器A 370包括第一缓冲器1200和第二缓冲器1210。类似地，固定宽度解码器B 375包括第一缓冲器1220和第二缓冲器1230。缓冲器的大小匹配在符号编码器300处划分的固定比特宽度数据块的大小(例如，每个16位)。比特流划分器365接收多路复用比特流355并将多路复用比特流355分成固定比特宽度数据块。参考图5，顺序的固定比特宽度数据块是A1、B1、A2、B2、A3、B3、B4、B5、A4、A5和B6。

固定宽度解码器A 370和固定宽度解码器B 375以循环顺序从比特流划分器365请求固定比特宽度数据块以初始加载它们对应的缓冲器。这样，固定宽度解码器A 370接收块A1并将其加载到第一缓冲器1200中。固定宽度解码器B 375然后接收块B1并将其加载到第一缓冲器1220中。接下来，固定宽度解码器A 370接收块A2并将其加载到第一缓冲器1220中。然后，固定宽度解码器B 375接收块B2并将其加载到第二缓冲器1230中。

此时，两个解码器都准备开始解码可变长度符号。如本文所讨论的，当解码器解码跨越其第一缓冲器与其第二缓冲器之间的边界的符号时，解码器从比特流划分器365请求额外的固定比特宽度数据块。当这种情况发生时，解码器将内容从其第二缓冲器移到其第一缓冲器，并将新接收的固定比特宽度数据块加载到其第二缓冲器中。

关于图12中所示的示例，固定宽度解码器A 370与固定宽度解码器B 375解码符号S2并行地解码符号S1。这两个解码器都没有请求另一个固定比特宽度数据块，因为符号S1和S2没有穿过第一个缓冲器边界。固定宽度解码器A 370然后与固定宽度解码器B 375解码符号S4并行地解码符号S3。固定宽度解码器A 370从比特流划分器365请求固定比特宽度数据块，因为符号S3越过第一缓冲器1200的边界，并且固定宽度解码器B 375还从比特流划分器365请求固定比特宽度数据块，因为符号S4越过第一缓冲器1220的边界。两个解码器的输出被馈送到组合器390并组合成解码的符号流395(如图3所示)。

虽然已经示出和描述了本公开的特定实施例，但是对于本领域技术人员来说明显的是，基于本文的教导，可以在不脱离本公开及其更广泛方面的情况下进行改变和修改。因此，所附权利要求在其范围内包含在本公开的真实精神和范围内的所有这些变化和修改。此外，应理解，本公开仅由所附权利要求限定。本领域技术人员将理解，如果意图引入特定数量的引入的权利要求元素，则将在权利要求中明确地陈述这样的意图，并且在没有这样的叙述的情况下，不存在这样的限制。对于非限制性示例，为了帮助理解，以下所附权利要求包含介绍性短语“至少一个”和“一个或多个”的使用以引入权利要求元素。然而，这些短语的使用不应被解释为暗示由不定冠词“一(a)”或“一(an)”引入权利要求要素将包含这种引入的权利要求要素的任何特定权利要求限制于仅包含一个这样的要素的公开内容，即使相同的权利要求包括引入短语“一个或多个”或“至少一个”和不定冠词，如“一(a)”或“一(an)”；对于在定冠词的权利要求中的使用也是如此。

Claims (20)

1.一种由信息处理系统实施的方法，所述方法包括：

将符号流分离为多个符号子流，所述多个符号子流中的每一个包含具有一个或多个不同符号长度的多个符号；

在所述多个符号子流中的每一个上将多个符号集中的每一个划分为多个固定宽度数据块，其中，所述多个固定宽度数据块的每一个的固定宽度是基于所述多个不同符号长度中的最长的一个确定的，所述划分产生所述多个固定宽度数据块的每一个之间的一个或多个边界；

识别所述一个或多个不同符号长度的多个符号中的一个或多个相对于所述一个或多个边界的一个或多个位置；

创建对应于所识别的一个或多个位置的符号边界信息；

基于所述符号边界信息将所述多个固定宽度数据块组合成多路复用比特流；以及

将所述多路复用比特流提供给目的地系统。

2.根据权利要求1所述的方法，其中，对于所述多个符号子流中的所选择的一个符号子流，所述方法还包括：

选择与一个或多个固定宽度数据块中所选的一个固定宽度数据块相对应的所述多个符号中的一个符号；

确定所选的符号是否越过与所选的固定宽度数据块对应的一个或多个边界中的所选的一个边界；

响应于确定所述所选的符号越过所述所选的边界，在所述符号边界信息的所选时隙中存储第一指示符；以及

响应于确定所述所选的符号没有越过所述所选的边界，在所述符号边界信息的所选时隙中存储第二指示符。

3.根据权利要求2所述的方法，其中所述组合还包括：

执行初始加载，所述初始加载以基于所述多个符号子流中的每一个的顺序将所述多个固定宽度数据块的一部分加载到所述多路复用比特流中；

在初始加载之后，确定所述所选的时隙是否包括所述第一指示符；以及

响应于确定所述所选的时隙包括所述第一指示符，将对应于所选的符号子流的所选的固定宽度数据块加载到所述多路复用比特流。

4.根据权利要求1所述的方法，其中，在所述划分之前，该方法还包括：

将未压缩的字节流编码成所述多个符号；以及

将所述多个符号包括在所述符号流中。

5.一种信息处理系统，包括：

一个或多个处理器；

存储器，耦合到所述一个或多个处理器中的至少一个处理器；

存储在所述存储器中并由所述一个或多个处理器中的至少一个处理器执行的一组计算机程序指令，以执行以下动作：

将符号流分离为多个符号子流，所述多个符号子流中的每一个包含具有一个或多个不同符号长度的多个符号；

在所述多个符号子流中的每一个上将多个符号集中的每一个划分为多个固定宽度数据块，其中，所述多个固定宽度数据块的每一个的固定宽度是基于所述多个不同符号长度中的最长的一个确定的，所述划分产生所述多个固定宽度数据块的每一个之间的一个或多个边界；

识别所述一个或多个不同符号长度的多个符号中的一个或多个相对于所述一个或多个边界的一个或多个位置；

创建对应于所识别的一个或多个位置的符号边界信息；

基于所述符号边界信息将所述多个固定宽度数据块组合成多路复用比特流；以及

将所述多路复用比特流提供给目的地系统。

6.根据权利要求5所述的信息处理系统，其中，对于所述多个符号子流中的所选择的一个，所述处理器执行进一步的动作，包括：

选择与一个或多个固定宽度数据块中所选的一个固定宽度数据块相对应的所述多个符号中的一个符号；

确定所选的符号是否越过与所选的固定宽度数据块对应的一个或多个边界中的所选的一个边界；

响应于确定所述所选的符号越过所述所选的边界，在所述符号边界信息的所选时隙中存储第一指示符；以及

响应于确定所述所选的符号没有越过所述所选的边界，在所述符号边界信息的所选时隙中存储第二指示符。

7.根据权利要求6所述的信息处理系统，所述处理器执行进一步的动作，包括：

执行初始加载，所述初始加载以基于所述多个符号子流中的每一个的顺序将所述多个固定宽度数据块的一部分加载到所述多路复用比特流中；

在初始加载之后，确定所述所选的时隙是否包括所述第一指示符；以及

响应于确定所述所选的时隙包括所述第一指示符，将对应于所选的符号子流的所选的固定宽度数据块加载到所述多路复用比特流。

8.根据权利要求5所述的信息处理系统，其中，在所述划分之前，所述处理器执行进一步的动作，包括：

将未压缩的字节流编码成所述多个符号；以及

将所述多个符号包括在所述符号流中。

9.一种存储在计算机可读存储介质中的计算机程序产品，包括计算机程序代码，当由信息处理系统执行时，使得所述信息处理系统执行动作，包括：

将符号流分离为多个符号子流，所述多个符号子流中的每一个包含具有一个或多个不同符号长度的多个符号；

在所述多个符号子流中的每一个上将多个符号集中的每一个划分为多个固定宽度数据块，其中，所述多个固定宽度数据块的每一个的固定宽度是基于所述多个不同符号长度中的最长的一个确定的，所述划分产生所述多个固定宽度数据块的每一个之间的一个或多个边界；

识别所述一个或多个不同符号长度的多个符号中的一个或多个相对于所述一个或多个边界的一个或多个位置；

创建相对对应于所识别的一个或多个位置的符号边界信息；

基于所述符号边界信息将所述多个固定宽度数据块组合成多路复用比特流；以及

将所述多路复用比特流提供给目的地系统。

10.根据权利要求9所述的计算机程序产品，其中，对于所述多个符号子流中的所选择的一个，所述信息处理系统执行进一步的动作，包括：

选择与一个或多个固定宽度数据块中所选的一个固定宽度数据块相对应的所述多个符号中的一个符号；

确定所选的符号是否越过与所选的固定宽度数据块对应的一个或多个边界中的所选的一个边界；

响应于确定所述所选的符号越过所述所选的边界，在所述符号边界信息的所选时隙中存储第一指示符；以及

响应于确定所述所选的符号没有越过所述所选的边界，在所述符号边界信息的所选时隙中存储第二指示符。

11.根据权利要求10所述的计算机程序产品，所述信息处理系统执行进一步的动作，包括：

执行初始加载，所述初始加载以基于所述多个符号子流中的每一个的顺序将所述多个固定宽度数据块的一部分加载到所述多路复用比特流中；

在初始加载之后，确定所述所选的时隙是否包括所述第一指示符；以及

响应于确定所述所选的时隙包括所述第一指示符，将对应于所选的符号子流的所选的固定宽度数据块加载到所述多路复用比特流。

12.根据权利要求9所述的计算机程序产品，其中，在所述划分之前，所述信息处理系统执行进一步的动作，包括：

将未压缩的字节流编码成所述多个符号；以及

将所述多个符号包括在符号流中。

13.一种由信息处理系统实施的方法，所述方法包括：

将多路复用的比特流分成多个固定宽度数据块；

使用多个解码器对包括在多个固定宽度数据块中的具有一个或多个不同符号长度的多个符号进行解码，得到多个解码符号子流，其中所述多个解码器中的每一个包括第一缓冲器和第二缓冲器，所述第一缓冲器和所述第二缓冲器都基于所述多个固定宽度数据块的固定宽度尺寸；

将所述多个解码符号子流组合成解码符号流；以及

处理所述解码符号流。

14.根据权利要求13所述的方法，其中，使用所述多个解码器中的所选的一个，所述方法还包括：

解码位于所述第一缓冲器中的多个符号中的所选的一个符号；

确定所选符号到达所述第二缓冲器；以及

响应于确定所选符号到达所述第二缓冲器：

将内容从所述第二缓冲器转移到所述第一缓冲器；以及

请求后续的固定宽度数据块。

15.根据权利要求14所述的方法，还包括：

接收所述后续的固定宽度数据块；以及

将所述后续的固定宽度数据块加载到所述第二缓冲器。

16.根据权利要求13所述的方法，其中所述处理还包括：

对所述解码符号流进行解码，得到重构的字节流。

17.一种信息处理系统，包括：

一个或多个处理器；

存储器，耦合到所述一个或多个处理器中的至少一个处理器；

存储在所述存储器中并由至少一个处理器执行的一组计算机程序指令，以便执行以下动作：

将多路复用的比特流分成多个固定宽度数据块；

使用多个解码器对包括在所述多个固定宽度数据块中的具有一个或多个不同符号长度的多个符号进行解码，得到多个解码符号子流，其中所述多个解码器中的每一个包括第一缓冲器和第二缓冲器，所述第一缓冲器和所述第二缓冲器都基于所述多个固定宽度数据块的固定宽度尺寸；

将所述多个解码符号子流组合成解码符号流；以及

处理所述解码符号流。

18.根据权利要求17所述的信息处理系统，其中，使用所述多个解码器中的所选的一个，所述处理器执行附加的动作，包括：

解码位于所述第一缓冲器中的所述多个符号中的所选的一个符号；

确定所选符号到达所述第二缓冲器；以及

响应于确定所述所选符号到达所述第二缓冲器：

将内容从所述第二缓冲器转移到所述第一缓冲器；以及

请求后续的固定宽度数据块。

19.根据权利要求18所述的信息处理系统，其中处理器执行附加的动作，包括：

接收所述后续的固定宽度数据块；以及

将所述后续的固定宽度数据块加载到所述第二缓冲器。

20.根据权利要求17所述的信息处理系统，其中处理器执行附加的动作，包括：

对所述解码符号流进行解码，得到重构的字节流。

Images