PUERTA | GATE-CS-2017 (Conjunto 2) | Pregunta 55

Considere un código binario que consta de solo cuatro palabras de código válidas como se indica a continuación.

00000, 01011, 10101, 11110

Sea p la distancia mínima de Hamming del código y q el número máximo de bits erróneos que pueden ser corregidos por el código. El valor de p y q son:

(A) p = 3 y q = 1
(B) p = 3 y q = 2
(C) p = 4 y q = 1
(D) p = 4 y q = 2

Respuesta: (A)
Explicación: Necesitamos encuentre la distancia mínima de hamming (diferencia en su posición de bit correspondiente)

00000, 01011, 10101, 11110

For two binary strings, hamming distance is number
of ones in XOR of the two strings.

Hamming distance of first and second is 3, so is 
for first and third. Hamming distance of first and
fourth is 4.

Hamming distance of second and third is 4, and 
second and fourth is 3.

Hamming distance of third and fourth is 3.

Thus a code with minimum Hamming distance d 
between its codewords can detect at most d-1
errors and can correct ⌊(d-1)/2⌋ errors.

Here d = 3. So number of errors that can be
corrected is 1.

Cuestionario de esta pregunta