G ado en Ma em´
a ica Compu acional
T abajo Final de G ado
Una in oducci´on a los c´odigos co ec o es
de e o es
Au o :
Elena Can e o L´
opez
Tu o acad´emico:
Ca los Galindo Pas o
Fecha de lec u a: 24 de Julio de 2023
Cu so acad´emico 2022/2023
Ag adecimien os
A mi u o , Ca los Galindo, po su ayuda e implicaci´on en la ealizaci´on del abajo. A mis
pad es y a mi he mana po su apoyo y paciencia.
G acias.
Resumen
La eo ´ıa de co ecci´on de e o es se inici´o en el a˜no 1948 pa a minimiza los e o es p o-
ducidos cuando se en ´ıa una g an can idad de in o maci´on. En es e abajo mos a emos los
aspec os m´as elemen ales de es a eo ´ıa, incluyendo una in oducci´on a la decodi icaci´on po
s´ınd omes y al p oblema p incipal de la eo ´ıa de la codi icaci´on lineal.
Palab as cla e
C´odigos co ec o es de e o es; s´ınd ome; p oblema p incipal de la codi icaci´on.
Keywo ds
E o -co ec ing codes; synd ome; he main p oblem o coding heo y.
´
Indice gene al
1. In oducci´
on 7
2. P ime as nociones sob e c´
odigos 9
2.1. C´odigos ......................................... 9
2.2. Pa ´ame os de un c´odigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3. In oducci´on a los cue pos ini os . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4. Espacios ec o iales sob e cue pos ini os . . . . . . . . . . . . . . . . . . . . . . . 18
3. In oducci´
on a los c´
odigos lineales 21
3.1. C´odigoslineales..................................... 21
3.1.1. Equi alencia de c´odigos lineales . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2. Codi icando y decodi icando con un c´odigo lineal . . . . . . . . . . . . . . . . . . 24
3.2.1. Codi icando con un c´odigo lineal . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.2. Decodi icando con un c´odigo lineal . . . . . . . . . . . . . . . . . . . . . . 25
3.2.3. P obabilidad de co ecci´on de e o es . . . . . . . . . . . . . . . . . . . . . 26
3.2.4. P obabilidad de de ecci´on de e o es . . . . . . . . . . . . . . . . . . . . . 28
5

3.3. El c´odigo dual, la ma iz de con ol de pa idad y la decodi icaci´on po s´ınd omes 28
3.3.1. Decodi icaci´on po s´ınd ome . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.2. Decodi icaci´on incomple a . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4. El p oblema p incipal de la eo ´ıa de la codi icaci´on lineal . . . . . . . . . . . . . 35
3.4.1. El p oblema MLCT pa a d=3........................ 37
3.4.2. El p oblema MLCT pa a d=4 . . . . . . . . . . . . . . . . . . . . . . . . . 40
4. Conclusi´
on 47
6
Cap´ı ulo 1
In oducci´on
El a ´ıculo de Shannon [29] puede conside a se como el abajo cien ´ı ico que p odujo el
nacimien o de la eo ´ıa de c´odigos co ec o es de e o es. Los c´odigos co ec o es de e o es son
una he amien a imp escindible cuando se en ´ıa una g an can idad de in o maci´on po medios
elec ´onicos. Es os c´odigos almacenan an o la in o maci´on a se en iada, como in o maci´on
ex a pa a co egi los e o es que se p oducen debido al uido del canal de ansmisi´on o de
los mecanismos que manejan la in o maci´on. Una de las p ime as u ilidades de es os c´odigos
se p odujo a la ho a de en ia o os desde el espacio, ya que, el canal (el espacio) es uidoso.
La apa ici´on en las ´ul imas d´ecadas de mul i ud de disposi i os que almacenan y en ´ıan g an-
des iche os hace imp escindible el uso de es os c´odigos que ga an izan la iabilidad de es os
disposi i os de uso dia io ( el´e onos m´o iles, o denado es, aplicaciones que manipulan o os,
e c.).
La llegada de la p ime a compu ado a cu´an ica no ha hecho pe de el in e ´es en la co ecci´on
de e o es sino que lo ha aumen ado, ya que las compu ado as cu´an icas come en, de momen o,
muchos m´as e o es que las compu ado as cl´asicas.
En es e abajo, hacemos una in oducci´on muy elemen al a la eo ´ıa de c´odigos co ec o es
de e o es. Nues o p op´osi o es ´unicamen e explica su u ilidad y algunos de sus compo a-
mien os y p oblemas asociados b´asicos. En nues a edacci´on hemos conside ado ´unicamen e
obje os simples pa a cons ui c´odigos co ec o es, como cue pos ini os y espacios ec o ia-
les sob e ellos. Tambi´en explicamos las ´ecnicas m´as b´asicas pa a el codi icado y decodi icado.
Adem´as es udiamos algunos aspec os elemen ales del p incipal p oblema de la eo ´ıa de c´odigos
co ec o es.
Es a memo ia s´olo p e ende deja al lec o lis o pa a p o undiza en es a in e esan e eo ´ıa.
Noso os hemos u ilizado b´asicamen e la e e encia [11]. Pa a p o undiza en el es udio de es os
c´odigos algunos ex os de in e ´es son [32], [27], [26], [20], [14] y [17].
7
8
Cap´ı ulo 2
P ime as nociones sob e c´odigos
2.1. C´odigos
En es e abajo amos a es udia algunos aspec os elemen ales de los c´odigos co ec o es de
e o es, as´ı como su o igen e impo ancia.
Los c´odigos co ec o es de e o es se emplean pa a la co ecci´on de e o es en mensajes que
se ansmi en a a ´es de canales con uido. Los canales de ansmisi´on pueden se : una l´ınea
ele ´onica o una comunicaci´on ´ıa sa ´eli e, en e muchos o os. Algunos ejemplos de uido son
aquellas dis o siones p oducidas po in e e encias, un e o humano o un ma e ial de ec uoso.
La unci´on de es os c´odigos es a˜nadi al mensaje o iginal una edundancia que pe mi a, al
ecep o , econs ui el mensaje co ec amen e aunque es e con enga e o es. Es e p oceso de
modi icaci´on del mensaje o iginal se denomina codi icaci´on. As´ı mismo, cuando se ecibe el
mensaje y se e i a la edundancia, se es ´a ealizando un p oceso de decodi icaci´on.
Las palab as-c´odigo de un c´odigo bina io son simplemen e sucesiones ini as de 0s y 1s. En es os
casos la edundancia incluida en las palab as-c´odigo consis e en a˜nadi un n´ume o adecuado de
0s y 1s dependiendo del mensaje. Con es a edundancia hacemos que la p obabilidad de que
el ecep o econs uya el mensaje o iginal sea mayo . Po an o, lo m´as con enien e se ´ıa que
las palab as-c´odigo engan poca simili ud en e ellas, ya que as´ı es menos p obable con undi las
debido a los e o es in oducidos po el uido.
De inimos un c´odigo q-a io como una secuencia de s´ımbolos pe enecien es a un conjun o Fq=
{λ1, λ2, ..., λq}con qelemen os. Po ende, si aplicamos es a no aci´on, el c´odigo bina io se ´ıa
equi alen e a un c´odigo 2-a io. Si las palab as-c´odigo ienen una medida ija de ns´ımbolos, se
dice que pe enecen a un c´odigo de bloque de longi ud n. Po an o podemos deci que (Fq)n
con iene odas las sucesiones posibles de nelemen os del conjun o Fq. Y adem´as su ca dinal
se ´ıa qn.
Vamos a de ini con cie o de alle la dis ancia de la que usualmen e se habla cuando que emos
9
1 = 1111111. Po an o, Ces un (7, 16, 3)-c´odigo.
Va iedades
Bloques
B1B2B3B4B5B6B7
11000101
21100010
30110001
41011000
50101100
60010110
70001011
(2.2)
2.3. In oducci´on a los cue pos ini os
Pa a acili a el uso y an´alisis de los c´odigos co ec o es de e o es es con enien e usa una
es uc u a algeb aica. Es o es especialmen e ´u il pa a ene un al abe o en el cual es posible
suma , es a , mul iplica y di idi sin es icci´on. En o as palab as, que emos da le a Fquna
es uc u a de cue po. Veamos la de inici´on.
De inici´
on 8. Un cue po Fes un conjun o de elemen os con dos ope aciones: + (llamada
adici´on) y ·(mul iplicaci´on) que sa is ace las siguien es p opiedades.
1. Fes ce ado pa a + y ·, es deci , si a, b ∈Fen onces a+bya·b∈F.
2. Leyes conmu a i as: a+b=b+a,a·b=b·a.
3. Leyes asocia i as: (a+b) + c=a+ (b+c), a·(b·c)=(a·b)·c.
4. Leyes dis ibu i as: a·(b+c) = a·b+a·c.
5. a+ 0 = apa a odo a∈F.
6. a·1 = apa a odo a∈F.
7. Pa a cada a∈Fexis e un elemen o in e so pa a la suma o adici´on (−a)∈F al que
a+ (−a) = 0.
8. Pa a cada a= 0 en F, exis e un elemen o in e so de la mul iplicaci´on a−1∈F al que
a·a−1= 1.
Las dos siguien es p opiedades de un cue po se deducen ´acilmen e de la de inici´on.
Lema 6. En cualquie cue po Fse cumplen las siguien es p opiedades:
1. a0=0pa a odo a∈F.
2. ab = 0 implica que a= 0 ob= 0. As´ı, el p oduc o de dos elemen os de un cue po, que
sean dis in os de 0, se ´a dis in o de 0.
Demos aci´on.
16

