公开(公告)号：US07956772B2

公开(公告)日：2011-06-07

申请号：US12604773

申请日：2009-10-23

Applicant: Mohammad Amin Shokrollahi ,  Michael Luby

Inventor： Mohammad Amin Shokrollahi ,  Michael Luby

IPC: H03M7/34

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

Abstract: A method of encoding data for transmission from a source to a destination over a communications channel is provided. A plurality of encoded symbols are generated from a set of input symbols including source symbols and redundant symbols, wherein the input symbols are organized such that at least one of the input symbols is not used for a first encoding process, so that it is permanently inactivated for the purposes of scheduling a decoding process. A method of decoding data is also provided, wherein encoded symbols generated from a set of input symbols are used to recover source symbols, wherein the input symbols are organized such that at least one of the input symbols is not used for a first decoding process, so that it is permanently inactivated for the purpose of scheduling the decoding process.

Abstract translation: 提供了一种用于通过通信信道从源传送到目的地的数据编码方法。 从包括源符号和冗余符号的一组输入符号生成多个编码符号，其中输入符号被组织为使得输入符号中的至少一个不用于第一编码处理，使得其被永久禁用 为了调度解码过程。 还提供了一种解码数据的方法，其中使用从一组输入符号生成的编码符号来恢复源符号，其中输入符号被组织成使得至少一个输入符号不用于第一解码处理， 因此为了调度解码过程的目的而使其永久失活。

公开(公告)号：US20100103001A1

公开(公告)日：2010-04-29

申请号：US12604773

申请日：2009-10-23

Applicant: Mohammad Amin Shokrollahi ,  Michael Luby

Inventor： Mohammad Amin Shokrollahi ,  Michael Luby

IPC: H03M13/00 ,  H03M13/05 ,  G06F11/10

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

Abstract: A method of encoding data for transmission from a source to a destination over a communications channel is provided. A plurality of encoded symbols are generated from a set of input symbols including source symbols and redundant symbols, wherein the input symbols are organized such that at least one of the input symbols is not used for a first encoding process, so that it is permanently inactivated for the purposes of scheduling a decoding process. A method of decoding data is also provided, wherein encoded symbols generated from a set of input symbols are used to recover source symbols, wherein the input symbols are organized such that at least one of the input symbols is not used for a first decoding process, so that it is permanently inactivated for the purpose of scheduling the decoding process.

Abstract translation: 提供了一种用于通过通信信道从源传送到目的地的数据编码方法。 从包括源符号和冗余符号的一组输入符号生成多个编码符号，其中输入符号被组织为使得输入符号中的至少一个不用于第一编码处理，使得其被永久禁用 为了调度解码过程。 还提供了一种解码数据的方法，其中使用从一组输入符号生成的编码符号来恢复源符号，其中输入符号被组织成使得至少一个输入符号不用于第一解码处理， 因此为了调度解码过程的目的而使其永久失活。

公开(公告)号：US07660245B1

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

申请号：US11229009

申请日：2005-09-16

Applicant: Michael Luby

Inventor： Michael Luby

IPC: H04J1/16

CPC classification number: H04L1/0041 ,  H04L1/0075 ,  H04L1/0083

Abstract: In a packet communications system stream data is transported over a channel over which packet loss or corruption is possible, with forward error correction (“FEC”) information. A transmitter receives source packets comprising source data, generates FEC source packets formatted to allow for identification of lost or corrupted source packets at a receiver, arranges source data from the source packets into a plurality of source symbols wherein at least one source packet is arranged into more than one source symbol, associates a plurality of source symbols with a source block, generates a plurality of repair symbols from the source block according to a predetermined FEC encoding process and groups the plurality of repair symbols into one or more FEC repair packets associated with the source block. A receiver can use the FEC repair symbols from the FEC repair packets to recover source symbols, as needed.

Abstract translation: 在分组通信系统中，数据通过前向纠错（“FEC”）信息在可能的分组丢失或损坏的信道上传送。 发射机接收包括源数据的源分组，生成格式化为允许在接收机处识别丢失或损坏的源分组的FEC源分组，将来自源分组的源数据排列成多个源符号，其中至少一个源分组被布置成 多个源符号将多个源符号与源块相关联，根据预定的FEC编码处理从源块生成多个修复符号，并将多个修复符号分组成与...相关联的一个或多个FEC修复包 源块。 接收机可以根据需要使用来自FEC修复分组的FEC修复符号来恢复源符号。

公开(公告)号：US20080309525A1

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

申请号：US11842047

申请日：2007-08-20

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

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

IPC: 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.

Abstract translation: 提供了一种用于通过通信信道从源传送到目的地的数据编码方法。 从要发送的有序输入符号组生成多个冗余符号。 从包括输入符号和冗余符号的组合组合生成多个输出符号，其中可能的输出符号的数目远大于组合符号集合中的符号数量，其中至少一个输出符号 是从组合的符号集合中的多于一个符号生成的，并且从组合的符号集合中的小于所有符号生成，并且使得有序输入符号集可以从任何预定数量再生到期望的准确度 ，N，输出符号。

