¿La definición de lineal código implica que $E(c_1 + c_2) = E(c_1) + E(c_2)$ para la codificación de la función $E$?

Question

Sé que si $c_1$ $c_2$ son dos codewords en un lineal de código binario $C$,$c_1 + c_2$$C$.

Sin embargo, la definición de los lineales (binario) código (como un subespacio de $\mathbb{F}_2^{n}$) implica que $E(c_1 + c_2) = E(c_1) + E(c_2)$ donde $E$ es alguna función de codificación?

Desde el código de Hamming utiliza un generador de matriz $G$ para generar código, satisface $G(c_1 + c_2) = G(c_1) + G(c_2)$. Es válido para todos los códigos lineales? O, ¿hay códigos lineales que no satisfacen $E(c_1 + c_2) = E(c_1) + E(c_2)$ para la codificación de las funciones de $E$?

Answer 1

Estoy satisfecho con la definición 8 dada en la conferencia nota de Venkatesan Guruswami mencionado por @Clemente C. en un comentario. Se afirma que un lineal de código tiene una transformación lineal para la codificación.

Definición 8 (Generador de matriz y codificación) Deje $C \subseteq \mathbb{F}_q^n$ ser lineal código de dimensión de $k$. Una matriz de $G \in \mathbb{F}_q^{n×k}$ se dice que es un generador de matriz para $C$ si $k$ columnas span $C$.El generador de matriz $G$ proporciona una forma de codificar un mensaje $x \in \mathbb{F}_q^k$ (pensado como un vector columna), como la palabra $Gx \in C \subseteq \mathbb{F}_q^n$. Por lo tanto lineal código tiene una codificación mapa de $E : \mathbb{F}_q^k \to \mathbb{F}_q^n$ que es una transformación lineal $x \to Gx$.

Answer 2

Que No, que no está implícita en la definición de un lineal de código. La definición de un lineal de código no está relacionado con la función de codificación, sólo con el (no asignados) conjunto de codewords.

Un bloque de código de longitud $n$ $2^k$ codewords se llama lineal $(n,k)$ código si y sólo si su $2^k$ codewords formar una $k$-dimensiones subespacio del espacio vectorial de todas las $n$-tuplas más el campo $GF(2)$

(Definición de binario códigos lineales de Lin & Costello):

Así que, estrictamente hablando, ello puede ocurrir por un lineal de código que $E(c_1 +c_2) \ne E(c_1) + E(c_2)$. Por ejemplo:

$$c_1: 00 \to 100$$ $$c_2: 01 \to 110$$ $$c_3: 10 \to 010$$ $$c_4: 11 \to 000$$

Este es un lineal de código (los codewords forman un subespacio lineal), pero la función de codificación no es: $E(c_1+c_2)=E(c_2) \ne E(c_1) + E(c_2)$

Sin embargo, es fácil demostrar que, dado un conjunto de codewords que forman un subespacio (es decir, dado un lineal de código), una función de codificación puede ser utilizada y que también es lineal (y que pueden ser expresados como un generador de matriz, el cual se multiplica por la entrada). Y, en la práctica, que es siempre el preferido.

(Por cierto, que también la razón por la que cada "real" lineal código asigna el cero de entrada para el cero de la palabra - una propiedad que no es estrictamente necesaria para tener un lineal de código, pero para tener un lineal de la función de codificación).