Parallel bit correlator

Details Parallel bit correlator Parallel bit correlator

2001-04-10

2004-05-18

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S422000

Reexamination Certificate

active

06738794

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to a parallel bit correlator for communications and Internet applications and to such a correlator useful as an Internet protocol (IP) filter.
BACKGROUND OF THE INVENTION
In communications systems such as ADSL modems, GSM systems and Internet applications devices (IADs), a series of data segments are transmitted in a stream. This stream of data includes control segments such as synchronization segments which are used by receiving devices to identify the beginning of a message packet, or for Internet protocol applications, the data stream contains address segments that define to which Internet device a particular message packet is addressed.
In either case the stream of data must be examined to see if it contains control segments, e.g., synchronization segments or address segments. These control segments may contain simply a few bits or may include a number of words each including a plurality of bits. Presently this examination is done serially. For example, if the control segments being searched for include four bits in a data stream of n bits, the system must first examine bits
1
-
4
to see if they match the sought four bit control segments. Then it examines bits
2
-
5
, then
3
-
7
and continue examining four bit sets shifted by one bit until the n-
3
th
through nth bit is examined or until a pattern match is found. This method is time consuming and processor-intensive, often requiring many instructions and iterations to find a pattern match.
BRIEF SUMMARY OF THE INVENTION
It is therefore an object of this invention to provide an improved parallel bit correlator.
It is a further object of this invention to provide such an improved parallel bit correlator which is faster and requires fewer iterations and instructions to find a pattern match.
It is a further object of this invention to provide such an improved parallel correlator which can function as an Internet protocol filter.
The invention results from the realization that a faster, more effective correlator for recognizing a predetermined bit pattern having a predefined numbers of m bits such as a synchronizing data segment or address data segment in a stream of data segments can be achieved with a parallel bit correlator that identifies successional sets of m bits in a data stream and simultaneously compares them to the predetermined bit pattern to determine whether that bit pattern (control segment) is present in the data stream.
This invention features a parallel bit correlator for recognizing a predetermined bit pattern including a predefined number m of bits in the stream of data bits including an array of logic cells and a bit match enabling circuit for enabling a number of sets of m logic cells corresponding to successive sets of m bits in a stream of data bits. A bit mask loading circuit holds a bit of the predetermined bit pattern for each logic cell and a detection circuit simultaneously compares each of the sets of m bits with the predetermined bit pattern.
In a preferred embodiment the array of logic cells may be arranged in rows and columns and the sets of m logic cells may be disposed in successive rows and columns. Each logic cell may include an AND gate each set of m logic cells may include a NOR gate responsive to the AND gate of each of the associated logic cells the enabling circuit may include a first bi-stable device for enabling the AND gate the means for storing may include a second bi-stable device for holding the value of the bit pattern and the means for detecting may include an X-OR gate responsive to the second bi-stable device and to a bit from the m bits in a stream of data bits.
This invention also features a programmable logic device using a parallel bit correlator for recognizing a predetermined bit pattern including a predefined number m of bits in a stream of data bits. There are means for identifying successive sets of m bits in a stream of data bits and means for simultaneously comparing each of the sets of m bits to the predetermined bit pattern for detecting the presence of a predetermined bit pattern in the stream of data.
In a preferred embodiment the means for identifying may include an array of logic cells and an enabling circuit for enabling a number of sets of m logic cells corresponding to the successive sets of m bits. The means for simultaneously comparing may include means for storing the predetermined bit pattern and means for detecting a match between the predetermined bit pattern and the sets of m bits. The array of logic cells may be arranged in rows and columns and the sets of m logic cells may be disposed in successive rows and columns. Each logic cell may include an AND gate, each set of m logic cells may include a NOR gate responsive to the AND gate of each of the associated logic cells the enabling circuit may include a first bi-stable device for enabling the AND gate. The means for storing may include a second bi-stable device for holding the value of a bit of the bit pattern. The means for detecting may include an X-OR gate responsive to the second bi-stable device and to a bit from the m bits in a stream of data bits.


REFERENCES:
patent: 3805037 (1974-04-01), Ellison
patent: 4722050 (1988-01-01), Lee et al.
patent: 4847801 (1989-07-01), Tong
patent: 4852098 (1989-07-01), Brechard et al.
patent: 4918638 (1990-04-01), Matsumoto et al.
patent: 5073864 (1991-12-01), Methvin et al.
patent: 5095525 (1992-03-01), Almgren et al.
patent: 5214763 (1993-05-01), Blaner et al.
patent: 5379243 (1995-01-01), Greenberger et al.
patent: 5383142 (1995-01-01), Chung
patent: 5528526 (1996-06-01), Klug et al.
patent: 5689452 (1997-11-01), Cameron
patent: 5894427 (1999-04-01), Chung
patent: 6246768 (2001-06-01), Kim
patent: 6317763 (2001-11-01), Vatinel
patent: 6384713 (2002-05-01), Yu
patent: 6389088 (2002-05-01), Blois et al.
patent: 6434662 (2002-08-01), Greene et al.
patent: 6631466 (2003-10-01), Chopra et al.

Affiliated with

Also associated with

Rating

Parallel bit correlator does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3189134