Código de la caña-Muller

Los códigos de la caña-Muller son una familia de códigos lineales que corrigen el error usados en comunicaciones. Los códigos de la caña-Muller pertenecen a las clases de códigos en la localidad verificables y en la localidad decodable códigos, que es por qué son útiles en el diseño de probabilistically checkable pruebas en la teoría de la complejidad computacional. Se nombran por Irving S. Reed y David E. Muller. Muller descubrió los códigos, y Reed propuso la lógica de la mayoría que descifra por primera vez. Los casos especiales de códigos de la Caña-Muller incluyen el código de Hadamard, el código de Walsh-Hadamard y el código de la Caña-Solomon.

Los códigos de la caña-Muller se ponen en una lista como RM (d, r), donde d es el pedido del código, y r determina la longitud del código, n = 2. Los códigos de RM se relacionan con funciones binarias en GF de campaña (2) sobre los elementos {0, 1}.

RM (0, r) los códigos son códigos de repetición de la longitud n = 2, precio y distancia mínima d = n.

RM (1, r) los códigos son códigos del control de la paridad de la longitud n = 2, precio y distancia mínima.

RM (r − 1, r) los códigos son códigos del control de la paridad de la longitud n = 2.

RM (r − 2, r) los códigos son la familia de Códigos Hamming ampliados de la longitud n = 2 con la distancia mínima d = 4.

Construcción

Una matriz de generación para un Reed–Muller el código de la longitud n = 2 se puede construir como esto. Vamos a escribir:

:

Note que cada miembro del juego X es un punto en. Definimos en el espacio n-dimensional los vectores del indicador

:

en subconjuntos por:

:

juntos con, también en, la operación binaria

:

referido como el producto de la cuña (este producto de la cuña no se debe confundir con el producto de la cuña definido en el álgebra exterior). Aquí, y son

los puntos en, y la operación son la multiplicación habitual en el campo.

es un espacio vectorial d-dimensional sobre el campo, por tanto es posible escribir

Definimos en el espacio n-dimensional los vectores siguientes con la longitud n: v = (1, 1, 1, 1, 1, 1, 1, 1) y

:

donde los H son hiperaviones en (con la dimensión d −1):

:

EL

Reed–Muller RM (d, r) el código de la orden r y longitud n = 2 es el código generado por v y los productos de la cuña de hasta r del v (donde según la convención un producto de la cuña de menos de un vector es la identidad para la operación).

Ejemplo 1

Deje a r = 3. Entonces n = 8, y

:

y

:

\begin {}de la matriz \

v_0 & = & (1,1,1,1,1,1,1,1) \\[2pt]

v_1 & = & (1,0,1,0,1,0,1,0) \\[2pt]

v_2 & = & (1,1,0,0,1,1,0,0) \\[2pt]

v_3 & = & (1,1,1,1,0,0,0,0). \\

\end {}de la matriz \

</matemáticas>

El RM (1,3) código es generado por el juego

:

o más explícitamente por las filas de la matriz

:

\begin {pmatrix }\

1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\

1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\

1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\

1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\

\end {pmatrix }\

</matemáticas>

Ejemplo 2

El RM (2,3) código es generado por el juego:

:

o más explícitamente por las filas de la matriz:

:

\begin {pmatrix }\

1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\

1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\

1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\

1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\

1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\

1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\

1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\

\end {pmatrix }\

</matemáticas>

Propiedades

Las propiedades siguientes sostienen:

1 El juego de todos los productos de la cuña posibles de hasta d del v forman una base para.

2 el RM  (d, r) el código tiene la fila

::

3 RM  (d, r) = RM  (d &minus; 1, r) | RM  (d &minus; 1, r &minus; 1) donde '|' denota el producto de la barra de dos códigos.

4 RM  (d, r) tiene el peso de Hamming mínimo 2.

Prueba

1

Los:There son

::

Los vectores de:such y tienen la dimensión n por tanto es suficiente comprobar que los vectores n atraviesan; equivalentemente es suficiente comprobar que RM (d, d) =.

