References on Interpreting Hadamard Transform results

I just did a survey of the indices of a number of really good texts
I've got laying around here, and there's scant little info regarding
Hadamard Transforms that I've been able to find.

The general idea of the HT (not to be confused with the Hartley
Transform) is pretty basic, but I'm interested in a reference that
talks a bit about interpreting the results.   So far I'm at a bit of a
loss as to what practical use the thing has or what the results mean.
I've found treatments that explain what it is (which is simple
enough), but very little on practical applications.

Any ideas amont the collective wisdom out there?

Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

Eric Jacobsen wrote:
> I just did a survey of the indices of a number of really good texts
> I've got laying around here, and there's scant little info regarding
> Hadamard Transforms that I've been able to find.
> 
> The general idea of the HT (not to be confused with the Hartley
> Transform) is pretty basic, but I'm interested in a reference that
> talks a bit about interpreting the results.   So far I'm at a bit of a
> loss as to what practical use the thing has or what the results mean.
> I've found treatments that explain what it is (which is simple
> enough), but very little on practical applications.
> 
> Any ideas amont the collective wisdom out there?
> 
> Eric Jacobsen
> Minister of Algorithms, Intel Corp.
> My opinions may not be Intel's opinions.
> http://www.ericjacobsen.org

The discrete Hadamard transform of an image is a two-valued (it uses 
Walsh functions) hologram of the image. I never figured out what 
wavelength recreates the image. But then, isn't a 2-D Fourier transform 
a diffraction pattern?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

eric.jacobsen@ieee.org (Eric Jacobsen) writes:

> I just did a survey of the indices of a number of really good texts
> I've got laying around here, and there's scant little info regarding
> Hadamard Transforms that I've been able to find.
> 
> The general idea of the HT (not to be confused with the Hartley
> Transform) is pretty basic, but I'm interested in a reference that
> talks a bit about interpreting the results.   So far I'm at a bit of a
> loss as to what practical use the thing has or what the results mean.
> I've found treatments that explain what it is (which is simple
> enough), but very little on practical applications.
> 
> Any ideas amont the collective wisdom out there?

Hi Eric,

Even Eric Weisstein's "CRC Concise Encyclopedia of Mathematics," which
usually has a prolific amount of information and references on such topics,
simply states,

  A Fast Fourier Transform-like algorithm which produces a hologram of an
  image.

There were no references.

I could also find no information on the subject in either Poularikas'
"The Transforms and Applications Handbook" or Bracewell's "The Fourier
Transform and its Applications."

Good luck!
-- 
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

"Randy Yates" <randy.yates@sonyericsson.com> wrote in message 
news:xxpsm3ba8in.fsf@usrts005.corpusers.net...
> eric.jacobsen@ieee.org (Eric Jacobsen) writes:
>
>> I just did a survey of the indices of a number of really good texts
>> I've got laying around here, and there's scant little info regarding
>> Hadamard Transforms that I've been able to find.
>>
>> The general idea of the HT (not to be confused with the Hartley
>> Transform) is pretty basic, but I'm interested in a reference that
>> talks a bit about interpreting the results.   So far I'm at a bit of a
>> loss as to what practical use the thing has or what the results mean.
>> I've found treatments that explain what it is (which is simple
>> enough), but very little on practical applications.
>>
>> Any ideas amont the collective wisdom out there?
>
> Hi Eric,
>
> Even Eric Weisstein's "CRC Concise Encyclopedia of Mathematics," which
> usually has a prolific amount of information and references on such 
> topics,
> simply states,
>
>  A Fast Fourier Transform-like algorithm which produces a hologram of an
>  image.
>
> There were no references.
>
> I could also find no information on the subject in either Poularikas'
> "The Transforms and Applications Handbook" or Bracewell's "The Fourier
> Transform and its Applications."
>
> Good luck!
> -- 
> Randy Yates
> Sony Ericsson Mobile Communications
> Research Triangle Park, NC, USA
> randy.yates@sonyericsson.com, 919-472-1124
Hi Eric,
    The only thing I can remember ever using it for was in deconstructing a 
