公开(公告)号：US20110103519A1

公开(公告)日：2011-05-05

申请号：US12549560

申请日：2009-08-28

Applicant: M. Amin Shokrollahi ,  Soren Lassen ,  Richard Karp

Inventor： M. Amin Shokrollahi ,  Soren Lassen ,  Richard Karp

IPC: H04L27/06

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

Abstract: A method for processing a chain reaction code includes first selecting a source symbol which is associated with an output symbol of degree two or higher (i.e., an output symbol which is itself associated with two or more input symbols), 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: 用于处理链式反应代码的方法包括首先选择与二度以上的输出符号相关联的源符号（即，本身与两个或多个输入符号相关联的输出符号），并且随后停用所选择的源 试图产生一级输出符号的符号。 可以连续地重复灭活过程，直到识别出一级的输出符号，和/或每当解码过程不能定位一度的输出符号时。

公开(公告)号：US07721184B2

公开(公告)日：2010-05-18

申请号：US11202933

申请日：2005-08-11

Applicant: Michael Luby ,  M. Amin Shokrollahi

Inventor： Michael Luby ,  M. Amin Shokrollahi

IPC: H03M13/00

CPC classification number: H03M13/3761 ,  H03M13/03 ,  H03M13/1102 ,  H03M13/19 ,  H03M13/29 ,  H03M13/373 ,  H03M13/3776 ,  H03M13/51

Abstract: Efficient methods for encoding and decoding Half-Weight codes are disclosed and similar high density codes are disclosed. The efficient methods require at most 3·(k−1)+h/2+1 XORs of symbols to calculate h Half-Weight symbols from k source symbols, where h is of the order of log(k).

Abstract translation: 有效的编码和解码方法公开半重码，并公开类似的高密度码。 有效的方法需要至多3（k-1）+ h / 2 + 1个符号XOR来计算h个k个符号的半重符号，其中h是log（k）的数量级。

公开(公告)号：US07720174B2

公开(公告)日：2010-05-18

申请号：US11354256

申请日：2006-02-13

Applicant: M. Amin Shokrollahi ,  Soren Lassen ,  Michael Luby

Inventor： M. Amin Shokrollahi ,  Soren Lassen ,  Michael Luby

IPC: H04K1/02 ,  H03M13/00

CPC classification number: H04L1/0041 ,  H03M13/1102 ,  H03M13/19 ,  H03M13/3761 ,  H04L2001/0093

Abstract: A method of encoding data for transmission from a source to a destination over a communications channel is provided. A plurality of redundant symbols are generated from an ordered set of input symbols to be transmitted. A plurality of output symbols are generated 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 can be regenerated to a desired degree of accuracy from any predetermined number, N, of the output symbols.

公开(公告)号：US07676735B2

公开(公告)日：2010-03-09

申请号：US11423391

申请日：2006-06-09

Applicant: Michael G. Luby ,  Mark Watson ,  M. Amin Shokrollahi

Inventor： Michael G. Luby ,  Mark Watson ,  M. Amin Shokrollahi

IPC: H03M13/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, a method for decoding data wherein the received data includes erasures and includes source symbols and repair symbols organized into one or more source blocks. The decoder uses a generator matrix, any square submatrix of which is invertible, such that the decoder performs decoding operations concurrently with the arrival of the source symbols and repair symbols that are a part of a source block. Novel methods for interleaving and specifying encoding structure for a large class of FEC codes, scheduling the sending of packets and the like, are also applied in conjunction with the method for decoding data.

Abstract translation: 在用于对来自编码器的信道上接收到的接收符号的数据进行解码的数据解码器中，一种用于解码数据的方法，其中所接收的数据包括擦除，并且包括被组织成一个或多个源块的源符号和修复符号。 解码器使用发生器矩阵，其任何平方子矩阵是可逆的，使得解码器与作为源块的一部分的源符号和修复符号的到达同时执行解码操作。 结合用于解码数据的方法，还应用了用于大量FEC码的交织和编码结构的新方法，调度分组的发送等。

公开(公告)号：US07633413B2

公开(公告)日：2009-12-15

申请号：US11842102

申请日：2007-08-20

Applicant: M. Amin Shokrollahi ,  Soren Lassen ,  Richard Karp

Inventor： M. Amin Shokrollahi ,  Soren Lassen ,  Richard Karp

IPC: H03M5/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), 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: 一种用于处理链式反应代码的方法包括：首先选择与二度以上的输出符号相关联的源符号（即，本身与两个或多个输入符号相关联的输出符号），并且随后停用所选择的源符号 试图产生一度的输出符号。 可以连续地重复灭活过程，直到识别出一级的输出符号，和/或每当解码过程不能定位一度的输出符号时。