1. Tenemos a0 = a(0 + 0) = a0 + a0. A˜nadiendo el in e so espec o de la suma de a0 en
ambos si ios ob enemos: 0 = a0+(−a0) = a0+a0+(−a0) = a0+0 = a0. Po ello, a0 = 0.
2. Supongamos que ab = 0. Si a= 0, en onces a iene un in e so pa a la mul iplicaci´on y, en
consecuencia, b= 1 ·b= (a−1a)b=a−1(ab) = a−10 = 0. Po an o, ab = 0 implica a= 0
ob= 0.
De inici´
on 9. Un conjun o de elemen os con dos p opiedades in e nas + y ·que sa is ace las
p opiedades de cue pos desde la (1) has a la (7), pe o no necesa iamen e la (8) se denomina
anillo.
No a 2. Po comodidad, emplea emos la palab a anillo pa a e e i nos a anillo conmu a i o o
abeliano con la iden idad.
De inici´
on 10. Un cue po ini o es un cue po que iene un n´ume o ini o de elemen os. A es e
n´ume o se le llama o den del cue po. El siguien e esul ado undamen al sob e cue pos ini os
ue demos ado po E a is e Galois (1811-1832).
Teo ema 5. Exis e un cue po de o den qsi y solo si qes una po encia de un n´ume o p imo.
Adem´as, si qes una po encia de un n´ume o p imo, en onces solo hay un cue po de ese o den.Un
cue po de o den qa menudo se denomina cue po de Galois de o den qy se deno a como GF(q).
La demos aci´on de es e eo ema se puede encon a en [16].
De inici´
on 11. Sea mun n´ume o en e o posi i o ijo. Dos en e os aybse llaman cong uen es
m´odulo m, simbolizado po a ≡bm´od m, si a−bes di isible po m, es deci , si a=km +b
pa a alg´un en e o k. Esc ibimos a ≡ bm´od msi aybno son cong uen es m´odulo m. Cada
n´ume o en e o, cuando se di ide po m, iene un esiduo (o es o) p incipal ´unico igual a uno de
los n´ume os en e os en el anillo de cong uencia Zm{0,1, . . . , m −1}. Se demues a ´acilmen e
que dos n´ume os en e os son cong uen es m´odulo msi, y solo si, ienen los mismos esiduos
p incipales en la di isi´on po m.
Teo ema 6. Suponemos que a≡a′m´od myb≡b′m´od m. En onces:
1. a+b≡a′+b′m´od m.
2. ab ≡a′b′m´od m.
Demos aci´on. Sabemos que a=a′+km yb=b′+lm pa a algunos en e os kyl. En onces:
1. a+b=a′+b′+ (k+l)my as´ı a+b≡a′+b′m´od m.
2. ab =a′b′+ (kb′+a′l+klm)my po ello, ab ≡a′b′m´od m.
El Teo ema 6 pe mi e calcula cong uencias sin abaja con n´ume os g andes. Obs´e ese, que
si a≡a′m´od m, en onces el uso epe ido de (2) mues a que, pa a odo en e o posi i o n,
an≡(a′)nm´od m.
Teo ema 7. Zmes un cue po si, y solo si, mes un n´ume o p imo.
17
Demos aci´on. P ime o, suponemos que mno es p imo. En onces m=ab pa a algunos en e os
posi i os a, b < m. En onces ab ≡0 m´od m, con a≡ 0 m´od myb≡ 0 m´od m.
En consecuencia, en Zmel p oduc o de los elemen os dis in os de 0, ayb, es 0 y, po an o, po
el Lema 6, se puede a i ma que Zmno es un cue po.
Aho a suponemos que mes p imo. Pa a demos a que Zmes un cue po, es su icien e
mos a que odo elemen o dis in o de 0 pe enecien e a Zm iene un in e so espec o a la
mul iplicaci´on. Tomamos aun elemen o dis in o de 0 en Zmy conside amos los m−1 elemen os
1a, 2a, . . . , (m−1)a. Es os elemen os son dis in os de 0, po que los elemen os ia no pueden ene
al n´ume o p imo mcomo di iso si iyano lo ienen. Adem´as, los elemen os son dis in os unos
de o os po que ia =ja implica que (i−j)a≡0 m´od mlo que obliga a que msea un di iso de
(i−j)ay po ello mes un di iso de i−j, ya que mes p imo y no di ide a a. En consecuencia,
i=j, ya que ambos i, j ∈ {1,2, . . . , m −1}.
As´ı, que en Zmlos m−1 elemen os 1a, 2a, . . . , (m−1)adeben coincidi como conjun o con
los elemen os 1,2, . . . , m −1, y uno de ellos, ja, debe se igual a 1. En onces jse ´a el in e so
de a.
2.4. Espacios ec o iales sob e cue pos ini os
En es e apa ado amos a asumi que qes una po encia de un n´ume o p imo y deno amos
po Fq´o GF(q) el cue po ini o de qelemen os, a los que llama emos escala es. El conjun o
GF(q)nde odas las n- uplas o denadas sob e GF(q) se deno a ´a po V(n, q) y sus elemen os
se llama ´an ec o es. De inimos dos ope aciones den o de V(n, q):
1. Suma de ec o es: si x= (x1, x2, . . . , xn) e y= (y1, y2, . . . , yn)∈V(n, q) en onces x+y=
(x1+y1, x2+y2, . . . , xn+yn).
2. Mul iplicaci´on de un ec o po un escala : si x= (x1, x2, . . . , xn)∈V(n, q) y a∈GF(q)
en onces ax = (ax1, ax2, . . . , axn).
Se puede demos a ´acilmen e que V(n, q) sa is ace los axiomas de espacio ec o ial sob e el
cue po Fq. Es deci , pa a odo u, , w ∈V(n, q) y pa a odo a, b ∈GF(q) se cumple que:
1. u+ ∈V(n, q).
2. (u+ ) + w=u+ ( +w).
3. El ec o o mado po odo 0s, 0 = (0,0,...,0) ∈V(n, q) y sa is ace que u+0 = 0+u=u.
4. Dado u= (u1, u2, . . . , un)∈V(n, q), el elemen o −u= (−u1,−u2,...,−un)∈V(n, q) y
sa is ace u+ (−u) = 0.
5. u+ = +u.
6. a ∈V(n, q).
7. a(u+ ) = au +a , (a+b)u=au +bu.
18
8. (ab)u=a(bu).
9. 1u=u, donde 1 es la iden idad mul iplica i a de GF(q).
Un subconjun o de V(n, q) se llama subespacio ec o ial de V(n, q) si es un espacio ec o ial
bajo la suma y mul iplicaci´on escala de inidas en V(n, q). El conjun o i ial 0 y el espacio
comple o V(n, q) son subespacios ec o iales de V(n, q). Un subespacio ec o ial se llama no
i ial si con iene al menos un ec o dis in o de 0.
Teo ema 8. Un conjun o C=∅incluido en V(n, q)es un subespacio ec o ial de V(n, q)si y
s´olo si Ces ce ado bajo la suma y la mul iplicaci´on escala , es deci , si y s´olo si Csa is ace
es as dos condiciones:
1. Si x, y ∈Cen onces x+y∈C.
2. Si a∈GF(q)yx∈Cen onces ax ∈C.
Demos aci´on. Se demues a ´acilmen e que si Csa is ace los axiomas 1 y 2 del Teo ema 8 de
espacio ec o ial, en onces Csa is ace odos los axiomas 1-9 de la subsecci´on 2,4 (con V(n, q)
eemplazado po C) pa a un espacio ec o ial. Pa a mos a que 0 ∈C, elegimos cualquie
x∈C, en onces, po (2), 0 = 0xy es o, po an o, pe enece a C. La p opiedad (2) ambi´en
mues a que si ∈C, en onces − ∈C, pa a − = (−1) .
Una combinaci´on lineal de ec o es 1, 2, . . . , pe enecien es a V(n, q), es un ec o de
la o ma a1 1+a2 2+· · · +a , donde los elemen os ai ep esen an escala es.
Un conjun o de ec o es { 1, 2, . . . , }es linealmen e dependien e si exis en los escala es no
odos ce o, a1, a2, . . . , a ales que
a1 1+a2 2+· · · +a = 0.
Po an o, di emos que los ec o es 1, 2, . . . , son linealmen e independien es, si cuando se
cumple
a1 1+a2 2+· · · +a = 0,
en onces a1=a2=· · · =a = 0.
Sea Cun subespacio ec o ial de V(n, q). Un subconjun o de C,
{ 1, 2, . . . , }
ecibe el nomb e de conjun o gene ado de Csi odo ec o de Cpuede se exp esado como una
combinaci´on lineal de 1, 2, . . . , . Un conjun o linealmen e independien e que adem´as es un
conjun o gene ado de C ecibe el nomb e de base de C.
Teo ema 9. Suponemos que Ces un subespacio ec o ial no i ial de V(n, q). En onces cual-
quie conjun o gene ado de Ccon iene una base de C.
Demos aci´on. Suponemos que { 1, 2, ..., }es un conjun o gene ado de C. Si es linealmen e
dependien e, en onces exis en escala es a1, a2, ..., a , al menos uno dis in o de 0, ales que:
a1 1+a2 2+... +a = 0.
19
Si omamos ajdis in o de 0 en onces
j=−(aj)−1
X
i=1,i=j
ai i
y, po an o, jes una combinaci´on lineal de o as i. De al mane a jes edundan e y puede
se omi ida del conjun o { 1, 2, ..., }pa a ene un conjun o gene ado de Cm´as peque˜no.
En onces, podemos omi i gene ado es edundan es, uno cada ez, has a que consigamos un
conjun o gene ado linealmen e independien e. Como se u iliza un conjun o ini o, el p oceso
debe inaliza .
Como cualquie subespacio ec o ial Cde V(n, q) con iene un conjun o gene ado ini o, po
el Teo ema 9 se deduce que odo subespacio ec o ial no i ial iene base. Una base puede se
pensada como un conjun o gene ado minimal, que no con iene ning´un gene ado edundan e.
Teo ema 10. Suponemos que { 1, 2, . . . , k}es una base de un subespacio ec o ial Cde
V(n, q). En onces:
1. Todo ec o de Cpuede se exp esado de mane a ´unica como una combinaci´on lineal de
ec o es de la base.
2. El subespacio Ccon iene exac amen e qk ec o es.
Demos aci´on.
1. Suponemos que un ec o xde Cse ep esen a de dos mane as como una combinaci´on
lineal de 1, 2, . . . , k. Conc e amen e de las siguien es o mas:
x=a1 1+a2 2+. . . +ak k,
x=b1 1+b2 2+. . . +bk k.
En onces (a1−b1) 1+ (a2−b2) 2+· · · + (ak−bk) k= 0. Pe o el conjun o { 1, 2, . . . , k}
es linealmen e independien e y ai−bi= 0 pa a i= 1,2, . . . , k. Es deci , ai=bipa a
i= 1,2, . . . , k.
2. Po la demos aci´on del p ime apa ado, los qk ec o es Pk
i=1 ai i ales que (aipe enece
aGF(q)) son p ecisamen e los ec o es dis in os de C.
Del Teo ema 10 se deduce que cualesquie a dos bases de un subespacio Ccon ienen el mismo
n´ume o de ec o es. Po ello, |C|=qk, y es e n´ume o kse llama la dimension del subespacio
C, se deno a po dim(C). Ya hemos mos ado una base de V(n, q) que iene n ec o es, po lo
que dim(V(n, q)) = n.
En es e apa ado se ha esc i o u ilizando in o maci´on ex a´ıda de las e e encias: [1], [8],
[15], [19], [20], [22], [24], [31] y [33].
20
Cap´ı ulo 3
In oducci´on a los c´odigos lineales
3.1. C´odigos lineales
En es e apa ado asumi emos que el al abe o Fqes el cue po de Galois Fq=GF(q), donde
qes una po encia de un n´ume o p imo, y conside a emos el espacio ec o ial V(n, q)=(Fq)n.
En es e abajo esc ibi emos el ec o (x1, x2, . . . , xn) como x1x2· · · xn. Un c´odigo lineal sob e
GF(q) es simplemen e un subespacio ec o ial de V(n, q), pa a alg´un en e o posi i o n. Es deci ,
un subconjun o Cde V(n, q) es un c´odigo lineal si, y solo si:
1. u+ ∈C, pa a odo uy en C.
2. au ∈Cpa a odo u∈C,a∈GF(q).
En conc e o, un c´odigo bina io es lineal si, y solo si, la suma de dos palab as-c´odigo cualesquie a
da como esul ado una palab a-c´odigo.
Si Ces un subespacio ec o ial de V(n, q) y su dimensi´on es k, en onces el c´odigo lineal Cse
dice que iene pa ´ame os [n, k], o, si especi icamos la dis ancia m´ınima d, iene pa ´ame os
[n, k, d].
No a 3.
1. Un c´odigo q-a io [n, k, d] es un c´odigo q-a io (n, qk, d) po el Teo ema 10. Sin emba go, no
odo c´odigo con pa ´ame os (n, qk, d) es un c´odigo lineal de pa ´ame os [n, k, d].
2. El ec o 0 = (0,0,...,0) au om´a icamen e pe enece a un c´odigo lineal.
3. Los c´odigos lineales a eces se llaman c´odigos de g upo.
El peso w(x) de un ec o x∈V(n, q) se de ine como el n´ume o de en adas de xdis in o
de 0. Una de las p opiedades m´as ´u iles de un c´odigo lineal es que su dis ancia m´ınima es igual
al alo m´as peque˜no de los pesos de sus palab as-c´odigo dis in as de 0. Pa a demos a es o
necesi amos un lema muy sencillo.
Lema 7. Si x, y ∈V(n, q), en onces
d(x, y) = w(x−y).
21

