瑞普特代码的解码

摘要

提供了一种解码瑞普特代码的方法与装置。该装置包括：解码器(140)，用来解码表示编码码元序列的分组序列。该解码器(140)利用瑞普特代码，至少部分地恢复该序列的至少某些丢失或者损坏的分组。

说明书

相关申请的交叉引用

本申请要求2006年2月8日提交的美国临时申请第60/771,377号的优先权，其内容通过引用融入本文。

技术领域

本发明总体涉及喷泉代码(fountain code)，更具体地，涉及解码瑞普特代码(raptor code)的方法与装置。

背景技术

第三代伙伴计划(3GPP)为在1998年12月确立的合作协议。该合作协议将称为组织伙伴的多个电信标准团体结合在一起。3GPP的原来的范围是产生基于已开发的全球移动通信系统(GSM)核心网络以及其支持的射频接入技术(即统一地面射频接入(UTRA)，频分双工(FDD)与时分双工(TDD)模式两者)的、对于第三代移动系统的、全球适用的技术规范与技术报告。之后修改了该范围，以包括对GSM技术规范与技术报告(包括已开发射频接入技术，例如通用分组射频服务(GPRS)以及GSM演进提高数据率(EDGE))的维护和开发。

系统瑞普特代码被采用作为3GPP多媒体广播/多播服务(MBMS)的应用层前向纠错(FEC)代码。为了解码瑞普特代码，解码器一般构造线性方程系统，并且使用高斯消除法来解方程。但是，当系统不满秩(即收到的源与奇偶校验分组不足以进行完全解码)时，解码器通常宣布失败，并且只输出收到的源分组。

发明内容

本发明处理现有技术的这些以及其他缺点与不足，本发明针对解码瑞普特代码的方法与装置。

根据本发明的一方面，提供了一种装置。该装置包括:解码器，用来解码表示解码码元序列的分组序列。解码器利用瑞普特代码，至少部分地恢复该序列的至少某些丢失或者损坏的分组。

根据本发明的一方面，提供了一种方法。该方法包括:解码表示解码码元序列的分组序列。该解码步骤利用瑞普特代码，至少部分地恢复该序列的至少某些丢失或者损坏的分组。

从以下对结合附图的示范性实施例的详细描述，可以清楚本发明的这些以及其他方面、特征以及优点。

附图说明

根据以下示范性附图，可以更好地理解本发明，其中:

图1为显示根据本发明的实施例的可以应用本发明的示范性视频编码/解码环境的方框图；以及

图2显示根据本发明的实施例的用来解码瑞普特代码的示范性方法的流程图。

具体实施方式

本发明针对解码瑞普特代码的方法与装置。

本说明书描述本发明。由此应该理解，本领域技术人员能够设想虽然没有在此处明确描述或者显示、但是实现了本发明并且包含在本发明精神与范围内的各种结构。

此处引述的所有例子与条件性语言都是出于教学目的，以帮助读者理解本发明人对现有技术作出贡献的本发明原理与概念，并且应该被理解为不限于具体引述的例子与条件。

另外，此处引述本发明的原理、方面以及实施例及其具体例子的所有语句都是要覆盖其结构与功能等价物两者。另外，此类等价物包含当前已知的等价物以及将来开发的等价物两者，即不管结构如何都执行相同功能的所有开发的元素。

由此，例如，本领域技术人员应该理解，此处呈现的方框图表示实现本发明的说明性电路的概念图示。类似地，应该理解，任何流程图、状态转移图、伪代码等等表示实际可以计算机可读介质表示、并且由计算机或者处理器执行的各种处理，而不管是否明确显示了此类计算机或者处理器。

图中显示的各种元素的功能可以通过使用专用硬件以及能够与适当软件相结合来执行软件的硬件来提供。当由处理器提供时，该功能可以由单个专用处理器、单个共享处理器、或者多个独立的处理器(某些可能被共享)提供。另外，对于术语“处理器”或者“控制器”的明确使用不应该被理解为专指能够执行软件的硬件，而是可以隐含地包括而不限于数字信号处理器(DSP)硬件、用来存储软件的只读存储器(ROM)、随机访问存储器(RAM)、以及非易失存储设备。

