公开(公告)号：US20060279437A1

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

申请号：US11423391

申请日：2006-06-09

申请人： Michael Luby ,  Mark Watson ,  M. Shokrollahi

发明人： Michael Luby ,  Mark Watson ,  M. Shokrollahi

IPC分类号： H03M7/00

CPC分类号： H03M13/2906 ,  H03M13/1515 ,  H03M13/1575 ,  H03M13/3761 ,  H04L1/0042

摘要： 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.

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

公开(公告)号：US20050242974A1

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

申请号：US11104391

申请日：2005-04-11

申请人： M. Shokrollahi ,  Michael Luby

发明人： M. Shokrollahi ,  Michael Luby

IPC分类号： H03M13/11 ,  H04L1/00 ,  H03M7/00

CPC分类号： H03M13/1102 ,  H03M7/30 ,  H03M13/3761 ,  H04L1/00

摘要： 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.

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

公开(公告)号：US20060036930A1

公开(公告)日：2006-02-16

申请号：US11202933

申请日：2005-08-11

申请人： Michael Luby ,  M. Shokrollahi

发明人： Michael Luby ,  M. Shokrollahi

IPC分类号： H03M13/03

CPC分类号： H03M13/3761 ,  H03M13/03 ,  H03M13/1102 ,  H03M13/19 ,  H03M13/29 ,  H03M13/373 ,  H03M13/3776 ,  H03M13/51

摘要： 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).

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

公开(公告)号：US20050257106A1

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

申请号：US11125818

申请日：2005-05-09

申请人： Michael Luby ,  M. Shokrollahi ,  Mark Watson

发明人： Michael Luby ,  M. Shokrollahi ,  Mark Watson

IPC分类号： G11C29/00 ,  H03D1/00 ,  H03M13/29 ,  H03M13/37 ,  H04L1/00 ,  H04L27/06

CPC分类号： H03M13/29 ,  H03M13/1102 ,  H03M13/19 ,  H03M13/3761 ,  H04L1/0041 ,  H04L1/0045 ,  H04L1/0057 ,  H04L1/0065

摘要： 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. 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 can be regenerated to a desired degree of accuracy from any predetermined number of the output symbols. The plurality of redundant symbols is generated from an ordered set of input symbols to be transmitted in a deterministic process such that a first set of static symbols calculated using a first input symbol has a low common membership with a second set of static symbols calculated using a second input symbol distinct from the first input symbol.

摘要翻译： 提供了一种用于通过通信信道从源传送到目的地的数据编码方法。 该方法对有序输入符号组进行操作，并且包括从输入符号生成多个冗余符号。 该方法还包括从包括输入符号和冗余符号的组合组合生成多个输出符号，其中可能的输出符号的数量远大于组合符号集合中的符号数，其中至少 一个输出符号是从组合符号集合中的多于一个符号和小于组合符号集合中的所有符号生成的，并且使得有序输入符号集可以从 任何预定数量的输出符号。 多个冗余符号从要在确定性过程中发送的有序输入符号集合生成，使得使用第一输入符号计算的第一组静态符号具有与使用第一输入符号计算的第二组静态符号的较低公共隶属关系 第二输入符号与第一输入符号不同。

公开(公告)号：US20060280254A1

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

申请号：US11423376

申请日：2006-06-09

申请人： Michael Luby ,  M. Shokrollahi

发明人： Michael Luby ,  M. Shokrollahi

IPC分类号： H04L27/00

CPC分类号： H03M13/3761 ,  G06F17/16 ,  H03M13/05 ,  H03M13/1197 ,  H03M13/1515 ,  H03M13/2785 ,  H03M13/37 ,  H03M13/373 ,  H03M13/47 ,  H03M13/611 ,  H03M13/616 ,  H03M13/6505 ,  H03M13/6569 ,  H04L1/0041 ,  H04L1/0045 ,  H04L1/0057

摘要： 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.

摘要翻译： 在使用具有存储器限制的计算装置对数据符号进行编码的编码器中，执行变换的方法包括将源块加载到计算装置的存储器中，执行小于所有源块的中间变换， 具有中间的源块的一部分在存储器中产生，然后完成变换，使得存储在存储器中的输出符号形成一组编码符号。 解码器可以以允许使用基本上相同的存储器来存储接收的数据和解码的源块的顺序执行解码步骤，作为就地转换执行。 使用就地变换，可以覆盖用于接收数据的大部分存储器，因为接收的数据被转换为解码的源数据，而不需要用于解码的源数据的相似大小的大部分存储器。

公开(公告)号：US20060262877A1

公开(公告)日：2006-11-23

申请号：US11354256

申请日：2006-02-13

申请人： M. Shokrollahi ,  Soren Lassen ,  Michael Luby

发明人： M. Shokrollahi ,  Soren Lassen ,  Michael Luby

IPC分类号： H04L27/00

CPC分类号： H04L1/0041 ,  H03M13/1102 ,  H03M13/19 ,  H03M13/3761 ,  H04L2001/0093

摘要： 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.

