Coding structure and properties for correcting insertion/deletion errors

by Willem Adriaan Clarke

Institution: University of Johannesburg
Year: 2012
Keywords: Error-correcting codes (Information theory); Digital communications
Record ID: 1475076
Full text PDF: http://hdl.handle.net/10210/5418


The digital transmission of information necessitates the compensation for disturbances introduced by the channel. The compensation method usually used in digital communications is error correcting coding. The errors usually encountered are additive in nature, i.e. errors where only symbol values are changed. Understandably, the field of additive error correcting codes has become a mature research field. Remarkable progress has been made during the past 50 years, to such an extent that near Shannon capacity can be reached using suitable coding techniques. Sometimes the channel disturbances may result in the loss and/or gain of symbols and a subsequent loss of word or frame synchronisation. Unless some precautions were made, a synchronisation error may propagate and corrupt large blocks of data. Typical precautions taken against synchronisation errors are: out-of-band clock signals distributed to the transmission equipment in a network; stringent requirements on clock stability and jitter; limits on the number of repeaters and regeneration to curb jitter and delays; line coding to facilitate better clock extraction; and - use of framing methods on the coding level. Most transmission systems in use today will stop data transmission until reliable synchronisation is restored. El multiplexing systems are still the predominantly used technology in fixed telephone line operators and GSM operators, and recovering from a loss of synchronisation (the FAS alarm) typically lasts approximately 10 seconds. Considering that the transmission speed is 2048 KB/s, a large quantity of data is lost in during this process. The purpose of this study is therefore to broaden the understanding of insertion/deletion correcting binary codes. This will be achieved by presenting new properties and coding techniques for multiple insertion/deletion correcting codes. Mostly binary codes will be considered, but in some instances, the results may also hold for non-binary codes. As a secondary purpose, we hope to generate interest in this field of study and enable other researchers to continue to deeper explore the mechanisms of insertion and/or deletion correcting codes.