Orthogonal transform processor

Details Orthogonal transform processor Orthogonal transform processor

2000-11-09

2004-05-11

Ton, Dang (Department: 2661)

Multiplex communications

Generalized orthogonal or special mathematical techniques

Particular set of orthogonal functions

C370S210000, C375S142000, C375S240070, C375S240180, C708S400000

Reexamination Certificate

active

06735167

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an orthogonal transform processor, and more particularly, to an orthogonal transform processor which employs a fast orthogonal transform algorithm to process a series of source data values.
2. Description of the Related Art
Digital signal processing applications often involve orthogonal transform algorithms such as the Fast Fourier Transform (FFT) and Fast Hadamard Transform (FHT). Particularly, FHT is frequently used in the technical fields of image processing and mobile communication because it can be implemented with simple hardware.
FIG. 12
shows how to generate Hadamard matrices. As seen from
FIG. 12
, Hadamard matrices are symmetric matrices consisting of ones and zeros. Their row vectors, referred to as the “Walsh codes,” are orthogonal to every other row vector. The generation process shown in
FIG. 12
may be repeated in the same manner to yield higher-order matrices, e.g., 8×8, 16×16, 32×32, 64×64, and so on.
As just stated above, Walsh codes are orthogonal to each other. A code sequence having such an orthogonal nature is useful in modulating, or encoding, transmission signals. This technique is known as the “orthogonal modulation.” When the code sequence consists of M orthogonal codewords, the modulation is called the “M-ary orthogonal modulation.
FIG. 13
is a diagram which shows an example of an M-ary orthogonal modulator using the Walsh code set of M=4. It is a common convention to designate each individual Walsh code by a unique number that starts with zero, such as 0, 1, 2, and 3, denoting the zeroth, first, second, and third Walsh codes, respectively. In the example modulator configuration of
FIG. 13
, these four Walsh codes are subjected to a selector SW
1
being controlled by source data to be modulated. The selector SW
1
chooses a Walsh code corresponding to each symbol of the source data sequence and sends it out as the encoded data. A source data symbol “01,” for example, causes the selector SW
1
to choose and output the Walsh code
1
, namely “0101.”
The inherent orthogonality of Walsh codes is also used to reconstruct the original data from a modulated data sequence that was produced as above. That is, the data is decoded by computing its correlation with each Walsh code.
FIG. 14
is a diagram which shows an example of a Walsh decoder. As seen from
FIG. 14
, the decoder comprises four correlators
1
-
1
to
1
-
4
and a maximum value selector
2
. The correlators
1
-
1
to
1
-
4
calculate correlation factors between the modulated source data signal and four different Walsh codes concurrently. The maximum value selector
2
selects one of the calculated correlation factors that exhibits the greatest value.
FIG. 15
provides a typical structure of the correlator
1
-
4
for Walsh code
3
(“0110”). This illustrated correlator
1
-
4
comprises flip-flops (FFs)
10
-
1
to
10
-
4
, multipliers
11
-
1
to
11
-
4
, and an adder
12
. The flip-flops
10
-
1
to
10
-
4
function as delay elements, giving a one-clock delay to their respective input signals. The multipliers
11
-
1
to
11
-
4
calculate the product of each bit of the Walsh code
3
and their input data supplied from the corresponding flip-flops
10
-
1
to
10
-
4
. In this multiplication processing, the bit values “0” and “1” are interpreted as bipolar levels “+1” and “−1,” respectively. The resultant products are then summed up by the adder
12
. In the example of
FIG. 15
, the correlator outputs a maximum correlation value when the input data sequence is “0110” (i.e., “+1, −1, −1, +1”).
The above function of Walsh correlators explains the principle of the decoder of FIG.
14
. That is, the decoder reproduces the original data by calculating the correlations between input data and different Walsh codes, finding which correlator indicates the highest correlation, and then outputting the corresponding symbol.
Referring again to
FIG. 15
, the illustrated correlator employs multipliers to determine whether the input data sequence coincides with a specific orthogonal codeword. Multipliers, however, generally needs a complex circuit structure, which results in an increased scale of hardware. This problem in correlative operations can be avoided by using adders and subtractors, in place of multipliers. FHT operators are known as an example of such correlators. In the FHT computation, correlation can be calculated with simple adders and subtractors, or butterfly operators, which are the fundamental components of Fast Fourier Transform.
FIG.
16
(A) is a signal flow diagram which shows the FHT computation based on 2×2 Hadamard matrix (i.e., Walsh code length=2). This diagram represents the summation and subtraction of two input signals w
0
and w
1
The resultant sum and difference are referred to herein as Walsh
0
and Walsh
1
, respectively.
w
0
+
w
1
=Walsh
0
  (1)
