Synchronizer Design Pattern for Frame Synchronization

Synchronizer Design Pattern
Intent
Many systems used in digital communication send data in synchronousback-to-back frames. When a receiver tunes to such a data stream, it has noknowledge of the frame boundaries. The Synchronizer Design Pattern is used tolook at the raw incoming bit or byte stream and detect and align to the frame structure.The frame structure is detected by searching for a sync pattern in the frame.
Once the synchronization is achieved, the Synchronizer confirms the presenceof the sync pattern in every frame. If the sync pattern in missed a certainnumber of times, loss of sync is declared.
Also Known As
Sync Handler
Frame Synchronizer
Motivation
On many occasions there is need to maintain synchronization between twoentities connected at opposite ends of a link. This design pattern providesmechanisms for:
Achieving initial synchronization (sync)
Once sync is achieved, confirming the presence of the sync framing
Initiating loss of sync procedures
Applicability
This pattern can be used in the following cases:
Maintaining sync in digital communication systems. e.g. digital trunk synchronization procedures. This design pattern provides a broad framework for implementing such sync systems.
The design pattern can also be applied in more general scenarios where periodic message communication is involved between entities to exchange state information. A good example would be routing protocols where periodic routing updates are used to keep different routers in sync with each other.
Structure
The Synchronizer is implemented as ahierarchical state machine. Thefollowing states are defined for the state machine:
Unsynchronized and searching for sync
Unsynchronized but confirming sync
Synchronized and in sync
Synchronized but confirming sync loss
Each state is represented with a class.
Participants
Synchronizer state machine class is the key participant in this pattern. Thestate machine uses state classes to keep track of state.
Collaboration
The following diagram shows the relationship between various classes involvedin the Synchronizer design pattern:

It is clear from the figure above that the state machine is organized into twohigh-level states, synchronized and unsynchronized. These states act as the baseclass for the following sub-states:
High level state Sub-state Description
Unsynchronized Searching_For_Sync The Synchronizer starts in this state. In this state, the Synchronizer is hunting for the sync pattern in the periodic data. In many cases, the framing of the data is not known, so the search for sync pattern is carried out bit by bit. The Synchronizer transitions to the Confirming_Sync_Pattern state after the first sync pattern is detected.
Confirming_Sync_Pattern Once the first sync pattern is detected, the sync pattern needs to be confirmed. If the sync pattern is detected with the expected periodicity, the Synchronizer transitions to In_Sync state. If the sync pattern is not detected with expected periodicity, the Synchronizer transitions back to the Searching_For_Sync state. (This might happen due to a false detection of the sync pattern)
Synchronized In_Sync The system transitions to the In_Sync state after the sync pattern has been detected and confirmed. When in this state, the Synchronizer checks for every expected sync pattern. If the expected sync pattern is not detected, a sync loss might have taken place. Sync loss detection and confirmation is handled in the Confirming_Sync_Loss state.
Confirming_Sync_Loss The Synchronizer enters this state even when one sync pattern is missed. The main objective here is to decide if the sync pattern loss was an isolated event or it points to link failure (sync loss). When in this state, the synchronizer checks for a pre-defined number of sync patterns. If all the expected sync patterns are missing, the system transitions to the Searching_For_Sync state. If sync patterns loss is not permanent, the system moves back to In_Sync state.
The figure below is the state transition diagram for the synchronizer.