Demos aci´on. El ec o x−y iene alo es dis in os de 0 cuando xeydi ie en.
No a 4. Pa a q= 2, el Lema 7 es igual que el Lema 3, eniendo en cuen a que “+” es lo mismo
que “−” si abajamos con m´odulo 2.
Teo ema 11. Sea Cun c´odigo lineal y sea w(C)el peso m´as peque˜no de las palab as-c´odigo
de Cdis in as de 0. En onces d(C) = w(C).
Demos aci´on. Exis en xeypalab as-c´odigo de C ales que d(C) = d(x, y). En onces, po el
Lema 7, d(C) = w(x−y)≥w(C),
pues o que x−yes una palab a-c´odigo del c´odigo lineal C.
Po o a pa e, pa a alguna palab a-c´odigo x∈C,
w(C) = w(x) = d(x, 0) ≥d(C),
ya que 0 pe enece al c´odigo lineal C. Po an o, d(C)≥w(C) y w(C)≥d(C), lo que demues a
que d(C) = w(C).
A con inuaci´on e emos algunas de las en ajas y des en ajas de los c´odigos lineales.
1. Ven aja 1. En un c´odigo gene al con Mpalab as-c´odigo, pa a encon a la m´ınima dis-
ancia debemos ealiza M
2=1
2M(M−1) compa aciones. Sin emba go, po el Teo ema
11 podemos busca la m´ınima dis ancia de un c´odigo lineal examinando solo los pesos de
M−1 palab as-c´odigo dis in as de 0.
2. Ven aja 2. Pa a especi ica un c´odigo no lineal, debemos nume a odas las palab as-
c´odigo. Podemos especi ica un c´odigo lineal de pa ´ame os [n, k] simplemen e dando bases
del espacio ec o ial con kpalab as-c´odigo.
De inici´
on 12. Una ma iz de ama˜no k×ncuyas ilas o man una base de un c´odigo
lineal de pa ´ame os [n, k] se llama ma iz gene ado a del c´odigo.
3. Ven aja 3. Hay buenos p ocesos pa a codi ica y decodi ica un c´odigo lineal, es o se e ´a
m´as adelan e.
Aho a amos a e algunas des en ajas:
1. Des en aja 1. Los c´odigos q-a ios lineales no es ´an de inidos a menos que qsea una po encia
p ima. Sin emba go, hay c´odigos q-a ios, donde qno es una po encia p ima, que pueden
ob ene se de c´odigos lineales sob e un g an al abe o.
2. Des en aja 2. La es icci´on a c´odigos lineales pa ece una es icci´on a c´odigos m´as d´ebiles
y es a gene alidad. Sin emba go, los c´odigos que son ´op imos suelen se ecuen emen e
lineales.
22
3.1.1. Equi alencia de c´odigos lineales
La de inici´on de equi alencia dada an e io men e se modi ica pa a c´odigos lineales, usando
solo pe mu aciones del ipo p oduc o, cuando es as se ealizan con escala es no nulos. As´ı,
dos c´odigos lineales sob e GF(q) son equi alen es si uno puede se ob enido a pa i del o o
median e una combinaci´on de ope aciones de los siguien es ipos:
1. Pe mu aciones de las posiciones del c´odigo.
2. Mul iplicaci´on (po un escala dis in o de 0) de los s´ımbolos que apa ecen en una posici´on
ija.
Teo ema 12. Dos ma ices de ama˜no k×ngene an c´odigos lineales con pa ´ame os [n, k]
equi alen es sob e GF(q)si una de las dos ma ices puede ob ene se a pa i de la o a median e
una secuencia de ope aciones de los siguien es ipos:
1. Pe mu aci´on de ilas.
2. Mul iplicaci´on de una ila po un escala dis in o de ce o.
3. Adici´on del p oduc o de una ila po un escala a o a.
4. Pe mu aci´on de columnas.
5. Mul iplicaci´on de cualquie columna po un escala dis in o de 0.
Demos aci´on. Las ope aciones de ila (1,2,3) p ese an la independencia lineal de las ilas de
una ma iz gene ado a y simplemen e eemplazan una base po o a del mismo c´odigo. Po o a
pa e, las ope aciones del ipo (4,5) con ie en una ma iz gene ado a en o a que p oduce un
c´odigo equi alen e.
Teo ema 13. Sea Guna ma iz gene ado a de un c´odigo de pa ´ame os [n, k]. En onces, eali-
zando las ope aciones del Teo ema 12, se puede ans o ma Gen una ma iz en o ma es ´anda .
[Ik|A],
donde Ikes la ma iz iden idad de dimensi´on k×k, y Aes una ma iz de dimensi´on k×(n−k).
Demos aci´on. En una secuencia de ans o maciones de la ma iz G, deno amos po gi,j la
en ada n´ume o (i, j) de la ma iz y po 1, 2, . . . , kyc1, c2, . . . , cnlas ilas y las columnas,
espec i amen e, de es a ma iz.
A con inuaci´on amos a e un p oceso que cons a de 3 pasos. Es e p oceso se aplica pa a j=
1,2, ..., k la j-´esima aplicaci´on ans o ma la columna cjen su o ma deseada (con 1 en la j-´esima
posici´on y 0 en el es o), dejando sin cambios las p ime as j−1 columnas ya con enien emen e
23
ans o madas. Supongamos en onces que Gya ha sido ans o mada













