Decoding of non-binary multiple insertion/deletion error correcting codes

Data that is either transmitted over a communication channel or stored in memory is not always completely error free. Many communication channels are subject to noise, and thus errors may occur during transmission from transmitter to receiver. For example, DRAM memory cell contents can change spuriously due to electromagnetic interference while magnetic flux can cause one or more bits to flip in magnetic storage devices. To combat these errors, codes capable of correcting insertion/deletion errors have been investigated. Levenshtein codes are the foundation of this thesis. His codes, first constructed by Varshamov-Tenengol’ts, are capable of correcting one insertion/deletion error. Helberg codes are based on Levenshtein codes and are able to correct multiple insertion/deletion errors. Even though there are codes with better rates, Helberg codes are still important because they can be constructed number-theoretically. In addition, Helberg codes also allow us to correct errors with certainty. However, prior to this thesis, there was no known efficient algorithm to decode Helberg codes. In this thesis, we first present an algorithm to decode deletion errors in Helberg codes as well as a way to generalize Helberg code to non-binary alphabets. Our algorithm recursively corrects one error at a time. As a result, this algorithm is much more efficient compared to exhaustive search. Secondly, we introduce a new class of non-binary codes capable of correcting multiple insertion/deletion errors by generalizing the construction for Helberg codes. Our decoding algorithm is also applicable to correcting deletion errors in these new non-binary codes as well. All the results in this thesis have been published in [9]