Uncertain notation in coding theory book

Question

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.

Answer 1

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.

Answer 2

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.