Solving overdetermined linear systems in GF(2)

Question

I have a system $y = Gx$ where $x$ is a $N\times1$ vector and $G$ is a $K\times N$ coding matrix, both with coefficients in $GF(2)$); the output $y$ is therefore a $K\times 1$ vector with coefficients in $GF(2)$. This is an overdetermined system ($K > N$.)

I need to understand options for recovering $x$ given the output $y$, as well as something about error-detection.

I am familiar with solving overdetermined linear systems with regular real numbers via least-squares, and am vaguely familiar with Hamming codes --- this is not a Hamming code, and the coefficients of $G$ are accidental rather than designed.

As an example, suppose I have

$$ G = \begin{bmatrix} 1 & 1 & 0 \cr 1 & 1 & 1 \cr 0 & 1 & 1 \cr 1 & 0 & 0 \cr 0 & 0 & 1 \end{bmatrix}$$

and a sample input $x = \begin{bmatrix}1 & 1 & 0\end{bmatrix}^T$. Then $y = \begin{bmatrix}0& 0& 1 & 1 & 0 \end{bmatrix}^T$.

Suppose also I have a one-bit error $w = \begin{bmatrix}0& 0& 1 & 1 & 0 \end{bmatrix}^T$ To go back from $y$ or $w$ to $x$, I would have to find a pseudo-inverse of $G$, so that $\begin{bmatrix}x|s\end{bmatrix}^T = Hy$ with H being a $5\times 5$ matrix and $s$ is two bits of values that could be used for error detection and maybe correction.

I don't think there are enough coding bits to correct a one-bit error, although I guess I could detect it.

How can I go about finding $H$?

Answer 1

Oh, I think I found it, it's just ordinary Gauss-Jordan elimination, which is always well-conditioned in $GF(2)$. So in the example I posted, here are one possible set of steps:

1. Start with $\begin{bmatrix}G\ |\ I_5\end{bmatrix}$, find first nonzero element of first row:

$$ \left[\begin{array}{ccc|ccccc} \boxed{1} & 1 & 0 & 1 & 0 & 0 & 0 & 0\cr 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \cr 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \cr 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \cr 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \end{array}\right]$$

2. Subtract row 1 from all other rows having a 1 in the same column, then find the first nonzero element of the next rows, which is in row 2:

$$ \left[\begin{array}{ccc|ccccc} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\cr 0 & 0 & \boxed{1} & 1 & 1 & 0 & 0 & 0 \cr 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \cr 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \cr 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \end{array}\right]$$

3. Subtract row 2 from all other rows having a 1 in the same column, then find the first nonzero element of the next rows:

$$ \left[\begin{array}{ccc|ccccc} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\cr 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \cr 0 & \boxed{1} & 0 & 1 & 1 & 1 & 0 & 0 \cr 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \cr 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \end{array}\right]$$

4. Subtract row 3 from all other rows having a 1 in the same column, then there are no more nonzero elements.

$$ \left[\begin{array}{ccc|ccccc} 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0\cr 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \cr 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \cr 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \cr 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \end{array}\right]$$

5. Swap rows to make the upper rows of the left matrix $I_{5,3}$ = $I_3$ in the upper rows with zeros in the remaining rows:

$$ \left[\begin{array}{ccc|ccccc} 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0\cr 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \cr 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \cr 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \cr 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \end{array}\right]$$

6. Now I am left with $\begin{bmatrix}I_{5,3}\ | \ H\end{bmatrix}$, so

$$ H = \begin{bmatrix} 0 & 1 & 1 & 0 & 0\cr 1 & 1 & 1 & 0 & 0 \cr 1 & 1 & 0 & 0 & 0 \cr 0 & 1 & 1 & 1 & 0 \cr 1 & 1 & 0 & 0 & 1 \end{bmatrix}$$

and I can verify that $HG = I_{5,3}$.

Then $\hat{x} = H(y+e)$ where $e$ is additive error, and $\hat{x}$ is a $5\times 1$ vector with decoded data in the first 3 rows and zeros in the other rows for $e=0$. It looks like if $e \neq 0$, then those other rows are always nonzero, but there is not enough information to correct the errors in this case.