还可以包括其他硬件，不管是常规的和/或定制的。类似的，在附图中显示的任何开关都只是概念性的。其功能可以通过操作程序逻辑、通过专用逻辑、通过程序控制与专用逻辑的交互、甚至手动地来执行，可由实现者根据情况选择具体技术。

在权利要求书中，表示为用来执行指定功能的部件的任何元素都要覆盖执行该功能的任何方式，包括例如(a)执行该功能的电路元素的组合；或者(b)任何形式的软件，因此包括固件、微代码等等，其与适当电路组合，用来执行履行功能的软件。这些权利要求限定的本发明在于以下实际情况:由各种所引述部件提供的功能被以权利要求所主张的方式组合在一起。由此认为可以提供这些功能的任何部件都等价于此处显示的部件。

在说明书中指“一个实施例”或者“实施例”意味着结合该实施例描述的具体特征、结构、特点等等被包含在本发明的至少一个实施例中。由此，在说明书各处出现的短语“在一个实施例中”或者“在实施例中”不一定都指相同的实施例。

转到图1，附图标记100总指可以应用本发明的示范性视频编码/解码环境。视频编码/解码环境100包括:视频编码器110，其输出端以信号通信方式连接到分组化与瑞普特编码器120的输入端。分组化与瑞普特编码器120的输出端以信号通信方式连接到无线/有线网络130的接入点。无线/有线网络130的另一接入点以信号通信方式连接到解分组化与瑞普特解码器140的输入端。解分组化与瑞普特解码器140的输出端以信号通信方式连接到视频解码器150的输入端。

视频编码器110接收要编码的输入视频信号并且输出编码比特流。分组化与瑞普特编码器120利用瑞普特代码对从视频编码器输出的编码比特流进行编码，并且对结果的比特流进行分组化，以通过无线/有线网络130发送。解分组化与瑞普特解码器140对发送来的比特流进行解分组化，以进行瑞普特代码的解码，从而获得用于视频解码器150随后解码的比特流。以下更详细地描述瑞普特代码的编码与解码。

应该理解，在实施例中，本发明可以相对于例如解分组化与瑞普特解码器140实现。但是，还应该理解，图1的示范性视频编码/解码环境100为可以应用本发明的许多环境和应用中的一个。即，在给出此处提供的对本发明教导的情况下，本领域以及相关领域的技术人员能够设想这种以及可以根据本发明应用瑞普特代码的解码的各种其他环境和应用，同时保持本发明的范围。例如，可以相对于可以相对于喷泉代码和纠错代码使用的任何类型的数据实现本发明。

根据本发明，公开了用于解码瑞普特代码的方法与装置。在实施例中，本发明的实现恢复尽可能多的分组，即使当收到的源与奇偶校验分组不足以进行完全解码时(即，即使当系统未满秩时)也如此。

在实施例中，如下编码瑞普特代码。在下文中，使用码元来表示编码过程中的分组，其为比特串。根据非系统瑞普特代码，生成系统瑞普特代码。由此，首先介绍非系统瑞普特代码。

非系统瑞普特代码为分层代码，例如在3GPP的情况下，可以包含三层。当然，也可以使用不同数目的层。假定K个中间码元，[C[0]，C[1]，...，C[K-1]]^T(请注意，这些K个中间码元实际为非系统瑞普特代码的K个源码元；对于系统瑞普特代码，利用K个源码元获得K个中间码元，这将在以下进一步描述)，首先利用高比率LDPC代码如下生成S个低密度奇偶校验(LDPC)码元。

$>\left(\begin{array}{c}C\left[K\right]\\ C[K+1]\\ ·\\ ·\\ ·\\ C[K+S-1]\end{array}\right)=H_{\mathrm{LDPC}}·\left(\begin{array}{c}C\left[0\right]\\ C\left[1\right]\\ ·\\ ·\\ ·\\ C[K-1]\end{array}\right),---\left(1\right)$>

