Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

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
share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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)$.

share|improve this answer
    
Makes sense, thank you! –  Dan Sandberg Feb 10 '13 at 18:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.