Telecomunicaciones

Cap´ ıtulo 7 C´digos Lineales o
7.1. Concepto de c´digo lineal. Matriz Generao dora
Sea A un cuerpo finito de q elementos. Si definimos en An las operaciones (x1 , ..., xn ) + (y1 , ..., yn ) = (x1 + y1 , .., xn + yn )

α(x1 , .., xn ) = (αx1 , .., αxn ) se obtiene un espacio vectorial sobre el cuerpo A de dimensi´n n. Un c´digo o o n n C ⊂ A se llama lineal si C es un subespacio vectorial de A. Si la dimensi´n o de C es k, se dir´ que C es un (n, k)-c´digo lineal o, si se quiere especificar a o la distancia m´ ınima d, un (n, k, d)-c´digo. El n´mero de elementos de un o u k (n, k)-c´digo es q . En efecto, basta recordar que, dada una base {v1 , .., vk } o de C, cada palabra-c´digo x de C puede expresarse en la forma o x = α1 v1 + ... + αk vk con αi ∈ K. Los escalares α1 , .., αk sonlas coordenadas de x en la base escogida. Sabemos que las coordenadas est´n un´ a ıvocamente determinadas 103

104

´ CAP´ ITULO 7. CODIGOS LINEALES

por x, una vez escogida la base. Por tanto, el n´mero de palabras-c´digo en u o C viene dado por Vq,k = q k (= variaciones con repetici´n de q elementos o n n tomados de k en k), mientras que A tiene q elementos. Ya vimos en el tema anterior queel hecho de ser C un c´digo de grupo o nos ofrece un c´lculo sencillo de la distancia m´ a ınima y un m´todo de decodie ficaci´n m´s eficiente por medio de la b´squeda de la palabra de peso m´ o a u ınimo en la clase lateral del mensaje recibido. Otra ventaja de los c´digos lineales o es la posibilidad de quedar especificados dando k palabras-c´digo linealmente o independientes. Una matriz k×n,formada por k filas que son palabras-c´digo o linealmente independientes, se dir´ que es una matriz generadora para el a c´digo C. o Recordamos que el alfabeto binario no es otra cosa que Z2 (clases de restos m´dulo 2). Ya hemos usado su estructura de grupo para la suma. Con o el producto dado por la tabla siguiente, Z2 es un cuerpo commutativo. · 0 1 0 0 0 1 0 1

Ejemplos 7.1.1. (a) (11111) es lamatriz generadora del c´digo binario o de repetici´n de longitud 5. o (b) El c´digo binario o C = {000, 011, 101, 110} tiene por matriz generadora G= 0 1 1 1 0 1

En este caso n = 3, k = 2 y Card(C) = 2k = 4. M´s adelelante, veremos que para estos c´digos existen m´todos de dea o e codificaci´n m´s adecuados que el de Slepian. o a

´ 7.2. EQUIVALENCIA DE CODIGOS LINEALES.

105

7.2.Equivalencia de C´digos Lineales. o

La definici´n usual de equivalencia de c´digos lineales es diferente de la o o dada para c´digos generales. S´lo se permiten permutaciones de s´ o o ımbolos en una posici´n determinada que consistan en la multiplicaci´n de los elementos o o de dicha posici´n por un escalar dado. o

Definici´n 7.2.1. Dos c´digos lineales se llaman equivalentes si uno puede o oobtenerse del otro por una combinaci´n de operaciones del tipo: o (a) Permutaci´n de posiciones, o (b) multiplicaci´n de todos los elementos que ocupan una posici´n dada por o o un escalar no nulo.

Teorema 7.2.2. Dos matrices k × n generan c´digos lineales equivalentes o si una de ellas se obtiene de la otra por una sucesi´n de operaciones de los o tipos siguientes: (F1) permutaci´n de filas, o (F2)multiplicaci´n de una fila por un escalar no nulo, o (F3) sumar a una fila un m´ltiplo escalar de otra, u (C1) permutaci´n de columnas, o (C2) multiplicar una columna por un escalar no nulo, ´ DEMOSTRACION: Las tres operaciones (F1), (F2) y (F3) preservan la independencia lineal de las filas de la matriz generadora de partida. Por tanto, s´lo implican o reemplazar una base por otra del mismo c´digo.Las operaciones (C1) y (C2) o convierten la matriz generadora en otra que genera un c´digo equivalente. o

106

´ CAP´ ITULO 7. CODIGOS LINEALES

Teorema 7.2.3. Sea G la matriz generadora de un (n, k)-c´digo lineal. Reao lizando operaciones del tipo anterior puede transformarse en una matriz de la forma (Ik |B), siendo B una matriz k × (n − k). ´ DEMOSTRACION: Durante las sucesivas...