| Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems -> Monitor Keywords |
|
|
  Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systemsUSPTO Application #: 20070300127Title: Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems Abstract: A method of encoding data for transmissions from a source to a destination over a communications channel is provided. The method operates on an ordered set of source symbols and may generate zero or more redundant symbols from the source symbols, wherein data is encoded in a first step according to a simple FEC code and in a second step, data is encoded according to a second FEC code, more complex than the first FEC code. The first FEC code and/or the second FEC code might comprise coding known in the art. These steps result in two groups of encoded data in such a way that a low-complexity receiver may make use of one of the groups of encoded data while higher complexity receivers may make use of both groups of encoded data. (end of abstract)
Agent: Townsend And Townsend And Crew, LLP - San Francisco, CA, US Inventors: Mark Watson, Michael G. Luby USPTO Applicaton #: 20070300127 - Class: 714758000 (USPTO) Related Patent Categories: Error Detection/correction And Fault Detection/recovery, Pulse Or Data Error Handling, Digital Data Error Correction, Forward Correction By Block Code, Error Correcting Code With Additional Error Detection Code (e.g., Cyclic Redundancy Character, Parity) The Patent Description & Claims data below is from USPTO Patent Application 20070300127. Brief Patent Description - Full Patent Description - Patent Application Claims
CROSS-REFERENCES [0001] This application claims priority from and is a non-provisional of U.S. Provisional Patent Application No. 60/799,536 filed May 10, 2006. [0002] The following references are include here and are incorporated by reference for all purposes: [0003] U.S. Pat. No. 6,307,487 entitled "Information Additive Code Generator and Decoder for Communication Systems" issued to Luby (hereinafter "Luby I"); [0004] U.S. Published Patent Application No. 2005/0257106 published Nov. 17, 2005 and entitled "File Download and Streaming System" to Luby, et al. (hereinafter "Luby II"); [0005] U.S. Pat. No. 7,068,729 entitled "Multi-Stage Code Generator and Decoder for Communication Systems" issued to Shokrollahi, et al. (hereinafter "Shokrollahi I"); [0006] U.S. Published Patent Application No. 2006/0036930 published Feb. 16, 2006 and entitled "Method and Apparatus for Fast Encoding of Data Symbols According to Half-Weight Codes" to Luby, et al. (hereinafter "Luby III"); and [0007] U.S. Pat. No. 6,856,263 entitled "Systems and Processes for Decoding Chain Reaction Codes Through Inactivation" issued to Shokrollahi, et al. (hereinafter "Shokrollahi II"). FIELD OF THE INVENTION [0008] The present invention relates to encoding and decoding data in communications systems, and more specifically to communication systems that encode and decode data to account for errors and gaps in communicated. BACKGROUND OF THE INVENTION [0009] Transmission of files and streams between a sender and a recipient over a communications channel has been the subject of much literature. Preferably, a recipient desires to receive an exact copy of data transmitted over a channel by a sender with some level of certainty. Where the channel does not have perfect fidelity, which characterizes most physically realizable systems, one concern is how to deal with data that is lost or corrupted in transmission. Lost data (erasures) are often easier to deal with than corrupted data (errors) because the recipient cannot always recognize when the transmitted data has been corrupted. [0010] Many error-correcting codes have been developed to correct erasures and/or errors. Typically, the particular code used is chosen based on some information about the infidelities of the channel through which the data is being transmitted, and the nature of the data being transmitted. For example, where the channel is known to have long periods of infidelity, a burst error code might be best suited for that application. Where only short, infrequent errors are expected, a simple parity code might be best. [0011] "Communication", as used herein, refers to data transmission, through space and/or time, such as data transmitted from one location to another or data stored at one time and used at another. The channel is that which separates the sender and receiver. Channels in space can be wires, networks, fibers, wireless media, etc. between a sender and receiver. Channels in time can be data storage devices. In realizable channels, there is often a nonzero chance that the data sent or stored by the sender is different when it is received or read by the recipient and those differences might be due to errors introduced in the channel. [0012] Data transmission is straightforward when a transmitter and a receiver have all of the computing power and electrical power needed for communications, and the channel between the transmitter and receiver is reliable enough to allow for relatively error-free communications. Data transmission becomes more difficult when the channel is in an adverse environment, or the transmitter and/or receiver has limited capability. In certain applications, uninterrupted error-free communication is required over long periods of time. For example, in digital television systems it is expected that transmissions will be received error-free for periods of many hours at a time. In these cases, the problem of data transmission is difficult even in conditions of relatively low levels of errors. [0013] Another scenario in which data communication is difficult is where a single transmission is directed to multiple receivers that may experience widely different data loss conditions. Furthermore, the conditions experienced by one given receiver may vary widely or may be relatively constant over time. [0014] One solution to dealing with date loss (errors and/or erasures) is the use of forward error correcting (FEC) techniques, wherein data is coded at the transmitter in such a way that a receiver can correct transmission erasures and errors. Where feasible, a reverse channel from the receiver to the transmitter allows for the receiver to relay information about these errors to the transmitter, which can then adjust its transmission process accordingly. Often, however, a reverse channel is not available or feasible, or is available only with limited capacity. For example, in cases in which the transmitter is transmitting to a large number of receivers, the transmitter might not be able to maintain reverse channels from all the receivers. In another example, the communication channel may be a storage medium. [0015] Thus, data is transmitted chronologically forward through time, and causality precludes a reverse channel that can fix errors before they happen. As a result, communication protocols often need to be designed without a reverse channel or with a limited capacity reverse channel and, as such, the transmitter may have to deal with widely varying channel conditions without prior knowledge of those channel conditions. [0016] In the case of a packet protocol used for data transport over a channel that can lose packets, a file, stream, or other block of data to be transmitted over a packet network is partitioned into equally-sized source symbols. Encoding symbols the same size as the source symbols are generated from the source symbols using an FEC code, and the encoding symbols are placed and sent in packets. The "size" of a symbol can be measured in bits, whether or not the symbol is actually broken into a bit stream, where a symbol has a size of M bits when the symbol is selected from an alphabet of 2.sup.M symbols. In such a packet-based communication system, a packet oriented erasure FEC coding scheme might be suitable. [0017] A file transmission is called reliable if it allows the intended recipient to recover an exact copy of the original file despite erasures in the network. A stream transmission is called reliable if it allows the intended recipient to recover an exact copy of each part of the stream in a timely manner despite erasures in the network. Both file transmission and stream transmission can instead be not entirely reliable, but somewhat reliable, in the sense that some parts of the file or stream are not recoverable or, for streaming, some parts of the stream might be recoverable but not in a timely fashion. [0018] Packet loss often occurs because sporadic congestion causes the buffering mechanism in a router to reach its capacity, forcing it to drop incoming packets. Protection against erasures during transport has been the subject of much study. [0019] In a system in which a single transmission is directed to more than one receiver, and in which different receivers experience widely different conditions, transmissions must be configured for the worst conditions between the transmitter and any receiver, i.e., it must be assumed that some receivers will not receive the transmission reliably. [0020] Erasure codes are known which provide excellent recovery of lost packets in such scenarios. For example, Reed-Solomon codes are well known and can be adapted to this purpose. However, a known disadvantage of Reed-Solomon codes is their relatively high computational complexity. Chain reaction codes, including LT.TM. chain reaction codes and Raptor.TM. multi-stage chain reaction ("MSCR") codes, provide excellent recovery of lost packets, and are highly adaptable to varying channel conditions. See, for example, Luby I, which describes aspects of chain reaction codes, and Shokrollahi I, which describes aspects of multi-stage chain reaction codes. Herein, the term "chain reaction code" should be understood to include chain reaction codes or multi-stage chain reaction codes, unless otherwise indicated. [0021] As a general rule, erasure codes that are capable of correcting large amounts of lost data have a greater cost in terms of computational complexity, device hardware and software complexity, and/or memory requirements than those codes which are designed only for very limited levels of errors. In particular, as is well known, a simple parity code can be used to correct a single lost symbol among a group of any given size. The complexity of encoding and decoding such a code is very low. Interleaved parity codes are well known as a technique for correcting bursts of lost symbols that are shorter than or equal to the interleave depth. Such codes also have very low encoding and decoding complexity. Continue reading... Full patent description for Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems or other areas of interest. ### Previous Patent Application: Wireless communication using codeword encoded with high-rate code Next Patent Application: A method and apparatus of defect areas management Industry Class: Error detection/correction and fault detection/recovery ### FreshPatents.com Support Thank you for viewing the Code generator and decoder for communications systems operating using hybrid codes to allow for multiple efficient users of the communications systems patent info. IP-related news and info Results in 4.87614 seconds Other interesting Feshpatents.com categories: Accenture , Agouron Pharmaceuticals , Amgen , AT&T , Bausch & Lomb , Callaway Golf |
||
