From: Xiao-An Wang <xiaoanwang@lucent.com>
Subject: Re: Fast Hadamard Transform
Date: Fri, 28 Jan 2000 09:56:11 -0500
Newsgroups: sci.math.num-analysis
Summary: [missing]

Michael,

Below is the C code for FHT.  It can also be used for
IFHT, but you need to scale the result by a constant,
something like 2^m.

/* ========================================================================= */
/* Fast Hadamard Transform routine for power-of-2 points

   Caution: This program replaces the input data with the transformed
            results.  So the input data should be duplicated if to be
            preserved, before calling this routine. */
/* ========================================================================= */

void FHT(double *data, short pwr_of_2)
{
  long length, i, j, k, ie, ie_half, kp;
  double temp;

  length = 1<<pwr_of_2;
  for (i = pwr_of_2; i > 0; i--)
  {
    ie = 1<<i;
    ie_half = ie>>1;
    for (j = 0; j < ie_half; j++)
    {
      for (k = j; k < length; k += ie)
      {
        kp = k+ie_half;
        temp = *(data+k)+*(data+kp);
        *(data+kp) = *(data+k)-*(data+kp);
        *(data+k) = temp;
      }
    }
  }
}


Michael Schmidt wrote:
> 
> Hi,
> I am looking for some C-Code for a 2^m-length
> Fast Hadamard Transform (FHT) and its inverse (IFHT).
> 
> In particular, I am interested in details for the
> decoding algorithm of first order Reed-Muller codes
> R(1,m) based on the FHT.
> 
> Thanks for any hints, Michael
> 

-- 
Xiao-an Wang                          1247 S. Cedar Crest Blvd.
Wireless Systems Engineering          Room 55E-212
Lucent Technologies, Inc.             Allentown, PA 18103, U. S. A.
xiaoanwang@lucent.com                 (610)712-2814 (610)712-2790(FAX)