Reed–Solomon Coding and Decoding
1. Input Bitstream to Symbols
Given input bitstream:
101011000…
Choose symbol size:
m = 3 ⇒ symbols in GF(2³)
Grouping bits:
101 | 011 | 000
Binary to decimal symbols:
[5, 3, 0]
2. Finite Field Construction GF(2³)
Primitive polynomial:
p(x) = x³ + x + 1
| Element | Polynomial | Binary | Decimal |
|---|---|---|---|
| α⁰ | 1 | 001 | 1 |
| α¹ | α | 010 | 2 |
| α² | α² | 100 | 4 |
| α³ | α + 1 | 011 | 3 |
| α⁴ | α² + α | 110 | 6 |
| α⁵ | α² + α + 1 | 111 | 7 |
| α⁶ | α² + 1 | 101 | 5 |
3. Message Polynomial
Choose RS(7,3):
n = 7, k = 3
Message symbols:
[5, 3, 0]
Message polynomial:
m(x) = 5 + 3x + 0x²
4. Generator Polynomial
Number of parity symbols:
n − k = 4
Generator polynomial:
g(x) = (x − α)(x − α²)(x − α³)(x − α⁴)
Expanded form:
g(x) = x⁴ + 6x³ + x² + 6x + 1
5. RS Encoding (Polynomial Division)
Multiply message by x⁴:
x⁴m(x) = 5x⁴ + 3x⁵
Divide by generator polynomial:
r(x) = 6 + 4x + 2x² + 5x³
Codeword polynomial:
c(x) = x⁴m(x) + r(x)
Final codeword symbols:
[6, 4, 2, 5, 5, 3, 0]
6. Modulation Output (Bitstream)
| Symbol | Binary |
|---|---|
| 6 | 110 |
| 4 | 100 |
| 2 | 010 |
| 5 | 101 |
| 5 | 101 |
| 3 | 011 |
| 0 | 000 |
Encoded bitstream:
110100010101101011000
Reed–Solomon Demodulation (Decoding Process)
7. Received Polynomial
Assume received symbols:
r(x) = c(x) + e(x)
where e(x) represents symbol errors.
8. Syndrome Computation
Syndromes:
S_i = r(α^i), i = 1, 2, 3, 4
If all syndromes are zero → no errors.
9. Error Locator Polynomial
Using Berlekamp–Massey algorithm:
Λ(x) = 1 + Λ₁x + Λ₂x²
Degree of Λ(x) gives number of symbol errors.
10. Error Position Detection
Chien search:
Λ(α^{-i}) = 0 ⇒ error at position i
11. Error Magnitude Calculation
Forney’s formula:
e_i = - \frac{Ω(α^{-i})}{Λ'(α^{-i})}
Correct the received symbols:
c_i = r_i − e_i
12. Output Data
Extract original message:
[5, 3, 0] ⇒ 101 | 011 | 000
Recovered bitstream:
101011000
Properties
- Minimum distance: dmin = n − k + 1
- Error correction: t = (n − k)/2
- Maximum Distance Separable (MDS)
Summary
- Bit stream is converted to **symbols** in GF(2^m) for RS encoding.
- RS codes correct symbol errors, which may include **multiple bit errors in one symbol**.
- Decoding is necessary to recover the original bit stream.
- Mapping back from symbols to bits completes the process.
RS coding is especially effective for burst errors and is widely used in optical and underwater laser communication systems.
Try Interactive Online Simulator for
Further Reading
End-to-End Wireless Communication Using GF(2³) and Reed–Solomon Coding
This document presents a complete bit-by-bit mathematical walkthrough of a wireless communication system using:
- Galois Field GF(2³)
- Reed–Solomon coding
- A noisy wireless channel
1. Source Bitstream
11010100101001011010010...
2. Definition of GF(2³)
2.1 Primitive Polynomial
α³ = α + 1
2.2 Field Elements
| GF Element | Binary |
|---|---|
| 0 | 000 |
| 1 | 001 |
| α | 010 |
| α² | 100 |
| α³ | 011 |
| α⁴ | 110 |
| α⁵ | 111 |
| α⁶ | 101 |
3. Bitstream to GF(2³) Symbols
3.1 Group Bits
110 101 001 010 010 110 100 100
3.2 Map to GF Symbols
| Bits | GF Symbol |
|---|---|
| 110 | α⁴ |
| 101 | α⁶ |
| 001 | 1 |
| 010 | α |
| 010 | α |
| 110 | α⁴ |
| 100 | α² |
| 100 | α² |
4. Reed–Solomon Encoding
4.1 RS Code Parameters
- RS(7, 3) over GF(2³)
- Data symbols k = 3
- Parity symbols = 4
- Error correction capability = 2 symbols
4.2 Message Polynomial
4.3 Generator Polynomial
4.4 Encoding Rule
c(x) = x⁴m(x) − r(x)
The resulting RS codeword contains 7 GF symbols.
5. RS Symbols to Transmitted Bits
Each GF symbol is converted back to its 3-bit representation and transmitted.
110 010 001 111 100 010 101
6. Wireless Channel
Noise causes bit errors during transmission.
Example
Transmitted: 110 010 001 111 100 010 101 Received: 110 010 001 101 100 010 101
7. Receiver: Bits to GF Symbols
| Bits | GF Symbol |
|---|---|
| 110 | α⁴ |
| 010 | α |
| 001 | 1 |
| 101 | α⁶ (error) |
| 100 | α² |
| 010 | α |
| 101 | α⁶ |
8. Reed–Solomon Decoding
8.1 Syndrome Calculation
8.2 Error Locator Polynomial
8.3 Chien Search
8.4 Error Magnitude (Forney)
8.5 Error Correction
9. Recover Original Bits
Extract the first 3 corrected symbols and map back to bits:
110101001
This matches the original transmitted data.
10. End-to-End Flow
11. Key Takeaways
- You always transmit bits, never α directly
- GF(2³) provides symbol-level arithmetic
- Reed–Solomon adds redundancy for error correction
- Wireless noise causes bit errors, RS corrects symbol errors