Systems and processes for decoding chain reaction codes through inactivation
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
H03M-005/00
H03M-013/37
H03M-013/11
H03M-013/19
출원번호
US-0549560
(2009-08-28)
등록번호
US-9240810
(2016-01-19)
발명자
/ 주소
Shokrollahi, Amin
Lassen, Soren
Karp, Richard
출원인 / 주소
Digital Fountain, Inc.
인용정보
피인용 횟수 :
1인용 특허 :
225
초록▼
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
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.
대표청구항▼
1. A decoder configured to function in a chain reaction code communication system wherein an encoder generates a plurality of multi-stage output symbols that are check symbols and generates a plurality of source symbols, wherein each of the check symbols is associated with one or more source symbols
1. A decoder configured to function in a chain reaction code communication system wherein an encoder generates a plurality of multi-stage output symbols that are check symbols and generates a plurality of source symbols, wherein each of the check symbols is associated with one or more source symbols, the check symbols associated with one or more source symbols referred to as check symbols of degree one or higher, wherein at least one check symbol is associated with at least two source symbols, the check symbols associated with two or more source symbols referred to as check symbols of degree two or higher, and wherein at least one source symbol is marked as active, the decoder comprising: (i) a selector configured to select one of the active source symbols associated with a check symbol of degree two or higher; and(ii) an activate module communicatively coupled to the selector and configured to deactivate the selected source symbol associated with a check symbol of degree two or higher. 2. The decoder of claim 1, wherein a transmitter transmits the one or more source symbols to a receiver, the decoder further comprising: a processor communicatively coupled to the activate module and configured to infer the check symbols without having to receive them from the transmitter; and to use the inferred check symbols to check that the one or more source symbols were received correctly. 3. A decoder for decoding input symbols from output symbols, wherein output symbols are generated at an encoder for source symbols derived from the input symbols and check symbols associated with source symbols, wherein a degree of a check symbol is the number of source symbols associated with that check symbol and the degree of check symbols can be one or more than one, the decoder comprising: a receiver configured to receive output symbols and check symbols; anda processor communicatively coupled to the receiver and configured to mark source symbols as active to indicate that it is to be decoded from received output symbols and check symbols; mark at least one of the active source symbols that is associated with a check symbol of degree two or higher as an inactive source symbol; decode, in part, the received source symbols, by decoding the active source symbols; determine a process for decoding the inactive source symbols; and to decode the inactive source symbols. 4. The decoder of claim 3, wherein the check symbols are generated according to a parity code. 5. The decoder of claim 3, wherein the check symbols are generated according to an LDPC code. 6. A decoder for decoding source symbols from output symbols, wherein output symbols are generated at an encoder derived from the source symbols, wherein a degree of an output symbol is the number of source symbols associated with that output symbol, the decoder comprising: a receiver configured to (i) receive a first set of output symbols; anda processor communicatively coupled to the receiver and configured to: (ii) recover source symbols from the output symbols contained in the first set of output symbols;(iii) deactivate one or more unrecovered source symbols associated with an output symbol of degree two or higher thereby reducing the degree of any output symbol associated with a deactivated source symbol by one;(iv) repeat (ii) and (iii) until all of the output symbols in the first set of output symbols have been used; and(v) decode the source symbols that have been deactivated. 7. The decoder of claim 6, wherein the processor is further configured to: (vi) determine if all of the source symbols have been recovered; and(vii) request a second set of output symbols if it is determined that not all of the source symbols have been recovered;the receiver is further configured to (viii) receive a second set of output symbols; andthe processor and the receiver are further configured to (ix) repeat (ii)-(viii) on the second set of output symbols until all of the source symbols have been recovered. 8. The decoder of claim 6, wherein the receiver is further configured to (vi) receive a second set of output symbols; andthe processor is further configured to (vii) merge the second set of output symbols into the first set of output symbols. 9. The decoder of claim 8, wherein (vi) and (vii) are configured to occur substantially concurrently with (ii)-(v). 10. The decoder of claim 9, wherein (ii)-(vii) repeat until all of the source symbols have been recovered. 11. A decoder that receives multi-stage output symbols, wherein the multi-stage output symbols are generated at an encoder derived from output symbols and check symbols, wherein the output symbols are generated at an encoder derived from source symbols, wherein a degree of an output symbol is the number of source symbols associated with that output symbol, wherein a degree of a check symbol is the number of source symbols associated with that check symbol, the decoder comprising: a receiver configured to (i) receive a first set of multi-stage output symbols wherein at least one of the multi-stage output symbols in the first set of multi-stage output symbols comprises a check symbol and at least one of the multi-stage output symbols in the first set of output symbols comprises an output symbol; anda processor communicatively coupled to the receiver and configured to: (ii) recover source symbols from the output symbols contained in the first set of multistage output symbols;(iii) deactivate one or more unrecovered source symbols associated with an output symbol of degree two or higher thereby reducing the degree of any output symbol associated with a deactivated source symbol by one;(iv) repeat (ii) and (iii) until all of the output symbols in the first set of output symbols have been used;(v) decode the source symbols that have been deactivated; and(vi) recover check symbols from the check symbols in the first set of multi-stage output symbols. 12. The decoder of claim 11, wherein the processor is further configured to: (vii) determine if all of the source symbols have been recovered; and(viii) request a second set of multi-stage output symbols if it is determined that not all of the source symbols have been recovered;the receiver is further configured to (ix) receive a second set of multi-stage output symbols; andthe processor and the receiver are further configured to (x) repeat (ii)-(ix) on the second set of multi-stage output symbols until all of the source symbols have been recovered. 13. The decoder of claim 12, wherein the processor and the receiver are further configured to (xi) repeat (ii)-(ix) on the second set of multi-stage output symbols until all of the check symbols have been recovered. 14. The decoder of claim 11, wherein the receiver is further configured to (vii) receive a second set of multi-stage output symbols; andthe processor is further configured to (viii) merge the second set of multi-stage output symbols into the first set of multi-stage output symbols. 15. The decoder of claim 14, wherein (vii) and (viii) occur substantially concurrently with steps (ii)-(vi). 16. The decoder of claim 15, wherein (ii)-(viii) repeat until all of the source symbols have been recovered. 17. The decoder of claim 16, wherein (ii)-(viii) repeat until all of the check symbols have been recovered. 18. The decoder of claim 15, wherein (vi) can be interrupted in favor of (ii) if new output symbols containing source symbols are received. 19. A non-transitory computer program product in a chain reaction code communication system wherein an encoder generates a plurality of multi-stage output symbols that are check symbols and generates a plurality of source symbols, wherein each of the check symbols is associated with one or more source symbols, the check symbols associated with one or more source symbols referred to as check symbols of degree one or higher, wherein at least one check symbol is associated with at least two source symbols, the check symbols associated with two or more source symbols referred to as check symbols of degree two or higher, and wherein at least one source symbol is marked as active, the computer program product comprising: a processor-readable medium storing processor-readable instructions configured to cause a processor to: (i) select one of the active source symbols associated with a check symbol of degree two or higher; and(ii) deactivate the selected source symbol associated with a check symbol of degree two or higher. 20. The product of claim 19, wherein a transmitter transmits the one or more source symbols to a receiver, and the instructions are further configured to cause the processor to: infer, at a decoder at the receiver, the check symbols without having to receive them from the transmitter; anduse the inferred check symbols to check that the one or more source symbols were received correctly. 21. A non-transitory computer program product for decoding input symbols from output symbols, wherein output symbols are generated at an encoder for source symbols derived from the input symbols and check symbols associated with source symbols, wherein a degree of a check symbol is the number of source symbols associated with that check symbol and the degree of check symbols can be one or more than one, the computer program product comprising: a processor-readable medium storing processor-readable instructions configured to cause a processor to: receive output symbols and check symbols;mark source symbols as active to indicate that it is to be decoded from received output symbols and check symbols;mark at least one of the active source symbols that is associated with a check symbol of degree two or higher as an inactive source symbol;decode, in part, the received source symbols, by decoding the active source symbols;determine a process for decoding the inactive source symbols; anddecode the inactive source symbols. 22. The product of claim 21, wherein the check symbols are generated according to a parity code. 23. The product of claim 21, wherein the check symbols are generated according to an LDPC code. 24. A non-transitory computer program product for decoding source symbols from output symbols, wherein output symbols are generated at an encoder derived from the source symbols, wherein a degree of an output symbol is the number of source symbols associated with that output symbol, the computer program product comprising: a processor-readable medium storing processor-readable instructions configured to cause a processor to: (i) receive a first set of output symbols;(ii) recover source symbols from the output symbols contained in the first set of output symbols;(iii) deactivate one or more unrecovered source symbols associated with an output symbol of degree two or higher thereby reducing the degree of any output symbol associated with a deactivated source symbol by one;(iv) repeat steps (ii) and (iii) until all of the output symbols in the first set of output symbols have been used; and(v) decode the source symbols that have been deactivated. 25. The product of claim 24, wherein the instructions are further configured to cause the processor to: (vi) determine if all of the source symbols have been recovered;(vii) request a second set of output symbols if it is determined that not all of the source symbols have been recovered;(viii) receive a second set of output symbols; and(ix) repeat steps (ii)-(viii) on the second set of output symbols until all of the source symbols have been recovered. 26. The product of claim 24, wherein the instructions are further configured to cause the processor to: (vi) receive a second set of output symbols; and(vii) merge the second set of output symbols into the first set of output symbols. 27. The product of claim 26, wherein steps (vi) and (vii) occur substantially concurrently with steps (ii)-(v). 28. The product of claim 27, wherein steps (ii)-(vii) repeat until all of the source symbols have been recovered. 29. A non-transitory computer program product for processing multi-stage output symbols, wherein the multi-stage output symbols are generated at an encoder derived from output symbols and check symbols, wherein the output symbols are generated at an encoder derived from source symbols, wherein a degree of an output symbol is the number of source symbols associated with that output symbol, wherein a degree of a check symbol is the number of source symbols associated with that check symbol, the computer program product comprising: a processor-readable medium storing processor-readable instructions configured to cause a processor to: (i) receive a first set of multi-stage output symbols wherein at least one of the multi-stage output symbols in the first set of multi-stage output symbols comprises a check symbol and at least one of the multi-stage output symbols in the first set of output symbols comprises an output symbol;(ii) recover source symbols from the output symbols contained in the first set of multistage output symbols;(iii) deactivate one or more unrecovered source symbols associated with an output symbol of degree two or higher thereby reducing the degree of any output symbol associated with a deactivated source symbol by one;(iv) repeat steps (ii) and (iii) until all of the output symbols in the first set of output symbols have been used;(v) decode the source symbols that have been deactivated; and(vi) recover check symbols from the check symbols in the first set of multi-stage output symbols. 30. The product of claim 29, wherein the instructions are further configured to cause the processor to: (vii) determine if all of the source symbols have been recovered;(viii) request a second set of multi-stage output symbols if it is determined that not all of the source symbols have been recovered;(ix) receive a second set of multi-stage output symbols; and(x) repeat steps (ii)-(ix) on the second set of multi-stage output symbols until all of the source symbols have been recovered. 31. The product of claim 30, wherein the instructions are further configured to cause the processor to (xi) repeat steps (ii)-(ix) on the second set of multi-stage output symbols until all of the check symbols have been recovered. 32. The product of claim 29, wherein the instructions are further configured to cause the processor to: (vii) receive a second set of multi-stage output symbols; and(viii) merge the second set of multi-stage output symbols into the first set of multi-stage output symbols. 33. The product of claim 32, wherein steps (vii) and (viii) occur substantially concurrently with steps (ii)-(vi). 34. The product of claim 33, wherein steps (ii)-(viii) repeat until all of the source symbols have been recovered. 35. The product of claim 34, wherein steps (ii)-(viii) repeat until all of the check symbols have been recovered. 36. The product of claim 33, wherein step (vi) can be interrupted in favor of step (ii) if new output symbols containing source symbols are received.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (225)
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.
Cheng Mark W ; Honkasalo Zhi-Chun,FIX, Method and apparatus for segmentation and assembly of data frames for retransmission in a telecommunications system.
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.
Parekh, Nileshkumar J.; Chandhok, Ravinder Paul (Rob); O'Keefe, Michael; Chen, An Mei; Walker, Gordon Kent, Methods and apparatus for providing content information to content servers.
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.
Lu,Ming; Zheng,Haitao, Radio link protocol (RLP)/point-to-point protocol (PPP) design that passes corrupted data and error location information among layers in a wireless data transmission protocol.
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.
Meulemans, Michael Edward; Averbuch, Aaron; Roberts, Jason; Showman, Ken; Mohammed, Mazhar; Dadzie, Joseph G., System and method for managing and communicating software updates.
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.
Haberman, Seth; Schuler, Chester L.; van der Burgh, Abeljan; Jansen, Alex; Niemeijer, Gerrit, System and method for simultaneous broadcast for personalized messages.
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.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.