1 0 · · · 0g1,j · · · g1n
0 1 · · · 0g2,j · · · g2n
.
.
..
.
.....
.
..
.
.....
.
.
0 0 · · · 0gj−1,j · · · gj−1,n
0 0 · · · 0gj,j · · · gj,n
.
.
..
.
.....
.
..
.
.....
.
.
0 0 · · · 0gk,j · · · gk,n













1. Paso 1. Si gj,j = 0 se pasa di ec amen e al paso 2. Si gj,j = 0 y si, adem´as, pa a algunas
i>jse cumple que gi,j = 0, en onces, se ealiza el in e cambio de jy i. Si se da el
caso de que gj,j = 0 y gi,j = 0 pa a odo i>j, en onces elegimos hcomo gj,h = 0 e
in e cambiamos cjych.
2. Paso 2. Aho a enemos gj,j = 0. Mul iplicamos jpo g−1
j,j
3. Finalmen e, si gj,j = 1. Pa a cada i= 1,2, . . . , k, con i=j, eemplazamos ipo i−gi,j · j.
La columna cjaho a iene la o ma deseada. Despu´es de aplica es os es pasos, la ma iz
gene ado a end ´a la o ma es ´anda .
3.2. Codi icando y decodi icando con un c´odigo lineal
3.2.1. Codi icando con un c´odigo lineal
Sea Cun c´odigo lineal de pa ´ame os [n, k] sob e GF(q) con Gma iz gene ado a. Con iene
qkpalab as-c´odigo y, po an o, pueden se usadas pa a comunica cualesquie a qkmensajes
dis in os. Iden i icamos esos mensajes con las qkk- uplas de V(k, q) y codi icamos un mensaje de
ipo ec o u=u1u2· · · uksimplemen e mul iplic´andolo po la pa e de echa po G. Suponiendo
que las ilas de Gson 1, 2, . . . , k, en onces
uG =
k
X
i=1
ui i.
Po an o, uG es una palab a-c´odigo de C, ya que es una combinaci´on lineal de las ilas de
la ma iz gene ado a. Se ha de ene en cuen a que la unci´on codi icado a u→uG mapea el
espacio ec o ial V(k, q) en un subespacio ec o ial de V(n, q) de dimensi´on k.
La egla de codi icaci´on es m´as sencilla si Ges ´a exp esada de o ma es ´anda . Suponemos que
G= [Ik|A], donde A= [ai,j ] es una ma iz de dimensi´on k×(n−k). En onces el mensaje del
ec o use codi ica de la siguien e mane a
x=uG =x1x2· · · xkxk+1 · · · xn,
24
donde xi=ui,1≤i≤k, son los d´ıgi os de los mensajes y
xk+i=
k
X
j=1
ajiuj,1≤i≤n−k.
son los d´ıgi os de chequeo. Es os ´ul imos ep esen an la edundancia que se ha a˜nadido al
mensaje pa a p o ege lo del uido.
3.2.2. Decodi icando con un c´odigo lineal
Suponemos que la palab a-c´odigo x=x1x2· · · xnse en ´ıa a a ´es de un canal y que al
ecep o le llega el ec o y=y1y2· · · yn. De inimos el ec o e o ecomo:
e=y−x=e1e2· · · en.
El decodi icado debe decidi a pa i de yqu´e palab a-c´odigo xha sido ansmi ida, es deci ,
qu´e ec o e o eha enido luga . Un ejemplo de esquema de decodi icaci´on, llamado de ecino
m´as ce cano pa a c´odigos lineales, ue c eado po Slepian en 1960 y u iliza el hecho de que un
c´odigo lineal es un subg upo del g upo adi i o V(n, q).
De inici´
on 13. Suponemos que Ces un c´odigo con pa ´ame os [n, k] sob e GF(q) y aes
cualquie ec o pe enecien e a V(n, q). En onces, el conjun o a+Cde inido po
a+C={a+x|x∈C}
es una clase del conjun o cocien e V(n, q)/C que llama emos clase de Ca pa i de aho a.
Lema 8. Suponemos que a+Ces una clase de Cy que b∈a+C. En onces,
b+C=a+C.
Demos aci´on. Sabiendo que b∈a+C, enemos que b=a+x, pa a alg´un x∈C. Aho a, si
b+y∈b+C, en onces
b+y= (a+x) + y=a+ (x+y)∈a+C.
Po an o, b+C⊆a+C. Po o o lado, si a+z∈a+C, en onces
a+z= (b−x) + z=b+ (z−x)∈b+C.
Po an o, a+C⊆b+C, y en onces b+C=a+C.
El siguien e eo ema es un caso pa icula del eo ema de Lag ange pa a subg upos.
Teo ema 14. Suponemos que Ces un c´odigo de pa ´ame os [n, k]sob e GF(q). En onces
1. Todo ec o de V(n, q)pe enece a alguna clase de C.
2. Toda clase con iene exac amen e qk ec o es.
3. Dos clases o son disjun as o coinciden o almen e, no pueden coincidi solo pa cialmen e.
En esumen, las clases de C cons i uyen una pa ici´on del espacio V(n, q).
25
Vemos aho a un ejemplo. Tomamos
G="1 0 1 1
0 1 0 1#,
y po el Teo ema 20, una ma iz de con ol de pa idad es:
H="1 0 1 0
1 1 0 1#.
En onces, los s´ınd omes de los l´ıde es de clases son
S(0000) = 00
S(1000) = 11
S(0100) = 01
S(0010) = 10.
La ma iz es ´anda se ´a:
l´ıde es de clase s´ınd omes
0000 1011 0101 1110 00
1000 0011 1101 0110 11
0100 1111 0001 1010 01
0010 1001 0111 1100 10.
Aho a el algo i mo de decodi icaci´on consis e: dado y, el ec o que se ecibe, calcula S(y) =
yHTy localiza S(y) en la columna de s´ınd omes de la ma iz. Localizamos yen la co espon-
dien e ila y la decodi icamos como la palab a-c´odigo en la pa e supe io de la columna que
con iene y. Po ejemplo, si se ecibe 1111, en onces S(1111) = 01 y, po an o, 1111 apa ece en
la e ce a ila de la ma iz.
Cuando p og amamos un o denado pa a hace una ma iz es ´anda decodi icado a, necesi amos
gua da solo dos columnas (los s´ınd omes y los l´ıde es de clase) en la memo ia del o denado .
Es a ma iz se llama abla de b´usqueda po s´ınd ome. La abla de b´usqueda po s´ınd ome de
el c´odigo an e io es:
s´ınd ome zl´ıde es de clase (z)
00 0000
11 1000
01 0100
10 0010.
El p oceso de decodi icaci´on es el siguien e:
Paso 1 Pa a un ec o ecibido ycalcula S(y) = yHT.
Paso 2 Sea z=S(y), y localizando a zen la p ime a columna de la abla de b´usqueda.
Paso 3 Decodi ica ycomo y− (z).
Po ejemplo, si y= 1111, en onces S(y) = 01 y lo decodi icamos como 1111 −0100 = 1011.
32

