| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Class of M-Ary Asymmetric Symbol Error Correcting Codes for Data Entry Devices
February 2004 (vol. 53 no. 2)
pp. 159-167
Abstract—Nonbinary M-ary symbols such as alphanumeric characters are commonly used in data entry devices, e.g., keyboards and character recognition devices. The M-ary symbols processed by these devices are sometimes mistaken for other symbols due to errors such as mistyping in keyboards or misreading in character recognition systems. These errors are generally asymmetric, not symmetric. For example, the symbols corresponding to adjacent keys in a keyboard have a high error probability due to mistapping. Similarly, in character recognition systems, two symbols having similar shape have high error probability to be misrecognized. These asymmetric errors can be corrected or detected by using M-ary asymmetric symbol error control codes. This paper proposes a new class of M-ary single asymmetric symbol error correcting codes by using a new class of rings obtained from a direct product of Galois fields. Asymmetric symbol errors are expressed by an error directionality graph, based on which the error correction capability of the codes is determined. The code is defined by a parity check matrix over the ring and functions which map a set of M-ary symbols into the ring. One of the functions is derived from the graph coloring problem of the error directionality graph. The proposed codes have greater information symbol length than the existing M-ary single symmetric symbol error correcting codes.
[1] T.R.N. Rao and E. Fujiwara, Error-Control Coding for Computer Systems. Prentice Hall, 1989.
[2] J.A. Gallian, Error Detection Methods ACM Computing Surveys, vol. 28, no. 3, pp. 504-517, Sept. 1996.
[3] D.T. Tang and V.Y. Lum, Error Control for Terminals with Human Operators IBM J. Research and Development, vol. 14, no. 4, pp. 409-416, July 1970.
[4] T. Noumi, T. Matsui, I. Yamashita, T. Wakahara, and M. Yoshimuro, An Analysis of Substituted/Rejected Patterns in Handwritten Numeral Recognition Technical Report of IEICE, PRU93-46 (in Japanese), pp. 25-32, Sept. 1993.
[5] R.R. Varshamov, A Class of Codes for Asymmetric Channels and a Problem from the Additive Theory of Numbers IEEE Trans. Information Theory, vol. 19, no. 1, pp. 92-95, Jan. 1973.
[6] Y. Saitoh and H. Imai, Constructions of Codes Correcting Burst Asymmetric Errors Lecture Notes in Computer Science, Applied Algebraic Algorithms and Error Correcting Codes, vol. 508, pp. 59-70, 1990.
[7] H. Inaba, F. Terashima, K. Wakasugi, and M. Kasahara, A Note on Character Recognition System Using Error Correcting Codes Trans. IEICE D-II, vol. J77-D-II, no. 2 (in Japanese), pp. 353-361, Feb. 1994.
[8] K. Namba and E. Fujiwara, A Class of Systematicm-Ary Single-Symbol Error Correcting Codes Systems and Computers in Japan, vol. 32, no. 6, pp. 21-28, June 2001.
[9] K. Saowapa, H. Kaneko, and E. Fujiwara, q-Ary Asymmetric Error Locating Codes under Directional Error Model Trans. IEICE A, vol. J84-A, no. 1 (in Japanese), pp. 73-83, Jan. 2001.
Index Terms:
Asymmetric symbol errors, asymmetric error control codes, error directionality graph, confusion matrix, graph coloring, ring, data entry devices.
Citation:
Haruhiko Kaneko, Eiji Fujiwara, "A Class of M-Ary Asymmetric Symbol Error Correcting Codes for Data Entry Devices," IEEE Transactions on Computers, vol. 53, no. 2, pp. 159-167, Feb. 2004, doi:10.1109/TC.2004.1261826