Algoritmo Reed Solomon

 Sto progettando una trasmissione radio di immagini ed uno dei vincoli e' che non e' garantita la perfetta qualita' della trasmissione con previsione di errori nella fase aerea e cercado una soluzione mi sono imbattuto nell'algoritmo Reed Solomon che peraltro ha una storia affascinante che riguarda le sonde Voyager 

In pratica quando Voyager hanno  superato Saturno il segnale era diventato cosi' debole che anche una ridondanza del 100% non permetteva di ricevere in modo affidabile. Quindi da terra i computer di bordo sono stati riprogrammati per utilizzare una codifica a correzione di errore Reed Solomon...questo algoritmo e' anche alla base della correzione degli errori nella lettura delle tracce dei CD audio rigati

 A differenza di CRC algoritmo che individua se il dato e' corrotto o meno ma non dice come riparare il flusso di dati, Reed Solomon e' un algoritmo FEC  (Forward Error Correction) che permette di correggere i bit errati dove presenti 

Reed Solomon permette di correggere uno o piu' errore in un pacchetto dati usando dati aggiuntivi di controllo (tipicamente in un pacchetto di 255 bytes 223 bytes sono del messaggio ed i rimanenti coefficienti per l'algoritmo  si possono correggere fino a 11 bytes trasmessi erroneamente.

 Questo un video sulla spiegazione dal punto di vista matematico del funzionamento

 https://www.youtube.com/watch?v=fBRMaEAFLE0

Il programma sottostante, usando una libreria Python, prende una immagine jpeg, la codifica con Reed Solomon, introduce degli errori e poi la ricostruisce. Visto che si tratta di un jpg e quindi compresso l'immagine con gli errori casuali non risultera' leggibile da un comune programma di gestione immagini

import reedsolo as rs

import random

# 1. Setup

n, k = 255, 223

codec = rs.RSCodec(n - k)

with open("image.jpg", "rb") as f:

    original_data = f.read()

# 2. Encode

encoded_data = bytearray()

for i in range(0, len(original_data), k):

    chunk = original_data[i : i + k]

    encoded_data.extend(codec.encode(chunk))

# 3. Corrupt (The "Stress Test")

# We will randomly corrupt 5% of the file

corrupted_data = bytearray(encoded_data)

num_errors = int(len(corrupted_data) * 0.05)

indices = random.sample(range(len(corrupted_data)), num_errors)

for idx in indices:

    corrupted_data[idx] = random.randint(0, 255)

# --- NEW STEP: Save the Corrupted Version ---

# Note: This file will likely be "broken" and might not open in

# standard viewers because the RS parity bytes are mixed in.

with open("corrupted_with_parity.bin", "wb") as f:

    f.write(corrupted_data)

# ---------------------------------------------

# 4. Decode & Repair

decoded_data = bytearray()

for i in range(0, len(corrupted_data), n):

    chunk = corrupted_data[i : i + n]

    try:

        # The magic happens here: errors are removed

        corrected_chunk = codec.decode(chunk)[0]

        decoded_data.extend(corrected_chunk)

    except rs.ReedSolomonError:

        # If a block has > 16 errors, we just take the corrupted data

        # so the file stays the same size (though it will be glitchy)

        decoded_data.extend(chunk[:k])

# 5. Save the Clean Result

with open("recovered_final.jpg", "wb") as f:

    f.write(decoded_data)

print(f"Done! Processed {len(indices)} errors.")