0
# Error Correction Codes
1

2
Forward error correction implementations including BCH (Bose-Chaudhuri-Hocquenghem) and Reed-Solomon codes. These codes provide robust error detection and correction capabilities for digital communications and data storage systems.
3

4
## Capabilities
5

6
### BCH Codes
7

8
BCH codes are cyclic linear block codes that can correct multiple random errors. They are particularly useful for correcting random errors in digital communications.
9

10
```python { .api }
11
class BCH:
12
    """
13
    A general BCH(n, k) code over GF(q).
14
    
15
    BCH codes are [n, k, d]_q linear block codes with codeword size n,
16
    message size k, minimum distance d, and symbols from alphabet of size q.
17
    """
18
    
19
    def __init__(self, n, k, c=1, extension_field=None, primitive_poly=None, primitive_element=None, systematic=True):
20
        """
21
        Construct BCH(n, k) code.
22
        
23
        Parameters:
24
        - n (int): Codeword size (must divide q^m - 1)
25
        - k (int): Message size  
26
        - c (int): First consecutive root, default 1
27
        - extension_field: Extension field for code construction
28
        - primitive_poly: Primitive polynomial for extension field
29
        - primitive_element: Primitive element for extension field
30
        - systematic (bool): Whether to use systematic encoding, default True
31
        """
32
    
33
    # Properties
34
    @property
35
    def field(self) -> type:
36
        """The Galois field the code is defined over."""
37
    
38
    @property
39
    def n(self) -> int:
40
        """The codeword size."""
41
    
42
    @property
43
    def k(self) -> int:
44
        """The message size."""
45
    
46
    @property
47
    def d(self) -> int:
48
        """The minimum distance."""
49
    
50
    @property
51
    def t(self) -> int:
52
        """The error correcting capability."""
53
    
54
    @property
55
    def generator_poly(self) -> Poly:
56
        """The generator polynomial g(x)."""
57
    
58
    @property
59
    def parity_check_poly(self) -> Poly:
60
        """The parity check polynomial h(x)."""
61
    
62
    @property
63
    def G(self) -> FieldArray:
64
        """The generator matrix G."""
65
    
66
    @property
67
    def H(self) -> FieldArray:
68
        """The parity check matrix H."""
69
    
70
    @property
71
    def is_systematic(self) -> bool:
72
        """Whether the code is systematic."""
73
    
74
    # Encoding and decoding
75
    def encode(self, message, parity_only=False):
76
        """
77
        Encode message into codeword.
78
        
79
        Parameters:
80
        - message: Message array of length k (or multiple messages)
81
        - parity_only (bool): Return only parity symbols if True
82
        
83
        Returns:
84
        FieldArray: Encoded codeword(s) of length n (or n-k if parity_only=True)
85
        """
86
    
87
    def decode(self, codeword, errors=False, output="message"):
88
        """
89
        Decode received codeword.
90
        
91
        Parameters:
92
        - codeword: Received codeword array of length n (or multiple codewords)
93
        - errors (bool): Return number of corrected errors if True
94
        - output (str): Output format - "message", "codeword", or "both"
95
        
96
        Returns:
97
        FieldArray or tuple: Decoded message/codeword, optionally with error count
98
        """
99
    
100
    def detect(self, codeword):
101
        """
102
        Detect errors in received codeword without correction.
103
        
104
        Parameters:
105
        - codeword: Received codeword array of length n
106
        
107
        Returns:
108
        bool or np.ndarray: True if errors detected, False otherwise
109
        """
110
```
111

112
### Reed-Solomon Codes
113

114
Reed-Solomon codes are a subset of BCH codes that achieve the Singleton bound and are optimal for correcting burst errors. They are widely used in digital communications, data storage, and QR codes.
115

