I read a problem from the book "Algebraic Codes for Data Transmission" by Richard E. Blahut:
A linear decoder is a decoder for which the decoder estimates the error pattern from the syndrome $\hat{\mathbf e} = f(\mathbf s)$. Here the syndrome $\mathbf s$ and the error vector $\mathbf e$ are related by $\mathbf s = \mathbf e \cdot \mathbf H^T$, and $\mathbf H$ is the parity-check matrix of a binary linear code $\mathbb C$.
They want me to show that a linear decoder for $\mathbb C$ can correct at most $n − k$ of the $n$ possible single-symbol errors, and conclude that a well-performing decoder must be equivalent to a non-linear mapping.
I'm vary confused about where to start. Could anyone help me out? Thanks!
$H$ is $(n-k)\times n$ dimensional therefore the syndrome has dimension $n-k.$ Now each of the weight one errors span a space of dimension one and they're linearly independent. So a syndrome can distinguish at most $n-k$ out of these $n$ possible single error vectors.