Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-03-12
2001-10-30
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06311202
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to wireless communications, and more particularly to a Fast Hadamard Transform arrangement that is employed to detect and correct errors occurring during the transmission of Walsh codewords.
BACKGROUND OF THE INVENTION
FIG. 1
illustrates a typical wireless telecommunications system. Switching center
201
is connected to a plurality of base stations, such as those depicted by base stations
203
-
1
through
203
-
5
. Additionally, switching center
201
is connected to local or long-distance telephone offices (not shown). Wireless terminals, such as those depicted by terminals
201
-
1
through
201
-
3
, communicate with a base station which is located in the same pre-determined geographic area, or cell, as itself. For instance, wireless terminals
201
-
1
and
201
-
2
are located in cell A, therefore communicate with base station
203
-
1
, which is located in and services cell A.
In order for wireless terminal
201
-
1
to communicate, it sends a signal via radio waves to base station
203
-
1
; base station
203
-
1
relays the received signal to switching center
201
; and, switching center
201
, according to instructions supplied as part of the signal, relays the signal elsewhere. If the desired destination of the signal is another wireless terminal, then switching center
201
relays the signal to a base station located in the same cell as the wireless terminal intended to receive the signal, and the base station transmits the signal via radio waves to the wireless terminal. Likewise, if the desired destination of the signal is a wireline terminal, such as wireline terminal
207
, then switching center
201
relays the signal to the desired destination via wirelines to the local or long-distance networks.
When information is transmitted via a digital wireless telecommunications channel, errors can occur in the transmission due to noise, interference and distortion. Various methods are utilized in order to detect and correct errors that occur during transmission.
FIG. 2
illustrates some of the components which are typically employed by a digital wireless telecommunications channel in order to detect and correct transmission errors. Information source
12
sends a digital message to encoder
14
. The digital message can consist of digitized voice signals, data, etc. Encoder
14
encodes the digital message and feeds it to transmitter
16
, which modulates the encoded message onto a carrier and transmits it via radio waves to receiver
18
. Receiver
18
receives the message, which may or may not have been corrupted during transmission. Receiver
18
demodulates the received message and feeds it to decoder
20
. Decoder
20
decodes the received message and feeds it to information destination
22
. Preferably, the digital message fed to information destination
22
is identical to the original digital message which was sent by information source
12
.
In order for information destination
22
to receive the same message that was sent by information source
12
, encoder
14
and decoder
20
operate to detect and correct errors due to corruption during transmission. Generally, encoder
14
partitions the digital message signal into fixed-length blocks and replaces each block with a codeword uniquely associated with it. The codeword is transmitted instead of the fixed-length block, and the received message is compared to a known set of legitimate codewords in order to determine whether it was corrupted during transmission. One such error detection/correction scheme involves the generation and transmission of Walsh codes.
According to the Walsh code system, encoder
14
partitions a message from information source
12
into blocks having n bits each. Each of the original n-bit blocks of information to be transmitted is converted into a codeword, unique to the block of information, having 2″ Walsh chips. Thus, a 3-bit block of data would have a Walsh codeword with 2
3
, or 8, Walsh chips. Instead of modulating and transmitting the original 3-bit block of data, transmitter 16 modulates and transmits the Walsh codeword to receiver
18
. When the Walsh codeword is received by receiver
18
, it is demodulated and fed to decoder
20
. Decoder
20
compares the received Walsh codeword, which has potentially been corrupted during transmission, to a set of legitimate Walsh codewords. If the received Walsh codeword matches one of the codewords in the set of legitimate Walsh codewords, then it is presumed that the received codeword was not corrupted during transmission, and can be decoded back into the 3-bit block of information which was originally intended to be transmitted.
If, however, the received Walsh codeword does not match one of the codewords in the set of legitimate Walsh codewords, then the received codeword was corrupted during transmission, and the receiver must determine which of the legitimate Walsh codewords was originally transmitted. In the prior art, a Fast Hadamard Transform (hereinafter “FHT”) algorithm is used to calculate, for each received codeword, the likelihood that a received codeword is a particular legitimate Walsh codeword. The FHT algorithm expresses this likelihood as a correlation coefficient. Thus, a received codeword has 2
n
correlation coefficients associated with it, one corresponding to each of the 2
n
legitimate Walsh codewords. The legitimate Walsh codeword having the largest correlation coefficient is the legitimate codeword most likely to have been transmitted. Thus, the FHT algorithm assigns to a received codeword the legitimate Walsh codeword having the largest correlation coefficient. The “winning” Walsh codeword is then decoded back into a 3-bit block of information and fed to information destination
206
.
Although many techniques for implementing Fast Hadamard Transforms are well-known in the prior art, these techniques are generally too slow and require too much hardware.
Thus, there exists a need for an FHT engine that is fast, compact and efficient.
SUMMARY OF THE INVENTION
The present invention, in accordance with one embodiment, is a Fast Hadamard Transform apparatus. The FHT apparatus is employed by a wireless telecommunication system for detecting and correcting errors that occur during the transmission of signal blocks, in accordance with the FHT algorithm. The FHT apparatus of the present invention requires a smaller amount of hardware and memory compared to prior art systems to store signals while performing the sum and difference operations required by the FHT algorithm.
According to one embodiment, the wireless communication system employs the FHT apparatus to receive signal blocks that have been encoded according to, for example, Walsh codewords. Preferably, correlation coefficients are generated by the FHT apparatus corresponding to legitimate codewords that may have been transmitted. For instance, an n-bit block of data desired to be transmitted via a wireless telecommunication channel is converted into a 2
n
-chip Walsh codeword prior to transmission. The 2
n
-chip Walsh codeword is transmitted instead of the n-bit block of data, and is received as chip pairs by a first transform stage of the FHT apparatus.
Advantageously, the FHT apparatus comprises a plurality of transform stages. Each transform stage of the apparatus performs a series of operations on the input signals that it receives. Each subsequent transform stage receives input signals from the stage preceding it in a number of clock cycles which is one half the number of clock cycles which the preceding stage received its input signals. Preferably, this is accomplished by progressively decreasing the memory storage capacity of first, second and third memory units (explained further below) employed in each stage by a factor of two.
Each stage of the apparatus comprises an adder and a subtractor. The adder and the subtractor receive input signal pairs within each received signal block (i.e.—one input signal is received by the adder and the other is received by the subtractor) so as to generate
Lucent Technologies - Inc.
Malzahn David H.
LandOfFree
Hardware efficient fast hadamard transform engine does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hardware efficient fast hadamard transform engine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware efficient fast hadamard transform engine will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2610069