martes, 3 de marzo de 2009

Sobre el software DSP

Capítulo IV (parte II)

Prescisión numérca


Los errores asociados con la representación de números son muy similares a los errores de cuantificación durante la conversión analógico-digital. Tu quieres almacenar un rango continuo de valores, sin embargo, sólo puedes representar un número finito de niveles de cuantificación. Cada vez que un nuevo número es generado, después de un cálculo matemático, por ejemplo, debe ser redondeado al valor más cercano que pueda almacenarse en el formato que se está usando.

Como ejemplo, imagina que asignas 32 bits para almacenar un número. Puesto que hay exactamente 232 = 4,294,967,296 diferentes patrones de bits posibles, puedes representar exactamente 4,294,967,296 números diferentes. Algunos lenguajes de programación permiten una variable llamada de un entero largo (long integer), almacenado como 32 bits, punto fijo, complemento a dos.

Esto significa que los 4,294,967,296 patrones de bits posibles representan los enteros entre
-2,147,483,648 y 2,147,483,647. En comparación, la precisión de punto flotante simple extiende estos 4,294,967,296 patrones sobre una gama mucho más amplia: - 3.4 × 1038 a 3.4 × 1038

Con las variables de punto fijo, las diferencias entre los números adyacentes son siempre exactamente uno. En la notación de punto flotante, las diferencias entre los números adyacentes varían sobre el rango del número representado. Si queremos escoger al azar un número de punto flotante, la diferencia con el siguiente número es aproximadamente diez millones de veces más pequeña que el número en sí (para ser exactos, 2-24 a 2-23 veces el número). Este es un concepto clave de la notación de punto flotante: los números grandes tienen grandes diferencias entre ellos, mientras que los números pequeños tienen pequeñas diferencias. la siguiente Figura ilustra esto mostrando números consecutivos de punto flotante, y las diferencias que los separan.



El programa en el cuadro siguiente ilustra la forma como el error de redondeo (error de cuantificación en cálculos matemáticos) provoca problemas en DSP. Dentro del bucle del programa, dos números aleatorios se añaden a la variable de punto flotante X, y restados luego de nuevo. Idealmente, esto no debería hacer nada. En realidad, el error de redondeo de cada una de las operaciones aritméticas hace que el valor de X gradualmente se derive lejos de su valor inicial. Esta deriva puede tomar una de dos formas dependiendo de cómo los errores se unan. Si los errores de redondeo al azar son positivos y negativos, el valor de la variable aleatoriamente aumentará y disminuirá. Si los errores son predominantemente del mismo signo, el valor de la variable se alejará mucho más rápidamente y de manera uniforme.


La siguiente figura muestra cómo la variable, X, en este programa de ejemplo, deriva en valor. Una preocupación evidente es que el error aditivo es mucho peor que el error aleatorio. Esto es debido a que los errores aleatorios tienden a anularse entre sí, mientras que el aditivo se dedica a acumular errores. El error aditivo es aproximadamente igual al error de redondeo de una sola operación, multiplicado por el número total de las operaciones. En comparación, el error aleatorio sólo aumenta de forma proporcional a la raíz cuadrada del número de operaciones. Como muestra este ejemplo, el error aditivo puede ser cientos de veces peor que el error aleatorio para los algoritmos comunes de DSP.



Lamentablemente, es casi imposible de controlar o predecir cuál de los dos comportamientos de un determinado algoritmo nos cabe esperar. Por ejemplo, en el programa anterior se genera un error aditivo. Esto puede ser cambiado por un error aleatorio limitándonos a hacer una ligera modificación en los números que se van sumar y restar. En particular, la curva de error aleatorio generada por la definición: A =EXP (RND) y B = EXP (RND), en lugar de: A= RND y B =RND. En lugar de A y B siendo distribuidos aleatoriamente entre los números 0 y 1, se vuelven valores exponencialmente distribuidos entre 1 y 2.718. Incluso este pequeño cambio es suficiente para cambiar el modo de acumulación de errores.

Dado que no podemos controlar la forma en que los errores de redondeo se acumulan, ten en cuenta el peor escenario posible. Esperamos que cada número de precisión simple tendrá un error de aproximadamente una parte en cuarenta millones, multiplicado por el número de operaciones que hayan tenido lugar a través de él. Esto se basa en el supuesto de error aditivo, y el error medio de una sola operación es de una cuarta parte del nivel de cuantificación. A través del mismo análisis, cada número de doble precisión tiene un margen de error de aproximadamente una parte de cuarenta cuatrillones, multiplicada por el número de operaciones.

