Perché posso "piegare" un intervallo di numeri interi in una metà della dimensione senza perdere informazioni?

Question

Sto cercando di capire un documento su lossless compressione di numeri in virgola mobile e rimanere bloccati in un particolare passaggio in cui gli autori mappano un intero con segno da un certo intervallo in un intervallo di metà della dimensione, perdendo le informazioni che riterrei necessarie. Ho la sensazione che gli autori stiano usando una tecnica standard che è così ovvia per il loro pubblico che non si preoccupano di spiegare, ma che è completamente opaco per me.

Il valore che viene "piegato" è la differenza tra due numeri interi positivi a 23 bit (le mantisse di un valore in virgola mobile previsto e effettivo) compreso tra 1 - 2 ²³ e 2 ²³ - 1. Gli autori spostano i numeri con i valori più alti (negativi e positivi) "verso l'interno", quindi l'intervallo risultante è metà della dimensione e ciascun numero (tranne 0) viene mappato su due possibili valori dell'intervallo originale. Questo mi fa domandare come mai il processo dovrebbe essere invertito per determinare il valore originale. Nelle stesse parole degli autori:

  

Calcoliamo il correttore firmato che è il modulo 2 più breve ²³ e il numero k che specifica l'intervallo più stretto (1-2 ^k , 2 ^k ) in cui rientra questo correttore. Successivamente, questo numero k , compreso tra 0 e 22, viene compresso [...]. Infine i bit significativi del correttore k + 1 sono compressi.

Lo pseudocodice per questo è dato come:

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
}

Ignorando il metodo di compressione effettivo, l'output è costituito da c e k . Quello che non capisco è: Come posso ripristinare il c originale da c e k quando il " avvolge c in " ; parte sopra mappa solo metà della gamma potenziale sull'altra metà? Ho provato questo su carta con 4 invece di 23 bit e non capisco.

Answer 1

Quando l'autore dice che stanno prendendo in considerazione i significati "modulo 2 ^ 23", ciò significa che i numeri verranno memorizzati in numeri interi a 23 bit, quindi i numeri che differiscono per multipli di 2 ^ 23 saranno "gli stessi" poiché il modello di bit è lo stesso. (Vedi http://mathworld.wolfram.com/ModularArithmetic.html )

Dal momento che il "wrapping" il codice dopo c = a-p aggiunge o sottrae solo 2 ^ 23 in c, quando invertilo successivamente calcolando a = c + p ottieni il valore giusto poiché il 2 ^ 23 non ha importanza.

Ecco un esempio in binario ...

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

quindi, poiché c < = - (1 < < 22), il wrapping si verifica ...

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

Che viene quindi codificato. Quindi, puoi tornare a da c e p:

a = c+p =      100000000000000000000001

ma poiché questo è memorizzato in un numero intero a 23 bit, questo equivale a:

a =             00000000000000000000001

che è l'originale a.