Раптор кодтары: Компьютерлік қателерді түзеу коды

error correction codes
In computer science, Raptor codes (rapid tornado; see Tornado codes) are the first known class of fountain codes with linear time encoding and decoding. They were invented by Amin Shokrollahi in 2000/2001 and were first published in 2004 as an extended abstract. Raptor codes are a significant theoretical and practical improvement over LT codes, which were the first practical class of fountain codes. Raptor codes, as with fountain codes in general, encode a given source block of data consisting of a number k of equal size source symbols into a potentially limitless sequence of encoding symbols such that reception of any k or more encoding symbols allows the source block to be recovered with some non zero probability. The probability that the source block can be recovered increases with the number of encoding symbols received above k becoming very close to 1, once the number of received encoding symbols is only very slightly larger than k. For example, with the latest generation of Raptor codes, the RaptorQ codes, the chance of decoding failure when k encoding symbols have been received is less than 1%, and the chance of decoding failure when k+2 encoding symbols have been received is less than one in a million. (See Recovery probability and overhead section below for more discussion on this.) A symbol can be any size, from a single byte to hundreds or thousands of bytes. Raptor codes may be systematic or non systematic. In the systematic case, the symbols of the original source block, i. e. the source symbols, are included within the set of encoding symbols. Some examples of a systematic Raptor code is the use by the 3rd Generation Partnership Project in mobile cellular wireless broadcasting and multicasting, and also by DVB H standards for IP datacast to handheld devices (see external links). The Raptor codes used in these standards is also defined in IETF RFC 5053. Online codes are an example of a non systematic fountain code.

The most advanced version of Raptor is the RaptorQ code defined in IETF RFC 6330. The RaptorQ code is a systematic code, can be implemented in a way to achieve linear time encoding and decoding performance, has near optimal recovery properties (see Recovery probability and overhead section below for more details), supports up to 56,403 source symbols, and can support an essentially unlimited number of encoding symbols. The RaptorQ code defined in IETF RFC 6330 is specified as a part of the Next Gen TV (ATSC 3.0) standard to enable high quality broadcast video streaming (robust mobile TV) and efficient and reliable broadcast file delivery (datacasting). In particular, the RaptorQ code is specified in A/331: Signaling, Delivery, Synchronization, and Error Protection within ATSC 3.0 (see List of ATSC standards for a list of the ATSC 3.0 standard parts). Next Gen TV (ATSC 3.0) goes well beyond traditional TV to provide a Broadcast internet enabling general data delivery services.

Raptor codes are formed by the concatenation of two codes. A fixed rate erasure code, usually with a fairly high rate, is applied as a 'pre code' or 'outer code'. This pre code may itself be a concatenation of multiple codes, for example in the code standardized by 3GPP a high density parity check code derived from the binary Gray sequence is concatenated with a simple regular low density parity check code. Another possibility would be a concatenation of a Hamming code with a low density parity check code. The inner code takes the result of the pre coding operation and generates a sequence of encoding symbols. The inner code is a form of LT codes. Each encoding symbol is the XOR of a pseudo randomly chosen set of symbols from the pre code output. The number of symbols which are XOR'ed together to form an output symbol is chosen pseudo randomly for each output symbol according to a specific probability distribution. This distribution, as well as the mechanism for generating pseudo random numbers for sampling this distribution and for choosing the symbols to be XOR'ed, must be known to both sender and receiver. In one approach, each symbol is accompanied with an identifier which can be used as a seed to a pseudo random number generator to generate this information, with the same process being followed by both sender and receiver. In the case of non systematic Raptor codes, the source data to be encoded is used as the input to the pre coding stage. In the case of systematic Raptor codes, the input to the pre coding stage is obtained by first applying the inverse of the encoding operation that generates the first k output symbols to the source data. Thus, applying the normal encoding operation to the resulting symbols causes the original source symbols to be regenerated as the first k output symbols of the code. It is necessary to ensure that the pseudo random
processes which generate the first k output symbols generate an operation which is invertible.

Two approaches are possible for decoding Raptor codes. In a concatenated approach, the inner code is decoded first, using a belief propagation algorithm, as used for the LT codes. Decoding succeeds if this operation recovers a sufficient number of symbols, such that the outer code can recover the remaining symbols using the decoding algorithm appropriate for that code. In a combined approach, the relationships between symbols defined by both the inner and outer codes are considered as a single combined set of simultaneous equations which can be solved by the usual means, typically by Gaussian elimination.

Raptor codes require O(symbol size) time to generate an encoding symbol from a source block, and require O(source block size) time to recover a source block from at least k encoding symbols.

Qualcomm, Inc. has published an IPR statement for the Raptor code specified in IETF RFC 5053, and an IPR statement for the more advanced RaptorQ code specified in IETF RFC 6330. These statements mirror the licensing commitment Qualcomm, Inc. has made with respect to the
MPEG DASH standard. The MPEG DASH standard has been deployed by a wide variety of companies, including DASH Industry Forum member companies.