Back to search

Rowan University

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

Abstract

dc:description.abstract

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].

Degree

thesis:*
Name thesis:degree_name
M.A. Mathematics
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Mathematics

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Le, Tuan Anh
Contributors dc:contributor
  • Nguyen, Hieu
  • Li, Ming-Sun
  • Hassen, Abdul

Subjects

dc:subject × 8

Identifiers

dc:identifier.*
Repository record dc:identifier
https://rdw.rowan.edu/etd/1544

Chain of custody

source
Harvested from
Rowan University
Base URL
rdw.rowan.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Le, Tuan Anh. Decoding of non-binary multiple insertion/deletion error correcting codes. Thesis thesis, https://rdw.rowan.edu/etd/1544