Communications: electrical – Digital comparator systems
Reexamination Certificate
2000-04-21
2002-05-07
Wambach, Margaret R. (Department: 2816)
Communications: electrical
Digital comparator systems
C377S080000, C377S081000
Reexamination Certificate
active
06384713
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates the recognition of patterns within digital signals and more particularly patterns within a serial bit stream.
2. Description of Related Art
In circuitry involved in transmitting packets of data such as disk drives and the Internet there is a need to identify patterns prior to starting data. One method used is to shift data into a shift register, and when the shift register is full, connect the data in the registers to a comparator to determine if the desired pattern is present. The time to make the comparison is the amount of time to shift the input data into the shift register plus the time to do the compare. As the number of bits of data to be compared increase this approach becomes less desirable.
In U.S. Pat. No. 5.459.754 (Newby et al.) a recognizer system including transmitting and receiving capability for a serial data stream uses a decision tree to recognize predetermined bit patterns to access a memory to retain previous states of comparison. When the system recognizes a final bit, a logical one is outputted to indicate the sought after pattern has been found. In U.S. Pat. No. 5.266.918 (Won et al.) a serial magnitude comparator is described in which compares input data values with an internal data value. The internal data value may be varied and the output of the comparator is a least significant bit and a most significant bit. In U.S. Pat. No. 4,524,345 (Sybel et al.) a high speed detector is described for detecting a flag character in a serial data stream. A pattern register is used to store a reference flag, pattern. As each bit in the serial data stream is received it is compared to each bit in the reference pattern using a set of comparators simultaneously.
When a pattern many bits long, needs to be detected in a serial bit stream, previous methods Would use an N-stage shift register which is long enough for the pattern needing detection. Once the shift register is filled with bits from the serial bit stream, all of the shift registers would output their bit value in parallel into a comparator circuit. The longer the pattern to be detected, the more stages that are required in the comparator, and the longer the delay before results are known. In today's world of faster and faster communications determining packet identification on the fly requires faster search and find timing to be able to keep up with the communications.
OBJECTS OF THE INVENTION
It is the object of the present invention to overcome the aforementioned problems.
It is another object of the present invention to provide a comparator containing a shift register having minimal internal delays.
It is another object of the present invention to compare bits in a serial bit stream, accomplished within shift register circuitry resulting in only three circuit delays beyond the end of a pattern included within the bit stream, and where a bit in the serial bit stream is compared to all reference bits defining the pattern in parallel.
It is an additional object of the present invention to provide a comparator/shift register with minimal internal delays.
SUMMARY OF THE INVENTION
To accomplish a compare using circuitry within a shift register, the first stage of the comparing shift register compares the first bit in the serial bit stream to the first reference bit. The second stage compares the first bit in the serial bit stream to the second reference bit, and so on until the first bit in the serial bit stream is compared to the last reference bit in the last stage of the comparing shift register. The results in each stage is combined in an AND circuit with the results in the next stage which accumulates the results from stage to stage. The results from the AND circuit in the last stage is a composite of all the compares in all the previous stages. If a compare is not found the next bit in the serial bit stream is compared to all the reference bits, one reference bit for each stage of the comparing shift register. Again the results of the compare are combined with AND circuits in each stage, and the last AND circuit provides the accumulation of the compare results from the last stage and all previous stages. In providing this comparison a total of only three circuits of delay are required beyond the delay of the normal shift register of any length, all exclusive NOR circuit for comparing, an AND circuit for accumulating compare results and a multiplexer (MUX) for choosing compare or at straight shift register.
All stages of the comparing shift register are the same except the first stage which does not have an AND circuit since there is no compare results to accumulate prior to the first stage results. A connection from the output of the output register of the previous stage is connected directly to a first input of a MUX and to a first input of an AND circuit. The AND circuit output is connected to a second input of the MUX. Again the exception is the first stage where the output of the input register is connected directly to the MUX and to an exclusive NOR (XNOR) for comparing a bit of the serial bit stream to the first reference bit. The output of the input register is connected to a first input of the XNOR in each stage of the comparing shift register so that each bit of the serial bit stream is compared to each reference bit. The reference bit to which the bits in the serial bit stream are compared is connected to the second input of the XNOR. The reference bit can be different for each comparator in the comparing shift register. The MUX in each stage is selected for shifting or for comparing, and a clock signal, CLK, opens the register so data from the previous stage can be clocked into the register.
In the compare/shift register of the present invention, an input register is clocked which connects a bit from a serial bit stream to the first stage of the comparator/shift register. In the first stage a bit in a serial bit stream is connected to a first input of a MUX and to a first input to an XNOR circuit. The bit from the serial bit stream is also connected to the first input of XNOR circuits in all subsequent stages of the comparator/shift register. The second input of the XNOR circuit in the first stage is connected to a first reference bit. The second input of an XNOR circuit in the second stage is connected to a second reference bit. In the third stage the second input to an XNOR circuit is connected to a third reference bit, and continuing in like manner until the last stage where the last reference bit is connected to the second input of an XNOR circuit in the last stage. The output of the XNOR circuit in the first stage is connected to the second input of the MUX. The MUX is controlled with a select signal that chooses the output of the XNOR for use in a compare configuration, or the serial hit stream for use as a shift register. The output of the MUX is connected to the input of the first stage output register. When a clock signal is applied to the register, the signal from the MUX is captured by the register and passed on to the second state.
In the second stage the output of the first stage register connects bits from the serial bit stream to a first input of an AND circuit and to a first input of a MUX. The output of the second stage XNOR circuit is connected to the second input of the AND circuit. The output of the AND circuit is connected to the second input of the MUX. A select signal selects either the serial bit stream to connect to the input of the second stage output register or the output of the AND circuit. When the circuitry is being used as a shift register the MUX select signal selects the serial bit stream, and when the circuitry is being used as a compare circuit the output of the AND circuit is connected to the second stage output register.
When being used as a compare circuit, the compare signal from the first stage is connected to the first input of the second stage AND circuit. The second stage compare signal is connected front the Output of the second stage XNOR circuit to the second input of th
Janofsky Eric B.
Marvell International Ltd.
Wambach Margaret R.
LandOfFree
Serial comparator does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Serial comparator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Serial comparator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2909515