ForwardErrorCorrection.pptVIP

Forward Error Correction Steven Marx CSC457 12/04/2001 Outline What is FEC? What is FEC? (2) Why FEC? Why FEC? (2) How is this possible? How is this possible? (2) How is this possible? (3) A Problem A Solution A Solution (2) Extension Fields Multiplication and Division Multiplication and Division (2) Multiplication and Division (3) Vandermonde Matrices Swarmcast - a real example Swarmcast (2) Other useful applications Conclusion * * What is FEC? Why do we need it? How does it work? Where is it used? Send k packets Reconstruct n packets Such that we can tolerate k-n losses Called an (n, k) FEC code Alternatives: ARQ (Automatic Repeat reQuest) requires feedback bad for multicast tolerance only suitable for some applications Advantages: sometimes no feedback channel necessary long delay path one-way transmission avoids multicast problems Disadvantages: computationally expensive requires over-transmission An easy example: (n, k) = (2, 3) FEC code transmitting two numbers: a and b Send three packets: 1. a 2. b 3. a + b Could be represented as matrix multiplication To encode: To decode, use subset of rows. More generally: y = Gx, where G is a “generator matrix” G is constructed in such a way that any subset of rows is linearly independent. A “systematic” generator matrix includes the identity matrix. a and b are 8-bit numbers a + b may require more bits loss of precision means loss of data Finite fields: field: we can add, subtract, multiply, and divide as with integers closed over these operations finite: finite number of elements Specific example: “prime field” or “Galois Field” - GF(p) elements 0 to p-1 modulo p arithmeticProblem: with the exception of p = 2, ?log(p)? log(p) bits required requires modulo operations q = pr elements with p prime, r 1 “extension field”, or GF(pr) elements can be considered polynomials of  degree r - 1 sum just sum modulo p extra simple with p = 2: exactly r bits needed sums and differences just XORs Exists an α whose powe