Algoritmo per generare un codice a correzione d'errore dimensione k su n bit

Question

voglio generare un codice su n bit per k diversi ingressi che voglio classificare. Il requisito principale di questo codice è il criterio di correzione degli errori: che la distanza minima tra due coppie di ingressi codifiche diverse è massimizzata. Non ho bisogno di essere precisi -. Approssimativa farà, e la facilità d'uso e la velocità di implementazione computazionale è una priorità troppo

In generale, n sarà nell'ordine delle centinaia, k nelle decine.

Inoltre, c'è un ragionevolmente stretto legato alla distanza minima di Hamming tra k diverso n bit codifiche binarie?

Answer 1

Il problema di trovare l'esatto miglior codice di correzione degli errori per determinati parametri è molto difficile, anche approssimativamente migliori codici sono difficili. In cima a quello, alcuni codici non hanno alcun algoritmi di decodifica decenti, mentre per altri il problema di decodifica è abbastanza difficile.

Tuttavia, si sta chiedendo una particolare serie di parametri in cui n »k, in cui, se ho capito bene si vuole un codice k-dimensionale di lunghezza n. (In modo che k bit sono codificati in n bit.) In questa gamma, in primo luogo, un codice casuale è probabile che abbia una buona distanza minima. L'unico problema è che la decodifica è ovunque da poco pratico intractible, ed effettivamente calcolo della distanza minima non è che facile.

In secondo luogo, se si vuole un codice di esplicita per il caso n »k, allora si può fare ragionevolmente bene con un codice BCH con q = 2. Mentre la pagina di Wikipedia spiega, c'è una buona decodifica algoritmo per codici BCH.

Per quanto riguarda i limiti superiori per la minima distanza di Hamming, nella gamma n »k si dovrebbe iniziare con la Hamming legato, anche conosciuto come il volume rilegato o l'imballaggio sfera legata. L'idea del limite è semplice e bella: Se la distanza minima è di t, allora il codice può correggere gli errori fino al pavimento distanza ((t-1) / 2). Se è possibile correggere gli errori a qualche raggio, vuol dire che le palle di Hamming di tale raggio non si sovrappongono. D'altra parte, il numero totale di parole possibili è 2 ⁿ , quindi se si divide per il numero di punti in un pallone Hamming (che nel caso binario è una somma dei coefficienti binomiali), si ottiene un limite superiore al numero di parole di codice senza errori. È possibile battere questo limite, ma per grande distanza minima non è facile. In questo regime è un ottimo rilegato.