Basic concepts of linear codes

Monday, June 6 2005
Presenter: J. Walker.
Material: 1.1 - 1.4
For Lecture: 1,4,5,8
Problem Set: 6, 10, 14, 17, 19.

Presenting: Wednesday, June 8. Section 1.6 Problem Set: 35, 40, 41, 43

Coding Theory - trying to transmit information across a channel that may change the information. Goal: Coming up with efficient ways to send code, while detecting and correcting errors.

Picture - Figure 1.1 from book, pg. 2
Message - Encoder - codeword - Channel (noise inserted) - recieved word - Decoder - estimate of code word - Unencoder - Estimate of message.

Think of the message as $\textbf x \in \mathbb{F}_q^k$. This is translated into a codeword $\textbf c \in \mathbb{F}_q^n$, where $n \geq k$. Let $C$ be the set of all possible codewords. Some error is introduced, $\textbf e \in \mathbb{F}_q^n$, resulting in the received word $\textbf y = \textbf c + \textbf e \in \mathbb{F}_q^n$. The decoder take $\textbf y$ and produces $\hat{ \textbf {c}} \in \mathbb{F}_q^n \in C$, where our hope is that $\hat{\textbf c} = \textbf c$. Finally, the unencoder produces a estimate of the message, $\hat{\textbf x} \in \mathbb{F}_q^2$. Because the encoder is injective, we usually skip the estimate of message / unencoder part.

Example of a Channel: Binary Symmetric Channel
Binary implies that $q = 2$, symmetric implies that the error is same for either 0 or 1. We have 2 possible errors -

1. A ``1" is received as a ``0" or
   
2. A ``0" is received as a ``1".

We denote the probability of error in any given bit as $p$, where $0 \leq p < \frac12$. Probabilities:

• $0 \rightarrow 1$: p
• $0 \rightarrow 0$: 1 - p
• $1 \rightarrow 1$: 1-p
• $1 \rightarrow 0$: p

Example: Repetition Code
Transmit each symbol $n$ times, then do a ``majority vote" to decode. If $n = 3$, $q = 2$, we have 2 messages (0, 1) and 2 codewords (000, 111). We can correct at most 1 error in the sent codeword. For example, we would decode 101 as 111 because 111 is the most probable codeword sent. However, the code can detect up to $n-1$ errors. The problem with this code is that it is too expensive - in order to correct one error, you must triple the message size.