Coding theory: transform generator matrix to standard form

This matrix calculator uses the techniques described in A First Course in Coding Theory by Raymond Hill [HILL86] to transform a generator matrix or parity-check matrix of a linear [n,k]-code into standard form. It works over GF(q) for q = 2,3,4*,5,7,11.

You have the option either to transform a k x n generator matrix G into standard form G'=[Ik|A] or to transform an (n-k) x n parity-check matrix H into standard form H'=[B|In-k]. When the generator/parity-check matrix is finally in standard form, it will also show the equivalent standard-form parity-check/generator matrix. Just select the value of q and the direction you want to go.

You can also use this to solve the matrix equation [A]x = b over GF(q) by entering an n x (n+1) augmented matrix [A|b] as G. See Solving Ax = b over GF(q) below.

Please read the disclaimer below before using this. If you don't understand this so far, give up, it's not for you.

Enter each row of the matrix on a separate line, with the elements separated by a space (or a comma). Try some of the examples below.

   Direction:

* In GF(4)={0,1,α,α2} use the number 2 for α and 3 for α2, so 1+1=2+2=3+3=0, 2+1=3, 3+1=2, 2+3=1; 2x2=3, 3x3=2, 2x3=1.





Some example matrices

Copy and paste one of these example matrices into the box above to test (the rows of numbers in yellow). Make sure you select the correct options for the modulus, q, and direction.
Example matrix(options) Standard form Equivalent
GF(2) G=
0 1 1 0 0 0 1
1 1 1 1 1 1 1
1 0 0 0 1 0 1
1 1 0 0 0 1 0
q = 2
G → •
G'=[I|A]=
1 0 0 0 1 0 1
0 1 0 0 1 1 1
0 0 1 0 1 1 0
0 0 0 1 0 1 1
H=[-A^T|I]
1 1 1 0 1 0 0
0 1 1 1 0 1 0
1 1 0 1 0 0 1
GF(3) G=
2 1 0 0 1
1 2 1 2 0
1 0 2 1 1
q = 3
G → •
G'=[I|A]=
1 0 0 0 2
0 1 0 0 0
0 0 1 2 1
H=[-A^T|I]
0 0 1 1 0
1 0 2 0 1
GF(5) H=
0 1 1 3 3
1 0 2 3 1
q = 5
H → •
H'=[B|I]=
3 4 0 1 0
2 3 2 0 1
G=[I|-B^T]=
1 0 0 2 3
0 1 0 1 2
0 0 1 0 3
GF(5) H=
2,4,2,3,0
0,2,0,2,4
3,0,0,1,4
q = 5
H → •
H'=[B|I]=
3 4 1 0 0
2 2 0 1 0
4 2 0 0 1
G=[I|-B^T]=
1 0 2 3 1
0 1 1 3 3
GF(4) G=
1 2 1 0 0
0 1 2 1 0
0 0 1 2 1
q = 4
G → •
G'=[I|A]=
1 0 0 1 2
0 1 0 2 2
0 0 1 2 1
H=[-A^T|I]
1 2 2 1 0
2 2 1 0 1
GF(11) G=
1 1 1 1 6
2 4 6 7 0
4 5 3 5 4
8 9 7 2 5
q = 11
G → •
G'=[I|A]=
1 0 0 0 10
0 1 0 0 2
0 0 1 0 8
0 0 0 1 8
H=[-A^T|I]
1 9 3 3 1

Note that this computation G→G' is also the transform of an augmented matrix of the form [A | b] to the form [I_4 | x], where A is a 4x4 matrix, I_4 is the 4x4 identity matrix, and b and x are 4x1 column vectors. This solves the equation Ax = b over GF(11). The solution in the above example should be xT = (10 2 8 8).


Solving Ax = b over GF(q)

You can solve the matrix equation [A]x = b in GF(q) for the n x n matrix [A] by entering the augmented matrix [A | b] as G. The standard form G' = [I_n | x] gives the solution for x.

For example, to solve Ax = b for x over GF(11) where
A = 1 1 1 1  b = 6
    2 4 6 7      0
    4 5 3 5      4
    8 9 7 2      5
enter G in the box above as follows:
1 1 1 1 6
2 4 6 7 0
4 5 3 5 4
8 9 7 2 5
Then select q = 11 and direction G → H. You should get the standard form G′ =
1 0 0 0 10
0 1 0 0 2
0 0 1 0 8
0 0 0 1 8
giving the solution xT = (10 2 8 8).

Reference

Disclaimer

DISCLAIMER: Provided as is with no warranties. Use at your own risk. This page is intended only for individuals wishing to check the results of their own calculations independently. It must not be used to answer assignment questions! We have done such complete and thorough testing of the code behind this page that we are confident the results will be 100% accurate under all possible circumstances and for all possible extreme inputs you may care to try. Yeah, sure we have. Please carry out whatever checks you consider necessary and make your own call on the results.

See also our other matrix calculator which transforms a matrix to row canonical form (row-reduced echelon form, RREF).

To comment on this page or to tell us about a problem please send us a message. Go to our Mathematics page.

Copyright © 2011-20 David Ireland <www.di-mgt.com.au>.

Last updated: 14 August 2020 01:11Z