Arytmetyka nasyceniowa

Dodawanie dwóch obrazów (A i B) z zastosowaniem arytmetyki nasyceniowej (górny) oraz artymetyki modulo (dolny)

Arytmetyka nasyceniowa (ang. saturation arithmetic) – sposób przeprowadzania obliczeń na całkowitych liczbach binarnych, w którym reakcją na przekroczenie zakresu liczb jest przypisanie wynikowi górnej bądź dolnej granicy zakresu. Arytmetyka ta znajduje zastosowanie m.in. w DSP (najczęściej w przetwarzaniu dźwięku i obrazu) — upraszcza programy i przyspiesza wiele algorytmów.

Dla porównania, arytmetyką powszechnie stosowaną w systemach komputerowych jest tzw. arytmetyka modularna (ang. wraparound arithmetic), tj. z wyniku uwzględniana jest zawsze określona liczba najmłodszych bitów, zaś fakt przekroczenia zakresu jest np. sygnalizowany przez procesor poprzez ustawienie określonych bitów w rejestrze flag – przy czym wykrywanie tej sytuacji i korygowanie wyników spoczywa na programie.

Obliczenia z nasyceniem dostępne są w popularnych procesorach komputerów osobistych posiadających rozszerzenia MMX, SSE2 i AVX2.

Algorytm

Nasycanie wyniku przebiega według poniższego schematu:

wynik pośredni := rezultat pewnego działania na
                  liczbach n-bitowych przechowujących
                  wartości z zakresu [min, max];
                  wynik pośredni przechowywany jest
                  na większej niż n liczbie bitów

if (wynik pośredni > max) then
  wynik := max
else if (wynik pośredni < min) then
       wynik := min
     else
       wynik := wynik pośredni

Uwzględniając to oraz wiedząc, że bajt bez znaku może przechowywać liczby z zakresu od 0 do 255, jeśli do bajta o wartości 230 zostanie dodane 100, to wynikiem będzie 255, ponieważ wynik pośredni 330 przekracza dopuszczalny zakres.

Media użyte na tej stronie

Saturated add.png
Autor: Wojciech Muła, Licencja: CC BY-SA 2.0
Comparision of saturated adding (sat) and wraparound adding