Understanding Cell Phone Technology: Block Codes for Error Control
The design of block codes relies on abstract algebra. Abstract algebra is all about sets of elements with special attributes. For example, a group is a set of elements with a defined operation that is closed, associative, and contains an identity and inverse for every element. By closed, we mean that the element resulting from applying an operation to two elements of the set is still in the set. By associative, we mean that when the operation is applied to three elements {a, b, c}, the associative property applies, e.g., a + (b + c) = (a + b) + c. The set {0,1} forms a group under mod 2 addition (we talked about mod 2 addition last week). The identity is 0. The inverse of 0 is 0, and the inverse of 1 is 1.
In abstract algebra, a field is a set of elements which:
· remains closed under two operations, called addition and multiplication;
· forms a commutative group under addition, that is, a + b = b + a;
· forms a commutative group under multiplication among its non-zero elements;
· distributes multiplication over addition, meaning a * (b + c) = a * b + a * c.
The binary set {0,1} forms a field under the operations of mod 2 addition and multiplication. Mod 2 multiplication is given by the following:
0*0 = 0
0*1 = 0
1*0 = 0
1*1 = 1
We call this field GF(2). GF stands for Galois Field, named after the mathematician Évariste Galois. You can learn more about this at https://mathworld.wolfram.com/FiniteField.html
Let’s get back to our block code design now. Suppose we want to send a 4-bit message u. There are 2^4 or 16 possible messages that can be sent. These messages actually belong to a 16-element field GF(2^4). We’re going to perform an operation on the messages in order to convert the 4-bit message into a 7-bit code word v for transmission. For those of you who are familiar with vectors and matrices, the transformation is accomplished by multiplying each 4-bit message vector by a 4×7 matrix to get a 7-bit code word vector. The following table shows all the possible messages and their corresponding code words.
Message u Code word v
————– —————–
0000 0000000
1000 1101000
0100 0110100
1100 1011100
0010 1110010
1010 0011010
0110 1000110
1110 0101110
0001 1010001
1001 0111001
0101 1100101
1101 0001101
0011 0100011
1011 1001011
0111 0010111
1111 1111111
This is a (7,4) Hamming code. I mentioned Hamming codes last week as the first kind of block code discovered. A schematic of the encoder appears in the attached diagram. We see that a 4-bit input (message)
u = (u0, u1, u2, u3)
generates a 7-bit output (code word)
v = (v0, v1, v2, v3, v4, v5, v6, v7) = (u0+u2+u3, u0+u1+u2, u1+u2+u3, u0, u1, u2, u3).
By adding on these extra bits, we’re adding some redundant information back into the stream. The decoder at the receiver can use the information contained in the extra 3 bits to recover as accurate a version of the transmitted message as possible. How the decoder does this is a little beyond the scope of this blog. What’s important to take away is that the decoder can use these extra bits to detect and correct at least some of the errors in that noise introduced during transmission. For this (7,4) code, the decoder will be able to correct any single digit error that occurs in a single code word.
Your cell phone uses its decoder to reconstruct the original message even when noise on the channel corrupts it. This is one of the amazing methods modern communications systems use to keep working even when the signal quality is poor.
We’re learned a lot about block codes today. Next week, we will investigate the other flavor of error controlling codes, convolutional codes.
