Namespaces
Variants
Actions

Difference between revisions of "Hamming distance"

From Encyclopedia of Mathematics
Jump to: navigation, search
(better)
(→‎References: isbn link)
 
Line 18: Line 18:
  
 
====References====
 
====References====
* Goldie, Charles M.; Pinch, Richard G.E. ''Communication theory'', London Mathematical Society Student Texts. '''20''' Cambridge University Press (1991) ISBN 0-521-40456-8 {{ZBL|0746.94001}}
+
* Goldie, Charles M.; Pinch, Richard G.E. ''Communication theory'', London Mathematical Society Student Texts. '''20''' Cambridge University Press (1991) {{ISBN|0-521-40456-8}} {{ZBL|0746.94001}}
* van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics '''86''' Springer (1992) ISBN 3-540-54894-7 {{ZBL|0747.94018}}
+
* van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics '''86''' Springer (1992) {{ISBN|3-540-54894-7}} {{ZBL|0747.94018}}
  
 
{{TEX|done}}
 
{{TEX|done}}

Latest revision as of 16:49, 23 November 2023

A function on words of fixed length over an alphabet describing the number of changes to the symbols of one word required to reduce it to another. Let $A$ be an alphabet of symbols and $C$ a subset of $A^n$, the set of words of length $n$ over $A$. Let $u=(u_1,\ldots,u_n)$ and $v = (v_1,\ldots,v_n)$ be words in $C$. The Hamming distance $d(u,v)$ is defined as the number of places in which $u$ and $v$ differ: that is, $\sharp\{ i : u_i \neq v_i,\,i=1,\dots,n \}$.

The Hamming distance satisfies $$ d(u,v) \ge 0 \ \text{and}\ d(u,v) = 0\ \text{if and only if}\ u=v\ ; $$ $$ d(u,v) = d(v,u)\ ; $$ $$ d(u,v) \le d(u,w) + d(w,v) \ . $$ Hamming distance is thus a metric on $C$.

In the theory of error-correcting codes it is assumed that words from $C$ are transmitted down a noisy channel and that some symbols are changed during the transmission: see for example the symmetric channel. Maximum likelihood decoding of a received word $r$ consists of finding the word in $C$ nearest to $r$ in the Hamming metric. If the minimum Hamming distance between words of $C$ is $\delta$, then this process is capable of detecting up to $\delta-1$ errors in $r$, and correcting up to $\left\lfloor \frac{\delta-1}{2} \right\rfloor$ errors.

The Hamming weight $w(x)$ of a word $x$ over an alphabet containing a distinguished symbol $0$ is the distance $d(\mathbf{0},x)$ where $\mathbf{0}$ is the all-$0$ word. For linear codes in a vector space over a finite field, the distance is determined by the weight: $d(x,y) = w(x-y)$.

References

  • Goldie, Charles M.; Pinch, Richard G.E. Communication theory, London Mathematical Society Student Texts. 20 Cambridge University Press (1991) ISBN 0-521-40456-8 Zbl 0746.94001
  • van Lint, J.H., "Introduction to coding theory" (2nd ed.) Graduate Texts in Mathematics 86 Springer (1992) ISBN 3-540-54894-7 Zbl 0747.94018
How to Cite This Entry:
Hamming distance. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hamming_distance&oldid=54614