Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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.

If this is not helpful, please consider editing more information into your question as to where exactly your difficulty is.

share|improve this answer
    
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
1  
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
add comment

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)

share|improve this answer
    
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.