Hamming(7,4)

Representació gràfica dels 4 bits de senyes d₁ a d₄ i 3 bits de paritat p₁ a p₃ i quins bits de paritat s'apliquen a quins bits de senyes

En teoria de còdics, Hamming (7,4) és el nom d'un còdic llineal de correcció d'errors que codifica quatre bits de senyes en sèt bits agregant tres bits de paritat. És un membre d'una família més gran de còdics de Hamming, encara que el terme còdic de Hamming a sovint es referix a este còdic específic que Richard Hamming va introduir en 1950. En aquell moment, Hamming treballava en els Bell Labs i estava frustrat en el clim a cometre errors del llector de targetes perforades, raó per la que va escomençar a treballar en còdics de correcció d'errors.

El còdic de Hamming agrega tres bits de verificació adicionals a cada quatre bits de senyes del mensage. l'algoritme de Hamming (7,4) pot corregir qualsevol error d'un sol bit o detectar tots els errors d'un sol bit i de dos bits. En atres paraules, la distància de Hamming mínima entre dos paraules de còdic correctes qualssevol és 3, i les paraules rebudes es poden decodificar correctament si estan a una distància de com a màxim una de la paraula de còdic que va ser transmesa pel remitent. Açò significa que per a situacions d'un mig de transmissió a on no es produïxen errors de racha, el còdic de Hamming (7,4) és efectiu (ya que el mig tindria que ser extremadament sorollós per a que dos dels sèt bits s'invertixquen).

En informació quàntica, el Hamming (7,4) s'utilisa com a base per al còdic de Steane, un tipo de còdic CSS utilisat per a la correcció d'errors quàntica.

Objectiu

L'objectiu dels còdics de Hamming és crear un conjunt de bits de paritat que se superponguen de modo que es puga detectar i corregir un error d'un sol bit en un bit de senyes o en un bit de paritat. Si be es poden crear múltiples superposicions, el método general es presenta en l'artícul dedicat als còdics de Hamming.

Bit #	1	2	3	4	5	6	7
Bit transmés	$p_1$	$p_2$	$d_1$	$p_3$	$d_2$	$d_3$	$d_4$
$p_1$	Sí No Sí No Sí No Sí $p_2$ No Sí Sí No No Sí Sí $p_3$ No No No Sí Sí Sí Sí Esta taula descriu quins bits de paritat cobrixen qué bits transmesos en la paraula codificada. Per eixemple, p2 proporciona una paritat parell per als bits 2, 3, 6 i 7. També detalla qué bit transmés està cobert per qué bit de paritat llegint la columna. Per eixemple, d1 està cobert per p1 i p2 pero no p3 Esta taula presenta una semblança sorprenent en la matriu de verificació de paritat (H) en la següent secció. Ademés, si s'eliminen les columnes de paritat de la taula anterior $d_1$ $d_2$ $d_3$ $d_4$ $p_1$ Sí Sí No Sí $p_2$ Sí No Sí Sí $p_3$ No Sí Sí Sí llavors també serà evident la semblança en les files 1, 2 i 4 de la matriu del generador de còdic (G) que figura a continuació. Per lo tant, en elegir correctament la cobertura de bits de paritat, tots els errors en una distància de Hamming d'1 poden detectar-se i corregir-se, raó principal per a utilisar un còdic de Hamming. Matrius de Hamming Els còdics de Hamming es poden calcular en térmens àlgebra llineal per mig de matrius perque els còdics de Hamming són còdics llineals. A los efectos dels còdics de Hamming, es poden definir dos matrius de Hamming: el còdic de la matriu generadora G i la matriu de comprovació de paritat H: ${𝐆}^{𝐓}:=\left(\begin{array}{cccc}1& 1& 0& 1\\ 1& 0& 1& 1\\ 1& 0& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right),𝐇:=\left(\begin{array}{ccccccc}1& 0& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 1& 1& 1& 1\end{array}\right).$ Posició dels bits de senyes i dels bits de paritat Com es va mencionar anteriorment, les files 1, 2 i 4 de G deurien resultar familiars, ya que assignen els bits de senyes als seus bits de paritat: p1 cobrix d1, d2, d4 p2 cobrix d1, d3, d4 p3 cobrix d2, d3, d4 Les files restants (3, 5, 6, 7) assignen les senyes a la seua posició en forma codificada i solament hi ha uns en eixa fila, per lo que és una còpia idèntica. De fet, estes quatre files són linealment independents i formen la matriu identitat (per disseny, no per coincidència). També com es va mencionar anteriorment, les tres files de H deurien resultar familiars. Estes files s'utilisen per a calcular el vector de síndrome en l'extrem receptor i si el vector de síndrome és vector nul (tot zeros), la paraula rebuda no conté errors; si no és zero, el valor indica qué bit s'ha invertit. Els quatre bits de senyes — ensamblados com un vector p — es multipliquen prèviament per G (és dir, Gp) i es pren el seu mòdul 2 per a obtindre el valor codificat que es transmet. Els 4 bits de senyes originals es convertixen en sèt bits (d'ahí el nom "Hamming (7,4)") en tres bits de paritat afegits per a garantisar una paritat uniforme utilisant les cobertura de bits de senyes anteriors. La primera taula anterior mostra la correspondència entre cada bit de senyes i la paritat en la seua posició de bit final (1 a 7), pero açò també es pot presentar en un diagrama de Venn. El primer diagrama d'este artícul mostra tres círculs (un per a cada bit de paritat) i tanca els bits de senyes que cobrix cada bit de paritat. El segon diagrama (mostrat a la dreta) és idèntic pero, en canvi, estan marcades les posicions dels bits. Per al restant d'esta secció, els següents 4 bits (mostrats com un vector columna) s'utilisaran com un eixemple d'eixecució: $𝐩=\left(\begin{array}{c}{d}_1\\ d_2\\ d_3\\ d_4\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}\right)$ Referències Referències