Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-02-15
2004-07-20
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S410000
Reexamination Certificate
active
06766342
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of digital signal processing, and more particularly to computation of an unordered Hadamard transform.
DESCRIPTION OF THE RELATED ART
A great variety of systems may be characterized by the property that they receive a signal and perform one or more mathematical operations on the received signal. Such signal processing is common in diverse fields such as telecommunications, wireless telecommunications, cryptography, filtering, data analysis, and others. Examples of such mathematical operations include the Fourier transform, the Walsh transform, the (ordered and unordered) Hadamard transform, and the Walsh-Hadamard transform, among others.
The Walsh transform is used in many areas such as image processing and digital communications as a fast way to compute an approximation of the FFT (Fast Fourier Transform). Lately it has found applications in cryptography and in testing the randomness of pseudo-random sequences. The latter application may require the computation of the Walsh transform for large 1 dimensional data sets (sometimes of the order of a 1 billion numbers or more).
Definition of Walsh Transform
The Walsh Transform of a sequence f(x), x=0, . . . ,N−1 is defined as:
W
(
u
)
=
(
1
/
N
)
∑
x
=
0
N
-
1
f
(
x
)
∏
l
=
0
n
-
1
(
-
1
)
b
i
(
x
)
b
n
-
l
-
1
(
u
)
(
1
)
where b
i
(x) denotes the i
th
bit of x, and n=log2(N).
Similarly, the inverse Walsh transform is defined as:
f
(
x
)
=
∑
u
=
0
N
-
1
W
(
u
)
∏
l
=
0
n
-
1
(
-
1
)
b
i
(
x
)
b
n
-
l
-
1
(
u
)
(
2
)
The Hadamard Transform is similar to the Walsh transform and its transform matrix is actually a permutation of the Walsh transform matrix. The unordered Hadamard transform matrix may be constructed recursively for any length which is a power of 2, using a basic 2×2 matrix H
2
according to the relations:
H
2
=
[
+
1
+
1
+
1
-
1
]
H
4
=
[
+
H
2
+
H
2
+
H
2
-
H
2
]
H
2
N
=
[
+
H
N
+
H
N
+
H
N
-
H
N
]
(
3
)
For signal processing applications, the ordered Hadamard transform is primarily used:
H
(
u
)
=
(
1
/
N
)
∑
x
=
0
N
-
1
f
(
x
)
(
-
1
)
∑
l
=
0
N
-
1
b
l
(
x
)
b
l
(
u
)
(
4
)
f
(
x
)
=
(
1
/
N
)
∑
u
=
0
N
-
1
H
(
u
)
(
-
1
)
∑
l
=
0
N
-
1
b
l
(
x
)
b
l
(
u
)
(
5
)
It is noted that the Walsh and the ordered Hadamard transform are actually permutations of the unordered Hadamard transform, therefore once the unordered Hadamard transform has been computed, if the order of the results is important, they may be obtained by a simple reordering.
Mathematical operations such as these are typically performed on a received signal by a computer system with a single processor and memory (Von Neumann architecture). While this approach works well for small data sets (signals), the processing of much larger data sets may not be feasible due to time constraints.
To address the problems of processing large signals or data sets, algorithms have been developed for performing various signal processing operations via parallel computation systems, such as large matrix transpositions, for example. While a number of efficient methods for computation of the unordered Hadamard transform on a single CPU have been proposed, there are currently no known methods for parallel computation of the unordered Hadamard transform.
Thus, there exists a substantial need for a system and method for parallel computation of the unordered Hadamard transform.
SUMMARY OF THE INVENTION
Various embodiments of a system and method are presented for parallel computation of the unordered Hadamard transform. In the preferred embodiment, the method is performed by a computing system which includes a plurality of interconnected processors, each with a corresponding local memory. The method is presented in four stages for clarity.
In stage one, an input signal x is received and partitioned into a plurality of M
1
sub-vectors x
i
, each having length M
2
. Thus, the signal x comprises M
1
×M
2
elements or values. The sub-vectors are then distributed to the local memories of the computing system. In other words, one or more of the sub-vectors x
i
are distributed or assigned to each processor/local memory.
Each processor may then compute a Hadamard transform (order M
2
) on the one or more sub-vectors in its local memory. In the preferred embodiment, the processors compute their respective transforms in parallel. The transforms performed on the sub-vectors x
i
may generate a plurality of M
1
result sub-vectors t
i
, each having length M
2
, which compose a distributed result vector t of length M
1
×M
2
.
In the second stage of the method, elements of the result vector t may be collected with a stride of M
2
and placed into consecutively indexed locations in a second result vector u. In other words, a stride permutation may be performed on the result vector t (with stride M
2
) to generate result vector u. Said another way, the vector t may be considered or interpreted as a distributed M
1
×M
2
matrix, where each result sub-vector t
i
is viewed as a column (or row) of the matrix. A parallel matrix transposition is then performed, resulting in a transposed M
2
×M
1
matrix, i.e., a matrix comprised of M
2
result sub-vectors u
j
, each of length M
1
.
In the third stage of the method, each processor may compute a Hadamard transform (order M
1
) on the one or more result sub-vectors u
j
in its local memory. In the preferred embodiment, the processors compute their respective transforms in parallel. The transforms performed on the sub-vectors generate a plurality of M
2
result sub-vectors v
j
, each having length M
1
, which compose a distributed result vector v of length M
2
×M
1
.
In the fourth stage of the method, elements of the result vector v may be collected with a stride of M
1
and placed into consecutively indexed locations in a final result vector w. In other words, a stride permutation is performed on the result vector v (with stride M
1
) to generate result vector w. Said another way, the vector v may be considered or interpreted as a distributed M
2
×M
1
matrix, where each result sub-vector v
j
is viewed as a column (or row) of the matrix. A parallel matrix transposition is then performed, resulting in a transposed M
1
×M
2
matrix, i.e., a matrix comprised of M
1
result sub-vectors w
i
, each of length M
2
. The ordered sub-vectors w
i
compose a distributed vector w, which is the unordered Hadamard transform of the input signal x.
It should be noted that if the order of elements of the final result is unimportant, then the last stage may be omitted, because only the order of the values changes.
REFERENCES:
patent: 5357454 (1994-10-01), Dent
patent: 5583803 (1996-12-01), Matsumoto et al.
patent: 6587590 (2003-07-01), Pan
F. Arguello et al., “Parallel Architecture for Fast Transforms with Trigonometric Kernel,” IEEE Trans. on Parallel and Distributed Systems, vol. 5, No. 10, Oct. 1994, pp. 1091-1099.
Peceli, G., Feher, B.: “Digital Filters Based on Recursive Walsh-Hadamard Transformation,” IEEE Trans. on Circuits and Systems, vol. CAS-37. No. 1. 1990, pp. 150-152.
Neungsoo Park and Viktor K. Prasanna, “Cache Conscious Walsh-Hadamard Transform,” The 26th International Conference on Acoustics, Speech, and Signal Processing, (ICASSP), May 2001.
Hood Jeffrey C.
Malzahn David H.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Williams Mark S.
LandOfFree
System and method for computing and unordered Hadamard... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for computing and unordered Hadamard..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for computing and unordered Hadamard... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3236496