Skip to content

Python library able to solve typical coding theory textbook exercises.

Notifications You must be signed in to change notification settings

christiansiegel/coding-theory-algorithms

Repository files navigation

Coding Theory Algorithms

Python library implementing different codes and related algorithms able to solve typical textbook exercises in Aarhus University's 'Information Theory and Coding' course.

Features included:

  • Linear Block Codes
  • Cyclic Codes
  • BCH codes
  • Reed Solomon codes
  • Galois Fields
  • Binary Symmetric Channel

Usage

See playground.py for an implementation of the following two examples. Run with python3 playground.py. Please refer to the code comments for a detailed function description.

Example 1

Exercise

Construct the Galois field GF(25) generated by p(X) = 1 + X2 + X5, showing a table with the polynomial and binary representations of its elements.

Code

p = np.array([1,0,1,0,0,1])
GF25 = GaloisField(p)
GF25.printInfo()

Printed Solution

Construct a GF(2^5) based on primitive
polynomial pi(X) = 1 + X^2 + X^5

Assuming pi(X) has root α, there is
pi(α) = 1 + α^2 + α^5 = 0,
then α^5 = 1 + α^2

Exp. rep.    vector rep.     poly. rep.
-------------------------------------------
0            [0 0 0 0 0]     0
1            [1 0 0 0 0]     1
α            [0 1 0 0 0]     α
α^2          [0 0 1 0 0]     α^2
α^3          [0 0 0 1 0]     α^3
α^4          [0 0 0 0 1]     α^4
α^5          [1 0 1 0 0]     1 + α^2
α^6          [0 1 0 1 0]     α + α^3
α^7          [0 0 1 0 1]     α^2 + α^4
α^8          [1 0 1 1 0]     1 + α^2 + α^3
α^9          [0 1 0 1 1]     α + α^3 + α^4
α^10         [1 0 0 0 1]     1 + α^4
α^11         [1 1 1 0 0]     1 + α + α^2
α^12         [0 1 1 1 0]     α + α^2 + α^3
α^13         [0 0 1 1 1]     α^2 + α^3 + α^4
α^14         [1 0 1 1 1]     1 + α^2 + α^3 + α^4
α^15         [1 1 1 1 1]     1 + α + α^2 + α^3 + α^4
α^16         [1 1 0 1 1]     1 + α + α^3 + α^4
α^17         [1 1 0 0 1]     1 + α + α^4
α^18         [1 1 0 0 0]     1 + α
α^19         [0 1 1 0 0]     α + α^2
α^20         [0 0 1 1 0]     α^2 + α^3
α^21         [0 0 0 1 1]     α^3 + α^4
α^22         [1 0 1 0 1]     1 + α^2 + α^4
α^23         [1 1 1 1 0]     1 + α + α^2 + α^3
α^24         [0 1 1 1 1]     α + α^2 + α^3 + α^4
α^25         [1 0 0 1 1]     1 + α^3 + α^4
α^26         [1 1 1 0 1]     1 + α + α^2 + α^4
α^27         [1 1 0 1 0]     1 + α + α^3
α^28         [0 1 1 0 1]     α + α^2 + α^4
α^29         [1 0 0 1 0]     1 + α^3
α^30         [0 1 0 0 1]     α + α^4

-> The non-zero elements of GF(2^5) are all roots of 1 + X^31.
-> The elements of GF(2^5) are all roots of 1 + X^32.

Example 2

Exercise

A binary linear cyclic code Ccyc(n, k) has code length n = 7 and generator polynomial g(X) = 1 + X2 + X3 + X4.

(a) Find the code rate, the generator and parity check matrices of the code in systematic form, and its Hamming distance. (b) If all the information symbols are ‘1’s, what is the corresponding code vector? (c) Find the syndrome corresponding to an error in the first information symbol, and show that the code is capable of correcting this error.

Code

