Aritmètica de saturació

Aritmètica de saturació (saturation arithmetic) és una versió d'aritmètica en la que totes les operacions com l'adició i la multiplicació estan llimitades a un ranc fix entre un valor mínim i un de màxim. Si el resultat d'una operació és major que el màxim, és ajustada ("restringida") al màxim; Si està per baix del mínim, és restringida al mínim. El nom ve de cóm els valors es tornen "saturats" una volta que alcancen els valors extrems; més adició al màxim o substraccions al mínim no canviaran el resultat.

Per eixemple, si l'interval vàlit de valors és de -100 a 100, les següents operacions produïxen els següents valors:

• 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

Com pot vore's en estos eixemples, propietats familiars com l'asociatividad i la distributividad fallen en l'aritmètica de saturació. Açò fa que siga desagradable tractar en matemàtiques abstractes, pero té un paper important que eixercitar en algoritmes i hardware digital.

Per lo general, els primers microprocessadorés de computador no varen implementar operacions aritmètiques sancer usant saturació aritmètica; en canvi, varen utilisar la més fàcil d'implementar aritmètica modular, en la que els valors que superaven el valor màxim "donaven el regrés" ("wrap around") cap al valor mínim, com les hores en un rellonge, passant de 12 a 1. En hardware, l'aritmètica modular en un mínim de zero i un màxim de $2^n-1$ pot ser implementada simplement descartant tot llevat els $n$ bits menors.

No obstant, encara que més difícil d'aplicar, la saturació aritmètica té numeroses ventages pràctiques. El resultat és numèricament tan propenc a la resposta verdadera com siga possible; és considerablement menys sorprenent tindre una resposta de 127 en lloc de 130 que obtindre una resposta de −126 en lloc de 130. També permet ser detectat consistentement, el desbordament (overflow) de adició i multiplicacions per simple comparació en el valor màxim o mínim (sempre i quan no siga permés a la senya prendre estos valors), en lloc d'usar un bit de desbordament o còmput excessiu.

Adicionalment, la saturació aritmètica permet algoritmes eficients per a molts problemes, particularment en el processament digital de senyals. Per eixemple, ajustar el nivell de volum d'una senyal de sò pot resultar en un desbordament i la saturació causa significativament menys distorsió del sò que el wrap-around. En paraules dels investigadors G. A. Constantinides et al.:

En sumar dos números usant la representació de complement a dos, el desbordament resulta en un fenomen de 'wrap-around'. El resultat pot ser una pèrdua catastròfica en relació senyal a soroll en un sistema DSP. Senyals en dissenys DSP són per lo tant generalment escalades adequadament per a evitar el desbordament per tots llevat els vectores d'entrada més extrems, o produïda usant components aritmètics de saturació.

Les operacions aritmètiques de saturació estan disponibles en moltes plataformes modernes i en particular va ser una de les extensions fetes per la plataforma Intel MMX, específicament per a tals aplicacions de processament de senyal.

L'aritmètica de saturació per a número entero, també ha segut implementada en software per a un número de llenguages de programació incloent C, C++, Eiffel. Açò ajuda als programadors anticipar i comprendre millor els efectes del desbordament. Per un atre costat, la saturació és difícil implementar eficientemente en software en una màquina en solament operacions d'aritmètica modular, ya que les implementacions simples requerixen forcalls que creen enormes retarts de la canonada (pipeline).

Encara que la saturació aritmètica és menys popular per a aritmètica de sancers en hardware, l'estàndart IEEE de menge flotant, la més popular abstracció per a tractar en número real aproximats, utilisa una forma de saturació en la que el desbordament és convertit en "infinit" o "infinit negatiu", i qualsevol atra operació en este resultat continua produint el mateix valor. Açò té la ventaja sobre la saturació simple que operacions posteriors que disminuïxquen el valor no terminaran produint un resultat "raonable", com en el còmput $\sqrt{x^2-y^2}$.

Vore també

• Aritmètica modular