CS144 7-4 FEC and Reed-Solomon

Introduction to Computer Networking, Stanford University
https://lagunita.stanford.edu/courses/Engineering/Networking-SP/SelfPaced/about

Unit 7: Lower Layers 중 FEC and Reed-Solomon 파트 수업 필기 정리

---

FEC

Forward Error Correction 

SNR / BER Curves

• when given a modulation scheme and SNR, you can compute expected BER(Bit Error Rate)
• BER can become low but never reaches zero!
• directly turning Link Layer Bits into Physical Layer Bits is really inefficient, far below Shannon limit

Coding

• add a redundancy to make up for expected bit errors
• coding gain: ratio of bits at link layer to bits at physical layer
  • 1/2 code: each link layer bit is 2 physical layer
• This concept is Forward Error Correction(FEC)
  • proactively adding some additional data(redundancy) so recipient can correct potential errors
  • so you can save the cost of message changes

Algorithms for Coding

• many algorithms with different tradeoffs: Hamming Codes, Convolutional Codes, LT Codes, LDPC, Turbo Codes, Tornado Codes, Raptor Codes..

Reed-Solomon Error Correction

• VEEERY commonly used coding algorithm: e.g. CDs, DVDs, DSL, WiMax, RAID6 storage...
• Mathematically simple (compared to some others)

Basic Idea

1. Take k chunks of data
2. represent the data as coefficients of a polynomial
3. compute points along the polynomial, then send those points
4. then recipient reconstitute the coefficients

Downsides

• points must be in a finite filed (so limited number of bits)

Details

• Two kinds of errors: Erasure: erased values, location of error is known Errors: bit error, location of error is unknown
• Take k chunks of data, code into n chunks (n ≥ k)
• Reed-Solomon can correct up erasures and errors: (255,223)→ (n-k) Erasures, (n-k)/2 Errors
  e.g. R(255,223) this can correct up to 255-223 = 32 Erasures / 32/2 = 16 Errors

This isn't what's done in practice today, too complex to decode, need for the math to work ... but it gives you the basic idea

used when when encoding and decoding packet data

Interleaving

• A (n+k, n) Reed-Solomon code protects against k erasures or k/2 errors
• but Physical media often have burst errors, so Reed-Solomon protection could be not enough
• with Interleaving we can encode data more robust
  e.g. when sending A₀ ~ A₂₀, B₀ ~ B₂₀, ... L₀ ~ L₂₀ sending it using interleaving A₀B₀..L₀, A₁B₁C₁..L₁, ...
  → so that Reed-Solomon protection could cover more Bit Errors