set of direct sequence spread spectrum codes into different nutually 
orthogonal sub-channels for a synchronous spread-spectrum multiple access 
scheme.
Best of Luck - Mike

"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message 
news:42278b35.322140484@news.west.cox.net...
>I just did a survey of the indices of a number of really good texts
> I've got laying around here, and there's scant little info regarding
> Hadamard Transforms that I've been able to find.
>
> The general idea of the HT (not to be confused with the Hartley
> Transform) is pretty basic, but I'm interested in a reference that
> talks a bit about interpreting the results.   So far I'm at a bit of a
> loss as to what practical use the thing has or what the results mean.
> I've found treatments that explain what it is (which is simple
> enough), but very little on practical applications.

Suppose that we have a sequence x[k] where k ranges from 0
to 2^m - 1.  We can regard this as a function that maps the set
{0, 1, ... , 2^m - 1} to real (or complex) numbers.  Then the DFT
supports cyclic convolution: the DFT of the cyclic convolution
sequence z[n] where

    z[n] = sum from k = 0 to 2^m - 1 of x[k].y[n-k]

with indices taken modulo 2^m is (ignoring multiplicative constants)
the term-by-term product of the DFTs of x[k] and y[k].  But, we
could also look at the integers {0, 1, ... , 2^m - 1} as m-bit binary
vectors that comprise the field GF(2^m), so that x[a] can also be
thought of as a function that maps the elements of GF(2^m) to real
(or complex) numbers.  Note that a is an m-bit vector regarded
as an element of GF(2^m).  Then, the Hadamard transform supports
what is sometimes called the Poisson convolution:  the Hadamard
transform of

    w[b] = sum over all a in GF(2^m) x[a].y[b-a]

is (ignoring multiplicative constants) the term-by-term product of the
Hadamard transforms of x[a] and y[a].  Notice that b-a = b.XOR.a
since addition and subtraction are the same operation in GF(2^m).

What is the Hadamard transform useful for?  Well, I have on my
bookshelf a whole book titled Hadamard Transform Optics (by
N. J. A. Sloane and M. Harwit, Academic Press 1979) which
shows how the Hadamard transform is used to design better
imaging spectrometers.  I would suspect that the book is no longer
in print....

One particular application of more direct interest to comp.dsp denizens
is the following.  Suppose we have a maximum-length linear feedback
shift register sequence of period 2^m - 1 and wish to compute the
periodic crosscorrelation between this sequence and some other sequence
x[k] of period 2^m -1.  No big deal: take the DFTs, multiply term by
term (conjugating one term), and then the inverse DFT.  Of course, this
works better if we have a good FFT algorithm for length 2^m-1.
Alternatively, if we *permute* the sequence x[k] appropriately, then
the Hadamard transform of the permuted sequence is, with appropriate
multiplicative constants and re-ordering (bit shuffling), the 
crosscorrelation
between the maximum length sequence and x[k].  Is it worth it?  Sure.
there is a fast Hadamard transform algorithm that uses only m.2^m
additions/subtractions and *no* multiplications which saves a lot of
computation as compared to three DFTs, fast or not.  This idea was used
in the Mariner 9 mission's communications systems about 35 years ago.
Some details (and circuit diagrams of the Green machine that implemented
the fast Hadamard transform) algorithm are in Chapter 14 of the well-known
MacWilliams and Sloane text on error-control codes.

Hope this helps.

On Fri, 4 Mar 2005 13:40:03 -0600, "Dilip V. Sarwate"
<sarwate@YouEyeYouSee.edu> wrote:

