Matematika v robotice 14. Saturační aritmetika

22. září 2013 v 6:24 | Petr |  Roboti a Matematika
Abychom se nemuseli otravovat s velikými čísly - předpokládejme že 4 bitový procesor zpracovává 4 bitový signál.
4 bitový signál - pokud jej bereme jako "číslo bez znaménka" alias Unsigned Integer - nabývá binárních hodnot 0000 - 1111 tedy 0-15. Pokud jej bereme jako Signed Integer - tedy "číslo se znaménkem" - nabývá hodnot 1000 - 0111 tedy -8 až +7.

Protože Unsigned integer je nejjednodušší - předpokládejme že počítáme s nimi - a že sčítáme 9+9 - což jsou obě zcela legální 4 bitová čísla. jejich součet je 18 a to už není legální 4 bitové číslo. Pokud si to napíšeme binárně je to 1001 + 1001 = 10010. Jenomže náš procesor je jenom 4 bitový takže z jeho pohledu 1001 + 1001 = 0010 neboli 9+9 = 2. Signál nám prostě "přetekl".
V případě Signed integer - je to ještě horší - představte si sčítání 7+1 tedy 0111 + 0001 = 1000. Neboli dekadicky 7+1 = -8, V obou případech pokud bychom si přetečení představili jako zvuk - patnrně by ten prudký skok signálu zněl v repráku jako "prásknutí" - až by se nám protočily bubínky. To je samozřejmě nežádoucí, proto inženýři vymysleli "Saturační aritmetiku". Ta si bere základ z analogového světa - pokud přebudíme zesilovač tak vám sinusovka něpřeteče na druhou stranu, ale zůstane pěkně ořezaná - jak to vidíme na obrázku.

Z hlediska satrurační aritmetiky - pokud počítáme 9+9 z našeho příkladu - výsledek bude 15 a pokud počítáme 15 + 9 výsledek bude zase 15. "Saturace" znamená nasycení - a na příkládcích je myslím docela vidět co tím autor myslel.

V satrurační aritmetice se vám signál ořízne jako v reálném analogovém zpracování - což je lepší než přetečení . Drobným problémem je, že až na specializované DSP procesory AVR, PICka, ARM, Intel, ani další komerční procesory satrurační aritmetiku nepodporují na hardwarové úrovni. Pokud výpočty se saturační aritmetikou programujeme softwarově - znamená to, že po každé operaci musíme výsledek kontrolovat na přetečení a pokud přetečení nastalo - musíme místo přeteklé hodnoty dosadit povolené minimumu / maximum.

Jelikož jazyk C vůbec přetečení nezná - berte jako fakt, že každý procesor má dva bity jménem CARRY a OVERFLOW které nastaví pokud při aritmetických operacích k přetečení došlo.
Potom vypadá každá matematická operace takto
C = A + B
IF CARRY THEN C = 255
Nebo pro odčítání
C = A - B
IF CARRY THEN C = 0

Tohle platí pro UNSIGNED integer - kde nám přetečení indikuje CARRY bit a OVERFLOW bitu si vůbec nevšímáme. To samé pro SIGNED Integer a 8 bitovou hodnotu :
C = A + B
IF OVERFLOW THEN C = 127
Nebo pro odčítání
C = A - B
IF OVERFLOW THEN C = -128
U SIGNED integerů nám přetečení indikuje OVERFLOW a zase si nevšímáme CARRY.
Jak to naprogramovat v C ? Opravdu nevím - já bych to pogramoval v AVR Assembleru takto.
ADD R16, R17
BRCC Continue
LDI R16, 255
: Continue
Jak to naprogramovat v C bych nechal na místní guruy přes vyšší programovací jazyky - třeba na to je nějaká knihovna, jelikož všechny numerické algoritmy spěchají - zatím jsem je programoval jenom v assembleru a žádnou knihovnu pro C jsem nepotřeboval.

Takže tolik jednoduchá a přitom celkem neznámá věc se saturační aritmetikou - zbývá už jenom tradiční rada pro brunety - začíná podzim a bude chladno - ale minikraťásky s legínami - zaujmou skoro stejně jako minikraťásky na holém zadku.
 

Buď první, kdo ohodnotí tento článek.

Komentáře

1 Petr G. Petr G. | 23. září 2013 v 4:03

kolik taktů by ušetřila hw implementace v ALU

2 Pablo2048 Pablo2048 | 23. září 2013 v 7:40

Ten priklad v AVR asm je trosku tendencni - resi pouze jednu polovinu, ale budiz... V C bych to napsal asi takhle:
uint16 c = a + b;
if (c & 0xff00)
  c = 0xff;

3 petr-kubac petr-kubac | 24. září 2013 v 12:42

