Low complexity multiple bits matched filter

Details Low complexity multiple bits matched filter Low complexity multiple bits matched filter

1999-09-17

2002-07-30

Vo, Don N. (Department: 2631)

Pulse or digital communications

Receivers

Particular pulse demodulator or detector

C714S794000

Reexamination Certificate

active

06426982

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to digital filtering of multiple bits input signals and computation of correlation or convolution values.
BACKGROUND OF THE INVENTION
In formation of correlation values from digital signals, the number of multiplications required to form a single correlation values can be as large as the number P of time slots or “chips” used to define the signal, if a conventional approach is used for computation of the correlation values. In a code division multiple access (CDMA) approach to communications, the communication symbols are multiplied or “spread” using a fixed pattern of reference symbols, referred to as pseudo-random (PN) code, and transmitted. At the receiver end, an optimal solution for detecting the received symbols, and identifying the particular code used for the spreading, employs a maximum likelihood (ML) decision rule. The ML solution for coded symbols is a matched filter or correlator, with coefficients given by the same PN code, a process known as “despreading”. Analysis of a correlation curve for the received signal and determination of the time shift and amplitude of its peak value allows two questions to be answered: (1) Is the reference pattern used to form the correlation curve likely to be the same as the spreading pattern used at the transmitter; and (2) If the answer to the first question is “yes”, what is the most likely time shift associated with the received signal.
A CDMA communication system receiver requires use of at least 3·N matched filter values, where N is the number of rake fingers used for the communications. The matched filter coefficients used for despreading account for the largest fraction of the gate count in a CDMA chip and have an associated built-in time delay for the substantial signal processing that is required. For example, in use of Code Division Multiple Access (CDMA) for signal recognition in a Global Positioning System (GPS), the number of chips used is P=1023, which requires about 1023 adders, arranged in about ten layers or more, to compute a single correlation value, and this computation is repeated for each of the approximately 1023 time shifts in order to compute a set of values for a full correlation curve. The time delay for (a minimum of) ten processing layers can be many tens of nanoseconds.
A second category where PN codes are used is in frame synchronization in digital communications. The transmitted information symbols are divided and packed into frames that also carry header and trailer information (overhead), including a preamble for synchronization of the remainder of an asynchronously transmitted frame. A PN code or “unique word” (UW) is included to assist in detecting the beginning point of the payload within a frame. The receiver searches for the UW within a frame, and an optimal solution is an ML synchronizer. Again, this requires use of a matched filter or correlator, with coefficients given by the UW used in the frame. Again, the matched filter coefficients used for pattern recognition account for the largest fraction of the gate count in frame synchronization.
What is needed is an approach that reduces the number of arithmetic operations used in formation of a correlation value used in CDMA communications, in frame synchronization and in any other signal processing procedure requiring formation of one or more correlation values. Preferably, the approach should have reduced complexity and should allow use of a much smaller gate count and have a smaller associated time delay for computation of each correlation value. Preferably, the approach should be flexible enough to accommodate a signal of any magnitude, using any signal representation format (binary, quaternary, octal, binary coded decimal, hexadecimal, etc.) and using any signal over-sampling rate.
SUMMARY OF THE INVENTION
These needs are met by the invention, which reduces the number of addition operations from M·N·R to a maximum of M·N, where M is the maximum number of orders of magnitude needed to represent a signal magnitude (e.g., M=1 for up to 10, M=2 for up to 100, etc. in decimal base), N is the number of binary digits used to represent a single “order of magnitude” (e.g., N=3 for octal, N=4 for a decimal or hexadecimal order of magnitude), and R is the over-sampling rate used for signal reception (e.g., R=2-10, or higher). The invention computes differences between two consecutive correlation values, rather than computing each correlation value separately, and this allows reduction, by a multiplicative factor of at least R, depending upon the structure of the reference or coding word, in the number of arithmetic operations for computation of a correlation value. The number of gates required is reduced by the same factor, and the associated time delay for computation of a correlation value is reduced by at least &Dgr;t(add)·log
2
(R), where &Dgr;t(add) is the time required to perform an addition of two values. Optionally, a time shift point at which the correlation curve reaches a maximum is automatically identified by this approach, and the corresponding (maximum) correlation value is quickly recovered after this time shift point has been identified.


REFERENCES:
patent: 4527278 (1985-07-01), Deconche et al.
patent: 5926786 (1999-07-01), McDonough et al.
patent: 6279133 (2001-08-01), Vafai et al.
patent: 2344493 (2000-06-01), None
Clark A P et al.: “Doppler-Shift Correction Via Correlation For a Received OPSK Signal”; IEE Proceedings I. Solid-State & Electron Devices; vol. 137, No. 6, Part 01; Dec. 1, 1990, pp. 387-394, XPOOO179891; GB, Institution of Electrical Engineers; ISSN: 0956-3776, p. 387, col. 2, line 11-20; p. 388, col. 2, last paragraph, figure 1.

Affiliated with

Also associated with

Rating

Low complexity multiple bits matched filter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Low complexity multiple bits matched filter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low complexity multiple bits matched filter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2904520