3.3.2. Decodi icaci´on incomple a
La decodi icaci´on incomple a es una combinaci´on de co ecci´on y de ecci´on de e o es, es a
´ul ima se usa cuando es p obable que la co ecci´on p opo cione la palab a-c´odigo inco ec a. Es
deci , si d(C) = 2 + 1 ´o 2 + 2, adop amos el siguien e esquema po el cual ga an izamos la
co ecci´on de e o es o menos en cualquie palab a-c´odigo, en algunos casos, se de ec an m´as
de e o es.
O ganizamos las clases de la ma iz es ´anda en o den c ecien e seg´un peso de los l´ıde es de
clases, y di idimos la ma iz en dos pa es: la supe io , que comp ende aquellas clases cuyos
l´ıde es ienen pesos meno es o iguales a y la in e io , que comp ende las clases es an es. Si el
ec o ecibido es ´a en la pa e supe io , lo decodi icamos como de cos umb e, si yes ´a en la
pa e in e io , sabemos que se han p oducido m´as de e o es y solici amos la e ansmisi´on.
Un esquema de decodi icaci´on incomple o es adecuado, especialmen e, pa a c´odigos con dis-
ancia m´ınima pa . Es o es as´ı po que, si d(C) = 2 + 2, en onces se pod ´an co egi has a
e o es y simul ´aneamen e de ec a + 1 e o es.
Cuando se lle a a cabo una decodi icaci´on incomple a median e una abla de consul a de s´ınd o-
mes, podemos p escindi de la ma iz es ´anda en el esquema de decodi icaci´on, y en la cons-
ucci´on de la abla. Es o se debe a que sabemos que los l´ıde es de clases es ´an en la pa e
supe io de la ma iz (son odos los ec o es con peso ≤ ), mien as que los de la mi ad in e io
no se usan en la decodi icaci´on. En de ini i a, solo almacenamos la pa e supe io de una abla
de b´usqueda de s´ınd omes.
A con inuaci´on amos a e un ejemplo.
Conside amos el c´odigo lineal con pa ´ame os [10,8] sob e GF(11) con la siguien e ma iz de
con ol de pa idad:
H="111111111 1
12345678910#.
Se ha elegido H, que es una ma iz que no es ´a en o ma es ´anda con la inalidad de ob ene
un buen algo i mo decodi icado . Sea Cun c´odigo 10-a io que se ob iene a pa i de un c´odigo
11-a io, eliminando las palab as-c´odigo que con ienen el d´ıgi o 10. Es deci , Ces el c´odigo de
10 d´ıgi os de n´ume os decimales x=x1x2· · · x10 cumpliendo las dos ecuaciones de con ol de
pa idad:
10
X
i=1
xi≡0 m´od 11 y
10
X
i=1
ixi≡0 m´od 11.
Median e el p incipio de inclusi´on-exclusi´on, se puede mos a que Ccon iene 82644629 palab as-
c´odigo pe o no amos a e la demos aci´on. Las palab as-c´odigo de Cpueden se enume adas
usando una ma iz gene ado a en o ma es ´anda . El p ime paso es pone Hen o ma es ´anda
median e ope aciones sob e las ilas. Llamamos 1y 2a la p ime a y segunda ila de la ma iz
33
espec i amen e.
H−→ ( 1→ 1+ 2)"2345678910 0
1 2 3 4 5 6 7 8 9 10#
−→ ( 1→(−1) 1) y ( 2→(−1) 2)"9 876543210
10987654321#
−→ ( 2→ 2−2 1)"9876543 2 10
34567891001#.
Usando el Teo ema 20 enemos que
G=














2 8
3 7
4 6
I85 5
6 4
7 3
8 2
9 1














