A Python implementation of syndrome decoding for error detection and correction in communication channels. This library provides tools to create, encode, and decode linear codes with a focus on ASCII text transmission.
Linear codes are a fundamental error correction technique in coding theory. They work by adding redundant bits to messages in a mathematically structured way, allowing detection and correction of transmission errors.
Key concepts:
-
Generator Matrix (G): Transforms k-bit messages into n-bit codewords
- G is a k×n matrix where k is message length and n is codeword length
- Encoded message: m × G = c (where m is the message and c is the codeword)
-
Parity Check Matrix (H): Used for error detection
- H is an (n-k)×n matrix
- For valid codewords: c × H^T = 0
- When errors occur: c × H^T = syndrome
-
Syndrome Decoding:
- Syndrome = received_word × H^T
- Non-zero syndrome indicates errors
- Syndrome pattern uniquely identifies error location
- Lookup syndrome in pre-computed table to find error pattern
- Message encoding: c = m × G
- Transmission through noisy channel: c → r (received word)
- Syndrome computation: s = r × H^T
- Error pattern lookup: e = syndrome_table[s]
- Error correction: m = r - e
git clone https://github.com/AmeanAsad/Syndrome-Error-Decoding.git cd Syndrome-Error-Correction pip install -r requirements.txt
Sample simulation results with 500 words, 10 trials, comparing different code parameters
from linear_code import LinearCode # Create a (12,8) linear code code = LinearCode(k=8, n=12) # Get encoding matrices G = code.get_generator_matrix() H = code.get_parity_check_matrix() syndrome_table = code.get_syndrome_decoding_table() # Example: Encode a message message = np.array([1, 0, 1, 1, 0, 1, 0, 1]) encoded = np.matmul(message, G) % 2 # Binary arithmeticfrom ascii_code import AsciiCode # Initialize ASCII encoder/decoder ascii_code = AsciiCode(k=8, n=12) # Encode and decode a single character text = "A" # Get binary representation binary = ascii_code.ascii_to_bin[text] # Simulate transmission error received = ascii_code.simulate_channel_noise(binary, error_rate=0.1) decoded = ascii_code.decode_letter(received) print(f"Original: {text}, Decoded: {decoded}") # Process entire string def process_text(text, ascii_code): decoded_text = "" for char in text: binary = ascii_code.ascii_to_bin[char] encoded = ascii_code.encode_letter(binary) received = ascii_code.simulate_channel_noise(encoded, error_rate=0.1) decoded_char = ascii_code.decode_letter(received) decoded_text += decoded_char return decoded_textfrom decoding_simulation import visualization # Basic simulation visualization(word_limit=100, num_trials=5) # Detailed simulation with custom parameters visualization( word_limit=500, num_trials=10, error_rate=0.125, # 12.5% bit error rate code_parameters=[(8,12), (8,14), (8,16)] # Compare different code sizes )- Implements core mathematical operations
- Generates systematic form of generator matrix
- Computes parity check matrix
- Builds syndrome lookup table
- Handles text-specific encoding/decoding
- Maps ASCII characters to binary vectors
- Implements syndrome decoding for error correction
- Maintains codeword dictionary
- Encoding: O(k×n) per character
- Syndrome computation: O(n×(n-k))
- Decoding table lookup: O(1)
- Total processing: O(n²) per character
from linear_code import LinearCode # Define custom error patterns for testing error_patterns = [ [1,0,0,0,0,0,0,0], # Single bit error [1,1,0,0,0,0,0,0], # Double bit error [1,1,1,0,0,0,0,0], # Triple bit error ] code = LinearCode(k=8, n=12) for pattern in error_patterns: corrected = code.correct_errors(pattern) print(f"Error pattern: {pattern}") print(f"Corrected: {corrected}\n")from ascii_code import AsciiCode import random import string # Track correction success rate success_count = 0 total_trials = 1000 ascii_code = AsciiCode(k=8, n=12) for _ in range(total_trials): original = random.choice(string.ascii_letters) binary = ascii_code.ascii_to_bin[original] encoded = ascii_code.encode_letter(binary) received = ascii_code.simulate_channel_noise(encoded, error_rate=0.1) decoded = ascii_code.decode_letter(received) if decoded == original: success_count += 1 success_rate = success_count / total_trials print(f"Success rate: {success_rate:.2%}")- Currently limited to binary linear codes
- Single error correction guaranteed
- Future improvements:
- Reed-Solomon code implementation
- Burst error handling
- Soft-decision decoding
- Variable code rate support
Contributions welcome! Areas of interest:
- Additional encoding schemes
- Performance optimizations
- Extended error pattern support
- Documentation improvements
This project is licensed under the MIT License.