使用基于子码元的代码来保护数据不被删除

摘要

本发明涉及一种使用基于子码元的代码来保护数据不被删除的方法。编码器(115)读取构成输入文件(101)或输入流(105)的有序的多个输入码元(110)，并产生输出子码元。该有序的多个输入码元各自是从输入字母表中选择的，且所生成的输出子码元包含输出子码元字母表中的选择。输出子码元是使用应用于输入码元的子码元的函数求值器来生成的。用于生成输出子码元的函数可以是对输入子码元中的某一些的XOR，且这些函数是从在扩域GF(2)上定义的线性码中获得的。在解码器(155)中，由接收方接收的输出子码元是从由基于输入序列的编码生成输出码元的一个发送方发送的这些输出子码元中获得的。

权利要求

1.一种用于在目的地经由通信信道从源接收数据的方法，其中所要接收的数据被排列成输入码元的有序集合，所述方法包括：经由所述通信信道接收多个输出码元，其中所述多个输出码元使得对与所编码的输入码元相等大小的所接收的输出码元的至少一个可能的集合，需要附加接收输出码元来从所述多个输出码元中完全地重新生成所述输入码元的有序集合；

从所述多个输出码元中生成多个输出子码元，其中输出子码元使用值函数和一组关联对应于一个或多个输入子码元，其中输入子码元是输入码元的一部分或全部，且至少一个输入码元被分成两个或多个输入子码元，且每一输入子码元可使用其输入码元内唯一的索引来标识，其中所述一组关联标识应用所述值函数的所述输入子码元，其中所述一组关联是使用链式反应码编码过程来确定的，其中至少一个输出子码元是各自含有其输入码元内的不同索引的多个输入子码元的函数；

从所述多个输出子码元中生成多个输入子码元；以及

从所述多个输入子码元中重新生成所述输入码元的有序集合。

2.如权利要求1所述的方法，其特征在于，给定输入码元的集合的可能的输出码元的个数相对于重新生成所述输入码元的有序集合所需的输出码元的个数实际上是无限的。

3.如权利要求1所述的方法，其特征在于，至少一个输出子码元对应于一个以上输入子码元、且少于所述输入子码元集合中的所有输入子码元、且少于至少一个输入码元中的所有子码元。

4.如权利要求1所述的方法，其特征在于，所述输入码元的每一个被分成公共个数的子码元，且所述公共个数大于1。

5.如权利要求1所述的方法，其特征在于，所述值函数对所有的输出子码元相同。

6.如权利要求1所述的方法，其特征在于，所述值函数对至少两个输出子码元不同。

7.如权利要求1所述的方法，其特征在于，所述值函数是所述一组关联的线性函数。

8.如权利要求7所述的方法，其特征在于，所述线性函数是使用交叉变换过程导出的。

9.如权利要求1所述的方法，其特征在于，所述值函数随输出子码元变化，所述值函数是使用交叉变换过程导出的所述一组关联的线性函数，其中多个值函数是使用应用于在至少高于其素域2次的有限域上定义的代码的生成矩阵的交叉变换过程得到的。

10.如权利要求9所述的方法，其特征在于，所述代码是在亏格大于0的曲线上定义的代数几何码。

11.如权利要求9所述的方法，其特征在于，所述代码是随机码。

12.如权利要求9所述的方法，其特征在于，所述代码是在作为高于其素域至少2次的扩张的有限域上的链式反应码。

13.如权利要求12所述的方法，其特征在于，所述链式反应码是随机码。

说明书

使用基于子码元的代码来保护数据不被删除

[0001] 本申请是国际申请日为2004年12月1日，申请号为PCT/US2004/040271，发明名称为“使用基于子码元的代码来保护数据不被删除”的申请的分案申请。

[0002] 相关申请的交叉引用

[0003] 本申请要求以下共同待批的美国临时专利申请的优先权：于2003年12月1日提交的名为“Protection of Data From Erasures Using Interleaved Transformationsand Codes From Algebraic Geometry(使用来自代数几何的交叉变换和代码来保护数据不被删除)”的美国临时专利申请60/526,218号(代理案卷号19186-005400US)；以及于2003年12月2日提交的名为“Protection of Data From Erasures UsingInterleaved Transformations and Codes From Algebraic Geometry(使用来自代数几何的交叉变换和代码来保护数据不被删除)”的美国临时专利申请60/526,452号，为所有目的，这些申请通过引用包含在此，如同在本文中全文描述。

[0004] 本申请也引用以下共同所有的专利和申请，包括：授予Luby的名为“Information Additive Code Generator and Decoder for Communication Systems(用于通信系统的信息加成码生成器和解码器)”的美国专利6,307,487号(后文中称为“Luby I”)以及授予Shokrollahi等人的名为“Multi-Stage Code Generator andDecoder for Communication Systems(用于通信系统的多级码生成器和解码器)”的美国专利(于2001年12月21日提交的美国专利申请10/032,156号)(后文中称为“Shokrollahi I”)，为所有目的，这些专利及申请中的每一个都通过引用包含在此，如同在本文档中全文描述。

[0005] 发明背景

[0006] 通过受损(impaired)网络传输数据成为了众多研究的主题。在众多计算机网络，诸如因特网或任何其它基于分组的网络上，通过首先将数据细分成分组，然后经由网络独立地将分组路由至目的地来发送数据。在这样的网络中，通常预期到分组的丢失。由于传输物理层上的错误、由于路由器或其它网点的溢出引起设备丢弃分组等可能会丢失分组。为确保完整地接收数据，通常使用各种机制来保护数据免于这种丢失。一般而言，丢失的单位是分组，因为分组或者被正确接收，或者就被认为丢失，并采取步骤来处理整个分组的丢失。因此，如果接收到分组的多个比特，但没有正确完整地接收该分组，该整个分组也被认为丢失。丢失可以采用遗失整个分组的形式，或可以采用确定分组中存在错误而产生不可靠的比特的形式，即删除和出错。

[0007] 近年来，提出了两种类型的代码用于当预期在传输期间将丢失数据时保护数据：链式反应码和多级链式反应码。对具有k个码元的给定内容，这些代码产生实际无限的输出码元流，使得能够从累积次数大约等于k的不同输出码元的任何集合的接收中恢复原始的k个码元。除非另外指出，否则应该理解，如此处所使用的对“一个链式反应码”或“多个链式反应码”的引用可应用于链式反应码，诸如在Luby I和/或其它地方描述的那些，且也可用于多级链式反应码，诸如Shokrollahi I中描述的那些。