其中H_LDPC表示S×K低密度奇偶校验矩阵。然后，如下通过利用格雷序列，利用高密度奇偶校验矩阵，生成H半码元。

$>\left(\begin{array}{c}C[K+S]\\ C[K+S+1]\\ ·\\ ·\\ ·\\ C[K+S+H-1]\end{array}\right)=H_{\mathrm{Half}}·\left(\begin{array}{c}C\left[0\right]\\ C\left[1\right]\\ ·\\ ·\\ ·\\ C[K+S-1]\end{array}\right),---\left(2\right)$>

其中，H_Half为H×(K+S)高密度奇偶校验矩阵。由此，如下获得L＝K+S+H个中间码元:

请注意，H_LDPC与H_Half为具有元素0或1的矩阵。在矩阵向量乘法中，可以使用逐比特XOR运算来进行加法。

可以如下利用Luby变换(LT)矩阵生成编码码元:

$>\left(\begin{array}{c}E\left[0\right]\\ E\left[1\right]\\ ·\\ ·\\ ·\\ E[L-1]\\ ·\\ ·\\ ·\end{array}\right)=H_{\mathrm{LT}}·\left(\begin{array}{c}C\left[0\right]\\ C\left[1\right]\\ ·\\ ·\\ ·\\ C[L-1]\end{array}\right),---\left(4\right)$>

请注意，H_LT为具有L列的低密度奇偶校验矩阵，而行数可以根据希望生成多少编码码元来变化。理论上，可以生成的编码码元的数目是无限的。另外，行中1的数目符合Luby变换分布。Luby变换分布为编码码元的次数(degree)的分布，其中次数(degree)指被XOR在一起形成编码码元的中间码元的数目。表1显示了Luby变换分布。

表1

 

degreeP(degree)10.009820.459030.211040.1134100.1113110.0799400.0156

在实践中，对于非系统瑞普特代码，编码码元在编码器中生成，并且被发送给接收机一侧。由于信道的非完美性，会丢失某些编码码元。解码器的任务是在给定收到的编码码元的情况下，恢复源码元[C[0]，C[1]，...，C[K-1]]^T。

对于系统瑞普特代码，头K个编码码元一般为源码元。为了产生剩余的编码码元，计算L个中间码元[C[0]，C[1]，...，C[L-1]]^T。从非系统瑞普特代码的构造过程，得到以下关系:

构造矩阵(H_LT)_K×(K+S+H)、H_LDPC与H_Half，使得矩阵A为满秩，即L。然后，可以通过解以上方程，计算中间码元[C[0]，C[1]，...，C[L-1]]^T。请注意(H_LT)_K·(K+S+H)包括半无限矩阵H_LT的头K行。可以利用矩阵H_LT的其他行以及L个中间码元，生成所有其他编码码元。矩阵I_S×S与I_H×H为尺寸分别为S×S与H×H的单位矩阵。矩阵0_S×H为尺寸为S×H的全零矩阵。

由此，请注意，如上所述，对于系统瑞普特代码，编码处理涉及解关于方程(5)的一组线性方程。因为A为稀疏矩阵，所以解方程(5)的复杂度相对较低。

在实践中，对于系统瑞普特代码，解码器的任务是在给定收到的编码码元的情况下，恢复头K个编码码元[E[0]，E[1]，...，E[K-1]]^T。

一般地，如下解码瑞普特代码。解码处理类似于编码处理。假设收到具有索引{I₀，I₁，…，I_M-1}的M个编码码元。H_LT矩阵中对应于M个编码码元的行形成尺寸为M×L的新矩阵。因此，解码处理涉及解以下线性系统:

在实践中，当矩阵B为秩L时，方程(6)中的线性系统是可解的。否则，解码器简单地输出收到的源码元，即收到的编码码元的集合{E[I_i]|0≤I_i≤(K-1)}。

在实施例中，如下解码瑞普特代码。该实施例允许恢复尽可能多的源码元。开始笼统描述实施例，然后参照图2另外对其进行描述。

