Method and apparatus for extracting a predetermined pattern from a serial bit stream

Abstract

An embedded framing bit pattern in a serial bit stream is located by combining the last bit to arrive of the serial bit stream with a predetermined number of prior bits of the serial bit stream which are spaced apart by the pitch of the bits of the framing bit pattern, and this combination of the bits is tested to determine if the combination matches part of the framing bit pattern. If a match does not occur, then the bits which were combined together are changed to a bit pattern that will not result in a match when these bits (except for the eldest bit which is disregarded) is combined again with a new bit of the serial bit stream, no matter what the logic state of the new bit. In this manner all of the bits, as they arrive and are combined and tested, will eventually be changed except the bits which are part of the framing bit pattern.

What is claimed is: 
     
       1. A method for locating the position of a framing pattern in a serial bit stream.Iadd., .Iaddend.wherein each of said framing bits is separated by P-1 bits of data.Iadd., .Iaddend.comprising the steps of: (a) after the arrival of {(M-1)×P}+1 bits of said serial bit stream at an input terminal.Iadd., .Iaddend.taking M samples P 1 , P 2 , . . . P M  of said serial bit stream.Iadd., .Iaddend.where P 1  is the last bit of said serial bit stream to have arrived at said input terminal, P 2  is the bit of said serial bit stream which arrived P bits prior to said P 1  bit, and P M  is the bit which arrived (M-1)×P bits prior to said P 1  bit;   (b) determining if the bit pattern sequence P M  . . . P 1  matches any M-bit sequence of the bit pattern formed by concatenating two of said framing patterns;   (c) if a match does not occur, changing said P 1 , P 2 , . . . P M-1  bit sample to a bit pattern such that the combination of the logic bit X, where logic bit X can be either a logical 1 or a logical 0, and the changed P 1 , P 2 , . . . P M-1  bits would not match any sequence of the bit pattern formed by concatenating two of said framing patterns, and if a match does occur, leaving the bits of said serial bit stream unaffected;   (d) upon arrival of the next bit of said serial bit stream at said input terminal.Iadd., .Iaddend.taking M samples P 1 , P 2 , . . . P M , where P 1  is the last bit of said serial bit stream to have arrived at said input terminal, P 2  is the bit of said serial bit stream which arrived P bits prior to said P 1  bit unless said P 2  bit, when it was in the P 1  position, was previously changed by the process of step (c), and P M  is the bit which arrived M-.Badd.1×P bits prior to said P 1  bit unless said P M  bit, when it was in the P 1 , P 2 , . . . P M-2  or P M-1  position, was previously changed by the process of step (c);   (e) repeating steps (b) through (d) while counting the number of matches which occur during the arrival of each successive block of said serial bit stream, each block equal to P bits in length; and   (f) repeating steps (a) through (e) if said count at the end of any of said blocks is zero, and having identified the position of said framing bits if said count at the end of any said blocks is one.   
     
     
       2. A method for locating the position of the framing pattern in a T1 serial bit stream encoded according to the ESF standard comprising the steps of: (a) upon the arrival of a bit of said serial bit stream at an input terminal.Iadd., .Iaddend.taking 4 samples P 1 , P 2 , P 3  and P 4  of said serial bit stream.Iadd., .Iaddend.where P 1  is the last bit to have arrived, P 2  is the bit of said serial bit stream which arrived 772 bits prior to said P 1  bit, P 3  is the bit of said serial bit stream which arrived 772 bits prior to said P 2  bit, and P 4  is the bit which arrived 772 bits prior to said P 3  bit;   (b) determining if the bit pattern sequence P 4 , P 3 , P 2  and P 1  matches the any of the bit sequences, 0010, 0101, 1011, 0110, 1100, and 1001;   (c) if a match does not occur, then changing said P 1 , P 2 , and P 3  bits to a first logic state, and if a match does occur, leaving the bits of said serial bit stream unaffected;   (d) upon arrival of the next bit of said serial bit stream at said input terminal, taking 4 samples P 1 , P 2 , P 3  and P 4 , where P 1  is the last bit of said serial bit stream to have arrived at said input terminal,   P 2  is the bit of said serial bit stream which arrived P bits prior to said P 1  bit unless said P 2  bit, when it was in the P 1  position, was previously changed by the process of step (c),   P 3  is the bit which arrived .Badd.1,544 bits prior to said P 1  bit unless said P 3  bit, when it was in the P 1  or P 2  position, was previously changed by the process of step (c), and   P 4  is the bit which arrived 2,316 bits prior to said P 1  bit unless said P 4  bit, when it was in the P 1 , P 2 , or P 3  position, was previously changed by the process of step (c);     (e) repeating steps (b) through (d) while counting the number of matches which occur during the arrival of successive blocks of said serial bit stream, each block equal to 772 bits in length; and   (f) repeating steps (a) through (e) if said count at the end of any of said blocks is zero, and having identified the position of said framing bits if said count at the end of any of said blocks is one.   
     
     
       3. Apparatus for locating the position of a bit framing pattern in a serial bit stream wherein each of said framing bits is separated by P-1 bits of data comprising: (a) a serial data input terminal for receiving said serial bit stream;   (b) K logic-storage means, each having an input terminal and an output terminal where said input terminal of said first logic-storage means is coupled to said serial data input terminal, said input terminal of said second logic-storage means is coupled to said output terminal of said first logic-storage means, and said rest of said remaining K logic-storage means are similarly connected to form a series circuit in which said Kth logic-storage means is the last circuit of said series circuit, each of said K logic-storage means including means for receiving a logic signal at said input terminal and either setting said logic signal to a first or second logic state or leaving said logic signal unaltered in response to a comparator output signal, for storing said altered or unaltered logic signal sequentially in P storage locations in synchronization with the rate of arrival of said serial bit stream at said serial data input terminal, and for providing at said output terminal the Pth prior altered or unaltered logic signal;   (c) comparison means coupled to said serial data input terminal and to said output terminals of said K logic-storage means for determining if the bit of said serial bit stream present at said input terminal in combination with said altered or unaltered logic signals at said output terminals of said first, second, . . . Kth logic-storage means respectively match any (K+1)-bit sequences of the pattern formed by concatenating two of said framing bit patterns and for providing said comparison output signal at an output terminal indicating if a match has occurred or not, said K logic-storage means responding to said comparison output signal by setting each of said logic signals to said first or second logic state such that the combination of a logic bit X, where logic bit X can be either a logical 1 or a logical 0, and said altered logic signals of said first, second, . . . and Kth logic-storage means respectively would not match any sequence of the bit pattern formed by concatenating two of said framing patterns if a match does not occur, and if a match does occur, leaving unaffected said logic signals of said K logic-storage means; and   (d) counting means for counting the number of matches which occur during successive blocks of said serial bit stream which arrive at said data input terminal, each of said blocks being P bits in length.   
     
     
       4. Apparatus for locating the position of the framing bits in a serial bit streams formed according to the ESF standard comprising: (a) an input terminal for receiving said serial bit stream;   (b) a first, second and third logic-storage means, each having an input terminal and an output terminal where said input terminal of said first logic-storage means is coupled to said serial data input terminal, said input terminal of said second logic-storage means is coupled to said output terminal of said first logic-storage means, and said input terminal of said third logic-storage means is coupled to said output terminal of said second logic-storage means, each of said logic-storage means including means for receiving a logic signal at said input terminal and either setting said logic to a first logic state or leaving said logic signal unaltered in response to a comparator output signal, for storing said altered or unaltered logic signal sequentially in 772 storage locations in synchronization with the rate of arrival of said serial bit stream at said serial data input terminal, and for providing at said output terminal the 772nd prior altered or unaltered logic signal;   (c) comparison means coupled to said serial data input terminal and to said output terminals of said first, second and third logic-storage means for determining if the bit of said serial bit stream present at said input terminal in combination with said altered or unaltered logic signals at said output terminals of said third, second and first logic-storage means respectively match any of the bit patterns 0010, 0101, 1011, 0110, 1100 and 1001 and for providing said comparator output signal at any output terminal indicating if a match has occurred or not, said first, second and third logic-storage means responding to said comparator output signal by setting each of said logic signals to said first logic stated if a match does not occur, and if a match does occur, leaving unaffected said logic signals of said logic-storage means; and   (d) counting means for counting the number of matches which occur during successive blocks of said serial bit stream which arrive at said data input terminal, each of said blocks being 772 bits in length. .Iadd.   
     
     
       5.  A method for acquiring the framing clock of a data stream, which is formatted in frames according to a protocol wherein a predetermined bit framing pattern is embedded in the data stream, comprising the steps of: a) carrying successive bits of the data stream in serial memory;   b) successively comparing sets of plural bits, at separations within said serial memory such that each said set of bits corresponds to a single respective bit position with respect to said frame formatting of said predetermined protocol, to ascertain whether each said set constitutes a portion of said bit framing pattern, and accordingly, for each said set:   if the bits of said set could not constitute a portion of said bit framing pattern, overwriting said bits of said respective set with a pattern which assures that the next succeeding test of a bit set at said bit position will also not detect a portion of said framing pattern:   c) and repeating said step (b), until said comparing step has detected, at all but one of the bit positions which are possible within said protocol, that the bit set at said bit position is not part of said framing pattern. .Iaddend. .Iadd.   
     
     
       6.  A circuit for locating the position of framing bits embedded in a serial bit stream, which is formatted in frames according to a protocol wherein a predetermined bit framing pattern is embedded in the data stream, comprising: at least three shift registers, having respective lengths corresponding to a separation of bits of said framing pattern within said bit stream;   a decoder, connected to receive and test the respective outputs of said shift registers, together with an incoming bit, to detect a match with said framing pattern;   a plurality of logic gates, wherein said shift registers are serially connected together through said logic gates, and said logic gates are controlled by the output of said decoder circuit so that; if said decoder indicates that a match has been detected, then the incoming bit is loaded into the input of a first one of said shift registers by said logic gates, and the output of said first one of said shift registers is connected to the input of a second one of said shift registers by said logic gates, and   the output of said second one of said shift registers is connected to the input of a third one of said shift registers by said logic gates; and     if said decoder indicates that a match has NOT been detected, then a predetermined sequence of bit values, which is not a portion of said framing pattern, is loaded into said first, second, and third shift registers by said logic gates. .Iaddend. .Iadd.7. The circuit of claim 6, further comprising a counter, connected to count the number of matches detected by said decoder during a number of bits corresponding to a separation of bits of said framing pattern within said bit stream, and to indicate, if and only if said number of matches is one, that the location of the framing bits within the serial bit stream has been determined.       
     
     
        .Iaddend. .Iadd.8.  The circuit of claim 6, further comprising: a noncycling counter, connected to count the number of matches detected by said decoder; and a cycling counter, connected to reset said noncycling counter at intervals corresponding to a separation of bits of said framing pattern within said bit stream; the output of said noncycling counter being connected to indicate, if and only if said number of matches detected by said noncycling counter is one, that the location of the framing bits within the serial bit stream has been determined. .Iaddend. .Iadd.9. The circuit of claim 6, wherein said predetermined sequence of bit values is three identical values. .Iaddend. .Iadd.10. The circuit of claim 6, wherein said predetermined sequence of bit values is 000. .Iaddend. .Iadd.11. The method of claim 5, wherein said protocol is compatible with the T1 protocol. .Iaddend. .Iadd.12. The circuit of claim 6, wherein said protocol is compatible with the T1 protocol. .Iaddend. .Iadd.13. The method of claim 5, wherein said bit framing pattern does not contain any sequence of three zeros, and wherein said pattern used in said overwriting step is all zeros. .Iaddend. .Iadd.14. The circuit of claim 6, wherein said bit framing pattern does not contain any sequence of three zeros, and wherein said predetermined sequence of bit values is all zeros. .Iaddend. .Iadd.15. The method of claim 5, wherein said protocol is compatible with the Enhanced Superframe Format (ESF) standard. .Iaddend. 
     
     
        .Iadd.16.  The circuit of claim 6, wherein said protocol is compatible with the Enhanced Superframe Format (ESF) standard. .Iaddend. .Iadd.17. The method of claim 5, wherein said sets of bits compared by said step (b) are shorter than the predetermined bit framing pattern of said protocol. .Iaddend. .Iadd.18. The circuit of claim 6, wherein said decoder is connected to test sets of bits which are shorter than the predetermined bit framing pattern of said protocol. .Iaddend. .Iadd.19. The method of claim 5, wherein said sets of bits compared by said step (b) are exactly two bits shorter than the predetermined bit framing pattern of said protocol. .Iaddend. .Iadd.20. The circuit of claim 6, wherein said decoder is connected to test sets of bits which are exactly two bits shorter than the predetermined bit framing pattern of said protocol. .Iadd.21. The method of claim 5, wherein said step (a) of carrying uses a serial memory which includes multiple shift registers connected together in succession, successive ones of said shift registers being interconnected through a logic gate which selectively performs said overwriting during data transfers between successive ones of said shift registers. .Iaddend. .Iadd.22. The method of claim 5, wherein said step (a) of conveying uses a serial memory which is implemented as multiple shift registers connected together in succession. .Iaddend.