Códigos correctores óptimos mediante técnicas elementales
Abstract
Grado en Matemáticas
Full text
Facultad de Ciencias Trabajo Fin de Grado Grado en Matemáticas Códigos correctores óptimos mediante técnicas elementales Autora: Cristina Martínez de Ilarduya Alcaide Tutor: José Enrique Marcos Naveira
“Do not go where the path may lead, go instead where there is no path and leave a trail.” Ralph Waldo Emerson Agradecimientos: Me gustar´ıa mostrar mi m´as sincero agradecimiento a Jos´e Enrique, mi tutor, por su implicaci´on y su atenci´on constante.
´ Indice general Introducci´on III 1. Cuerpos finitos 1 2. C´odigos lineales en bloque 5 2.1. C´odigosdivisibles..................................... 9 2.2. Cotas de c´odigos lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3. Decodificaci´on de c´odigos lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3. C´odigos lineales binarios con t´ecnicas elementales 15 3.1. C´odigo lineal binario ´optimo de par´ametros [15,5,7]2................. 16 3.2. C´odigo lineal binario ´optimo de par´ametros [20,5,9]2................. 20 3.3. C´odigo lineal binario ´optimo de par´ametros [28,7,12]2................. 25 3.4. C´odigo lineal binario ´optimo de par´ametros [77,7,36]2................. 28 3.5. C´odigo lineal binario ´optimo de par´ametros [93,8,44]2................. 30 3.6. C´odigo lineal binario ´optimo de par´ametros [120,9,56]2................ 32 3.7. C´odigos lineales binarios de par´ametros [26,6,11]2y [20,6,8]2............ 34 3.8. C´odigos lineales binarios de par´ametros [120,8,57]2y [121,8,58]2.......... 37 3.9. C´odigos lineales binarios de par´ametros [171,9,72]2y [135,9,63]2.......... 40 3.10. C´odigos lineales binarios de par´ametros [250,10,114]2y [240,10,112]2........ 43 3.11. C´odigo lineal binario de par´ametros [130,9,58]2.................... 46 3.12. C´odigo lineal binario de par´ametros [262,10,120]2................... 47 4. Construcciones sencillas basadas en el c´odigo simplex binario 51 4.1. C´odigo lineal binario ´optimo de par´ametros [95,6,48]2................. 53 4.2. C´odigo lineal binario ´optimo de par´ametros [119,6,60]2................ 55 4.3. C´odigo lineal binario ´optimo de par´ametros [191,7,96]2................ 57 4.4. Otras construcciones con el c´odigo simplex binario . . . . . . . . . . . . . . . . . . . 58 4.4.1. C´odigo lineal binario ´optimo de par´ametros [94,7,46]2............ 58 4.4.2. C´odigo lineal binario ´optimo de par´ametros [190,7,95]2............ 59 i
4.4.3. C´odigo lineal binario ´optimo de par´ametros [254,9,126]2........... 60 5. Un c´odigo distinto 63 6. C´odigos ´optimos con la construcci´on (u|u+v)67 7. C´odigos lineales ternarios 69 7.1. C´odigosimplexternario ................................. 69 7.2. Construcci´on (u+v+w|2u+v|u) .......................... 71 7.2.1. C´odigo lineal ternario ´optimo de par´ametros [18,9,6]3............. 72 7.3. C´odigo Reed-Muller ternario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 7.3.1. C´odigo Reed-Muller ternario R3(1, m) ..................... 73 7.3.2. C´odigo Reed-Muller ternario R3(2, m) ..................... 75 7.3.3. C´odigo Reed-Muller ternario R3(3, m) ..................... 77 7.3.4. C´odigo Reed-Muller ternario R3(r, m) ..................... 78 7.4. C´odigos lineales ternarios obtenidos con Maple .................... 80 7.4.1. C´odigo lineal ternario de par´ametros [21,6,10]3................ 81 7.4.2. C´odigo lineal ternario de par´ametros [42,7,20]3................ 82 7.4.3. C´odigo lineal ternario ´optimo de par´ametros [126,6,81]3........... 83 Bibliograf´ıa 89 ii
Introducci´on La teor´ıa de los c´odigos correctores de errores tiene su origen en el art´ıculo [Sha] de C.E. Shannon publicado en . Los c´odigos correctores de errores se utilizan en la industria cuando se quiere enviar una informaci´on a trav´es de un canal sujeto a ruido. Un c´odigo corrector a˜nade informaci´on extra al mensaje que se quiere transmitir con el fin de recuperar la informaci´on enviada. El siguiente diagrama proporciona una representaci´on visual de un sistema de transmisi´on de informaci´on general: Emisor //Codificaci´on //Canal //Decodificaci´on //Receptor Ruido OO Los denominados c´odigos en bloque transmiten la informaci´on en palabras de la misma longitud. Dentro de los c´odigos en bloque, los c´odigos lineales son los m´as estudiados debido a que su estructura permite utilizar las herramientas del ´algebra lineal tanto para obtener resultados te´oricos como para su manejo pr´actico. El objetivo del presente Trabajo de Fin de Grado es el estudio de los c´odigos lineales sobre cuerpos finitos con el prop´osito de hallar t´ecnicas elementales que nos permitan construir c´odigos ´optimos, pues no hay un m´etodo expl´ıcito para construir una familia de estos c´odigos. En el primer cap´ıtulo, de car´acter introductorio, mostramos las nociones b´asicas de cuerpos finitos necesarias para cualquier curso de teor´ıa de c´odigos. En un primer momento, nuestra intenci´on fue profundizar m´as en estas ideas. Sin embargo, hemos acabado centr´andonos en c´odigos sobre los cuerpos F2yF3. No obstante, por su inter´es, hemos decidido no eliminar gran parte del contenido de este cap´ıtulo. En el cap´ıtulo exponemos los c´odigos lineales. Tratamos el concepto de matriz generadora, matriz de control y diferentes propiedades de los c´odigos. Adem´as, se muestran diversas cotas de c´odigos y la decodificaci´on general propia de c´odigos lineales. En los siguientes tres cap´ıtulos se presentan los c´odigos lineales binarios, algunos de ellos ´optimos, que hemos conseguido hallar con diferentes t´ecnicas, tras multitud de ensayos fallidos. La mayor´ıa de estos c´odigos me han sido sugeridos por mi tutor [Mar]. Hemos utilizado tambi´en otros m´etodos como, por ejemplo, el que sugiere [Til]. El inter´es principal de estos c´odigos es la cualidad de ser ´optimos, si bien tambi´en hemos valorado los c´odigos con pocos pesos, dos o tres pesos no nulos, y la propiedad de autoortogonalidad. Asimismo, destaca el hecho de poder calcular a mano la distribuci´on de pesos del c´odigo. Nos hemos limitado a longitudes de los c´odigos peque˜nas, n≤, para poder cotejarlos con las tablas de [Grassl] y as´ı iii
saber si nos acerc´abamos a c´odigos ´optimos. No obstante es obvio que t´ecnicas tan elementales no tienen l´ımite y f´acilmente pueden proporcionar c´odigos an´alogos de par´ametros mucho mayores. Posteriormente, aplicando estas t´ecnicas a c´odigos lineales ternarios, hemos obtenido resultados muy pobres. Para estos c´odigos ha sido necesario el uso de ordenador, nosotros hemos utilizado el software Maple. A pesar de ello, describimos otros procedimientos que resultan m´as interesantes, como el c´odigo simplex ternario y la construcci´on (u+v+w|2u+v|u). A continuaci´on se expone c´omo, a partir de este ´ultimo m´etodo, se han construido los c´odigos Reed-Muller ternarios de la forma que dicta [KsPa]. Es posible que c´odigos similares con mayor longitud valgan para ser utilizados en t´ecnicas criptogr´aficas. Un ejemplo es el uso de c´odigos en el criptosistema McEliece. Los c´odigos tambi´en tienen aplicaci´on en combinatoria y teor´ıa de grafos, as´ı como en esquemas de compartici´on de secretos, protocolos seguros (multi-party computation) y autenticaci´on, entre muchas otras. iv
Cap´ıtulo 1 Cuerpos finitos Este cap´ıtulo est´a dedicado a la presentaci´on de algunas de las ideas y resultados b´asicos de la teor´ıa de cuerpos finitos que se utilizan en la teor´ıa de c´odigos correctores de errores. Las demostraciones de estos enunciados pueden encontrarse en [LiPi], cap´ıtulo y en [MuTe], cap´ıtulos y. Sea pun n´umero primo, quna potencia de un primo, es decir q=pn. Se dan por conocidos los cuerpos finitos primos Fp= (Z/(p),+,·) y se sabe que existe un ´unico cuerpo finito primo para cada primo p, salvo isomorfismos. Un cuerpo finito de qelementos se denota por Fq=GF(q). Sea Aun anillo o cuerpo de caracter´ıstica p, entonces para todo a, b ∈Ay todo n∈Nse cumple (a+b)p=ap+bp(a+b)pn=apn+bpn Teorema 1 Sea Kun cuerpo finito, entonces su caracter´ıstica es un primo p, el cuerpo tiene pn elementos y es una extensi´on de grado ndel cuerpo primo Fp. Sea P(X)∈Fp[X] un polinomio irreducible de grado n≥2, entonces Fp[X]/(P(X)) es un cuerpo con pnelementos. Teorema 2 Sea q=pn. El cuerpo finito Fqes exactamente el conjunto de ra´ıces del polinomio Xq−X∈Fp[X]. En consecuencia, Fqes el cuerpo de descomposici´on de dicho polinomio sobre Fp. Luego dos cuerpos con pnelementos son isomorfos. Para cada potencia de un primo pnexiste un ´unico cuerpo con pnelementos, salvo isomorfismo. Teorema 3 El cuerpo GF(pn)tiene exactamente un subcuerpo con pdelementos para cada divisor d|n. No hay otros subcuerpos de GF(pn). Teorema 4 Sea q=pny el cuerpo Fq. Su grupo aditivo es isomorfo a (Fq,+) ∼ =( nveces z }| { Z/(p)× · · · × Z/(p),+) Su grupo multiplicativo (Fq\ {0},·)es c´ıclico de orden pn−1. Luego, Fqtiene exactamente ϕ(pn−1) elementos cuyo orden multiplicativo es q−1 = pn−1. Considerando la correspondiente propiedad de los grupos c´ıclicos finitos, para cada d∈Nque divide a q−1 = pn−1, el cuerpo Fqtiene exactamente ϕ(d) elementos de orden multiplicativo d. Adem´as, todo elemento no nulo de Fqes una ra´ız de la unidad. Un elemento de Fqcuyo orden multiplicativo es q−1 se denomina elemento primitivo del cuerpo, o ra´ız primitiva. 1
Precisamos lo que se entiende por c´odigos equivalentes y c´odigo sistem´atico. Dos c´odigos lineales C1,C2son equivalentes si se puede obtener uno del otro realizando las operaciones siguientes: •Existe una permutaci´on σdel conjunto {1,2, . . . , n}tal que C2=n(xσ(1), xσ(2), . . . , xσ(n)):(x1, x2, . . . , xn)∈ C1o •Multiplicando la componente en una posici´on fija de todos los elementos de C1por una constante no nula de Fq. Dos c´odigos equivalentes tienen los mismos par´ametros, [n, k, d]q. Un [n, k, d]q-c´odigo Cse denomina sistem´atico si una de sus matrices generadoras es de la forma G= [Ik, A], donde Ikes la matriz identidad de orden kyAes una matriz de orden k×(n−k). Si esto ocurre, decimos que la matriz generadora est´a en la forma est´andar. En este caso, la operaci´on de codificaci´on de un mensaje original proporciona un mensaje donde las kprimeras coordenadas del vector codificado es el propio mensaje original y las (n−k) restantes coordenadas son los llamados s´ımbolos de control. Si la matriz generadora G= [Ik, A] est´a en la forma est´andar, entonces la matriz H= [−At, In−k] es una matriz de control del c´odigo. En este caso decimos que la matriz de control est´a en la forma est´andar. Proposici´on 34 Todo c´odigo lineal es equivalente a uno sistem´atico. Demostraci´on: Sea el c´odigo Cde par´ametros [n, k, d] sobre Fq. La dimensi´on de Ces k, entonces una matriz generadora Gde Ctiene orden k×ny rango k, luego posee kcolumnas linealmente independientes. Mediante una permutaci´on σdel conjunto {1,2, . . . , n}podemos conseguir que estas columnas sean las kprimeras. As´ı, se obtiene una matriz G0= [A, B] con Aregular, de tama˜no k×k. Ahora, mediante una sucesi´on de operaciones elementales (m´etodo de Gauss) puede transformarse Aen la matriz identidad Ik. Si estas operaciones se realizan en la matriz G0, obtenemos una matriz en forma est´andar cuyas filas generan el mismo espacio que las de G0y que es, por tanto, un c´odigo sistem´atico equivalente al que tiene a Gpor matriz generadora. El siguiente resultado permite calcular la distancia m´ınima a partir de la matriz de control del c´odigo, en lugar de calcular el peso de todas sus palabras. Teorema 35 Sea un c´odigo lineal con matriz de control H. La distancia m´ınima ddel c´odigo es el valor que cumple lo siguiente: Todo subconjunto de d−1columnas de Hes linealmente independiente; existe un subconjunto de dcolumnas linealmente dependientes. Demostraci´on: Sea dla distancia m´ınima y a su vez el peso m´ınimo del c´odigo. Sea Hla matriz de control con columnas u1, . . . , un. Si se toma un vector v= (a1, . . . , an) no nulo de peso menor que el peso m´ınimo del c´odigo d,vno est´a en el c´odigo. Entonces, 0 6=Hvt=a1u1+· · · +anun, es decir, cada d−1 columnas de Hson linealmente independientes. Ahora, si se toma un vector x, que pertenezca al c´odigo, de peso exactamente el peso m´ınimo d, sabemos que 0 = Hxt, luego en Hhay dcolumnas linealmente independientes. Sabemos que todo subespacio vectorial es un subgrupo. Es curioso el hecho de que sobre los cuerpos finitos primos Fpse satisface la implicaci´on rec´ıproca. 8
Proposici´on 36 Sea pprimo. Sea Fn pconsiderado espacio vectorial sobre Fp. Sea Vun subgrupo de Fn p, entonces Ves un subespacio vectorial de Fn p. Definimos ahora lo que se entiende por c´odigo ´optimo. Definici´on 37 Un c´odigo lineal de par´ametros [n, k, d]qse dice ´optimo si no existe ning´un otro c´odigo con par´ametros [n, k, d2]qtal que d2> d. Hay otros dos conceptos de c´odigo ´optimo referidos a los par´ametros nyk. Para la longitud n tenemos el siguiente: Definici´on 38 Un c´odigo lineal de par´ametros [n, k, d]qse dice ´optimo si no existe ning´un otro c´odigo con par´ametros [n2, k, d]qtal que n2< n. 2.1. C´odigos divisibles Seguidamente se˜nalaremos una serie de propiedades que ser´an ´utiles m´as adelante. Una de las caracter´ısticas de algunos de los c´odigos que hemos construido en cap´ıtulos posteriores es que los pesos de todas las palabras-c´odigo son divisibles entre un n´umero entero. Examinando [HuPl], hemos reparado en el inter´es de esta caracter´ıstica, pues est´a relacionada con la propiedad de autoortogonalidad. A continuaci´on se dan las nociones de c´odigo divisible, c´odigo dual, c´odigo autodual y c´odigo autoortogonal y los teoremas que las relacionan. Decimos que un c´odigo Ces divisible si todas las palabras-c´odigo tienen peso divisible por un entero 4>1. Se dice que el c´odigo es divisible por 4;4es un divisor de Cy el divisor de Cser´a el mayor de los divisores. Sea Cun c´odigo lineal y sea Huna matriz de control de C. Podemos considerar Hcomo la matriz generadora de otro c´odigo sobre Fq. Este c´odigo es el denominado c´odigo dual de C, y se denota por C⊥. De hecho, C⊥es el c´odigo que consiste en el subespacio ortogonal de Crespecto de la forma bilineal sim´etrica B:Fn q×Fn q−→ Fqdada por B(x, y) = Pn i=1 xiyi. Como dicha forma es no degenerada, se tiene que C⊥tiene dimensi´on n−ksi Ctiene dimensi´on k. Adem´as, si Ges una matriz generadora de C, la igualdad GHt= 0 implica que Ges una matriz de control de C⊥. Un c´odigo Ces autoortogonal si C ⊆ C⊥. Un c´odigo Ces autodual si C=C⊥. En el siguiente teorema, veremos algunos resultados elementales sobre el peso de palabras-c´odigo cuando trabajamos con c´odigos sobre F2, que resultar´an ´utiles m´as adelante. Teorema 39 Se cumple lo siguiente: (i)Si x, y ∈Fn 2, entonces w(x+y) = w(x) + w(y)−2·w(x∩y), donde x∩yes el vector de Fn 2, que tiene unos exactamente en aquellas posiciones donde ambos x, y tengan unos. (ii)Si x, y ∈Fn 2, entonces w(x∩y)≡x·y(mod 2). (iii)Si x∈Fn 2, entonces w(x)≡x·x(mod 2). Veamos, pues, la relaci´on entre los c´odigos lineales binarios divisibles entre cuatro y los c´odigos autoortogonales. 9
Teorema 40 Sea Cun c´odigo lineal binario. (i)Si Ces autoortogonal y cada fila de una matriz generadora suya tiene peso divisible entre cuatro, entonces todas las palabras del c´odigo Ctienen peso divisible entre cuatro. (ii)Si todas las palabras del c´odigo Ctienen peso divisible entre cuatro, entonces Ces autoortogonal. Demostraci´on: Para (i), sean x, y filas de la matriz generadora. Por el Teorema 39, w(x+y) = w(x) + w(y)−2·w(x∩y)≡0 + 0 −2·w(x∩y)≡0 (mod 4). Ahora procedemos por inducci´on sabiendo que cada palabra-c´odigo es la suma de ciertas filas de la matriz generadora. Para (ii), sean x, y ∈ C. De nuevo por el Teorema 39, 2(x·y)≡2·w(x∩y)≡2·w(x∩y)−w(x)− w(y)≡ −w(x+y)≡0 (mod 4). Luego x·y≡0 (mod 2). Es natural preguntarse si el Teorema 40 puede generalizarse a c´odigos cuyas palabras-c´odigo tienen pesos divisibles entre otros n´umeros aparte del cuatro. El Teorema 40 afirma que los c´odigos binarios divisibles entre cuatro son autoortogonales. Esto no es cierto si consideramos c´odigos binarios divisibles entre dos. 2.2. Cotas de c´odigos lineales A continuaci´on se describen las cotas de c´odigos lineales m´as comunes. Teorema 41 (Cota de Hamming) Sea Cun c´odigo lineal q-ario de longitud nque corrige terrores, entonces se cumple n 0+n 1(q−1) + n 2(q−1)2+· · · +n t(q−1)t≤qn−k(2.1) Demostraci´on: Como Ccorrige terrores, las bolas de radio tcentradas en las palabras del c´odigo Cson disjuntas. El cardinal de una bola de radio tes n 0+n 1(q−1) + n 2(q−1)2+· · · +n t(q−1)t Tenemos qkbolas disjuntas, cada una del cardinal anterior, todas ellas contenidas en Fn q, que tiene cardinal qn, con lo que la desigualdad (2.1) queda probada. Se dice que un c´odigo es perfecto si en la desigualdad (2.1) se da la igualdad. Teorema 42 (Cota de Singleton) Sea C ⊆ Fn qun [n, k, d]qc´odigo lineal, entonces k+d≤n+ 1 (2.2) Demostraci´on: Para toda palabra (x1, . . . , xn) del c´odigo, suprimimos las d−1 ´ultimas coordenadas. Obtenemos palabras (x1, . . . , xn−d+1) que son todas distintas. Luego qk≤qn−d+1 y queda probada la desigualdad (2.2). Se dice que un c´odigo es de M´axima Distancia de Separaci´on (MDS) si se da la igualdad en (2.2). Seguidamente, daremos la noci´on de c´odigo residual, que nos permite obtener otra cota para c´odigos lineales. 10
Proposici´on 43 Sea Cun c´odigo lineal con par´ametros [n, k, d]sobre Fq, entonces existe un c´odigo de par´ametros [n−d, k −1,dd/qe]sobre Fq. Se denomina c´odigo residual. Demostraci´on: Sea c∈ C una palabra-c´odigo de peso exactamente dy sea Guna matriz generadora del c´odigo en la que la palabra csea la primera fila. Permutando las columnas de Gy multiplic´andolas por constantes no nulas, de forma que las d coordenadas no nulas de csean exactamente las dprimeras y sean todas unos, se obtiene un c´odigo equivalente a Cque llamaremos Casimismo. La nueva matriz generadora de Cde orden k×ny rango ktiene la forma siguiente. En la primera fila se encuentra el vector ces decir, hay dunos y (n−d) ceros. B= 1 1 1 · · · 1 0 0 0 · · · 0 G2 La submatriz G2es de orden (k−1)×(n−d). El rango de G2es (k−1), puesto que, si no fuese as´ı y el rango fuese menor que (k−1), con transformaciones elementales de las filas de G2(y de B), podr´ıamos lograr que la primera fila de G2fuese toda de ceros. Fij´andonos en la matriz grande By haciendo una combinaci´on lineal de esta segunda fila y tambi´en de su primera fila, conseguir´ıamos una palabra-c´odigo de Cno nula de peso menor que d, en contra de la hip´otesis. Ahora, sea C2el c´odigo lineal sobre Fqcuya matriz generadora es G2, sabemos que tiene par´ametros [n−d, k −1, d2]q. Veamos cual es el peso m´ınimo del c´odigo. Sea x∈ C no nula combinaci´on lineal de las k−1 ´ultimas filas de B, de forma que la correspondiente combinaci´on lineal de las k−1 filas de G2tenga peso w. Sea δiel n´umero de coordenadas en la primera secci´on de xque tiene valor ipara cada i∈Fq. La palabra c´odigo x−ic ∈ C y tiene peso w+d−δiy, como este peso debe ser mayor o igual que dconcluimos que w≥δipara cada i∈Fq. N´otese que Pq i=1 δi=d. Por lo cual, alg´un δi≥d/q luego w≥d/q. Como todos los valores son enteros, tenemos que w≥ dd/qe, es decir, d2≥ dd/qe. Aplicando la Proposici´on 43 reiteradamente mientras se pueda, se obtiene el siguiente resultado. Teorema 44 (Cota de Griesmer) Sea Cun [n, k, d]-c´odigo lineal sobre Fq, entonces n≥ k−1 X i=0 d qi(2.3) Los c´odigos que alcanzan la cota de Griesmer (2.3) con igualdad tienen la propiedad de ser ´optimos. 2.3. Decodificaci´on de c´odigos lineales En esta secci´on se expone un m´etodo general de decodificaci´on de c´odigos lineales. Sea Cun c´odigo lineal de par´ametros [n, k, d] sobre Fq. Como sabemos Ccorrige t=d−1 2 errores. 11
Si se env´ıa una palabra-c´odigo c∈ C y se recibe y∈Fn q, el error cometido durante la transmisi´on ha sido e=y−c. La estrategia que seguiremos para decodificar yes la siguiente: calculamos la distancia de ya todas las palabras de Cy la decodificamos por la m´as pr´oxima, si existe. Si durante la transmisi´on se han cometido a lo m´as terrores, es decir, w(e)≤t, entonces d(c, y) = w(e)≤t yces la ´unica palabra del c´odigo con tal propiedad; la decodificaci´on es, por tanto, correcta. Si t < w(e)< d, podemos detectar que se han producido errores, puesto que y6∈ C, pero no corregirlos en general. Si w(e)≥dla decodificaci´on fallar´a eventualmente. La mayor informaci´on acerca del error cometido la da el llamado s´ındrome. Supongamos, como antes, que se ha enviado cy recibido y=c+e. Sea Huna matriz de control del c´odigo C. Definici´on 45 Se denomina s´ındrome de yal vector s(y) = Hyt∈Fn−k q Se verifica y∈ C si y solo si s(y)=0 en cuyo caso la palabra yse supone transmitida correctamente. Como el s´ındrome es una aplicaci´on lineal, se cumple s(y) = s(c+e) = s(c) + s(e) = s(e) y, por lo tanto, conocemos el s´ındrome del error cometido. Proposici´on 46 El s´ındrome del vector recibido s(y)es una combinaci´on lineal de las columnas de la matriz Hcorrespondientes a las posiciones en las que se han producido los errores. Consideremos en Fn qla relaci´on de equivalencia u∼vsi y solo si u−v∈ C El espacio vectorial cociente obtenido, m´odulo dicha relaci´on, se denota por Fn q/C. Los elementos de Fn q/Cson clases de equivalencia u+C=nu+x:x∈ Co Como cada clase posee #C=qkelementos (´o representantes), el cardinal de Fn q/Ces qn−ky su dimensi´on es n−k. Notemos que u, v est´an en la misma clase de equivalencia si y solo si u−v∈ C, es decir, si y solo si s(u) = s(v). De esta manera, recibido y, al conocer s(y), conocemos la clase a la que pertenece el error cometido. Definici´on 47 Si en una clase de equivalencia existe un ´unico elemento de peso m´ınimo, este elemento se denomina el l´ıder de la clase. En general, no toda clase tendr´a l´ıder, ya que el elemento de peso m´ınimo no ser´a, en general, ´unico. Sin embargo, si una clase contiene un elemento de peso ≤t, este es el l´ıder de la clase, como asegura la siguiente proposici´on. 12
Proposici´on 48 Cada clase de Fn q/Cposee a lo sumo un elemento de peso ≤t. Demostraci´on: Si existen u, v en la misma clase, ambos de peso ≤t, entonces u−v∈ C yw(u−v)≤ w(u) + w(v)≤2t < d(C), lo cual implica que u−v= 0 y u=v. Recibido un vector y, decodificar ysignifica encontrar la palabra de Cm´as pr´oxima a y, y la decodificaci´on ser´a posible si y solo si esta palabra existe, es decir, si es ´unica. Como todos los vectores y−x,x∈ C, est´an en la misma clase de equivalencia de Fn q/C, que es la clase de y, el m´ınimo de d(y, x) = w(y−x) se obtiene cuando y−xes el l´ıder de la clase. Por consiguiente, la decodificaci´on es posible si y solo si la clase del vector recibido posee l´ıder y el error es asumido como el l´ıder de la clase. La Proposici´on 48 garantiza que si el n´umero de errores no supera la capacidad correctora del c´odigo, entonces la decodificaci´on es correcta. Para realizar este proceso, se construye una tabla (Standard Decoding Array, SDA) con dos columnas y tantas filas como clases hay en Fn q/C, es decir, qn−kfilas. En la primera columna escribimos el s´ındrome de un elemento cualquiera de cada una de las clases; en la segunda el l´ıder de la clase correspondiente, si existe. Esta tabla se construye una vez y sirve para la decodificaci´on de cualquier vector. Algoritmo 49 Recibido un vector y 1. Calcular s(y)y buscarlo en la columna de s´ındromes. 2. Si la clase correspondiente no posee l´ıder, la decodificaci´on falla. Fin. 3. Si la clase posee l´ıder, e, se decide que ees el error cometido. La palabra decodificada es y−e. Fin. Este es un algoritmo gen´erico de decodificaci´on v´alido para cualquier c´odigo lineal, impracticable si el tama˜no de la tabla es muy grande. Casi todo c´odigo lineal particular tiene un algoritmo propio de decodificiaci´on mucho m´as eficiente, siendo la sencillez del algoritmo de decodificaci´on uno de los criterios para preferir un c´odigo en una aplicaci´on real. 13
Cap´ıtulo 3 C´odigos lineales binarios con t´ecnicas elementales El objetivo de este cap´ıtulo es la obtenci´on de c´odigos lineales binarios ´optimos utilizando construcciones muy simples basadas meramente en sumas. Entendemos por c´odigo ´optimo aquel c´odigo que, fijada su longitud y dimensi´on, tenga la m´axima distancia m´ınima posible. Llamaremos c´odigo casi ´optimo a un c´odigo con par´ametros [n, k, d −1]2, siendo dla distancia m´ınima del c´odigo ´optimo para dicha longitud y dimensi´on, nyk. En las p´aginas [Grassl] y [SchSch] podemos ver tablas en las que se muestran c´odigos que tienen la m´axima distancia m´ınima en funci´on de los par´ametros de longitud y dimensi´on, y, en los casos en los que no se sabe con exactitud dicha distancia m´ınima ´optima, se expone la cota de esta y el c´odigo con la m´axima distancia m´ınima encontrado hasta el momento, pudiendo ser esta distancia m´ınima efectivamente la m´axima. Siendo los m´etodos utilizados tan sencillos, no esper´abamos encontrar nada revelador. A pesar de ello, hemos obtenido en algunos casos c´odigos ´optimos, c´odigos casi ´optimos y otros ejemplos cautivadores. El principal valor de este hecho es la posibilidad de realizar a mano los c´alculos de los pesos, el n´umero de palabras que hay para cada peso y otros datos del c´odigo, lo cual es posible gracias a la notable simetr´ıa de los c´odigos. Adem´as, hemos hallado c´odigos en los que el n´umero de pesos no nulos es peque˜no y, en algun caso, hemos obtenido c´odigos de gran longitud. Algunas caracter´ısticas que hemos observado en los c´odigos que hemos construido han suscitado nuestro inter´es. Hay c´odigos con solo dos o tres pesos no nulos. Si se desea profundizar en ello, pueden consultarse los art´ıculos [WaDiXu] y [Ding], que tratan sobre c´odigos con dos y tres pesos no nulos, respectivamente. Otra propiedad de algunos c´odigos es que los pesos de todas sus palabras son divisibles entre cuatro y, por tanto, son c´odigos autoortogonales. Sin embargo, estos c´odigos son poco susceptibles de ser utilizados en aplicaciones reales debido a su baja dimensi´on, puesto que esto conlleva una baja tasa de transmisi´on de informaci´on. Los c´odigos lineales binarios que hemos obtenido tienen los siguientes par´ametros: •C´odigos ´optimos [15,5,7]2,[20,5,9]2,[20,6,8]2,[21,5,10]2,[28,7,12]2,[77,7,36]2, [93,8,44]2,[120,9,56]2,[121,8,58]2,[136,9,64]2 15
•C´odigos casi ´optimos [26,6,11]2,[120,8,57]2,[135,9,63]2 •Otros c´odigos interesantes [130,9,58]2,[171,9,72]2,[240,10,112]2,[262,10,120]2 Los c´odigos lineales binarios con solo tres pesos no nulos tienen los siguientes par´ametros: [15,5,7]2,[21,5,10]2,[28,7,12]2,[93,8,44]2,[120,9,56]2,[136,9,64]2 Hemos obtenido los siguientes par´ametros correspondientes a c´odigos divisibles entre cuatro y, por consiguiente, a c´odigos autoortogonales: [28,7,12]2,[93,8,44]2,[120,9,56]2,[136,9,64]2,[240,10,112]2 Como ya hemos comentado, los c´odigos que hemos construido poseen dimensi´on baja. Quien desee profundizar en este tema, puede examinar los siguientes art´ıculos: [BoJaf] y [Til] tratan sobre c´odigos con dimensi´on a lo sumo y dimensi´on , respectivamente; [BoJaVe] se ocupa de los c´odigos de dimensi´on ocho y [DoGuSi] de los c´odigos de dimensi´on nueve. Finalmente, el art´ıculo [GuBh], adem´as de ocuparse de los c´odigos de dimensi´on nueve, se refiere a los c´odigos de dimensi´on diez. Compararemos nuestros c´odigos con los c´odigos de [Grassl], cuyas construcciones son en muchos casos automatizadas utilizando el sistema algebraico computacional Magma y, en consecuencia, m´as laboriosas. 3.1. C´odigo lineal binario ´optimo de par´ametros [15,5,7]2 A modo de introducci´on, para describir las t´ecnicas que usaremos en este cap´ıtulo, comenzaremos dando un ejemplo bastante simple para obtener un c´odigo de par´ametros bien conocidos [15,5,7]2. Sea el c´odigo lineal binario, subespacio vectorial de F15 2, de par´ametros [15,5, d]2siguiente: LLamamos cabecera a los elementos ai∈F2que se encuentran en las primeras componentes de las palabras-c´odigo; y llamamos cola al resto de elementos que dependen linealmente de los elementos de la cabecera. Dicho esto, en la cabecera de las palabras del c´odigo, cinco coordenadas, se colocan los elementos a1, . . . , a5∈F2libres; y en la cola, todas las sumas posibles de tres elementos de los anteriores con sub´ındices distintos. C1=n(a1, a2, a3, a4, a5, ai+aj+ak) : ai∈F2, i, j, k ∈ {1,...,5},distintoso⊂F15 2 De esta manera, tal como se indic´o previamente, la longitud del c´odigo es n= 5 + 5 3= 5 + 10 = 15 es decir, 5 elementos en la cabecera y 5 3elementos en la cola, que es el n´umero de subconjuntos de tres elementos elegidos del conjuntos de cinco elementos de la cabecera, los cuales se sumar´an para obtener los elementos correspondientes. 16
La dimensi´on es k= 5 y, por lo tanto, el n´umero de palabras que hay en el c´odigo es 25= 32. Describiremos una matriz generadora G1dividi´endola en bloques. En el primer bloque se tiene la matriz identidad 5 ×5, que nos dar´a la informaci´on que hemos codificado, v∈F5 2, al realizar el producto v·G1= [v|w]. El segundo bloque estar´a formado por todas las columnas en las que hay tres unos y el resto ceros, que, en el producto anterior, nos dar´a w∈F10 2y nos permitir´a corregir errores en el proceso de decodificaci´on. El orden de estas columnas es irrelevante pues dar´a lugar a c´odigos equivalentes. Esta matriz tendr´a orden 5 ×15 y rango 5. G1= 100001111· · · 0 010001110· · · 0 001001001· · · 1 000100101· · · 1 000010010· · · 1 De esta forma, el c´odigo C1es sistem´atico. Sabemos que, en un c´odigo lineal, el peso m´ınimo es igual a la distancia m´ınima. Por consiguiente, para hallar la distancia m´ınima del c´odigo, se calculan los pesos de todas las palabras-c´odigo; para ello usaremos m´etodos combinatorios. Recordemos que, dado un elemento de un c´odigo C,x∈ C, se define su peso w(x) como el n´umero de coordenadas no nulas de x. Los resultados se muestran en la siguiente tabla. niP3peso 1 6 7 2 6 8 3 4 7 4 4 8 5 10 15 Cuadro 3.1: Pesos del c´odigo En la primera columna aparece el n´umero exacto de aique son distintos de cero, ni, lo que dar´a el peso de la cabecera. En la segunda columna, se muestra el peso de la cola, cu´antas sumas de tres elementos son distintas de cero dependiendo del n´umero ni. En la ´ultima columna, los elementos de la fila correspondiente se suman, dando como resultado el peso total de las palabras-c´odigo con dicha propiedad. Los c´alculos se detallan a continuaci´on: •Si en la cabecera hay exactamente un ai6= 0, el peso de la cabecera ser´a igual a 1. El peso de la cola ser´a 4 2, pues las ´unicas sumas que resultan distintas de cero son las sumas que contienen al aidistinto de cero; los otros dos elementos de la suma podr´an ser cualesquiera entre los cuatro elementos de la cabecera que son distintos de cero. 1 + 4 2= 1 + 6 = 7 •Si en la cabecera hay exactamente dos ai6= 0, el peso de la cabecera ser´a 2. Hallemos el peso de la cola. Fij´emonos en que la ´unica manera de que un elemento de la cola sume uno es que 17
Observamos que la construcci´on del c´odigo lineal dada en [Grassl] es m´as compleja que en nuestro caso. Construction of a linear code [20,5,9] over GF (2): [1]: [8,7,2] Cyclic Linear Code over GF (2) Dual of the Repetition Code of length 8 [2]: [135,8,65] Linear Code over GF (2) Let C1 be the BCH Code over GF (2) of parameters 127 63. Let C2 the Subcode Between Code of dimension 8 between C1 and the BCH Code with parameters 127 64. Return Construction X using C1, C2 and [1] [3]: [70,7,33] Linear Code over GF (2) Puncturing of [2] at {2,10,11,12,13,14,15,17,18,19,20,21,24,25,26,27,29,31,32,33,38,39,41,42, 43,45,48,49,53,55,57,58,64,66,67,68,69,73,74,75,77,78,80,81,84,87,89,92, 97,100,101,102,105,107,108,110,114,118,119,122,123,125,127,128,135} [4]: [37,6,17] Linear Code over GF (2) Puncturing of [3] at {2,8,10,11,14,17,20,21,22,24,27,31,33,35,38,39,40,41,43,44,45,48,49,50,51, 52,55,57,58,60,61,62,65} [5]: [20,5,9] Linear Code over GF (2) Puncturing of [4] at {2,7,8,10,12,13,14,17,21,22,23,25,28,29,30,31,33} El [20,5,9]2c´odigo lineal binario se trata de un c´odigo ´optimo pues cumple la cota de Griesmer (2.3) con igualdad. 4 X i=0 9 2i=9+5+3+2+1=20 Igual que en el caso anterior, se sigue el m´etodo general de decodificaci´on debido a la peque˜na cantidad de palabras que tiene el c´odigo. Recibida una palabra, el receptor comprueba si dicha palabra est´a en el c´odigo; en el caso de que la palabra est´e en el c´odigo, interpreta que la palabra ha sido transmitida de forma correcta. Si la palabra no est´a en el c´odigo, se compara la distancia de dicha palabra con el resto de palabras hasta que esta sea menor que 4, que es la capacidad correctora del c´odigo. El c´odigo de par´ametros [20,5,9]2extendido da lugar a un c´odigo lineal binario de par´ametros [21,5,10]2, el cual tambi´en es ´optimo. Veamos a continuaci´on la relaci´on entre sus pesos y el n´umero de palabras del c´odigo con dichos pesos y observemos que se trata de un c´odigo con solo tres pesos no nulos. A0= 1 A10 = 20 A12 = 10 A16 = 1 24
3.3. C´odigo lineal binario ´optimo de par´ametros [28,7,12]2 Siguiendo el mismo procedimiento que en los ejemplos anteriores, se considera el siguiente c´odigo lineal incluido en F28 2. C3=n(a1, a2, a3, a4, a5, a6, a7,X 5 aj) : ai∈F2, i, j ∈ {1,...,7}o⊂F28 2 Se trata de un c´odigo lineal binario cuyas palabras est´an constituidas por una cabecera, en la que se colocan los elementos que definen la dimensi´on del c´odigo, y por una cola, formada por todas las posibles sumas de cinco elementos que se pueden formar con los elementos de la cabecera y sub´ındices distintos. As´ı pues, la longitud del c´odigo es n= 7 + 7 5= 28 esto es, 7 elementos en la cabecera y 7 5elementos en la cola, resultado de tomar todos los posibles subconjuntos de cinco elementos del conjunto de siete elementos de la cabecera para formar todas las sumas requeridas. La dimensi´on del subespacio vectorial C3es k= 7 y, en consecuencia, el n´umero de palabras en C3 es 27= 128. Una matriz generadora G3tendr´a orden 7 ×28, rango 7 y la siguiente forma. G3= 10000001111· · · 0 01000001111· · · 0 00100001111· · · 1 00010001110· · · 1 00001001001· · · 1 00000100101· · · 1 00000010010· · · 1 De la misma manera que en los ejemplos anteriores, vamos a describir G3dividi´endola en bloques. Primero, tendremos la matriz identidad 7 ×7. El siguiente bloque, 7 ×21, estar´a compuesto por todas las posibles columnas en las que hay cinco unos y el resto ceros sin repetirse ninguna. El orden de estas columnas no es importante ya que dar´a c´odigos equivalentes. Los resultados de los pesos de las palabras se muestran en la tabla. niP5peso 1 15 16 2 10 12 3 6+3 12 4 12 16 5 1+10 16 6 6 12 7 21 28 Cuadro 3.5: Pesos del c´odigo 25
A continuaci´on se desarrollan los c´alculos realizados. •Si en la cabecera hay exactamente un ai6= 0, el peso de la cabecera es 1. Hallemos el peso de la cola. Es claro que las ´unicas componentes que ser´an distintas de cero ser´an las que contengan al aique es distinto de cero en la suma. Puesto que en la cola est´an (sumados) todos los subconjuntos de cinco elementos elegidos entre los siete de la cabecera, el n´umero de elementos de la cola que contiene a un determinado aies 6 4, todos los posibles subconjuntos de cuatro elementos elegidos entre los seis restantes. 1 + 6 4= 1 + 15 = 16 •Si en la cabecera hay exactamente dos ai6= 0, el peso de la cabecera es 2. Para hallar el peso de la cola, nos damos cuenta de que la componente correspondiente a las sumas de cinco elementos en los que est´en ambos aidistinto de cero ser´a cero, al igual que las componentes en las que no est´e ninguno de ellos. Entonces, para cada uno de los aidistinto de cero, el n´umero de sumas que ser´an distintas de cero, ser´a 5 4, todos los posibles subconjuntos de cuatro elementos tomados entre los cinco que quedan. Como hay dos ai, el n´umero total de componentes que ser´an distintas de cero y aportar´an al peso ser´an 2 ·5 4. 2+2·5 4= 2 + 10 = 12 •Si en la cabecera hay exactamente tres ai6= 0, el peso de la cabecera es 3. El peso de la cola es 6 + 3. Las componentes que ser´an distintas de cero pueden ser de dos tipos. En primer lugar, ser´an distintas de cero las componentes en las que aparezcan los tres aique son distintos de cero. Hay 4 2componentes con esta propiedad, el n´umero de subconjuntos de dos elementos que se pueden tomar entre los cuatro elementos de la cabecera que son cero, para que la suma tenga cinco elementos. El otro tipo de componentes que ser´an distintas de cero son las que contienen a uno y solo uno de los aidistintos de cero, puesto que si contuviesen a dos de ellos, la suma en F2ser´ıa cero. Como hay cuatro elementos de la cabecera iguales a cero y tres distintos de cero, solo hay una componente de este tipo para cada ai, es decir, en total 3. 3 + 4 2+ 3= 3 + 6 + 3 = 12 •Si en la cabecera hay exactamente cuatro ai6= 0, el peso de la cabecera es 4. Las ´unicas sumas de cinco elementos elegidos entre siete, de los cuales cuatro son distintos de cero, ser´an las sumas en las que hay tres elementos distintos de cero y dos iguales a cero. El n´umero de subconjuntos que podemos tomar de tres elementos en un conjunto de cuatro es 4 3y el n´umero de subconjuntos que podemos tomar de dos elementos en un conjunto de tres es 3 2. Luego, en total, el peso de la cola es el producto 4 3·3 2 4 + 4 3·3 2= 4 + 12 = 16 26
•Si en la cabecera hay exactamente cinco ai6= 0, el peso de la cabecera es 5. En la cola, las componentes que son distintas de cero contendr´an en sus elementos sumados o a los cinco elementos distintos de cero, o a tres de ellos. En el caso de contener a tres de ellos, hay en total el n´umero de subconjuntos que podemos tomar de tres elementos en el conjunto de los cinco que son distintos de cero; los otros dos elementos que completan la suma ser´an los dos elementos de la cabecera que son distintos de ellos. En conclusi´on, el peso de la cola ser´a 1 + 5 3. 5 + 1 + 5 3= 5 + 1 + 10 = 16 •Si en la cabecera hay exactamente seis ai6= 0, el peso de la cabecera es 6. En la cabecera solo hay un elemento distinto de cero; las componentes que tengan a este elemento como parte de la suma, sumar´an 4 = 0 en F2. El resto de las sumas sumar´an 5 = 1 en F2, luego el peso de la cola es igual a 6 5, todos los subconjuntos que se pueden tomar de cinco elementos elegidos en un conjunto de seis. 6 + 6 5= 6 + 6 = 12 •Si en la cabecera hay exactamente siete ai6= 0, el peso de la cabecera es 7. Todas las componentes de la cabecera son unos y, por consiguiente, todas las sumas de cinco elementos escogidos de la cabecera ser´an igual a uno en F2. 7 + 7 5= 7 + 21 = 28 Calculamos cu´antas palabras hay para cada uno de los pesos y mostramos los resultados en una tabla. En todo c´odigo lineal est´a la palabra que tiene todas sus componentes nulas. (i) Si hay exactamente un ai6= 0, entonces el peso es 16. Luego hay 7 palabras de peso 16, una para cada i∈ {1,2,3,4,5,6,7}. (ii) Si hay exactamente dos ai6= 0, el n´umero de palabras con esta propiedad es 7 2= 21 y, como hemos visto, el peso de cada una de ellas es 12. (iii) El n´umero de palabras con exactamente tres ai6= 0 es 7 3= 35. Cada una de ellas tiene peso 12. (iv) El n´umero de palabras con exactamente cuatro ai6= 0 es 7 4= 35. Cada una de ellas tiene peso 16. (v) El n´umero de palabras con exactamente cinco ai6= 0 es 7 5= 21. Cada una de ellas tiene peso 16. (vi) El n´umero de palabras con exactamente seis ai6= 0 es 7 6= 7. Cada una de ellas tiene peso 12. 27
(vii) Y, por ´ultimo, hay una palabra con todos los elementos de la cabecera distintos de cero. Tiene peso 28. El n´umero total de palabras es 1 + 7 + 21 + 35 + 35 + 21 + 7 + 1 = 128 = 27, como ya sab´ıamos. El c´odigo C3se trata de un c´odigo autocomplementario puesto que la palabra cuyas componentes son todas uno est´a en el c´odigo. Esto quiere decir que si una palabra x∈ C3, entonces la palabra x+ [1,...,1] ∈ C3, la cual se trata de su palabra complementaria. Observamos esta caracter´ıstica, junto con el hecho de que el c´odigo tiene solamente tres pesos no nulos. Notemos, adem´as, que el peso de cada palabra es divisible entre cuatro y, por ese motivo, se trata de un c´odigo autoortogonal. A0= 1 A12 = 63 A16 = 63 A28 = 1 En conclusi´on, la distancia m´ınima del c´odigo es d= 12 y se tiene un c´odigo de par´ametros [28,7,12]2. Examinando la tabla correspondiente a c´odigos lineales binarios ´optimos en [Grassl], se observa que se trata de un c´odigo ´optimo. n/k 5 6 7 8 9 26 12 12 11 10 9 27 13 12 12 10 10 28 14 12 12 11 10 29 14 13 12 12 11 30 15 14 12 12 12 Cuadro 3.6: Bounds on the minimum distance of linear codes over GF (2) Sin embargo, observando dicha tabla, notemos que existe un c´odigo con par´ametros [27,7,12]2. Esto quiere decir que nuestro c´odigo de par´ametros [28,7,12]2no es ´optimo con respecto a la Definici´on 38 que dimos en la p´agina 9 porque existe otro con menor longitud pero con igual dimensi´on y distancia m´ınima. La construcci´on de dicho c´odigo dada en [Grassl] se realiza recortando un c´odigo BCH extendido. Construction of a linear code [28,7,12] over GF (2): [1]: [32,11,12] Linear Code over GF (2) Extended BCH Code with parameters 31 11 [2]: [28,7,12] Linear Code over GF (2) Shortening of [1] at {29 . . . 32} 3.4. C´odigo lineal binario ´optimo de par´ametros [77,7,36]2 Tomamos un c´odigo lineal binario de par´ametros [77,7, d]2definido como sigue: en la cabecera de las palabras-c´odigo se colocan siete elementos ai∈F2; y, en la cola, todas las posibles sumas de 28
tres y cuatro elementos escogidos entre los aique hemos colocado en la cabecera con sub´ındices distintos. C4=n(a1, . . . , a7,X 3 aj,X 4 ak) : ai∈F2, i, j, k ∈ {1,...,7}o⊂F77 2 La longitud del c´odigo es n= 7 + 7 3+7 4= 7 + 35 + 35 = 77 y la dimensi´on de C4como subespacio vectorial de F77 2es k= 7. El n´umero de palabras que hay en el c´odigo es 27= 128. Para hallar la distancia m´ınima del c´odigo, calcularemos los pesos de todas las palabras con m´etodos combinatorios, como hemos hecho en otros casos. A continuaci´on se muestran los resultados en una tabla, as´ı como los c´alculos detallados. A partir de ahora a˜nadiremos como ´ultima columna el n´umero de palabras que hay en el c´odigo dependiendo de la cantidad de aidistintos de cero en la cabecera y lo denotaremos por no. El n´umero de palabras que hay en el c´odigo con exactamente j coordenadas de la cabecera distintas de cero para cada j∈ {0, . . . , k}es k j=7 j. niP3P4peso no 1 15 20 36 7 2 20 20 42 21 3 19 16 38 35 4 16 16 36 35 5 15 20 40 21 6 20 20 46 7 7 35 0 42 1 Cuadro 3.7: Pesos del c´odigo y n´umero de palabras •Exactamente un ai6= 0 : 1 + 6 2+6 3= 1 + 15 + 20 = 36 •Exactamente dos ai6= 0 : 2+2·5 2+ 2 ·5 3= 2 + 2 ·10 + 2 ·10 = 42 •Exactamente tres ai6= 0 : 3 + 1+3·4 2+4+3·4 3=3+(1+3·6) + (4 + 3 ·4) = 38 •Exactamente cuatro ai6= 0 : 4 + 4 3+ 4 ·3 2+4 3·3+4=4+(4+4·3) + (4 ·3 + 4) = 36 29
•Exactamente cinco ai6= 0 : 5 + 5 3+ 5+5 3·2 = 5 + (10 + 5) + 10 ·2 = 40 •Exactamente seis ai6= 0 : 6 + 6 3+6 3= 6 + 20 + 20 = 46 •Exactamente siete ai6= 0 : 7 + 7 3+ 0 = 7 + 35 + 0 = 42 Veamos de manera concisa cu´antas palabras hay con cada uno de los pesos. Reparemos, adem´as, en la curiosa distribuci´on de estos. A0= 1 A36 = 42 A38 = 35 A40 = 21 A42 = 22 A46 = 7 Por ende, la distancia m´ınima del c´odigo es d= 36. El c´odigo que hemos construido tiene par´ametros [77,7,36]2, que, como observamos en la tabla correspondiente de [Grassl], es un c´odigo ´optimo. Reparemos en dicha tabla. n/k 5 6 7 8 9 75 38 36 36 34 33-34 76 38 37 36 35 34 77 39 38 36 36 34-35 78 40 38 37 36 35-36 79 40 39 38 36 36 Cuadro 3.8: Bounds on the minimum distance of linear codes over GF (2) Observemos que, no obstante, existen c´odigos de par´ametros [77,8,36]2, [76,7,36]2y [75,7,36]2, este ´ultimo es el c´odigo ´optimo si tomamos la acepci´on de c´odigo ´optimo dada en la Definici´on 38. 3.5. C´odigo lineal binario ´optimo de par´ametros [93,8,44]2 Sea el c´odigo lineal binario, subespacio vectorial de F93 2, de par´ametros [93,8, d]2siguiente. En la cabecera de las palabras del c´odigo se colocan los elementos a1, . . . , a9∈F2, con el detalle de que a9=a1+· · · +a8; y, en la cola, todas las sumas posibles de seis elementos de los anteriores con sub´ındices distintos. 30
C5=n(a1, . . . , a8, a9=a1+· · · +a8,X 6 aj) : ai∈F2, i, j ∈ {1,...,9}o⊂F93 2 La longitud del c´odigo es n= 9 + 9 6= 9 + 84 = 93 La dimensi´on es k= 8 y, por lo tanto, el n´umero de palabras que hay en el c´odigo es 28= 256. Nota 50 Si hubiese nueve ailinealmente independientes en la cabecera y tom´asemos la palabra en la que los nueve aifuesen iguales a uno, el peso de dicha palabra ser´ıa nueve, puesto que todas las sumas de seis elementos resultar´ıan cero. En dicho caso, la distancia m´ınima ser´ıa a lo sumo d= 9. Para hallar la distancia m´ınima del c´odigo, se calculan los pesos de todas las palabras-c´odigo con m´etodos combinatorios. En este caso solo hay una cantidad par de aidistintos de cero en la cabecera, por la condici´on a9=a1+· · · +a8, lo cual es una ventaja a la hora de calcular los pesos de todas las palabras del c´odigo. Los resultados se muestran en la siguiente tabla y a continuaci´on se detallan las cuentas. niP6peso no 2 42 44 36 4 44 48 126 6 38 44 84 8 56 64 9 Cuadro 3.9: Pesos del c´odigo y n´umero de palabras •Exactamente dos ai6= 0 : 2+2·7 5= 2 + 2 ·21 = 44 •Exactamente cuatro ai6= 0 : 4 + 4 3·5 3+ 4= 4 + (4 ·10 + 4) = 48 •Exactamente seis ai6= 0 : 6 + 3·6 5+6 3= 6 + (3 ·6 + 20) = 44 •Exactamente ocho ai6= 0 : 8 + 8 5= 8 + 56 = 64 En este caso, puesto que a9=a1+· · · +a8, el n´umero de palabras que hay en el c´odigo con exactamente jelementos aidistintos de cero para j∈ {2,4,6,8}se obtiene, teniendo en cuenta si a9es igual o distinto de cero. Si a9es igual a cero, el n´umero de palabras con jelementos aidistintos 31
de cero es k j=8 j; elegimos subconjuntos de jelementos de la cabecera entre los 8 linealmente independientes, a9ser´a cero puesto que es la suma de un n´umero par de unos. En el otro caso, si a9es distinto de cero, entonces el n´umero de palabras con jelementos aidistintos de cero es k j−1=8 j−1; elegimos j−1 elementos de la cabecera entre los 8 linealmente independientes, a9ser´a igual a uno puesto que es la suma de un n´umero impar de elementos distintos de cero, es decir, habr´a j−1+1 elementos distintos de cero en total. En conclusi´on, el n´umero de palabras con exactamente jelementos aidistintos de cero para j∈ {2,4,6,8}es k j−1+k j. Adem´as, en todo c´odigo lineal est´a la palabra con todas sus componentes nulas. A continuaci´on se muestra el n´umero de palabras en relaci´on a su peso destacando el hecho de que C5se trata de un c´odigo con solo tres pesos no nulos. Por a˜nadidura, todas los pesos del c´odigo son divisibles entre cuatro, lo cual implica que es un c´odigo autoortogonal. A0= 1 A44 = 120 A48 = 126 A64 = 9 Como consecuencia, la distancia m´ınima del c´odigo es d= 44 y se tiene un c´odigo de par´ametros [93,8,44]2. Examinando la tabla correspondiente a c´odigos lineales binarios ´optimos en [Grassl], se observa que se trata de un c´odigo ´optimo. n/k 6 7 8 9 10 91 45 44 43 41-42 40-41 92 46 45 44 42-43 41-42 93 46 46 44 42-44 42 94 47 46 44 43-44 42-43 95 48 47 45 44 43-44 Cuadro 3.10: Bounds on the minimum distance of linear codes over GF (2) Advertimos que existe un [92,8,44]2c´odigo lineal binario, el cual es ´optimo seg´un la Definici´on 38 de la p´agina 9. 3.6. C´odigo lineal binario ´optimo de par´ametros [120,9,56]2 Sea el c´odigo lineal binario, subespacio vectorial de F120 2, de par´ametros [120,9, d]2siguiente. En principio, las palabras-c´odigo tendr´ıan, como ya hemos visto en los casos anteriores, una cabecera con elementos a1, . . . , a9∈F2y, en la cola, todas las sumas posibles de tres y siete elementos de los anteriores con sub´ındices distintos. Sin embargo, en este c´odigo eliminaremos la cabecera y nos quedaremos solo con la cola. C6=n(X 3 ai,X 7 aj) : ai, aj∈F2, i, j ∈ {1,...,9}o⊂F120 2 32
La longitud del c´odigo es n=9 3+9 7= 84 + 36 = 120 Hemos comprobado con Maple que la dimensi´on es k= 9 y, por lo tanto, el n´umero de palabras que hay en el c´odigo es 29= 512. Para hallar la distancia m´ınima del c´odigo, se calculan los pesos de todas las palabras-c´odigo con m´etodos combinatorios. Los resultados se muestran en la siguiente tabla y, a continuaci´on, se detallan las cuentas, que se han realizado de forma similar a los casos anteriores. niP3P7peso no 1 28 28 56 9 2 42 14 56 36 3 46 18 64 84 4 44 20 64 126 5 40 16 56 126 6 38 18 56 84 7 42 22 64 36 8 56 8 64 9 9 84 36 120 1 Cuadro 3.11: Pesos del c´odigo y n´umero de palabras •Exactamente un ai6= 0 : 8 2+8 6= 28 + 28 = 56 •Exactamente dos ai6= 0 : 2·7 2+ 2 ·7 6= 2 ·21 + 2 ·7 = 42 + 14 = 56 •Exactamente tres ai6= 0 : 1+3·6 2+6 4+ 3= (1 + 3 ·15) + (15 + 3) = 46 + 18 = 64 •Exactamente cuatro ai6= 0 : 4 3+ 4 ·5 2+4 3·5 4= (4 + 4 ·10) + 4 ·5 = 44 + 20 = 64 •Exactamente cinco ai6= 0 : 5 3+ 5 ·4 2+4 2+5 3= (10 + 5 ·6) + (6 + 10) = 40 + 16 = 56 •Exactamente seis ai6= 0 : 6 3+ 6 ·3 2+6 5·3 2= (20 + 6 ·3) + 6 ·3 = 38 + 18 = 56 33
n/k 6 7 8 9 10 118 59 58 56 56 55-56 119 60 59 57 56 56 120 60 60 58 56 56 121 60 60 58 56-57 56 122 61 60 58 57-58 56-57 123 62 61 59 58 56-58 Cuadro 3.17: Bounds on the minimum distance of linear codes over GF (2) 3.9. C´odigos lineales binarios de par´ametros [171,9,72]2y [135,9,63]2 Sea el c´odigo lineal binario, subespacio vectorial de F171 2, de par´ametros [171,9, d]2siguiente. En la cabecera de las palabras del c´odigo se colocan los elementos a1, . . . , a9∈F2; y en la cola todas las sumas posibles de cinco y siete elementos de los anteriores con sub´ındices distintos. C9=n(a1, . . . , a9,X 5 aj,X 7 ak) : ai∈F2, i, j, k ∈ {1,...,9}o⊂F171 2 La longitud del c´odigo es n= 9 + 9 5+9 7= 9 + 126 + 36 = 171 La dimensi´on es k= 9 y el n´umero de palabras que hay en el c´odigo es 29= 512. Para hallar la distancia m´ınima del c´odigo, se calculan los pesos de todas las palabras-c´odigo con m´etodos combinatorios. Los resultados se muestran en la siguiente tabla y, a continuaci´on, se detallan las cuentas. niP5P7peso no 1 70 28 99 9 2 70 14 86 36 3 60 18 81 84 4 60 20 84 126 5 66 16 87 126 6 66 18 90 84 7 56 22 85 36 8 56 8 72 9 9 126 36 171 1 Cuadro 3.18: Pesos del c´odigo y n´umero de palabras •Exactamente un ai6= 0 : 1 + 8 4+8 6= 1 + 70 + 28 = 99 40
•Exactamente dos ai6= 0 : 2+2·7 3+ 2 ·7 6= 2 + 2 ·35 + 2 ·7 = 86 •Exactamente tres ai6= 0 : 3 + 6 2+ 3 ·6 4+6 4+ 3= 3 + (15 + 3 ·15) + (15 + 3) = 81 •Exactamente cuatro ai6= 0 : 4 + 4 3·5 2+ 4 ·5 4+4 3·5 4= 4 + (4 ·10 + 4 ·5) + 4 ·5 = 84 •Exactamente cinco ai6= 0 : 5 + 1 + 5 3·4 2+ 5+4 2+5 3= 5 + (1 + 10 ·6 + 5) + (6 + 10) = 87 •Exactamente seis ai6= 0 : 6 + 6 5+6 3·3 2+6 5·3 2= 6 + (6 + 20 ·3) + 6 ·3 = 90 •Exactamente siete ai6= 0 : 7 + 7 5+7 3+1 + 7 5= 7 + (21 + 35) + (1 + 21) = 85 •Exactamente ocho ai6= 0 : 8 + 8 5+8 7= 8 + 56 + 8 = 72 •Exactamente nueve ai6= 0 : 9 + 9 5+9 7= 9 + 126 + 36 = 171 El c´odigo C9tambi´en se trata de un c´odigo autocomplementario, puesto que la palabra cuyas componentes son todas uno est´a en el c´odigo. Observamos dicho rasgo en el n´umero y peso de las palabras-c´odigo. El peso de una palabra y su complementaria suman 171, luego debe haber parejas de pesos que sumen dicha cifra. A0= 1 A72 = 9 A81 = 84 A84 = 126 A85 = 36 A86 = 36 A87 = 126 A90 = 84 A99 = 9 A171 = 1 41
Como consecuencia, la distancia m´ınima del c´odigo es d= 72 y se tiene un c´odigo de par´ametros [171,9,72]2. Examinando la tabla correspondiente a c´odigos lineales binarios ´optimos en [Grassl], se observa que existe un c´odigo lineal binario de par´ametros [171,9,81]2. Sin embargo, para dichas longitud y dimensi´on, la cota para la distancia m´ınima es 82. Esto quiere decir que el c´odigo ´optimo podr´ıa tener distancia m´ınima 81, ya conocido, o distancia m´ınima 82 para la cual a´un no se conoce ning´un c´odigo. Se trata de un problema abierto. La notaci´on que se usa en las tablas de [Grassl] para se˜nalar este hecho es 81-82. El c´odigo de par´ametros [171,9,72]2no tiene gran inter´es, pero si eliminamos los elementos de la cola correspondientes a las sumas de siete elementos, obtenemos un [135,9,63]2c´odigo lineal binario, el cual es casi ´optimo, siendo el c´odigo ´optimo un [135,9,64]2c´odigo lineal binario. C9∗=n(a1, . . . , a9,X 5 aj) : ai∈F2, i, j ∈ {1,...,9}o⊂F135 2 Adaptando la tabla de pesos del c´odigo y n´umero de palabras 3.18 obtenemos lo siguiente: niP5peso no 1 70 71 9 2 70 72 36 3 60 63 84 4 60 64 126 5 66 71 126 6 66 72 84 7 56 63 36 8 56 64 9 9 126 135 1 Cuadro 3.19: Pesos del c´odigo y n´umero de palabras La palabra cuyas componentes son todas uno est´a en el c´odigo C9∗, luego es autocomplementario. Observemos dicha peculiaridad en la relaci´on entre los pesos y el n´umero de palabras del c´odigo. A0= 1 A63 = 120 A64 = 135 A71 = 135 A72 = 120 A135 = 1 El c´odigo C9∗extendido, resultado de a˜nadir a C9∗un bit de paridad, tiene par´ametros [136,9,64]2 y es un c´odigo ´optimo, como hemos comprobado recurriendo a [Grassl]. Notemos que se trata de un three-weight code y cada uno de estos pesos son divisibles entre cuatro, el c´odigo C9∗extendido es un c´odigo autoortogonal. 42
A0= 1 A64 = 255 A72 = 255 A136 = 1 3.10. C´odigos lineales binarios de par´ametros [250,10,114]2 y[240,10,112]2 Sea el c´odigo lineal binario, subespacio vectorial de F250 2, de par´ametros [250,10, d]2dado a continuaci´on. En la cabecera de las palabras del c´odigo se colocan los elementos a1, . . . , a10 ∈F2y, en la cola, todas las sumas posibles de tres y siete elementos de los anteriores con sub´ındices distintos. C10 =n(a1, . . . , a10,X 3 aj,X 7 ak) : ai∈F2, i, j, k ∈ {1,...,10}o⊂F250 2 La longitud del c´odigo es n= 10 + 10 3+10 7= 10 + 120 + 120 = 250 La dimensi´on es k= 10 y, por lo tanto, el n´umero de palabras que hay en el c´odigo es 210 = 1024. Para hallar la distancia m´ınima del c´odigo, se calculan los pesos de todas las palabras-c´odigo con m´etodos combinatorios. Los resultados se muestran en la siguiente tabla y, a continuaci´on, se detallan las cuentas. niP3P7peso no 1 36 84 121 10 2 56 56 114 45 3 64 56 123 120 4 64 64 132 210 5 60 60 125 252 6 56 56 118 210 7 56 64 127 120 8 64 64 136 45 9 84 36 129 10 10 120 120 250 1 Cuadro 3.20: Pesos del c´odigo y n´umero de palabras •Exactamente un ai6= 0 : 1 + 9 2+9 6= 1 + 36 + 84 = 121 •Exactamente dos ai6= 0 : 2+2·8 2+ 2 ·8 6= 2 + 2 ·28 + 2 ·28 = 114 43
•Exactamente tres ai6= 0 : 3 + 1+3·7 2+7 4+ 3 ·7 6= 3 + (1 + 3 ·21) + (35 + 3 ·7) = 123 •Exactamente cuatro ai6= 0 : 4 + 4 3+ 4 ·6 2+4 3·6 4+ 4=4+(4+4·15) + (4 ·15 + 4) = 132 •Exactamente cinco ai6= 0 : 5 + 5 3+ 5 ·5 2+5 2+5 3·5 4= 5 + (10 + 5 ·10) + (10 + 10 ·5) = 125 •Exactamente seis ai6= 0 : 6 + 6 3+ 6 ·4 2+6 5·4 2+6 3= 6 + (20 + 6 ·6) + (6 ·6 + 20) = 118 •Exactamente siete ai6= 0 : 7 + 7 3+ 7 ·3 2+1 + 7 5·3 2= 7 + (35 + 7 ·3) + (1 + 21 ·3) = 127 •Exactamente ocho ai6= 0 : 8 + 8 3+ 8+8 7+8 5= 8 + (56 + 8) + (8 + 56) = 136 •Exactamente nueve ai6= 0 : 9 + 9 3+9 7= 9 + 84 + 36 = 129 •Exactamente diez ai6= 0 : 10 + 10 3+10 7= 10 + 120 + 120 = 250 El c´odigo C10 tambi´en se trata de un c´odigo autocomplementario. Observamos dicho rasgo en el n´umero y peso de las palabras-c´odigo. El peso de una palabra y su complementaria suman 250, luego debe haber parejas de pesos que sumen dicha cifra. A0= 1 A114 = 45 A118 = 210 A121 = 10 A123 = 120 A125 = 252 A127 = 120 A129 = 10 A132 = 210 A136 = 45 A250 = 1 44
Como consecuencia, la distancia m´ınima del c´odigo es d= 114 y se tiene un c´odigo de par´ametros [250,10,114]2. Examinando la tabla correspondiente a c´odigos lineales binarios ´optimos en [Grassl], observamos que existe un c´odigo lineal binario de par´ametros [250,10,120]2y que la cota para la distancia m´ınima es 122. Si consideramos el c´odigo de par´ametros [250,10,114]2sin cabecera, obtenemos un [240,10,112]2 c´odigo lineal binario, el cual est´a cerca de ser un c´odigo ´optimo, siendo el c´odigo ´optimo un c´odigo de par´ametros [240,10,114]2. Para esos par´ametros de longitud y dimensi´on, la cota para la distancia m´ınima es 116. C10∗=n(X 3 ai,X 7 aj) : ai, aj∈F2, i, j ∈ {1,...,10}o⊂F240 2 Una matriz generadora del c´odigo tendr´a por columnas a todos los vectores con tres unos y el resto ceros, y todos los vectores con siete unos y las dem´as componentes nulas. Hemos comprobado con Maple que el rango de dicha matriz es 10 y, por tanto, la dimensi´on del c´odigo no ha disminuido con respecto al c´odigo del que part´ıamos, k= 10. Esta matriz tendr´a orden 10 ×240. G10∗= 111111111· · · 0 1 1 1 1 1 · · · 0 111111110· · · 0 1 1 1 1 0 · · · 0 100000001· · · 0 1 1 1 1 1 · · · 0 010000001· · · 0 1 1 1 1 1 · · · 1 001000000· · · 0 1 1 1 1 1 · · · 1 000100000· · · 0 1 1 1 1 1 · · · 1 000010000· · · 0 1 0 0 0 1 · · · 1 000001000· · · 1 0 1 0 0 1 · · · 1 000000100· · · 1 0 0 1 0 0 · · · 1 000000010· · · 1 0 0 0 1 0 · · · 1 A continuaci´on exponemos la tabla adaptada a partir de la tabla 3.20. niP3P7peso no 1 36 84 120 10 2 56 56 112 45 3 64 56 120 120 4 64 64 128 210 5 60 60 120 252 6 56 56 112 210 7 56 64 120 120 8 64 64 128 45 9 84 36 120 10 10 120 120 240 1 Cuadro 3.21: Pesos del c´odigo y n´umero de palabras Veamos la relaci´on entre los pesos de las palabras del c´odigo y el n´umero de estas que tienen dichos pesos. Adicionalmente, observemos que todos los pesos son divisibles entre cuatro. El c´odigo C10∗ es autoortogonal. 45
A0= 1 A112 = 255 A120 = 512 A128 = 255 A240 = 1 Fij´emonos en el peque˜no n´umero de pesos que tiene el c´odigo. Adem´as, podemos observar que se trata de un c´odigo autocomplementario, siendo los pares de pesos complementarios los siguientes: 0 y 240, 112 y 128; y, por ´ultimo 120 es complementario de s´ı mismo. El n´umero de palabras de un peso y de su peso complementario, como ya hab´ıamos comentado anteriormente, es el mismo. 3.11. C´odigo lineal binario de par´ametros [130,9,58]2 Sea el c´odigo lineal binario, subespacio vectorial de F130 2, de par´ametros [130,9, d]2dado seguidamente. En la cabecera de las palabras del c´odigo, se colocan los elementos a1, . . . , a10 ∈F2, con el detalle de que a10 =a1+· · · +a9; y en la cola todas las sumas posibles de siete elementos de los anteriores con sub´ındices distintos. C11 =n(a1, . . . , a9, a10 =a1+· · · +a9,X 7 aj) : ai∈F2, i, j ∈ {1,...,10}o⊂F130 2 La longitud del c´odigo es n= 10 + 10 7= 10 + 120 = 130 La dimensi´on es k= 9 y, por lo tanto, el n´umero de palabras que hay en el c´odigo es 29= 512. Para hallar la distancia m´ınima del c´odigo, se calculan los pesos de todas las palabras-c´odigo con m´etodos combinatorios. Como ya vimos en un caso anterior, solo hay una cantidad par de elementos aidistintos de cero en la cabecera, lo que simplifica los c´alculos del peso. Los resultados se muestran en la siguiente tabla y, a continuaci´on, se detallan las cuentas. niP7peso no 2 56 58 45 4 64 68 210 6 56 62 210 8 64 72 45 10 120 130 1 Cuadro 3.22: Pesos del c´odigo y n´umero de palabras •Exactamente dos ai6= 0 : 2+2·8 6= 2 + 2 ·28 = 58 46
•Exactamente cuatro ai6= 0 : 4 + 4 3·6 4+ 4= 4 + (4 ·15 + 4) = 68 •Exactamente seis ai6= 0 : 6 + 6 5·4 2+6 3= 6 + (20 + 6 ·6) = 62 •Exactamente ocho ai6= 0 : 8 + 8 7+8 5= 8 + (8 + 56) = 72 •Exactamente diez ai6= 0 : 10 + 10 7= 10 + 120 = 130 Ya explicamos en un caso similar c´omo hallar el n´umero de palabras-c´odigo. El n´umero de palabras que hay en el c´odigo con exactamente jelementos aidistintos de cero para cada j∈ {2,4,6,8,10} es k j−1+k j. No olvidemos que en todo c´odigo lineal est´a la palabra nula. El c´odigo C11 se trata igualmente de un c´odigo autocomplementario, puesto que la palabra cuyas componentes son todas uno est´a en el c´odigo. Observamos dicha caracter´ıstica en el n´umero y peso de las palabras-c´odigo. El peso de una palabra y su complementaria suman 130, luego debe haber parejas de pesos que sumen dicha cifra. A0= 1 A58 = 45 A62 = 210 A68 = 210 A72 = 45 A130 = 1 Como consecuencia, la distancia m´ınima del c´odigo es d= 58 y se tiene un c´odigo con par´ametros [130,9,58]2. Examinando la tabla correspondiente a c´odigos lineales binarios ´optimos en [Grassl], el c´odigo ´optimo tiene par´ametros [130,9,62]2. 3.12. C´odigo lineal binario de par´ametros [262,10,120]2 Sea el c´odigo lineal binario, subespacio vectorial de F262 2, de par´ametros [262,10, d]2siguiente. En la cabecera de las palabras del c´odigo se colocan los elementos a1, . . . , a10 ∈F2y, en la cola, todas las sumas posibles de cinco elementos de los anteriores con sub´ındices distintos. C12 =n(a1, . . . , a10,X 5 aj) : ai∈F2, i, j ∈ {1,...,10}o⊂F262 2 47
La longitud del c´odigo es n= 10 + 10 5= 10 + 252 = 262 La dimensi´on es k= 10 y, por lo tanto, el n´umero de palabras que hay en el c´odigo es 210 = 1024. Para hallar la distancia m´ınima del c´odigo, se calculan los pesos de todas las palabras-c´odigo con m´etodos combinatorios. Los resultados se muestran en la siguiente tabla y, a continuaci´on, se detallan las cuentas. niP5peso no 1 126 127 10 2 140 142 45 3 126 129 120 4 120 124 210 5 126 131 252 6 132 138 210 7 126 133 120 8 112 120 45 9 126 135 10 10 252 262 1 Cuadro 3.23: Pesos del c´odigo y n´umero de palabras •Exactamente un ai6= 0 : 1 + 9 4= 1 + 126 = 127 •Exactamente dos ai6= 0 : 2+2·8 4= 2 + 2 ·70 = 142 •Exactamente tres ai6= 0 : 3 + 7 2+ 3 ·7 4= 3 + (21 + 3 ·35) = 129 •Exactamente cuatro ai6= 0 : 4 + 4 3·6 2+ 4 ·6 4= 4 + (4 ·15 + 4 ·15) = 124 •Exactamente cinco ai6= 0 : 5 + 1 + 5 3·5 2+ 5 ·5 4= 5 + (1 + 10 ·10 + 5 ·5) = 131 •Exactamente seis ai6= 0 : 6 + 6 5+6 3·4 2+ 6= 6 + (6 + 20 ·6 + 6) = 138 48
•Exactamente siete ai6= 0 : 7 + 7 5+7 3·3 2= 7 + (21 + 35 ·3) = 133 •Exactamente ocho ai6= 0 : 8 + 8 5+8 3= 8 + (56 + 56) = 120 •Exactamente nueve ai6= 0 : 9 + 9 5= 9 + 126 = 135 •Exactamente diez ai6= 0 : 10 + 10 5= 10 + 252 = 262 El c´odigo C12 se trata de un c´odigo autocomplementario. Observamos dicha propiedad en el n´umero y peso de las palabras-c´odigo. El peso de una palabra y su complementaria suman 262, luego debe haber parejas de pesos que sumen dicha cifra. A0= 1 A120 = 45 A124 = 210 A127 = 10 A129 = 120 A131 = 252 A133 = 120 A135 = 10 A138 = 210 A142 = 45 A262 = 1 Como consecuencia, la distancia m´ınima del c´odigo es d= 120 y se tiene un [262,10,120]2c´odigo lineal binario. Examinando la tabla correspondiente a c´odigos lineales binarios ´optimos en [SchSch], se observa que existe un c´odigo [262,10,126]2. Sin embargo, dados esos par´ametros de longitud y dimensi´on, la cota superior para la distancia m´ınima es 128. Nuestro c´odigo de par´ametros [262,10,120]2no tiene especial inter´es en cuanto a c´odigos ´optimos; sin embargo, se trata de un c´odigo de gran longitud. En un c´odigo de tales caracter´ısticas, generalmente no ser´ıamos capaces de hacer los c´alculos a mano para hallar sus pesos, su distancia m´ınima y otros par´ametros. De hecho, hemos tenido que acudir a la tabla de [SchSch] puesto que en la tabla de [Grassl] no se muestran c´odigos lineales binarios con longitud mayor de 256. En resumen, la naturaleza elemental de estos c´odigos permitir´a su utilizaci´on como ejemplos en la asignatura de C´odigos Correctores. Adem´as, estas t´ecnicas pueden proporcionar c´odigos con longitudes mucho mayores a las que hemos visto, v.g., el c´odigo C=n(a1, . . . , a21,X 17 aj) : ai∈F2, i, j ∈ {1,...,21}o es un c´odigo lineal binario de par´ametros [5985,21, d]2. 49
una vez hecho esto, veremos cu´al es el peso m´ınimo que, como ya sabemos, coincide con la distancia m´ınima. Notemos que ambos c´odigos son constant-weight codes, es decir, todas las palabras no nulas tienen el mismo peso, peso 4 en el caso de S3y peso 8 en las palabras del c´odigo C. As´ı pues, formaremos la tabla con todas las combinaciones y pesos posibles. A continuaci´on se describen las cuentas. uivipeso 0 8 64 4 0 60 4 8 60 Cuadro 4.3: Pesos del c´odigo •Si combinamos las dos palabras de peso nulo, la palabra resultante tendr´a peso nulo; si combinamos la palabra de peso nulo del primer c´odigo con una palabra de peso 8 del segundo c´odigo, el peso de la palabra obtenida ser´a 0+8+8·7 = 64 •Si tomamos una palabra de peso 4 del primer c´odigo y la combinamos con palabras de distintos pesos del segundo c´odigo, obtendremos lo siguiente: si la combinamos con la palabra de peso 0, tendremos peso 4+0+4·14 = 60 y si la combinamos con la palabra de peso 8, el peso resultante ser´a 4+8+4·(14 −8) + 8 ·(7 −4) = 60 Seguidamente se muestra la relaci´on que existe entre los pesos y el n´umero de palabras del c´odigo. A0= 1 A60 = 56 A64 = 7 De nuevo, se trata de un c´odigo autoortogonal con solo dos pesos no nulos. La distancia m´ınima es 60 y, por esa raz´on, el c´odigo que hemos construido tiene par´ametros [119,6,60]2. Examinando la tabla de [Grassl] que se muestra a continuaci´on, advertimos que dicho c´odigo es ´optimo; tambi´en lo es en el sentido de la Definici´on 38. n/k 4 5 6 7 8 117 62 60 58 58 56 118 62 60 59 58 56 119 63 60 60 59 57 120 64 61 60 60 58 121 64 62 60 60 58 Cuadro 4.4: Bounds on the minimum distance of linear codes over GF (2) 56
4.3. C´odigo lineal binario ´optimo de par´ametros [191,7,96]2 Sea Cel c´odigo lineal binario de par´ametros [11,3,6]2dado en la secci´on 4.1. Recordemos que las palabras del c´odigo Ctienen peso 0, 6 u 8. Tomemos el c´odigo simplex binario S4. El c´odigo S4tiene par´ametros [15,4,8]2y todas sus palabras no nulas tienen peso 8. Llevando a cabo la construcci´on ya vista dada en (4.2), obtenemos el c´odigo lineal binario B=CS4=n(u1, . . . , u11, v1, . . . , v15, ui+vj) : (u1, . . . , u11)∈ C,(v1, . . . , v15)∈ S4o cuya longitud es n= 11 + 15 + 11 ·15 = 191 y cuya dimensi´on es k= 3 + 4 = 7 De la misma forma que en el caso anterior, se halla la distancia m´ınima. Mostramos los resultados en la siguiente tabla y a continuaci´on se precisan las cuentas. uivipeso 0 8 96 6 0 96 6 8 96 8 0 128 8 8 96 Cuadro 4.5: Pesos del c´odigo •En primer lugar, si tomamos la palabra nula del c´odigo Cy la combinamos con la palabra nula del c´odigo S4, obtenemos la palabra nula. Si, en cambio, la combinamos con una palabra de S4de peso 8, el peso de la palabra resultante ser´a 0 + 8 + 11 ·8 = 96 •En segundo lugar, si escogemos una palabra de Cde peso 6 y la combinamos con la palabra nula de S4, obtenemos una palabra de peso 6+0+6·15 = 96 si la combinamos con una palabra de S4de peso 8, tendremos peso 6+8+6·(15 −8) + 8 ·(11 −6) = 96 es decir, si separamos las coordenadas de las palabras de Ben tres bloques siendo el primer bloque las coordenadas de una palabra de C, el segundo bloque las coordenadas de una palabra de S4y el tercer bloque el resto de coordenadas de la palabra de B, entonces en este caso tendremos peso 6 del primer bloque, peso 8 del segundo bloque y, por ´ultimo, las combinaciones de coordenadas con distintas de cero del primer bloque con coordenadas nulas del segundo bloque y las combinaciones de coordenadas distintas de cero del segundo bloque con coordenadas nulas del primer bloque, esto es, 6 ·(15 −8) + 8 ·(11 −6). En definitiva, la palabra resultante tendr´a peso 96. 57
•Finalmente, si seleccionamos la palabra de peso 8 de Cy la combinamos con la palabra nula de S4, obtenemos una palabra de peso 8+0+8·15 = 128 y si la combinamos con una palabra de peso 8 de S4, el peso ser´a 8+8+8·(15 −8) + 8 ·(11 −8) = 96 Veamos a continuaci´on el n´umero de palabras que hay con cada uno de los pesos del c´odigo. Notemos que el c´odigo, que solo cuenta con dos pesos no nulos, es autoortogonal, puesto que el peso de cada palabra es divisible entre cuatro. A0= 1 A96 = 126 A128 = 1 La distancia m´ınima del c´odigo es, entonces, 96 y Btendr´a par´ametros [191,7,96]2. Hemos comprobado que, efectivamente, el c´odigo de par´ametros [191,7,96]2es un c´odigo ´optimo seg´un nuestra definici´on y tambi´en seg´un la Definici´on 38. Por a˜nadidura, resaltemos el hecho de que casi todas las palabras de Btienen peso 96. Veamos la tabla de [Grassl] donde hemos obtenido la informaci´on relativa a c´odigos ´optimos. n/k 5 6 7 8 9 189 96 96 94 94 92 190 96 96 95 94 92 191 97 96 96 95 92 192 98 96 96 96 93 193 98 96 96 96 94 Cuadro 4.6: Bounds on the minimum distance of linear codes over GF (2) 4.4. Otras construcciones con el c´odigo simplex binario Los siguientes c´odigos se han construido utilizando una t´ecnica an´aloga a la dada en [Til] para c´odigos Reed-Muller. En nuestro caso, en lugar de esta familia de c´odigos, hemos utilizado c´odigos simplex, que, como ya sabemos, est´an estrechamente relacionados con los c´odigos Reed-Muller. Recordemos que el c´odigo simplex binario Srtiene par´ametros [2r−1, r, 2r−1]2y el c´odigo simplex binario aumentado, a˜nadiendo el vector todo unos, tiene par´ametros [2r−1, r + 1,2r−1−1]2y los siguientes pesos: 2r−1−1, 2r−1, 2r−1. Denotemos por Sruna matrix generadora del c´odigo simplex binario Sr. 4.4.1. C´odigo lineal binario ´optimo de par´ametros [94,7,46]2 Sea el c´odigo lineal binario Cun c´odigo cuya matriz generadora es la siguiente: 58
G= 1 1 1 . . . 1 0 0 0 . . . 0 1 1 1 . . . 1 S6S5 La longitud de Ces 63 + 31 = 94 y la dimensi´on es 7. La distancia m´ınima es 46 puesto que la distancia m´ınima del c´odigo S6aumentado es 31 y la del c´odigo S5aumentado es 15. Cualquier combinaci´on de las filas de la matriz dar´a una palabra con peso mayor o igual que 31 + 15 = 46, como ocurre si tomamos la primera fila cuyo peso es 63. Los pesos del c´odigo, en relaci´on al n´umero de palabras que hay con cada uno, son los siguientes: A0= 1 A46 = 31 A47 = 62 A48 = 31 A62 = 1 A63 = 2 En conclusi´on, hemos construido un c´odigo lineal binario de par´ametros [94,7,46]2. Examinando las tablas de [Grassl], observamos que es un c´odigo ´optimo. n/k 5 6 7 8 9 92 47 46 45 44 42-43 93 48 46 46 44 42-44 94 48 47 46 44 43-44 95 48 48 47 45 44 96 48 48 48 46 44 Cuadro 4.7: Bounds on the minimum distance of linear codes over GF (2) 4.4.2. C´odigo lineal binario ´optimo de par´ametros [190,7,95]2 Sea el c´odigo lineal binario Ccon matriz generadora G. Las primeras columnas de Gser´an las columnas del c´odigo simplex binario S7y las siguientes ser´an las columnas del c´odigo simplex binario S6aumentado, a˜nadiendo al c´odigo S6la palabra cuyas componentes son todas uno. G= 1 1 1 . . . 1 S7S6 El c´odigo simplex binario S7tiene par´ametros [127,7,64]2y el c´odigo S6aumentado, [63,7,31]2. Por tanto, el c´odigo C, construido a partir de su matriz generadora, tiene longitud 127 + 63 = 190, dimensi´on 7 y distancia m´ınima 95. Esto ´ultimo es debido a que todas las palabras de S7tienen peso 64 y el peso m´ınimo del c´odigo S6aumentado es 31; por consiguiente cualquier combinaci´on de las filas de Gtiene, como m´ınimo, distancia 64 + 31 = 95, como vemos a continuaci´on. 59
A0= 1 A95 = 63 A96 = 63 A127 = 1 El c´odigo lineal binario Ctiene par´ametros [190,7,95]2. Si ahora a˜nadimos un bit de paridad a este c´odigo, obtenemos un c´odigo de par´ametros [191,7,96]2, que es un c´odigo autoortogonal con solo dos pesos no nulos. Este ´ultimo c´odigo tiene los mismos par´ametros y la misma distribuci´on de pesos que el c´odigo dado en la secci´on 4.3, construido de forma muy diferente. Sin embargo, no es f´acil ver si son c´odigos equivalentes. A0= 1 A96 = 126 A128 = 1 Ambos c´odigos son c´odigos ´optimos, como podemos observar en la siguiente tabla de [Grassl]. n/k 5 6 7 8 9 188 96 95 94 93 91 189 96 96 94 94 92 190 96 96 95 94 92 191 97 96 96 95 92 192 98 96 96 96 93 Cuadro 4.8: Bounds on the minimum distance of linear codes over GF (2) 4.4.3. C´odigo lineal binario ´optimo de par´ametros [254,9,126]2 Sea el c´odigo lineal binario Ccuya matriz generadora es G= 1 1 1 . . . 1 0 0 0 . . . 0 0 0 0 . . . 0 1 1 1 . . . 1 S7S7 El c´odigo simplex binario S7tiene par´ametros [127,7,64]2, luego el c´odigo Ctiene longitud 127 + 127 = 254 y dimensi´on 9 puesto que hay 9 filas linealmente independientes. Si consideramos las dos mitades de la matriz Gque hemos diferenciado, observamos que en cada una de ellas est´a la matriz generadora del c´odigo simplex binario S7aumentado. Con esto en mente, calculamos los pesos del c´odigo: A0= 1 A126 = 127 A127 = 256 A128 = 127 A254 = 1 60
La distancia m´ınima, por tanto, es 126. El c´odigo Ctiene par´ametros [254,9,126]2y es un c´odigo ´optimo, como podemos ver en la siguiente tabla de [Grassl]. n/k 7 8 9 10 11 252 126 126 124 121-123 120-122 253 127 126 125 122-124 120-122 254 128 127 126 122-124 120-123 255 128 128 127 123-124 120-124 256 128 128 128 124 121-124 Cuadro 4.9: Bounds on the minimum distance of linear codes over GF (2) Veamos, a continuaci´on, el caso general. Sea el c´odigo Ccuya matriz generadora es G= 1 1 1 . . . 1 0 0 0 . . . 0 0 0 0 . . . 0 1 1 1 . . . 1 SrSr Sabemos que el c´odigo simplex binario Srtiene par´ametros [2r−1, r, 2r−1]2. De este modo, la longitud de Ces 2r−1+ 2r−1 = 2r+1 −2 y la dimensi´on, r+ 2, pues Gtiene r+2 filas linealmente independientes. Como hemos visto en el caso particular, cada una de las dos mitades de la matriz Gcontiene a la matriz generadora del c´odigo simplex binario aumentado, cuyos pesos son 2r−1−1, 2r−1, 2r−1. Por tanto, los pesos del c´odigo C, en relaci´on al n´umero de palabras con cada uno de los pesos, son los siguientes: A0= 1 A2r−2= 2r−1 A2r−1= 2(2r−1) + 2 A2r= 2r−1 A2r+1−2= 1 En conclusi´on, el c´odigo Ctiene par´ametros [2r+1 −2, r + 2,2r−2]2. 61
Cap´ıtulo 5 Un c´odigo distinto Llegados a este punto, daremos una nueva construcci´on para la obtenci´on de un c´odigo lineal binario ´optimo de par´ametros [110,8,52]2. El hecho de que, a partir de esta t´ecnica, hallemos un c´odigo ´optimo es realmente curioso. Sea Cel c´odigo lineal binario de par´ametros [5,4,2]2definido de la siguiente manera: C=n(a1, a2, a3, a4, a5=a1+a2+a3+a4) : ai∈F2, i ∈ {1,2,3,4,5}o⊂F5 2 Las palabras de Cson todas de peso par a causa del bit de paridad. Los pesos en relaci´on al n´umero de palabras del c´odigo de par´ametros [5,4,2]2se muestran seguidamente. A0= 1 A2= 10 A4= 5 Dado C, definimos el c´odigo Bcomo sigue: en la cabecera de las palabras-c´odigo escribimos los vectores (a1, . . . , a5)∈ C y (b1, . . . , b5)∈ C; y en la cola, por un lado, todas las combinaciones de sumas de tres elementos de los aim´as un elemento bj, y, por otro lado, de forma sim´etrica, todas las combinaciones de aisumadas a adiciones de tres elementos de los bi. B=a1, . . . , a5, b1, . . . , b5,(X 3 ai) + bj, ak+ (X 3 bl): (a1, . . . , a5),(b1, . . . , b5)∈ C Una matriz generadora del c´odigo Btiene la siguiente estructura: las diez primeras columnas, que forman la cabecera, contienen dos matrices generadoras del c´odigo C, lo cual era previsible pues hemos usado dos c´odigos Cpara la construcci´on de B; las siguientes 50 columnas de Gson todas las posibles columnas que combinan columnas con dos y tres unos en las primeras cuatro filas y columnas de la matriz generadora de Cen las segundas cuatro filas; y, las ´ultimas 50 columnas son, de forma an´aloga, todas las posibles columnas que combinan columnas de la matriz generadora de Cen las primeras cuatro filas y columnas con dos y tres unos en las segundas cuatro filas. 63
G= 10001 111111· · · 0 1 · · · 1 1 · · · 0 1 · · · 1 01001 01 1 1 1 1 1 · · · 1 1 · · · 1 0 · · · 0 0 · · · 1 00101 111110· · · 1 0 · · · 0 1 · · · 1 0 · · · 1 00011 000001· · · 1 0 · · · 0 0 · · · 1 0 · · · 1 10001100011· · · 1 1 · · · 1 1 · · · 1 1 · · · 0 001001010010· · · 1 0 · · · 1 0 · · · 1 1 · · · 0 00101001010· · · 1 0 · · · 1 0 · · · 1 1 · · · 1 00011000110· · · 1 0 · · · 1 0 · · · 1 0 · · · 1 El c´odigo Btiene longitud n=5+5+5 3·5+5·5 3= 110 y dimensi´on k= 4+4 = 8. Hallemos la distancia m´ınima de igual forma que en los casos anteriores. La simetr´ıa debida a que ambos c´odigos son el mismo nos ahorrar´a algunos c´alculos. •Si tomamos la palabra nula del primer c´odigo y la palabra nula del segundo, obtenemos la palabra nula de B. Si tomamos la palabra nula del primer c´odigo y una palabra de peso 2 del segundo c´odigo, el peso de la palabra resultante ser´a 0 + 2 + 5 3·2+5·2·3 2= 52 Si combinamos la palabra nula con una palabra de peso 4 del segundo c´odigo, tendremos peso 0 + 4 + 5 3·4+5·4 3= 64 •Si ahora tomamos una palabra de peso 2 del primer c´odigo y la combinamos con una palabra de peso tambi´en 2 del segundo c´odigo, el peso es 2+2+22·3 2·3 + (1 + 3) ·2= 56 y si la combinamos con una palabra de peso 4, el peso de la palabra ser´a 2 + 4 + 2·3 2+ (1 + 3) ·4+2·4 2+ 3 ·4 3= 52 •Por ´ultimo, si escogemos una palabra de peso 4 del primer c´odigo y la combinamos con una del mismo peso del segundo c´odigo, obtenemos peso 4+4+24 3+4 2·4= 64 Los resultados los resumimos en la siguiente tabla. 64
aibipeso 0 2 52 0 4 64 2 2 56 2 4 52 4 4 64 Cuadro 5.1: Pesos del c´odigo Examinemos la relaci´on entre los pesos y el n´umero de palabras del c´odigo y notemos que se trata de un c´odigo con solo tres pesos no nulos. Adem´as, todos los pesos del c´odigos son divisibles entre cuatro y, por ese motivo, Bes un c´odigo autoortogonal. A0= 1 A52 = 120 A56 = 100 A64 = 35 La distancia m´ınima de Bes, por lo tanto, 52. Hemos hallado un c´odigo de par´ametros [110,8,52]2, que es un c´odigo ´optimo. Observemos la tabla obtenida en [Grassl]. n/k 6 7 8 9 10 108 54 53 52 50 49-50 109 54 54 52 51 50 110 55 54 52 52 50-51 111 56 55 53 52 51-52 112 56 56 54 52 52 Cuadro 5.2: Bounds on the minimum distance of linear codes over GF (2) Notemos, no obstante, que el c´odigo de par´ametros [110,8,52]2no es ´optimo conforme a la Definici´on 38 puesto que existen c´odigos lineales binarios de par´ametros [108,8,52]2y [109,8,52]2. 65
coordenada wi6= 0 que se anule al sumarle ui+vi,ui+viser´a distinto de cero, lo cual implica que o −ui+vies distinto de cero o lo es ui. Por consiguiente, por cada coordenada ui+vi+wique se anule siendo wi6= 0 se a˜nade una coordenada no nula a uno de los dos bloques, al menos. En definitiva, el peso de las palabras de este tipo es mayor o igual que dW≥min(3dU,2dV, dW). El c´odigo Ctiene, por tanto, par´ametros [3n, kU+kV+kW,min(3dU,2dV, dW)]3 Veamos la estructura de la matriz generadora del c´odigo C. Si los c´odigos U,VyWtienen matrices generadoras GU,GVyGW, respectivamente, entonces el c´odigo Ctiene la siguiente matriz generadora: GW0 0 GVGV0 GU2GUGU (7.2) En el caso especial en que la construcci´on es (u+v|2u+v|u), el c´odigo resultante tiene par´ametros [3n, kU+kV,min(3dU,2dV)]3 y la matriz generadora tiene la siguiente forma: GVGV0 GU2GUGU(7.3) 7.2.1. C´odigo lineal ternario ´optimo de par´ametros [18,9,6]3 Veamos un ejemplo de la construcci´on (u+v+w|2u+v|u) combinando los siguientes c´odigos lineales ternarios: •Sea Uel c´odigo lineal de par´ametros [6,5,2]3. •Sea Vel c´odigo lineal de par´ametros [6,3,3]3dado por la matriz generadora 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 •y, por ´ultimo, sea Wel c´odigo lineal de par´ametros [6,1,6]3. Notemos que 3dU= 2dV=dW= 6. El c´odigo dado por C=n(u+v+w , 2u+v , u) : u∈ U, v ∈ V, w ∈ Wo 72
tiene longitud 3 ·6 = 18, dimensi´on 5 + 3 + 1 = 9 y distancia m´ınima 6. Se trata de un c´odigo lineal ternario con par´ametros [18,9,6]3, el cual es ´optimo, si bien existen c´odigos de par´ametros [17,9,6]3y [18,10,6]3. Veamos la tabla de [Grassl]. n/k 7 8 9 10 11 16 6 6 5 4 4 17 7 6 6 5 4 18 8 7 6 6 5 19 9 8 7 6 6 20 9 9 8 7 6 Cuadro 7.1: Bounds on the minimum distance of linear codes over GF (3) 7.3. C´odigo Reed-Muller ternario El prop´osito principal de esta secci´on es presentar los c´odigos Reed-Muller ternarios haciendo uso de la construcci´on (u+v+w|2u+v|u) vista en la secci´on anterior, de forma an´aloga a la manera en que se generan los c´odigos Reed-Muller binarios a partir de la construcci´on (u|u+v), como sugiere [KsPa]. Para empezar, describiremos con detalle los c´odigos Reed-Muller m´as simples, con el fin de hacer m´as sencilla la comprensi´on del caso general. Para concluir, citaremos brevemente c´omo se definieron originalmente los c´odigos Reed-Muller ternarios en [Mass]. Se define el c´odigo R3(r, 0) como R3(r, 0) = ({0}, r < 0 F3, r ≥0(7.4) es decir, el c´odigo R3(r, 0) con r < 0 es el c´odigo lineal trivial de longitud uno cuya ´unica palabra es la palabra nula. Siguiendo [KsPa], denotaremos a sus par´ametros por [1,0,∞]3. El c´odigo R3(r, 0) con r≥0 tiene como palabras los elementos del cuerpo finito F3y par´ametros [1,1,1]3. Se define ahora el c´odigo R3(r, m) de forma inductiva como R3(r, m) = n(u+v+w, 2u+v, u) : u∈ R3(r, m−1), v ∈ R3(r−1, m−1), w ∈ R3(r−2, m−1)o(7.5) La recurrencia (7.5) define una familia infinita de c´odigos lineales ternarios. Denotaremos por [n(r, m), k(r, m), d(r, m)]3los par´ametros de R3(r, m) y por G(r, m) la matriz generadora del c´odigo. 7.3.1. C´odigo Reed-Muller ternario R3(1, m) Puesto que los c´odigos Reed-Muller ternarios se definen recurrentemente, estudiaremos, en primer lugar, los c´odigos R3(1, m). Para ello, previamente, examinemos los c´odigos Reed-Muller ternarios R3(0, m). De acuerdo con la definici´on dada en (7.4), el c´odigo R3(0,0) = F3es el c´odigo de par´ametros [1,1,1]3con matriz generadora G(0,0) = [ 1 ]. El c´odigo R3(0,1), a partir de lo anterior, es 73
R3(0,1) = n(u+v+w , 2u+v , u) : u∈ R3(0,0), v ∈ R3(−1,0), w ∈ R3(−2,0)o De nuevo, por la definci´on dada en (7.4), sabemos que los c´odigos R3(r, 0) con r < 0 son los c´odigos de par´ametros [1,0,∞]3yno aportan nada a la construcci´on anterior, al igual que no aportar´an nada los c´odigos R3(r, m) con r < 0 en los casos posteriores. El c´odigo R3(0,1) es, por tanto, el siguiente: R3(0,1) = n(0,0,0),(1,1,1),(2,2,2)o es decir, tiene par´ametros [3,1,3]3y matriz generadora G(0,1) = [1 1 1]. De forma recurrente, observamos que el c´odigo R3(0, m) construido de la forma R3(0, m) = {(u+v+w , 2u+v , u) : u∈ R3(0, m −1), v ∈ R3(−1, m −1), w ∈ R3(−2, m −1)} es el c´odigo R3(0, m) = n(0,0,...,0),(1,1,...,1),(2,2,...,2)o con par´ametros [3m,1,3m]3y matriz generadora G(0, m)=[ m z }| { 1 1 · · · 1] Conocidas la estructura y los par´ametros de los c´odigos R3(0, m), estamos en condiciones de construir los c´odigos R3(1, m). Estos c´odigos se generan de forma especial puesto que se emplea la construcci´on (u+v|2u+v|u), dado que, como vimos en (7.4), los c´odigos R3(−1, m) = [1,0,∞]no aportan nada a la construcci´on. En (7.4) tambi´en se advierte que el c´odigo R3(1,0) = F3es el c´odigo lineal ternario de par´ametros [1,1,1]3y su matriz generadora es G(1,0) = [ 1 ]. Sabiendo esto, somos capaces de construir el c´odigo R3(1,1): R3(1,1) = n(u+v+w , 2u+v , u) : u∈ R3(1,0), v ∈ R3(0,0), w ∈ R3(−1,0)o Hemos visto que los c´odigos R3(1,0) y R3(0,0) tienen, ambos, par´ametros [1,1,1]3. Hallaremos los par´ametros de R3(1,1) teniendo en cuenta que estamos utilizando la construcci´on (u+v|2u+v|u). Por tanto, como vimos en la secci´on anterior, la longitud es n(1,1) = 3 ·1 = 3, la dimensi´on k(1,1) = 1 + 1 = 2 y la distancia m´ınima d(1,1) = min(3 ·1,2·1) = 2. El c´odigo R3(1,1) tiene par´ametros [3,2,2]3. Una matriz generadora de R3(1,1) tiene orden 2 ×3 y la estructura dada en (7.3): G(1,1) = G(0,0) G(0,0) 0 G(1,0) 2G(1,0) G(1,0) =1 1 0 1 2 1 A partir de lo anterior, el c´odigo R3(1,2) R3(1,2) = n(u+v+w , 2u+v , u) : u∈ R3(1,1), v ∈ R3(0,1), w ∈ R3(−1,1)o tiene par´ametros [9,3,6]3y la siguiente matriz generadora de orden 3 ×9: 74
G(1,2) = G(0,1) G(0,1) 0 G(1,1) 2G(1,1) G(1,1) = 1 1 1 1 1 1 0 0 0 1 1 0 2 2 0 1 1 0 1 2 1 2 1 2 1 2 1 Siguiendo la misma l´ınea, el c´odigo R3(1,3) R3(1,3) = n(u+v+w , 2u+v , u) : u∈ R3(1,2), v ∈ R3(0,2), w ∈ R3(−1,2)o es el c´odigo de par´ametros [27,4,18]3y su matriz generadora tiene orden 4×27 y la siguiente forma: G(1,2) = G(0,2) G(0,2) 0 G(1,2) 2G(1,2) G(1,2) = 111111111111111111000000000 111111000222222000111111000 110220110220110220110220110 121212121212121212121212121 El c´odigo R3(1, m) se construye, como vimos en (7.5), de la siguiente forma: R3(1, m) = n(u+v+w , 2u+v , u) : u∈ R3(1, m −1), v ∈ R3(0, m −1), w ∈ R3(−1, m −1)o Su matriz generadora es G(1, m) = G(0, m −1) G(0, m −1) 0 G(1, m −1) 2G(1, m −1) G(1, m −1) y sus par´ametros cumplen las siguientes propiedades, las cuales son consecuencia directa de las propiedades de la construcci´on (u+v+w|2u+v|u) por inducci´on sobre m: •n= 3m •k(1, m) = k(1, m −1) + k(0, m −1) + k(−1, m −1) = k(1, m −1) + 1 + 0 = m+ 1 •d(1, m) = min{3(2 ·3m−2),2·3m−1}= 2 ·3m−1 El c´odigo R3(1, m) tiene par´ametros [3m, m + 1,2·3m−1]3. Este c´odigo cumple la cota de Griesmer (2.3) con igualdad y, por tanto, es ´optimo. m X i=0 2·3m−1 3i= 2 ·3m−1+ 2 ·3m−2+· · · + 2 ·3 + 2 + 1 = 2 ·3m−1 2+ 1 = 3m 7.3.2. C´odigo Reed-Muller ternario R3(2, m) En la misma l´ınea, examinemos los c´odigos Reed-Muller ternarios R3(2, m). Igual que en los casos anteriores, para m= 0, por la definici´on dada en (7.4), el c´odigo R3(2,0) = F3tiene par´ametros [1,1,1]3. 75
El c´odigo general R3(2, m) se construye de la siguiente forma: R3(2, m) = n(u+v+w , 2u+v , u) : u∈ R3(2, m −1), v ∈ R3(1, m −1), w ∈ R3(0, m −1)o Su matriz generadora tiene la siguiente configuraci´on: G(2, m) = G(0, m −1) 0 0 G(1, m −1) G(1, m −1) 0 G(2, m −1) 2G(2, m −1) G(2, m −1) El c´odigo R3(2, m) tiene par´ametros •n= 3m •La dimensi´on es k(2, m) = k(2, m −1) + k(1, m −1) + k(0, m −1) = k(2, m −1) + m+ 1 (7.6) •d(2, m) = min{3·3m−2,2·2·3m−2,3m−1}= 3m−1 obtenidos por inducci´on a partir de las propiedades de la construcci´on (u+v+w|2u+v|u). Veamos cu´al es exactamente la dimensi´on del c´odigo R3(2, m). Calcularemos inicialmente las dimensiones de los primeros c´odigos m´as sencillos y veremos c´omo se ajustan a una forma cuadr´atica. k(2,0) = 1 k(2,1) = 1 + 1 + 1 = 3 k(2,2) = 3 + 2 + 1 = 6 k(2,3) = 6 + 3 + 1 = 10 k(2,4) = 10 + 4 + 1 = 15 k(2,5) = 15 + 5 + 1 = 21 Como se cumple (7.6), sabemos que k(2, m) = am2+bm +c. Hallemos los par´ametros a,byc: Para m= 0, tenemos que c= 1. Para m= 1, tenemos las ecuaciones a+b+ 1 = 3, a+b= 2 y, finalmente, para m= 2, tenemos 4a+ 2b+ 1 = 6. De las tres ecuaciones anteriores, obtenemos los valores a= 1/2 y b= 3/2, por tanto, la siguiente igualdad: k(2, m) = m2+ 3m+ 2 2=(m+ 2)(m+ 1) 2=m+ 2 2 N´otese que m+ 2 2=m+ 1 2+m+ 1 Por inducci´on sobre m, se sigue que el c´odigo R3(2, m) tiene par´ametros 3m,m+2 2,3m−13. 76
7.3.3. C´odigo Reed-Muller ternario R3(3, m) Los c´odigos Reed-Muller ternarios R3(3, m) se construyen a partir de los c´odigos que hemos visto previamente de la forma R3(3, m) = n(u+v+w , 2u+v , u) : u∈ R3(3, m −1), v ∈ R3(2, m −1), w ∈ R3(1, m −1)o y una matriz generadora suya es G(3, m) = G(1, m −1) 0 0 G(2, m −1) G(2, m −1) 0 G(3, m −1) 2G(3, m −1) G(3, m −1) Al igual que en los casos anteriores, los par´ametros de los c´odigos R3(3, m) se obtienen por inducci´on sobre ma partir de las caracter´ısticas de la construcci´on (u+v+w|2u+v|u) y son los siguientes: •n= 3m •La dimensi´on es k(3, m) = k(3, m −1) + k(2, m −1) + k(1, m −1) = k(3, m −1) + m+ 1 2+m(7.7) •d(3, m) = min{3·2·3m−3,2·3m−2,2·3m−2}= 2 ·3m−2 Puesto que la dimensi´on k(3, m) sigue la f´ormula inductiva (7.7), sabemos que k(3, m) = am3+ bm2+cm +d. Calculemos los primeros valores de este par´ametro para hallar los coeficientes del polinomio anterior. k(3,0) = 1 k(3,1) = 1 + 1 + 1 = 3 k(3,2) = 3 + 3 2+ 2 = 8 k(3,3) = 8 + 4 2+ 3 = 17 k(3,4) = 17 + 5 2+ 4 = 31 k(3,5) = 31 + 6 2+ 5 = 51 Dichos coeficientes son a= 1/6, b= 1, c= 5/6 y d= 1. En definitiva, dada la recursi´on (7.7) junto con los valores anteriores, obtenemos la bonita f´ormula k(3, m) = m+ 3 3−m Es curiosa la sucesi´on de dimensiones que hemos ido obteniendo: m 0,m+1 1,m+2 2,m+3 3−m . . . Por ejemplo, el c´odigo R3(3,5) tiene par´ametros [35,51,2·33]3= [243,51,54]3. Sin embargo, est´a lejos de ser un c´odigo ´optimo, puesto que existe un c´odigo de par´ametros [243,51,85]3y, para un c´odigo con dicha longitud y dimensi´on, la distancia m´ınima tiene cota superior 122. El c´odigo R3(3, m) tiene par´ametros 3m,m+3 3−m, 2·3m−23. 77
7.3.4. C´odigo Reed-Muller ternario R3(r, m) En general, los c´odigos R3(r, m) pueden generarse haciendo uso de la construcci´on (u+v+w|2u+v|u) y, como vimos al principio de las secci´on, teniendo en cuenta (7.4), se definen como R3(r, m) = n(u+v+w , 2u+v , u) : u∈ R3(r, m−1), v ∈ R3(r−1, m−1), w ∈ R3(r−2, m−1)o De este modo, su matriz generadora G(r, m) es de la forma dada en (7.2), siendo GU,GVyGW las matrices generadoras de los c´odigos convenientes, como se muestra a continuaci´on: G(r, m) = G(r−2, m −1) 0 0 G(r−1, m −1) G(r−1, m −1) 0 G(r, m −1) 2G(r, m −1) G(r, m −1) Las propiedades del c´odigo Reed-Muller ternario R3(r, m), ya estudiadas en sus formas m´as sencillas, son las siguientes: (i)n(r, m)=3m (ii)k(r, m) = k(r, m −1) + k(r−1, m −1) + k(r−2, m −1) (iii)d(r, m) = ∞, r < 0 3m−r/20≤rpar ≤2m 2·3m−(r+1)/2,1≤rimpar ≤2m−1 1, r > 2m (iv)R3(r, m)⊂ R3(r+ 1, m) Demostraci´on: Las propiedades (i), (ii), (iii) son consecuencia de las propiedades de la construcci´on (u+v+w|2u+v|u) por inducci´on sobre m. La propiedad (iv) tambi´en se demuestra por inducci´on sobre mteniendo en cuenta que U0⊂ U,V0⊂ V yW0⊂ W implica (U0+V0+W0|2U0+V0| U0)⊂(U+V+W | 2U+V | U). R3(0,5) R3(0,4) R3(1,5) R3(0,3) R3(1,4) R3(2,5) R3(0,2) R3(1,3) R3(2,4) R3(3,5) R3(−1,0) R3(0,1) R3(1,2) R3(2,3) R3(3,4) R3(4,5) R3(0,0) R3(1,1) R3(2,2) R3(3,3) R3(4,4) R3(5,5) R3(3,2) R3(4,3) R3(5,4) R3(6,5) R3(5,3) R3(6,4) R3(7,5) R3(7,4) R3(8,5) R3(9,5) Cuadro 7.2: Secuencia de construcci´on de los c´odigos Reed-Muller sobre el cuerpo finito F3 78
Hemos visto que los c´odigos Reed-Muller ternarios se construyen de forma inductiva haciendo uso de la construcci´on (u+v+w|2u+v|u). De esta manera, componen una secuencia de c´odigos formados unos a partir de otros. Este hecho se ilustra en la figura 7.2 y, a continuaci´on, se muestran los par´ametros de algunos de estos c´odigos en la tabla 7.3. Observamos que los c´odigos con mejores par´ametros, a pesar de no ser ´optimos en alg´un caso, son los c´odigos que est´an en el interior de la figura 7.2, pues los c´odigos que la limitan son poco interesantes. n k d n k d R3(r, 0) 1 1 1 R3(5,4) 81 66 6 R3(−r, 0) 1 0 ∞ R3(4,4) 81 50 9 R3(1,1) 3 2 2 R3(3,4) 81 31 18 R3(0,1) 3 1 3 R3(2,4) 81 15 27 R3(3,2) 9 8 2 R3(1,4) 81 5 54 R3(2,2) 9 6 3 R3(0,4) 81 1 81 R3(1,2) 9 3 6 R3(9,5) 243 242 2 R3(0,2) 9 1 9 R3(8,5) 243 237 3 R3(5,3) 27 26 2 R3(7,5) 243 222 6 R3(4,3) 27 23 3 R3(6,5) 243 192 9 R3(3,3) 27 17 6 R3(5,5) 243 147 18 R3(2,3) 27 10 9 R3(4,5) 243 96 27 R3(1,3) 27 4 18 R3(3,5) 243 51 54 R3(0,3) 27 1 27 R3(2,5) 243 21 81 R3(7,4) 81 80 2 R3(1,5) 243 6 162 R3(6,4) 81 76 3 R3(0,5) 243 1 243 Cuadro 7.3: Par´ametros de los c´odigos Reed-Muller sobre el cuerpo finito F3 Para terminar, se expone de forma sucinta y sin demostraciones la definici´on primitiva de los c´odigos Reed-Muller ternarios, que puede verse en [KsPa] y [Mass]. Primeramente, sea G1= 1 0 0 1 1 0 1 2 1 y se define Gmrecursivamente como 79
Gm= Gm−10 0 Gm−1Gm−10 Gm−12Gm−1Gm−1 La fila j-´esima de Gmcorresponde a la fila j-´esima del tri´angulo de Pascal reducida m´odulo 3, es decir, Gmes una tabla de los coeficientes binomiales reducidos m´odulo 3. En [Mass] se prueba que Gmtiene la siguiente propiedad: un c´odigo generado por un subconjunto de las filas de Gmcuyos pesos sean {w1, w2, . . . , wk}tiene distancia m´ınima min(w1, w2, . . . , wk). Por tanto, si elegimos todas las filas de Gmcuyos pesos sean w≥d, se genera un c´odigo con distancia m´ınima d. Se dice que dicho c´odigo es un c´odigo Reed-Muller ternario. Veamos, usando inducci´on, que cualquier c´odigo Reed-Muller ternario, o cualquier c´odigo generado a partir de las filas de Gm, puede generarse recursivamente usando la construcci´on (u+v+w|2u+v|u). Sean los c´odigos de par´ametros [1,1,1]3y [1,0,∞]3anteriores. Es claro que cualquier combinaci´on de las filas de G1puede obtenerse con la construcci´on (u+v+w|2u+v|u) siendo • W = [1,1,1]3si la primera fila de G1est´a incluida; W= [1,0,∞]3en otro caso. • V = [1,1,1]3si la segunda fila de G1est´a incluida; V= [1,0,∞]3en otro caso. • U = [1,1,1]3si la tercera fila de G1est´a incluida; U= [1,0,∞]3en otro caso. De forma similar, si Ges una matriz generadora obtenida a partir de filas de Gm, entonces, por definici´on de Gm,Gse escribe de la forma siguiente: GW0 0 GVGV0 GU2GUGU donde GW,GVyGUconsisten en una combinaci´on de filas de Gm−1. Claramente, asignando U, VyWa los c´odigos generados por GU,GVyGW, respectivamente, y aplicando la construcci´on (u+v+w|2u+v|u), se produce el c´odigo generado por G. Por inducci´on, todos los c´odigos generados por las filas de Gmpueden obtenerse inductivamente con la construcci´on (u+v+w|2u+v|u) usando los c´odigos [1,1,1]3y [1,0,∞]3como bloques de construcci´on. Una familia infinita de c´odigos ternarios con propiedades similares a las de los c´odigos Reed-Muller binarios pueden construirse recursivamente a partir de los c´odigos [1,1,1]3y [1,0,∞]3. 7.4. C´odigos lineales ternarios obtenidos con Maple Se muestran, a continuaci´on, algunos ejemplos en los que, aplicando t´ecnicas similares a las descritas en los Cap´ıtulos 3 y 5 a c´odigos lineales ternarios, se obtienen c´odigos pr´oximos a c´odigos ´optimos. Como ap´endice mostraremos los c´odigos Maple utilizados para hallar todos los pesos de los c´odigos. 80
7.4.1. C´odigo lineal ternario de par´ametros [21,6,10]3 Sea Cel c´odigo lineal ternario cuyas palabras-c´odigo tienen la siguiente forma: se colocan seis elementos libres ai∈F3, seguidos de todas las sumas posibles de cuatro elementos de los anteriores con sub´ındices distintos. C=n(a1, a2, a3, a4, a5, a6,X 4 aj) : ai∈F3, i, j ∈ {1,...,6}o⊂F21 3 La longitud del c´odigo Ces n= 6 + 6 4= 6 + 15 = 21 y la dimensi´on es k= 6, por lo que hay 36= 729 palabras en el c´odigo. Una matriz generadora de Ctiene la siguiente estructura: G= 1 0 0 0 0 0 1 1 1 1 · · · 0 0 1 0 0 0 0 1 1 1 1 · · · 0 0 0 1 0 0 0 1 1 1 0 · · · 1 0 0 0 1 0 0 1 0 0 1 · · · 1 0 0 0 0 1 0 0 1 0 1 · · · 1 0 0 0 0 0 1 0 0 1 0 · · · 1 Debido a que ahora las operaciones son en el cuerpo F3, los c´alculos no son f´acilmente realizables a mano y hemos recurrido a Maple para hallar todos los pesos del c´odigo, en relaci´on al n´umero de palabras con cada peso, y, en consecuencia, la distancia m´ınima. A0= 1 A10 = 42 A11 = 42 A12 = 140 A14 = 210 A15 = 70 A16 = 210 A21 = 14 La distancia m´ınima del c´odigo Ces d= 10 y, por tanto, hemos construido un c´odigo lineal ternario de par´ametros [21,6,10]3. Examinando las tablas de [Grassl], observamos que el c´odigo ´optimo es un c´odigo de par´ametros [21,6,11]3, luego nuestro c´odigo Ces un c´odigo casi ´optimo. N´otese que el correspondiente c´odigo binario C∗=n(a1, a2, a3, a4, a5, a6,X 4 aj) : ai∈F2, i, j ∈ {1,...,6}o⊂F21 2 tiene par´ametros [21,6,6]2ya que, si todos los elementos de la cabecera son distintos de cero, a1=a2=. . . =a6= 1, el peso de dicha palabra es 6. 81
Bibliograf´ıa [Bier] J. Bierbrauer,Introduction to Coding Theory, Chapman & Hall, CRC, 2005. [BoJac] I. Bouyukliev, E. Jacobsson, “Results on binary linear codes with minimum distance 8 and 10”, IEEE Trans. Inf. Theory, vol. 57, no. 9, pp. 6089-6093, Sep. 2011. [BoJaf] I. Bouyukliev, D. Jaffe, “Optimal binary linear codes of dimension at most seven”, Discrete Mathematics, 226, pp.51-70, 2001. [BoJaVe] I. Bouyukliev, D. Jaffe, V. Vavrek, “The smallest length of eight-dimensional binary linear codes with prescribed minimum distance”, IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1539-1544, Jul. 2000. [Ding] K. Ding, C. Ding, “Binary linear codes with three weights”, IEEE Communications Letters, vol. 18, no. 11, pp. 1879-1882, Nov. 2014. [DoGuSi] S. Dodunekov, S. Guritman, J. Simonis, “Some new results on the minimum length of binary linear codes of dimension nine”, IEEE Trans. Inf. Theory, vol. 45, no. 7, pp. 2543-2546, Nov. 1999. [GuBh] T.A. Gulliver, V.K. Bhargava, “New optimal binary linear codes of dimensions 9 and 10”, IEEE Trans. Inf. Theory, vol. 43, no. 1, pp. 314-316, Jan. 1997. [Hill] R. Hill,A First Course in Coding Theory, Oxford University Press, 1986. [Hoff] D.G. Hoffman, D.A. Leonard, C.C. Lindner, K.T. Phelps, C.A. Rodger, J.R. Wall,Coding Theory, The Essentials, Marcel Dekker, P.A.M., New York, 1991. [HuPl] W.C. Huffman, V. Pless,Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003. [KsPa] F.R. Kschischang, S. Pasupathy, “Some ternary and quaternary codes and associated sphere packings”, IEEE Trans. Inf. Theory, vol. 38, no. 2, pp. 227-246, Mar. 1992. [LiPi] R. Lidl, G. Pilz,Applied Abstract Algebra, Springer, 1998. [Mar] J.E. Marcos, comunicaci´on personal, 2019. [Mass] J.L. Massey, D.J. Costello, J. Justesen, “Polynomial weights and code constructions”, IEEE Trans. Inf. Theory, vol. IT-19, pp. 101-110, Jan. 1973. [MuTe] C. Munuera, J. Tena,Codificaci´on de la informaci´on, Universidad de Valladolid, Valladolid 1997. 89
[Sha] C.E. Shannon, “A mathematical theory of communication”, Bell Syst. Tech. J., 27, pp. 379-423 and 623-656, 1948. [Til] H.v. Tilborg, “The smallest length of binary 7-dimensional linear codes with prescribed minimum distance”, Discrete Mathematics, 33, pp. 197-207, 1981. [WaDiXu] Q. Wang, K. Ding, R. Xue, “Binary linear codes with two weights”, IEEE Communications Letters, vol. 19, no. 7, pp. 1097-1100, Jul. 2015. [Grassl] M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes”. Online available at http://www.codetables.de/ [SchSch] W.Ch. Schmid, R. Sch¨ urer,http://mint.sbg.ac.at/ 90