Browse Prior Art Database

Efficient Hadamard Transformations

IP.com Disclosure Number: IPCOM000109378D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 1 page(s) / 24K

Publishing Venue

IBM

Related People

Coppersmith, D: AUTHOR [+3]

Abstract

An efficient implementation of Hadamard transforms for architectures with fused multiply/adds is presented.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 100% of the total text.

Efficient Hadamard Transformations

       An efficient implementation of Hadamard transforms for
architectures with fused multiply/adds is presented.

      The Hadamard transform on 4 points computes the product of an
arbitrary vector by the matrix

                            (Image Omitted)

The following algorithm performs this computation with 7 operations,
where an operation is any ternary instruction of the form + a + bc on
the input variables a, b, c.  The input data is the vector (x0 x1 x2
x3) and the output vector is (y0 y1 y2 y3).
           1. z0 = x1 + x2
           2. z1 = z0 + x3
           3. z2 = x0 - z1
           4. y0 = x0 + z1
           5. y1 = z2 + 2x2
           6. y2 = z2 - 2x1
           7. y3 = z2 - 2x3

      For n a power of 2, the n-point Hadamard transform involves the
product by the matrix which is defined recursively by the formula
                 Hn = H(n/2)   H2,
where denotes the tensor product and