Error correcting codes and minimum distances

Question

I was looking at a challenge online (at King's website) and although I understand the general idea behind it I'm slightly lost - maybe the wording is a little off? Here is the problem and I'll state what I don't understand below:

Error correcting codes are used in a wide variety of applications ranging from satellite communication to music CDs. The idea is to encode a binary string of length k as a binary string of length n>k, called a codeword such that even if some bit(s) of the encoding are corrupted (if you scratch on your CD for instance), the original k-bit string can still be recovered. There are three important parameters associated with an error correcting code: the length of codewords (n), the dimension (k) which is the length of the unencoded strings, and finally the minimum distance (d) of the code. Distance between two codewords is measured as hamming distance, i.e., the number of positions in which the codewords differ: 0010 and 0100 are at distance 2. The minimum distance of the code is the distance between the two different codewords that are closest to each other. Linear codes are a simple type of error correcting codes with several nice properties. One of them being that the minmum distance is the smallest distance any non-zero codeword has to the zero codeword (the codeword consisting of n zeros always belongs to a linear code of length n). Another nice property of linear codes of length n and dimension k is that they can be described by an n×k generator matrix of zeros and ones. Encoding a k-bit string is done by viewing it as a column vector and multiplying it by the generator matrix. The example below shows a generator matrix and how the string 1001 is encoded. graph.png Matrix multiplication is done as usual except that additon is done modulo 2 (i.e., 0+1=1+0=1 and 0+0=1+1=0). The set of codewords of this code is then simply all vectors that can be obtained by encoding all k-bit strings in this way. Write a program to calculate the minimum distance for several linear error correcting codes of length at most 30 and dimension at most 15. Each code will be given as a generator matrix. Input You will be given several generator matrices as input. The first line contains an integer T indicating the number of test cases. The first line of each test case gives the parameters n and k where 1≤n≤30, 1≤k≤15 and n > k, as two integers separated by a single space. The following n lines describe a generator matrix. Each line is a row of the matrix and has k space separated entries that are 0 or 1. Output For each generator matrix output a single line with the minimum distance of the corresponding linear code.

Sample Input 1

2

7 4

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

0 1 1 1

1 0 1 1

1 1 0 1

3 2

1 1

0 0

1 1

Sample Output 1

3

0

Now my assumption is that the question is asking "Write a program that can take in the linear code in matrix form and say what the minimum distance is from an all zero codeword" I just don't understand why there is a 3 output for the first input and a 0 for the second input?

Very confused.

Any ideas?

Answer 1

For first example:

Input binary string: 1000
Resulting code: 1100001
Hamming distance to zero codeword 0000000: 3

For second example:

Input binary string: 11
Resulting code: 000
Hamming distance to zero codeword 000: 0

Your goal is to find valid non-zero codeword (which can be produced from some non-zero k-bit input string) with minimal Hamming distance to zero codeword (in different words - with minimal amount of ones in binary representation) and return that distance.

Hope that helps, the problem description is indeed a little bit hard to understand.

EDIT. I've made typo in first example. Actual input should be 1000 not 0001. Also it's may be not clear what exactly is input string and how the codeword is calculated. Let's look at first sample.

Input binary string: 1000

This binary string in general is not part of generator matrix. It is just one of all possible non-zero 4-bit strings. Let's multiply it by generator matrix:

(1 0 0 0) * (1 0 0 0) = 1
(0 1 0 0) * (1 0 0 0) = 0
(0 0 1 0) * (1 0 0 0) = 0
(0 0 0 1) * (1 0 0 0) = 0
(0 1 1 1) * (1 0 0 0) = 0
(1 0 1 1) * (1 0 0 0) = 1
(1 1 0 1) * (1 0 0 0) = 1

One way to find input that produces "minimal" codeword is to iterate all 2^k-1 non-zero k-bit strings and calculate codeword for each of them. This is feasible solution for k <= 15.

Another example for first test case 0011 (it's possible to have multiple inputs that produce "minimal" output):

(1 0 0 0) * (0 0 1 1) = 0
(0 1 0 0) * (0 0 1 1) = 0
(0 0 1 0) * (0 0 1 1) = 1
(0 0 0 1) * (0 0 1 1) = 1
(0 1 1 1) * (0 0 1 1) = 2 = 0 (mod 2)
(1 0 1 1) * (0 0 1 1) = 2 = 0 (mod 2)
(1 1 0 1) * (0 0 1 1) = 1

Resulting code 0011001 also has Hamming distance 3 to the zero codeword. There is no 4-bit string with code that has less that 3 ones in binary representation. That's why the answer for first test case is 3.