Reduced complexity fast hadamard transform

An apparatus for performing a reduced complexity radix-4 fast Hadamard transform, comprising:

• first calculating means for calculating a quantity {tilde over (w)}=w0+w1+w2−w3 wherein w0, w1, w2, w3 comprise first, second, third and fourth inputs of said radix-4 fast Hadamard transform, respectively;
• and
• second calculating means for calculating a first fast Hadamard transform output in accordance with the equation s0={tilde over (w)}+2w3;
• third calculating means for calculating a second fast Hadamard transform output in accordance with the equation s1={tilde over (w)}−2w1;
• fourth calculating means for calculating a third fast Hadamard transform output in accordance with the equation s2={tilde over (w)}−2w2;
• and
• fifth calculating means for calculating a fourth fast Hadamard transform output in accordance with the equation s3={tilde over (w)}+2w0.

A method of performing an even order fast Hadamard transform, said method comprising the steps of:

• cascading in series one or more radix-4 fast Hadamard transform stages, each radix-4 fast Hadamard transform stage comprising one or more radix-4 fast Hadamard transform modules;
• and
• each said radix-4 fast Hadamard transform module adapted to perform the steps of:
• calculating a quantity {tilde over (w)}=w0+w1+w2−w3 wherein w0, w1, w3 comprise a first input, a second input, a third input and a fourth input of said radix-4 fast Hadamard transform, respectively;
• and
• calculating the quantities s0={tilde over (w)}+2w3, s1={tilde over (w)}−2w2, s2={tilde over (w)}−2w2, s3=−{tilde over (w)}+2w0, wherein s0, s1, s2, s3 comprise a first output, a second output, a third output and a fourth output of said radix-4 fast Hadamard transform, respectively.

A method of performing a fast Hadamard transform H2N of order M=2N wherein N is an odd positive integer greater than or equal to 3, said method comprising the steps of:

• cascading in series one or more radix-4 fast Hadamard transform stages, each radix-4 fast Hadamard transform stage comprising one or more radix-4 fast Hadamard transform modules;
• adding a radix-2 fast Hadamard transform stage to said cascaded series of radix-4 fast Hadamard transforms;
• each said radix-4 fast Hadamard transform module adapted to perform the steps of:
• calculating a quantity {tilde over (w)}=w0+w1+w2−w3 wherein w0, w1, w2, w3 comprise a first input, a second input, a third input and a fourth input of said radix-4 fast Hadamard transform, respectively;
• and
• calculating the quantities s0={tilde over (w)}+2w3, s1={tilde over (w)}−2w1, s2={tilde over (w)}−2w2, s3=−{tilde over (w)}+2w0, wherein s0, s1, s2, s3 comprise a first output, a second output, a third output and a fourth output of said radix-4 fast Hadamard transform, respectively.

A computer program product for use in a computing device, said computer program product comprising:

• a computer usable medium having computer readable program code means embodied in said medium for performing a fast Hadamard transform H2N of order M=2N wherein N is a positive integer greater than 2, said computer program product comprising:
• computer readable program code means for performing 2N−2 fast Hadamard transforms on an input so as to generate a first intermediate result;
• computer readable program code means for permuting said first intermediate result to generate a first permuted result;
• computer readable program code means for performing four H2N−2 fast Hadamard transforms on said first permuted result to generate a second intermediate result;
• and
• computer readable program code means for permuting said second intermediate result to generate a fast Hadamard transform output.

An apparatus for implementing a fast Hadamard transform H2N of order M=2N wherein N is a positive integer greater than 2, comprising:

• a first stage adapted to perform 2N−2 H4 fast Hadamard transforms on an input so as to generate a first intermediate result;
• a first permutation stage adapted to permute said first intermediate result to generate a first permuted result;
• a second stage adapted to perform four H2N−2 fast Hadamard transforms on said first permuted result so as to generate a second intermediate result;
• and
• a second permutation state adapted to permute said second intermediate result to generate a fast Hadamard transform output.

A computer program product for use in a computing device, said computer program product comprising:

• a computer usable medium having computer readable program code means embodied in said medium far performing a radix-4 fast Hadamard transform, said computer program product comprising:
• computer readable program code means for calculating a quantity {tilde over (w)}=w0+w1+w2−w3 wherein w0, w1, w2, W3 comprise a first input, a second input, a third input and a fourth input of said radix-4 fast Hadamard transform, respectively;
• and
• computer readable program code means for calculating the quantities s0={tilde over (w)}+2w3, s1={tilde over (w)}−2w1, s2={tilde over (w)}−2w2, s3=−{tilde over (w)}+2w0, wherein s0, s1, s2, s3 comprise a first output, a second output, a third output and a fourth output of said radix-4 fast Hadamard transform, respectively.