为了解码瑞普特代码，根据收到的具有索引{I₀，I₁，…，I_M-1}的M个编码码元，构造方程(6)中的线性系统。可以使用高斯消除方法将矩阵B转换为上三角矩阵。当然，本发明不仅限于使用高斯消除法，并且因此可以使用其他方法来将矩阵B转换为上三角矩阵，同时维持本发明的范围。如果三角化成功，即矩阵B为秩L，则使用回溯方法来获得中间码元[C[0]，C[1]，...，C[L-1]]^T。可以利用方程(4)计算缺失的源码元。

如果三角化失败，即矩阵B秩小于L，则一般结果为解码处理停止。但是，根据本发明的实施例，仍然进行回溯运算来获得中间码元子集，表示为[C[p₀]，C[p₁]，...，C[p_W-1]]^T，其中p_i表示中间码元的索引，W表示所恢复的中间码元的数目，0≤p_i<L，并且W<L。可以利用方程(4)以及[C[p₀]，C[p₁]，...，C[p_W-1]]^T计算缺失的源码元子集。

为了说明，提供关于回溯运算以及利用部分恢复的中间码元来恢复缺失的源码元的例子。首先，假设L＝3，并且在三角化之后，获得以下线性系统:

其中矩阵B为满秩。由此，可以成功的进行回溯运算:首先，从该系统的第三行，获得C[2]＝1；然后从第二行，$>C\left[1\right]\oplus C\left[2\right]=0,$>获得C[1]＝1；最后，从第一行，$>C\left[0\right]\oplus C\left[1\right]=1,$>获得C[0]＝0。因为恢复了所有中间码元，所以可以利用方程(4)计算所有的缺失源码元。

现在解释利用部分恢复的中间码元来恢复缺失源码元。类似地，假设L＝3。在三角化之后，获得以下线性系统:

请注意，矩阵B的秩仅为2，而不是满秩。只能恢复两个中间码元:首先，从该系统的第二行，获得C[1]＝0；然后从该系统的第一行，$>C\left[0\right]\oplus C\left[1\right]=1,$>获得C[0]＝1。即使没有恢复中间码元C[2]，仍然可以计算缺失码元E[0]＝1，这是因为E[0]＝C[0]。

在实施例中，只有当矩阵B的秩大于预定门限时，才进行上述的回溯运算。这可以节省某些运算，例如当矩阵B的秩较小时，所获得的中间码元子集为小集合。恢复某些源码元的概率可能较低。

转到图2，附图标记200总指解码瑞普特代码的示范性方法。方法200包括开始块205，其将控制传递给功能块210。功能块210接收具有索引{I₀，I₁，…，I_M-1}的编码码元，并且将控制传递给功能块215。功能块215利用方程(6)根据收到的编码码元构造线性系统方程，并且将控制传递给功能块220。功能块220利用例如高斯消除法来进行方程(6)中矩阵B的上三角化，并且将控制传递给判断块225。判断块225确定矩阵B的秩是否小于秩L。如果是，则将控制传递给判断块230。否则，将控制传递给功能块250。

判断块230确定矩阵B的秩是否大于门限。如果是，则将控制传递给功能块235。否则，将控制传递给结束块299。

功能块235使用回溯运算来恢复具有索引{p(0)，p(1)，p(W-1)}的中间码元，其中W<L，并且将控制传递给功能块240。功能块240利用具有索引{p(0)，p(1)，p(W-1)}的中间码元与方程(4)，获得缺失源码元子集，并且将控制传递给结束块299。

功能块250使用回溯运算来恢复所有中间码元，并且将控制传递给功能块255。功能块255利用方程(4)，获得所有缺失源码元，并且将控制传递给结束块299。

现在描述本发明的许多伴随优点/特征中的某一些，某些已经在以上提及。例如，一个优点/特征为一种装置，包括解码器，用来解码表示编码码元序列的分组序列。解码器利用瑞普特代码，至少部分地恢复该序列的至少某些丢失或者损坏的分组。

另一个优点/特征为一种装置，具有上述解码器，其中该解码器根据编码码元构造线性系统方程，该线性系统方程由以下表示

