公开(公告)号：WO2006135877A2

公开(公告)日：2006-12-21

申请号：PCT/US2006/022913

申请日：2006-06-12

Applicant: DIGITAL FOUNTAIN, INC. ,  LUBY, Michael, G. ,  WATSON, Mark ,  SHOKROLLAHI, M. Amin

Inventor： LUBY, Michael, G. ,  WATSON, Mark ,  SHOKROLLAHI, M. Amin

IPC: H03M7/00

CPC classification number: H03M13/2906 ,  H03M13/1515 ,  H03M13/1575 ,  H03M13/3761 ,  H04L1/0042

Abstract: In a data decoder for decoding data from received symbols received over a channel from an encoder, wherein the received data can include erasures and include source symbols and repair symbols and wherein the decoder uses in decoding a generator matrix, any square submatrix of which is invertible, such that the decoder can perform decoding operations concurrently with the arrival of the source symbols and repair symbols, a method of decoding comprising representing in decoder memory a system of equations derived, at least in part, from the generator matrix, substituting received source symbols into the system of equations as the source symbols are received before receiving all source symbols, identifying, using decoder logic, repair equations to be used for solving the system of equations as repair symbols arrive, calculating, using decoder logic, vector values for equations as source symbols arrive, and converting the system of equations into an upper triangular form as repair symbols arrive at the decoder. Novel methods can be used for interleaving and specifying encoding structure for a large class of FEC codes, scheduling the sending of packets and the like.

Abstract translation: 在用于从通过编码器的信道上接收的接收到的符号中对数据进行解码的数据解码器中，其中所接收的数据可以包括擦除并且包括源符号和修复符号，并且其中解码器在对发生器矩阵进行解码时使用，任何正方形子矩阵是可逆的 ，使得解码器可以与源符号和修复符号的到达同时执行解码操作，解码方法包括在解码器存储器中表示至少部分地从发生器矩阵导出的等式的系统，代替接收的源符号 在接收所有源符号之前接收到源符号的系统，识别使用解码器逻辑，用于解决修复符号到达的方程组的修正方程，使用解码器逻辑来计算方程式的向量值 源符号到达，并将方程组转换为上三角形作为修复符号 到达解码器。 可以使用新的方法来交织和指定大类FEC码的编码结构，调度分组的发送等。

公开(公告)号：WO2005112250A3

公开(公告)日：2005-11-24

申请号：PCT/US2005/016334

申请日：2005-05-09

Applicant: DIGITAL FOUNTAIN, INC. ,  LUBY, Michael G. ,  SHOKROLLAHI, M. Amin ,  WATSON, Mark

Inventor： LUBY, Michael G. ,  SHOKROLLAHI, M. Amin ,  WATSON, Mark

IPC: H03M13/00 ,  H03M13/03

Abstract: A method of encoding data for transmission from a source to a destination over a communications channel (145) is provided. The method operates on an ordered set of input symbols (205) and includes generating a plurality of redundant symbols from the input symbols (205). The method also includes generating a plurality of output symbols from a combined set of symbols including the input symbols and the redundant symbols, wherein the number of possible output symbols is much larger than the number of symbols in the combined set of symbols, wherein at least one output symbol is generated from more than one symbol in the combined set of symbols and from less than all of the symbols in the combined set of symbols, and such that the ordered set of input symbols (205) can be regenerated to a desired degree of accuracy from any predetermined number of the output symbols.

公开(公告)号：WO2005036753A2

公开(公告)日：2005-04-21

申请号：PCT/US2004/033222

申请日：2004-10-06

Applicant: DIGITAL FOUNTAIN, INC. ,  SHOKROLLAHI, M. Amin

Inventor： SHOKROLLAHI, M. Amin

IPC: H03M

CPC classification number: H03M13/3761

Abstract: A communications system includes an encoder that produces a plurality of redundant symbols. For a given key, an output symbol is generated from a combined set of symbols including the input symbols and the redundant symbols. The output symbols are generally independent of each other, and an effectively unbounded number of output symbols (subject to the resolution of the key used) can be generated, if needed. The output symbols are information additive such that a received output symbol is likely to provide additional information for decoding even when many symbols are already received. The output symbols are such that a collection of received output symbols can provide probabilistic information to support error correction. A decoder calculates check symbols from the output symbols received, wherein each check symbol is associated with one or more input symbols and redundant symbols For each received output symbol, the decoder updates a running total of estimated information content and, in one or more rounds, generates a probability distribution for each input symbol over all or some of the possible values of input symbols. This process may be repeated until, for all of the input symbols, one of the many possible values is much more probable than others, or the process may be repeated a predetermined number of rounds, or other criteria is met. The updating can take into account already decoded symbols, additional output symbols and the check symbols.

