Verständnisproblem Festkomma-Arithmetik

[Fractional (Gast)]

Hallo.

Ich habe derzeit ein kleines Verständnisproblem bei der 
Festkomma-Arithmetik, genauer gesagt bei der Verwendung des 
Fractional-Formats Q15 oder Q31.
Bitte korrigiert mich, wenn ich falsch liege:

Bei der Addition von zwei Q1.31 Zahlen ist das Ergebnis im Format Q2.31.
Das ist mir ja klar, da ja das Ergebnis nicht mehr im Bereich [-1,1[ 
sein muss. Gleiches gilt für die Subtraktion.

Für die Multiplikation von zwei Q1.31 Zahlen ist das Ergebnis im Format 
Q2.62. Die zweite binäre Vorkommastelle wird benötigt, dass das Ergebnis 
von -1 * -1 dargestellt werden kann. Um das Ergebnis wieder in Q1.31 
darzustellen, muss es um 31 Stellen nach rechts verschoben und saturiert 
werden.

Wie sieht es bei der Division?
Wenn man die Multiplikation gedanklich umformt:

                                         Q2.62
Q1.31 * Q1.31 = Q2.62    ==>    Q1.31 = -------
                                         Q1.31

würde das richtige Ergebnis rauskommen.
Aber dabei habe ich das Problem, dass das Ergebnis auch 1 werden kann.
Die Zahl 1 kann aber im Q1.31 Format nicht dargestellt ...
Habe ich dabei einen Denkfehler oder übersehe ich was?

Kann da jemand ein gutes Buch/Webseite empfehlen?
Ich habe schon mehrere Bücher bei Google Books und so gefunden, aber die 
Kapitel über Festkommazahlen/Fractionals sind da meistens nur 
oberflächlich behandelt. Behauptungen, dass Zahlen von +/-1 (also inkl. 
+1) dargestellt werden können oder dass bei der Multiplikation von 
Fractionals nie ein Überlauf auftreten kann, sind keine seltenheit :(

[Torsten C. (torsten_c)]

Fractional schrieb:
> Bei der Addition von zwei Q1.31 Zahlen ist das Ergebnis im Format Q2.31.
> Das ist mir ja klar, da ja das Ergebnis nicht mehr im Bereich [-1,1]
> sein muss.

Also Vorzeichen-behaftet (Q nicht UQ). Für Q1.31 brauchst Du 33 Bits.

Du meinst sicher "Q31", damit Du mit 32 Bit auskommst:
> For a given Qm.n format, using an m+n+1 bit signed integer container with
> n fractional bits:
> * its range is [-(2^m),2^m-2^-n]
> * its resolution is 2^-n
https://en.wikipedia.org/wiki/Q_%28number_format%29

Fractional schrieb:
> Aber dabei habe ich das Problem, dass das Ergebnis auch 1 werden kann.

Nicht nur das. Es kann sogar größer werden als 1, wenn der Nenner 
kleiner ist, als der Zähler. Das nennt man Überlauf und dagegen ist jede 
Division abzusichern, erst Recht gegen eine Division durch Null.

Fractional schrieb:
> Ich habe derzeit ein kleines Verständnisproblem

Ist es damit gelöst?

[Fractional (Gast)]

Hallo.

Also es gibt ja 2 Konventionen (eigentlich ziemlich dumm...):
1) 32 Bit -> Q31 -> Q1.31
2) 32 Bit -> Q31 -> Q0.31
ich beziehe mich auf die erste Notation, wo also das "Vorzeichen-Bit" 
mitgezählt wird.

Das das Ergebnis der Division >= 1 werden kann ist mir auch nach dem 
Post aufgefallen.

[Torsten C. (torsten_c)]

Fractional schrieb:
> Also es gibt ja 2 Konventionen (eigentlich ziemlich dumm...):

Also 2) Nur der Teil "0." ist optional.

Wo hast Du die 1. Konvention gesehen, wo der Teil "1." optional ist?

UQ0.32 = UQ32 -> 32 Bit unsigned
UQ1.31        -> 32 Bit unsigned
Q0.31 = Q31   -> 32 Bit signed
Q1.31 wären      33 Bit signed, also … naja.