Consequences
Use of this pattern has the following benefits:
Provides a common framework for implementing synchronization logic
Use of hierarchical state machine reduces the amount of code by reducing code duplication in various states.
Use of a state machine forces the developer to handle all possible cases of synchronization events.
Implementation
The implementation is explained in terms of the following scenarios:
Attaining Synchronization
Loosing Synchronization
System starts up in "Searching For Sync" state. In this state, the incoming data stream is being analyzed bit by bit, looking for the occurrence of the sync pattern.
As a soon as a first sync pattern is detected, the system transitions to the "Confirming Sync Pattern" state.
Now the system checks if the sync pattern is repeating as expected. This check is made according to the specified periodicity.
If the sync pattern is repeating, the system transitions to the "In Sync" state. (If the sync pattern was not found, the system would have transitioned back to the "Searching For Sync" state)
At this point, the system is considered to be synchronized.
When the system is synchronized, it is in the "In Sync" state. In this state, the system is constantly monitoring the periodic occurrence of the sync pattern.
If an expected sync pattern is found to be missing, the system transitions to the "Confirming Sync Loss". The system is still in a synchronized state. The main purpose of the "Confirming Sync Loss" state is to check if the loss of sync was an isolated event or it represents complete loss of sync.
In the "Confirming Sync Loss" state, the system looks for the sync pattern at the expected time interval. If the sync pattern is seen again, the system transitions back to the "In Sync" state.
In this case, the sync pattern is not detected for a preconfigured number of times.
The system is now in sync loss state. The system is transitioned to the "Searching For Sync" state.
Sample Code and Usage
The following code defines a simple byte level synchronizer. Here thesynchronizer is receives one byte at a time from the serial link.
Synchronizer.h
class Synchronizer { private: // Counter incremented when a good sync pattern is detected in an out of sync state int m_goodSyncCounter; // Counter incremented when a sync loss is detected in an in sync state int m_badSyncCounter; // Counter used to keep track of sync periodicity. Reset whenever a sync pattern // is detected. int m_byteCounter; // Array for storing the frame contents char m_frameBytes[FRAME_SIZE]; friend class Base_State; friend class Unsynchronized; friend class Synchronized; friend class Searching_For_Sync_State; friend class Confirming_Sync_Pattern_State; friend class In_Sync_State; friend class Confirming_Sync_Loss_State; // Abstract base class for all states class Base_State { void HandleByteStream(Synchronizer &m, char byte) = 0; }; class Unsynchronized : public Base_State { // Common handling for all unsynchronized states should be here }; class Synchronized : public Base_State { // Common handling for all synchronized states should be here }; class Searching_For_Sync_State : public Unsynchronized { void HandleByteStream(Synchronizer &m, char byte); }; class Confirming_Sync_Pattern_State : public Unsynchronized { void HandleByteStream(Synchronizer &m, char byte); }; class In_Sync_State : public Synchronized { void HandleByteStream(Synchronizer &m, char byte); }; class Confirming_Sync_Loss_State : public Synchronized { void HandleByteStream(Synchronizer &m, char byte); }; static Searching_For_Sync_State searching_for_sync_state; static Confirming_Sync_Pattern_State confirming_sync_pattern_state; static In_Sync_State in_sync_state; static Confirming_Sync_Loss_State confirming_sync_loss_state; Base_State *m_pCurrentState; void ChangeState(Base_State *pNextState) { m_pCurrentState = m_pNextState; } // Pass Frame to higher layer .Pointer to the beginning of the frame // is passed (Sync pattern is included) void PassFrameToHigherLayer(const char *pFrameData); public: // Handle a byte aligned stream. In this example, the sync pattern // is defined at byte boundaries. void HandleByteStream(char byte) { // Pass the byte to the currently active state m_pCurrentState->HandleByteStream(Synchronizer &m, char byte); } };
Synchronizer.cpp
// Search byte-wise for a sync pattern. As soon as the pattern is found, transition to // frame-wise searching for confirming sync patterns void Synchronizer::Searching_For_Sync_State::HandleByteStream(Synchronizer &m, char byte) { if (byte == SYNC_PATTERN) { m.m_byteCounter = 0; m.m_goodSyncCounter = 0; m.ChangeState(&m.confirming_sync_state); } } // Perform a frame-wise search for the sync pattern. Go back to byte-wise frame search if // even one expected sync is missed. If the frame-wise sync search finds expected number of // sync patterns, move to the the in-sync state void Synchronizer::Confirming_Sync_Pattern_State::HandleByteStream(Synchronizer &m, char byte) { if (m.m_byteCounter == FRAME_SIZE) { m.m_byteCounter = 0; if (byte == SYNC_PATTERN) { if (++m.m_goodFrameCounter == GOOD_SYNC_THRESHOLD) { // We have detected the required number of // sync signals. So copy the sync byte and change // state to in sync m.m_frameBytes[m.m_byteCounter] = byte; m.ChangeState(m.in_sync); } } else // Expected sync pattern not found { // Since the expected sync pattern was not found, go back to // byte wise search for sync pattern m.ChangeState(&m.searching_for_sync_state); } } } // Keep receiving bytes and pass them to the higher layers when a frame has // been completed. Even if one sync is detected to be bad, start checking // for sync loss. void Synchronizer::In_Sync_State::HandleByteStream(Synchronizer &m, char byte) { if (m.m_byteCounter == FRAME_SIZE) { // Beginning of a new frame m.m_byteCounter = 0; m.PassFrameToHigherLayer(m.m_frameBytes); if (byte != SYNC_PATTERN) { m.m_badSyncCounter = 1; m.ChangeState(m.confirming_sync_loss_state); } } m.m_frameBytes[m.m_byteCounter++] = byte; } // Check for sync loss. If a given consecutive bad sync threshold is exceeded, transition // to the unsynchronized state and perform a byte wise search for the sync pattern. void Synchronizer::Confirming_Sync_Loss_State::HandleByteStream(Synchronizer &m, char byte) { if (m.m_byteCounter == FRAME_SIZE) { m.m_byteCounter = 0; if (byte != SYNC_PATTERN) { if (++m.m_badFrameCounter == BAD_SYNC_THRESHOLD) { // Too many sync misses have been detected. // Moving to out of sync state m.ChangeState(&m.searching_for_sync_state); } } else // Expected sync pattern is found { // Since the expected sync pattern was found, go back to // the in sync state m.ChangeState(&m.in_sync_state); } } m.m_frameBytes[m.m_byteCounter++] = byte; }
Known Uses
Digital Trunk Synchronization
Frame and Super-frame synchronization in TDMA and CDMA systems
Related Patterns
Hierarchical State Machines
Serial Port Design Pattern
Transmit Protocol Handler Design Pattern
Receive Protocol Handler Design Pattern