[0008] 使用链式反应码，对给定的k个输入码元的输入集合的可能的输出码元个数被称为是“实际无限的”，因为几乎在所有情况中，相对于实际生成的输出码元，可能的输出码元个数要多得多，或者用于输入码元恢复的输出码元个数远小于可能码元的个数。例如，如果有10,000比特的输入码元码，且一般预期的传输是大小高达10吉比特的文件或流，则编码器应被设计成处理k＝1,000,000个码元的输入。这样的解码器可被配置成能够生成多达32
2 (40亿)个没有重复的输出码元。如果这还不够，则解码器可被配置成能够生成更多的没有重复的输出码元。当然，由于所有的物理可实现系统都是有限的，因此解码器最终将到达一种状态，在该状态中它重复，但总是可如此设计该状态，使得对任何预期的传输和出错率，没有重复的输出码元的个数是实际无限的。

[0009] 此处，分组可携带一个或多个码元。尽管不是必需的，但输入码元中所编码的比特数和输出码元中所编码的比特数可以是相同的。

[0010] 在某些实施例中，这些代码通过在输入码元上执行XOR来对数据编码，且它们通过在所接收的码元上执行XOR来解码，但也可使用或改为使用其它运算。XOR是有用的运算，因为它快速且可逆。其它运算也可提供这些优点。

[0011] 这些代码解决了将在其中发送方或接收方未知丢失率的受损网络上数据从一个或多个发送方分发到一个或多个接收方的问题。原因之一在于，当可能的输出码元数相对于输入码元数较大时，接收方可以在即使接收方之间没有协调的情况下也以该压倒性的多余(overwhelming odds)而不重复由另一接收方发送的分组。该特性被称为接收方是“信息加成(information additive)”的。

[0012] 在某些情况中，不必或不期望从给定内容中产生实际无限数量的输出码元。例如，当接收方时间受限时，可能无法享受等待附加码元在给定时间间隔之后到达的奢侈。例如，当将实况电影发送给一个或多个接收方时，情况就是这样。由于实况传输的本质，不可能总是等待足够的编码数据到达接收方，因为接收方的反馈必须与发送方的发送同步而不能被长时间地中断。在这样的情况中，预期到丢失，发送方可对内容添加固定数量的附加的冗余码元，并将内容与冗余码元一起发送。如果在内容传输期间发生的丢失的数量不大于冗余码元的个数，则预期将在接收方恢复所丢失的数据。

[0013] 也可使用链式反应码来解决这个问题。在这样的情况中，编码器仅生成固定数量的已编码数据，而不是实际无限的数据流。然而，在某些情况中，可能更适宜使用不同的解决方案。例如，由于链式反应码的解码过程的概率性本质，这些过程可能导致对非常小的内容大小的某些额外的开销。

[0014] Reed-Solomon码(“RS码”)是用于处理受到编码器输出与解码器输入之间的删除的数据的传输或存储的一类码。在本公开全文中，应理解，编码不限于传输，而是在时间、空间等分离的编码器处表示经由当已编码数据流经信道时可能展现出删除和/或错误的信道而来自解码器的原始数据。众多研究者曾对众多条件、数据和信道广泛地研究了RS码，且RS码已知具有某些性质。

[0015] 一种这样的条件被描述为“最优性条件”。RS码不在二元域而在更大的伽罗瓦域上运算。RS码的基本性质之一是它们满足最优性条件，使得当使用RS码对k个码元编码时，产生用于存储或传输的n＜k个码元，可从所编码的n个码元的k个不同的接收码元的任何可能的组合中肯定地恢复原始的k个码元。由于原始的k个码元不能从少于k个不同的接收码元中恢复，因此该接收码元数被认为是“最优的”。

[0016] 该最优性是有代价的，因为编码所需的运算次数较多，且随着代码的变长(即，使用伽罗瓦域)，次数变多。使用RS码，提前确定最大块长度n，其中块长度是从原始的k个输入码元中生成的输出码元的个数。注意到，如果丢失了多于n-k个输出码元，则不能恢复原始的k个输入码元。块长度n不能被任意加长来处理任何预期的条件，因为对较大的块长度计算变得更难，且对非常大的块长度是不切实际的。

[0017] 可以显示，对在以块长度n和维数k的伽罗瓦域GF(2A)上定义的Reed-Solomon码，产生输出码元的码元的XOR的次数平均等于k*(n-k)*A/(2*n)。使用这样的Reed-Solomon码，使用k个输入码元来产生总共n个输出码元，其中一般k个输入码元包含在n个输出码元中，且n大于k。与之对比，当使用链式反应码时，产生输出码元的码元的XOR的平均次数等于独立于k的常数或所产生的输出码元的个数。对解码器也成立类似的结果。

[0018] Reed-Solomon码的长度n不能超过2A+1。这后一条件与通常将A选为2的幂的事实一起有时可能相当大地减慢了编码和解码过程。例如，假设原始内容大小为32KB(其中1KB＝1024字节)，每一分组可对1KB的输入数据进行编码，并总共将要发送48个分组。在该示例中，内容可分为32个1KB的组块(每一组块分配给将要发送的一个分组)，然后每一组块可进一步细分成X个输入码元。然后可以并行地应用Reed-Solomon编码过程X次，每次对来自每一组块的一个输入码元进行运算(诸如对每一组块的所有第一输入码元进行运算，然后对每一组块的第二输入码元进行运算等)，这意味着每一运算考虑32个输入码元。假设这为X个位置中的每一个产生16个附加的输出码元，且将每一组X个输出码元放在一起来产生要发送的16个附加的分组，每一个长1KB。在该示例中，作为2的A幂的最小可接受的A是A＝8，因为对A＝4则将得到2+1＝17，这小于48。在该操作中，Reed-Solomon码在域GF(256)中运算，因此每一码元为1字节长，且X＝1024。如该示例所示，尽管这些码可满足最优性条件，但它们要求相当多的计算且对可能的码长度有限制。

