Aritmética de saturación
Aritmética de saturación (saturation arithmetic) es una versión de aritmética en la que todas las operaciones como la adición y la multiplicación están limitadas a un rango fijo entre un valor mínimo y uno máximo. Si e resultado de una operación es mayor que el máximo, es ajustada ("restringida") al máximo; Si está por debajo del mínimo, es restringida al mínimo. El nombre viene de cómo los valores se vuelven "saturados" una vez que alcanzan los valores extremos; más adiciones al máximo o sustracciones al mínimo no cambiarán el resultado.
Por ejemplo, si el intervalo válido de valores es de -100 a 100, las siguientes operaciones producen los siguientes valores:
- 60 + 43 = 100
- (60 + 43) − 150 = −50
- 43 − 150 = −100
- 60 + (43 − 150) = −40
- 10 × 11 = 100
- 99 × 99 = 100
- 30 × (5 − 1) = 100
- 30 × 5 − 30 × 1 = 70
Como puede verse en estos ejemplos, propiedades familiares como la asociatividad y la distributividad fallan en la aritmética de saturación. Esto hace que sea desagradable tratar con matemáticas abstractas, pero tiene un papel importante que desempeñar en algoritmos y hardware digital.
Por lo general, los primeros microprocesadores de computador no implementaron operaciones aritméticas entero usando saturación aritmética; en cambio, utilizaron la más fácil de implementar aritmética modular, en la que los valores que superaban el valor máximo "daban la vuelta" ("wrap around") hacia el valor mínimo, como las horas en un reloj, pasando de 12 a 1. En hardware, la aritmética modular con un mínimo de cero y un máximo de puede ser implementada simplemente descartando todo excepto los bits menores.
Sin embargo, aunque más difícil de aplicar, la saturación aritmética tiene numerosas ventajas prácticas. El resultado es numéricamente tan cercano a la respuesta verdadera como sea posible; es considerablemente menos sorprendente tener una respuesta de 127 en lugar de 130 que obtener una respuesta de −126 en vez de 130. También permite ser detectado consistentemente, el desbordamiento (overflow) de adiciones y multiplicaciones por simple comparación con el valor máximo o mínimo (siempre y cuando no sea permitido al dato tomar estos valores), en vez de usar un bit de desbordamiento o cómputo excesivo.
Adicionalmente, la saturación aritmética permite algoritmos eficientes para muchos problemas, particularmente en el procesamiento digital de señales. Por ejemplo, ajustar el nivel de volumen de una señal de sonido puede resultar en un desbordamiento y la saturación causa significativamente menos distorsión del sonido que el wrap-around. En palabras de los investigadores G. A. Constantinides et al.:
Al sumar dos números usando la representación de complemento a dos, el desbordamiento resulta en un fenómeno de 'wrap-around'. El resultado puede ser una pérdida catastrófica en relación señal a ruido en un sistema DSP. Señales en diseños DSP son por lo tanto generalmente escaladas adecuadamente para evitar el desbordamiento por todos excepto los vectores de entrada más extremos, o producida usando componentes aritméticos de saturación.[1]
Las operaciones aritméticas de saturación están disponibles en muchas plataformas modernas y en particular fue una de las extensiones hechas por la plataforma Intel MMX, específicamente para tales aplicaciones de procesamiento de señal.
La aritmética de saturación para números enteros, también ha sido implementada en software para un número de lenguajes de programación incluyendo C, C++, Eiffel. Esto ayuda a los programadores anticipar y comprender mejor los efectos del desbordamiento. Por otro lado, la saturación es difícil implementar eficientemente en software en una máquina con solo operaciones de aritmética modular, ya que las implementaciones simples requieren bifurcaciones que crean enormes retrasos de la tubería (pipeline).
Aunque la saturación aritmética es menos popular para aritmética de enteros en hardware, el estándar IEEE de coma flotante, la más popular abstracción para tratar con números reales aproximados, utiliza una forma de saturación en la que el desbordamiento es convertido en "infinito" o "infinito negativo", y cualquier otra operación con este resultado continúa produciendo el mismo valor. Esto tiene la ventaja sobre la saturación simple que operaciones posteriores que disminuyan el valor no terminarán produciendo un resultado "razonable", como en el cómputo .
Véase también
Referencias
- G. A. Constantinides, P. Y. K. Cheung, and W. Luk. Synthesis of Saturation Arithmetic Architectures
Enlaces externos
- SARITH: Safe ARITHmetic – A Progress Report: Report on a saturation arithmetic component for Eiffel.