La tabla 4-2 ilustra un particularmente molesto problema de error de redondeo. Cada uno de los dos programas en esta tabla realiza la misma tarea: la impresión de 1001 números igualmente espaciados entre 0 y 10. La parte izquierda del programa utiliza la variable de punto flotante, X, como el índice de bucle. Cuando se encarga la ejecución del bucle, el ordenador comienza por establecer el índice de la variable a partir del valor del bucle (0 en este ejemplo). Al final de cada ciclo de bucle, el tamaño del paso (0,01 en el caso), se añadirá al índice. Una decisión se toma entonces: ¿hay más ciclos de bucles necesarios, o se completó el bucle? El bucle se termina cuando el computador considera que el valor del índice es mayor que el valor de terminación (en este ejemplo, 10,0). Como demuestra la salida generada, el error de redondeo en las adiciones causa que el valor de X acumule una discrepancia importante en el curso del bucle. De hecho, el error acumulado impide la ejecución del último ciclo de bucle. En lugar de que X tenga un valor de 10.0 en el último ciclo, el error hace que el último valor de X sea igual a 10.000133. Dado que X es mayor que el valor de terminación, el ordenador piensa que su labor está hecha, y termina el bucle prematuramente. Este último valor desaparecido es un error común en muchos programas de ordenador.


En comparación, el programa de la derecha utiliza una variable entera, I%, para controlar el bucle. La suma, resta, o multiplicación de dos enteros siempre produce otro entero. Esto significa que la notación de punto fijo no tiene absolutamente ningún error de redondeo con estas operaciones. Los enteros son ideales para el control de bucles, así como otras variables que se someten a múltiples operaciones matemáticas. ¡El último ciclo del bucle está garantizado que se ejecutará! A menos que tenga una fuerte motivación para hacer otra cosa, siempre use enteros para índices de bucle y contadores.

Si es necesario usar una variable de punto flotante como un índice de bucle, trata de usar fracciones, que sean una potencia de dos (como por ejemplo: 1/2, 1/4, 3/8, 27/16), en lugar de una potencia de diez (Por ejemplo: 0.1, 0.6, 1.4, 2.3, etc.) Por ejemplo, sería mejor utilizar: FOR X = 1 TO 10 STEP 0.125, en lugar de: FOR X = 1 a 10 STEP 0.1. Esto permite que el índice siempre de una representación binaria exacta, reduciendo así el error de redondeo. Por ejemplo, el número decimal: 1.125, se puede representar exactamente en la notación binaria: 1.001000000000000000000000 × 20. En comparación, el número decimal: 1.1, se halla entre dos números de punto flotante: 1.0999999046 y 1.1000000238 (en binario estos números son: 1,00011001100110011001100× 20 y 1,00011001100110011001101 × 20). Esto resulta en un error inherente cada vez que 1.1 se encuentra en un programa.

Un hecho útil para recordar: la precisión de punto flotante simple tiene una representación binaria exacta para cada número completo entre ± 16,8 millones (para ser exactos, ± 224). Por encima de este valor, las diferencias entre los niveles son más grandes que uno, causando que algunos conjuntos de valores número se puedan perder. Esto permite que los números de punto flotante en su conjunto (entre ± 16,8 millones), puedan ser sumados, restados y multiplicados, sin error de redondeo.

Velocidad de ejecución

La programación DSP puede ser vagamente dividida en tres niveles de complejidad: Ensamblador, Compilado, y de aplicación específica. Para entender la diferencia entre estas tres, tenemos que empezar con los conceptos básicos de la electrónica digital. Todos los microprocesadores se basan en torno a un conjunto de registros binarios internos, es decir, un grupo de flip-flops que pueden almacenar una serie de unos y ceros. Por ejemplo, en el microprocesador 8088, el núcleo del original IBM PC, cuenta con cuatro registros de propósito general, cada una de ellos de 16 bits. Estos se identifican por los nombres: AX, BX, CX y DX. También hay otros nueve registros con fines especiales, llamados: SI, DI, SP, BP, CS, DS, SS, ES, e IP. Por ejemplo, IP, es el Puntero de Instrucción, donde reside en la memoria la próxima instrucción.

Supongamos que escribimos un programa para sumar los números: 1234 y 4321. Cuando comienza el programa, IP contiene la dirección de una sección de memoria que contiene un patrón de unos y ceros, como se muestra en la siguiente tabla. Aunque parece sin sentido para la mayoría de los seres humanos, este patrón de unos y ceros contiene todos los comandos y los datos necesarios para completar la tarea. Por ejemplo, cuando el microprocesador encuentra el patrón de bits: 00000011 11000011, lo interpreta como un comando para tomar los 16 bits almacenados en el registro BX, y sumarlos en binario a los 16 bits almacenado en el registro AX, y almacenar el resultado en el registro AX. Este nivel de programación se denomina código máquina, y no es más que un trabajo un pelo por encima de los circuitos electrónicos reales.