116
```python { .api }
117
class ReedSolomon:
118
    """
119
    A general RS(n, k) code over GF(q).
120
    
121
    Reed-Solomon codes are [n, k, n-k+1]_q linear block codes with
122
    maximum distance separable property.
123
    """
124
    
125
    def __init__(self, n, k, c=1, field=None, primitive_poly=None, primitive_element=None, systematic=True):
126
        """
127
        Construct RS(n, k) code.
128
        
129
        Parameters:
130
        - n (int): Codeword size (must be ≤ field order)
131
        - k (int): Message size
132
        - c (int): First consecutive root, default 1  
133
        - field: Galois field for the code, auto-selected if None
134
        - primitive_poly: Primitive polynomial for field construction
135
        - primitive_element: Primitive element for field construction
136
        - systematic (bool): Whether to use systematic encoding, default True
137
        """
138
    
139
    # Properties (same as BCH)
140
    @property
141
    def field(self) -> type:
142
        """The Galois field the code is defined over."""
143
    
144
    @property
145
    def n(self) -> int:
146
        """The codeword size."""
147
    
148
    @property
149
    def k(self) -> int:
150
        """The message size.""" 
151
    
152
    @property
153
    def d(self) -> int:
154
        """The minimum distance (equals n-k+1)."""
155
    
156
    @property
157
    def t(self) -> int:
158
        """The error correcting capability (equals floor((d-1)/2))."""
159
    
160
    @property
161
    def generator_poly(self) -> Poly:
162
        """The generator polynomial g(x)."""
163
    
164
    @property
165
    def parity_check_poly(self) -> Poly:
166
        """The parity check polynomial h(x)."""
167
    
168
    @property
169
    def G(self) -> FieldArray:
170
        """The generator matrix G."""
171
    
172
    @property
173
    def H(self) -> FieldArray:
174
        """The parity check matrix H."""
175
    
176
    @property
177
    def is_systematic(self) -> bool:
178
        """Whether the code is systematic."""
179
    
180
    # Encoding and decoding (same interface as BCH)
181
    def encode(self, message, parity_only=False):
182
        """
183
        Encode message into codeword.
184
        
185
        Parameters:
186
        - message: Message array of length k (or multiple messages)
187
        - parity_only (bool): Return only parity symbols if True
188
        
189
        Returns:
190
        FieldArray: Encoded codeword(s) of length n (or n-k if parity_only=True)
191
        """
192
    
193
    def decode(self, codeword, errors=False, output="message"):
194
        """
195
        Decode received codeword with error correction.
196
        
197
        Parameters:
198
        - codeword: Received codeword array of length n (or multiple codewords)
199
        - errors (bool): Return number of corrected errors if True
200
        - output (str): Output format - "message", "codeword", or "both"
201
        
202
        Returns:
203
        FieldArray or tuple: Decoded message/codeword, optionally with error count
204
        """
205
    
206
    def detect(self, codeword):
207
        """
208
        Detect errors in received codeword without correction.
209
        
210
        Parameters:
211
        - codeword: Received codeword array of length n
212
        
213
        Returns:
214
        bool or np.ndarray: True if errors detected, False otherwise
215
        """
216
```
217

218
## Usage Examples
219

220
### Basic BCH Code Usage
221

222
```python
223
import galois
224
import numpy as np
225

226
# Create BCH(15, 7) code over GF(2)
227
bch = galois.BCH(15, 7)
228
print(f"BCH code: {bch}")
229
print(f"Field: {bch.field.name}")
230
print(f"Parameters: n={bch.n}, k={bch.k}, d={bch.d}, t={bch.t}")
231

232
# Get field for creating messages
233
GF = bch.field
234

235
# Encode a message
236
message = GF([1, 0, 1, 1, 0, 1, 0])  # k=7 bits
237
codeword = bch.encode(message)
238
print(f"Message: {message}")
239
print(f"Codeword: {codeword}")
240

241
# Add errors to codeword
242
received = codeword.copy()
243
received[0] ^= 1  # Flip first bit
244
received[5] ^= 1  # Flip sixth bit
245
print(f"Received (with 2 errors): {received}")
246

247
# Decode with error correction
248
decoded_msg, num_errors = bch.decode(received, errors=True)
249
print(f"Decoded message: {decoded_msg}")
250
print(f"Number of corrected errors: {num_errors}")
251
print(f"Decoding successful: {np.array_equal(decoded_msg, message)}")
252
```
253

254
### Reed-Solomon Code Usage
255

256
```python
257
import galois
258
import numpy as np
259

260
# Create RS(255, 223) code (commonly used in telecommunications)
261
rs = galois.ReedSolomon(255, 223)
262
print(f"Reed-Solomon code: {rs}")
263
print(f"Field: {rs.field.name}")
264
print(f"Parameters: n={rs.n}, k={rs.k}, d={rs.d}, t={rs.t}")
265

266
# Get field for creating messages
267
GF = rs.field
268

269
# Encode a message
270
message = GF.Random(rs.k)  # Random k-symbol message
271
codeword = rs.encode(message)
272
print(f"Message length: {len(message)}")
273
print(f"Codeword length: {len(codeword)}")
274

275
# Simulate burst errors
276
received = codeword.copy()
277
error_positions = [10, 11, 12, 13, 14]  # 5 consecutive errors
278
for pos in error_positions:
279
    received[pos] = GF.Random()  # Random error
280

281
print(f"Added {len(error_positions)} errors at positions {error_positions}")
282

283
# Decode with error correction
284
try:
285
    decoded_msg, num_errors = rs.decode(received, errors=True)
286
    print(f"Number of corrected errors: {num_errors}")
287
    print(f"Decoding successful: {np.array_equal(decoded_msg, message)}")
288
except Exception as e:
289
    print(f"Decoding failed: {e}")
290
```
291