g = np.array([1,0,1,1,1])
cc = CyclicCode(g, 7)
cc.printInfo()

Printed Solution

-> Linear Block Code Cb( 7 , 3 )
-> Message length (k):              3
-> Codeword length (n):             7
-> Coding rate (R = k/n):           0.42857142857142855
-> Minimum Distance (dmin):         4
-> Error Detection Capability:      3
-> Error Correction Capability (t): 1
-> Weight Distribution (A):         [0 0 0 7 0 0 0]
-> Generator Matrix (G):

[[1 0 1 1 1 0 0]
 [1 1 1 0 0 1 0]
 [0 1 1 1 0 0 1]]

-> Parity Check Matrix (H):

[[1 0 0 0 1 1 0]
 [0 1 0 0 0 1 1]
 [0 0 1 0 1 1 1]
 [0 0 0 1 1 0 1]]

-> Message Codeword Table:

Messages -> Codewords
[0 0 0] [0 0 0 0 0 0 0] m(X) = 0             c(X) = 0
[1 0 0] [1 0 1 1 1 0 0] m(X) = 1             c(X) = 1 + X^2 + X^3 + X^4
[0 1 0] [1 1 1 0 0 1 0] m(X) = X             c(X) = 1 + X + X^2 + X^5
[1 1 0] [0 1 0 1 1 1 0] m(X) = 1 + X         c(X) = X + X^3 + X^4 + X^5
[0 0 1] [0 1 1 1 0 0 1] m(X) = X^2           c(X) = X + X^2 + X^3 + X^6
[1 0 1] [1 1 0 0 1 0 1] m(X) = 1 + X^2       c(X) = 1 + X + X^4 + X^6
[0 1 1] [1 0 0 1 0 1 1] m(X) = X + X^2       c(X) = 1 + X^3 + X^5 + X^6
[1 1 1] [0 0 1 0 1 1 1] m(X) = 1 + X + X^2   c(X) = X^2 + X^4 + X^5 + X^6

-> Parity Check Equations:

c0 = m0 ⊕ m1
c1 = m1 ⊕ m2
c2 = m0 ⊕ m1 ⊕ m2
c3 = m0 ⊕ m2
c4 = m0
c5 = m1
c6 = m2

-> Syndrome Vector Equations:

s0 = r0 ⊕ r4 ⊕ r5
s1 = r1 ⊕ r5 ⊕ r6
s2 = r2 ⊕ r4 ⊕ r5 ⊕ r6
s3 = r3 ⊕ r4 ⊕ r6

-> Standard Array:

0000000 | 1011100 1110010 0101110 0111001 1100101 1001011 0010111 
-----------------------------------------------------------------
1000000 | 0011100 0110010 1101110 1111001 0100101 0001011 1010111 
0100000 | 1111100 1010010 0001110 0011001 1000101 1101011 0110111 
0010000 | 1001100 1100010 0111110 0101001 1110101 1011011 0000111 
0001000 | 1010100 1111010 0100110 0110001 1101101 1000011 0011111 
0000100 | 1011000 1110110 0101010 0111101 1100001 1001111 0010011 
0000010 | 1011110 1110000 0101100 0111011 1100111 1001001 0010101 
0000001 | 1011101 1110011 0101111 0111000 1100100 1001010 0010110 

-> Decoding Table:

Correctable Error Patterns -> Syndromes
[0 0 0 0 0 0 0] [0 0 0 0]
[1 0 0 0 0 0 0] [1 0 0 0]
[0 1 0 0 0 0 0] [0 1 0 0]
[0 0 1 0 0 0 0] [0 0 1 0]
[0 0 0 1 0 0 0] [0 0 0 1]
[0 0 0 0 1 0 0] [1 0 1 1]
[0 0 0 0 0 1 0] [1 1 1 0]
[0 0 0 0 0 0 1] [0 1 1 1]

About

Python library able to solve typical coding theory textbook exercises.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages