Generator Polynomial

Generator Polynomial \(g(D)\) is equivalent to the Generator Matrix in Linear Block Coding sense. Its degree is equal to the number of parity bits in the code which is \(n-k\). It is unique as it is the only code word polynomial of minimum degree \(n-k\), and any multiplication done on it is a #Code Word Polynomial.

Its property can be stated mathematically as below:

$$ \begin{align} g(D) &= 1 + \sum^{n-k-1}_{i=1} g_i D^i + D^{n-k}\\ x(D) &= a(D) g(D) \mod (D^n + 1) \end{align} $$

Where:

Links to this page
  • TIT3131 Chapter 4: Cyclic Code
  • Syndrome Decoding
  • Parity Polynomial

    Parity Polynomial \(b(D)\) is defined as below using several facts from #Cyclic Code and #Generator Polynomial:

  • Generator Matrix

    In Cyclic Code world, a Generator Matrix can be constructed using the following formula from #Generator Polynomial:

  • Cyclic Code Encoder

    To encode a #Cyclic Code, we need to construct a circuit including components such as a gate, flip-flop (a register that store value), and modulo-2 adder (or simply a XOR logic gate). Each flip-flop represents \(g_i\) from Generator Polynomial# where \(0 < i < n - k\), and to their right, there should be a modulo-2 adder connected to it depending on the value of \(g_i\). If \(g_i\) is 0, this indicates that there is no connection (otherwise it is a direct connection), thus no modulo-2 adder should be installed to the right of the flip-flop \(g_i\). Initially, all flip-flops store a value of 0, and after the end of each shift round, the value will be shifted to the right. The gate should be connected to the first flip-flop and the last flip-flop. The input will be coming from the right to the left.

  • Cyclic Code
    \(g(D)\) is the Generator Polynomial#

    Due to the nature of Cyclic Code, we can state that a binary polynomial of order \(n-1\) or less is a code word polynomial if and only if it is a multiple of \(g(D)\)#. Multiply a polynomial with \(D^i\) modulus with \(D^n + 1\) can be viewed as a \(i\) right cyclic shift.

#math #encoding