Codifica / Correzione errori sfida

https://stackoverflow.com/questions/2393362

25-09-2019
|

Domanda

E 'matematicamente possibile per codificare e messaggio iniziale 4 byte in 8 byte e se uno degli 8 byte è completamente caduto e un altro è sbagliato per ricostruire il messaggio iniziale 4 byte? Non ci sarebbe alcun modo per ritrasmissione né sarebbe la posizione del caduto byte di essere conosciuto.

Se si usa Reed Solomon correzione degli errori con 4 "parità" byte appiccicato alla fine dei 4 byte "dati", come DDDDPPPP, e si finisce con DDDEPPP (dove E è un errore) e un byte di parità è stato fatto cadere, non credo ci sia un modo per ricostruire il messaggio iniziale (anche se corretto me se sbaglio) ...

Che dire moltiplicare (o eseguire un'altra operazione matematica) il messaggio iniziale di 4 byte per una costante, quindi utilizzando le proprietà di un'operazione matematica inversa per determinare quali byte è stata abbandonata. Oppure, impongono alcuni vincoli sulla struttura del messaggio in modo che ogni altri bisogni byte da dispari e gli altri devono essere ancora.

In alternativa, invece di byte, potrebbe anche essere di 4 cifre decimali codificate in qualche modo in 8 cifre decimali dove gli errori possono essere rilevati e corretti nelle stesse circostanze di cui sopra - nessuna ritrasmissione e la posizione del byte caduto non è noto .

Sto cercando tutte le idee folli chiunque potrebbe avere ... Tutte le idee là fuori?

EDIT:

Può essere un po 'forzato, ma la situazione che sto cercando di risolvere è quella in cui si dispone di, diciamo, una stampante difettosa che stampa i numeri importanti in un form, che vengono poi spediti via a un'impresa di trasformazione che utilizza l'OCR per leggere le forme. L'OCR non sta per essere perfetto, ma dovrebbe avvicinarsi con solo cifre da leggere. La stampante difettosa potrebbe essere un problema più grande, dove può cadere un numero intero, ma non c'è modo di sapere di quale si cadrà, ma saranno sempre venire fuori nel giusto ordine, non ci sarà alcuna cifra scambiati.

Il modulo potrebbe essere modificato in modo che stampi sempre uno spazio tra i primi quattro numeri ei numeri di correzione degli errori, cioè 1234 5678, in modo che si potrebbe sapere se una cifra iniziale 1234 è stata abbandonata o un 5678 errore di correzione di cifre è stata abbandonata , se questo ha il problema più facile da risolvere. Sto pensando in qualche modo simile al modo in cui verificare i numeri di carta di credito tramite un algoritmo, ma in quattro pezzi cifre.

Si spera, che fornisce alcuni chiarimenti in merito a quello che sto cercando ...

Soluzione

In assenza di "bello" struttura algebrica, ho il sospetto che sarà difficile trovare uno schema conciso che si ottiene fino a 10 ** 4 parole di codice, dal momento che le informazioni-teoricamente, non c'è molto di allentamento. (Quello di seguito è possibile utilizzare GF (5) per 5 ** 5 = 3125.) Per fortuna, il problema è abbastanza piccolo che si potrebbe provare il metodo di code-costruzione avido di Shannon (trovare una parola in codice che non è così in conflitto con quello già scelto, aggiungerlo al set).

Codifica fino a 35 bit come un f polinomiale su GF (128). Valutare il polinomio a otto punti predeterminati x0, ..., X7 e codificare come 0f (x0) 1f (x1) 0f (x2) 1f (x3) 0f (x4) 1f (x5) 0f (x6) 1f (X7), dove gli zeri alternati e sono memorizzate nella MSB.

Quando la decodifica, prima occhiata alle MSB. Se il MSB non corrisponde l'indice mod 2, allora questo byte è corrotto e / o è stato spostato a sinistra di una delezione. Assumere esso è buono e spostarlo verso destra (eventualmente accumulare più valori diversi possibili in un punto). Ora abbiamo almeno sette valutazioni di un quarto grado polinomio f nei punti noti, di cui al massimo uno è corrotto. Ora possiamo provare tutte le possibilità per la corruzione.

EDIT: bmm6o ha avanzato la pretesa che la seconda parte della mia soluzione non è corretta. Non sono d'accordo.

Rivediamo le possibilità per il caso in cui i bit più significativi sono 0101101. Supponiamo X è la matrice di byte inviati e Y è la matrice di byte ricevuti. Da un lato, Y [0], Y [1], Y [2], Y [3] hanno MSB corretti e presunti in X [0], X [1], X [2], X [3] . D'altra parte, Y [4], Y [5], Y [6] hanno MSB errate e si presume essere X [5], X [6], X [7].

Se X [4] è caduto, poi abbiamo sette corrette valutazioni di f.

Se X [3] è caduto e X [4] è corrotto, allora abbiamo una valutazione non corretta a 3, e sei valutazioni corrette.

Se X [5] è caduto e X [4] è corrotto, allora abbiamo una valutazione non corretta a 5, e sei valutazioni corrette.

Non ci sono più possibilità oltre a queste, ma non abbiamo mai avere meno di sei valutazioni corrette, che basta a recuperare f.

Altri suggerimenti

Credo che si avrebbe bisogno di studiare ciò che codici cancellazione potrebbe offrire. Non conosco nessun limiti io, ma forse qualche tipo di codice MDS potrebbe raggiungere questo obiettivo.

EDIT: Dopo una rapida ricerca ho trovato RSCode biblioteca e nel esempio si dice che

In general, with E errors, and K erasures, you will need
* 2E + K bytes of parity to be able to correct the codeword
* back to recover the original message data.

Quindi, appare come codice Reed-Solomon è infatti la risposta e si può effettivamente ottenere il recupero da una cancellazione e un errore nel codice di 8,4.

codici di parità opera finché due byte di dati non sono interessati da errori o perdita e finché l'errore non è uguale a qualsiasi byte di dati mentre un byte di parità viene persa, imho.

codici di correzione di errore può in generale raschiature maniglia, ma in letteratura si suppone nota la posizione della cancellazione. Nella maggior parte dei casi, la cancellazione sarà introdotto dal demodulatore quando c'è scarsa fiducia che i dati corretti possono essere recuperati dal canale. Ad esempio, se il segnale non è chiaramente 0 o 1, il dispositivo può indicare che i dati sono stati persi, piuttosto che rischiare l'introduzione di un errore. Dal momento che una cancellazione è essenzialmente un errore con una posizione nota, sono molto più facili da risolvere.

Non sono sicuro di ciò che la vostra situazione è dove si può perdere un singolo valore e si può ancora essere sicuri che i valori rimanenti vengono consegnati nell'ordine corretto, ma non è una situazione classica codifica indirizzi teoria.

Cosa algorithmist sta suggerendo di cui sopra è questo: se potete limitarvi a solo 7 bit di informazioni, è possibile compilare l'8 bit di ciascun byte con alternanza di 0 e 1, che vi permetterà di conoscere la posizione del byte mancante . Cioè, mettere uno 0 nella bit alto di byte 0, 2, 4, 6 e 1 nei bit alti degli altri. Sul lato di ricezione, se si riceve solo 7 byte, a quella perduta, saranno stati sceso da tra i byte i cui bit di corrispondere. Purtroppo, questo non è giusto: se la cancellazione e l'errore sono adiacenti, non è possibile sapere immediatamente quale byte è stata abbandonata. Per esempio, bit alti 0101101 potrebbero derivare da far cadere il 4 ° byte, o da un errore nel 4 ° di byte e far cadere il terzo, o da un errore nel quarto byte e far cadere il 5 °.

È possibile utilizzare il codice lineare:

1 0 0 0  0 1 1 1
0 1 0 0  1 0 1 1
0 0 1 0  1 1 0 1
0 0 0 1  1 1 1 0

(cioè si inviano dati come (a, b, c, d, b + c + d, a + c + d, a + b + d, a + b + c) (dove aggiunta è implementato con XOR, poiché a, b, c, d sono elementi di GF (128))). È un codice lineare con la distanza 4, in modo che possa correggere un errore singolo byte. È possibile decodificare con sindrome decodifica , e poiché il codice è auto-duale, la matrice H sarà lo stesso come sopra.

Nel caso in cui ci sia un byte caduto, è possibile utilizzare la tecnica di cui sopra per determinare quale sia. Una volta stabilito che, si sta essenzialmente decodificare un codice diverso - il codice "bucata", creato facendo cadere quella data di byte. Dal momento che il codice forato è ancora lineare, è possibile utilizzare la sindrome di decodifica per determinare l'errore. Si dovrà calcolare la parity-check matrice per ciascuno dei codici accorciati, ma si può fare questo prima del tempo. Il codice accorciato ha distanza 3, in modo che possa correggere eventuali errori a singolo byte.

Nel caso di cifre decimali, assumendo uno va con prima cifra dispari, seconda cifra anche, terza cifra dispari, ecc - con due cifre, si ottiene 00-99, che può essere rappresentato in 3 pari / dispari cifre / dispari (125 combinazioni totali) - 00 = 101, 01 = 103, 20 = 181, 99 = 789, ecc così si codifica due serie di cifre decimali in 6 cifre totali, poi le ultime due cifre significano cose circa i primi gruppi di 2 cifre o un checksum di qualche tipo ... La prossima alla ultima cifra, suppongo, potrebbe essere una sorta di indicatore pari / dispari su ciascuno dei messaggi iniziali 2 cifre iniziali (1 = persino prime 2 cifre, 3 = dispari primi due cifre) e seguire il modello di essere dispari. Poi, l'ultima cifra potrebbe essere l'unico luogo di una somma delle singole cifre, in questo modo se una cifra mancava, sarebbe immediatamente evidente e potrebbe essere corretto assumendo l'ultima cifra era corretta. Anche se, sarebbe gettare le cose fuori se una delle ultime due cifre sono state ritirate ...

Sembra essere teoricamente possibile se si assume 1 errore di bit nel byte sbagliato. Abbiamo bisogno di 3 bit per identificare byte caduto e 3 bit per identificare byte sbagliato e 3 bit per identificare po 'sbagliato. Abbiamo 3 volte che molti bit extra.

Ma se abbiamo bisogno di identificare qualsiasi numero di bit di errore nel byte di sbagliato, si tratta di 30 bit. Anche questo sembra essere possibile con 32 bit, anche se 32 è un po 'troppo vicino per il mio conforto.

Ma non so a caldo per codificare per ottenere che. Prova turbocode?

In realtà, come ha detto Krystian, quando si correggere un codice RS, saranno corretti sia il messaggio che i byte "parità", fino a quando si dispone di v + 2e <(nk) dove v è il numero di cancellature (voi conoscere la posizione) ed e è il numero di errori. Questo significa che se hai solo errori, è possibile correggere fino a (nk) / 2 errori, o (NK-1) cancellature (circa il doppio del numero di errori), o un mix di entrambi (vedi articolo di Blahut: Transform tecniche per codici di controllo errore e < a href = "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.2084&rep=rep1&type=pdf" rel = "nofollow"> a universale Reed-Solomon decoder ).

La cosa ancora più bella è che è possibile verificare che la correzione ha avuto successo: controllando che il polinomio sindrome contiene solo 0 coefficienti, si sa che i byte + message di parità sono entrambi corretti. Si può fare, prima di verificare se il messaggio ha bisogno di alcuna correzione, e inoltre è possibile fare il check dopo la decodifica per controllare che sia il messaggio che i byte di parità sono stati completamente riparati.

Il v legato + 2e <(n-k) è ottimale, non si può fare di meglio (è per questo che Reed-Solomon è chiamato un errore codice di correzione ottimale). In realtà è possibile andare oltre questo limite utilizzando bruteforce si avvicina, fino a un certo punto (è possibile ottenere 1 o 2 più simboli per ogni 8 simboli) utilizzando elenco decodifica , ma è ancora un dominio nella sua infanzia, non so di qualsiasi attuazione pratica che funziona.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow