情報を失わずに、整数範囲を半分のサイズに「折りたたむ」ことができるのはなぜですか?

Question

私は理解しようとしています 浮動小数点数の可逆圧縮に関する論文 そして、著者が特定の範囲の符号付き整数を半分のサイズの範囲にマッピングするという特定のステップで行き詰まり、必要だと思われる情報が失われてしまいます。著者たちは、聴衆にとっては明白なのでわざわざ説明する必要もないような、標準的なテクニックを使っているような気がしますが、私にはまったくわかりません。

「折り畳まれる」値は、1 ～ 2 の間にある 2 つの 23 ビット正の整数 (予測された浮動小数点値と実際の浮動小数点値の仮数) の差です。²³ そして2²³ - 1.著者らは、最大値 (負と正) を持つ数値を「内側」に移動するため、結果の範囲は半分のサイズになり、各数値 (0 を除く) は元の範囲の 2 つの可能な値にマッピングされます。このことを考えると、元の値を決定するためにプロセスをどのように逆にすればよいのか疑問に思います。著者自身の言葉では次のようになります。

最短のモジュロ 2 である符号付き補正子を計算します。²³ そしてその番号 k 最も狭い間隔を指定します (1-2^k , 2^k) この補正器はこれに該当します。次にこの数字 k, 、0 ～ 22 の範囲は圧縮されます [...]。最後に、 k + 1 補正器の重要なビットが圧縮されます。

この疑似コードは次のようになります。

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
}

実際の圧縮方法を無視すると、出力は次のようになります。 c そして k. 。私が理解できないのは次のとおりです: どうすれば元に戻せますか c から c そして k 上記の「wrap c into」の部分は、潜在的な範囲の半分を残りの半分にマッピングするだけの場合ですか? 紙の上で23ビットではなく4ビットで試してみましたが、理解できませんでした。

Answer 1

著者が「2^23 を法とする」仮数部を考慮していると言っているのは、数値が 23 ビット整数で格納されることを意味します。そのため、ビット パターンが次のとおりであるため、2^23 の倍数だけ異なる数値は「同じ」になります。同じ。（見る http://mathworld.wolfram.com/ModularArithmetic.html)

c=a-p の後の「ラッピング」コードは 2^23 を c に加算または減算するだけなので、後で a = c+p を計算してこれを逆にすると、2^23 は重要ではないため、正しい値が得られます。

以下はバイナリの例です...

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

次に、c<=-(1<<22) なので、ラッピングが発生します...

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

それがエンコードされます。その後、c と p から a を返すことができます。

a = c+p =      100000000000000000000001

ただし、これは 23 ビット整数で格納されるため、次と同等です。

a =             00000000000000000000001

これがオリジナルの a です。