[0019] 引出对编码论的一些概念的介绍。传输粒度指的是作为单位发送和接收的对象的大小。例如，分组网络以分组发送和接收数据。即使仅删除或破坏了分组的某些比特，但整个分组被丢弃，并激活机制(前向纠错、请求再次发送等)来整体恢复分组。因此，这样的对象以其整体或者被无错地接收或者被删除。在某些应用中，对象大小可以是传输分组的大小或者更小。当预期到传输分组之间的丢失的相关性时，则传输粒度的大于分组大小。在其它应用中，传输粒度可小于分组大小。

[0020] 计算粒度指的是在编码器和/或解码器中对其运算的对象的大小。因此，如果编码器的基本运算为XOR 128字节单位，则这就是计算粒度。包含细分成128-字节子码元的1024个字节的码元(例如，可以为分组)可以是分成8个子码元的码元(如果所有子码元具有相同大小，这不是必需的，但较为简单)且在这些子码元进行XOR。计算粒度因此为128字节。

[0021] Reed-Solomon码的最优性的原因之一在于其传输粒度与其计算粒度之间的关系。一个示例将示出这一点。

[0022] 考虑域GF(256)上的Reed-Solomon码，它用于对给定文件编码，并经由信道以各自大小为1024字节的分组发送所编码的信息。在该示例中，计算粒度可等于128字节(1024字节除以8)，而传输粒度等于1024字节。在该示例中，诸如比特序列的XOR等基本运算在作为整体的128字节单位上进行。

[0023] 通常，编码和解码的效率随计算粒度而变化。可按照多种方式测量效率，而测量的一种方法是按照编码或解码数据单位的运算的平均次数。通常，编码和解码对较细的计算粒度效率较低，而对较粗的计算粒度效率较高。然而，较细计算粒度的代码可提供较好的接收开销，即确保对表示向编码器提供的码元数上的正确解码所需接收的额外码元数可保持非常小。作为结果，对给定码在编码效率与传输开销之间存在折衷。

[0024] Reed-Solomon码处于该编码折衷的一端，因为计算粒度足够小，使得在接收了与编码一样多的数据之后，可保证对面临删除的数据的最优恢复。在另一端，在二元字母表上定义的码(诸如用于在分组网络上传输的那些)具有与传输粒度一样大的计算粒度，但可能在确保完整解码所需的接收开销上效率低下。

[0025] 如上所述，Reed-Solomon码需要预先确定最大出错率，即如果将k个码元编码成n个RS-码元，则大于(n-k)/n的出错率将使得解码器不能恢复所发送的数据。因此，在由所发送数据的不成功恢复的最终概率测量的传输系统中，Reed-Solomon码尽管其最优性但还是显示出正的失败概率。这是因为，存在由接收方接收的数据量实际上小于所发送的数据的正概率。作为结果，最终，编码系统可能具有较低效率的编码，而仍旧具有需要降低的失败概率。

[0026] 因此，需要的是这样一种用于编码和解码经由信道发送的数据的编码系统和方法，它可如特定应用、可用的处理能力和数据集所需地折衷计算工作量和开销效率。

[0027] 发明概述

[0028] 在根据本发明的通信系统的一个实施例中，编码器使用输出码元的子码元来实现或控制计算工作量和开销效率的折衷，用于例如，以少量的开销效率为代价极大地减少计算工作量。编码器读取构成输入文件或输入流的有序的多个输入码元，并产生输出子码元。该有序的多个输入码元各自是从输入字母表中选择的，且所生成的输出子码元构成输出子码元字母表中的选择。输出子码元是使用应用于输入码元的子码元的函数求值器生成的。
在某些实施例中，可调用编码器一次或多次，每一次产生一个输出子码元。然后可将输出子码元组装成输出码元，并将其发送至其目的地。

[0029] 在根据本发明的各方面的一个编码过程中，用于从输入子码元生成输出子码元的函数是对输入子码元中某一些的XOR。在根据本发明的各个方面的另一编码过程中，这些函数是通过使用GF(2)上的扩域的正则表达式将该码的生成矩阵或奇偶校验矩阵中的每一条目变换成适当的二元矩阵，从在GF(2)的扩域上定义的线性码获得的。

[0030] 在根据本发明的各方面的解码器中，由接收方接收的输出子码元是从由基于输入序列(文件、流等)的编码生成这些输出码元的一个发送方发送的输出码元中获得的。因为在传输中输出码元可能丢失，即使解码器仅接收到所发送的输出码元的任意一部分，它也正常操作。

[0031] 本发明提供诸如能够控制计算工作量与传输消息的折衷的优点。例如，放松最优性要求，对可能的传输工作量的小小增加将可极大地减少计算工作量。使用某些代码，可容易地得到附加的输出，使得可仅在接收超过最优性条件下解码所需的码元数的相对少量的附加码元的情况下任意地减少解码失败率。在实现中，通过计算单位(作为单独的编码或解码运算的一部分的数据之间的界限)和丢失单位(数据之间的界限，其中如果单位界限内的任何数据不可用则，该单位界限内的所有数据被认为丢失)可减少计算工作量。在具体实现中，丢失单位为码元或分组，计算单位为子码元。

[0032] 可通过参考说明书的其余部分和附图来实现对此处所公开的本发明的本质和优点的进一步理解。

[0033] 附图描述

[0034] 图1是根据本发明的一个实施例的通信系统的框图。

[0035] 图2是更详细示出的图1中的编码器1的一部分的框图。

[0036] 图3示出了生成矩阵；图3A示出了GF(4)域上的基础矩阵，而图3B示出了GF(2)上的二元生成矩阵。

[0037] 图4是图1中输出码元生成器的图示。

[0038] 图5是图1中子码元生成器的图示。

[0039] 发明的详细描述

[0040] 在此处所述的示例中，描述了称为“基于子码元的编码”的编码方案，首先是对本说明书中使用的各种术语的意义和范围的解释。

[0041] 编码器是从文件、流或其它输入数据源接收输入数据并对该数据编码使得信道可能对数据产生的影响可由信道的另一端处的解码器纠正，而使解码器能以所需的任何准确度重新生成原始数据的软件过程、硬件装置、组合等。

[0042] 使用基于子码元的编码，由发送方按所需从输入文件中生成输出码元。每一输出码元包含一个或多个子码元，其中至少一个输出码元包含至少两个子码元。输出码元内的每一子码元是通过使用编码器或解码器软件和/或硬件，对构成输入文件的码元的子码元执行计算运算来生成的。一旦生成之后，输出码元然后可置于分组之中，并发送至其目的地，每一分组包含一个或多个输出码元。