公开(公告)号：US20050242974A1

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

申请号：US11104391

申请日：2005-04-11

Applicant: M. Shokrollahi ,  Michael Luby

Inventor： M. Shokrollahi ,  Michael Luby

IPC: H03M13/11 ,  H04L1/00 ,  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）一个或多个非系统输出符号。

公开(公告)号：US08185809B2

公开(公告)日：2012-05-22

申请号：US11679170

申请日：2007-02-26

Applicant: Michael Luby ,  Ronen Vainish ,  Lars Rasmussen ,  David Kushi ,  Serban Simu ,  Adrian Perrig ,  Roberto Attias ,  Michael Walfish ,  Diane Hernek ,  John Byers

Inventor： Michael Luby ,  Ronen Vainish ,  Lars Rasmussen ,  David Kushi ,  Serban Simu ,  Adrian Perrig ,  Roberto Attias ,  Michael Walfish ,  Diane Hernek ,  John Byers

IPC: H03M13/03

CPC classification number: H04L69/14

Abstract: A method of serving content to multiple clients via a network is provided. Independent sessions with each of a plurality of clients are maintained, wherein the number of clients in the plurality of clients can vary over time, and wherein the start of each session and the end of each session can be independent of the start and end of other sessions. A stream of packet payloads is received, each packet payload of the stream of packet payloads including data generated from the content, wherein each packet payload in at least a subset of the stream of packet payloads includes a different set of data. Each packet payload in the stream of packet payloads is transmitted to each client of the plurality of clients in corresponding packets, wherein the packet payload transmitted to a client at any particular time is independent of the state of the corresponding session.

Abstract translation: 提供了通过网络向多个客户端提供内容的方法。 维护与多个客户端中的每一个的独立会话，其中多个客户端中的客户端的数量可以随时间变化，并且其中每个会话的开始和每个会话的结束可以独立于其他的开始和结束 会话 接收到分组有效载荷流，分组有效载荷流的每个分组有效载荷包括从内容生成的数据，其中分组有效载荷流的至少一个子集中的每个分组有效载荷包括不同的数据集合。 分组有效载荷流中的每个分组有效载荷被发送到相应分组中的多个客户端中的每个客户端，其中在任何特定时间发送到客户端的分组有效载荷与相应会话的状态无关。

公开(公告)号：US07447235B2

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

申请号：US10962373

申请日：2004-10-08

Applicant: Michael Luby ,  Matt Doucleff ,  Avi Wigderson ,  Soren Lassen

Inventor： Michael Luby ,  Matt Doucleff ,  Avi Wigderson ,  Soren Lassen

IPC: H04L1/12

CPC classification number: H04L1/1819 ,  H03M13/3761 ,  H03M13/6547 ,  H04L1/1887 ,  H04L69/16 ,  H04L69/163

Abstract: 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.

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

公开(公告)号：US20060280254A1

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

申请号：US11423376

申请日：2006-06-09

Applicant: Michael Luby ,  M. Shokrollahi

Inventor： Michael Luby ,  M. Shokrollahi

IPC: H04L27/00

CPC classification number: 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

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.

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

公开(公告)号：US20060262877A1

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

申请号：US11354256

申请日：2006-02-13

Applicant: M. Shokrollahi ,  Soren Lassen ,  Michael Luby

Inventor： M. Shokrollahi ,  Soren Lassen ,  Michael Luby

IPC: H04L27/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.

公开(公告)号：US08279755B2

公开(公告)日：2012-10-02

申请号：US12606421

申请日：2009-10-27

Applicant: Michael Luby

Inventor： Michael Luby

IPC: H04J1/16

CPC classification number: H04L1/0041 ,  H04L1/0075 ,  H04L1/0083

Abstract: In a packet communications system stream data is transported over a channel over which packet loss or corruption is possible, with forward error correction (“FEC”) information. A transmitter receives source packets comprising source data, generates FEC source packets formatted to allow for identification of lost or corrupted source packets at a receiver, arranges source data from the source packets into a plurality of source symbols wherein at least one source packet is arranged into more than one source symbol, associates a plurality of source symbols with a source block, generates a plurality of repair symbols from the source block according to a predetermined FEC encoding process and groups the plurality of repair symbols into one or more FEC repair packets associated with the source block. A receiver can use the FEC repair symbols from the FEC repair packets to recover source symbols, as needed.

Abstract translation: 在分组通信系统中，数据通过前向纠错（FEC）信息在可能的分组丢失或损坏的信道上传送。 发射机接收包括源数据的源分组，生成格式化为允许在接收机处识别丢失或损坏的源分组的FEC源分组，将来自源分组的源数据排列成多个源符号，其中至少一个源分组被布置成 多个源符号将多个源符号与源块相关联，根据预定的FEC编码处理从源块生成多个修复符号，并将多个修复符号分组成与...相关联的一个或多个FEC修复包 源块。 接收机可以根据需要使用来自FEC修复分组的FEC修复符号来恢复源符号。