Desigualdad triangular y distancia de Hamming

Question

La pregunta que intento responder es

deje $x,y,z$ sean códigos binarios con el mismo número de bits, dé un ejemplo o demuestre que no puede suceder lo siguiente.

$dH(x,y)=5$ , $dH(y,z) = 2$ y $dh(x,z) = 6$ donde $dH$ es la distancia de Hamming entre los códigos.

He aplicado la desigualdad del triángulo que confirma que esto puede ser posible ya que $dH(x,z) < dh(x,y) + dH(y,z)$ . Sin embargo, no encuentro ningún ejemplo. Me parece que la única manera de obtener este escenario sería que $dH(y,z)$ sea un número impar en lugar de un número par. He escrito algo de código para intentar generar un ejemplo pero no puedo obtener ningún ejemplo así que estoy seguro de que esto no es posible, ¿alguien puede ayudarme a confirmar si esto es o no el caso?

Answer 1

Supongamos sin pérdida de generalidad que $y$ está hecho de ceros; $y = 00000...$ y que $dH(y,z) = 2$ . Sea $i, j$ denotan las posiciones en las que $z_i = z_j = 1$ (los dos lugares donde $z \neq y$ ). Supongamos que $dH(x,y) = 5$ . Así que $x$ tiene $5$ puestos que son $1$ . Hay tres casos:

1) Si $x_i = x_j = 1$ entonces $dH(x,z) = 3$ Porque $x, z$ sólo difieren en las posiciones que son 1 en $x$ y no en $z$ y son 3.

Ejemplo : $x = 11\color{red}{111}00..$ , $z = 11\color{blue}{000}00..$

2) $x_i = 1$ y $x_j = 0$ o $x_i = 0$ y $x_j = 1$ en ambos casos $dH(x,z) = 4$

Ejemplo : $x = 1\color{blue}{0}\color{red}{111}00..$ , $z = 1\color{red}{1}\color{blue}{000}00..$

3) $x_i = x_j = 0$ en este caso $dH(x,z) = 7$ - ya que hay 5 posiciones en las que $x$ es 1 y $z$ es cero, y 2 más donde $x$ es 0 y $z$ es 1.

Ejemplo : $x = \color{blue}{00}\color{red}{11111}00..$ , $z = \color{red}{11}\color{blue}{00000}00..$

En ninguno de los casos $dH(x,z) = 6$ así que tienes tu contradicción.

Answer 2

Sean dos números de longitud $n$ , $x$ y $y$ , han $a$ y $b$ ( $a\le b$ ) $1$ en común con un tercer número de longitud $n$ , $0\dots0$ .

Sea el número de $1$ 's $x$ y $y$ tienen en común ser $c$ .

Sabemos que $0\le c\le a$ y también que el número de $1$ 's que $a$ no tiene en común con $b$ es $a-c$ .

El número de $1$ 's que $b$ no tiene en común con $a$ es $b-c$ .

Así que $dH(x,y)=(a-c)+(b-c)=a+b-2c$ .

En su pregunta $a=2$ , $b=6$ y $c\in\{0,1,2\}$ por lo que es imposible que $dH(x,y)=5$ .

Tenga en cuenta que si voltea un bit en $z$ y volteas el mismo bit en ambos $x$ y $y$ entonces los números de Hamming no cambian, y el intercambio de columnas de bits (es decir, el intercambio de $(x_i,y_i,z_i)\leftrightarrow(x_j,y_j,z_j)$ ) tampoco cambia el número de Hamming.

Para completar la prueba, cualquier conjunto de números creado a partir de $0\dots0$ utilizando las transformaciones anteriores, con los números correspondientes que tienen los números de Hamming apropiados, tiene los mismos números de Hamming, y $dH(x,y)$ es invariable.