[0043] 如此处所使用的，术语“文件”指的是存储在一个或多个源处且要作为一个单位传递到一个或多个目的地的任何数据。因此，来自文件服务器或计算机存储设备的文档、图像和文件都是可传递的“文件”的示例。文件可具有已知大小(诸如存储在硬盘上的1兆图像)或可具有未知大小(诸如从流源的输出取出的文件)。在任一方法中，文件都是输入码元的序列，其中每一输入码元具有一个文件中的位置和一个值。

[0044] 传输是经由信道将数据从一个或多个发送方发送到一个或多个接收方以便传递文件的过程。如果一个发送方经由完美的信道连接至任何数量的接收方，则由于所有的数据都将被正确接收，因此所接收的数据可以是输入文件的精确副本。此处，假定信道不是完美的，这也是大多数现实信道的情况。在众多信道不完善性之中，所感兴趣的两个不完善性是数据删除和数据不完整性(这可作为数据删除的特殊情况处理)。当信道丢失或掉落数据时发生数据删除。当接收方在数据中的某些已经通过之前没有开始接收数据、接收方在传输结束之前停止接收、或接收方间断地停止并再次开始接收数据时，发生数据不完整性。作为数据不完整性的一个示例，移动卫星发送方可能发送表示输入文件的数据并在接收方处于范围之中之前开始发送。一旦接收方位于范围之中，可接收数据直到卫星移动到范围之外，此处接收方可重定向其卫星天线(在此期间它没有接收数据)来开始接收关于由已经移动到范围之内的另一卫星发送的同一输入文件的数据。

[0045] 如通过阅读本说明书应该显而易见的，由于接收方可如同接收方在全部时间内都在范围之内，但直到接收方开始接收数据的那一点之前信道丢失所有的数据一样来对待数据不完整性(且接收方具有相同的问题)，因此数据不完整性是数据删除的特殊情况。同样，如在通信系统设计中公知的，可单单通过掉落含有可检测错误的所有数据块或码元，可检测错误可等价于删除。

[0046] 一般而言，传输是通过连接发送方和接收方的信道将数据从发送方移动到接收方的动作。信道可以是实时信道，其中当信道获得数据时信道将数据从发送方移动到接收方，或者信道可以是在数据从发送方到接收方的传输中存储某些或所有数据的存储信道。后者的一个示例是磁盘存储或其它存储设备。在该示例中，生成数据的程序或设备可被看作是发送方，它将数据发送给存储设备。接收方是从存储设备中读取数据的程序或设备。发送方用来将数据放到存储设备上的机制、存储设备本身以及接收方用来从存储设备中获得数据的机制共同构成了信道。如果存在这些机制或存储设备可能丢失数据的几率，则将被作为信道中的数据删除来对待。

[0047] 1.基本实现

[0048] 在一个典型实现中，使用基于子码元的编码来发送文件涉及，从输入文件中生成、形成或提取输入码元，为每一输入码元生成子码元、将这些子码元编码成一个或多个输出子码元、从输出子码元中创建输出码元以及通过信道将该输出码元发送到一个或多个接收方。

[0049] 使用基于子码元的编码来接收(或重建)输入文件的副本涉及，从一个或多个数据流接收输出码元的某一集合或子集、为每一所接收到的输出码元生成子码元、从所接收的输出子码元的值中解码输入子码元、从所解码的输入子码元中创建输入码元、以及从输入码元中重新组装输入文件。在某些实施例中，例如当输入文件可从所解码的输入子码元中直接重新组装时，丢弃了最后一步。

[0050] 现在将参考附图来描述本发明的各方面。

[0051] 图1是使用基于子码元的编码的通信系统100的框图。在通信系统100中，向子码元生成器110提供输入文件101或输入流105。子码元生成器110从输入文件或流中生成一个或多个输入子码元的序列(IS(0，0)，IS(0，1)，IS(0，2)，...)，每一输入码元具有一个值和两个位置(图1中示为括号内的整数)。子码元生成器110将值m用作为其输入之一，这是每一输入或输出码元内的子码元的个数。子码元生成器的输出被分成每组m个的组，使用第二括号内的整数标识每一组的元素，它是0与m-1之间的整数。

[0052] 如上所述，每一输入子码元的大小是编码系统的计算粒度，而传输粒度可以是大于或等于m倍计算粒度的任何数字。在此处所提供的示例中，为说明简单起见，通常假定子码元的大小都是相等的，但应该理解，大小可以有变化，且对正确的运行而言不必使用恒定的大小。

[0053] 输入子码元的可能值，即其字母表，一般是2M个码元的字母表，使得每一输入码元对输入文件的M个比特编码。M的值一般由通信系统100的用途来确定，但通用系统可包括对输入子码元生成器110的子码元大小输入，使得M可随用途而有所变化。将输入子码元生成器110的输出提供给编码器115。

[0054] 编码器115从由输入子码元生成器110提供的输入子码元生成输出子码元，其值为OS(i，j)。每一输出子码元的值是基于对一个或多个输入子码元的某一函数生成的，这些输入子码元在此处称为输出子码元的“相关联输入码元”或简称为“关联”。函数(“值函数”)和关联的选择是根据以下将更详细描述的过程完成的。通常，但不总是，M对输入子码元和输出子码元是相同的，即它们均对同样个数的比特编码。

[0055] 在某些实施例中，编码器使用输入子码元的个数K来选择关联。如果K事先未知，诸如当输入是流文件时，则K可以仅仅是估计值。值K也可由编码器115用来为输入子码元分配存储。

[0056] 编码器115向输出码元生成器135提供输出子码元。也向输出码元生成器135提供每一码元内的子码元个数m。输出码元生成器135将图1中示为OS(0)，OS(1)，...，等的其输出提供给发送模块140。发送模块140通过信道145将输出码元发送给接收模块150。假定信道145为删除信道，但这不是通信系统100的正确操作的要求。模块140、145和150可以是任何合适的硬件组件、软件组件、物理介质或其任何组合，只要发送模块140适于将输出码元以及关于它们的键的任何所需数据发送到信道145，且接收模块150适于从信道
145接收码元和可能某些关于它们的键的数据。值K如果用于确定关联，则可经由信道145发送它，或者它可由编码器115和解码器155的协议预先设定。