,
y en onces C={(x1, x2, . . . , x8,2x1+3x2+· · ·+9x8,8x1+7x2+· · ·+x8)}, donde x1, x2, . . . , x8
oman alo es 0,1,2,. . . ,9 y se omi en las palab as que ienen el d´ıgi o 10 en cualquie a de los
dos ´ul imos luga es de las coo denadas.
Aho a desc ibimos un esquema de decodi icaci´on po s´ınd ome incomple o que co egi ´a cual-
quie e o ´unico y que simul ´aneamen e de ec a ´a cualquie e o doble que su ja de la ans-
posici´on de dos d´ıgi os de una palab a-c´odigo.
Suponemos que x= (x1, x2, . . . , x10) es la palab a-c´odigo ansmi ida y que y= (y1, y2, . . . , y10)
es el ec o ecibido. El s´ınd ome
(A, B) = yHT= 10
X
i=1
yi,
10
X
i=1
iyi!
se calcula (m´odulo 11).
Suponemos que ha ocu ido un ´unico e o , as´ı que pa a jykdis in as de 0 enemos,
(y1, y2, . . . , y10)=(x1, . . . , xj−1, xj+k, xj+1, . . . , x10).
En onces
A=
10
X
i=1
yi= 10
X
i=1
xi!+k≡ky
B=
10
X
i=1
iyi= 10
X
i=1
ixi!+jk ≡jk
ambas calculadas (m´odulo 11).
Po an o, la magni ud de e o k iene dada po Ay la posici´on de e o j iene dada po el
alo de B/A. En onces, el esquema de decodi icaci´on es como emos a con inuaci´on:
34
1. Si (A, B) = (0,0), en onces yes una palab a-c´odigo donde suponemos que no hay e o es.
2. Si A= 0 y B= 0, en onces suponemos que ha ocu ido un ´unico e o que se co ige
eliminando Ade la en ada n´ume o (B/A) de y.
3. Si A= 0 o B= 0, pe o no ambos, en onces se han de ec ado al menos dos e o es.
Es e caso siemp e su ge si se ansponen dos d´ıgi os de una palab a-c´odigo, pues en onces
A= 0 y B= 0.
Po ejemplo, suponemos que y= 0610271355. Calculamos que A= 8 y que B= 6. Po an o,
B/A = 6 ·8−1= 6 ·7 = 42 = 9, as´ı que el d´ıgi o n´ume o 9 debe se 5 −8 = −3 = 8.
3.4. El p oblema p incipal de la eo ´ıa de la codi icaci´on lineal
En la in oducci´on se habl´o del p oblema p incipal de la eo ´ıa de la codi icaci´on. Es e
p oblema consis ´ıa en encon a Aq(n, d), es deci , el mayo alo de Mpa a el cual exis e un
c´odigo q-a io de pa ´ame os (n, M, d). A con inuaci´on, se a a a a el mismo p oblema, pe o,
es ingi´endolo a c´odigos lineales.
Si qes una po encia p ima, deno amos po Bq(n, d) el mayo alo de Mpa a el cual exis e
un c´odigo lineal de pa ´ame os (n, M, d) sob e GF(q). Cla amen e, Bq(n, d) es siemp e una
po encia de qyBq(n, d)≤Aq(n, d). Po an o, nos e e imos al p oblema de encon a Bq(n, d)
como el p oblema p incipal de la eo ´ıa de la codi icaci´on lineal conocido como MLCT po sus
siglas en ingl´es.
Si omamos los alo es de qyd ijos, el p oblema se p esen a de la siguien e o ma:
Ve si´
on 1 del p oblema MLCT. Pa a una longi ud dada (n), encon a la mayo dimen-
si´on k al que exis a un c´odigo de pa ´ame os [n, k, d] sob e GF (q). En onces, pa a es a kse
iene que Bq(n, d) = qk.
La edundancia de un c´odigo de pa ´ame os [n, k, d] se de ine como n−k, es deci , el n´ume o
de s´ımbolos que iene una palab a-c´odigo. Aho a amos a e una e si´on al e na i a.
Ve si´
on 2 del p oblema MLCT. Pa a una edundancia dada ( ), encon a la longi ud
m´axima n al que exis a un c´odigo de pa ´ame os [n, n − , d] sob e GF(q).
Resol e la e si´on 1 pa a odos los alo es de nequi ale a esol e la e si´on 2 pa a odos
los alo es de . Es o se debe a que, en ambos casos, conocemos exac amen e los alo es de n
ykpa a los cuales exis e un c´odigo de pa ´ame os [n, k, d]. Es a equi alencia se pod ´a e en
un eo ema que a a emos m´as adelan e. Po o o lado, la e si´on 2 nos da una ap oximaci´on
m´as na u al que se e ´a en el p oximo eo ema, pe o pa a ello debemos da unas de iniciones.
35
De inici´
on 18. Un conjun o de pa ´ame os (n, s) en V( , q) es un conjun o de n ec o es pe -
enecien es a V( , q) con la p opiedad de que cualquie subconjun o selemen os son linealmen e
independien es.
Se deno a po m´axs( , q) el mayo alo de npa a el cual exis e un conjun o de pa ´ame os
(n, s) en V( , q). Un conjun o de pa ´ame os (n, s) en V( , q) que cumple n= m´axs( , q) se llama
op imal. El p oblema del empaque ado pa a V( , q) es de e mina los alo es de m´axs( , q) y
los conjun os de pa ´ame os (n, s) op imales. Es e p oblema ue conside ado po Bose en 1947
con in e ´es es ad´ıs ico y en 1961 po su elaci´on con la eo ´ıa de c´odigos, que iene dada po el
Teo ema 22. Necesi amos aqu´ı un esul ado p e io.
Teo ema 21. Suponemos que Ces un c´odigo lineal de pa ´ame os [n, k]sob e GF(q)con ma iz
de pa idad H. En onces, la dis ancia m´ınima de Ces dsi, y solo si, cualesquie a d−1columnas
de Hson linealmen e independien es pe o algunas dcolumnas son linealmen e dependien es.
Demos aci´on. Po el Teo ema 11 sabemos que la m´ınima dis ancia de Ces igual al meno
peso de las palab as-c´odigo dis in as de 0. Sea x=x1x2· · · xnun ec o en V(n, q). En onces
x∈Csi, y solo si, xHT= 0, y es o es equi alen e a x1H1+x2H2+· · · +xnHn= 0, donde
H1, H2, . . . , Hn ep esen an las columnas de H.
En onces, pa a cada palab a-c´odigo xde peso d, hay un conjun o de dcolumnas linealmen e
dependien es que pe enecen a H. Po o o lado, si exis ie a un conjun o de d−1 columnas
linealmen e dependien es de Hllamadas Hi1, Hi2, . . . , Hid−1, en onces exis i ´ıan los escala es
xi1, xi2, . . . , xid−1, dis in os de 0 ales que
xi1Hi1+xi2Hi2+· · · +xid−1Hid−1= 0
Pe o en onces el ec o x= (0 · · · 0xi10· · · 0xi20· · · 0xid−10· · · 0), eniendo xijen la posici´on
ijpa a j= 1,2, . . . , d −1 y 0s en el es o, cumpli ´ıa que xHT= 0 y po an o, se ´ıa una
palab a-c´odigo de peso meno que d.
Teo ema 22. Exis e un c´odigo de pa ´ame os [n, n − , d]sob e GF(q)si, y solo si, exis e un
conjun o de pa ´ame os (n, d −1) en V( , q).
Demos aci´on. Supongamos que Ces un c´odigo de pa ´ame os [n, n − , d] sob e GF(q) con H
como ma iz de con ol de pa idad. En onces, po el Teo ema 21, las columnas de H o man un
conjun o de pa ´ame os (n, d−1) en V( , q). Po o o lado, suponemos que Kes un conjun o de
pa ´ame os (n, d −1) en V( , q). Si o mamos una ma iz Hde dimensi´on ×ncon los ec o es
de Kcomo sus columnas, en onces, de nue o po el Teo ema 21, Hes la ma iz de con ol de
pa idad de un c´odigo de pa ´ame os [n, n − ] cuya dis ancia m´ınima es, al menos, d.
Co ola io 4. Dados los alo es en e os posi i os q, d y , el mayo alo de npa a el cual exis e
un c´odigo de pa ´ame os [n, n − , d]sob e GF(q)es m´axd−1( , q).
A pa i del Co ola io 4 podemos deduci que, el p oblema p incipal de la eo ´ıa de la codi-
icaci´on lineal, conc e amen e la e si´on dos de es e, es equi alen e a encon a el m´axd−1( , q).
A con inuaci´on, amos a e que los alo es de Bq(n, d) ienen dados ambi´en po la soluci´on
de es e p oblema.
36
Teo ema 23. Suponemos que m´axd−1( −1, q)≤n≤m´axd−1( , q). En onces Bq(n, d) = qn− .
Demos aci´on. Como n≤m´axd−1( , q), exis e un c´odigo de pa ´ame os [n, n− , d] sob e GF(q)
y, po an o, Bq(n, d)≥qn− . Si Bq(n, d) ue a es ic amen e mayo que qn− , en onces exis i ´ıa
un c´odigo de pa ´ame os [n, n− +1, d], lo que implica que n≤m´axd−1( −1, q), con adiciendo
la hip´o esis.
Conside a emos a con inuaci´on el p oblema MLCT pa a alo es c ecien es de la dis ancia
m´ınima d. Los casos d= 1 y d= 2 se a an ´acilmen e. Po lo an o, conside a emos p ime o
el p oblema pa a d= 3 y lo esol e emos pa a odos los alo es de qy . Luego conside a emos
el caso d= 4, esol iendo el p oblema MLCT pa a q= 2 y dando los esul ados conocidos pa a
q > 2. Pa a los casos de dmayo que 4, se sabe muy poco en cuan o a los esul ados gene ales.
3.4.1. El p oblema MLCT pa a d= 3
An es de comenza a a a el p oblema se a a e una no a que nos se i ´a pa a comp ende
algunos concep os necesa ios.
No a 7. Cualquie ec o pe enecien e a V( , q) iene exac amen e q−1 m´ul iplos escala es
dis in os de 0, o mando el conjun o {λ |λ∈GF(q), λ = 0}. En e ec o, los q −1 ec o es
dis in os de 0 pe enecien es a V( , q) se pueden pa iciona en (q −1)/(q−1) conjun os que
llama emos clases, ales que dos ec o es son escala es m´ul iples uno espec o a o o si y solo
si es ´an en la misma clase. Si elegimos un ec o de cada clase ob enemos un conjun o de
(q −1)/(q−1) ec o es, donde ning´un pa de ellos son linealmen e dependien es. En onces,
po el Teo ema 21, omando esas columnas como las columnas de Hse p oduce una ma iz
de con ol de pa idad de un c´odigo de pa ´ame os [(q −1)/(q−1),(q −1)/(q−1) − , 3].
Es e c´odigo se llama c´odigo Hamming q-a io y se deno a po Ham( , q). Hay que eco da que
pa a de ini Ham( , q) se deben elegi di e en es ma ices de con ol de pa idad, pe o cualquie
ma iz puede se ob enida a pa i de o a po pe mu aci´on de las columnas y/o mul iplicaci´on
de es as po escala es que sean dis in os de 0. Po an o, los c´odigos de Hamming son c´odigos
lineales que es ´an de inidos de mane a ´unica po sus pa ´ame os.
Teo ema 24. Dada una edundancia , la m´axima longi ud nde un c´odigo de pa ´ame os
[n, n − , 3] sob e GF(q)es (q −1)/(q−1). Es deci , m´ax2( , q)=(q −1)/(q−1).
Demos aci´on. Po el Co ola io 4, el alo de nes necesa iamen e m´ax2( , q), el mayo alo
de un conjun o (n, 2) en V( , q). Aho a un conjun o Sde ec o es en V( , q) es un conjun o de
pa ´ame os (n, 2) si, y solo si, ning´un ec o de Ses un m´ul iplo escala de cualquie ec o de
S. Como se puede e en la No a 7, los q −1 ec o es dis in os de 0 que pe enecen a V( , q)
se pa icionan en (q −1)/(q−1) clases, cada clase con iene q−1 ec o es cuyos escala es son
m´ul iplos del es o. En onces, el conjun o m´as g ande con pa ´ame os (n, 2) es un conjun o de
(q −1)/(q−1) ec o es, uno de cada una de esas clases.
37

