시끄러운 부동 소수점 배열을 '체크섬'하는 방법은 무엇입니까?

Question

지정된 소수의 부정확성을 허용하면서 부동 소수점 배열을 '체크섬'하는 빠르고 쉬운 방법은 무엇입니까?

이론적으로는 무한 정밀도로 동일한 배열을 출력해야하는 두 개의 알고리즘이 있습니다. 그러나 그것들은 다르게 작동하기 때문에 부동 소수점 오차는 다르게 축적 될 것입니다. 그러나 배열 길이는 정확히 같아야합니다. 배열이 똑같은지 테스트하는 빠르고 쉬운 방법이 필요합니다. 물론 숫자를 쌍으로 비교할 수 있으며 최대 오류를보고 할 수 있습니다. 그러나 하나의 알고리즘은 C++에 있고 다른 하나는 Mathematica에 있고 나는 파일에 숫자를 쓰거나 한 시스템에서 다른 시스템으로 그것을 붙여 넣는 것을 원하지 않습니다. 그래서 간단한 체크섬을 원합니다.

간단히 배열의 모든 숫자를 더할 수 있습니다. 배열 길이가 N이고 각 숫자에서 0.0001의 오류를 허용 할 수 있다면 abs(sum1-sum2)<0.0001*N인지 확인합니다. 하지만이 단순한 '체크섬'은 견고하지 않습니다. 하나의 엔트리에서 +10의 에러와 다른 엔트리에서 -10의 에러. (그리고 어쨌든, 확률 이론은 N이 아닌 sqrt (N)과 같이 성장할 것이라고 말합니다.) 물론 체크섬은 데이터의 덩어리에 대한 낮은 차원의 요약이므로 누락 될 수 있습니다. 일부 오류 대부분의 경우 ... 그러나 간단한 체크섬은 그럼에도 불구하고 악의가없는 버그 유형 오류를 찾는 데 유용합니다.

또는 2 차원 체크섬 [sum(x[n]), sum(abs(x[n]))]을 만들 수 있습니다. 그러나 내가 할 수있는 최선의 방법, 즉 sum(x[n])에 "더 직각"이 될 수있는 다른 기능이 있습니까? 일부 임의의 함수 (예 : [sum(f1(x[n])), sum(f2(x[n]))], 그러면 '원시 오류 허용치'는 '체크섬 오류 허용치'로 어떻게 변환되어야합니까?

저는 C++로 프로그래밍하고 있습니다 만, 어떤 언어로든 답을 볼 수있어서 기쁩니다.

Answer 1

나는 결정 론적 대답을 찾고 잠시 동안 찾지 못했다. 좋은 대답이 있다면, 그것은 중장비 수학 스킬 (기능 분석)을 요구할 것입니다.

나는 "어떤 교활한 방법으로 이산화 후, 이산 체크섬을 적용"한 해결책이 없다고 확신합니다. "0/1 /?의 문자열로 분리합니다. 여기서?는 와일드 카드를 의미합니다". 임의의 이산화는 서로 매우 가까운 두 부동 소수점 숫자가 서로 다른 이산 코드로 끝날 수있는 속성을 갖게 될 것이고 이산 체크섬은 우리가 알고 싶은 것을 말하지 않을 것입니다.

그러나 매우 간단한 무작위 체계가 잘 작동합니다. {+ 1, -1} 알파벳에서 의사 임의 문자열 S를 생성하고 csx = sum (X_i * S_i) 및 csy = sum (Y_i * S_i)을 계산하십시오. 여기서 X와 Y는 부동 소수점 숫자의 원래 배열입니다. 오류를 평균 0의 독립적 인 정규 확률 변수로 모델링하면 csx-csy의 분포를 계산하기가 쉽습니다. 우리는 여러 문자열 S에 대해이 작업을 수행 한 다음 평균 오류가 0이라는 가설 테스트를 수행 할 수 있습니다. 테스트에 필요한 문자열 S의 수는 고정되어 있으며 배열 크기에서 선형 적으로 증가하지 않으므로 "저 차원 적 요약"에 대한 나의 필요성. 이 방법을 사용하면 오류의 표준 편차를 쉽게 예측할 수 있습니다.

Answer 2

이 시도 :

#include <complex> 
#include <cmath> 
#include <iostream> 

// PARAMETERS 
const size_t no_freqs = 3; 
const double freqs[no_freqs] = {0.05, 0.16, 0.39}; // (for example) 

int main() { 
    std::complex<double> spectral_amplitude[no_freqs]; 
    for (size_t i = 0; i < no_freqs; ++i) spectral_amplitude[i] = 0.0; 
    size_t n_data = 0; 
    { 
     std::complex<double> datum; 
     while (std::cin >> datum) { 
      for (size_t i = 0; i < no_freqs; ++i) { 
       spectral_amplitude[i] += datum * std::exp(
        std::complex<double>(0.0, 1.0) * freqs[i] * double(n_data) 
       ); 
      } 
      ++n_data; 
     } 
    } 
    std::cout << "Fuzzy checksum:\n"; 
    for (size_t i = 0; i < no_freqs; ++i) { 
     std::cout << real(spectral_amplitude[i]) << "\n"; 
     std::cout << imag(spectral_amplitude[i]) << "\n"; 
    } 
    std::cout << "\n"; 
    return 0; 
} 

그것은 푸리에의 몇 가지 임의의 점은 전체 데이터 세트의 변환을 반환합니다. 이것들은 말하자면 퍼지 체크섬을 만듭니다.

Answer 3

나는 gray codes과 같은 것을 통해 원하는 것을 얻을 수 있다고 생각합니다. 값을 회색 코드로 변환하고 n 비트를 수정할 수있는 일종의 체크섬을 사용하면 n-1 비트 오류를 ​​제외하고 두 배열이 같은지 여부를 감지 할 수 있습니다. (오류의 각 비트는 숫자가 "하나씩 꺼짐"을 의미하며, 매핑은 이것이 최하위 숫자의 변형이 될 것입니다).

그러나 정확한 세부 사항은 나를 넘어서 있습니다. 특히 부동 소수점 값의 경우.

도움이되는지 모르겠지만 회색 코드가 해결하는 것은 병리학 적 반올림의 문제입니다. 순진한 해결책이 둥근 다음 체크섬이 될 수있는 것처럼 문제를 해결할 것입니다. 단순 라운딩은 항상 병리 사례를 가지고 있습니다. 예를 들어 바닥을 사용하는 경우 0.9999999와 1은 별개입니다. 회색 코드 접근법은 이웃 값이 항상 단일 비트 떨어져 있기 때문에 비트 기반 체크섬이 "거리"를 정확하게 반영하므로이를 처리하는 것으로 보입니다.

[업데이트 :] 더 정확하게 원하는 것은 회색으로 인코딩 된 시퀀스 사이에 hamming distance의 예상치를 제공하는 체크섬입니다. 회색으로 인코딩 된 시퀀스는 여러 개를 모두 가질 수 있으므로 0.0001 만 신경 쓰면 회색으로 인코딩 된 부분이 쉽습니다. 10000 및 정수 사용).

그런 체크섬처럼 보입니다. do exist : 오류 감지 코드는 오류 감지에 사용할 수 있습니다.최소 해밍 거리 d를 갖는 코드는 코드 워드에서 d-1 개의 오류를 검출 할 수있다. 최소 거리 기반 오류 정정 코드를 오류 검출에 사용하는 것은 검출 될 최소 오류 수에 대한 엄격한 제한이 필요한 경우에 적합 할 수있다.

그래서 단지의 경우 그것은 분명하지 않다 : 최소 오류로

• 여러 최소 해밍 거리보다 큰 오류 검출 코드를 사용하여 해당 코드
• 을 회색으로 정수에게
• 변환을 얻을 수 당신이 용인 할 수있는 오류.

그래도 나는 그것이 옳은지 잘 모릅니다. 당신은 여전히 ​​float에서 정수로 변환에서 병리학적인 반올림을 얻습니다. 그래서 당신은 1 + len (데이터) (최악의 경우, 각 값에 반올림 오류가있는) 최소 해밍 거리가 필요해 보인다. 그것은 가능한가? 대용량 배열에서는 그렇지 않을 수도 있습니다.

아마도 더 나은 태그/설명을 다시 한 번 물어서 일반적인 방향이 가능합니까? 아니면 지금 태그를 추가 하시겠습니까? 우리는이 일을 살아가는 사람이 필요합니다. [나는 두 개의 태그를 더했다]

Answer 4

데이터의 최소 유효 자릿수를 0으로 설정하여 얻은 데이터에 대해 표준 정수 체크섬을 계산하는 방법은 무엇입니까?