Una implementación de CRC-16 para Basic Stamp 2 y Windows

Introducción

La motivación para escribir este artículo nace de mi reciente incursión en el campo del chequeo de errores usando "Cyclic Redundancy Check" (CRC), y mi primera experiencia fue darme cuenta de que, en efecto, tal chequeo es necesario.

Concretamente, mi proyecto consiste en un circuito basado en Basic Stamp 2, encargado de recibir ocho GPIs ("closures") y transmitir, via RS232, un bit-map de los mismos hacia un PC. En este último corre un programa escrito en Visual Basic 6.0, encargado de recepcionar la transmisión, decodificar el estado de los GPIs y reaccionar a ello correspondientemente.

Mi primer intento fue transmitir tan solo un byte (el bit-map), lo cual funcionó perfectamete mientras el prototipo y el PC estuvieron separados por un simple cable. Mas cuando el mismo byte tuvo que viajar a través de un sistema de transmisión serio, en este caso un salto satelital, comencé a tener problemas: no siempre lo recibido coincidía con lo transmitido. Obviamente, necesitaba un mecanismo para validar el dato en el extremo receptor.

A decir verdad, mecanismos de chequeo de errores existen muchos, comenzando por el simple chequeo de paridad implementado de facto en RS232. Mi elección de CRC-16, lo confiezo, estuvo basada, más que nada, en su popularidad; sistemas tan conocidos como USB hacen uso de él. En verdad, no quise desaprovechar la oportunidad de incursionar en este campo que, además de popular, me resultó interesante.

Hay muchos "sabores" de CRC y una teoría extensamente documentada en la que no quise sumergirme del todo. Mi interés se centró en entender el algoritmo hasta el punto de poder implementarlo con facilidad en cualquier sistema. De esto último trata este artículo.

La meta de CRC-16

Ya he dicho que "CRC" viene de "Cyclic Redundancy Check" (chequeo por redundancia cíclica), y lo de "cíclico" es importante.

La meta del algoritmo es obener una palabra de chequeo (checksum) que, en el caso de CRC-16, consta de 16 bits. El algoritmo se aplica al dato bajo validación, bit por bit. Al final de la corrida se obtiene un checksum que, independientemente de la extensión del dato, será siempre de 16 bits.

Digamos que nuestra transmisión consiste en paquetes de tamaño variable compuestos por un "header" (encabezamiento), un "byte count" (conteo de bytes) y n "data bytes" (bytes de dato), como se muestra en la figura 1.

Nuestro sistema transmitirá el paquete en ese orden, comenzando por el "header", y añadirá al final los dos bytes del checksum comenzando por el menos significativo, los cuales se tramsmitirán también como parte del mismo paquete.

El cálculo de este checksum se realiza previo a la transmisión, aplicando el algoritmo a todos los bytes precedentes, comenzando por HEADER y terminando por DATAn.

En el extremo receptor, se aislará el checksum recibido y se procederá a recalcularlo en base al el resto del paquete. Si el checksum calculado resulta igual al transmitido, el paquete se dará por válido.

Cómo funciona

La figura 2 es una representación gráfica del algoritmo CRC-16.

Nótese que el mismo puede implementarse fácilmente por harware utilizando compuertas XOR y un registro de desplazamiento de 16 bits. De ser así, el dato entraría seriadamente por la primera compuerta; una vez que todos los bits DATA hubieran entrado, el registro contendría el checksum en sí.

Nosotros no lo vamos a implementar por hardware, sino por software, pero es interesante notar que no hay restricción para el tamaño del dato, que este se procesa bit a bit, y que el proceso transcure de manera continua, es decir, cíclicamente.

Esto nos da algunas pistas importantes para el diseño de nuestra rutina de cálculo. Lo de "cíclico" se traduce en un "loop" (lazo). Lo de "bit a bit" se traduce en que cada iteración del loop procesará, no un byte del paquete, sino cada uno de los bits de cada byte; en otras palabras, tendremos que imaginar (y procesar) el paquete como un tren de bits y no como una secuencia de bytes.

En el diagrama de la Fig. 2, cada rectángulo representa un bit: el "registro" consta de 16 bits y la variable fb, de 1 bit. He colocado grandes números rojos indicando el órden en que deben realizarse las operaciones. Es muy importante respetar este orden.

Antes de comenzar, hay que iniciar todas las variables en cero, después de lo cual entramos en el loop.

Comenzamos por hacer un XOR entre el bit menos significativo del dato y el menos significativo del registro, depositando el resultado en fb. No es difícil construir el resto guiándonos por este diagrama. Al final de la corrida, es decir, cuando hayamos procesado todos los bits del dato, el registro contendrá el checksum, así calculado.

El siguiente "pseudo-código" nos aporta más detalles sobre la implementación del algoritmo por software sin distraernos con las especificades de un lenguaje concreto.

