Information Theory, Coding and Cryptography.

Ranjan Bose’s chapter about cyclic codes begins with a riveting quote by Pascal, Blaise “We arrive at the truth, not by reason only, but also by the heart.” Quotes like this make a comprehensive book about information theory even more captivating.

Linear Block Codes, block codes –every message (size k) corresponds to a codeword (size n), and follows a one-to-one relation— follows linearity property. According to the linearity property, a new code word generated by linear addition of two code word should belong to the set of all the defined code words.

\forall c_1 \in C, \forall c_2 \in C \Rightarrow c_1 + c_2 \in C

Cyclic block codes: Cyclic shift of a codeword results in another valid codeword. We use Galois Field representation os cyclic codes to lower the complexity encoding and encoding algorithms.

Here the first thing we would like to do is check if the code is liner and then cyclic. Let’s take a code C= {0000, 0101, 1010, 1111}.
Now to check linearity we will ex-or two codewords.
1010 + 0101 = 1111 \in C
1010 + 1111 = 0101 \in C

For Cyclic property, let’s circularly right shift every code word by 1

C_{n-1} = {0000, 1010, 0101, 1111} which is equivalent to C

Coefficients in a polynomial are elements of GF(q) and highest power is called the degree of a polynomial. Interesting fact: F[x] (polynomial) is a ring and not a field because polynomials of degree greater than zero do not have a multiplicative inverse.

GF(2) \quad \begin{bmatrix} + & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1&0 \end{bmatrix}  \quad \quad \begin{bmatrix} \cdot & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0&1 \end{bmatrix}

GF(3) \quad \begin{bmatrix} + & 0 & 1 & 2\\ 0 & 0 & 1&2 \\ 1 & 1&2&0 \\2&2&0&1 \end{bmatrix}  \quad \quad \begin{bmatrix} \cdot & 0 & 1&2 \\ 0 & 0 & 0 &0\\ 1 & 0&1&2\\2&0&2&1 \end{bmatrix}

GF(4) \quad \begin{bmatrix} + & 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 2&3 \\ 1 & 1&0&3&2 \\2&2&3&0&1 \\3&3&2&1&0 \end{bmatrix}  \quad \quad \begin{bmatrix} \cdot & 0 & 1 &2&3\\ 0 & 0 & 0&0&0 \\ 1 & 0&1 &2&3 \\2&0&2&3&1\\3&0&3&1&2 \end{bmatrix}

Given this, How does one generate a cyclic code.

  • Take a polynomial f(x) in R_n .
  • Obtain a set of polynomials by multiplying f(x) by all possible polynomials in R_n .
  • The ser of polynomials obtained above corresponds to the set of codewords belonging to a cyclic code. 
Ranjan Bose’s Information Theory, Coding and Cryptography.

4 thoughts on “Information Theory, Coding and Cryptography.

Leave a Reply

%d bloggers like this: