정보를 잃지 않고 범위의 정수를 크기의 절반으로 "접을"수 있습니까?

Question

나는 이해하려고 노력하고있다 부동 소수점 번호의 무손실 압축에 관한 논문 저자가 특정 범위에서 서명 된 정수를 특정 범위에서 크기의 절반 범위에 매핑하여 필요한 정보를 잃어버린 특정 단계에 갇히게됩니다. 나는 저자들이 청중에게 너무 분명한 표준 기술을 사용하고 있다고 생각하지 않아서 설명하기를 귀찮게하지는 않지만 나에게 완전히 불투명하다는 느낌이 들었습니다.

"접은"값은 1-2 사이의 23 비트 양성 정수 (예측 된 Mantissas와 실제 부동 소수점 값)의 차이입니다.²³ 그리고 2²³ -1. 저자는 숫자를 가장 높은 값 (음수 및 양수) "안쪽"으로 이동 시키므로 결과 범위는 크기의 절반이며 각 숫자 (0 제외)는 원래 범위에서 두 가지 가능한 값으로 맵핑됩니다. 따라서 원래 값을 결정하기 위해 프로세스를 어떻게 바꾸어야하는지 궁금해합니다. 저자 자신의 말로 :

우리는 가장 짧은 모듈로 2 인 서명 된 조정자를 계산합니다.²³ 그리고 숫자 k 가장 큰 간격을 지정합니다 (1-2^케이 , 2^케이)이 교정기가 떨어지는 곳. 다음 으로이 숫자 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 위의 "랩 C"부분이 전위 범위의 절반을 다른 절반에 매핑 할 때? 나는 23 비트 대신 4 개로 종이에 이것을 시도했지만 나는 그것을 얻지 못한다.

Answer 1

저자가 "Modulo 2^23"의 중요성을 고려하고 있다고 말하면, 숫자는 23 비트 정수에 저장 될 것이므로 2^23의 배수로 다른 숫자는 "동일"합니다. 똑같다. (보다 http://mathworld.wolfram.com/modulararithmetic.html)

C = AP 이후의 "랩핑"코드는 2^23을 추가하거나 빼기 때문에 나중에 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입니다.