RFC 6330
RaptorQ Forward Error Correction Scheme for Object Delivery
5.7. Operating with Octets, Symbols, and Matrices
5.7.1. General
The remainder of this section describes the arithmetic operations that are used to generate encoding symbols from source symbols and to generate source symbols from encoding symbols. Mathematically, octets can be thought of as elements of a finite field, i.e., the finite field GF(256) with 256 elements, and thus the addition and multiplication operations and identity elements and inverses over both operations are defined. Matrix operations and symbol operations are defined based on the arithmetic operations on octets. This allows a full implementation of these arithmetic operations without having to understand the underlying mathematics of finite fields.5.7.2. Arithmetic Operations on Octets
Octets are mapped to non-negative integers in the range 0 through 255 in the usual way: A single octet of data from a symbol, B[7],B[6],B[5],B[4],B[3],B[2],B[1],B[0], where B[7] is the highest order bit and B[0] is the lowest order bit, is mapped to the integer i=B[7]*128+B[6]*64+B[5]*32+B[4]*16+B[3]*8+B[2]*4+B[1]*2+B[0]. The addition of two octets u and v is defined as the exclusive-or operation, i.e., u + v = u ^ v. Subtraction is defined in the same way, so we also have u - v = u ^ v.
The zero element (additive identity) is the octet represented by the
integer 0. The additive inverse of u is simply u, i.e.,
u + u = 0.
The multiplication of two octets is defined with the help of two
tables OCT_EXP and OCT_LOG, which are given in Section 5.7.3 and
Section 5.7.4, respectively. The table OCT_LOG maps octets (other
than the zero element) to non-negative integers, and OCT_EXP maps
non-negative integers to octets. For two octets u and v, we define
u * v =
0, if either u or v are 0,
OCT_EXP[OCT_LOG[u] + OCT_LOG[v]] otherwise.
Note that the '+' on the right-hand side of the above is the usual
integer addition, since its arguments are ordinary integers.
The division u / v of two octets u and v, and where v != 0, is
defined as follows:
u / v =
0, if u == 0,
OCT_EXP[OCT_LOG[u] - OCT_LOG[v] + 255] otherwise.
The one element (multiplicative identity) is the octet represented by
the integer 1. For an octet u that is not the zero element, i.e.,
the multiplicative inverse of u is
OCT_EXP[255 - OCT_LOG[u]].
The octet denoted by alpha is the octet with the integer
representation 2. If i is a non-negative integer 0 <= i < 256, we
have
alpha^^i = OCT_EXP[i].
5.7.3. The Table OCT_EXP
The table OCT_EXP contains 510 octets. The indexing starts at 0 and
ranges to 509, and the entries are the octets with the following
positive integer representation:
1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 1425.7.4. The Table OCT_LOG
The table OCT_LOG contains 255 non-negative integers. The table is indexed by octets interpreted as integers. The octet corresponding to the zero element, which is represented by the integer 0, is excluded as an index, and thus indexing starts at 1 and ranges up to 255, and the entries are the following: 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100, 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114,
166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145, 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92, 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40, 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212, 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103, 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171, 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203, 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80, 88, 1755.7.5. Operations on Symbols
Operations on symbols have the same semantics as operations on vectors of octets of length T in this specification. Thus, if U and V are two symbols formed by the octets u[0], ..., u[T-1] and v[0], ..., v[T-1], respectively, the sum of symbols U + V is defined to be the component-wise sum of octets, i.e., equal to the symbol D formed by the octets d[0], ..., d[T-1], such that d[i] = u[i] + v[i], 0 <= i < T. Furthermore, if beta is an octet, the product beta*U is defined to be the symbol D obtained by multiplying each octet of U by beta, i.e., d[i] = beta*u[i], 0 <= i < T.5.7.6. Operations on Matrices
All matrices in this specification have entries that are octets, and thus matrix operations and definitions are defined in terms of the underlying octet arithmetic, e.g., operations on a matrix, matrix rank, and matrix inversion.5.8. Requirements for a Compliant Decoder
If a RaptorQ-compliant decoder receives a mathematically sufficient set of encoding symbols generated according to the encoder specification in Section 5.3 for reconstruction of a source block, then such a decoder SHOULD recover the entire source block. A RaptorQ-compliant decoder SHALL have the following recovery properties for source blocks with K' source symbols for all values of K' in Table 2 of Section 5.6.
1. If the decoder receives K' encoding symbols generated according
to the encoder specification in Section 5.3 with corresponding
ESIs chosen independently and uniformly at random from the range
of possible ESIs, then on average the decoder will fail to
recover the entire source block at most 1 out of 100 times.
2. If the decoder receives K'+1 encoding symbols generated according
to the encoder specification in Section 5.3 with corresponding
ESIs chosen independently and uniformly at random from the range
of possible ESIs, then on average the decoder will fail to
recover the entire source block at most 1 out of 10,000 times.
3. If the decoder receives K'+2 encoding symbols generated according
to the encoder specification in Section 5.3 with corresponding
ESIs chosen independently and uniformly at random from the range
of possible ESIs, then on average the decoder will fail to
recover the entire source block at most 1 out of 1,000,000 times.
Note that the Example FEC Decoder specified in Section 5.4 fulfills
both requirements, i.e.,
1. it can reconstruct a source block as long as it receives a
mathematically sufficient set of encoding symbols generated
according to the encoder specification in Section 5.3, and
2. it fulfills the mandatory recovery properties from above.
6. Security Considerations
Data delivery can be subject to denial-of-service attacks by
attackers that send corrupted packets that are accepted as legitimate
by receivers. This is particularly a concern for multicast delivery
because a corrupted packet may be injected into the session close to
the root of the multicast tree, in which case the corrupted packet
will arrive at many receivers. The use of even one corrupted packet
containing encoding data may result in the decoding of an object that
is completely corrupted and unusable. It is thus RECOMMENDED that
source authentication and integrity checking are applied to decoded
objects before delivering objects to an application. For example, a
SHA-256 hash [FIPS.180-3.2008] of an object may be appended before
transmission, and the SHA-256 hash is computed and checked after the
object is decoded but before it is delivered to an application.
Source authentication SHOULD be provided, for example, by including a
digital signature verifiable by the receiver computed on top of the
hash value. It is also RECOMMENDED that a packet authentication
protocol such as TESLA [RFC4082] be used to detect and discard
corrupted packets upon arrival. This method may also be used to
provide source authentication. Furthermore, it is RECOMMENDED that
Reverse Path Forwarding checks be enabled in all network routers and switches along the path from the sender to receivers to limit the possibility of a bad agent successfully injecting a corrupted packet into the multicast tree data path. Another security concern is that some FEC information may be obtained by receivers out-of-band in a session description, and if the session description is forged or corrupted, then the receivers will not use the correct protocol for decoding content from received packets. To avoid these problems, it is RECOMMENDED that measures be taken to prevent receivers from accepting incorrect session descriptions, e.g., by using source authentication to ensure that receivers only accept legitimate session descriptions from authorized senders.7. IANA Considerations
Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA registration. For general guidelines on IANA considerations as they apply to this document, see [RFC5052]. IANA has assigned the value 6 under the ietf:rmt:fec:encoding registry to "RaptorQ Code" as the Fully-Specified FEC Encoding ID value associated with this specification.8. Acknowledgements
Thanks are due to Ranganathan (Ranga) Krishnan. Ranga Krishnan has been very supportive in finding and resolving implementation details and in finding the systematic indices. In addition, Habeeb Mohiuddin Mohammed and Antonios Pitarokoilis, both from the Munich University of Technology (TUM), and Alan Shinsato have done two independent implementations of the RaptorQ encoder/decoder that have helped to clarify and to resolve issues with this specification.9. References
9.1. Normative References
[FIPS.180-3.2008] National Institute of Standards and Technology, "Secure Hash Standard", FIPS PUB 180-3, October 2008. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC4082] Perrig, A., Song, D., Canetti, R., Tygar, J., and B. Briscoe, "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): Multicast Source Authentication Transform Introduction", RFC 4082, June 2005.
[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error Correction (FEC) Building Block", RFC 5052, August 2007.9.2. Informative References
[LTCodes] Luby, M., "LT codes", Annual IEEE Symposium on Foundations of Computer Science, pp. 271-280, November 2002. [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and J. Crowcroft, "The Use of Forward Error Correction (FEC) in Reliable Multicast", RFC 3453, December 2002. [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, "Raptor Forward Error Correction Scheme for Object Delivery", RFC 5053, October 2007. [RaptorCodes] Shokrollahi, A. and M. Luby, "Raptor Codes", Foundations and Trends in Communications and Information Theory: Vol. 6: No. 3-4, pp. 213-322, 2011.
Authors' Addresses
Michael Luby Qualcomm Incorporated 3165 Kifer Road Santa Clara, CA 95051 U.S.A. EMail: luby@qualcomm.com Amin Shokrollahi EPFL Laboratoire d'algorithmique Station 14 Batiment BC Lausanne 1015 Switzerland EMail: amin.shokrollahi@epfl.ch Mark Watson Netflix Inc. 100 Winchester Circle Los Gatos, CA 95032 U.S.A. EMail: watsonm@netflix.com Thomas Stockhammer Nomor Research Brecherspitzstrasse 8 Munich 81541 Germany EMail: stockhammer@nomor.de Lorenz Minder Qualcomm Incorporated 3165 Kifer Road Santa Clara, CA 95051 U.S.A. EMail: lminder@qualcomm.com