[2]: Nevím co je ta "druhá polovina" - předpokládáte že sčítáním dvou usnigned - tedy kladných čísel vznikne záporný výsledek ?
No a ten váš příklad je krásný, ale je na něm vidět jak C v kritických sekcích plýtvá výkonem - protože vy zjevně předpokládáte že A+B se sčítá v 16 bitovém rozlišení.
Na druhé straně dneska v době ARMů v ceně 16 nožičkové PICky - není důvod stresovat se assemblerem.

4 Dalík Dalík | 24. září 2013 v 23:06

[2]:: nevšiml jste si ještě, že VŠECHNY články tohoto blogu jsou tendenční? Je to přeci jednoznačně dané jeho názvem - "nekorektní blog". Což je dobré chápat nejen směrem k nečtenářům, ale i k nebohým čtenářům.  S čímž se ovšem někteří čtenáři smiřují těžce.

Asi dáme panu geekovi úkol saturačně sečíst signed 4bit numera:
7+(-1)=?
-8+(-1)=?
-1+(-1)=?

Do odečítání bych se raději nepouštěl, protože písemné odečítání je na moji hlavu moc. Už hodinu bádám nad odečítáním a fakt to nedávám. A totiž, i kdybych to nakonec pochopil, tak za půl roku to stejně nebudu vědět. Takže je mnohem lepší se bez takovýchto znalostí obejít. No, není lepší fungovat ve světě dvojkových doplňků a všechno jen sčítat?

5 Pablo2048 Pablo2048 | 25. září 2013 v 8:03

[3]: Tou druhou polovinou myslim to, ze preteceni na "druhe strane" ma vratit hodnotu 127, coz Vase konstrukce neresi :-)
Jiste - C bude vzdycky mene efektivni, nez optimalizovany ASM kod - viz. Vas clanek o vykonu lidskeho mozku - byla by prece ostuda, kdyby prekladac C dokazal takovou specifickou zalezitost prelozit lepe :D

[3]:

6 Pablo2048 Pablo2048 | 25. září 2013 v 8:26

[4]: i vsiml a proto jsem reakci napsal ve stejnem duchu a - muzu Vas uklidnit - jsem s tim smireny. Dekuji za (nezadany) titul geeka, za ktereho se nepovazuji a na oplatku mam pro Vas jiny ukol - mejme dnes bezne pouzivany STM32F1xx - velmi rad bych videl Vase reseni v ASM, ktere vycte obraz z kamery OV2640 a ulozi ho ve formtu JPEG na SD kartu v souborovem systemu FAT32 do adresare rekneme /foto/
Abych predesel dalsim ofenzivnim poznamkam - chapu, ze assembler ma stale vyznam (konecknocu jsem na nem take vyrostl), muj prispevek pouze nabidl podobne "nekorektni" reseni problemu pro diskuzi nebo inspiraci...

7 Dalík Dalík | 25. září 2013 v 11:39

Pablo [4]:: Tak pozor, teď došlo možná k politováníhodnému nedorozumnění, Vás za geeka rozhodně nepovažuji, tím úkolem jsem chtěl oslovit autora blogu.
Protože věc v blogu probranou prostě nechápu.

Např. - sčítání signed integer 4 bit:
-1 + 1 = 0
tedy: 1111 + 0001 = 0000
Nastaveny budou příznaky C i O a výsledek bude zcela správný.

Jenže podle geeka P.K., cituji:
"Tohle platí pro UNSIGNED integer - kde nám přetečení indikuje CARRY bit a OVERFLOW bitu si vůbec nevšímáme. To samé pro SIGNED Integer a 8 bitovou hodnotu :
C = A + B
IF OVERFLOW THEN C = 127"

Takže, pakliže tuto logiku uplatníme pro  4bitové číslo, tak:
-1 + 1 = 7

Z čehož nemám dobrý pocit.

8 Pablo2048 Pablo2048 | 25. září 2013 v 12:45

[7]: eee, tak to se omlouvam za svoji trosku prudsi reakci... Ja si myslim, ze to je ok - v uvodu pan Kubac pise neco o 4 bitovem procesoru, pak by to fungovalo :-), akorat pak byl prechod na AVR...

9 Dalík Dalík | 25. září 2013 v 13:14

Pablo: v poho.

A už to chápu, geek má pravdu, jako vždy. Ke generování overflow dojde pouze v těch potřebných ošemetných případech. Wiki: "Internally, the overflow flag is usually generated by an exclusive or of the internal carry into and out of the sign bit".
Takže je to OK a mé dotazy se stávají bezpředmětnými. Tak to má být :)

Komentáře jsou uzavřeny.


Aktuální články

Reklama