एफडीएफ

Question

के बिना 1 डी फास्ट कनवॉल्यूशन मुझे 2 बड़े सरणी के खिलाफ 1 डी कनवॉल्यूशन चाहिए। मैं इस कोड का उपयोग सी # में कर रहा हूं लेकिन इसे चलाने में बहुत समय लगता है।

मुझे पता है, मुझे पता है! एफएफटी संकल्प बहुत तेज है। लेकिन इस परियोजना में मैं इसका उपयोग नहीं कर सकता। यह एफएफटी का उपयोग न करने के लिए प्रोजेक्ट की बाधा है (कृपया पूछें क्यों नहीं: /)।

यह सी # में मेरे कोड (matlab से मोड़ा वैसे,) है:

var result = new double[input.Length + filter.Length - 1]; 
for (var i = 0; i < input.Length; i++) 
{ 
    for (var j = 0; j < filter.Length; j++) 
    { 
     result[i + j] += input[i] * filter[j]; 
    } 
} 

तो, किसी को भी FFT widthout किसी भी तेजी से घुमाव के एल्गोरिथ्म जानता है?

Answer 1

कनवल्शन संख्यानुसार एक अतिरिक्त चादर के आसपास कदम के साथ एक बहुपद गुणा के समान है। इसलिए, सभी बहुपद और बड़े पूर्णांक गुणा एल्गोरिदम का उपयोग रूपांतरण को करने के लिए किया जा सकता है।

फास्ट ओ (एन लॉग (एन)) रन-टाइम प्राप्त करने का एकमात्र तरीका एफएफटी है। लेकिन आप अभी भी Karatsuba's algorithm जैसे विभाजन-और-विजय दृष्टिकोण का उपयोग करके उप-वर्गबद्ध रन-टाइम प्राप्त कर सकते हैं।

करात्सुबा का एल्गोरिदम लागू करने के लिए काफी आसान है जब आप समझते हैं कि यह कैसे काम करता है। यह ओ (एन^1.585) में चलता है, और क्लासिक ओ (एन^2) दृष्टिकोण को सुपर-ऑप्टिमाइज़ करने की कोशिश करने से शायद तेज़ होगा।

Answer 2

यहां दो संभावनाएं हैं जो मामूली गति प्रदान कर सकती हैं, लेकिन आपको सुनिश्चित करने के लिए परीक्षण करने की आवश्यकता होगी।

1. कुछ परीक्षणों को हटाने के लिए आंतरिक पाश को अनलोल करें। यदि आप जानते हैं कि फ़िल्टर की लंबाई हमेशा एक बहु होगी तो कुछ एन
2. लूप के क्रम को उलट दें। filter.length पूरे सरणी पर गुजरता है। यह आंतरिक पाश में कम dereferencing करता है लेकिन खराब कैशिंग व्यवहार हो सकता है।

Answer 3

आप अनुक्रमित की संख्या को कम कर सकता है result को एक्सेस करता है, साथ ही Length गुण:

int inputLength = filter.Length; 
int filterLength = filter.Length; 
var result = new double[inputLength + filterLength - 1]; 
for (int i = resultLength; i >= 0; i--) 
{ 
    double sum = 0; 
    // max(i - input.Length + 1,0) 
    int n1 = i < inputLength ? 0 : i - inputLength + 1; 
    // min(i, filter.Length - 1) 
    int n2 = i < filterLength ? i : filterLength - 1; 
    for (int j = n1; j <= n2; j++) 
    { 
     sum += input[i - j] * filter[j]; 
    } 
    result[i] = sum; 
} 

---

आप आगे बाहरी पाश विभाजित हैं, तो आप कुछ दोहरा सशर्त, से छुटकारा पा सकते । (यह 0 < filterLength ≤ inputLength ≤ resultLength मान लिया गया है)

int inputLength = filter.Length; 
int filterLength = filter.Length; 
int resultLength = inputLength + filterLength - 1; 

var result = new double[resultLength]; 

for (int i = 0; i < filterLength; i++) 
{ 
    double sum = 0; 
    for (int j = i; j >= 0; j--) 
    { 
     sum += input[i - j] * filter[j]; 
    } 
    result[i] = sum; 
} 
for (int i = filterLength; i < inputLength; i++) 
{ 
    double sum = 0; 
    for (int j = filterLength - 1; j >= 0; j--) 
    { 
     sum += input[i - j] * filter[j]; 
    } 
    result[i] = sum; 
} 
for (int i = inputLength; i < resultLength; i++) 
{ 
    double sum = 0; 
    for (int j = i - inputLength + 1; j < filterLength; j++) 
    { 
     sum += input[i - j] * filter[j]; 
    } 
    result[i] = sum; 
} 

Answer 4

आप एक विशेष आईआईआर फ़िल्टर का उपयोग कर सकते हैं। फिर उस के रूप में की तरह की प्रक्रिया:

y(n)= a1*y(n-1)+b1*y(n-2)...+a2*x(n-1)+b2*x(n-2)...... 

मुझे लगता है कि यह तेजी से है।