其中，E表示具有索引{I₀，I₁，…，I_M-1}的编码码元，M表示编码码元的数目，C[0]，C[1]，...C[L-1]表示要编码到分组序列中的中间码元，K表示当使用非系统瑞普特代码时对应于中间码元子集的源码元的数目，或者当使用系统瑞普特代码时对应于编码码元子集的源码元的数目，S表示从中间码元生成的低密度奇偶校验码元，H_LDPC表示用来生成低密度奇偶校验码元的矩阵，H表示从中间码元生成的半码元，H_Half表示用来生成半码元的矩阵，表示生成编码码元的矩阵，I_S×S表示尺寸为S×S的单位矩阵，0_S×H表示尺寸为S×H的零矩阵，I_H×H表示尺寸为H×H的单位矩阵，B表示矩阵，L表示中间码元的数目。

另一个优点/特征为一种装置，具有如上述构造线性系统方程的解码器，其中该解码器将矩阵B转换为上三角矩阵。

另外，另一个优点/特征为一种装置，具有如上述构造线性系统方程并且将矩阵B转换为上三角矩阵的解码器，其中该解码器使用高斯消除法将矩阵B转换为上三角矩阵。

另外，另一个优点/特征为一种装置，具有如上述构造线性系统方程并且将矩阵B转换为上三角矩阵的解码器，其中该解码器进行回溯运算以恢复至少某些中间码元，由[C[p₀]，C[p₁]，...，C[p_W-1]]^T表示，其中p_i表示所述至少某些中间码元中的特定一个的索引，W表示所述至少某些中间码元中的数目，0≤p_i≤L并且W<L，并且当将矩阵B转换为上三角矩阵失败时，使用以下，从所述至少某些中间码元，计算对应于丢失或者损坏的分组的丢失或者损坏的源码元:

$>\left(\begin{array}{c}E\left[0\right]\\ E\left[1\right]\\ ·\\ ·\\ ·\\ E[L-1]\\ ·\\ ·\\ ·\end{array}\right)=H_{\mathrm{LT}}·\left(\begin{array}{c}C\left[0\right]\\ C\left[1\right]\\ ·\\ ·\\ ·\\ C[L-1]\end{array}\right).$>

另外，另一个优点/特征为一种装置，具有如上述构造线性系统方程、将矩阵B转换为上三角矩阵、并且进行回溯运算的解码器，其中只有当矩阵B的秩大于预定门限时，该解码器才进行回溯运算。

另一个优点/特征为一种装置，具有上述解码器，其中该解码器进行回溯运算以获得对应于编码码元的中间码元子集，并且从该中间码元子集，计算对应于所述至少某些丢失或者损坏的分组的丢失或者损坏的源码元。

本领域技术人员根据此处的教导，可以容易地理解本发明的这些以及其他特征和优点。应该理解，可以各种形式的硬件、软件、固件、专用处理器、或者其组合，实现本发明的教导。

最优选地，将本发明的教导实现为软件和硬件的组合。另外，软件可以实现为以有形方式包含在程序存储单元上的应用程序。该应用程序可以被上传到包含任何适当体系结构的机器，并且由该机器执行。优选地，将该机器实现在计算机平台上，其具有诸如一或多个中央处理单元(CPU)、随机访问存储器(RAM)、以及输入/输出接口等硬件。该计算机平台还可以包含操作系统或者微指令代码。此处描述的各种处理与功能可以为微指令代码的一部分、或者应用程序一部分、或者为其组合，其可以由CPU执行。另外，各种其他外围单元可以连接到该计算机平台，例如附加数据存储单元以及打印单元。

还应该理解，因为在附图中显示的某些组成的系统组件与方法优选地以软件实现，所以系统组件或者处理功能块之间的实际连接可能会依赖于本发明所编程的方式而变化。在给定此处的教导的情况下，相关领域技术人员将能够设想本发明的这些以及类似实现或者配置。

虽然此处参照附图描述了说明性实施例，但是应该理解本发明不限于这些确切的实施例，并且相关领域技术人员可以进行各种变化与修改而不会脱离本发明的范围或者原理。所有这些变化与修改都要包含在权利要求书限定的本发明的范围之内。