Por que pode “dobrar” uma gama de números inteiros em uma metade do tamanho sem perda de informação?

Question

Eu estou tentando entender o papel um em lossless compressão de números de ponto flutuante e ficar preso em uma determinada etapa, onde os autores mapear um inteiro assinado de uma determinada faixa em um intervalo de metade do tamanho, perdendo informação que eu acho que é necessário. Tenho a sensação de que os autores estão usando alguma técnica padrão que é tão óbvio para o seu público que eles não se preocupam em explicar, mas que é completamente opaco para mim.

O valor que está a ser "dobrado" é a diferença entre dois de 23 bits inteiros positivos (os mantissas de um e um valor de ponto flutuante real prevista) que se situa entre 1 - 2 ²³ e 2 < sup> 23 - 1. os autores mover os números com os valores mais elevados (positivos e negativos) "dentro", assim que a escala resultante é a metade do tamanho e cada número (exceto 0) mapeia para dois valores possíveis do intervalo original. Isso me faz pensar como o processo nunca deve ser revertida para determinar o valor original. Nos authors` próprias palavras:

Calculamos o corrector assinado que é o mais curto de módulo 2 ²³ e o número k que especifica o intervalo mais apertada (1-2 ^k , 2 ^k ) no qual este corrector cai. Em seguida, esse número k, que varia entre 0 e 22 é comprimido [...]. Finalmente os k + 1 bits significativos do corrector são compactados.

O pseudocódigo para isto é dada como:

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 o método de compressão real, a saída é constituída por c e k. O que eu não entendo é:? Como posso restaurar o c original do c e k quando o "envoltório c em" parte acima apenas mapas metade da faixa de potencial para a outra metade Eu tentei isso em papel com 4 em vez de 23 bits e eu simplesmente não consegui-lo.

Answer 1

Quando o autor diz que eles estão considerando as significando "módulo 2 ^ 23", que significa que os números serão armazenados em números inteiros de 23 bits, por isso os números que diferem em múltiplos de 2 ^ 23 será "o mesmo", já que o padrão de bits é o mesmo. (Veja http://mathworld.wolfram.com/ModularArithmetic.html )

Uma vez que o código "embrulho" depois c = ap só adiciona ou subtrai 2 ^ 23 para c, quando posteriormente inverter esta calculando a = c + p lo a obter o valor correto como a 2 ^ 23 não importa.

Aqui está um exemplo em binário ...

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

então, desde que c <= - (1 << 22), o envolvimento ocorre ...

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

Qual é então codificado. Então, mais tarde, você pode obter de volta um de c e p:

a = c+p =      100000000000000000000001

mas uma vez que este é armazenado em um inteiro de 23-bit, isto é equivalente a:

a =             00000000000000000000001

que é a uma origem.