Generating and communicating source identification information to enable reliable communications
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
H04J-003/24
H04J-003/06
G06F-003/00
G06F-011/00
H04L-012/801
H04L-001/00
H04L-001/18
출원번호
US-0210024
(2008-09-12)
등록번호
US-9237101
(2016-01-12)
발명자
/ 주소
Chen, Steve
Luby, Michael G.
Prasad, Manu
Seed, William
Stockhammer, Thomas
출원인 / 주소
Digital Fountain, Inc.
인용정보
피인용 횟수 :
2인용 특허 :
215
초록▼
A method of generating Source Identification information from a source packet stream and reliably transmitting the Source Identification information from a source to a destination over a communications channel is provided. The method operates on a set of source packets, wherein Source Identification
A method of generating Source Identification information from a source packet stream and reliably transmitting the Source Identification information from a source to a destination over a communications channel is provided. The method operates on a set of source packets, wherein Source Identification information for each source packet to be transmitted is derived and delivered with the Source Identification information of all or most other source packets of an associated source block. The method includes techniques to minimize the network bandwidth required to deliver Source Identification information and techniques to overcome network impairments. When combined with FEC techniques, retransmission techniques, or combinations of FEC techniques and retransmission techniques, the methods described herein allow receivers to recover lost source packets, while simultaneously ensuring that the original source packets are not modified and thereby ensuring backwards compatibility for legacy receivers.
대표청구항▼
1. A method for generating and transmitting source identification data for source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other
1. A method for generating and transmitting source identification data for source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising: generating source identification data from the K source data units;transmitting a first data stream to a receiver, wherein the first data stream comprises a set of the source data units, wherein the first data stream does not have the source identification data; andtransmitting a second data stream to the receiver, wherein the second data stream comprises the source identification data, wherein the second data stream is distinct from the first data stream, wherein the source identification data is distinct from the set of the source data units transmitted on the first data stream, and wherein the source identification data is usable to identify source data units in the set of source data units transmitted on the first data stream. 2. The method of claim 1 wherein the source identification data enables a recipient of the first and the second data streams to determine identification labels for the K source data units used to generate the source identification data. 3. The method of claim 1 wherein the source identification data enables a recipient of the first and the second data streams to determine identification labels for any source data unit. 4. The method of claim 1 wherein the source identification data enables a recipient of the first and the second data streams to determine a position of a given source data unit with respect to an ordering of all the source data units. 5. The method of claim 1 wherein the source identification data enables a recipient of the first and the second data streams to determine a position of a given source data unit with respect to a source-determined order sequence of all of the source data units. 6. The method of claim 1 wherein the second data stream further comprises repair data for the source data units. 7. The method of claim 1 wherein the second data stream further comprises repair data for the source identification data. 8. The method of claim 1 wherein the first data stream is transmitted via DVB-T and wherein the second data stream is transmitted via DVB-H. 9. The method of claim 1 further comprising: receiving a request from the receiver for additional data; andtransmitting a third data stream to the receiver. 10. The method of claim 9 wherein the third data stream comprises a second set source data units. 11. The method of claim 9 wherein the third data stream comprises repair data for the source data units. 12. A method for generating and transmitting source identification data for source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising: generating source identification data from the K source data units, comprising:a) creating an ordered set S from each of the K source data units; i) applying a hash function, Hi, to each member of S, wherein Hi maps the members of S to one of a possible L hash outputs and wherein Hi maps at least X of the members of S to a unique hash output;ii) creating a vector corresponding to the L hash outputs, wherein the vector indicates which of the L hash outputs experience collisions and which of the L hash outputs uniquely map to a member of S;iii) creating a set, Si, comprising the elements of S that do not map to a unique hash output;iv) iterating steps i-iii until either Si is an empty set or a maximum number of iterations have been executed, wherein for each iteration of steps i-iii Si is used as S, wherein for each iteration Hi is a hash function that differs from the hash function used during the previous iteration of steps i-iii, wherein for each iteration the values of L and X can change; andb) generating source identification data from the vectors created during each iteration of steps i-iii;c) transmitting a first data stream to a receiver, wherein the first data stream comprises a set of the source data units; andd) transmitting a second data stream to the receiver, wherein the second data stream comprises the source identification data. 13. The method of claim 12 wherein the vector further indicates the location of each uniquely mapped member of S in S, the method further comprising: generating a position-to-sequence mapping from the location of the uniquely mapped members of S as indicated by the vectors created during each iteration of steps i-iii. 14. A non-transitory computer readable medium comprising code for performing the method of claim 1. 15. A transmitter comprising a processor and the computer readable medium of claim 14 coupled to the processor. 16. A method for receiving source identification data and associating the source identification data with source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising: receiving a plurality of source data units from a first data stream, wherein the first data stream does not have the source identification data;receiving source identification data from a second data stream, wherein the second data stream is distinct from the first data stream; andassociating the source identification data obtained from a set of packets from the second data stream with the plurality of source data units obtained from packets distinct from the set of packets from the second data stream, wherein the source identification data is usable to identify source data units in the plurality of source data units. 17. The method of claim 16 further comprising: determining identification labels for the received plurality of source data units. 18. The method of claim 16 further comprising: determining identification labels for any source data units that are not a member of the received plurality of source data units. 19. The method of claim 16 further comprising: determining a position for a source data unit in the plurality of source data units with respect to an ordering of all the source data units. 20. The method of claim 16 further comprising: determining a position for a source data unit in the plurality of source data units with respect to a source-determined order sequence of all of the source data units. 21. The method of claim 16 further comprising: receiving repair data for the plurality of source data units from the second data stream. 22. The method of claim 16 further comprising: receiving repair data for the source identification data from the second data stream. 23. The method of claim 16 wherein the first data stream is received via DVB-T and wherein the second data stream is received via DVB-H. 24. The method of claim 16 further comprising: analyzing the source identification data and the plurality of source data units to determine if any of the K source data units have not been received; andif any of the K source data units have not been received, requesting additional data. 25. The method of claim 24 further comprising: receiving the additional data from a third data stream. 26. A method for receiving source identification data and associating the source identification data with source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising: receiving a plurality of source data units from a first data stream;receiving source identification data from a second data stream; andassociating the source identification data with the plurality of source data units comprises:i) creating a set, S, from each of the plurality of source data units;ii) applying a hash function, Hi, to each member of S to obtain a hashed output associated with each of member of S, wherein Hi maps each of the members of S to one of a possible L hash outputs;iii) determining which of the hashed outputs uniquely identify the source data unit associated with the hashed output;iv) if it is determined that a hashed output does uniquely identify a source data unit, removing the uniquely identified source data unit from S and associating a proper set of identification data from the source identification data with the uniquely identified source data unit; andv) if it is determined that one of the hashed output is not unique, iterating steps i-iii unit S is an empty set or until a maximum number of iterations have been executed, wherein for each iteration Hi is a hash function that differs from the hash function used during the pervious iteration of steps ii-iv with a potentially different value of L. 27. The method of claim 26 wherein the Hi applied for each iteration of steps ii-v is determined from the source identification data. 28. The method of claim 26 wherein determining which of the hashed outputs uniquely identify the source data unit associated with the hashed output comprises: comparing each hashed output to a vector from the source identification data, wherein the vector corresponds to the possible L hash outputs, and wherein the vector indicates which of the L hash outputs experience collisions and which of the L hash outputs uniquely map to a member of S. 29. The method of claim 28 wherein the source identification data includes a position-to-sequence mapping and wherein associating a proper set of identification data from the source identification data with the uniquely identified source data unit comprises associating location information from the position-to-sequence mapping to the uniquely identified source data unit. 30. The method of claim 26 further comprising: if a source data unit is associated with a proper set of identification data from the source identification data, passing the source data unit to a decoder. 31. The method of claim 26 further comprising: if a source data unit is not associated with a proper set of identification data from the source identification data, discarding the source data unit. 32. A non-transitory computer readable medium comprising code for performing the method of claim 16. 33. A receiver comprising a processor and the computer readable medium of claim 32 coupled to the processor. 34. A system for generating and transmitting source identification data for source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the system comprising: means for generating source identification data from the K source data units; andmeans for transmitting a first data stream and a second data stream to a receiver, wherein the first data stream comprises a set of the source data units, wherein the first data stream does not have the source identification data, wherein the second data stream comprises the source identification data, wherein the second data stream is distinct from the first data stream, wherein the source identification data is distinct from the set of the source data units transmitted on the first data stream, and wherein the source identification data is usable to identify source data units in the set of source data units transmitted on the first data stream. 35. A system for receiving source identification data and associating the source identification data with source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the system comprising: means for receiving a plurality of source data units from a first data stream and receiving source identification data from a second data stream, wherein the first data stream does not have the source identification data, wherein the second data stream is distinct from the first data stream; andmeans for associating the source identification data obtained from a set of packets from the second data stream with the plurality of source data units obtained from packets distinct from the set of packets from the second data stream, wherein the source identification data is usable to identify source data units in the plurality of source data units.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (215)
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.
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.
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.
Kim, Young Wook; Kim, Jong Soo; Park, Jung Jun; Yang, Seung Kwan; Oh, Jae Won; Woo, Chang Hee; Lee, Sang Hyun, System and method for managing buffering in peer-to-peer (P2P) based streaming service and system for distributing application for processing buffering in client.
Kim, Young Wook; Kim, Jong Soo; Park, Jung Jun; Yang, Seung Kwan; Oh, Jae Won; Woo, Chang Hee; Lee, Sang Hyun, System and method for packetizing data stream in peer-to-peer (P2P) based streaming service.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.