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: d_min = 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.

Further Reading

1. Galois Field

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

p(x) = x³ + x + 1
α³ = α + 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	α²

m = [α⁴, α⁶, 1, α, α, α⁴, α², α²]

---

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

m(x) = α⁴ + α⁶x + 1x²

4.3 Generator Polynomial

g(x) = (x − α)(x − α²)(x − α³)(x − α⁴)

4.4 Encoding Rule

x⁴m(x) = q(x)g(x) + r(x)
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

Sᵢ = r(αⁱ),   i = 1,2,3,4

8.2 Error Locator Polynomial

Λ(x) = 1 + λ₁x + λ₂x²

8.3 Chien Search

Λ(α⁻ʲ) = 0

8.4 Error Magnitude (Forney)

eⱼ = −Ω(α⁻ʲ) / Λ′(α⁻ʲ)

8.5 Error Correction

cⱼ = rⱼ − eⱼ

---

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

Bits → GF(2³) symbols → RS encoding → Wireless channel → RS decoding → GF(2³) symbols → Bits

---

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