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 having a problem understanding a bit of nation while reading these lecture notes on coding theory.

In chapter 2 it describes codes as $(n,|\mathcal{C}|)$ but then in chapter 3 it switches to $[n,k]$ and it appears rather confusing. Can anyone see what's really the difference - it looks like $|\mathcal{C}|=2^k$, but what the point of introducing this square braket notation which doesn't make any fundamental difference and just confuses instead.

share|improve this question
    
The first notation is for general codes. The second is for linear codes. It might seem silly to switch, but it's not ambiguous. –  Adam Saltz Jul 24 '11 at 11:55

2 Answers 2

up vote 3 down vote accepted

The notation $[n,k]$ specifically denotes a linear code of length $n$ and dimension $k$, i.e. a code that is closed under addition (and scalar multiplication, if the alphabet field is not the prime field). The notation $(n,|\mathcal{C}|)$ is used, when non-linear codes are allowed. If the minimum distance $d$ is included, then the notations $[n,k,d]$ and $(n,|\mathcal{C}|,d)$ are common. If the alphabet field is something other than binary, say, a field of $q$ elements, then the subscript $q$ is added: $[n,k,d]_q$.

Especially when the topic is studied by combinatorial methods linearity is not always assumed. The combinatorialists derived several bounds early in the development of the theory, and they were also interested in non-linear codes, because some of the problems on bounds of existence are then more interesting. Hence this notation was used to make the distinction clear.

You are correct in that when $q=2$ (=the default), then $|\mathcal{C}|=2^k$. Take notice of the round vs. square brackets.

share|improve this answer

Good question. For a general code $\mathcal C$, the main parameters of interest are its blocklength $n$ and size $|\mathcal C|$. On the other hand, for the more structured examples of linear codes, there is a more natural alternative to its size: the dimension $k$ of the code. Conveniently, as you point out, the size of a code of dimension $k$ is simply $2^k$; so the dimension is already conveying the size of the code as well.

But why is the dimension is more natural? I do not know how to answer this question directly, but I will give you a flavor of the prominent role played by the dimension in the life of a linear code.

  • First, if the dimension of $\mathcal C$ is $k$, then any $k+1$ vectors from $\mathcal C$ are linearly independent.
  • Moreover, $\mathcal C$ can be described as the linear span of precisely $k$ linearly independent vectors from $\mathcal C$.
  • There is a notion of a dual space $\mathcal C^{\bot}$ consisting of the "dual" codewords that are orthogonal to all codewords in $\mathcal C$; the dimension of the dual is exactly $n-k$. (Dual codewords come up while decoding linear codes.)

As you can see, the concept of dimension is ubiquitous while studying linear codes.

Finally, a comment on the notation. The differing notations $(n, |\mathcal C|)$ vs. $[n, k]$ is not to confuse the reader (:)) but to clarify that they stand for different, though related, concepts. One stands for size and the other for dimension. More importantly, one notation can be used for any code, whereas the other has been tailored for linear codes.

share|improve this answer
    
The most natural reason to use a linear code is that then using an agreed upon basis (as in your second bullet point) gives a way of encoding any $k$ (information) bits into $n$ (coded) bits by using them as coefficients w.r.t. to the chosen basis. A further useful observation is that a linear code necessarily acts transitively on itself by translations. Translations are isometries of the Hamming space. So the `constellation of nearby other codewords' looks identical no matter which codeword you are standing on. –  Jyrki Lahtonen Jul 24 '11 at 12:57
    
And another frequently occurring advantage related to your third bullet point is that the generators of the dual code can be used as parity checks. Thus with a linear code it is relatively to quick to check that a given string of bits is a valid codeword. –  Jyrki Lahtonen Jul 24 '11 at 13:01
    
Jyrki, nice points. I must confess that while I was thinking of $\mathcal C$ as sets, I seem to have overlooked the fact that you can also(!) use them to encode bits :-) –  Srivatsan Jul 24 '11 at 13:23

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.