快速频率有序Walsh-Hadamard变换

Question

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

---

我正在寻找一个实现,或指示如何实现,顺序排序的 Fast Walsh Hadamard变换(参见本节和此).

我稍微调整了一个在线发现的非常好的实现:

// (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

如图所示这里(从内联参考):

Walsh矩阵的行的顺序排序可以通过首先应用比特反转置换然后格雷码置换来从Hadamard矩阵的排序导出.

比特反转算法有各种实现,例如:

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

格雷码可以从这里获得:

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