Autor Tema: Ráfagas en códigos cíclicos

0 Usuarios y 1 Visitante están viendo este tema.

01 Abril, 2022, 09:24 pm
Leído 566 veces

mg

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 530
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Estoy atascado en el siguiente ejercicio.

Decimos que un vector \( x\in\mathbb{F}_q^n \) es una rafaga si todas sus coordenadas no nulas son consecutivas. Las ráfagas son particularmente interesantes cuando representan errores en códigos binarios. Probar que un código cíclico \( C\subset{}\mathbb{F}_2^n \) de dimensión k no contiene ninguna ráfaga de peso \( l\leq{}n−k \).


Mi idea es plantear un reducción al absurdo pero no atino a por donde puedo avanzar. Lo que si que esta claro que si supongo que existe tal ráfaga entonces esta es de la forma \( (1,...,1,0,....,0) \), con \( l \) unos y \( n-l \) ceros porque el código es cíclico y estamos en \( \mathbb{F}_2 \).

Una ayuda no me vendría mal, gracias.

Un saludo.


CORRREGIDO: el número de unos y de ceros

02 Abril, 2022, 12:46 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 56,141
  • País: es
  • Karma: +0/-0
Hola

Decimos que un vector \( x\in\mathbb{F}_q^n \) es una rafaga si todas sus coordenadas no nulas son consecutivas. Las ráfagas son particularmente interesantes cuando representan errores en códigos binarios. Probar que un código cíclico \( C\subset{}\mathbb{F}_2^n \) de dimensión k no contiene ninguna ráfaga de peso \( l\leq{}n−k \).


Mi idea es plantear un reducción al absurdo pero no atino a por donde puedo avanzar. Lo que si que esta claro que si supongo que existe tal ráfaga entonces esta es de la forma \( (1,...,1,0,....,0) \), con \( n-l \) unos y \( l \) ceros porque el código es cíclico y estamos en \( \mathbb{F}_2 \).

 No se si estoy confundido con lo que significa cada cosa. ¡Creo que si!  :D

 ¿El peso no es el número de unos? ¿una ráfaga de peso \( l \) no sería entonces con \( l \) unos?.

 ¿Un código de dimensión \( k \) no es un subespacio vectorial de dimensión \( k \) de \( F_2^n \)? ¿No contienen entonces siempre una ráfaga de peso cero (al vector cero)?.

 Saludos.

02 Abril, 2022, 01:10 pm
Respuesta #2

mg

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 530
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
 
Hola

Decimos que un vector \( x\in\mathbb{F}_q^n \) es una rafaga si todas sus coordenadas no nulas son consecutivas. Las ráfagas son particularmente interesantes cuando representan errores en códigos binarios. Probar que un código cíclico \( C\subset{}\mathbb{F}_2^n \) de dimensión k no contiene ninguna ráfaga de peso \( l\leq{}n−k \).


Mi idea es plantear un reducción al absurdo pero no atino a por donde puedo avanzar. Lo que si que esta claro que si supongo que existe tal ráfaga entonces esta es de la forma \( (1,...,1,0,....,0) \), con \( n-l \) unos y \( l \) ceros porque el código es cíclico y estamos en \( \mathbb{F}_2 \).

 No se si estoy confundido con lo que significa cada cosa. ¡Creo que si!  :D

 ¿El peso no es el número de unos?
El peso es el número de coordenadas distintas de cero, por tanto en \( \mathbb{F}_2 \) es el número de unos, pero no en general.

Citar
¿una ráfaga de peso \( l \) no sería entonces con \( l \) unos?.
En este código cíclico sí, por lo dicho anteriormente, y además los unos han de ser consecutivos. (sea \( x=(x_0,...,x_{n-1}) \) que pertenece al código también consideramos que \( x_{n-1} \) y \( x_0 \) son consecutivas)

Citar
¿Un código de dimensión \( k \) no es un subespacio vectorial de dimensión \( k \) de \( F_2^n \)?¿No contienen entonces siempre una ráfaga de peso cero (al vector cero)?.

 Saludos.

Respecto a la primera pregunta sí cuando el código es lineal, como es nuestro caso (cíclico es más que lineal), pero no en general. Y a la segunda sí, precisamente porque es subespacio vectorial.

02 Abril, 2022, 01:12 pm
Respuesta #3

mg

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 530
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Por cierto, corrijo el mensaje original por la observación de Luis.

02 Abril, 2022, 08:51 pm
Respuesta #4

mg

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 530
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Ya tengo la respuesta al ejercicio, muchas gracias. Resulta que el espacio generado por las ráfagas cicladas tendría una dimensión mayor que el propio código por tanto no pueden existir tales ráfagas.

03 Abril, 2022, 08:57 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 56,141
  • País: es
  • Karma: +0/-0
Hola

Ya tengo la respuesta al ejercicio, muchas gracias. Resulta que el espacio generado por las ráfagas cicladas tendría una dimensión mayor que el propio código por tanto no pueden existir tales ráfagas.

Pero sigo si verlo claro. ¿Estás seguro de que las definiciones y el teorema a probar es tal y como lo has puesto?.

¿El vector \( (1,0,0,0) \) no es una ráfaga de peso \( l=1 \)?. Y está contenida en cualquier subespacio de dimensión \( 1 \) en \( F_2^4 \). Eso contradice:

Probar que un código cíclico \( C\subset{}\mathbb{F}_2^n \) de dimensión k no contiene ninguna ráfaga de peso \( l\leq{}n−k \).

Sospecho que no entiendo bien alguna definición, pero no estoy seguro de cuál.

Saludos.

03 Abril, 2022, 12:31 pm
Respuesta #6

mg

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 530
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Pero ojo, para un código cíclico debe verificarse que es un subespacio vectorial de dimensión k, y además que si \( x\in{}C \), y \( x=(x_0,...,x_{n-1}) \) entonces \( (x_{n-1},x_0,x_1,...,x_{n-2})\in{}C \). Esa es la condición de que sea cíclico. En el ejemplo que has puesto tu código sería todo \( F^4_2 \) porque tendrías que todos los vectores canónicos pertenecen a tu código y además como el código es lineal, las combinaciones lineales de ellos también serían parte de código.

La demostración del ejercicio es la siguiente. Suponemos que tenemos un código en las condiciones del enunciado y por reducción al absurdo supongamos que existe una ráfaga de peso l. Entonces tal ráfaga podríamos escribirla como \( (1,...,1,0,..,0) \) con \( l \) unos y \( n-l \) ceros. Por hipótesis el código es cíclico y por tanto \( (0,1,...(\,l \,veces),1,0,...,0)\in{}C \) y así sucesivamente hasta el vector \( (0,...,0,1,...,1) \). Ahora bien, todos estos vectores pertenecen al código y además son linealmente independientes luego generan un subespacio vectorial contenido en el código de dimensión el número de vectores, esto es \( n-l+1 \). Como por hipótesis \( l\leq{}n-k\Longrightarrow{}k\geq{}n-l+1\geq{}k+1 \), y ahí está la contradicción.

03 Abril, 2022, 11:08 pm
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 56,141
  • País: es
  • Karma: +0/-0
Hola

Pero ojo, para un código cíclico debe verificarse que es un subespacio vectorial de dimensión k, y además que si \( x\in{}C \), y \( x=(x_0,...,x_{n-1}) \) entonces \( (x_{n-1},x_0,x_1,...,x_{n-2})\in{}C \).

Vale. No era consciente de esa parte de la definición Con eso todo claro.

Saluos.