Siehe Wikipedia^^:
> For a given UQm.n format, using an m+n bit unsigned integer …

Ist Dein kleines Verständnisproblem nun gelöst?

[Fractional (Gast)]

Ausgehend von vorzeichenbehafteten, in 2er Komplement dargestellten 
Fractional-Zahlen. Ich hätte meinen ersten Beitrag etwas detaillierter 
schreiben sollen.... :/

Nein, tut mir leid. Die Notation ist nicht mein Verständnisproblem ;)
Ich würde gerne eine Allgemeine Formel (oder ähnliches) für die 
Vorgehensweise der Fractional-Division haben.

Vgl. Multiplikation:
Qm1.n1 * Qm2.n2 = Q(m1+m2).(n1+n2)



Zu der Darstellung im Q-Format:
Es gibt zwei Konventionen, wie unter anderem auch auf der 
Wikipedia-Seite steht 
https://en.wikipedia.org/wiki/Q_%28number_format%29

... There are two conflicting notations for fixed point. Both notations 
are written as Qm.n, where:
...
m. (optional, assumed to be zero or one) is the number of bits set aside 
to designate the two's complement integer portion of the number, 
exclusive or inclusive of the sign bit (therefore if m is not specified 
it is taken as zero or one).
-----

Weitere:

http://asf.atmel.com/docs/latest/uc3b/html/group__group__qformat.html

https://books.google.at/books?id=h590cd_BagMC&pg=PA88&dq=%22Q1.15%22&hl=de&sa=X&ved=0CCIQ6AEwAGoVChMIkYfDl5C6xwIVhVcaCh3cPgRg#v=onepage&q=Q1.15&f=false

[Torsten C. (torsten_c)]

Ah, OK, danke. Wieder was gelernt. :-) Und das wichtigste:
> The choice of convention can be determined by summing m+n.
Fractional schrieb:
> ich beziehe mich auf die erste Notation
Dann bleiben wir bei dieser.

Fractional schrieb:
> Wenn man die Multiplikation gedanklich umformt:
> Q1.31 * Q1.31 = Q2.62

Also z.B.:

     -1 x   -1 =      1 ist in Q1.7/Q2.14-Festkomma-Arithmetik:
   0x80 x 0x80 = 0x4000

Das passt, denn +1 lässt sich in Q2.14 darstellen.

Aber nicht in Q1.7! Das war doch Dein Verständnisproblem, oder?

Ich würde die -1 daher als "Überlauf" betrachten und nicht benutzen.

Wenn Du den Bereich "±1" benötigtst, solltest Du in Q2.30 rechnen statt 
in Q1.31.

@All: Oder hat jemand eine bessere Idee?

Zur Division nochmal genauer: Vorher den Überlauf abfangen, falls der 
Betrag (Absolut-Wert) des Nenners kleiner als der Betrag des Zählers 
ist, dann klappt es auch bei der Division!

Also "kleiner" und nicht "kleiner oder gleich"!

Wenn Du mit "Nenner < Zähler" arbeiten willst, musst Du den Nenner 
vorher mit "<<" shiften, also z.B. aus einem Q2.30 ein "Q1.31" machen.


Ist Dein kleines Verständnisproblem nun gelöst?

BTW1: Ich habe gehört, dass einige Compiler mit den Operatoren ">>" und 
"<<" ein "logisches Shift" machen, kein arithmetisches. Ggf. also 
Vorsicht beim Umwandeln von negativen Zahlen z.B. von Q4.60 in Q2.30!

BTW2: Was ist, wenn man z.B. mit einer Auflösung von 2^-1 arbeitet?
Ist das dann Q0.32 = "Q-1.32"? Eigentlich ist diese ganze 
Q-Format-Konvention ziemlich dumm.

Beruflich arbeiten wir bei Festkomma-Arithmetik mit "Datentyp", "Offset" 
und "Auflösung". Also:

Ein Signal (Variable) hat eine Auflösung von 2^x und einen Offset von y.
Ein "Q-1.32" wäre dann ein INT32 mit Auflösung = 2^-32 und Offset = 0 
und ginge von -0,5 bis +0,499….