- Cyclic Code: A linear block code where shifting the bits of a codeword by any amount (left or right, with carry/wraparound) results in another valid codeword
- Generator Polynomial: The polynomial of minimal degree (smallest power) from a cyclic code that is non-zero which "generates" every other codeword in the code by multiplying itself with the input bits

- Codewords in cyclic codes are represented as polynomials
- 1101000 = 1 + 1X + 0X
^{2}+ 1X^{3}= 1 + X + X^{3} - 0110100 = 0 + 1X + 1X
^{2}+ 0X^{3}+ 1X^{4}= X + X^{2}+ X^{4}

- 1101000 = 1 + 1X + 0X
- Polynomials in turn can also be represented as the
quotient and remainder by dividing the polynomial with another
- v(X) = q(X)j(X) + b(X)
- q(X) and b(X) are the quotient and remainder of dividing v(X) by j(X)

- The basis polynomial for the rest of the codewords in the cyclic code
- denoted g(X)
- Codeword = input*g(X)
- Input = (1100) = 1 + X
- g(X) = (1101) = 1 + X + X
^{3} - codeword = Input*g(X) = (1+X)(1+X+X
^{3}) =

1 + X + X^{3}+ X + X^{2}+ X^{4}=

1 + X^{2}+ X^{3}+ X^{4}=

(1011100) for a (7,4) code- X + X = 0 since modulo 2 addition for binary GF(2)

- The above method of encoding the input doesn't gurantee the result is systematic (ordered by parity bits then info bits)
- To generate systematic codewords, you encode via the following:
- Multiply input u(X) by X
^{n-k} - Divide result by g(X), remainder = b(X)
- Output codeword = u(X)X
^{n-k}+ b(X)

- Multiply input u(X) by X

- Systematic Generator and Parity Check matrices are made via:
- for i=0, 1, ... k-1
- divide X
^{n-k-i}by g(X) and save remainder as b_{i}- b
_{i}= b_{i,0}+ b_{i,1}X + ... b_{i,n-k-1}X^{n-k-1}

- b

- divide X
- Form the generator matrix
**G**in the following format:- Each row is [b
_{i}| u^{i}], where u^{i}is a zero vector except for a 1 in the i^{th}position

- Each row is [b
- Form the parity matrix
**H**in the following format- The first (n-k) columns are the identity matrix
- The remaining k columns are the remainders calculated in step 1

- for i=0, 1, ... k-1

- A circuit for encoding can be made by extracting values from either g(X) or values from the parity check matrix
- An encoding circuit using the generator polynomial looks like:
- For each g
_{1}...g_{n-k-1}its corresponding adder (+) is only placed in the circuit if g_{i}is 1 (otherwise you're just adding 0 at each point)

- For each g
- For example, encoding the (7,4) code with g(X) = 1 + X + X
^{3}, and input u(X) = (1011) - A similar circuit and process can be made using the parity matrix values (shown in book as well)