US 4,734,676 AGranted

Method and device for detecting a particular bit pattern in a serial train of bits

AssigneeInternational Business Machines Corporation

InventorsSimon Huon, Victor Spagnol

Life of this patent

Estimating the term…

Loading patent…

Abstract

Memory 60 contains a decision table which is a replica of the particular N-bit pattern to be detected. When a bit is received over line 12, a table lookup operation is performed to determine whether the entry at the address indicated by address counter 34 contains a bit that matches the received bit. If so, the content of the address counter is incremented by one and the device waits for another bit to be received over line 12. If the bit in the entry does not match the received bit, then, if the address indicated by the counter is zero, the count of the counter is maintained at zero and the device waits for another bit to be received; or, if the address is different from zero, the counter is reset to zero and the bit present on line 12 is again presented to the table in order, this time, to be compared with the bit in the entry at address zero. The pattern is detected when the address contained in the counter is equal to N and when the last bit in the pattern matches the bit with which it is compared.

Claims2

Dependent claims

A device for detecting a particular pattern of N bits in a serial train of binary coded bits, said device comprises:

an address generator;
first storage means containing a first table of N entries, the n.sup.th of which comprises an information item denoting a match or a mismatch depending on whether the n.sup.th bit of the bit pattern to be detected has a first or a second binary value;
second storage means containing a second table of N entries, the n.sup.th of which comprises an information item denoting a match or a mismatch depending on whether the n.sup.th bit of the bit pattern to be detected has said second binary value or not;
means for selecting an entry in said first or second storage means according to whether the bit being examined in the train of bits has said first or second binary value, the address of said entry being indicated by the address generator;
means for incrementing by one the content of said address generator when the addressed entry contains an information item denoting a match;
means for resetting to zero the content of said address generator when the addressed entry contains an information item denoting a mismatch, and for addressing the first entry in said first or second storage means according to whether the bit being examined has said first or second binary value, if the content of said address generator is different from zero;
and
means for indicating that said bit pattern has been detected when the content of said address generator is N and the addressed entry contains an information item denoting a match.

5 more elements

A method of detecting a unique pattern of N sequential binary bits in a serial train of bits, said method comprises the steps of:

establishing an address pointer value which can be controlled to assume any one of N values;
establishing a first table which includes N addressable locations each of which in sequence corresponds to one of the N bits in the unique pattern of N sequential bits and storing in sequence in each said location a first information item indicating a match when the corresponding sequential bit in the train assumes a first value and a second information item indicating a mismatch when the corresponding sequential bit in the train assumes a second value;
establishing a second table which includes N addressable locations each of which in sequence corresponds to the N bits in the unique pattern of N sequential bits and storing in sequence in each said location a first information item indicating a match when the corresponding sequential bit in the train assumes said second value and a second information item indicating a mismatch when the corresponding sequential bit in the train assumes said first value;
receiving and examining in sequence the individual bit contained in the train of bits, and
if the bit being examined has said first value accessing the information item in the first table under control of said address pointer value, or
if the bit being examined has said second value accessing the information item in the second table under control of said address pointer value;
incrementing by one the address pointer value if the information item accessed indicates a match and repeating the above sequence of steps for the next bit in the train of bits or resetting the address pointer to its lowest value if the information item accessed indicates a mismatch and thereafter repeating the above sequence of steps for the current bit in the train of bits whenever the address pointer value prior to resetting was at a value greater than the lowest value or for the next bit when the address pointer was at its lowest value;
and
indicating that the unique pattern of N sequential binary bits has been detected when the address pointer value attains its maximum value and the information item then being accessed under control of maximum pointer value indicates a match.

6 more elements

Dependencies are inferred from the claim text.