[0057] 如上所述，信道145可以是实时信道，诸如穿过因特网的路径或从电视发射机到电视接收器的广播链路或从一点到另一点的电话连接，或者信道145可以是存储信道，诸如CD-ROM、磁盘驱动器、万维网站等。信道145甚至可能是实时信道和存储信道的组合，诸如当一人通过电话线将输入文件从个人计算机发送到因特网服务供应商(ISP)时形成的信道，输入文件存储在Web服务器上，并随后经由因特网发送给接收方。

[0058] 因为假定信道145是删除信道，因此通信系统100不假定离开接收模块150的输出码元与进入发送模块140的输出码元之间的一一对应。事实上，当信道145包括分组网络时，通信系统100甚至可能不能假定通过信道145的传输中保持的任何两个或多个分组的相对顺序。

[0059] 接收模块150将所接收到的码元RS(0)、RS(1)提供给子码元生成器160。也向该生成器给出每一所接收的输出码元包含的子码元个数的值m。该信息可在传输之前在发送方与接收方之间共享，它可以是传输的一部分，或者如果它对接收方未知且接收方不必立刻解码，则它可在稍后提供。如前所述，对所有接收的输出码元，值m不必相同。

[0060] 子码元生成器160生成示为RS(0，0)，RS(0，1)，...，等的输出，并将其给予解码器155。当每一所接收的码元包含m个子码元时，子码元生成器160的输出被分成各自含有m个的组，其中每一组对应于每一所接收的码元内的子码元。第二括号内的整数对应于子码元在所接收的码元内的位置，而第一个整数对应于输出的子码元是其子码元的所接收的码元。在这种情况中，子码元生成器的输出为RS(0，0)，...，RS(0，m-1)，RS(1，0)，...RS(1，m-1)等。

[0061] 解码器155使用由子码元生成器160提供的输出子码元来恢复输入子码元(再一次为IS(0，0)，IS(0，1)，IS(0，2)，...)。解码器155将所恢复的输入子码元提供给码元生成器162，后者又产生输入码元IS(0)，IS(0)，...等。将这些输入码元提供给输入文件重新组装器165，后者生成输入文件101或输入流105的副本170。在某些应用中，可绕过码元生成器162，而将输出直接转发给输入文件重新组装器165。

[0062] 2.基本编码器

[0063] 图2是基本编码器的示例性框图。对每一生成的输出码元230，它包含由F(i，j)表示的函数求值器。在图2的示例中，m＝4且总共存在12个输入子码元，由201，...，212表示。函数求值器220计算输入子码元的函数来生成输出子码元230。例如，在图2所示的情况中，函数求值器使用函数F(i，j)来从输入IS(0，0)，IS(0，3)，IS(1，1)，IS(1，3)和IS(2，2)中生成其输出OS(i，j)的值。

[0064] 在某些实施例中，每一生成的输出子码元具有不同的相关联的函数，这是确定性或伪随机生成的。在其它实施例中，函数求值器220可以对所生成的输出码元中的多个是相同的，且可仅在用于函数的输入值集合中有所不同。例如，如果使用简单的交叉方案，则对j的所有值，F(i，j)都可以是相同的，且仅在输入值集合中有所不同。特别地，在该情况中，函数F(i，j)仅使用子码元IS(0，j)，IS(1，j)，IS(2，j)等作为输入。

[0065] 如图2中所示，函数求值器220可以是其输入的任何函数。在某些实施例中，尤其在那些期望具有线性码的情况中，应选择是自变量的线性函数的函数，例如自变量的XOR。现在将描述可由函数求值器220使用的一类这样的线性函数，称为“交叉变换”。

[0066] 3.交叉变换

[0067] 此处描述的某些过程使用了Bloemer、Kalfane、Karp、Karpinski、Luby和Zuckerman的国际计算机科学协会(ICSI)技术报告TR-95-048“An XOR basederasure resilient coding scheme(基于XOR的删除弹性编码方案)”中隐含叙述的方法。

[0068] 考虑将以s个码元组织的输入数据变换成以t个码元组织的输出数据的变换过程，其中(输入数据和输出数据的)每一码元包含相等大小的m个子码元，且其中变换使用mt行s列的基础矩阵，每一基础矩阵的条目是有限域GF(2)中的值。

[0069] 该变换过程由将基础矩阵的每一条目变换成m行m列的二元矩阵开始。该变换使用有限域的正则表达式作为GF(2)的模，这是有限代数和编码理论领域中普通技术人员所公知的概念，因此将不在这里详细描述。对原始的基础矩阵的所有条目应用该变换，产生t*m行s*m列的新的二元矩阵。该变换过程对输入数据的s*m个子码元应用该新的矩阵来得出t*m个输出子码元，新二元矩阵每行一个。新二元矩阵的每一行对应于一个子码元，其中该变换过程通过对行和列中有一个1的每一输入子码元进行XOR来确定给定的输出子码元。以这种方式创建的最终的t*m个子码元被分组成各自具有m个子码元的组来产生t个码元。

[0070] 注意，该变换过程仅需要执行子码元的XOR。它执行XOR的次数取决于原始矩阵，但该次数平均等于s*t*m/2。

[0071] 作为上述变换过程的一个示例，考虑图3A中所示的在域GF(4)＝{0，1，α，α2}上的s＝5而t＝2的基础矩阵。对GF(4)，m＝2。使用GF(4)在对于基{1，α}的GF(2)上的正则表达式，图3A的基础矩阵变换成图3B中所示的新二元矩阵，它是s*m＝10行t*m＝4列的矩阵。

[0072] 使用该变换后的矩阵，包含5个码元、每一码元包含2个子码元的原始数据如下变换：四个输出子码元中的第一个被计算为输入子码元3，6，7，9，10的XOR，因为这些是图3B的矩阵的第一行中“1”的位置。注意，“1”是对二元值的一种状态的任意指示，因此应将其视为使用输入码元的标志。

[0073] 第二个输出子码元被计算为输入子码元4，5，6，8，9的XOR。第三输出子码元被计算为输入子码元1，5，8，10的XOR。最后，最后一个(第四个)输出子码元被计算为输入子码元2，6，7，8，9，10的XOR。在该情形中，执行子码元的XOR的总次数为20。

