Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-04-25
2001-05-22
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06237014
ABSTRACT:
BACKGROUND OF THE INVENTION
1) Field of the Invention
This invention pertains to the field of digital signal processing and, more particularly, to digital correlation.
2) Background of the Related Art
Correlators have been widely used in signal processing to measure the degree of correspondence between a data sequence and a predetermined pattern or reference sequence. In the case of one-dimensional digital signal processing, a correlation value y representing the correspondence between a sequence of data samples, d
i
, and a sequence of reference values, r
i
, is found by:
y
=
∑
i
=
1
n
(
r
i
·
d
i
)
Correlation is used in a number of applications including speech cognition, pattern recognition of printed matter in check-processing equipment, and communication system synchronization.
Correlators have been used in many communication systems to perform receiver clock synchronization. In that case, to facilitate synchronization, a communication transmitter and a communication receiver are each furnished with a reference sequence having a predetermined pattern. The communication transmitter transmits the reference sequence to facilitate synchronization of the receiver clock to the transmitted signal. The reference sequence is chosen to have good autocorrelation properties, e.g., a well-defined correlation peak and relatively low sidelobes.
FIG. 1
shows a communication receiver correlator operating with a correlation reference sequence, which is eight (8) bits in length, to produce a correlation peak at the time when the received data sequence matches the reference sequence. In the example of
FIG. 1
, it is assumed that each data sample is represented as an 8-bit two's-complement number having a value in the range of ±127. At each clock period, the last eight samples of input data d
i
(i=1,8) are multiplied sample by sample against the reference sequence bits r
i
(i=1,8) to produce a correlation value y. That is, y may have a maximum value of +1016 and a minimum value of −1016. The correlation value y is compared against a correlation threshold, y
TH
, and whenever y exceeds y
TH
, a correlation match is declared indicating that the correlation sequence has been received and the receiver is thereby synchronized to the transmitter.
Correlators have also been used in direct sequence spread-spectrum communication systems to detect received signals that have been spread for transmission using binary sequences called spreading codes. In this case, the transmitter and receiver are each furnished with a reference sequence having a predetermined pattern corresponding to the spreading code.
The transmitter spreads the original data signal to be transmitted with the spreading code to produce a spread spectrum signal. At the receiver, a despreading correlator recovers the original data signal by correlating the received signal against the reference sequence corresponding to the spreading code.
Correlators have been built using dedicated digital signal processors. However, these devices are limited by their processing speed. Thus, they may not be practical for high speed correlation, especially for very long reference sequences.
FIG. 2
is a block diagram of a conventional programmable digital correlator
100
of length n according to the prior art which may be used for receiver synchronization or for despreading a spread spectrum signal. The correlator
100
comprises a data delay line
101
, reference sequence storage
103
, multiplier stage
105
, and an adder tree
107
. The operation of this prior art correlator
100
will now be described.
During an initialization process, a reference sequence of reference values r
i
(i=1,n) is stored into the reference sequence storage
103
. In the example correlator of
FIG. 1
, it is assumed that each reference sequence value r
i
is represented as a 1-bit binary value. On each reference clock cycle, a new reference sequence value r
i
is supplied to the reference sequence storage
103
in the correlator
100
. The reference sequence storage
103
is comprised of an n-stage reference shift register further comprised of n 1-bit reference sequence registers
104
.
A received data sequence of data samples d
i
(i=1,n) is supplied to the correlator
100
for correlation with the reference sequence. In the general case, each data sample d
i
is represented as an m-bit binary value. In the example correlator of
FIG. 2
, m=8. On each data clock cycle, a new data sample d
i
is supplied to the data delay line
101
in the correlator
100
.
The data delay line
101
is configured as an n-stage data sequence shift-register. On each data clock cycle, a new data sample d
1
is shifted byte-wise into first data Register-1
102
of the data delay line. The data sample d
2
which had been stored in the first data Register-1 on the previous data clock cycle, is shifted into the second data Register-2. Similarly the data samples d
i
in all other data registers are each shifted one register to the right. The oldest data sample, d
n+1
, stored in the last data register Register-n exits the data delay line
101
and is discarded.
Correlation of the data sequence d
i
(i=1,n) with the reference sequence r
i
(i=1,n) is performed by first multiplying each data sample d
i
by a corresponding reference value r
i
in the multiplier stage
105
. The multiplier stage
105
is comprised of n multipliers
106
. The n multipliers
106
produce n correlation multiplication products, y
i
=d
i
*r
i
(i=1,n), each represented as an m-bit binary value, in this example m=8.
The n m-bit correlation multiplication products y
i
are then supplied to n/2 first stage adders
108
of the adder tree
107
. Each first stage adder
108
adds two of the m-bit correlation multiplication products y
i
to produce an (m+1)-bit intermediate correlation sum z
i
. The n/2 first stage adders
108
produce n/2 intermediate correlation sums z
i
which are supplied to n/4 second stage adders in the adder tree
106
. This process repeats until final stage adder
109
of the adder tree produces a single (m+log
2
(n))-bit correlation value y. Thus, the adder tree consists of log
2
(n) stages with a total number of n−1 adders.
An example of a prior art conventional correlator is the HSP45256, manufactured by Harris Corporation.
The prior art conventional programmable digital correlator
100
requires a large amount of circuitry. For example, consider a correlator of length n=128 for correlating 128 data samples represented as 8-bit numbers with a reference sequence of 128 1-bit numbers. The 128-stage data delay line requires one flip-flop for each bit to be stored. For the 8-bit data samples, the data delay line requires 8*128=1024 flip-flops. The reference sequence storage requires an additional 128 flip-flops, one for each bit in the reference sequence.
When designing with application specific integrated circuits (ASICs), the amount of logic is measured in gates, which are understood to be equivalent 2-input NAND gates. All other gates and flip-flops are converted to the required number of equivalent 2-input NAND gates. For example, a flip-flop is equivalent to at least six 2-input NAND gates.
The data delay line's 1024 flip-flops represent a logic requirement of 1024×6 gates=6144 equivalent 2-input NAND gates, and the reference storage requires 128×6 gates=768 equivalent 2-input NAND gates.
Each multiplier in the correlator must multiply a signed 8-bit data sample by a reference value, which is typically a 1-bit value. The 1-bit reference value can be an encoded value, with a value of ‘1’ indicating ‘−1’, and a value of ‘0’ indicating ‘+1’.
The result of the multiply is therefore either the same as the sample data (if the reference value is ‘0’), or it is minus the sample data value (if the reference value is ‘1’). Each multiplier can therefore be implemented as 8 XOR gates, and an 8 bit incrementor.
Decker David George
Freidin Philip Manuel
Krasner Norman Franklin
GE Capital Spacenet Services, Inc.
Jones Volentine, L.L.C.
Mai Tan V.
LandOfFree
Correlator method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Correlator method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Correlator method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452646