M-Ary Substitution/Deletion/Insertion/Adjacent-Symbol-Transposition Error Correcting Codes for Data Entry Systems

Haruhiko KANEKO  Eiji FUJIWARA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.7   pp.1668-1676
Publication Date: 2009/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.1668
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
Keyword: 
nonbinary code,  data entry system,  asymmetric error,  substitution error,  deletion error,  insertion error,  transposition error,  

Full Text: PDF(560.7KB)>>
Buy this Article




Summary: 
Nonbinary M-ary data processed by data entry systems, such as keyboard devices and character recognition systems, often have various types of error, such as symbol-substitution errors, deletion errors, insertion errors, and adjacent-symbol-transposition errors. This paper proposes nonsystematic M-ary codes capable of correcting these errors. The code is defined as a set of codewords that satisfy three conditions required to correct substitution, deletion/insertion, and adjacent-symbol-transposition errors. Since symbol-substitution errors in data entry systems are usually asymmetric, this paper also presents asymmetric-symbol-substitution error correcting codes capable of correcting deletion, insertion, and adjacent-symbol-transposition errors. For asymmetric-symbol-substitution error correction, we employ a mapping derived from the vertex coloring in an error directionality graph. The evaluation shows that the asymmetric codes have three to five times larger number of codewords than the symmetric codes.