Teorema de McWilliams

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de mayo de 2019; las comprobaciones requieren 2 ediciones .

En la teoría de la codificación, el teorema de McWilliams establece una conexión entre la función de peso de un código lineal y la función de peso de su código dual . Una de las consecuencias del teorema es obtener un límite superior en la cardinalidad de un código. Nombrado en honor a la inglesa Florence McWilliams

Sea un código lineal binario de longitud . La distribución de peso del código es una secuencia numérica donde denota el número de palabras de código con peso : ${\displaystyle C\subconjunto \mathbb {F} _{2}^{n))$ $norte$ $C$ $\{A_{w}\}_{w=0}^{n},$ ${\ estilo de visualización \ estilo de visualización A_ {w}}$ $C$ $w$

A_{w}=\#\{c\in C\mid {\mathsf {w}}(c)=w\}

La función de peso (o enumerador de peso ) es un polinomio de dos variables

W(C;x,y)=\sum _{w=0}^{n}A_{w}x^{w}y^{nw}.

Propiedades elementales de la función de peso

${\ estilo de visualización \ estilo de visualización W (C; 0,1) = A_ {0} = 1.}$
$\displaystyle W(C;1,1)=\sum _{w=0}^{n}A_{w}=|C|.$
${\ estilo de visualización \ estilo de visualización W (C; 1,0) = A_ {n} = 1,}$ cuando de otra manera ${\ estilo de visualización (1, \ ldots, 1) \ en C,}$ ${\ estilo de visualización \ estilo de visualización W (C; 1,0) = A_ {n} = 0.}$
$\displaystyle W(C;1,-1)=\sum _{w=0}^{n}A_{w}(-1)^{nw}=A_{n}+(-1)^ {1}A_{n-1}+\ldots +(-1)^{n-1}A_{1}+(-1)^{n}A_{0}.$

Enunciado del teorema

Denote el código dual por $C$

C^{\perp}=\{x\in \mathbb {F}_{2}^{n}\,\mid \,\forall c\in C:\langle x,c\rangle =0 {\mbox{ }}\},

donde denota el producto escalar de vectores en un espacio vectorial . ${\ estilo de visualización \ ángulo \,, \, \ ángulo}$ $\mathbb{F}_2^n$

El teorema de McWilliams dice que

W(C^{\perp };x,y)={\frac {1}{\mid C\mid }}W(C;yx,y+x).

Literatura

Pless V. Introducción a la teoría de los códigos correctores de errores . - Wiley, Nueva York, § 8.2, 1998.
Lint van JH Introducción a la teoría de la codificación . — Springer-Verlag, Berlín, § 3.5, 1999.
Roth R.M. Introducción a la teoría de la codificación . - Prensa de la Universidad de Cambridge, Cambridge, § 4.4, 2006.

Véase también

Polinomios de Kravchuk
teorema de Delsarte