Saltar al contenido principal
LibreTexts Español

4.4: Distancia Hamming

  • Page ID
    82445
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Necesitamos alguna técnica para decir lo similares que son los patrones de dos bits. En el caso de cantidades físicas como la longitud, es bastante natural pensar en dos medidas como cercanas, o aproximadamente iguales. ¿Hay un sentido similar en el que dos patrones de bits están cerca?

    Al principio es tentador decir que dos patrones de bits están cerca si representan enteros que son adyacentes, o números de punto flotante que están cerca. Sin embargo, esta noción no es útil porque se basa en significados particulares atribuidos a los patrones de bits. No es obvio que dos patrones de bits que difieren en el primer bit deben ser más o menos “diferentes” entre sí que dos que difieren en el último bit.

    Una definición más útil de la diferencia entre dos patrones de bits es el número de bits que son diferentes entre los dos. A esto se le llama la distancia Hamming, después de Richard W. Hamming (1915 — 1998)\(^1\). Así 0110 y 1110 están separados por una distancia Hamming de uno. Dos patrones que son iguales están separados por una distancia de Hamming de cero.

    Tenga en cuenta que una distancia de Hamming solo se puede definir entre dos patrones de bits con el mismo número de bits. No tiene sentido hablar de la distancia Hamming de una sola cadena de bits, o entre dos cadenas de bits de diferentes longitudes.

    Usando esta definición, el efecto de los errores introducidos en el canal se puede describir por la distancia Hamming entre los dos patrones de bits, uno en la entrada al canal y el otro en la salida. Sin errores significa distancia de Hamming cero, y un solo error significa Hamming distancia uno. Si ocurren dos errores, esto generalmente significa una distancia Hamming de dos. (Tenga en cuenta, sin embargo, que si los dos errores suceden al mismo bit, el segundo cancelaría el primero, y la distancia de Hamming en realidad sería cero).

    La acción de un codificador también se puede apreciar en términos de distancia de Hamming. Para proporcionar detección de errores, es necesario que el codificador produzca patrones de bits para que dos entradas diferentes se separen en la salida por la distancia de Hamming al menos dos; de lo contrario, un solo error podría convertir una palabra de código legal en otra. Para brindar protección de doble error, la separación de dos palabras clave válidas cualquiera debe ser de al menos tres. Para que la corrección de un solo error sea posible, todas las palabras de código válidas deben estar separadas por la distancia de Hamming al menos tres.


    \(^1\)See a biography of Hamming at http://www-groups.dcs.st-andrews.ac....s/Hamming.html


    This page titled 4.4: Distancia Hamming is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Paul Penfield, Jr. (MIT OpenCourseWare) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.