卷积：在卷积的最后一个元素是永远正确的

Question

我写一个C++实现卷积用下面的函数

vector<double> Conv(vector<double> a, vector<double> b) 
{ 
    // a and b are the same size 
    int n = a.size() * 2 - 1; 
    vector<double> c; 
    for (int i = 0; i < n; i++) { 
     c.push_back(0); 
     for (int j = 0; j <= i; j++) { 
      c[i] += a[j] * b[i - j]; 
     } 
    } 
    return c; 
} 

的问题是，所有的卷积值是除了最后一个是正确的。我使用我在网上找到的卷积计算器进行了检查。

示例输入：

矢量A = < 0.961232，0.00685581，0.905588，0.914544>

矢量B = < 0.719889，0.675933，0.0571511，0.148412>

返回向量= < 0.691981 ，0.654664,0.711493,1.41354,0.670944,0.186668,0.6653971>

预计= < 0.691980343 248，0.65466385166109，0.71149237410793，1.413537159886891，0.67094330437252，0.1866673218544，0.135729304128>

在返回的矢量彩车的精度是好的，但最后的结果不匹配。

Answer 1

根据其他社区成员的评论，我相信你的算法不太正确。而不是调试，我决定通过谷歌找到一个正确的。

这两个环节上给我的线索：

• Convolution of Vectors (Mlmode)

• Convolution of two vectors in R

我使用这些链接，使C++中的小样本：

#include <iostream> 
#include <vector> 

template <typename VALUE> 
void convolve(
    std::vector<VALUE> &c, // out 
    const std::vector<VALUE> &a, const std::vector<VALUE> &b) // in 
{ 
    const size_t nA = a.size(), nB = b.size(); 
    const size_t nC = nA + nB - 1; 
    c.clear(); c.resize(nC, (VALUE)0); 
    for (size_t i = 0; i < nA; ++i) { 
    for (size_t j = 0; j < nB; ++j) { 
     c[i + j] += a[i] * b[j]; 
    } 
    } 
} 

template <typename VALUE> 
inline std::vector<VALUE> convolve(
    const std::vector<VALUE> &a, const std::vector<VALUE> &b) 
{ 
    std::vector<VALUE> c; convolve(c, a, b); return c; 
} 

template <typename VALUE> 
void print(
    std::ostream &out, const char *label, const std::vector<VALUE> &vec) 
{ 
    out << label << '[' << vec.size() << "]: {"; 
    const char *sep = " "; 
    for (const VALUE &v : vec) { 
    out << sep << v; 
    sep = ", "; 
    } 
    out << " }" << std::endl; 
} 

int main() 
{ 
    // test 1 
    // http://www.omatrix.com/manual/mlmode_conv.htm 
    { std::cout << "Test 1:" << std::endl; 
    const std::vector<int> a = { 
     1, 1, 1, 1, 1 
    }; 
    std::vector<int> c; 
    convolve(c, a, a); 
    print(std::cout, "a", a); 
    std::cout << "Convolution of a and a:" << std::endl; 
    print(std::cout, "c", c); 
    } 
    // test 2 
    { std::cout << "Test 2:" << std::endl; 
    const std::vector<float> a = { 
     0.961232f, 0.00685581f, 0.905588f, 0.914544f 
    }; 
    const std::vector<float> b = { 
     0.719889f, 0.675933f, 0.0571511f, 0.148412f 
    }; 
    std::vector<float> c; 
    convolve(c, a, b); 
    print(std::cout, "a", a); 
    print(std::cout, "b", b); 
    std::cout << "Convolution of a and b:" << std::endl; 
    print(std::cout, "c", c); 
    } 
    // done 
    return 0; 
} 

注：

1. 要复制一个向量（因为它是在return完成）可能是大载体昂贵。因此，我通过参考提供了结果向量。 （对于那些，谁喜欢return我写了一个inline包装，但我没有使用它。）

2. 相反的vector::push_back()，我用vector::resize()。一次进行分配通常比较便宜（尤其是如果从开始就知道大小的话）。 vector::resize()也用于初始化。为了丢弃可能的先前值，以前完成了vector::clear()。 （vector::clear()是一种便宜的方法，因为它不会释放存储空间，而只是重置内部元素数量。）

3. 我制作了convolve模板。这使得使用更加灵活。

予编译和克测试它++中的cygwin在Windows 10（64位）：

$ g++ -std=c++11 -o vector-convolution vector-convolution.cc 

$ ./vector-convolution.exe 
Test 1: 
a[5]: { 1, 1, 1, 1, 1 } 
Convolution of a and a: 
c[9]: { 1, 2, 3, 4, 5, 4, 3, 2, 1 } 
Test 2: 
a[4]: { 0.961232, 0.00685581, 0.905588, 0.914544 } 
b[4]: { 0.719889, 0.675933, 0.0571511, 0.148412 } 
Convolution of a and b: 
c[7]: { 0.69198, 0.654664, 0.711492, 1.41354, 0.670943, 0.186667, 0.135729 } 

$ 

这看起来相当不错：

• 根据试验1的匹配的预期值到Convolution of Vectors (Mlmode)。

• 测试2与您的问题的预期值相匹配。