Resumen

crc es una herramienta para experimentar con los códigos CRC. Dado un polinomio generador especificado como parámetro, crc puede utilizarse para mostrar el cálculo detallado del CRC para un mensaje específico, o para mostrar los códigos que se generan para un determinado tamaño de mensaje.

1. Instalación

Descargar el binario disponible en el siguiente enlace:

http://webdiis.unizar.es/~chus/docencia/rc/crc/bin/crc

o generarlo compilando el código fuente:

$ gcc -g -Wall -Wextra -O3 -march=native -fopt-info-vec-optimized crc.c  -o crc -lm
    

También está disponible un fichero Makefile para facilitar la compilación:

$ make

El código fuente y el fichero Makefile están disponibles en el siguiente enlace:

http://webdiis.unizar.es/~chus/docencia/rc/crc/src

crc se distribuye bajo la licencia GPLv3, y se ejecuta en un terminal Linux.

2. Uso de la herramienta crc

Para mostrar las opciones de ejecución:

$ ./crc -h
crc v1.0 (2-ene-2024)
    
uso: ./crc opciones
 -M, --message
     polinomio del mensaje, por ejemplo: 101010
 -m, --msize
     tamaño del mensaje
 -G, --generator
     polinomio generador, por ejemplo: 10101
 -H, --hamming
     calcula la distancia de Hamming del código para mensajes mayores de 14 bits
 -v, --version
     Muestra versión y finaliza
 -h, --help
     Muestra el uso del programa

2.1. Cálculo detallado de CRC

El siguiente ejemplo muestra el cálculo detallado del crc para un mensaje y un polinomio generador especificados como parámetros:

$ ./crc -M1101011011 -G10011
** crc v1.0 (2-ene-2024), arrancando ...
    
Mensaje:   M(x)=x^9+x^8+x^6+x^4+x^3+x+1, grado 9
Generador: G(x)=x^4+x+1, grado 4
    
11010110110000 | 10011 
                -------
10011
-----
/10011
 10011
 -----
 /00001
  00000
  -----
  /00010
   00000
   -----
   /00101
    00000
    -----
    /01011
     00000
     -----
     /10110
      10011
      -----
      /01010
       00000
       -----
       /10100
        10011
        -----
        /01110
         00000
         -----
         /1110

         MSG|CRC
  1101011011|1110

2.2. Análisis de códigos CRC

El siguiente ejemplo muestra los códigos CRC para mensajes de 4 bits que se obtienen con el polinomio generador x^4+x+1. Asimismo, se analizan las características del polinomio generador.

./crc -m4 -G10011
** crc v1.0 (2-ene-2024), arrancando ...
    
Mensajes M de 4 bits
Generador: G(x)=x^4+x+1, grado 4
    
      MSG|CRC
(00) 0000|0000
(01) 0001|0011
(02) 0010|0110
(03) 0011|0101
(04) 0100|1100
(05) 0101|1111
(06) 0110|1010
(07) 0111|1001
(08) 1000|1011
(09) 1001|1000
(10) 1010|1101
(11) 1011|1110
(12) 1100|0111
(13) 1101|0100
(14) 1110|0001
(15) 1111|0010
    
Polinomio generador G(x)=x^4+x+1, grado 4
- Tiene dos términos? SI -> detecta errores de un bit
- Factor x+1? NO -> no detecta número impar de errores
- Factor x^2+1? NO -> detecta 2 errores separados por 1 bit
- Factor x^3+1? NO -> detecta 2 errores separados por 2 bits
- Factor x^4+1? NO -> detecta 2 errores separados por 3 bits
- Distancia entre 1 de mayor y menor peso: 4 -> detecta ráfagas de 4 errores
Buscando distancia de Hamming del código generado (120 códigos)...
OK          
Distancia de Hamming: 3 (1-0) -> detecta 2 errores
Tiempo de ejecución:   0.0s

Anexo A. Acerca de este documento

Para la edición de este documento se ha utilizado Markdown [2]. El fuente puede encontrarse en el siguiente enlace:

http://webdiis.unizar.es/~chus/docencia/rc/crc/crc.md

Las conversiones a formato pdf y HTML se han realizado con pandoc 3.1.12.1 [3]. La orden usada para generar el fichero pdf es:

$ pandoc -f markdown -V papersize=A4  \
  -V geometry:"top=2cm, bottom=1.5cm, left=2cm, right=2cm" \
   crc.md --pdf-engine=pdflatex -o crc.pdf

Y para generar salida en formato HTML:

$ pandoc  -f markdown  -s crc.md -o crc.html

Si se quiere utilizar una hoja de estilo:

$ pandoc  -f markdown  -s --css=css_template  crc.md -o crc.html 

Anexo B. Versiones

2-enero-2024: Versión inicial

16-octubre-2024: Actualizada versión de pandoc y orden para generar el fichero pdf.

19-noviembre-2024: Paso de subsecciones a secciones (## -> #). Reducción de indentado en código.

Referencias

[1] Licencia GPLv3. Fecha de consulta: 2-enero-2024. Disponible en http://www.gnu.org/licenses/gpl-3.0.html

[2] Daring Fireball. Markdown syntax. Fecha de consulta: 2-enero-2024. Disponible en https://daringfireball.net/projects/markdown/

[3] Pandoc: a universal document converter. Fecha de consulta: 2-enero-2024. Disponible en http://pandoc.org/