c++ - 快速序列有序 Walsh-Hadamard 变换

Question

编辑 您可以在 Github 上查看我的实现:https://github.com/Sheljohn/WalshHadamard

---

我正在寻找sequence-ordered Fast Walsh Hadamard 变换的实现或有关如何实现的指示(参见 this 和 this)。

我稍微改编了一个非常好的实现，发现 online :

// (a,b) -> (a+b,a-b) without overflow
void rotate( long& a, long& b )
{
    static long t;
    t = a;
    a = a + b;
    b = t - b;
}

// Integer log2
long ilog2( long x )
{
    long l2 = 0;
    for (; x; x >>=1) ++l2;
    return l2;
}

/**
 * Fast Walsh-Hadamard transform
 */
void fwht( std::vector<long>& data )
{
    const long l2 = ilog2(data.size()) - 1;

    for (long i = 0; i < l2; ++i)
    {
        for (long j = 0; j < (1 << l2); j += 1 << (i+1))
        for (long k = 0; k < (1 << i ); ++k)
            rotate( data[j + k], data[j + k + (1<<i)] );
    }
}

但它不按顺序计算 WHT(隐式使用自然 Hadamard 矩阵)。请注意，在上面的代码中(如果您尝试的话)，数据的大小需要是 2 的幂。

我的问题是:这个实现是否有一个简单的改编来提供顺序排序的 FWHT？

一个可能的解决方案是编写一个小函数来动态计算 Hn(n 阶 Hadamard 矩阵)的元素，计算过零的数量，并创建行的排名，但我想知道是否有是一种更聪明的方法。在此先感谢您的任何输入!干杯

Answer 1

如图所示here (从 your reference 内链接):

The sequency ordering of the rows of the Walsh matrix can be derived from the ordering of the Hadamard matrix by first applying the bit-reversal permutation and then the Gray code permutation.

位反转算法有多种实现方式，例如:

// Bit-reversal
// adapted from http://www.idi.ntnu.no/~elster/pubs/elster-bit-rev-1989.pdf
void bitrev(int t, std::vector<long>& c)
{
  long n = 1<<t;
  long L = 1;
  c[0]  = 0;
  for (int q=0; q<t; ++q)
  {
    n /= 2;
    for (long j=0; j<L; ++j)
    {
      c[L+j] = c[j] + n;
    }
    L *= 2;
  }
}

格雷码可从here获取:

/*
    The purpose of this function is to convert an unsigned
    binary number to reflected binary Gray code.

    The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
    return (num >> 1) ^ num;
}

这些可以结合起来产生最终的排列:

// Compute a permutation of size 2^order 
// to reorder the Fast Walsh-Hadamard transform's output 
// into the Walsh-ordered (sequency-ordered)
void sequency_permutation(long order, std::vector<long>& p)
{
  long n = 1<<order;

  std::vector<long> tmp(n);
  bitrev(order, tmp);
  p.resize(n);
  for (long i=0; i<n; ++i)
  {
    p[i] = tmp[binaryToGray(i)];
  }
}

剩下要做的就是将排列应用于正常的沃尔什-阿达玛变换输出。

void permuted_fwht(std::vector<long>& data, const std::vector<long>& permutation)
{
  std::vector<long> tmp = data;
  fwht(tmp);

  for (long i=0; i<data.size(); ++i)
  {
    data[i] = tmp[permutation[i]];
  }
}

请注意，对于给定的数据大小，排列是固定的，因此只需计算一次(假设您正在处理多个数据 block )。因此，将它们放在一起你会得到如下内容:

  std::vector<long> p;

  const long order = ilog2(data_block_size) - 1;
  sequency_permutation(order, p);

  permuted_fwht( data_block_1, p);
  permuted_fwht( data_block_2, p);
  //...