US 6,766,342 B2 · System and method for computing and unordered Hadamard transform

Abstract

A system and method for parallel computation of the unordered Hadamard transform. The computing system includes a plurality of interconnected processors and corresponding local memories. An input signal x is received, partitioned into M1 sub-vectors xi of length M2, and distributed to the local memories. Each processor computer a Hadamard transform (order M2) on the sub-vectors in its local memory (in parallel), generating M1 result sub-vectors ti of length M2, which compose a vector t of length M1×M2. A stride permutation (stride M2) is performed on t generating vector u. Each processor computes a Hadamard transform (order M1) on the sub-vectors uj in its local memory (in parallel), generating M1 result sub-vectors vj of length M2, which compose a vector v of length M2×M1. A stride permutation is performed on v (stride M1) generating result vector w, which is the Hadamard transform of the input signal x.

Claims46

Dependent claims

A system for performing parallel computation of a Hadamard transform on a signal x, the system comprising:

a plurality of interconnected processors;
a plurality of memory mediums, wherein each of the memory mediums is coupled to a corresponding one of the plurality of interconnected processors;
an input for receiving the signal x;
wherein the plurality of interconnected processors are each operable to execute at least one Hadamard transform on respective portions of the signal x, thereby producing respective Hadamard transform result portions, and wherein the plurality of interconnected processors are operable to process in a parallel fashion to produce said respective Hadamard transform result portions;
wherein the plurality of interconnected processors are operable to generate the Hadamard transform of the signal x based on the respective Hadamard transform result portions;
and
wherein the Hadamard transform of the signal x is useable in analyzing the signal x.

4 more elements

A system for performing parallel computation of a Hadamard transform of a signal x, the system comprising:

a plurality of interconnected processors;
a plurality of memory mediums, wherein each of the memory mediums is coupled to a corresponding one of the plurality of interconnected processors;
an input for receiving the signal x;
wherein each of the plurality of memory mediums stores at least a respective portion of a parallel Hadamard transform software program for execution by the corresponding one of the plurality of interconnected processors;
wherein each of the plurality of interconnected processors is operable to execute said respective said-portions portion of the parallel Hadamard transform software program to compute the Hadamard transform of the signal x, and wherein the plurality of interconnected processors are operable to process in a parallel fashion to produce said Hadamard transform of the signal x, thereby producing a Hadamard transform result;
and
wherein the Hadamard transform result is useable in analyzing the signal x.

4 more elements

A system for performing parallel computation of a Hadamard transform of a signal x, the system comprising:

a plurality of interconnected processors;
a plurality of memory mediums, wherein each of the memory mediums is coupled to a corresponding one of the plurality of interconnected processors;
an input for receiving the signal x;
wherein each of the plurality of memory mediums stores at least a respective portion of a parallel Hadamard transform software program for execution by the corresponding one of the plurality of interconnected processors;
wherein each of the plurality of memory mediums stores at least a portion of the signal x;
wherein each of the plurality of interconnected processors is operable to execute said respective portion of the parallel Hadamard transform software program to compute the Hadamard transform of the signal x, and wherein the plurality of interconnected processors are operable to process in a parallel fashion to produce said Hadamard transform of the signal x;
and
wherein the Hadamard transform of the signal x is useable in analyzing the signal x.

5 more elements

A system for performing parallel computation of a Hadamard transform on a signal x, the system comprising:

a plurality of interconnected processors;
a plurality of memory mediums, wherein each of the memory mediums is coupled to a corresponding one of the plurality of interconnected processors;
and
an input for receiving the signal x;
wherein the plurality of interconnected processors are each operable to execute at least one Hadamard transform on one or more respective sub-vectors of the signal x, thereby producing a plurality of first sub-vectors ti, comprising a vector t, and wherein the plurality of interconnected processors are operable to process in a parallel fashion to produce the plurality of first sub-vectors ti;
wherein the plurality of interconnected processors are operable to permute data from the plurality of first sub-vectors ti to generate a plurality of second sub-vectors uj, comprising a vector u;
wherein the plurality of interconnected processors are each operable to execute at least one Hadamard transform on sub-vectors uj, thereby producing a plurality of third sub-vectors vj, comprising a vector v, and wherein the plurality of interconnected processors are operable to process in a parallel fashion to produce the plurality of third sub-vectors vj;
and
wherein values of said vector v comprise unordered values of the Hadamard transform of signal x.

6 more elements

Dependencies are inferred from the claim text.

System and method for computing and unordered Hadamard transform

Life of this patent

System and method for computing and unordered Hadamard transform

Life of this patent

Abstract

Claims46