²⁴⁰ views

Kernel: SageMath (latest)

Códigos lineales

En esta sesión vamos a ver las definiciones básicas de los códigos lineales. Recordemos que un código puede venir dado por una matriz generatriz (traspuesta en SAGE) o por una matriz de control.

Vamos a empezar por considerar un código sobre $\mathbb{F}_8$ .

In [4]:

# Códigos lineales sobre F_8
F.<a>=GF(8)

Podemos definir un código a partir de su matriz generatriz:

In [5]:

# definición de códigos lineales
M = matrix(F, [[1,1+a,0,0,0,a],[1,a^2+1,0,0,1,0], [0,0,1,1,0,1], [1,0,1,0,1,a^2]])
C = LinearCode(M)

Veamos algunos parámetros del código:

In [7]:

C.ambient_space().base_field().cardinality()

Out[7]:

8

In [4]:

Out[4]:

[6, 4] linear code over GF(8)

In [5]:

# Cosas que podemos calcular:
C.cardinality()

Out[5]:

4096

In [7]:

8^4

Out[7]:

4096

In [8]:

C.dimension()

Out[8]:

4

In [9]:

C.length()

Out[9]:

6

C es un subconjunto de $(\mathbb{F}_8)^6$ :

In [10]:

C.ambient_space()

Out[10]:

Vector space of dimension 6 over Finite Field in a of size 2^3

También podemos calcular una matriz de control a partir de $C$ .

In [11]:

C.parity_check_matrix()

Out[11]:

[          1           0           a a^2 + a + 1           1     a^2 + 1]
[          0           1       a + 1 a^2 + a + 1     a^2 + 1         a^2]

Como hemos visto en teoría, si $M$ es una matriz generatriz y $A$ es una matriz de control, necesariamente debe ser $AM=0.$ Recordemos que en SAGE, la matriz $M$ es la traspuesta de nuestra matriz $M$ :

In [12]:


C.parity_check_matrix() * C.generator_matrix().transpose()

Out[12]:

[0 0 0 0]
[0 0 0 0]

Tambiés es posible construir un código a partir de la matriz de control:

In [13]:

C2 = codes.LinearCodeFromCheckMatrix( C.parity_check_matrix() )

Out[13]:

/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/repl/ipython_kernel/__main__.py:1: DeprecationWarning: LinearCodeFromCheckMatrix is deprecated. Please use sage.coding.code_constructions.from_parity_check_matrix instead.
See http://trac.sagemath.org/21165 for details.
  from ipykernel.kernelapp import IPKernelApp

In [14]:

sage.coding.code_constructions.from_parity_check_matrix(C.parity_check_matrix())

Out[14]:

[6, 4] linear code over GF(8)

In [15]:

C == C2

Out[15]:

True

Veamos si es posile decodificar una palabra recibida (suponiendo que hemos cometido un sólo error):

In [16]:

z = vector(F, [1,1+a,0,0,0,0])
z in C

Out[16]:

False

In [17]:

# nota: C.decode() o C.decode_to_code(), dependiendo de la versión de SAGE
C.decode_to_code(z)

Out[17]:

(1, a + 1, 0, 0, 0, a)

SAGE puede usar los dos métodos de decodificación que hemos visto en clase: método del síndrome y método de distancia mínima. En general, ambos tienen que dar la misma decodificación:

In [18]:

# Métodos de decodificación
C.decoders_available()

Out[18]:

['Syndrome', 'NearestNeighbor']

In [19]:

C.decode_to_code(z, 'Syndrome')

Out[19]:

(1, a + 1, 0, 0, 0, a)

In [20]:

C.decode_to_code(z, 'NearestNeighbor')

Out[20]:

(1, a + 1, 0, 0, 0, a)

Pero si la palabra recibida tiene más de $\bigl\lfloor (d-1)/2\bigr\rfloor$ errores, pasan cosas malas:

In [21]:

C.minimum_distance()

Out[21]:

3

In [22]:

z = vector(F, [1,a,1,0,0,0]) # dos errores.

In [23]:

C.decode_to_code(z, 'Syndrome')

Out[23]:

(a, a + 1, 1, 0, 0, 0)

In [24]:

C.decode_to_code(z, 'NearestNeighbor')

Out[24]:

(1, a^2 + a, 1, 0, 0, a^2 + a)

In [25]:

C.random_element()

Out[25]:

(a^2, a^2 + a, a + 1, a^2 + a, 1, a^2 + 1)

La suma directa de subespacios es un subespacio, así que podemos sumar códigos:

In [3]:

C1=codes.random_linear_code(F,10,4)
C2=codes.random_linear_code(F,8,3)
D=C1.direct_sum(C2)
D

Out[3]:

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-3-ae49577c5322> in <module>()
----> 1 C1=codes.random_linear_code(F,Integer(10),Integer(4))
      2 C2=codes.random_linear_code(F,Integer(8),Integer(3))
      3 D=C1.direct_sum(C2)
      4 D
NameError: name 'F' is not defined

In [27]:

D.minimum_distance()

Out[27]:

4

In [1]:

Out[1]:

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-1-57b8d7453841> in <module>()
----> 1 D

NameError: name 'D' is not defined

Ejercicio 1 Construya una función parametros(C) que dado un código C devuelva todos los parámetros que hemos dado en clase: $(n,m,d)_q$ , $\delta(\mathcal{C})$ , $R(\mathcal{C})$ y redundancia.

Ejercicio 2 Consideramos el código lineal $\mathcal C$ sobre $\mathbb F_2$ , definido por la matriz generatriz (por columnas) $M= \left( \begin{array}{cc} 1&0 \\ 0&1 \\ 1&0 \\ 1&1 \\ 1&1 \\ 1&1 \\ 0&1 \\ 0&1 \\ \end{array} \right)$ Halle los parámetros del código y una matriz de control. Calcular todos los síndromes con líder de peso menor o igual que $2$ . Si recibimos la palabra $11011011$ y sabemos que se han cometido, a lo sumo, dos errores, ¿cuál es la palabra enviada y cuál el error cometido?

La idea de este ejercicio es aprender a calcular los síndromes. Para ello, puede empezar por construir la función peso(v) a idea de este ejercicio es aprender a calcular los síndromes. Para ello, puede empezar por construir la función peso(v) que calcule el peso del vector v. A continuación, se pueden seleccionar los vectores de peso menor o igual que dos con una comprensión de lista:

[v for v in C.ambient_space() if peso(v)<=2]

y calcular los posibles síndromes.

Ejercicio 3 Por el procedimiento de generar códigos aleatorios (muchos, al menos 100), ¿cuál es el mejor código lineal de longitud 8 y dimensión 5 sobre $\mathbb F_2$ que puede conseguir? (En términos de distancia mínima, tasa de transmisión, etc.) Compare con el mejor código conocido en www.codetables.de

(Usa la función codes.RandomLinearCode(8,3,F2)

In [ ]:

Códigos lineales

Product

Resources

Company