公开(公告)号：US07451377B2

公开(公告)日：2008-11-11

申请号：US11538906

申请日：2006-10-05

Applicant: M. Amin Shokrollahi

Inventor： M. Amin Shokrollahi

IPC: H03M13/00

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 can be generated, if needed. Received output symbols can provide probabilistic information for error correction. A decoder calculates check symbols from the output symbols received. 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 possible values. 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.

Abstract translation: 通信系统包括产生多个冗余符号的编码器。 对于给定的密钥，从包括输入符号和冗余符号的组合组合生成输出符号。 输出符号通常彼此独立，如果需要，可以产生有效无限数量的输出符号。 接收的输出符号可以提供用于纠错的概率信息。 解码器从接收的输出符号计算检验符号。 对于每个接收到的输出符号，解码器更新估计信息内容的运行总计，并且在一个或多个循环中，针对所有或一些可能的值生成每个输入符号的概率分布。 可以重复该过程，直到对于所有输入符号来说，许多可能值中的一个值比其他值更可能更多，或者可以重复该过程预定数量的循环，或满足其他标准。

公开(公告)号：US20080180285A1

公开(公告)日：2008-07-31

申请号：US11894670

申请日：2007-08-20

Applicant: M. Amin Shokrollahi ,  Michael G. Luby

Inventor： M. Amin Shokrollahi ,  Michael G. Luby

IPC: H04L1/00

CPC classification number: H03M13/1102 ,  H03M7/30 ,  H03M13/3761 ,  H04L1/00

Abstract: A method of encoding data into a chain reaction code includes generating a set of input symbols from input data. Subsequently, one or more non-systematic output symbols is generated from the set of input symbols, each of the one or more non-systematic output symbols being selected from an alphabet of non-systematic output symbols, and each non-systematic output symbol generated as a function of one or more of the input symbols. As a result of this encoding process, any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered, and (b) one or more of the non-systematic output symbols.

公开(公告)号：US07394407B2

公开(公告)日：2008-07-01

申请号：US11104391

申请日：2005-04-11

Applicant: M. Amin Shokrollahi ,  Michael G. Luby

Inventor： M. Amin Shokrollahi ,  Michael G. Luby

IPC: H03M7/00

CPC classification number: H03M13/1102 ,  H03M7/30 ,  H03M13/3761 ,  H04L1/00

Abstract: A method of encoding data into a chain reaction code includes generating a set of input symbols from input data. Subsequently, one or more non-systematic output symbols is generated from the set of input symbols, each of the one or more non-systematic output symbols being selected from an alphabet of non-systematic output symbols, and each non-systematic output symbol generated as a function of one or more of the input symbols. As a result of this encoding process, any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered, and (b) one or more of the non-systematic output symbols.

Abstract translation: 将数据编码为链式反应代码的方法包括从输入数据生成一组输入符号。 随后，从该组输入符号生成一个或多个非系统输出符号，一个或多个非系统输出符号中的每一个从非系统输出符号的字母表中选择，并且生成每个非系统输出符号 作为一个或多个输入符号的函数。 作为该编码处理的结果，可从（i）预定数量的非系统输出符号中恢复该组输入符号的任何子集，或（ii）不包括在该系统输出符号中的（a）输入符号的组合 要恢复的输入符号的子集，以及（b）一个或多个非系统输出符号。

公开(公告)号：US07293222B2

公开(公告)日：2007-11-06

申请号：US10769732

申请日：2004-01-29

Applicant: M. Amin Shokrollahi ,  Soren Lassen

Inventor： M. Amin Shokrollahi ,  Soren Lassen

IPC: H03M13/11

CPC classification number: H03M13/6502 ,  H03M13/1102 ,  H03M13/19 ,  H03M13/3761

Abstract: Decoding that uses an extended Hamming code in one of the primary stages of static encoding uses a calculation of the r+1 Hamming redundant symbols for k input symbols from which Hamming redundant symbols are calculated, where r satisfies 2r−1−r≦k

Abstract translation: 在静态编码的主要阶段之一中使用扩展汉明码的解码使用计算汉明冗余符号的k个输入符号的r + 1汉明冗余符号的计算，其中r满足2≤r-1 < / SUP> -r <= K <2 -r-1。 这种有效的方法要求输入符号的2k + 3r + 1个异或，以计算r + 1汉明冗余符号。

公开(公告)号：US07030785B2

公开(公告)日：2006-04-18

申请号：US11031331

申请日：2005-01-07

Applicant: M. Amin Shokrollahi ,  Soren Lassen ,  Richard Karp

Inventor： M. Amin Shokrollahi ,  Soren Lassen ,  Richard Karp

IPC: H03M7/00 ,  H03M13/00 ,  H04L1/18

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), 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.