[0074] 如下给出该特定示例中的函数F(i，j)：

[0075] F(0，0)＝IS(1，0)+IS(2，1)+IS(3，0)+IS(4，0)+IS(4，1)

[0076] F(0，1)＝IS(1，1)+IS(2，0)+IS(2，1)+IS(3，1)+IS(4，0)

[0077] F(1，0)＝IS(0，0)+IS(2，0)+IS(3，1)+IS(4，1)

[0078] F(1，1)＝IS(0，1)+IS(2，1)+IS(3，0)+IS(3，1)+IS(4，0)+IS(4，1)

[0079] 其中符号“+”表示XOR。

[0080] 交叉变换可用作使用由GF(2)扩域上的其生成矩阵和奇偶校验矩阵定义的代码的编码器和/或解码器的实施例的一部分。

[0081] 4.基本输出码元生成器

[0082] 图4是输出码元生成器135的框图。该图例示了m＝4且3个输出码元的情况。在该示例中，输出码元生成器135将四个输出码元的组，示为OS(i，0)，OS(i，1)，OS(i，
2)，...，OS(i，m-1)(该附图中标为401，...412)打包成输出码元OS(i)(在附图中标为
420、430和440)。对所有输出码元选择相同的值m仅是为了简明起见。该值对不同的输出码元可有所不同，只要输出码元生成器指示对要生成的输出码元值m是什么。

[0083] 5.基本子码元生成器

[0084] 图5是基本子码元生成器160的框图。该图例示了m＝4，且3个所接收码元RS(0)、RS(1)、RS(2)的情况。子码元生成器160的运算对应于图4中给出的输出码元生成器135的运算的逆运算。

[0085] 在图5中给出的示例中，子码元生成器135为每一所接收到的码元创建4个子码元(图中子码元标记为501，...，512)。子码元RS(i，0)，...，RS(i，3)对应于所接收到的码元RS(i)(该附图中标记为520、530和540)。对所有所接收的码元选择相同的值m仅是为了简明起见。该值对不同的所接收码元可有所不同，只要对每一所接收的码元向子码元生成器提供对该码元的值m为何的指示。这样的指示可通过来自发送器的带外信息或者通过由发送方和接收方共享的预先确定的算法来提供给子码元生成器。

[0086] 6.使用GF(2)扩域上的交叉变换和代码的基于子码元的编码

[0087] 如上所述，基于子码元的编码可与此处所述的交叉变换一起使用来设计用于在预期删除的分组网络上传输的代码，使得该代码显示出关于计算和删除粒度与工作量的期望折衷。

[0088] 在一个实施例中，编码器和解码器被配置成使用在扩域GF(2m)上定义的代码。该代码可由生成矩阵、奇偶校验矩阵或达到类似结果的某种抽象编码过程或规则集来定义。为表达简明起见，此处示例使用生成矩阵来描述编码，但应理解，可对相同、相似、不同的结果使用其它方法。

[0089] 假设生成矩阵具有n行和k列。假定该代码是系统的，可以理解，该代码也可以改为非系统的。

[0090] 使用系统码，包含前k列的子矩阵是单位矩阵。包含其余的r＝n-k列的子矩阵此处称为C。该矩阵C具有r行和k列。假定要编码的数据是k个码元(或分组)长。则编码过程是将以上的交叉变换过程应用于矩阵C和要编码的数据的过程。

[0091] 与以往的编码方法相比，这种编码方法的优点之一在于，传输方案的开销性质由m有限域GF(2)上原始码的结构来支配，而计算是在域GF(2)上执行的。对代码参数的明智选择，诸如此处所述的或根据此处所述的选择方法，可能获得提供上述折衷的优异平衡的编码结构。

[0092] 由于子码元的存在，解码过程更为复杂，且一般以如下所述的步骤进行。值得注意的是，解码计算工作量仍旧可比用来获得相同的错误恢复结果的前述方法少。

[0093] 在一个示例解码过程中，假定所编码的数据分组各自具有相关联的位置，且该位置可由1到n的整数表示。前k个位置被称为系统位置，在传输之前处于这些位置中的所编码数据与要编码的数据完全相同。其余位置中的数据(或分组)称为冗余分组。如前所述，假定给出一个生成矩阵，其中前k行形成单位矩阵，而其余的r行形成矩阵C。

[0094] 在解码过程的一个实施例中，步骤如下：

[0095] 1)记录和存储已删除系统分组的位置q1，q2，...，qe，其中e是这样的已删除分组的个数。如果没有这样的分组存在，声明成功解码并退出。

[0096] 2)置计数器l＝0。

[0097] 3)当解码不成功(即，还没有恢复所有的原始分组)，执行以下的子步骤(a)到(e)：

[0098] (a)找出e+l个非已删除冗余分组。如果少于e+l个非已删除冗余分组可用，则声明解码出错。否则，由p1，p2，...，pe+l表示e+l个非已删除冗余分组的位置。

[0099] (b)形成包含对应于位置p1，p2，...，pe+l的行和对应于位置q1，q2，...，qe的列的生成矩阵的子矩阵。将这个矩阵称为D。注意到该矩阵为C的子矩阵。

[0100] (c)找出D的可逆的e×e子矩阵，例如通过高斯消去法或显式确定或其它方法。如果这样的子矩阵不存在，则对计数器l增加1并前进至步骤3。

[0101] (d)如果这样的可逆子矩阵存在，则记录其行r1，...，re，并在基域上计算其逆，将该逆称为B。

[0102] (e)对矩阵B和包含位置r1，...，re处的冗余分组的数据应用交叉变换来获得位置q1，q2，...，qe处的已删除系统分组。声明解码成功并停止。

