Error-correcting multi-stage code generator and decoder for communication systems having single transmitters or multiple transmitters
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
H03M-013/00
H03M-013/37
출원번호
US-0252331
(2008-10-15)
등록번호
US-8887020
(2014-11-11)
발명자
/ 주소
Shokrollahi, M. Amin
출원인 / 주소
Digital Fountain, Inc.
대리인 / 주소
Morris, Anthony R.
인용정보
피인용 횟수 :
7인용 특허 :
216
초록▼
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 effectiv
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.
대표청구항▼
1. A method of receiving data transmitted from a source over a communications channel, wherein the data is transmitted as a plurality of output symbols and is generated from at least one symbol in a combined set of input symbols of an input file and redundant symbols, wherein the number of possible
1. A method of receiving data transmitted from a source over a communications channel, wherein the data is transmitted as a plurality of output symbols and is generated from at least one symbol in a combined set of input symbols of an input file and redundant symbols, wherein the number of possible valid output symbols for a given set of symbols in the combined set is independent of the number of input symbols in the input file, and wherein the redundant symbols are generated from the input symbols, the method comprising: receiving output symbols from the communications channel, wherein the communications channel might have introduced errors and/or erasures; andregenerating at least a subset of the symbols in the combined set from the received output symbols, the subset of the symbols in the combined set including a plurality of regenerated input symbols and a plurality of regenerated redundant symbols, the regenerating using input symbol probability distributions determined from estimates of output symbol probability distributions, wherein an input symbol probability distribution represents probabilities of particular input symbols having been encoded to form the received output symbols, and wherein the estimates of output symbol probability distributions are determined from probabilities, given a received output symbol, that a particular output symbol was transmitted. 2. The method of claim 1, further comprising: determining, for received output symbols, an information quantity associated with the received output symbol;accumulating a total information quantity associated with a plurality of received output symbols; andtriggering regenerating when the accumulated total information quantity meets predefined criteria relative to an information content quantity of the ordered set of input symbols. 3. The method of claim 2, wherein the predefined criteria includes a criterion that the accumulated total information is equal to the information content quantity of the ordered set of input symbols plus a small additional amount of information, wherein the small additional amount of information is a percentage of the information content quantity of the input symbols. 4. The method of claim 1, further comprising: quantizing output symbol probability distributions according to a coarse quantization in a first decoding phase; andquantizing output symbol probability distributions according to a fine quantization in a second decoding phase, wherein the coarse quantization has fewer quantization levels than the fine quantization. 5. The method of claim 1, wherein output symbol probability distributions comprise probability values each taking on one of two values, with one of the values representing a high probability and the other representing a low probability. 6. The method of claim 1, further comprising reading the output symbol probability distributions as representing probability per bit of an output symbol indicating a probability that the bit was a one or a zero at transmission. 7. The method of claim 1, further comprising reading the input symbol probability distribution stored as a data structure not including entries for possible transmitted bits or symbols when the corresponding estimated probability is zero. 8. The method of claim 1, wherein each output symbol is associated with a key I selected from a key alphabet and the number of possible keys in the key alphabet is independent of the number of input symbols in the input file. 9. The method of claim 1, wherein the redundant symbols include a first plurality of redundant symbols and a second plurality of redundant symbols, wherein the regenerating at least some of the unregenerated input symbols includes: regenerating, from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols, at least one of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols; andregenerating at least one unregenerated input symbol from redundant symbols of the second plurality of redundant symbols and the plurality of decoded input symbols if the step of regenerating from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols does not regenerate the input symbols to a desired degree of accuracy. 10. The method of claim 9, further comprising: regenerating some of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols using an LDPC decoder; andregenerating some input symbols from redundant symbols of the second plurality of redundant symbols using a Hamming decoder. 11. The method of claim 1, further comprising tracking, for error correction, probability estimates for more than one possibility for a given input symbol and then selecting the highest probability estimate. 12. The method of claim 1, wherein probability distributions comprise probability estimates that are based, at least in part, on strength or intensity of communications signals representing the received output symbols. 13. The method of claim 1, wherein probability distributions comprise probability estimates that are based on a function of distance between a received signal and possible values for the received signal. 14. The method of claim 1, further comprising calculating an estimate of an amount of information in a received output symbol as a binary entropy of a probability distribution of the received output symbol over possible transmitted output symbols. 15. Computer-readable program code embedded in non-transitory computer storage medium for processing data received over a communications channel, the data having been transmitted as a plurality of output symbols generated from a combined set of input symbols of an input file and redundant symbols, wherein the number of possible valid output symbols for a given set of symbols in the combined set is independent of the number of input symbols in the input file, and wherein the redundant symbols are generated from the input symbols, the program code comprising: program code for receiving output symbols, possibly including errors and/or erasures; andprogram code for regenerating at least a subset of the symbols in the combined set from the received output symbols taking into account the possibility of errors and/or erasures, the subset of the symbols in the combined set including a plurality of regenerated input symbols and a plurality of regenerated redundant symbols, the program code for regenerating also including program code for (i) determining input symbol probability distributions from estimates of output symbol probability distributions, wherein an input symbol probability distribution represents probabilities of particular input symbols having been encoded to form the received output symbols, and (ii) determining the estimates of output symbol probability distributions from probabilities, given a received output symbol, that a particular output symbol was transmitted. 16. The computer-readable program code of claim 15, further comprising: program code for determining, for received output symbols, an information quantity associated with the received output symbol;program code for accumulating a total information quantity associated with a plurality of received output symbols; andprogram code for triggering one or more of the steps of regenerating when the accumulated total information quantity meets predefined criteria relative to an information content quantity of the ordered set of input symbols. 17. The computer-readable program code of claim 16, wherein the predefined criteria includes a criterion that the accumulated total information is equal to the information content quantity of the ordered set of input symbols plus a small additional amount of information, wherein the small additional amount of information is a percentage of the information content quantity of the ordered set of input symbols. 18. The computer-readable program code of claim 15, further comprising: program code for coarse quantization for quantizing output symbol probability distributions coarsely in a first decoding phase; andprogram code for fine quantization for quantizing output symbol probability distributions in a second decoding phase, wherein the coarse quantization has fewer quantization levels than the fine quantization. 19. The computer-readable program code of claim 15, wherein output symbol probability distributions comprise probability values each taking on one of two values, with one of the values representing a high probability and the other representing a low probability. 20. The computer-readable program code of claim 15, further comprising program code to read the output symbol probability distributions as representing probability per bit of an output symbol indicating a probability that the bit was a one or a zero at transmission. 21. The computer-readable program code of claim 15, further comprising program code to read the input symbol probability distribution stored as a data structure not including entries for possible transmitted bits or symbols when the corresponding estimated probability is zero. 22. The computer-readable program code of claim 15, wherein each output symbol is associated with a key I selected from a key alphabet and the number of possible keys in the key alphabet is independent of the number of input symbols in the input file. 23. The computer-readable program code of claim 15, wherein the redundant symbols include a first plurality of redundant symbols and a second plurality of redundant symbols, wherein the program code for regenerating at least some of the unregenerated input symbols includes: program code for regenerating, from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols, at least one of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols; andprogram code for regenerating at least one unregenerated input symbol from redundant symbols of the second plurality of redundant symbols and the plurality of decoded input symbols if regenerating from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols does not regenerate the input symbols to a desired degree of accuracy. 24. The computer-readable program code of claim 23, further comprising: program code for regenerating some of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols using an LDPC decoder; andprogram code for regenerating some input symbols from redundant symbols of the second plurality of redundant symbols using a Hamming decoder. 25. The computer-readable program code of claim 15, further comprising program code for tracking, for error correction, probability estimates for more than one possibility for a given input symbol and then selecting the highest probability estimate. 26. The computer-readable program code of claim 15, wherein probability distributions comprise probability estimates that are based, at least in part, on strength or intensity of communications signals representing the received output symbols. 27. The computer-readable program code of claim 15, wherein probability distributions comprise probability estimates that are based on a function of distance between a received signal and possible values for the received signal. 28. The computer-readable program code of claim 15, further comprising calculation program code for calculating an estimate of an amount of information in a received output symbol as a binary entropy of a probability distribution of the received output symbol over possible transmitted output symbols. 29. A decoder for decoding input symbols from a plurality of received output symbols, the plurality of received output symbols having been transmitted over a communications channel that might have introduced errors and/or erasures, and the output symbols having been generated from at least one symbol in a combined set of input symbols of an input file and redundant symbols, wherein the number of possible valid output symbols for a given set of symbols in the combined set is independent of the number of input symbols in the input file, and wherein the redundant symbols are generated from the input symbols, the decoder comprising: a receive module for receiving output symbols from the communications channel and for storing output symbols as data units; anda decoding unit for regenerating at least a subset of the symbols in the combined set from the received output symbols, the subset of the symbols in the combined set including a plurality of regenerated input symbols and a plurality of regenerated redundant symbols, the regenerating using input symbol probability distributions determined from estimates of output symbol probability distributions, wherein an input symbol probability distribution represents probabilities of particular input symbols having been encoded to form the received output symbols, and wherein the estimates of output symbol probability distributions are determined from probabilities, given a received output symbol, that a particular output symbol was transmitted. 30. The decoder of claim 29, further comprising: a dynamic decoder module;storage for regenerated input symbols and regenerated redundant symbols; anda static decoder module. 31. The decoder of claim 29, further comprising storage for output symbol probability distributions. 32. The decoder of claim 29, further comprising storage for the input symbol probability distribution, stored as a data structure not including entries for possible transmitted bits or symbols when the corresponding estimated probability is zero. 33. The decoder of claim 29, further comprising a key generator, wherein each output symbol is associated with a key I selected from a key alphabet and the number of possible keys in the key alphabet is independent of the number of input symbols in the input file. 34. The decoder of claim 29, wherein the decoding unit further comprises storage for a total information quantity associated with a plurality of received output symbols and is configured to trigger a regenerating process when the total information quantity meets a predefined criteria relative to an information content quantity of the input symbols. 35. The decoder of claim 34, wherein the predefined criteria includes a criterion that the total information quantity is equal to the information content quantity of the input symbols plus a small additional amount of information, wherein the small additional amount of information is a percentage of the information content quantity of the input symbols. 36. The decoder of claim 29 wherein the decoding unit is configured to perform at least two levels of quantization. 37. The decoder of claim 29, wherein output symbol probability distributions comprise probability values each taking on one of two values, with one of the values representing a high probability and the other representing a low probability. 38. The decoder of claim 29, wherein each output symbol is associated with a key I selected from a key alphabet and the number of possible keys in the key alphabet is independent of the number of input symbols in the input file. 39. The decoder of claim 29, wherein the redundant symbols include a first plurality of redundant symbols and a second plurality of redundant symbols, and the decoding unit is configured to regenerate, from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols, at least one of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols, and regenerate at least one unregenerated input symbol from redundant symbols of the second plurality of redundant symbols and the plurality of decoded input symbols if regenerating from the regenerated redundant symbols of the first plurality of redundant symbols and the plurality of regenerated input symbols does not regenerate the input symbols to a desired degree of accuracy. 40. The decoder of claim 39, further comprising: an LDPC decoder that regenerates some of the unregenerated input symbols and unregenerated redundant symbols of the second plurality of redundant symbols; anda Hamming decoder that regenerates some input symbols from redundant symbols of the second plurality of redundant symbols. 41. The decoder of claim 29, wherein probability distributions comprise probability estimates that are based, at least in part, on strength or intensity of communications signals representing the received output symbols. 42. The decoder of claim 29, wherein probability distributions comprise probability estimates that are based on a function of distance between a received signal and possible values for the received signal.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (216)
Parry, William G.; Lee, Mingtzong; Lorton, Christopher W.; Raja, Jayachandran; Smirnov, Serge, Analyzing, indexing and seeking of streaming information.
Chang,Hoon; Lee,Hyun Seok; Kim,Dae Gyun; Koo,Chang Hoi, Apparatus and method for exchanging variable-length data according to radio link protocol in mobile communication system.
Chang,Hoon; Lee,Hyun Seok; Kim,Dae Gyun; Koo,Chang Hoi, Apparatus and method for exchanging variable-length data according to radio link protocol in mobile communication system.
Eberlein Ernst,DEX ; Breiling Marco,DEX ; Stoessel Jan,DEX ; Gerhauser Heinz,DEX, Apparatus and method for transmitting information and apparatus and method for receiving information.
Oh, Jong-Ee; Lee, Sok-Kyu; Cheong, Min-Ho; Choi, Jee-Yon; Park, Jae-Woo; Chung, Hyun-Kyu, Apparatus and method for transmitting/receiving data in communication system.
Dill,Jeffrey C.; Lopez Permouth,Sergio R.; Lindsey,Alan Ray; Lo,Yung Cheng; Alder,Frank A.; Song,Xiangyu, Apparatus and method of CTCM encoding and decoding for a digital communication system.
Watson, Mark; Luby, Michael G., Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems.
Gelman Alexander (Brooklyn NY) Kobrinski Haim (Colts Neck NJ) Smoot Lanny S. (Morris Township ; Morris County NJ) Weinstein Stephen B. (Summit NJ), Communications architecture and method for distributing information services.
Glover Willie T. (San Jose CA) Singh Gururaj (San Jose CA) Gupta Amar (Cupertino CA) Newman Peter (Mountain View CA), Concurrent multi-channel segmentation and reassembly processors for asynchronous transfer mode.
Bolosky William J. ; Douceur John R., Continuous media file server system and method for scheduling network resources to play multiple files having different data transmission rates.
Witty Carl R. ; Birdwell Kenneth J. ; Sargent James Randall ; Moran Brian, Data delivery system and method for delivering data and redundant information over a unidirectional network.
Butterfield Lee A ; Giallorenzi Thomas R ; Gibson ; Jr. L Andrew ; Griffin Dan M ; Harris Johnny M ; Perkins Steven B ; Steagall R William, Data scrambling system and method and communications system incorporating same.
Shokrollahi,M. Amin, Error-correcting multi-stage code generator and decoder for communication systems having single transmitters or multiple transmitters.
Shokrollahi,M. Amin, Error-correcting multi-stage code generator and decoder for communication systems having single transmitters or multiple transmitters.
Schuster Guido M. ; Borella Michael ; Mahler Jerry ; Sidhu Ikhlaq, Forward error correction system for packet based data and real time media, using cross-wise parity calculation.
Luby Michael G. ; Shokrollahi Mohammad Amin,DEX ; Stemann Volker,DEX ; Mitzenmacher Michael D. ; Spielman Daniel A., Irregularly graphed encoding technique.
Wolfgang, H. Lewis, METHOD FOR PACKET-LEVEL FEC ENCODING, IN WHICH ON A SOURCE PACKET-BY-SOURCE PACKET BASIS, THE ERROR CORRECTION CONTRIBUTIONS OF A SOURCE PACKET TO A PLURALITY OF WILDCARD PACKETS ARE COMPUTED, AND TH.
Luby Michael G. ; Mitzenmacher Michael D. ; Shokrollahi Mohammad Amin,DEX ; Spielman Daniel A. ; Stemann Volker,DEX, Message encoding with irregular graphing.
Krause Edward A. ; Shen Paul ; Tom Adam S., Method and apparatus for encoding and formatting data representing a video program to provide multiple overlapping prese.
Kroeger, Brian William; Vojcic, Branimir; Pickholtz, Raymond L.; El-Dinary, Ashruf, Method and apparatus for forward error correction coding for an AM in-band on-channel digital audio broadcasting system.
Miura,Tsuyoshi; Ihara,Noriyuki; Fujita,Shin; Nakagawa,Akira; Ichiki,Atsushi, Method and apparatus for generating error correction data, and a computer-readable recording medium recording an error correction data generating program thereon.
Deck Bernhard,DEX ; Lehmann Josef,DEX ; Ramseier Stefan,CHX ; Westby Oddleif,NOX, Method and apparatus for information transmission via power supply lines.
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.
Park, Jaewoo; Oh, Jong-Ee; Lee, Il-Gu; Lee, Sok-Kyu; Cheong, Minho; Choi, Jeeyon; Lee, Jae-Seung; Kim, Yun-Joo, Method and apparatus for transceiving data in a MIMO system.
Baird Randall B. ; McFadden Martin J., Method for accessing one or more streams in a video storage system using multiple queues and maintaining continuity ther.
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.
Kim, Jin Pil; Kim, Young In; Hong, Ho Taek; Choi, In Hwan; Kwak, Kook Yeon; Lee, Hyoung Gon; Kim, Byoung Gill; Kim, Jin Woo; Kim, Jong Moon; Song, Won Gyu, Method of processing traffic information and digital broadcast system.
Rachel E. Tillman ; Thomas R. Gardos ; John J. Kirby ; Jeff N. Kidder ; Rajeeb Hazra, Method of providing replay on demand for streaming digital multimedia.
Shokrollahi, Mohammad Amin; Luby, Michael, Methods and apparatus employing FEC codes with permanent inactivation of symbols for encoding and decoding processes.
Horn,Gavin; Luby,Michael G.; Rasmussen,Jens; Knudsgaard,Per; Lassen,Soren, Methods and apparatus for scheduling, serving, receiving media-on demand for clients, servers arranged according to constraints on resources.
Asamizuya Noboru,JPX ; Ebihara Norio,JPX ; Karibe Haruyuki,JPX ; Kodama Yasumasa,JPX ; Kagawa Masaaki,JPX, On-demand data transmission by dividing input data into blocks and each block into sub-blocks such that the sub-blocks a.
Aggarwal Charu Chandra ; Wolf Joel Leonard ; Yu Philip Shi-Lung, Permutation based pyramid block transmission scheme for broadcasting in video-on-demand storage systems.
Srikantan,Geetha; Narasimhan,Aravind; Proctor,Seth; Brittenson,Jan; Shafer,Matthew; Sergent,Jonathan S., Streaming a single media track to multiple clients.
Castagna, Pete; Randall, Dave, System and method for interference mitigation using adaptive forward error correction in a wireless RF data transmission system.
Rasmussen,Jens; Shokrollahi,Amin; Lassen,Soren; Horn,Gavin; Goyal,Vivek; Dobyns,Barry; Luby,Michael, System and method for reliably communicating the content of a live data stream.
Brewer, Tony M.; Blackmon, Harry C.; Davies, Chris; Dozier, Harold W.; McDermott, III, Thomas C.; Wallach, Steven J.; Walker, Dean E.; Yeh, Lou, System and method for router data aggregation and delivery.
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.
Campanella S. Joseph, System for time division multiplexing broadcast channels with R-1/2 or R-3/4 convolutional coding for satellite transmission via on-board baseband processing payload or transparent payload.
Chilvers, Henry C.; Olague, Craig Alan; Archer, Kuan Hidalgo, Systems and methods for providing remote program ordering on a user device via a web server.
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.
Schreiber William F. (Cambridge MA) Polley Michael O. (Belmont MA), Television transmission system using spread spectrum and orthogonal frequency-division multiplex.
Baik, Jong-Hyun; Suh, YoungKil; Kim, Sung-Won; Heo, Jun, Apparatus and method for transmitting data using fountain code in wireless communication system.
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는 부적절한 답변을 할 수 있습니다.