c++ - 快速序列排序的Walsh-Hadamard变换

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

我正在寻找序列排序的快速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矩阵)，计算零交叉的数量并创建行的排名，但是我想知道是否有更聪明的方法道路。预先感谢您的任何投入!干杯

最佳答案

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



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

// 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)];
  }
}

剩下要做的就是将置换应用于普通的Walsh-Hadamard变换输出。

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]];
  }
}

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

  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);
  //...