Pulse or digital communications – Synchronizers – Frequency or phase control using synchronizing signal
Reexamination Certificate
1998-12-09
2001-06-12
Ghebretinsae, Temesghen (Department: 2631)
Pulse or digital communications
Synchronizers
Frequency or phase control using synchronizing signal
C375S364000, C370S514000
Reexamination Certificate
active
06246736
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to systems and methods for searching for and maintenance of frame alignment in incoming digital data streams.
BACKGROUND OF THE INVENTION
It is common for serial data streams to be comprised of sets of contiguous frames with each frame including one or more FAS (frame alignment sequence) bits. The FAS bits constitute the FAS, and are used to delineate frames of an incoming serial bit stream and the position of the frame within a multiframe structure. Delineation of frames offers a receiving station the ability to know exactly what bit of an incoming set of frames is being received at any time.
When a receiving station is receiving frames and the location of the FAS has been determined, it is said to be In-Frame (IF). When the receiving station is not locked to the FAS, it is said to be Out-of-Frame (OOF). The receiver then must invoke a FAS search algorithm in order to find the FAS within the incoming data stream.
U.S. Pat. No. 4,347,606 to Hoogeveen which issued on Aug. 31, 1982, is entitled “Method of Frame Synchronization of a Digital TDM Communication System and Arrangement for Performing the Method” and discloses a method which keeps track of how many FAS bits, starting from the first FAS bit, have been received in each of the possible FAS bit stream locations. Each time a correct bit is received, this count is incremented. Each time an incorrect bit is received, the count is reset to zero, and the search started over again for that particular location. A disadvantage of this system is that the algorithm searches for the FAS in a predetermined order, starting with the first FAS bit. Thus, even for the correct FAS location, most of the time the embedded FAS will be out of phase with the FAS it is being compared with.
U.S. Pat. No. 4,847,877 to Besseyre which issued on Jul. 11, 1989 is entitled “Method and Apparatus for Detecting a Predetermined Bit Pattern Within a Serial Bit Stream” discloses a system in which a four bit subsequence of a twelve bit FAS is used to identify a starting point in the FAS. A table look-up is performed to identify the next eight bits of the FAS. The next twelve bits are compared to these eight bits. If these are found, then the FAS is deemed to have been located. Disadvantageously, the methods provided in Besseyre do not examine the different possible FAS bit streams concurrently and do not deal with mimics. Mimic bit streams exist when at least one potential FAS location which ultimately does not contain the actual FAS contains bits which match the entire FAS for a significant period of time.
SUMMARY OF THE INVENTION
It is an object of the invention to obviate or mitigate one or more of the above identified disadvantages.
A method and apparatus for detecting a framing alignment sequence within a received bit stream are provided. A stream state memory location is assigned for each possible location of the framing alignment sequence. Bits of a particular stream are loaded into the respective stream state memory location. If the bits do not match an acceptable subsequence of the framing alignment sequence then the stream is eliminated from consideration by writing an exile state to the respective stream state memory location. Then subsequently received bits are used to transition either to the next state if the next bit is a correct bit in the framing alignment sequence, or to the exile state if the bit is not the correct bit. After all of the streams have been exiled but one, the remaining stream may contain the framing alignment sequence. However, it may be that a certain number of correctly received bits are required to declare in-frame with sufficient certainty in which case incoming bits will continue to be processed until this is satisfied. Example applications include detection of the DS1 superframe and extended superframe framing alignment sequences.
According to a first broad aspect, the present invention provides a method for the purpose of frame synchronization, of detecting a repeating predetermined M-bit sequence included within an incoming serial bit stream, the M bit sequence being distributed over the bit stream in a predetermined manner in one of N possible streams within the bit stream, and the predetermined pattern containing M unique or semi-unique subsequences each K bits in length allowing for wrap-around within the M-bit pattern, the method comprising the steps of: a) associating with each subsequence a respective state transition bit, the state transition bit being the bit in the repeating predetermined M-bit sequence following the subsequence, each particular subsequence having a respective next subsequence, that being the subsequence consisting of the second through last bits of the particular subsequence and the state transition bit; b) for each of said N possible streams, receiving K bits of the stream and storing them; c) for each stored K bits, determining if they match any of the M unique subsequences in which case the stored bits are a stored subsequence, and if not, eliminating that stream from further consideration; d) receiving a next bit, and if the stream to which it belongs has not been previously eliminated from consideration then looking up the stored subsequence of that stream and determining if the next bit is the state transition bit for that subsequence, and if so storing the next subsequence in place of the stored subsequence, and if not eliminating the stream from further consideration; e) repeating step d) until predetermined criteria have been satisfied.
According to a second broad aspect, the present invention provides a method for detecting a repeating predetermined M-bit pattern included within an incoming serial bit stream, the M bits being distributed over the bit stream in a predetermined manner in one of N possible streams within the bit stream, and the predetermined pattern containing M unique or semi-unique subsequences each K bits in length, the method comprising the steps of: a) associating with each subsequence a respective unique state identifier and a respective state transition bit, the state transition bit being the bit in the repeating predetermined sequence following the subsequence, each state having a respective next state, that being the state associated with the subsequence consisting of the second through last bits of the previous subsequence and the state transition bit; b) for each of said N possible streams, receiving K-1 bits of the stream and storing them; c) for each of said N possible streams, receiving a Kth bit, and determining if the previously received K-1 bits plus the Kth bit match any of the M unique subsequences and if so storing the state identifier for that unique subsequence in place of the stored bits, and if not, eliminating that stream from further consideration; d) receiving a next bit, and if the stream to which it belongs has not previously been eliminated from consideration then looking up the stored state of that stream and determining if the next bit is the state transition bit for that state, and if so storing the state identifier of the next state in place of the stored state, and if not eliminating the stream from further consideration; e) repeating step d) until predetermined criteria have been satisfied.
According to a third broad aspect, the present invention provides an apparatus for detecting a repeating FAS (framing alignment sequence) M bits in length included within an incoming serial bit stream, the M bits being distributed over the bit stream in a predetermined manner in one of N possible streams within the bit stream, and the FAS containing M unique or semi-unique subsequences each K bits in length allowing for wrap-around within the FAS, the apparatus comprising: a stream state memory having K bits of storage for each of said N possible streams; means for receiving K bits of each of said N possible streams and storing them in the stream state memory and for receiving subsequent bits; a state machine in which each of said M unique or semi-unique subsequences is associated with a valid state,
Ghebretinsae Temesghen
Nortel Networks Limited
LandOfFree
Digital signal framing systems and methods does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital signal framing systems and methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital signal framing systems and methods will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2479202