[0103] 以下是使用一个特定值集的这种解码过程的详细示例。假设k＝16且n＝24，并假设在传输了24个分组之后，接收到位置1，2，4，5，6，7，8，9，11，12，13，14，15，16，18，20，22处的分组。丢失了位置3和10处的系统分组，而其它14个正确接收。所以q1＝3而q2＝10。将计数器l置为0，获得2+0＝2个非已删除冗余分组。这可以是位置18和20处的分组，所以p1＝18而p2＝20。设置具有生成矩阵的行18和20以及列3和10的矩阵，即行2和4以及列3和10的C的子矩阵。假设该矩阵的秩不为2，则步骤3(c)不成功。增加计数器l为1，并返回至步骤3，该过程继续。此时，例如设置p1＝18，p2＝20且p3＝22，可形成包含生成矩阵的这几行和列3和10的C的子矩阵。如果该矩阵满秩，则步骤3(c)将成功，且对应于非已删除系统位置18和22的行1和3将形成可逆子矩阵。在步骤3(d)计算该矩阵的逆，称为B，并将交叉变换过程(步骤3(e))应用于该矩阵和包含位置18和
22处冗余分组的数据，这将产生在位置3和10处的已删除分组的值。

[0104] 在某些实施例中，在步骤2中，可对值l选择某个大于0的数字。这可在例如如果预期对所有的小值l，步骤3(c)将不成功时发生。有可能有众多其它的变化，本领域的普通技术人员可在阅读本公开之后推导出这些变化。

[0105] 7.代数几何码

[0106] 结合交叉变换的子码元解码过程产生尤其良好结果的一类代码为代数几何码类，即“AG码”。AG码是Reed-Solomon码的扩展，它允许在同一域上构造远长于Reed-Solomon码的代码。这些代码是使用有限域上的曲线的点以及曲线在规定的极点上的函数构造的。对这些代码的构造对有限代数和编码论领域的普通技术人员而言是公知的，从而不在此处详细描述。这些代码的各种文献之一是Goppa，V.D的“Geometry and Codes(几何与代码)”(Kluwer Academic Publisher 1988)。

[0107] AG码共享许多Reed-Solomon码的性质。它们通常可由显式的生成矩阵和奇偶校验矩阵描述，且给定其维数k和块长度n，其最小距离不能小于n-k+1-g，其中g是作为底层曲线的参数的非负整数。该参数被称为曲线的亏格(genus)。亏格0的曲线一般产生Reed-Solomon码，而较高亏格的曲线可产生就块长度而言有实质改进(虽然以较小的最小距离为代价)的代码。

[0108] 例如，如果底层域为GF(16)，则最长的可能的Reed-Solomon码具有块长度17。与之对比，可能显示出具有块长度24的亏格1的AG码。该代码的最小距离比最优值小1。这样的代码可用于以下示例性情况中。该情况仅用于说明性的目的描述，而不旨在限制应用的范围。

[0109] 假设将经由网络传输16KB长的一段数据，其中分组具有1KB的有效负载。而且，假设针对33％的丢失保护数据。然后，使用亏格1、块长度24且维数16的AG码的生成矩阵，并使用上述交叉变换过程，可能产生24KB的经编码的内容。由于每一子码元是分组有效负载(即，码元)的1/4，该变换涉及大小为256字节的子码元的XOR。得到的代码具有以1的概率从接收的17个分组的任意集合中解码原始的16个分组，并以大约96％的概率形成接收的16个分组的集合(即，16个分组的可能组合的96％使得可从该组合中解码原始的16个分组)的能力。

[0110] 可使AG码成为系统的。例如，在以上情况中，所编码数据的前16KB可等于原始的16KB，附加的8KB表示冗余数据。为产生该冗余数据，对8行16列的矩阵应用上述交叉变换过程。在这样的情况中，产生冗余数据的子码元XOR的次数平均为8*16*4/2，即256。在该操作之后，所产生的经编码的数据包含96个子码元，使得每个生成的子码元的子码元XOR次数为256/96，稍小于3。

[0111] 如果以上使用Reed-Solomon码，则其上定义Reed-Solomon码、作为2的幂的最小可能的域扩张需要为GF(256)。在这种情况中，子码元将与前一情况中的一半一样大，且它平均需要8*16*8/2＝512次子码元的XOR来产生冗余数据，这又转化成前一情况的编码速度的一半。

[0112] 以下描述了可用于在分组有效负载大小为1KB的基于分组的网络上传输多达64KB大小的内容的某种AG码。这些示例仅用于说明性的目的，而不应解释为限制本发明的范围。这些示例由所编码内容的长度而不是原始内容的长度作为参数。对后者的转换可通过期望的保护丢失率来进行。例如，当所编码内容的长度为24KB，且预期25％的丢失时，则原始内容的长度可设为等于18KB。

[0113] 对多达8KB的所编码内容大小而言，可能使用来自带有9个有理点的最大可能个数的GF(4)上的椭圆曲线的AG码。这样的曲线的一个示例为Hermitian曲线。对应于该曲线的代码保证可能从最多超过1个附加分组来恢复内容。对该任务的Reed-Solomon码将必须在域GF(16)中操作，并大约折半此示例中构造的AG码的编码和解码速度。

[0114] 对多达24KB的所编码内容大小而言，可能使用来自带有25个有理点的最大可能个数的GF(16)上的椭圆曲线的AG码。这样的曲线对本领域的普通技术人员而言是公知的，因此可容易地构造相应的代码。对这些代码，保证上述解码过程中的索引l永远不会超过1。换言之，如果所接收的分组个数比原始分组个数大1，则解码过程即成功。然而，如果所接收到的分组的个数等于原始分组的个数，则存在与解码器相关联的失败的某种概率。在此情况中，该概率可在数学上计算，大约等于1/25，即4％。

[0115] 对多达32KB的所编码内容大小而言，可能使用来自带有33个点的GF(16)上亏格2的最大超椭圆曲线的AG码。该曲线对本领域的普通技术人员而言也是公知的，相关联代码的构造也是如此。在该情况中，以上过程中的索引l永不超过2。对多达37KB的所编码内容大小而言，可能使用来自带有38个点的GF(16)上亏格3的最大曲线的AG码。在该情况中，以上过程中的索引l永不超过3。对多达44KB的所编码内容大小而言，可能使用来自带有38个点的GF(16)上亏格4的最大曲线的AG码。在该情况中，以上过程中的索引l永不超过4。对多达64KB的所编码内容大小而言，可能使用带有65个有理点的GF(16)上的Hermitian曲线。在该情况中，索引l永不超过值6。

[0116] 在以上情况的每一个中，从任何k个所接收到的分组中都能以某一良好的概率恢复包含k个分组的原始内容，且该概率随这所接收到的分组的个数超过k而快速增加，如果超过的量等于所使用的曲线的亏格则到达概率1。

