For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
M-Ary Substitution/Deletion/Insertion/Adjacent-Symbol-Transposition Error Correcting Codes for Data Entry Systems
Haruhiko KANEKO Eiji FUJIWARA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2009/07/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
nonbinary code, data entry system, asymmetric error, substitution error, deletion error, insertion error, transposition error,
Full Text: PDF(560.7KB)>>
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.