Abstract translation: 通信系统包括产生多个冗余符号的编码器。 对于给定的密钥，从包括输入符号和冗余符号的组合组合生成输出符号。 输出符号通常彼此独立，并且如果需要，可以产生有效无限数量的输出符号（取决于所使用的密钥的分辨率）。 输出符号是信息加法，使得即使已经接收到许多符号，所接收的输出符号也可能提供用于解码的附加信息。 输出符号使得所接收的输出符号的集合可以提供概率信息以支持纠错。 解码器从接收到的输出符号计算检查符号，其中每个检查符号与一个或多个输入符号和冗余符号相关联对于每个接收的输出符号，解码器更新估计信息内容的运行总计，并且在一个或多个循环中， 在输入符号的全部或部分可能的值上生成每个输入符号的概率分布。 可以重复该过程，直到对于所有输入符号来说，许多可能值中的一个值比其他值更可能更多，或者可以重复该过程预定数量的循环，或满足其他标准。 更新可以考虑已经解码的符号，附加的输出符号和检查符号。

公开(公告)号：WO2007098397A3

公开(公告)日：2007-08-30

申请号：PCT/US2007/062302

申请日：2007-02-16

Applicant: DIGITAL FOUNTAIN, INC. ,  SHOKROLLAHI, M. Amin ,  LUBY, Michael, G. ,  WATSON, Mark ,  MINDER, Lorenz

Inventor： SHOKROLLAHI, M. Amin ,  LUBY, Michael, G. ,  WATSON, Mark ,  MINDER, Lorenz

IPC: H04B14/04

Abstract: A method of encoding data for transmission from a source to a destination over a communications channel is provided. The method operates on an ordered set of input symbols and includes generating a plurality of redundant symbols from the input symbols based on linear constraints. The method also includes generating a plurality of output symbols from a combined set of symbols including the input symbols and the redundant symbols based on linear combinations, wherein at least one of the linear constraints or combinations is over a first finite field and at least one other of the linear constraints or combinations is over a different second finite field, and such that the ordered set of input symbols can be regenerated to a desired degree of accuracy from any predetermined number of the output symbols.

公开(公告)号：WO2006135878A3

公开(公告)日：2006-12-21

申请号：PCT/US2006/022914

申请日：2006-06-12

Applicant: DIGITAL FOUNTAIN, INC. ,  LUBY, Michael, G. ,  SHOKROLLAHI, M. Amin

Inventor： LUBY, Michael, G. ,  SHOKROLLAHI, M. Amin

IPC: H04L27/00

Abstract: In an encoder for encoding symbols of data using a computing device having memory constraints, a method of performing a transformation comprising loading a source block into memory of the computing device, performing an intermediate transformation of less than all of the source block, then replacing a part of the source block with intermediate results in the memory and then completing the transformation such that output symbols stored in the memory form a set of encoded symbols. A decoder can perform decoding steps in an order that allows for use of substantially the same memory for storing the received data and the decoded source block, performing as in-place transformations. Using an in-place transformation, a large portion of memory set aside for received data can be overwritten as that received data is transformed into decoded source data without requiring a similar sized large portion of memory for the decoded source data.

公开(公告)号：WO2003105350A1

公开(公告)日：2003-12-18

申请号：PCT/US2003/018353

申请日：2003-06-10

Applicant: DIGITAL FOUNTAIN, INC. ,  SHOKROLLAHI, M. Amin ,  LASSEN, Soren ,  KARP, Richard

Inventor： SHOKROLLAHI, M. Amin ,  LASSEN, Soren ,  KARP, Richard

IPC: H03M13/00

CPC classification number: H03M13/3761 ,  H03M13/1102 ,  H03M13/1191 ,  H03M13/19 ,  H03M13/47

Abstract: A method for processing a chain reaction codes includes first selecting a source symbol which is associated an output symbol of degree two or higher (i.e., an output symbol which is itself associated with two or more input symbols), recovering the value of this symbol for example by solving a system of linear equations, and subsequently deactivating the selected source symbol in an attempt to produce an output symbol of degree one. The inactivation process can be repeated either successively until an output symbol of degree one is identified, and/or whenever the decoding process is unable to locate an output symbol of degree one.

Abstract translation: 一种用于处理链式反应代码的方法包括：首先选择与二度以上的输出符号相关联的源符号（即，本身与两个或多个输入符号相关联的输出符号），将该符号的值恢复 例如，通过求解线性方程组的系统，随后去激活所选择的源符号以试图产生一级的输出符号。 可以连续地重复灭活过程，直到识别出一级的输出符号，和/或每当解码过程不能定位一度的输出符号时。