[미국특허]
Multi-stage code generator and decoder for communication systems
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
H04K-001/02
H03M-013/00
출원번호
UP-0354256
(2006-02-13)
등록번호
US-7720174
(2010-06-10)
발명자
/ 주소
Shokrollahi, M. Amin
Lassen, Soren
Luby, Michael
출원인 / 주소
Digital Fountain, Inc.
대리인 / 주소
Jacobs, Jeffrey D.
인용정보
피인용 횟수 :
50인용 특허 :
38
초록▼
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 inclu
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.
대표청구항▼
What is claimed is: 1. A method of employing two or more stages of encoding to encode data for transmission from a transmitter to at least one receiver over a communication channel, the method comprising: generating, during a first encoding stage, a plurality of redundant symbols from an ordered se
What is claimed is: 1. A method of employing two or more stages of encoding to encode data for transmission from a transmitter to at least one receiver over a communication channel, the method comprising: generating, during a first encoding stage, a plurality of redundant symbols from an ordered set of input symbols representing the data to be encoded for transmission; generating, during a second encoding stage, a set of output symbols derived from a combination of the plurality of redundant symbols and the ordered set of input symbols, wherein the number of possible output symbols that could be generated is independent of the number of input symbols in the ordered set of input symbols; and transmitting at least some of the set of output symbols over the communications channel to at least one receiver such that the ordered set of input symbols can be regenerated to a desired degree of accuracy from a predetermined number of output symbols received by the at least one receiver. 2. The method of claim 1, wherein the set of output symbols are generated such that an order of transmission of the output symbols can be independent of the output symbols previously received by the at least one receiver. 3. The method of claim 1, wherein generating comprises storing the plurality of redundant symbols on a storage media independent of the transmitting of the output symbols. 4. The method of claim 3, wherein generating the set of output symbols comprises retrieving the stored plurality of redundant symbols from the storage media substantially concurrently with transmission of the output symbols. 5. The method of claim 1, wherein generating a plurality of redundant symbols is done using a static encoder. 6. The method of claim 5, wherein the static encoder generates the plurality of redundant symbols using one or more of Reed-Solomon encoding, Tornado encoding, Hamming encoding, or Low Density Parity Check encoding. 7. The method of claim 1, wherein generating the set of output symbols is done using a dynamic encoder. 8. A method of employing two or more stages of encoding to encode data for transmission from a transmitter to at least one receiver over a communication channel, the method comprising: generating, during a first encoding stage, a plurality of redundant symbols from an ordered set of input symbols representing the data to be encoded for transmission; generating, during a second encoding stage, a set of output symbols derived from a combination of the plurality of redundant symbols and the ordered set of input symbols, wherein the number of possible output symbols that could be used in the set of output symbols is independent of the number of input symbols in the ordered set of input symbols; and transmitting at least some of the set of output symbols over the communications channel to at least one receiver such that the ordered set of input symbols can be regenerated to a desired degree of accuracy from a predetermined number of output symbols received by the at least one receiver, wherein generating the set of output symbols is done using a dynamic encoder, wherein the dynamic encoder generates the set of output symbols using chain-reaction encoding. 9. The method of claim 1, wherein the at least one receiver is a storage medium. 10. The method of claim 1, wherein the communication channel is a combination of a real-time channel and a storage channel. 11. The method of claim 1, wherein generating the plurality of redundant symbols comprises computing a number, R, of the redundant symbols from a number, K, of input symbols, wherein R and K are known in advance and K/(R+K) is a code rate of a static code used in the generating. 12. A method of employing two or more stages of encoding to encode data for transmission from a transmitter to at least one receiver over a communication channel, the method comprising: generating, during a first encoding stage, a plurality of redundant symbols from an ordered set of input symbols representing the data to be encoded for transmission; generating, during a second encoding stage, a set of output symbols derived from a combination of the plurality of redundant symbols and the ordered set of input symbols, wherein the number of possible output symbols that could be used in the set of output symbols is independent of the number of input symbols in the ordered set of input symbols; and transmitting at least some of the set of output symbols over the communications channel to at least one receiver such that the ordered set of input symbols can be regenerated to a desired degree of accuracy from a predetermined number of output symbols received by the at least one receiver, wherein generating the set of output symbols comprises employing a dynamic encoder to generate the set of output symbols using the set of redundant symbols generated from the input symbols, the ordered set of input symbols, and a plurality of dynamic keys. 13. A method of decoding output symbols transmitted over a communications channel, the method comprising: receiving a plurality of encoded output symbols and corresponding keys from the communications channel, wherein the encoded output symbols can be received in an order independent of the order of encoded output symbols previously received; decoding at least some of the encoded output symbols using a dynamic decoder and the corresponding keys to recover a first set of input symbols and at least some redundant symbols used in the creation of a first subset of the encoded output symbols; and decoding at least some of the encoded output symbols using a static decoder to recover a second set of input symbols used in the creation of a second subset of the encoded output symbols that were not decoded by the dynamic decoder. 14. The method of claim 13, wherein the encoded output symbols are generated from an ordered set of input symbols and wherein the number of the ordered set of input symbols used to generate the encoded output symbols is independent of the number of possible encoded output symbols. 15. The method of claim 13, wherein at least a portion of the decoding at least some of the encoded output symbols using the dynamic decoder and the decoding at least some of the encoded output symbols using the static decoder are performed in an interleaved manner. 16. The method of claim 13, wherein at least a portion of the encoded output symbols are stored in a storage medium. 17. The method of claim 13, wherein the number of encoded output symbols decoded is dependent on a desired degree of accuracy to which the static decoder and dynamic decoder can recover input symbols that were used to generate the encoded output symbols. 18. The method of claim 13, wherein the number of encoded output symbols decoded is dependent on a desired degree of accuracy to which the static decoder or dynamic decoder can recover input symbols used to generate the encoded output symbols. 19. The method of claim 13, wherein decoding at least some of the encoded output symbols using the dynamic decoder comprises labeling the encoded output symbols having a weight of one as being part of a decodable set of the encoded output symbols. 20. The method of claim 19, further comprising reducing the set of encoded output symbols having a weight of two or more by decoding the decodable set of encoded output symbols. 21. The method of claim 19, wherein decoding at least some of the encoded output symbols using the dynamic decoder comprises decoding the encoded output symbols using chain reaction decoding. 22. The method of claim 13, wherein receiving the plurality of encoded output symbols and corresponding keys comprises receiving the plurality of encoded output symbols and inferring the corresponding keys from the receiving process. 23. The method of claim 21, wherein inferring the corresponding keys from the receiving process comprises inferring an output symbol's corresponding key from a output symbol index of the output symbol. 24. The method of claim 21, wherein inferring the corresponding keys from the receiving process comprises inferring an output symbol's corresponding key based on the time at which the output symbol was received. 25. A system for transmitting encoded data over a communications channel, the system comprising: a processor; a computer readable storage medium coupled to the processor, wherein the computer readable storage medium comprises: a) program code for generating a set of redundant symbols from an ordered set of input symbols; and b) program code for generating a plurality of encoded output symbols and corresponding keys, wherein the encoded output symbols are generated from a combination of the redundant symbols and the ordered set of input symbols, and wherein the number of possible encoded output symbols is independent of the number of input symbols employed to generate the encoded output symbols; and a transmitter configured to transmit the encoded output symbols over a communication channel to one or more receivers. 26. The system of claim 25, wherein the encoded output symbols are encoded such that the order of transmission of the encoded output symbols is independent of the encoded output symbols previously received by the one or more receivers. 27. The system of claim 25, wherein the system is further configured such that the transmitter transmits explicit keys for transmitted encoded output symbols. 28. The system of claim 25, wherein the redundant symbols are stored prior to transmitting the encoded output symbols. 29. The system of claim 25, further comprising program code for transmitting the encoded output symbols to a storage channel. 30. The system of claim 25, further comprising program code for storing the encoded output symbols. 31. The method of claim 1, wherein generating the set of output symbols is done using a dynamic encoder. 32. The method of claim 7, wherein the dynamic encoder generates the set of output symbols using chain-reaction encoding. 33. The method of claim 1, wherein generating the set of output symbols comprises employing a dynamic encoder to generate the set of output symbols using the set of redundant symbols generated from the input symbols, the ordered set of input symbols, and a plurality of dynamic keys.
Luby Michael G. ; Shokrollahi Mohammad Amin,DEX ; Stemann Volker,DEX ; Mitzenmacher Michael D. ; Spielman Daniel A., Irregularly graphed encoding technique.
Luby Michael G. ; Mitzenmacher Michael D. ; Shokrollahi Mohammad Amin,DEX ; Spielman Daniel A. ; Stemann Volker,DEX, Message encoding with irregular graphing.
Balicki Janusz K. ; Nouban Bezhad ; Kiani Khusrow, Method and apparatus for reducing the number of programmable architecture elements required for implementing a look-up t.
Danneels Gunner D. ; Cox Katherine ; Odell Robert M. ; Schlesinger Robert A. ; Gregory Leora J. ; Sampat Ketan R., Method for semi-reliable, unidirectional broadcast information services.
Albanese Andres (Berkeley CA) Luby Michael G. (Berkeley CA) Bloemer Johannes F. (Berkeley CA) Edmonds Jeffrey A. (Berkeley CA), System for packetizing data encoded corresponding to priority levels where reconstructed data corresponds to fractionali.
McRae Daniel D. (West Melbourne FL) Clark George C. (Indialantic FL) Szuchy Nicholas C. (Melbourne Beach FL), Technique for high rate digital transmission over a dynamic dispersive channel.
Watson, Mark; Luby, Michael G., Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient uses of the communications systems.
Luby, Michael G.; Pakzad, Payam; Shokrollahi, Mohammad Amin; Watson, Mark; Vicisano, Lorenzo, Encoding and decoding using elastic codes with flexible source block mapping.
Luby, Michael G.; Watson, Mark; Vicisano, Lorenzo; Pakzad, Payam; Wang, Bin, Enhanced block-request streaming using block partitioning or request controls for improved client-side handling.
Shokrollahi, M. Amin, Error-correcting multi-stage code generator and decoder for communication systems having single transmitters or multiple transmitters.
Reznik, Alexander; Zeira, Eldad M.; Ye, Chunxuan, Method and apparatus for transmitting and receiving multimedia broadcast multicast services via a dedicated downlink carrier.
Luby, Michael G.; Shokrollahi, Mohammad Amin; Minder, Lorenz Christoph, Methods and apparatus employing FEC codes with permanent inactivation of symbols for encoding and decoding processes.
Luby, Michael G.; Shokrollahi, Mohammad Amin; Minder, Lorenz Christoph, Methods and apparatus employing FEC codes with permanent inactivation of symbols for encoding and decoding processes.
Luby, Michael G.; Shokrollahi, Mohammad Amin; Minder, Lorenz Christoph, Methods and apparatus employing FEC codes with permanent inactivation of symbols for encoding and decoding processes.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.