Los c´odigos op imales de pa ´ame os [n, n − , 3] con n= (q −1)/(q−1) son c´odigos
Ham( , q), de inidos en la No a 7. La soluci´on al p oblema MLCT, conc e amen e a la e si´on
1, se consigue a pa i de los Teo emas 23 y 24 y la mos amos en el siguien e eo ema.
Teo ema 25. Bq(n, 3) = qn− , donde es el ´unico en e o que cumple (q −1−1)/(q−1) < n ≤
(q −1)/(q−1).
No a 8.
1. Es ´acil exp esa Bq(n, 3) como una unci´on expl´ıci a de qyn. Po el Teo ema 24, exis e
un c´odigo de pa ´ame os [n, n − , 3] sob e GF(q) si y s´olo si n≤(q )/(q−1). A su ez,
es o ´ul imo ocu e si, y s´olo si, ≥logq{n(q−1) + 1}, lo que equi ale a que n− ≤
n−logq{n(q−1) + 1}. Po an o, se cumple que Bq(n, 3) = q⌊n−logq{n(q−1)+1}⌋.
2. Pa a cons ui un c´odigo lineal de pa ´ame os (n, M, 3) con M=Bq(n, 3), se debe encon-
a el meno en e o al que n≤(q −1)/(q−1). Se esc ibe como una ma iz de con ol
de pa idad, con n ec o es columna de V( , q) ales que ninguna columna es m´ul iple de
o a. Esa ma iz de con ol de pa idad siemp e puede ob ene se bo ando columnas de la
ma iz de con ol de pa idad de un c´odigo Hamming (Ham( , q)). Po an o, los mejo es
c´odigos lineales co ec o es de un solo e o con una longi ud p e ijada son o bien c´odigos
Hamming o c´odigos aco ados de Hamming.
An es de e el caso d= 4, es impo an e obse a que un conjun o de pa ´ame os (n, s)
se puede e como un conjun o de pun os en el espacio p oyec i o asociado PG( −1, q) que
emos a con inuaci´on.
De inici´
on 19. Dado el espacio ec o ial V( , q) = {(a1, a2, . . . , a )|ai∈GF(q)}, le asociamos
una es uc u a combina o ia P G( −1, q) que es ´a o mada po pun os y l´ıneas que se de inen
de la siguien e mane a.
Los pun os de P G( −1, q) son los espacios ec o iales unidimensionales de V( , q). Las l´ıneas
de PG( −1, q) son espacios ec o iales bidimensionales de V( , q). El pun o Ppe enece a la
l´ınea Lsi, y solo si, Pes un subespacio de L.PG( −1, q) ecibe el nomb e de espacio p oyec i o
de dimensi´on −1 sob e GF(q). Cada pun o Pde PG( −1, q), como subespacio de V( , q) de
dimensi´on 1, se gene a po un ´unico ec o dis in o de 0. En onces, si a= (a1, a2, . . . , a )∈P,
se cumple que
P={λa|λ∈GF(q)}.
En la p ´ac ica, iden i icamos el pun o Pcon cualquie ec o dis in o de 0 que lo con enga.
Dicho de o a o ma, los pun os de PG( −1, q) son los ec o es dis in os de 0 de V( , q) con la
egla de que si a= (a1, a2, . . . , a ) y b= (b1, b2, . . . , b ) son dos de esos ec o es, en onces
a=ben PG( −1, q) si y solo si a=λb en V( , q)
pa a alg´un λdis in o de 0.
Aho a amos a e algunas p opiedades elemen ales de PG( −1, q).
Lema 12. En PG( −1, q)se cumplen las siguien es a i maciones.
38
1. Su n´ume o de pun os es (q −1)/(q−1).
2. Dados dos pun os cualesquie a, hay una ´unica ec a que los con iene.
3. Cada ec a con iene exac amen e q+ 1 pun os.
4. Cada pun o apa ece en (q −1−1)/(q−1) ec as.
Demos aci´on.
1. Como cada uno de los q −1 ec o es dis in os de 0 de V( , q) iene q−1 escala es dis in os
de 0, el n´ume o de pun os de P G( −1, q) es (q −1)/(q−1).
2. Si aybson dis in os pun os de PG( −1, q), en onces la ´unica l´ınea que pasa po ellos
con iene los pun os λa +µb, donde λyµson escala es y al menos uno de ellos es dis in o
de 0.
3. En 2, hay q2−1 elecciones pa a el pa (λ, µ), pe o como es amos iden i icando m´ul iplos
po escala es, el n´ume o de pun os dis in os en la l´ınea es (q2−1)/(q−1) = q+ 1.
4. Sea el n´ume o de ec as en las cuales apa ece un pun o P. Sea Xel conjun o {(Q, L)|Q
es un pun o =P, L es una l´ınea que con iene a ambos PyQ}. Con amos los elemen os
de Xde dos mane as dis in as. Pa a cada una de las (q −1)/(q−1) −1 opciones de Q,
hay una ´unica l´ınea Lque con iene a Py a Q. En onces
|X|= (q −1)/(q−1) −1=(q −q)/(q−1).
Po o o lado, pa a cada una de las l´ıneas que pasan po P, hay (po el apa ado 3), q
pun os Q dis in os de P que se encuen an en L. As´ı,
|X|= q.
Ope ando con ambas exp esiones ob enemos que = (q −1−1)/(q−1).
De inici´
on 20. El espacio p oyec i o PG(2, q) se llama en ealidad plano p oyec i o sob e
GF(q). Po el Lema 12 se sabe que PG(2, q) es un dise˜no de pa ´ame os (q2+q+ 1, q + 1,1)
sim´e ico, po an o es un plano p oyec i o como se de ini´o en el apa ado 2.2.
No a 9.
1. Los pun os de PG( −1, q) pueden se e ique ados haciendo que la coo denada, dis in a
de 0, si uada m´as a la izquie da sea igual a 1.
2. Si q= 2, los pun os de P G( −1,2) ienen dados po los ec o es dis in os de 0 pe ene-
cien es a V( , 2).
De inici´
on 21. Un conjun o Kde npun os en PG( −1, q) es un conjun o de pa ´ame os
(n, s) si los ec o es que ep esen an los pun os de K o man un conjun o de pa ´ame os (n, s)
en el espacio ec o ial subyacen e V( , q).
No a 10.
39
1. Dos en ajas de abaja con PG( −1, q) son: p ime o, que se pueden usa algunos
a gumen os de con eo pa a ob ene co as supe io es de m´axs( , q) y, segundo, que muchos
conjun os de pa ´ame os (n, s) ´op imos esul an se con igu aciones geom´e icas na u ales.
2. Un conjun o de pa ´ame os (n, 2) en PG( −1, q) es simplemen e un conjun o de npun os
dis in os de PG( −1, q). As´ı que desc ibimos el c´odigo Hamming Ham( , q) como un
c´odigo con la ma iz de con ol de pa idad H, cuyas columnas son los di e en es pun os
de PG( −1, q). Dis in as ep esen aciones de esos pun os como ec o es da ´an como
esul ado di e en es c´odigos, que se ´an equi alen es en e si.
3.4.2. El p oblema MLCT pa a d=4
La longi ud m´axima de un c´odigo de pa ´ame os [n, n − , 4], pa a una dada, es igual al
alo de m´ax3( , q), que es la mayo medida de un conjun o de pa ´ame os (n, 3) en V( , q).
Un conjun o de pa ´ame os (n, 3) en el plano PG(2, q) se llama un n-a co, mien as que un
conjun o de pa ´ame os (n, 3) en PG( −1, q), pa a > 3, se llama n-go o. Como 3 pun os
de PG( −1, q) son linealmen e dependien es si y solo si son colineales, puede desc ibi se un
n-a co/n-go o como un conjun o de npun os, de los que ning´un conjun o de es son colineales.
El p oblema de de e mina los alo es de m´ax3( , q), ue p ime amen e conside ado po Bose
en 1942. Es o ue ´apidamen e esuel o pa a q= 2, pa a odo , y pa a ≤4, pa a odo q. Sin
emba go, a pesa de que ue un p oblema muy impo an e, se ha esuel o s´olo pa a los pa es
adicionales ( , q) = (4,3) y (5,3). Los alo es conocidos de m´ax3( , q) se pueden obse a en la
siguien e exp esi´on.
m´ax3( , 2) = 2 −1.
m´ax3(3, q) = (q+ 1,si qes impa ,
q+ 2,si qes pa .
m´ax3(4, q) = (q2+ 1,si qes impa ,
q2+ 2,si qes pa .
m´ax3(5,3) = 20.
m´ax3(6,3) = 56.
Aho a e emos algunas demos aciones.
40
La de e minaci´
on de m´ax3( , 2)
Aqu´ı a amos el p oblema de encon a c´odigos bina ios lineales op imales con d= 4. El
siguien e Teo ema mues a que debemos ob ene esos c´odigos a pa i de los c´odigos op imales
de m´ınima dis ancia 3 simplemen e a˜nadiendo un d´ıgi o de chequeo de la pa idad.
Teo ema 26. Suponemos que des impa . En onces exis e un c´odigo bina io de pa ´ame os
[n, k, d]si, y solo si, exis e un c´odigo bina io de pa ´ame os [n+ 1, k, d + 1].
Demos aci´on. La demos aci´on del Teo ema 3 es ´alida bajo la es icci´on de que los c´odigos
sean lineales. Es o se debe a que un c´odigo ex endido (es deci , el c´odigo ob enido de un d´ıgi o
de chequeo de la pa idad) es lineal.
Co ola io 5. Suponemos que des pa . En onces
1. B2(n, d)=B2(n−1, d −1).
2. m´axd−1( , 2) = m´axd−2( −1,2) + 1.
Demos aci´on.
1. Se ob iene inmedia amen e del Teo ema 26.
2. El hecho de que n≤m´axd−1( , 2), ocu e ´unicamen e si exis e un c´odigo bina io de
pa ´ame os [n, n− , d]. Es o ´ul imo sabemos que sucede si y s´olo si exis e un c´odigo bina io
de pa ´ame os [n−1, n − , d −1], y es e exis e si, y solo si, n−1≤m´axd−2( −1,2), que
es equi alen e a n≤m´axd−2( −1,2) + 1.
Co ola io 6. m´ax3( , 2) = 2 −1.
Demos aci´on. Po el Teo ema 24, m´ax2( , 2) = 2 −1. En onces m´ax3( , 2) = (2 −1−1) + 1 =
2 −1.
El c´odigo bina io op imal con d= 4 y edundancia es el c´odigo Hamming ex endido
Ham( −1,2). Como emos, la ma iz de con ol de pa idad de es e c´odigo es:
¯
H=





0
H.
.
.
0
1 1 · · · 1






,
donde Hes una ma iz de con ol de pa idad pa a Ham( −1,2), al que las columnas de Hson
jus amen e los pun os de PG( −2,2). Las columnas de ¯
H o man un 2 −1-go o en PG( −1,2).
¯
Hconsis e en los pun os de PG( −1,2) que no pe enecen al subespacio {(x1, . . . , x )|x = 0}.
Geom´e icamen e, se puede desc ibi como el complemen o de un hipe plano.
41
48

Bibliog a ´ıa
[1] Ande son, I. (1974). A i s cou se in combina o ial ma hema hics. Cla endon P ess. Ox o d.
[2] Ba lo i, A. (1955). Un es ensione del eo ema di Seg e-Kus aanheimo. Bolle ino dell’Unione
Ma ema ica I aliana 10, 498-506.
[3] Bose, Raj Chand a. (1947). Ma hema ical heo y o he symme ical ac o ial design. Sankh-
ya 8, 107-166.
[4] B uen, A. A. y Hi sch eld, J. W. P. (1978). Applica ion o line geome y o e ini e ields II.
The He mi ian su ace. Geome iae Dedica a. 7, 333-353.
[5] Co e , T. M. y Thomas, J. A. (1991). Elemen s o in o ma ion heo y. New Yo k: John
Wiley & Sons.
[6] Fen on, N. E. y V´amos, P. (1982). Ma oid in e p e a ion o maximal k-a cs in p ojec i e
spaces. Rend. Ma . 2, 573-580.
[7] Games, R. A. (1983). The packing p oblem o p ojec i e geome ies o e GF(3) wi h di-
mension g ea e han i e. Jou nal o Combina o ial Theo y 35, 126-144.
[8] Hall, M. (1967). Combina o ial heo y. Wiley-In e science.
[9] Helge , H. J. y S ina , R. D. (1973) Minimum-dis ance bounds o bina y linea codes.
IEEE T ansac ions on In o ma ion Theo y, ol. 19, 344-356.
[10] Hill, R. (1973). On he la ges size o cap in S5,3. A i Accad. Naz. Lincei Rend, 54, 378-384.
[11] Hill, Raymond. (1978). Caps and codes. Disc e e Ma hema ics, 22, 111-137.
[12] Hi sch eld, J. W. P. (1979). P ojec i e geome ies o e ini e ields. Ox o d Un e si y P ess.
[13] Hi sch eld, James. (1983). Maximum se s in ini e p ojec i e spaces. In Su eys in combi-
na o ics, Socie y Lec u e No e Se ies. Camb idge Uni e si y P ess, 55-76.
[14] Hu man, W. C. , Kim, J-L. y Sol´e, P. (2021). Concise Encyclopedia o Coding Theo y.
Chapman and Hall.
49
[15] Lidl, R. y Niede ei e , H. (1983). Fini e ields. Camb idge Uni e si y P ess.
[16] Lidl, R. y Pilz, G. (1997). Applied abs ac algeb a. Sp inge .
[17] Ling, S. y Xing, C. (2004). Coding Theo y: A i s cou se. 1s Edi ion. Camb idge Uni e si y
P ess.
[18] an Lin , J. H. (1982). In oduc ion o coding heo y. Sp inge -Ve lag.
[19] Mackenzie, C. y Sebe y, J. (1984). Maximal e na y codes and Plo kin’s bound. A s Com-
bina o ia, 17A, 251-270.
[20] MacWilliams, F.J. y Sloane, N.J.A. (1997). The heo y o e o -co ec ing codes(No h-
Holland Ma hema ical Lib a y, Volume 16). No h Holland Publishing.
[21] McEliece, R. y T uss, J. K. (1977). The heo y o in o ma ion and coding. Addison-Wesley.
[22] No ds om, A. W. y Robinson, J. P. (1967). An op imum non-linea code. In . Con ol, 11,
613-616.
[23] Pelleg ino, G. (1970). Sul massimo o dine delle calo e in S4,3. Ma ema iche (Ca ania), 25,
1-9.
[24] Plo kin, M. (1960). Bina y codes wi h speci ied minimum dis ance. IEEE T ansac ions on
In o ma ion Theo y, 6, 445-450.
[25] Q is , B. (1952). Some ema ks conce ning cu es o he second deg ee in a ini e plane.
Annales Academiae scien ia um Fennicae: Ma hema ica-Physica, no 134.
[26] Roman, S. (1992). Coding and in o ma ion heo y (G adua e Tex s in Ma hema ics GTM,
olume 134). Sp inge -Ve lag.
[27] Ro h, R. (2006). In oduc ion o coding heo y. Camb idge Uni e si y P ess.
[28] Seg e, B. (1954). Sulle o ali nei piani linea i ini i. Rend. dell´ı Acc. Nazionale dei Lincei,
17, 141-142.
[29] Shannon, C. E. (1948). A ma hema ical heo y o communica ion. Bell Sys em Technical
Jou nal, 27, 379-423 y 623-656.
[30] Slepian, D. (1960). Some u he heo y o g oup codes. Bell Sys em Technical Jou nal, 39,
1219-1252.
[31] Sloane, N. J. A. (1982). Recen bounds o codes, sphe e packings and ela ed p oblems
ob ained by linea p og aming and o he me hods. Con empo a y Ma hema ics, 9, 153-185.
[32] Tena A., J. G. y Munue a G., C. (1997). Codi icaci´on de la in o maci´on. Ediciones Uni e -
sidad de Valladolid.
50
[33] Tie ¨a ¨ainen, A. (1980). Bounds o bina y codes jus ou side he Plo kin ange. In o. Con-
ol, 47, 85-93.
[34] Ve hoe , T. (1985). An upda ed able o minimum-dis ance bounds o bina y linea codes.
IEEE T ansac ions on In o ma ion Theo y, 39, 662-677.
51