¿Un buen decodificador debe ser no lineal?

Question

Leí un problema del libro "Algebraic Codes for Data Transmission" de Richard E. Blahut:

Un decodificador lineal es un decodificador para el cual el decodificador estima el patrón de error a partir del síndrome $\hat{\mathbf e} = f(\mathbf s)$. Aquí el síndrome $\mathbf s$ y el vector de error $\mathbf e$ están relacionados por $\mathbf s = \mathbf e \cdot \mathbf H^T$, y $\mathbf H$ es la matriz de comprobación de paridad de un código lineal binario $\mathbb C$.

Quieren que demuestre que un decodificador lineal para $\mathbb C$ puede corregir como máximo $n k$ de los $n$ posibles errores de un solo símbolo, y concluir que un decodificador de alto rendimiento debe ser equivalente a un mapeo no lineal.

Estoy muy confundido acerca de por dónde empezar. ¿Alguien podría ayudarme? ¡Gracias!

Answer 1

$H$ es $(n-k)\times n$ dimensional por lo tanto el síndrome tiene dimensión $n-k.$ Ahora cada uno de los errores de peso uno abarca un espacio de dimensión uno y son linealmente independientes. Así que un síndrome puede distinguir como máximo $n-k$ de estos $n$ posibles vectores de error únicos.