[0117] 8.随机码

[0118] 与交叉变换结合的基于子码元的编码过程对块码决不特别。一般而言，本发明的m教导可受益于有限域GF(2)上的任何码，或者更一般地，任何有限域GF(q)上的任何码。例如，该过程可与随机码结合来获得有益的效果。

[0119] 随机码可用作块码，或类似于链式反应码，对其而言，可生成的输出码元的个数预先是不固定的，而约为大于输入码元个数的数量级。具体地，可能的输出码元的个数可以比任何预期的丢失模式大，使得发送器(或一组发送器，可能未协调的)不必为期望成功传输而在一段时间上重复输出码元。尽管没有物理过程可以真正是无限的且可重复的，但可容易地使用如Luby I或他处所述的链式反应码，使得给定输入序列的输出码元的个数是实际无限的。因为输出码元的不相关序列不太可能重叠(由于给定输入序列的输出码元的较大空间)，这些码有时被称为“信息加成码”。

[0120] 对随机块码，生成矩阵是通过随机或伪随机地选择GF(q)中的元素获得的。应理解，如此处所用，“随机”也可包含“伪随机”，但为改进本公开的可读性起见，没有在所有地方都明确地指出。域大小q负责矩阵的秩性质。一般而言，q越大，则给定维数的矩阵具有满秩的可能性越高。上述解码过程中步骤3(c)的成功与否是由矩阵的秩性质确定的。

[0121] 对GF(q)上的随机链式反应码，每一输出码元是使用如Luby I和Shokrollahi I中所述的键来生成的。对每一键，选择输入码元的子集，并随之对输入码元元素中的每一个选择域GF(q)中的随机或伪随机元素。概念上，形成包含GF(q)中所选值以及对对应于未选择的输入码元的那些位置的0的向量，且将结合交叉变换的基于子码元的编码过程应用于该矩阵。创建矩阵的中间步骤纯粹是概念性的，可在应用中整体省略。

[0122] 作为示例，再次考虑GF(16)上的代码的情况。k行k列的随机矩阵在有大约等于93％的概率的GF(16)上可逆。(应理解，除非以其它方式指出，否则对此处描述为“随机”的任何事物，也可使用“伪随机”。)这意味着，在应用上述解码过程中，在93％的情况中，计数器l保持为0，因此不需要接收超过原始数据大小的数据。k行k+1列的随机矩阵有大约等于99.5％的概率具有秩k。这意味着，仅在0.5％的情况中，计数器l才会达到2。类似地，l永不超过2的概率大约为99.7％，l永不超过3的概率大约为99.998％，l永不超过4的-9
概率大约为99.99998％，诸如此类，且它超过6的概率大约为4×10 。表1示出了解码器对所接收的超额分组的个数的各个其它值的出错概率。表1中的数据示出了可能构造具有非常良好的开销的随机码，因为它们是在较小的域上构建的，因此它们具有比Reed-Solomon码更有效编码和解码算法。

[0123] 表1

[0124] 所接收到的超额分组 解码出错概率

[0125] 0 6.6×10-2

[0126] 1 4.2×10-3

[0127] 2 2.7×10-4

[0128] 3 1.7×10-5

[0129] 4 1.2×10-6

[0130] 5 6.4×10-8

[0131] 6 4.0×10-9

[0132] 7 2.5×10-10

[0133] 8 1.6×10-11

[0134] 9 9.8×10-13

[0135] 10 6.1×10-14

[0136] 域GF(4)上发生类似的结果。表2示出了GF(4)上作为所接收的超额分组的个数的函数的解码器的出错概率。注意，相比GF(16)上的代码，GF(4)增加了一倍的编码和解码速度。

[0137] 表2

[0138] 所接收到的超额分组 解码出错概率

[0139] 0 3.1×10-1

[0140] 1 8.2×10-2

[0141] 2 2.1×10-2

[0142] 3 5.2×10-3

[0143] 4 1.3×10-3

[0144] 5 3.3×10-4

[0145] 6 8.2×10-5

[0146] 7 2.1×10-5

[0147] 8 5.1×10-6

[0148] 9 1.3×10-6

[0149] 10 3.2×10-7

[0150] 以上的数字示出，即使在非常小的开销的情况下，基于信息加成码的GF(4)或GF(16)上的随机码也运行得非常优异。

[0151] 尽管示出了与交叉变换一起使用的非Reed-Solomon编码的若干示例，但其它非Reed-Solomon基础矩阵也可起作用。

[0152] 变化

[0153] 在某些变化中，并行操作编码器来更快速地生成输出码元。为了获得子码元操作的某些便利，并行编码器模块应该是相互依赖而不是完全独立操作的。例如，并行编码器可协调在多个输入码元中对子码元集合的选择用于值函数的应用，使得子码元在多个输入码元中混合且来自输入码元内的不同子码元位置。

[0154] 结论

[0155] 基于子码元的编码可使用少于Reed-Solomon码的算术运算来操作。注意到，如果要求了最优性条件，则这样的代码不存在，但是通过放松该要求，则可能有所感兴趣的代码。尽管可示出，对这样的码不得不丧失就必须接收以便能够解码原始内容的输出码元的个数而言的最优性条件，但是某类代码显示出示出它们在大多数情况中类似于Reed-Solomon码执行，且仅在少量情况中需要额外的码元来恢复原始内容的合理的统计特性。

[0156] 观察到不总是要求绝对的最优性，且这并不总是导向对数据的完全恢复，通常可以相当少的计算工作量来得到足够好的接近最优传输效率。例如，使用具有较小字母表的代码极大地减少了计算工作量，同时仅引起对绝对最优性的稍微放松。

[0157] 在某些较佳实施例中，向经由可能有损的通信介质通信的两个或多个多用途计算机提供执行上述通信过程的指令集(或软件)。机器的个数可从一个发送方和一个接收方变化到任何数量的发送和/或接收的机器。连接机器的通信介质可以是有线、光学、无线等。上述通信系统具有多种用途，通过阅读本说明书这是显而易见的。

[0158] 以上描述是说明性而非限制性的。在审阅本公开之后，对本领域的技术人员而言，本发明的各种变化是显而易见的。从而，本发明的范围不是参考以上描述确定的，而是参考所附权利要求书以及其等效实施方式的全部范围来确定的。