公开(公告)号：US08458567B2

公开(公告)日：2013-06-04

申请号：US12263098

申请日：2008-10-31

申请人： Michael Luby ,  Matt Doucleff ,  Avi Wigderson ,  Soren Lassen

发明人： Michael Luby ,  Matt Doucleff ,  Avi Wigderson ,  Soren Lassen

IPC分类号： H03M13/00

CPC分类号： H04L1/1819 ,  H03M13/3761 ,  H03M13/6547 ,  H04L1/1887 ,  H04L69/16 ,  H04L69/163

摘要： In a transport system, data is reliably transported from a sender to a receiver by organizing the data to be transported into data blocks, wherein each data block comprises a plurality of encoding units, transmitting encoding units of a first data block from the sender to the receiver, and detecting, at the sender, acknowledgments of receipt of encoding units by the receiver. At the sender, a probability that the receiver received sufficient encoding units of the first data block to recover the first data block at the receiver is detected and the probability is tested against a threshold probability to determine whether a predetermined test is met. Following the step of testing and prior to the sender receiving confirmation of recovery of the first data block at the receiver, when the predetermined test is met, transmitting encoding units of a second data block from the sender. If an indication of failure to recover the first data block is received at the sender, sending further encoding units for the first data block from the sender to the receiver. In some embodiments, the predetermined test is a comparison of the probability against the threshold probability and the predetermined test is met when the probability is greater than the threshold probability.

摘要翻译： 在传送系统中，通过将要传送的数据组织成数据块，数据可靠地从发送方传送到接收方，其中每个数据块包括多个编码单元，将第一数据块的编码单元从发送器发送到 并且在发送器处检测由接收器接收编码单元的确认。 在发送器处，检测到接收器接收到第一数据块的足够的编码单元以恢复接收器处的第一数据块的概率，并且针对阈值概率测试概率以确定是否满足预定的测试。 在测试步骤之后，并且在发送方接收到在接收机处恢复第一数据块的确认之前，当满足预定测试时，从发送方发送第二数据块的编码单元。 如果在发送方收到恢复第一数据块的指示，则从发送方向接收方发送第一数据块的另外的编码单元。 在一些实施例中，预定测试是当概率大于阈值概率时，对阈值概率的概率和满足预定测试的概率的比较。

公开(公告)号：US07721184B2

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

申请号：US11202933

申请日：2005-08-11

申请人： Michael Luby ,  M. Amin Shokrollahi

发明人： Michael Luby ,  M. Amin Shokrollahi

IPC分类号： H03M13/00

CPC分类号： H03M13/3761 ,  H03M13/03 ,  H03M13/1102 ,  H03M13/19 ,  H03M13/29 ,  H03M13/373 ,  H03M13/3776 ,  H03M13/51

摘要： 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).

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

公开(公告)号：US07720174B2

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

申请号：US11354256

申请日：2006-02-13

申请人： M. Amin Shokrollahi ,  Soren Lassen ,  Michael Luby

发明人： M. Amin Shokrollahi ,  Soren Lassen ,  Michael Luby

IPC分类号： H04K1/02 ,  H03M13/00

CPC分类号： H04L1/0041 ,  H03M13/1102 ,  H03M13/19 ,  H03M13/3761 ,  H04L2001/0093

摘要： 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.

公开(公告)号：US20070189401A1

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

申请号：US11674628

申请日：2007-02-13

申请人： Mark Watson ,  Michael Luby

发明人： Mark Watson ,  Michael Luby

IPC分类号： H04L27/00

CPC分类号： H04L1/0041 ,  H03M13/373 ,  H03M13/3761 ,  H04B1/66 ,  H04L1/0057 ,  H04L1/0078 ,  H04N19/89

摘要： Transmitters and receivers deal with streams of data, wherein the receiver is expected to begin using received data before receiving all of the data. Concurrent streams are sent and FEC coding is used with the streams and done as an aggregate. The transmitter performs FEC operations over the plurality of streams, wherein source blocks from at least two streams logically associated into a jumbo source block and FEC processing is performed to generate one or more jumbo repair block from the jumbo source block. Each of the source blocks comprises one or more source symbols from their respective stream. The jumbo source symbols can be of constant size and are suitably aligned along size boundaries that make processing efficient. Each source symbol need not be the same size, and the number of source symbols from each stream in a jumbo source block need not be the same value across streams.

摘要翻译： 发射机和接收机处理数据流，其中接收机预期在接收所有数据之前开始使用接收的数据。 并发流被发送，FEC编码与流一起使用，并作为聚合完成。 发射机对多个流执行FEC操作，其中执行逻辑上关联到巨型源块和FEC处理中的至少两个流的源块，以从巨型源块生成一个或多个巨型维修块。 每个源块包括来自它们各自的流的一个或多个源符号。 巨型源符号可以具有恒定的大小，并且可以沿着使处理有效的大小边界适当地对齐。 每个源符号不需要相同的大小，并且来自巨型源块中的每个流的源符号的数量不必在每个流之间具有相同的值。