292
### Shortened Codes
293

294
```python
295
import galois
296

297
# Create full RS(31, 21) code
298
rs_full = galois.ReedSolomon(31, 21)
299
print(f"Full code: {rs_full}")
300

301
# Use as shortened RS(25, 15) code
302
k_short = 15  # Shortened message length
303
n_short = 25  # Shortened codeword length
304

305
# Encode shortened message
306
GF = rs_full.field
307
message_short = GF.Random(k_short)
308
codeword_short = rs_full.encode(message_short)[:n_short]
309

310
print(f"Shortened message length: {len(message_short)}")
311
print(f"Shortened codeword length: {len(codeword_short)}")
312

313
# Decode shortened codeword
314
decoded_short = rs_full.decode(codeword_short)
315
print(f"Shortened decoding successful: {np.array_equal(decoded_short, message_short)}")
316
```
317

318
### Systematic vs Non-Systematic Encoding
319

320
```python
321
import galois
322

323
# Systematic encoding (default)
324
bch_sys = galois.BCH(15, 7, systematic=True)
325
message = galois.GF(2)([1, 0, 1, 1, 0, 1, 0])
326

327
# In systematic encoding, message appears unchanged in codeword
328
codeword_sys = bch_sys.encode(message)
329
print(f"Message: {message}")
330
print(f"Systematic codeword: {codeword_sys}")
331
print(f"Message part: {codeword_sys[:bch_sys.k]}")
332
print(f"Parity part: {codeword_sys[bch_sys.k:]}")
333

334
# Get only parity symbols
335
parity_only = bch_sys.encode(message, parity_only=True)
336
print(f"Parity symbols only: {parity_only}")
337
```
338

339
### Error Detection Only
340

341
```python
342
import galois
343

344
# Create RS code for error detection
345
rs = galois.ReedSolomon(31, 21)
346
GF = rs.field
347

348
# Encode message
349
message = GF.Random(rs.k)
350
codeword = rs.encode(message)
351

352
# Test error detection
353
clean_detected = rs.detect(codeword)
354
print(f"Clean codeword errors detected: {clean_detected}")
355

356
# Add errors
357
corrupted = codeword.copy()
358
corrupted[0] = GF.Random()
359
corrupted[10] = GF.Random()
360

361
errors_detected = rs.detect(corrupted)
362
print(f"Corrupted codeword errors detected: {errors_detected}")
363
```
364

365
### Batch Processing
366

367
```python
368
import galois
369

370
# Create RS code
371
rs = galois.ReedSolomon(15, 9)
372
GF = rs.field
373

374
# Encode multiple messages at once
375
messages = GF.Random((5, rs.k))  # 5 messages
376
codewords = rs.encode(messages)  # Batch encoding
377

378
print(f"Batch encoded {messages.shape[0]} messages")
379
print(f"Messages shape: {messages.shape}")
380
print(f"Codewords shape: {codewords.shape}")
381

382
# Add errors to all codewords
383
corrupted = codewords.copy()
384
corrupted[:, 0] = GF.Random(5)  # Error in first position of each codeword
385

386
# Batch decode
387
decoded_messages, error_counts = rs.decode(corrupted, errors=True)
388
print(f"Decoded messages shape: {decoded_messages.shape}")
389
print(f"Error counts: {error_counts}")
390
print(f"All decoded correctly: {np.array_equal(decoded_messages, messages)}")
391
```
392

393
## Performance and Implementation Notes
394

395
- **Algorithmic Efficiency**: Uses efficient syndrome-based decoding algorithms
396
- **Memory Optimization**: Systematic encoding reduces storage requirements
397
- **Batch Processing**: Supports vectorized encoding/decoding of multiple messages
398
- **Field Integration**: Seamlessly works with any finite field created by GF()
399
- **Error Bounds**: BCH codes can correct up to t errors, RS codes achieve maximum distance separable bound
400
- **Shortened Codes**: Support for shortened codes without reconstructing the full code