How to compute generator matrix from a parity check matrix?

Question

I have a parity matrix ("H") that is not in canonical form (the identity matrix is not on the right side).

I'm trying to programatically calculate the generator matrix ("G") from it.

The Wikipedia entry on Hamming codes talks about the relationship between parity check matrixes and generator matrixes:

http://en.wikipedia.org/wiki/Hamming_code

It says that H*transpose(G)=0

I thought I could figure out G by taking the Nullspace of H. However, I end up with many fractional numbers and don't know how to use that. The examples I've seen use gauss-jordan elimination to put the matrix into row-echelon form. However, shouldn't I be able to do it numerically using svd or something like that?

Here's some code where I multiply a message by a generator matrix (the example is taken from Wikipedia). I would like to get the same message when I multiply by the generator that I have calculated.

import numpy as np
import scipy.linalg

def nullspace(A, atol=1e-13, rtol=0):
    A = np.atleast_2d(A)
    u, s, vh = np.linalg.svd(A)
    tol = max(atol, rtol * s[0])
    nnz = (s >= tol).sum()
    ns = vh[nnz:].conj().T
    return ns

H = np.mat( [[1,1,1,1,0,0],
             [0,0,1,1,0,1],
             [1,0,0,1,1,0]] )

G = np.mat( [[1,0,0,1,0,1],
             [0,1,0,1,1,1],
             [0,0,1,1,1,0]] )

M = np.mat( [1,0,1] )

print "Message * generator=", M*G

GT2 = nullspace(H)
G2 = GT2.T

print "Message * calculated generator=", M*G2

Answer 1

With forward-error-correcting coding, one is working in a finite field, typically the field of two elements denoted by GF$(2)$ or $\mathbb F_2$. So, there are no fractional numbers and no fancy methods such as singular value decomposition: you use bit-by-bit XOR additions of the rows of $H$ and Gauss-Jordan elimination to reduce $H$ to row-echelon form $[P_{(n-k)\times k} \mid I_{(n-k)\times(n-k)}]$.

Then, set $G = [I_{k\times k} \mid (P^T)_{k\times(n-k)}]$ and you are done. (For nonbinary fields, use $[I \mid -P^T]$). Note that all arithmetic in the verification $HG^T = 0$ is also finite field arithmetic with $1\cdot 1 =1$ and $1+1 = 0 = 1\oplus 1$ for the case of GF$(2)$.