Warum kann ich „fold“ eine Reihe von ganzen Zahlen in eine Hälfte der Größe, ohne Informationen zu verlieren?

Question

Ich versuche ein Papier auf lossless zu verstehen Kompression von Gleitkommazahlen und erhalten auf einen bestimmten Schritt stecken, wo die Autoren eine signierte ganze Zahl von einem bestimmten Bereich in einem Bereich von der halben Größe der Karte, Informationen zu verlieren, die ich denken würde, erforderlich ist. Ich habe das Gefühl, dass die Autoren eine Standard-Technik verwenden, die ihrem Publikum so offensichtlich ist, dass sie nicht erklären stören, aber das ist völlig undurchsichtig für mich.

Der Wert, der „gefaltet“ ist die Differenz zwischen zwei 23-Bit-positiven ganzen Zahlen Wesen (die Mantissen einer vorhergesagten und einer tatsächlichen Gleitkommawert), die liegt zwischen 1 bis 2 ²³ und 2 < sup> 23 - 1. die Autoren bewegen die Zahlen mit den höchsten Werten (negativ und positiv) „nach innen“, so dass der resultierende Bereich halb so groß ist und jede Zahl (außer 0) zuordnet zwei mögliche Werte aus der Original-Bereich. Das macht mich fragen, wie der Prozess sollte immer den ursprünglichen Wert zu bestimmen, rückgängig gemacht werden. In den authors` eigenen Worten:

  

Wir berechnen den signierten Korrektor, dass der kürzeste modulo 2 ²³ und die Anzahl k, die das engste Intervall angibt (1-2 ^K 2 ^k ), in denen dieser Korrektors fällt. Als nächstes diese Zahl k, die zwischen 0 bis 22 reicht komprimiert wird [...]. Schließlich werden die k + 1 Bits des Korrektors komprimiert werden.

Der Pseudo-Code für diese gegeben ist als:

void comp mantissa(int expo, int a, int p) {
  // c will be within [1-2^23 ... 2^23 -1]
  int c = a - p;
  // wrap c into [1-2^22 ... 2^22 ]
  if (c <= -(1<<22)) c += 1<<23;
  else if (c > (1<<22)) c -= 1<<23;
  // find tightest [1-2^k ... 2^k ] containing c
  int k = 0;
  // loop could be replaced with faster code
  int c1 = (c < 0 ? -c : c);
  while (c1) { c1 = c1 >> 1; k++ }
  // adjust k for case that c is exactly 2k
  if (k && (c == 1<<(k-1))) k--;

  // .. further code omitted for brevity
}

, um die Ist-Kompressionsverfahren Ignorieren, besteht die Ausgabe der c und k. Was ich nicht bekommen, ist: Wie kann ich das Original c von c und k, wenn die „Wrap-c in“ Teil über nur abbildet Hälfte des Potentialbereich auf die andere Hälfte wiederherstellen Ich habe versucht, diese auf Papier mit 4 anstelle von 23 Bit und ich es einfach nicht bekommen.

Answer 1

Wenn der Autor sagt, dass sie die Mantissen „Modulo 2 ^ 23“ in Betracht ziehen, dass die Zahlen bedeutet, wird in 23-Bit-Integer gespeichert werden, so dass Zahlen, die von 2 um ein Vielfaches unterscheiden ^ 23 wird „das gleiche“, da die Bitmuster ist das gleiche. (Siehe http://mathworld.wolfram.com/ModularArithmetic.html )

Da die „Wrapping“ Code nach c = ap fügt nur oder subtrahiert 2 ^ 23 bis c, wenn Sie später diese rückgängig machen, indem die Berechnung a = c + p Sie den richtigen Wert zu erhalten als 2 ^ 23 keine Rolle spielt.

Hier ist ein Beispiel binär ...

a =             00000000000000000000001
p =             10000000000000000000100
c = a-p =      -10000000000000000000011

dann, da c <= - (1 << 22) tritt die Verpackung ...

c = c+(1<<23) = 11111111111111111111101

Welche wird dann codiert. Dann später, können Sie eine von c und p zurück:

a = c+p =      100000000000000000000001

aber da dies in einer 23-Bit-Ganzzahl gespeichert ist, das entspricht:

a =             00000000000000000000001

, die das Original a.