>One particular application of more direct interest to comp.dsp denizens
>is the following.  Suppose we have a maximum-length linear feedback
>shift register sequence of period 2^m - 1 and wish to compute the
>periodic crosscorrelation between this sequence and some other sequence
>x[k] of period 2^m -1.  No big deal: take the DFTs, multiply term by
>term (conjugating one term), and then the inverse DFT.  Of course, this
>works better if we have a good FFT algorithm for length 2^m-1.
>Alternatively, if we *permute* the sequence x[k] appropriately, then
>the Hadamard transform of the permuted sequence is, with appropriate
>multiplicative constants and re-ordering (bit shuffling), the 
>crosscorrelation
>between the maximum length sequence and x[k].  Is it worth it?  Sure.
>there is a fast Hadamard transform algorithm that uses only m.2^m
>additions/subtractions and *no* multiplications which saves a lot of
>computation as compared to three DFTs, fast or not.  This idea was used
>in the Mariner 9 mission's communications systems about 35 years ago.
>Some details (and circuit diagrams of the Green machine that implemented
>the fast Hadamard transform) algorithm are in Chapter 14 of the well-known
>MacWilliams and Sloane text on error-control codes.
>
>Hope this helps.

Dilip,

Thanks for the note.

I can easily see how enough scrambling of the HT basis functions would
provide a crosscorrelation of an MLLF sequence with an input sequence
since the kernels of the HT (and most transforms) are dot products.
That seems to me to be just redefining a series of carefully arranged
dot products as a transform, which can easily turn into a case of
semantic argument about what is or is not a transform.

This assumes I've understood you correctly, though, which may not be
the case.  I'm just imagining the permuting and bit shuffling you were
describing could perhaps also be accomplished by fiddling with the
basis function.  In any case, I can easily see the computational
advantage, though.

For the Mariner 9 case, then, I'm assuming it was used for either
synchronization (the correlation function again) or despreading?

Cheers,

Eric
Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message 
news:4228c479.58641843@news.west.cox.net...
> On Fri, 4 Mar 2005 13:40:03 -0600, "Dilip V. Sarwate"
> <sarwate@YouEyeYouSee.edu> wrote:
>
>>One particular application of more direct interest to comp.dsp denizens
>>is the following. ......
>>Alternatively, if we *permute* the sequence x[k] appropriately, then
>>the Hadamard transform of the permuted sequence is, with appropriate
>>multiplicative constants and re-ordering (bit shuffling), the 
>>crosscorrelation
>>between the maximum length sequence and x[k].  Is it worth it?  Sure.
>>there is a fast Hadamard transform algorithm that uses only m.2^m
>>additions/subtractions and *no* multiplications which saves a lot of
>>computation as compared to three DFTs, fast or not.  This idea was used
>>in the Mariner 9 mission's communications systems about 35 years ago.
>>Some details (and circuit diagrams of the Green machine that implemented
>>the fast Hadamard transform) algorithm are in Chapter 14 of the well-known
>>MacWilliams and Sloane text on error-control codes.
>
> Thanks for the note.
>
> I can easily see how enough scrambling of the HT basis functions would
> provide a crosscorrelation of an MLLF sequence with an input sequence
> since the kernels of the HT (and most transforms) are dot products.
> That seems to me to be just redefining a series of carefully arranged
> dot products as a transform, which can easily turn into a case of
> semantic argument about what is or is not a transform.

> This assumes I've understood you correctly, though, which may not be
> the case.  I'm just imagining the permuting and bit shuffling you were
> describing could perhaps also be accomplished by fiddling with the
> basis function.  In any case, I can easily see the computational
> advantage, though.


It is possible to permute the basis functions (rows of the Hadamard matrix)
instead of the sequence x[k], but, after permutation, the Hadamard matrix
may not support the *fast* algorithm, which depends on the structure of the
matrix being of the form
             H_m-1    H_m-1
H_m =
              H_m-1  -H_m-1

There is still a computational advantage of sorts with a permuted matrix
though, since we need (2^m)^2 additions/subtractions to grind things
out (and no multiplications) as compared to 3 (or 2) FFTs.

> For the Mariner 9 case, then, I'm assuming it was used for either
> synchronization (the correlation function again) or despreading?

