Fast pattern correlator and method

• US 5,239,497 A
• Filed: 10/02/1991
• Issued: 08/24/1993
• Est. Priority Date: 10/02/1991
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: McKay, Brent M., Worger, William R., Grube, Carl A.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US07/769,662
• Time in Patent Office: 692 Days
• Field of Search: 364/715.11, 364/728.03
• US Class Current: 708/422
• CPC Class Codes: G06F 17/153 Multidimensional correlation or convolution
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

A fast pattern correlator and method comprising received bitstream data blocks split into estimation blocks and correlation blocks. Correlation blocks are extracted and compared to an expected pattern using a correlation part starting location estimator and correlator. The number of bit errors resulting is compared to a predetermined maximum in a threshold comparator. Extracting the correlation blocks includes indexing consecutive estimation blocks using an estimation part correlation table and predicting consistent correlation block starting locations. The correlation blocks are correlated with the expected pattern to produce an exclusive-OR result, which, used with a bit-error table, can be used to find a number of bit errors in the correlation.

Claims

1. A fast pattern correlator for correlating bitstream data to an expected pattern comprising:

communications systems means for receiving the bitstream data in an estimation part and a correlation part;

correlation part starting location estimator means coupled to the communications systems means, the correlation part starting location estimator means for determining a starting location for the correlation part based on positions of unique blocks of the bitstream data in the estimation part;

correlator means coupled to the correlation part starting location estimator means and to the communications systems means, the correlator means for receiving the starting location from the correlation part starting location estimator means, for receiving the correlation part of the bitstream data from the communications means, and for receiving an expected pattern and producing a bit error number from the correlation part and the expected pattern; and

threshold comparator means coupled to the correlator means and to the communications systems means, the threshold comparator means for receiving the bit error number from the correlator means and producing an output to the communications system means.

2. A fast pattern correlator as claimed in claim 1 wherein the correlation part starting location estimator means comprises estimation part correlation table means coupled to the correlator means, the estimation part correlation table means for predicting the starting location for the correlation part using the estimation part, based on the positions of the unique blocks of the bitstream data.

3. A fast pattern correlator as claimed in claim 2 wherein the correlator means comprises:

exclusive-OR means coupled to the estimation part correlation table means, the exclusive-OR means for exclusive-ORing the correlation part and the expected pattern; and

bit error table means coupled to the exclusive-OR means and coupled to the threshold comparator means, the bit error table means for producing the bit error number from the correlation part and the expected pattern.

4. A method for fast correlation of bitstream data comprising the steps of:

receiving a plurality of bitstream data blocks containing the bitstream data;

splitting the plurality of bitstream data blocks into a plurality of consecutive estimation blocks and a plurality of correlation blocks;

determining a starting location for the plurality of correlation blocks based on positions of unique bitstream data blocks within the plurality of bitstream data blocks in the plurality of consecutive estimation blocks;

extracting the plurality of correlation blocks from the plurality of bitstream data blocks;

comparing the plurality of correlation blocks to an expected pattern; and

generating a number of bit errors between the plurality of correlation blocks and the expected pattern.

5. A method for fast correlation of bitstream data as claimed in claim 4, wherein the step determining a starting location for the plurality of correlation blocks comprises the steps of:

indexing an estimation block from the plurality of consecutive estimation blocks in an estimation part correlation table; and

predicting a correlation block location from the estimation part correlation table.

6. A method for fast correlation of bitstream data as claimed in claim 5, wherein the steps of indexing and predicting are repeated for the plurality of consecutive estimation blocks until a minimum number of consistent correlation block locations have been predicted.

7. A method for fast correlation of bitstream data as claimed in claim 6, wherein the step of extracting the plurality of correlation blocks further comprises the step of counting through the plurality of consecutive estimation blocks to the plurality of correlation blocks.

8. A method for fast correlation of bitstream data as claimed in claim 4, wherein the step of comparing the plurality of correlation blocks to an expected pattern comprises the steps of:

exclusive-ORing the plurality of correlation blocks and the expected pattern to produce an exclusive-OR result; and

indexing the exclusive-OR result in a bit-error table to find a number of bit errors.

9. A method for fast correlation of bitstream data as claimed in claim 8, further comprising the step of verifying that the number of bit errors is less than a predetermined value.

10. A method for fast correlation of bitstream data in a communications system comprising the steps of:

defining a plurality of bitstream data blocks containing the bitstream data such that the bitstream data in each bitstream data block is unique;

receiving the plurality of bitstream data blocks;

splitting the plurality of bitstream data blocks into a plurality of consecutive estimation blocks and a plurality of correlation blocks;

determining a starting location for the plurality of correlation blocks based on positions of the bitstream data blocks;

extracting the plurality of correlation blocks from the plurality of bitstream data blocks;

comparing the plurality of correlation blocks to an expected pattern;

generating a number of bit errors between the plurality of correlation blocks and the expected pattern; and

communicating the number of bit errors to the communications system.

11. A method for fast correlation of bitstream data in a communications system as claimed in claim 10, wherein the step of determining comprises the steps of:

indexing as estimation block from the plurality of consecutive estimation blocks in an estimation part correlation table; and

predicting a correlation block location from the estimation part correlation table.

12. A method for fast correlation of bitstream data in a communications system as claimed in claim 11, wherein the steps of indexing and predicting are repeated for the plurality of consecutive estimation blocks until a minimum number of consistent correlation block locations have been predicted.

13. A method for fast correlation of bitstream data in a communications system as claimed in claim 12, wherein the step of extracting the plurality of correlation blocks further comprises counting through the plurality of consecutive estimation blocks to the plurality of correlation blocks.

14. A method for fast correlation of bitstream data as claimed in claim 10, wherein the step of comparing the plurality of correlation blocks to an expected pattern comprises the steps of:

exclusive-ORing the plurality of correlation blocks and the expected pattern to produce an exclusive-OR result; and

indexing the exclusive-OR result in a bit-error table to find a number of bit errors.

15. A method for fast correlation of bitstream data as claimed in claim 14, further comprising the step of verifying that the number of bit errors is less than a predetermined value.

16. A correlator for comparing data to an expected pattern comprising:

means for receiving the data in an estimation part and a correlation part;

estimator means coupled to the means for receiving the data, the estimator means for determining a starting location for the correlation part based on positions of unique blocks of data;

correlator means coupled to the estimator means and to the means for receiving the data, the correlator means for receiving the starting location from the estimator means, for receiving the correlation part of the data from the means for receiving the data, and for receiving an expected pattern and producing a bit error count between the correlation part and the expected pattern; and

threshold comparator means coupled to the correlator means and to the means for receiving the data, the threshold comparator means for receiving the bit error count from the correlator means and producing an output.

17. A fast pattern correlator as claimed in claim 16 wherein the estimator means comprises estimation part correlation table means coupled to the correlator means, the estimation part correlation table means for predicting the starting location for the correlation part using the estimation part based on the positions of the unique blocks of data.

18. A fast pattern correlator as claimed in claim 17 wherein the correlator means comprises:

exclusive-OR means coupled to the estimation part correlation table means, the exclusive-OR means for exclusive-ORing the correlation part and the expected pattern; and

bit error table means coupled to the exclusive-OR means and coupled to the threshold comparator means, the bit error table means for producing the bit error count between the correlation part and the expected pattern.