w
0
−
w
1
=Walsh
1
  (2)
Actually, the above 2×2 FHT operation is realized by a combination of an adder
20
-
1
and a subtractor
20
-
2
, as shown in FIG.
16
(B).
When the Walsh code
1
itself (w
0
=+1, w
1
=−1) is given as an input, the FHT operator of FIG.
16
(B) will output the following results (see FIG.
17
).
Walsh
0
=
w
0
+
w
1
=(+1)+(−1)=0  (3)
Walsh
1
=
w
0
−
w
1
=(+1)−(−1)=2  (4)
That is, the FHT operator outputs an auto-correlation value of “2” at its lower output terminal corresponding to the Walsh code
1
. Similarly, the FHT operator will produce the following correlation values when the Walsh code
0
itself (w
0
=+1, w
1
=+1) is given.
Walsh
0
=
w
0
+
w
1
=(+1)+(+1)=2  (5)
Walsh
1
=
w
0
−
w
1
=(+1)−(+1)=0  (6)
In this second example, the illustrated FHT operator outputs an auto-correlation value of “2” at its upper output terminal corresponding to the Walsh code
0
.
FIG. 18
is a signal flow diagram showing the FHT computation based on 4×4 Hadamard matrix (i.e., Walsh code length=4). Consider, for example, that the Walsh code
3
itself (w
0
=+1, w
1
=−1, w
2
=−1, w
3
=+1) is given as an input. In this case, the result will be as follows:
walsh0
=
 
⁢
w0
+
w1
+
w2
+
w3
=
 
⁢
(
+
1
)
+
(
-
1
)
+
(
-
1
)
+
(
+
1
)
=
0
(
7
)
walsh1
=
 
⁢
w0
-
w1
+
w2
-
w3
=
 
⁢
(
+
1
)
-
(
-
1
)
+
(
-
1
)
-
(
+
1
)
=
0
(
8
)
walsh2
=
 
⁢
w0
+
w1
-
w2
-
w3
=
 
⁢
(
+
1
)
+
(
-
1
)
-
(
-
1
)
-
(
+
1
)
=
0
(
9
)
walsh3
=
 
⁢
w0
-
w1
-
w2
-
w3
=
 
⁢
(
+
1
)
-
(
-
1
)
-
(
-
1
)
+
(
+
1
)
=
4
(
10
)
That is, the illustrated operator outputs an auto-correlation value of “4” at its output terminal corresponding to the Walsh code
3
.
The above-described FHT computation may be implemented directly in hardware, using adders and subtractors. This simple approach, however, is not realistic particularly when the code length is long, because of the intolerable propagation delay times resulting from its cascaded stages of adders and subtractors. To solve this problem, most implementations use the techniques of pipelined processing.
FIG. 19
is a timing diagram of typical pipelined processing when the code length is four. This processing can be realized by a circuit shown in FIG.
20
. The circuit comprises flip-flops (FFs)
50
to
56
, butterfly operators
57
and
58
, rearrangement switches
59
and
60
, a selector
61
, and an operation timing generator
62
.
The flip-flops
50
to
56
delay their input data by a predetermined time. The butterfly operators
57
and
58
perform a butterfly operation with the supplied data. The rearrangement switches
59
and
60
change the order of the supplied data as required. The selector
61
selec

Affiliated with

Also associated with

Rating

Orthogonal transform processor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Orthogonal transform processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Orthogonal transform processor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3201393