Finding the information sets of a linear code.

I'm trying to get a better understanding of linear codes, so I decided to work on problems from various textbooks. I'm having trouble understanding how to do this problem, and I was wondering if anyone can lead me in the right direction.

Problem The matrix $G = [I_{4} | A]$, where $$G = \left[ \begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1\end{array} \right]$$

is a genrator matrix in standard form for a $[7,4]$ binary code, denoted by $\mathcal{H}_3$. The parity check matrix for $\mathcal{H}_3$ is $$H = [A^{T} | I_{3}] = \left[ \begin{array}{cccc|ccc} 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{array} \right].$$

Find at least four information sets in $\mathcal{H}_3$. Find at least one set of four coordinates that do not form an information set. $\blacksquare$

The book defines an information set as follows: Given a $[n,k]$ linear code $\mathcal{C}$, a generator matrix for $\mathcal{C}$ is any $k \times n$ matrix $G$ whose rows form a basis for $\mathcal{C}$. For any set of $k$ independent columns of $G$, the corresponding set of coordinates forms an information set for $\mathcal{C}$.

Any help would be greatly appreciated since I've been staring at this for quite some time. Thanks!

-

Are you having trouble finding sets of 4 independent/dependent columns in $G$? or are you having trouble finding the corresponding set of coordinates, given the set of 4 independent columns?

If your problem is the first of the above, then the question is, do you know what it means for a set of vectors to be (linearly) independent, and how to test a set of vectors for this property? Can you see, for example, that the first 4 columns of $G$ are independent, while columns 2, 3, 4, 5 are not? There is a non-trivial linear combination of columns 2 through 5 giving the zero vector, namely, the 5th minus the sum of the other three; but there is no linear combination of the first 4 columns giving zero, other than the combination with all four coefficients being zero.

-
Gerry, this has been helpful. I was unsure as to how to find the information sets, but after reading your answer, it makes more sense. From linear algebra, I remember how to test for independence by using row operations. From what you said, I understand that $(1, 2, 3, 4)$ would form an information set. From the book's definition, would I have to find another set of 4 columns that are independent, or would I have to find any number of columns that are independent? For instance, can I say $(1, 2, 3)$ is an iformation set? – josh Aug 30 '12 at 12:19
You quoted the book as saying "any set of $k$ independent columns," and it's evident in your example that $k=4$, so, no, it would appear that $(1,2,3)$ is not an information set. – Gerry Myerson Aug 30 '12 at 13:10
Ok, that's what I figured, but I wanted to make sure it was correct. After some calculations, I was able to find 4 more information sets, namely: $(1, 5, 6, 7)$, $(2, 5, 6, 7)$, $(3, 5, 6, 7)$, $(4, 5, 6, 7)$. Thanks again for your help! – josh Aug 30 '12 at 13:59
There is also a code in the text called the $[n, 1]$ repitition code, which has a generator matrix of $G = [1 | 1 \cdots 1]$. Would this code have $n$ information sets since there are $n$ sets of 1 independent columns? – josh Aug 30 '12 at 14:20
Yes.${}{}{}{}{}$ – Gerry Myerson Aug 30 '12 at 23:22

As I interpret your book's definition of an "information set", the "set of coordinates" that corresponds to a set of columns is literally the index of those columns in the matrix $G$. So if $$G=\left[\begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right],$$ the "set of coordinates" corresponding to "the first, second, fourth, and seventh columns" is literally just (1,2,4,7). Since these columns are not linearly independent, this would be an example of a set of four coordinates which do not form an information set.

That $G$ has four independent columns is what allows it to uniquely encode a message of length four. If you take any four-digit message $m$ and multiply $mG$ then the resulting 7-digit codeword can be translated uniquely back to the original message; if $G$ had fewer than $4$ independent columns, this multiplication would yield the same result for more than one 4-digit message, and in a sense you would lose information. You could never be sure you decoded certain messages correctly.

Another way to think of the situation is that because $G$ has four independent columns, it has rank 4 and thus when you put it in row-reduced echelon form, it will be a standard generator matrix (the $G$ in this example already is a standard generator matrix). If it wasn't, though, and yet it still had four independent columns, you could convert it easily. Now, if you look at what happens when you multiply $mG$, the result is the message $m$ itself with three additional digits tacked onto the end. If the columns of the identity matrix were at other coordinates, the codeword would have the message $m$ rearranged as those columns are rearranged, with additional digits inserted where the other columns are.

I hope this rambling was useful rather than even-more confusing. This document has a pretty good explanation of information sets as well (see p. 39). (I'm not sure who to credit, but the document originally came from Jonathan Hall's MSU webpage)

-
Thank you Kirk! From what you said, I understand that $(1,2,4,7)$ is a set of 4 coordinates that does not form an information set. Would $(1, 2, ,3, 4)$ be an information set since these columns are Linearly Independent? To find another one, would I have to find another set of 4 columns that are Linearly Independent? – josh Aug 30 '12 at 12:04
Yup, that's exactly right. The list of indices of the columns is the same as the "corresponding coordinates" of the columns, and ANY $k$ linearly independent ones are what make up an information set, so long as there are enough of them. It doesn't matter which set of them you find :) – Kirk Boyer Aug 30 '12 at 15:29
Thank you Kirk! I have another observation for you. In the commments above, I mentioned a generating code of the form $G = [1 | 1 , \cdots , 1]$ for the $[n,1]$ binary repetition code of length $n$. Would this code have $n$ information sets since there are $n$ columns of legnth 1 that are independent? – josh Aug 30 '12 at 15:56