Como trabajar en binario conduce eventualmente hasta a los más pacientes ingenieros a la locura, a estos patrones de unos y ceros se les asignan nombres de acuerdo a la función que realizan. A este nivel de la programación se le llama ensamblador, y un ejemplo se muestra en la siguiente Tabla. Aunque un programa en ensamblador es mucho más fácil de entender, es fundamentalmente lo mismo que la programación en código de máquina, ya que hay una correspondencia uno-a-uno entre los comandos del programa y las acciones adoptadas en el microprocesador.


Por ejemplo: ADD AX, BX se traduce a: 00000011 11000011. Un programa llamado ensamblador se usa para convertir el código ensamblador (llamado el código fuente) en los patrones de unos y ceros (llamados el código objeto o código ejecutable). Este código ejecutable se puede ejecutar directamente en el microprocesador. Evidentemente, la programación de ensamblador requiere un amplio conocimiento de la construcción interna de un particular microprocesador que se pretende utilizar.

La programación de ensamblador implica la manipulación directa de la electrónica digital: registros, localizaciones de memoria, estado de los bits, etc. El siguiente nivel de sofisticación puede manipular variables abstractas sin referencia alguna al hardware particular. Estos se llaman compilados o lenguajes de alto nivel. Una docena o así son de uso común, tales como: C, BASIC, FORTRAN, PASCAL, APL, COBOL, LISP, etc. La siguiente tabla muestra un programa BASIC para añadir 1234 y 4321. El programador sólo conoce las variables A, B y C, y nada sobre el hardware.

Un programa llamado compilador se utiliza para transformar el código fuente de alto nivel directamente a código de máquina. Esto requiere que el compilador asigne los lugares de memoria del hardware a cada una de las variables abstractas que son referenciadas. Por ejemplo, la primera vez que el compilador encuentra la variable A (línea 100), entiende que el programador está utilizando este símbolo en el sentido de una variable de punto flotante de simple precisión. En consecuencia, el compilador designa cuatro bytes de memoria que se utilizarán para nada más que para contener el valor de esta variable. Cada vez que aparece una A en el programa, la computadora sabe que tiene que actualizar el valor de los cuatro bytes como sea necesario. El compilador también rompe complicadas expresiones matemáticas, tales como: Y = LOG (XCOS (Z)), en aritmética más básica. Los microprocesadores sólo saben sumar, restar, multiplicar y dividir. Cualquier cosa que sea más complicada se debe hacer como una serie de estas cuatro operaciones elementales.

Los lenguajes de alto nivel aíslan al programador del hardware. Esto hace la programación mucho más fácil y permite que el código fuente pueda ser transportado entre los diferentes tipos de microprocesadores. Lo que es más importante, el programador que utiliza un lenguaje compilado no necesita saber nada acerca del funcionamiento interno de la computadora. Otro programador ha asumido esta responsabilidad, el que escribió el compilador.

La mayoría de los compiladores funcionan mediante la conversión de todo el programa en código de máquina antes de que sea ejecutado. Una excepción a esto es un tipo de compilador llamado intérprete, de los cuales el intérprete BASIC es el ejemplo más común. Un intérprete convierte una sola línea de código fuente en código de máquina, ejecuta el código máquina, y luego pasa a la siguiente línea de código fuente. Esto proporciona un entorno interactivo para programas simples, aunque la velocidad de ejecución es muy lenta (piensa en un factor de 100).

El nivel más alto de sofisticación de programación se encuentra en paquetes de aplicaciones para DSP. Estos vienen en una variedad de formas, y con frecuencia se proporcionan apoyo a hardware específico. Suponga que usted compra un nuevo microprocesador desarrollado de DSP a integrar en su proyecto actual. Estos dispositivos suelen tener muchas capacidades y características de DSP: entradas analógicas, salidas analógicas, E/S digital, filtros antialiasing y de reconstrucción, etc. La pregunta es: ¿cómo se programa? En el peor de los casos, el fabricante le dará un ensamblador, y esperará que tu aprendas la arquitectura interna del dispositivo. En un caso típico, te darán un compilador de C, lo que le permite el programar sin ser molestado por la forma en que opera el microprocesador.

En el mejor de los casos, el fabricante proporcionará un sofisticado paquete de software para ayudarte en la programación: las bibliotecas de algoritmos, rutinas de E/S preescritas, herramientas de depuración, etc. Puede que simplemente conectes iconos de forma deseada en un sistema fácil de utilizar de pantalla gráfica. Las cosas que manipular son vías de señales, algoritmos de procesamiento de señales analógicas, parámetros E/S, etc. Cuando estés satisfecho con el diseño, es transformado en código de máquina adecuado para la ejecución en el hardware. Otros tipos de paquetes de aplicaciones se utilizan con el procesamiento de imágenes, análisis espectral, instrumentación y control, diseño de filtros digitales, etc. Esta es la forma del futuro.

