lunes, 2 de marzo de 2009

Sobre el software DSP

Capítulo IV (parte I)

Las aplicaciones DSP (digital signal processing) suelen ser programadas en los mismos lenguajes que cualquier otra tarea de ciencia e ingeniería, tales como: C, BASIC y ensamblador. El poder y la versatilidad de C hacen que sea el lenguaje elegido por científicos e informáticos y otros programadores profesionales. Por otro lado, la simplicidad de Basic lo hace ideal para los científicos e ingenieros que sólo de vez en cuando visitan el mundo de la programación. Independientemente de la lengua que se utilice, la mayoría de los problemas importantes de software DSP están enterrados muy por debajo en el ámbito de los unos y ceros. Estos incluye temas como: cuantos números son representados por patrones de bits, el error de redondeo en la aritmética del ordenador, la velocidad de cálculo de los diferentes tipos de procesadores, etc.

Las computadoras digitales son muy competentes almacenando y recordando los números; por desgracia, este proceso no está exento de errores. Por ejemplo, si le damos la instrucción a nuestro equipo de que guarde el número: 1,41421356. El equipo lo hará mejor que pueda, y almacenará el número más cercano que pueda representar: 1,41421354. En algunos casos este error es bastante insignificante, mientras que en otros casos, es desastroso. Como otro ejemplo, un clásico error de cálculo resulta de la adición de dos números con valores muy diferentes, por ejemplo, 1 y 0,00000001. Nos gustaría que la respuesta fuera 1,00000001, pero la respuesta del ordenador es 1. La comprensión de cómo las computadoras almacenan y manipulan los números te permite anticipar y corregir estos problemas antes de que tu programa escupa datos sin sentido.

Estos problemas se deben a que siempre un número fijo de bits son asignados para almacenar cada número, por lo general de 8, 16, 32 o 64. Por ejemplo, considera el caso de que se utilicen ocho bits para almacenar el valor de una variable. Debido a que hay 28 = 256 posibles patrones de bits, la variable sólo puede tomar 256 valores diferentes. Esta es una limitación fundamental de la situación, y no hay nada que se pueda hacer al respecto. La parte que podemos controlar es que valor declaramos que cada patrón de bit represente. En los casos más sencillos, los patrones de 256 bits puede representar los enteros de 0 a 255, 1 a 256, -127 a 128, etc. En un esquema más inusual, los patrones de 256 bits pueden representar 256 números exponencialmente relacionados: 1, 10, 100, 1000, …, 10254, 10255. Cada acceso a los datos debe comprender el valor que cada patrón de bit representa. Esto generalmente es proporcionado por un algoritmo o fórmula para la conversión entre el valor representado y el correspondiente patrón de bits, y viceversa.

Aunque hay muchos esquemas de codificación posibles, sólo dos se han convertido en formatos comunes, el punto fijo (también llamados números enteros) y punto flotante (también llamados números reales).

Punto fijo (enteros)

La representación de punto fijo se utiliza para almacenar números enteros, tanto positivos como negativos: …-3, -2, -1, 0, 1, 2, 3, …. Los programas de alto nivel, tales como C y BASIC, por regla general destinan 16 bits para almacenar cada entero. En el caso más simple, los 216 = 65,536 posibles patrones de bits son asignados a los números de 0 a 65535. A esto se le llama formato entero sin signo (unsigned integer). La conversión entre el patrón de bit y el número que se representa no es más que el cambio entre la base 2 (binario) y la base 10 (decimal). La desventaja del entero sin signo es que los números negativos no pueden ser representados.

El formato Offset binario es similar al entero sin signo, excepto en que los valores decimales se desplazan para permitir los números negativos. De esta manera, una representación de 16 bits utiliza 32,767 como compensación, lo que resulta en un rango entre -32,767 y 32,768. El offset binario no es un formato normalizado, y encontrarás otras compensaciones utilizadas, por ejemplo, 32,768. El uso más importante del offset en binario es en la conversión analógica a digital y en su inversa digital a analógica. Por ejemplo, la gama de voltajes de entrada de -5v a 5v puede ser asignada a los números digitales de 0 a 4095, para una conversión de 12 bits.