The Mariner 9 code was essentially a (31,6) PN sequence code
(the m-sequence and its shifts and complements).  Crosscorrelating
the received signal with the m-sequence was effectively computing the
autocorrelation function of the m-sequence (a thumbtack).  The machine
used the fast Hadamard transform idea to compute all crosscorrelation
values simultaneously, and the location of the peak value in the
transform gave 5 data bits and the sign of the peak the 6th data bit.

Was it spreading? or was it coding? or was it 31-ary orthogonal
modulation?  Let's not get into semantic discussions.... 

On Fri, 4 Mar 2005 17:37:30 -0600, "Dilip V. Sarwate"
<sarwate@YouEyeYouSee.edu> wrote:

>The Mariner 9 code was essentially a (31,6) PN sequence code
>(the m-sequence and its shifts and complements).  Crosscorrelating
>the received signal with the m-sequence was effectively computing the
>autocorrelation function of the m-sequence (a thumbtack).  The machine
>used the fast Hadamard transform idea to compute all crosscorrelation
>values simultaneously, and the location of the peak value in the
>transform gave 5 data bits and the sign of the peak the 6th data bit.
>
>Was it spreading? or was it coding? or was it 31-ary orthogonal
>modulation?  Let's not get into semantic discussions.... 

Dilip,

Thanks again, this makes sense and does answer my question.

I agree on the semantics, too.  ;)

Cheers,

Eric
Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

eric.jacobsen@ieee.org (Eric Jacobsen) wrote in message news:<422a02f6.140174187@news.west.cox.net>...
> On Fri, 4 Mar 2005 17:37:30 -0600, "Dilip V. Sarwate"
> <sarwate@YouEyeYouSee.edu> wrote:
> 
> >The Mariner 9 code was essentially a (31,6) PN sequence code
> >(the m-sequence and its shifts and complements).  Crosscorrelating

> >the received signal with the m-sequence was effectively computing the
> >autocorrelation function of the m-sequence (a thumbtack).  The machine
> >used the fast Hadamard transform idea to compute all crosscorrelation
> >values simultaneously, and the location of the peak value in the
> >transform gave 5 data bits and the sign of the peak the 6th data bit.
> >
> >Was it spreading? or was it coding? or was it 31-ary orthogonal
> >modulation?  Let's not get into semantic discussions.... 
> 
> Dilip,
> 
> Thanks again, this makes sense and does answer my question.
> 
> I agree on the semantics, too.  ;)
> 
> Cheers,
> 
> Eric
> Eric Jacobsen
> Minister of Algorithms, Intel Corp.
> My opinions may not be Intel's opinions.
> http://www.ericjacobsen.org

What did you think of my method of generating Gaussian noise with the
Hadamard transform? I think the main use will be for optimisation and
neural nets.
I would call my efforts persistence research (ie 1984 to 2004) done in
complete isolation from any sources of information on the Transform (I
only got the internet in 2003), certainly it is not explained by any
great ability.  Hope it's useful.  I published a couple of articles in
Servo Magazine (Feb 2004, Oct 2004) about it.  More for the money that
anything else.  It's only what was on my web page anyway.
Sean O'Connor

On 04 Mar 2005 07:41:04 -0500, Randy Yates
<randy.yates@sonyericsson.com> wrote:

>Hi Eric,
>
>Even Eric Weisstein's "CRC Concise Encyclopedia of Mathematics," which
>usually has a prolific amount of information and references on such topics,
>simply states,
>
>  A Fast Fourier Transform-like algorithm which produces a hologram of an
>  image.
>
>There were no references.
>
>I could also find no information on the subject in either Poularikas'
>"The Transforms and Applications Handbook" or Bracewell's "The Fourier
>Transform and its Applications."
>
>Good luck!
>-- 
>Randy Yates

Randy,

I checked the indices in nearly everything I have, including
Abramowitz and Stegun as well as the CRC handbook.   I figure between
those two if it ain't in there it's close to not existing, but neither
had a reference.

Fortunately there are groups like this to which we can turn, though.
;)

Cheers,

Eric


Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org