La distinción entre estos tres niveles puede ser muy difusa. Por ejemplo, la mayoría de los lenguajes compilados te permiten manipular el hardware directamente. Asimismo, un lenguaje de alto nivel con una rica biblioteca de funciones DSP está muy cerca de ser un paquete de aplicaciones. El punto de estas tres categorías es entender lo que estás manipulando: (1) hardware, (2) variables abstractas, o (3) los procedimientos completos y los algoritmos.

Existe también otro concepto importante detrás de estas clasificaciones. Al utilizar un lenguaje de alto nivel, te basas en el programador que escribió el compilador para entender las mejores técnicas para la manipulación del hardware. De igual modo, al utilizar un paquete de aplicaciones, te basas en el programador que escribió el paquete para entender mejor las técnicas DSP . Aquí está el problema: los programadores no han visto el problema particular que tu estás tratando. Por lo tanto, no siempre pueden proporcionarte una solución óptima. A medida que se opera a un nivel más alto, esperamos que el código máquina final será menos eficiente en términos de uso de memoria, velocidad y precisión.

¿Qué lenguaje de programación debo usar? Eso depende de quién eres y de lo que quieras hacer. La mayoría de los científicos y programadores de computadoras usan C (o el más avanzados de C + +). Potencia, flexibilidad, modularidad; C lo tiene todo. C es tan popular, que la pregunta se convierte en: ¿Por qué alguien programaría su aplicación DSP en algo distinto de C? Tres respuestas me vienen a la mente. En primer lugar, DSP ha crecido tan rápidamente que algunas organizaciones y personas están bloqueadas en el modo de otros idiomas, tales como FORTRAN y PASCAL. Esto es especialmente cierto en el caso de militares y agencias gubernamentales que son notoriamente lentas para cambiar. En segundo lugar, algunas aplicaciones requieren la máxima eficiencia, sólo alcanzable por la programación en ensamblador. Este cae en la categoría de "un poco más de velocidad por mucho más trabajo." En tercer lugar, C en particular no es un idioma fácil de dominar, especialmente para los programadores a tiempo parcial. Esto incluye una amplia gama de ingenieros y científicos que necesitan de vez en cuando técnicas DSP para ayudar en sus actividades de investigación o de diseño. Este grupo a menudo se convierte a BASIC, debido a su sencillez.

Comparar la velocidad de ejecución de hardware o software, es una tarea ingrata, no importa cual sea el resultado, el perdedor tendrá que llorar ¡el partido es injusto! Los programadores a los que les gustan los lenguajes de alto nivel (como los informáticos tradicionales ), sostienen que el ensamblador es sólo un 50% más rápido que el código compilado, pero cinco veces más problemático. Los que les gusta el ensamblador (por lo general, los científicos y los ingenieros de hardware) se refieren a la inversa: el montaje es cinco veces más rápido, pero sólo el 50% más difícil de usar. Como en la mayoría de las controversias, ambas partes pueden proporcionar datos selectivos en apoyo de sus reivindicaciones.

Como regla práctica, cabe esperae que una subrutina escrita en ensamblador sea de entre 1.5 y 3.0 veces más rápida que un programa comparable de alto nivel. La única manera de saber el valor exacto es escribir el código y realizar pruebas de velocidad. Como los ordenadores personales van en aumento en la velocidad de alrededor de 40% cada año, la escritura de una rutina en ensamblador es equivalente a un salto de alrededor de un período de dos años en la tecnología de hardware.

La mayoría de los programadores profesionales se ven bastante ofendidos ante la idea de utilizar ensamblador, y lo mismo con BASIC. Su razón es bastante simple: BASIC y ensamblador no permiten el uso de buenas prácticas de software. Buen código debe ser potable (capaz de pasar de un tipo de ordenador a otro), modular (roto en una estructura bien definida de subrutinas), y fáciles de entender (con muchas observaciones y descriptivos nombres de variables). La débil estructura de ensamblador y de BASIC dificulta el logro de estas normas. Esto se complica por el hecho de que las personas que se sienten atraídas por ensamblador y BASIC a menudo tienen poco entrenamiento formal en la estructura adecuada de software y documentación.

Los amantes de ensamblador responden a este ataque con uno propio. Supongamos que escribes un programa en C, y tu competidor escribe el mismo programa en ensamblador. El usuario final tendrá la primera impresión de que tu programa es basura, porque es dos veces más lento. Nadie sugeriría que escribas grandes programas en ensamblador, sólo las partes del programa que requieren una rápida ejecución. Por ejemplo, muchas funciones en las bibliotecas de software DSP están escritas en ensamblador, y luego se accede desde programas más amplio escritos en C. Incluso los más firmes puristas utilizarán software en código ensamblador, siempre y cuando no lo tengan que escribir.

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

No hay comentarios:

Publicar un comentario