:Let x ser un elemento de X y definir

::

:Then

El:Expansion vía el distributivity del producto de la cuña da. Entonces desde la envergadura de vectores tenemos RM (d, d) =.

2

:By 1, todos tales productos de la cuña deben ser en línea recta independientes, por tanto la fila de RM (d, r) debe ser simplemente el número de tales vectores.

3

:Omitted.

4

Inducción de:By.

:The RM (d, 0) el código es el código de repetición de longitud n =2 y peso n = 2 = 2. Por 1 RM (d, d) = y tiene el peso 1 = 2 = 2.

El producto de la barra del artículo de:The (cifrando la teoría) da una prueba que el peso del producto de la barra de los dos códigos C, C da

::

:If 0

:: el ii) RM (d-1, r-1) tiene el peso 2 = 2

El:then el producto de la barra tiene el peso

::

Construcción alternativa

Un código de la Caña-Muller RM (r, m) existe para cualquier número entero y. RM (m, m) se define como el universo código. RM (&minus;1,m) se define como el código trivial . Los códigos de RM restantes se pueden construir de estos códigos elementales usando la construcción que dobla la longitud

:

De esta construcción, RM (r, m) es un código del bloque lineal binario (n, k, d) con la longitud n = 2, dimensión y distancia mínima para. El código dual a RM (r, m) es RM (m-r-1, m). Esto muestra que la repetición y los códigos de SPC son duals, biorthogonal y los Códigos Hamming ampliados son duals y que los códigos con k=n/2 son autoduales.

Construcción basada en polinomios del grado bajo sobre un campo finito

Hay el otro, manera simple de construir códigos de la Caña-Muller basados en polinomios del grado bajo sobre un campo finito. Esta construcción en particular se satisface para su aplicación como códigos en la localidad verificables y en la localidad decodable códigos.

Deje ser un campo finito y dejar y ser números enteros positivos, donde se debería pensar como más grande que. Vamos a codificar mensajes que consisten en elementos de como palabras en clave de la longitud así: interpretamos el mensaje como un - el polinomio de la variante aleatoria del grado como máximo con el coeficiente de. Tal polinomio tiene coeficientes. La codificación de la Caña-Muller de es la lista de las evaluaciones de en todos; la palabra en clave en la posición puesta índice por tiene el valor.

Mesa de Reed–Muller códigos

La mesa debajo de listas el RM (r, m) códigos de longitudes hasta 32.

Descifre códigos de RM

RM (r, m) los códigos se pueden descifrar usando el descifre lógico de la mayoría. La idea básica del descifre lógico de la mayoría es

construir varias sumas de control para cada elemento de la palabra del código recibido. Ya que cada una de las sumas de control diferentes debe todo

tenga el mismo valor (es decir el valor del peso del elemento de la palabra del mensaje), podemos usar un descifre de la lógica de la mayoría para descifrar

el valor del elemento de la palabra del mensaje. Una vez que cada pedido del polinomio se descifra, la palabra recibida se modifica

en consecuencia quitando las palabras en clave correspondientes cargadas por las contribuciones del mensaje descifradas, hasta ahora etapa.

Así pues para un código de RM de pedido de rth, tenemos que descifrar iterativamente r+1, tiempos antes de que lleguemos al final

palabra en clave recibida. También, los valores de los trozos del mensaje se calculan a través de este esquema; finalmente podemos calcular

la palabra en clave multiplicando la palabra del mensaje (sólo descifrado) con la matriz del generador.

Una pista si el descifre tuviera éxito, debe tener la palabra recibida modificada de un todo-cero, al final de (r + 1) - etapa que descifra

a través del descifre lógico de la mayoría. Esta técnica fue propuesta por Irving S. Reed y es más general cuando aplicado

a otros códigos de la geometría finitos.

Notas

Artículos de investigación:

Libros de texto:

Enlaces externos



Buscar