Implementación en P-Basic

La siguiente subrutina ha sido probada en un Basic Stamp 2 de Parallax. Aquí nos detendremos en algunos detalles linguísticos.

En el momento de llamar a esta subrutina, la variable wData ya contiene el dato a validar.

Para este proyecto concreto, el paquete consta de cuatro bytes: Un Header+ByteCount (el uno mapeado dentro del otro), un solo byte de datos y dos bytes de cheksum, de ahi que wData sea tan solo una palabra (16 bits). La variable crc es una palabra también.

Con el fin de poder manipular a ambas a nivel de bit, he declarado los "aliases" wDataBit y crc_b, respectivamente. Una vez declados, puedo tratarlos en el programa como arreglos de bits.

El resto del código se explica por sí mismo. Para aquellos no familiarizados con P-Basic, el símbolo ^ es el operador XOR y los sufijos BITn hacen retornar el bit n de la variable afectada; por ejemplo, crc.BIT14 retorna el bit 14 de crc.

Implementación en Visual Basic 6.0

He tenido que emplear algunas artimañas ya que Visual Basic no es un lenguaje orientado a "embedded applications" y carece, por tanto, de instrucciones para manipular bits individualmente. Seguramente, estas artimañas tendrán mayor interés para el lector que el código mismo, así que comenzaré por aquí.

Variables tipo Bit

No existe tal cosa como un "tipo Bit" en Visual Basic, pero nada me impide definir una variable de tipo byte y utilizar de ella tan solo el bit menos significativo, dejando los bits restantes en cero.

Nada me impide tampoco constuir un arreglo de bytes y "pensarlo" como un arreglo de bits, siempre que me limite a uilizar el bit menos significativos de cada elemento, dejando el resto en cero.

Por supesto, esto supone un desperdicio de memoria, pero en un PC eso no es gran problema.

Desplazamiento de Bits (Shift)

Desplazar un número binario una vez hacia la izquierda es equivalente a multiplicarlo por 2. Desplazarlo una vez a la derecha es equivalente a dividirlo entre 2. Siendo así, puedo conseguir el desplazamiento de un "registro" (variable), de esta manera:

Nótese el uso de la función Int(), la cual retorna el resultado truncado, que es justamente lo que se quería.

Aislar un Bit

Para aislar bits, usamos "máscaras" y operaciones AND, según se ilustra en la figura 3.

Digamos, por ejemplo, que necesito aislar el segundo bit (B1) de una variable reg y copiarlo (como bit) a una variable b pensada como Bit. El siguiente listado ilustra cómo hacerlo.

Uso de arreglos para manipular una variable escalar a nivel de Bit

Las técnicas anteriores nos permiten manipular bits pero, sin dudas, resultan en un código engorroso y oscuro. Una solución más programática, especialmente si el procesamiento es complejo, consiste en declarar un arreglo de bytes "pensados" como bits.

Si el contenido procede de una variable escalar, habrá primero que vaciarlo en el arreglo; al final del procesamiento habrá que vaciarlo de vuelta a la variable escalar.

Listado completo

He aquí el código que en la vida real estoy utilizando para validar mis datos recibidos por el puerto serie del PC.

Se trata de una función cuyo único argumento es el dato a validar y que retorna el checksum calculado por ella, formateado este como una cadena de caracteres (string).

En este listado hay detalles que se salen un poco del tema, pero vale la pena explicarlos para que el código se pueda entender.

En primer lugar, ya habrá notado el lector que esta función toma y retorna strings. Esto me resulta cómodo por razones que no pueden verse en el listado por encontrarse en otras partes de mi programa. De cualquier manera, la idea de almacenar datos binarios en un string es bastante natural: a fin de cuentas, un string no es más que una secuencia de bytes y, dicho sea de paso, en mis strings, cada carácter constituye un byte del dato, no su representación ASCII sino el contenido binario puro, de ahi que haga uso de la funcion Asc() para leerlos.

En segundo lugar, esta función es un poco más genérica que la rutina que vimos en P-Basic, en el sentido de que está pensada para aquel y otros dispositivos similares, los cuales pueden transmitir hasta 4 bytes de datos, de ahi que la constante K_MAX_BYTES sea igual a 5 (cuatro bytes de dato más un header).

Por último, nótese que no es esta una función reusable sino una escrita para un proyecto concreto. Mi propósito al mostrarla solo ha sido el de ilustrar el concepto a través un código que ha sido probado.

Conclusión

Creo que lo más útil de este artículo está en la Fig. 2. Lo digo porque en la práctica me servió como guia para escribir las dos rutinas aquí mostradas y utilizadas en mi proyecto.

Si este esfuerzo ha servido al lector para ayudarlo a implementar CRC-16 en su propio proyecto, entonces habrá cumplido su propósito.

Download

Artículo en formato PDF.