Serial comparator

• US 6,384,713 B1
• Filed: 04/21/2000
• Issued: 05/07/2002
• Est. Priority Date: 04/21/2000
• Status: Expired due to Term

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Yu, Daxiao
• Primary Examiner(s): Wambach, Margaret R.
• Application Number:
  US09/556,758
• Time in Patent Office: 746 Days
• Field of Search: 340/146.2, 377/80, 377/81
• US Class Current: 340/146.2
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

In this invention compare circuitry is integrated into a serial shift register which can detect a bit pattern of any length with only the delay of three circuits being added to the shift of the last bit in the bit pattern. The circuitry is connected to operate either is a shift register or as a comparator for an N element bit pattern. Between adjacent registers in the shift register is a MUX used to select compare or shift register operation. An exclusive NOR circuit performs the compare between bits of the serial bit stream and reference bits of the pattern to be protected. An AND circuit accumulates the compare of a particular stage with the compare with the preceding stage. In the last stage the AND circuit provide an accumulated compare result of the preceding number of bit equaling in length the length of the bit pattern for which the compare is being performed.

Claims

1. A selectable serial comparator/shift register, in response to a selection signal, shifts serial input data or compares the serial input data with a first predetermined value and a second predetermined value, said comparator comprising:

a) a first stage, in response to the selection signal, to selectively compare at first portion of the input serial data with the first predetermined value, or shift the input serial data; and

b) a second stage to receive a result from the first stage and, in response to the selection signal, to selectively, compare a second portion of the input serial data with the second predetermined value and to provide a comparison result of the serial data with the first and second predetermined values, or shift the input serial data.

2. A selectable serial comparator/shift register according to claim 1, further comprising N stages arranged in a serial manner, in response to the selection signal, selectively shift the input serial data or compare the serial input data with N predetermined values, wherein N is a positive integer greater than two.

3. A selectable serial comparator/shift register according to claim 1, wherein said first stage comprises a first logic unit to receive the input serial data and the first predetermined value, a first selector responsive to the selection signal and a first register to receive an output of said first logic unit or the input serial data in accordance with said first selector.

4. A selectable serial comparator/shift register according to claim 3, wherein said first logic unit comprises a first exclusive NOR logic circuit.

5. A selectable serial comparator/shift register according to claim 1, wherein said second stage comprises a second logic unit to receive the serial data, the second predetermined value and the result from said first stage, a second selector responsive to the selection signal, and a second register to receive an output of said second logic unit or the result from said first stage in accordance with said second selector.

6. A selectable serial comparator/shift register according to claim 5, wherein said second logic unit comprises a second exclusive NOR logic circuit to receive the serial data and the second predetermined value, and an AND logic circuit to receive an output of said second exclusive NOR logic circuit and the said first stage.

7. A selectable serial comparator/shift register according to claim 4, wherein said second stage comprises a second logic unit to receive the serial data, the second predetermined value and the result from said first stage, a second selector responsive to the selection signal, and a second register to receive an output of said second logic unit or the result from said first stage in accordance with said second selector.

8. A selectable serial comparator/shift register according to claim 7, wherein said second logic unit comprises a second exclusive NOR logic circuit to receive the serial data and the second predetermined value, and an AND logic circuit to receive an output of said second exclusive NOR logic circuit and the output of said first register.

9. A selectable serial comparing/shift register means, in response to a selection signal, shifts serial input data or compares the serial input data with a first predetermined value and a second predetermined value, said comparing means comprising:

a) a first circuit means, in response to the selection signal, for selectively comparing a first portion of the input serial data with the first predetermined value, or shifting the input serial data; and

b) a second circuit means for receiving a result from the first circuit means and, in response to the selection signal, for selectively comparing a second portion of the input serial data with the second predetermined value and to provide a comparison result of the serial data with the first and second predetermined values, or shifting the input serial data.

10. A selectable serial comparator/shifting register according to claim 9, further comprising N circuit means arranged in a serial manner in response to the selection signal for selectively shifting the input serial data or comparing the serial input data with N predetermined values, wherein N is a positive integer greater than two.

11. A selectable serial comparator/shift register according to claim 9, wherein said first circuit means comprises a first logic means for receiving the input serial data and the first predetermined value, a first selector means responsive to the selection signal and a first register means for storing an output of said first logic means or the input serial data in accordance with said first selector means.

12. A selectable serial comparator/shift register according to claim 11, wherein said first logic means comprises a first exclusive NOR means.

13. A selectable serial comparator/shift register according to claim 9, wherein said second circuit means comprises a second logic means for receiving the serial data, the second predetermined value and the result from said first circuit means, a second selector means responsive to the selection signal, and a second register means for storing an output of said second logic means or the result from said first circuit means in accordance with said second selector means.

14. A selectable serial comparator/shift register according to claim 13, wherein said second logic means comprises a second exclusive NOR means for logically exclusively NORing the serial data and the second predetermined value, and an AND means for logically ANDing an output of said second exclusive NOR means and the said first circuit means.

15. A selectable serial comparator/shift register according to claim 12, wherein said second circuit means comprises a second logic means for receiving the serial data, the second predetermined value and the result from said first circuit means, a second selector means responsive to the selection signal, and a second register means for storing an output of said second logic means or the result from said first circuit means in accordance with said second selector.

16. A selectable serial comparator/shift register according to claim 15, wherein said second logic means comprises a second exclusive NOR means for logically exclusively NORing the serial data and the second predetermined value, and an AND means for logically ANDing an output of said second exclusive NOR means and the output of said first register means.

17. A method, in response to a selection signal, of shifting serial input data or of comparing the serial input data with a first predetermined value and a second predetermined value, said method comprising the steps of:

a) selectively, in response to the selection signal,

a1) comparing a first portion of the input serial data with the first predetermined value, or

a2) shifting the input serial data; and

b) selectively, response to the selection signal,

b1) comparing a second portion of the input serial data with the second predetermined value and to provide a comparison result of the serial data with the first and second predetermined values, or

b2) shifting the input serial data.

18. A method according to claim 17, further comprising the steps of repeating step (b) N times with N predetermined values, wherein N is a positive integer greater than two.

19. A method according to claim 17, wherein step (a) further comprises the steps of:

c) performing logical operations on the input serial data and the first predetermined value,

d) storing an output of step (c) or the input serial data in accordance with the selection signal.

20. A method according to claim 19, wherein step (c) comprises the step of logically exclusively NORing the input data and the first predetermined data.

21. A method according to claim 17, wherein step (b) comprises the steps of:

c) performing logical operations on the serial data, the second predetermined value and the result from step (a),

d) storing an output of said step (c) or the result from step (a) in accordance with sail selection signal.

22. A method according to claim 21, wherein step (c) comprises the steps of:

e) logically exclusively NORing the serial data and the second predetermined value, and

f) logically ANDing all output of step (e) and the result of step (a).

23. A method according to claim 20, wherein step (b) comprises the steps of:

g) performing logical operations on the serial data, the second predetermined value and the result from said step (d)

h) storing an output of step (g) or the result from step (d) in accordance with the selection signal.

24. A method according to claim 23, wherein step (g) comprises the steps of:

i) logically exclusively NORing the serial data and the second predetermined value, and

j) logically ANDing an output of step (i) and the output of step (d).