Error Correcting Codes are commonly used to transmit data over noisy communication channels. The noisy channel may introduce errors like flipping of bits or deletion or insertion of bits. The simplest form of error correcting codes usually correct errors that are caused by flipping of bits.
The general scheme of error correcting code is as follows:
The encoder converts a message into a codeword by adding a certain amount of redundancy to the message bits.
The method of determining the redundancy bits varies for different schemes of encoding.
The encoded message is sent across a noisy channel
At the receiver end, the decoder tries to determine the exact message that was sent by making use of the message bits and the redundant bits that were transmitted across the channel.
Each coding scheme has certain limitations on the error conditions that can be corrected.
The amount of redundant data attached to each packet is pre-determined by the amount of noise that a channel may add to each packet.
Error Correcting Codes for Data Synchronization:
The data synchronization scheme using error-correcting codes assumes that data on each device is in the form of sets. The elements of the sets are unindexed, meaning that only the content of the individual sets matter and not the relative position of the elements within the set.
Each host determines its characteristic vector as described earlier. Each characteristic vector is of length equal to that of a valid code word of the code C. The length of the code word is the value of the maximum allowable element in the set. Each characteristic vector can be thought of as a received code word. These code words could be valid or invalid depending on the values of the data present in each set.
The decoding algorithm of the coding scheme when applied to the characteristic vector gives an idea of the distance of the characteristic vector from a valid code word.
One very popular and extensively studied coding scheme is the BCH Error Correcting Code. For the purpose of synchronization the BCH code was chosen because of the vast amount of literature available about BCH codes. An implementation of Tornado codes and LDPC codes were also studied to see if they could be applied to the Set-Reconciliation problem.