Signo y magnitud es otra forma muy sencilla de representar números negativos. El bit del extremo izquierdo se denomina bit de signo, y es un cero para números positivos, y un uno para los números negativos. Los otros bits son un estándar de representación binaria del valor absoluto del número. Esto se traduce en un patrón de bit que derrocha, ya que existen dos representaciones para el cero, 0000 (cero positivo) y 1000 (cero negativo). Este esquema de codificación, en números de 16 bits, tiene un rango de -32767 a 32767.

Estas tres primeras representaciones son conceptualmente simples, pero difíciles de implementar en hardware. Recuerda que cuando A = B + C se introduce en un programa de ordenador, algún ingeniero de hardware tiene que buscar la manera de hacer que el patrón de bits que representa a B, se combine con el patrón de bits que representa a C, para formar el patrón de bits que represente a A.

El complemento a dos (Two's complement) es el formato más querido por los ingenieros de hardware, y es la manera cómo los enteros suelen estar representados en las computadoras. Su funcionamiento es análogo al odómetro (aparato que mide la distancia recorrida por un coche) en un automóvil nuevo. Si se conduce hacia adelante cambia: 00000, 00001, 00002, 00003, y así sucesivamente. Cuando marcha hacia atrás, el odómetro cambia: 00000, 99999, 99998, 99997, etc.

Usando 16 bits, complemento a dos puede representar números de -32,768 a 32,767. La mayoría de los bits de la izquierda son 0 si el número es positivo o cero, y 1 si el número es negativo. En consecuencia, la mayoría de los bits de la izquierda, se llama el bit de signo, al igual que en la representación signo y magnitud. La conversión entre decimal y el complemento a dos es sencilla para los números positivos, una simple conversión de binario a decimal. Para los números negativos, el siguiente algoritmo se utiliza a menudo: (1) tomar el valor absoluto del número decimal, (2) convertirlo a binario, (3) complementar todos los bits (unos se hacen ceros y ceros se hacen unos), ( 4) sumar 1 al número binario. Por ejemplo: -5 →5 →0101→ 1010 → 1011. El formato complemento a dos es difícil para los seres humanos, pero fácil para la electrónica digital.

Punto flotante (números reales)

El esquema de codificación de los números de punto flotante es más complicado que el esquema de punto fijo. La idea básica es la misma que la utilizada en la notación científica, donde una mantisa se multiplica por diez elevada a algún exponente. Por ejemplo, 5,4321 × 106, donde 5.4321 es la mantisa y 6 es el exponente. La notación científica es excepcional para representar cantidades muy grandes o muy pequeñas . Por ejemplo: 1.2 × 1050, es el número de átomos en la tierra, o 2.6 × 10-23, la distancia que una tortuga rastrea en un segundo, en comparación con el diámetro de nuestra galaxia. Observe que los números representados en notación científica se normalizan de manera que exista un solo dígito distinto de cero a la izquierda de la coma decimal. Esto se logra ajustando el exponente según se necesite.

La representación de punto flotante es similar a la notación científica, con excepción de que todo se lleva a cabo en base dos, en lugar de en base diez. Si bien varios formatos similares se encuentran en uso, el más común es ANSI / IEEE Std. 754-1985. Esta norma define el formato de 32 bits para los números llamados de precisión única (single precision), así como los de 64 bits llamados de doble precisión. Como se muestra en el siguiente gráfico, Los 32 bits utilizados en la precisión doble se dividen en tres grupos diferentes: los bits de 0 a 22 forman la mantisa, los bits de 23 a 30 forman el exponente, y el bit 31 es el bit de signo. Estos bits forman el número de punto flotante, v, por la siguiente relación:


El término: (-1)S, simplemente significa que el bit de signo, S, es 0 para un número positivo y 1 para un número negativo. La variable, E, es el número entre 0 y 255 representado por los ocho bits del exponente. Restando 127 de este número permite al exponente correr de 2 elevado a-127 a 2 elevadoa a128. En otras palabras, el exponente se almacena en binario compensado (offset) con una compensación de 127.

La mantisa, M , es formada desde los 23 bits como una fracción binaria. Por ejemplo, la fracción decimal: 2,783, se interpreta: 2+ 7 / 10+ 8 / 100+ 3 / 1000. La fracción binaria: 1,0101, significa: 1+ 0 / 2+ 1 / 4+ 0 / 8+1 / 16. Los números de punto flotante son normalizados de la misma manera que en la notación científica, es decir, sólo hay un dígito distinto de cero a la izquierda de la coma decimal (llamado punto binario en base 2).





Dado que el único número distinto de cero que existe en base de dos es 1, el dígito principal en la mantisa siempre será un 1, y, por tanto, no necesita ser almacenado. La eliminación de esta redundancia permite disponer al número de un adicional bit de precisión. Los 23 bits almacenados, a la que se refiere la notación: m 22 , m 21 ,...,m 0 , forma mantisa de acuerdo a:



En otras palabras, M = 1+ m 22 2 -1 + m 21 2 -2 + m 20 2 -3 … Si los bits de 0 a 22 son todos ceros, M toma el valor de uno. Si los bits de 0 y 22 son todos unos, M está sólo un pelo por debajo de dos, es decir, 2 -2 -23 .

Usando este esquema de codificación, el número mas grande que puede ser representado es: ±(2-2 -23 ) × 2 128 = ± 6.8 × 10 38 . Por lo tanto el número más pequeño que puede ser representado es: ±1.0 × 2 -127 = ± 5.9 × 10 -39 .

El estándar IEEE reduce este rango ligeramente para liberar un patrón de bits y que se les pueda asignar un significado especial. En particular, el más grande y el más pequeño de los números permitidos en el estándar son ± 3.4 × 10 38 y ± 1.2 × 10 -38 , respectivamente. Este patrón de bits liberado permite tres clases especiales de números: (1) ± 0 se define como todos los bits de la mantisa y exponente siendo cero. (2) ± ∞ se define como todos los bits de la mantisa siendo cero, y todos los bits del exponente siendo uno. (3) Un grupo de números muy pequeños sin normalizar entre ± 1.2 × 10 -38 y ± 1.4 × 10 -45 . Estos son los más bajos números de precisión obtenida mediante la eliminación de la exigencia de que el dígito líder en la mantisa sea uno. Además de estas tres clases especiales, hay patrones de bits a los que no se les asigna un significado, comúnmente conocidos como NANs (No Un Número).

El estándar IEEE para doble precisión simplemente añade más bits a la mantisa y al exponente. De los 64 bits usados para almacenar un número de doble precisión, los bits de 0 a 51 son la mantisa, y los 52 a 62 bits son el exponente, y el bit 63 es el de signo. Al igual que antes, la mantisa es de entre uno y menos de dos, es decir, M = 1+ m51 2-1+ m50 2-2+ m49 2-3… Los 11 bits del exponente forman un número entre 0 y 2047, con una compensación de 1023, permitiendo exponentes del 2-1023 a 21024. El más grande y el más pequeño de los números permitidos son ± 1.8 × 10308 × ± 2.2 × 10-308, respectivamente. ¡Estos son números increíblemente grandes y pequeños! Es muy raro encontrar una aplicación donde la precisión simple no sea adecuada. Probablemente nunca encuentres un caso en que la doble precisión límite lo que quieres lograr.


Texto basado en: "The Scientist and Engineer's Guide to Digital Signal Processing"
Steve Smith

No hay comentarios:

Publicar un comentario