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
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.
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.
p = np.array([1,0,1,0,0,1])
GF25 = GaloisField(p)
GF25.printInfo()
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.
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.
g = np.array([1,0,1,1,1])
cc = CyclicCode(g, 7)
cc.printInfo()
-> 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]