Design of Check Digit Systems over an Arbitrary Alphabet
Mathematics
Final Report Abstract
The use of check digit systems in real life applications is pervasive, penetrating every corner of the globe and of our daily lives. Some well-known examples include but not limited to credit card numbers, ISBN code for books, UPC code for products, VIN for Vehicles, IMEI for mobile phones, and identity card number for people in most nations. Beyond all doubt, a smart choice of the check digit system will ensure not only the data integrity, but also reduces the ARQ demands and thus boost the efficiency of the information flow. In spite of advances in coding theory, most of check digit systems (or codes) used in practice are still based on simple arithmetic methods such as division, (weighted) modular check sum and Luhn formulae. In general, the problem differentiates itself from the classical error control codes in threefold. First, it should work over any alphabet, not necessarily a prime power; Secondly, the operation is not necessarily over a field (e.g., it could operate over gruops/quasigroups). Thirdly, it deals with detecting/correcting atypical error patterns, for example, the adjacent transposition error, which is treated as two independent substitution errors in classical coding theory. All these make the problem more general and difficult to deal with. From both theoretical and practical points of view, we are interested in the code construction, which is competitive in both the computational complexity and the error detection/correction capability. The aim is to gain a comprehensive understanding of the atypical error patterns made by human operators and to develop new techniques and new design to tackle them. The ultimate goal is to eventually provide effective and adaptive solutions to different application requirements. Not limiting ourselves to the classical coding theory, we exploited new possibilities based on matrix algebra and polynomial rings to design new alternatives. Our main contributions are twofold. First we focused on design of the check digit system with one check digit. Our proposed scheme is based on matrix algebra, works over an arbitrary alphabet, and with improved performance in terms of error detecting capability (compared with several wellknown and widely used systems and those standardized in ISO/IEC 7064). Besides the check digit system with one check digit, we also investigated the design with more check digits involved. For instance, with two check digits, the resulting codes could have the capability of correcting all the single- and adjacent transposition errors. Our proposed codes are systematic, over polynomial rings, and improve the existing schemes in terms of code rate (i.e., longer code length for fixed number of check digits with a certain error correction capability guarantee) and the number of the code candidates. In addition, systems with more check digits that enhance secure communication were also studied. A particularly interesting instance is the alphanumeric system. Alphanumeric is a combination of alphabetic and numeric characters. Such a system is very popular in human interfaces. To our knowledge, our proposal with one check digit gives the best performance among existing alphanumeric systems (e.g., hybrid system MOD 37, 36 as described in ISO/IEC 7064) in terms of error detection capability. For the alphanumeric systems with two check digits, our proposal enables a code length of 19 with capability of correcting all the single and adjacent transposition errors. These are new in the literature. Besides, industry has shown interest in our alphanumeric instance with one check digit.
Publications
- A general check digit system based on finite groups, Design, Codes and Cryptography, vol. 80, no.1, pp. 149-163, Jul. 2016
Y. Chen, M. Niemenmaa, A. J. Han Vinck
(See online at https://doi.org/10.1007/s10623-015-0072-8) - Individual Secrecy for broadcast channels with receiver side information, IEEE Trans. Info. Theory, vol. 63, no.7, pp.4687-4708, Jul. 2017
Y. Chen, O. O. Koyluoglu, and A. Sezgin
(See online at https://doi.org/10.1109/TIT.2017.2699201) - Individual secrecy for the broadcast channel, IEEE Trans. Info. Theory, vol. 63, no.9, pp.5981-5999, Sept. 2017
Y. Chen, O. O. Koyluoglu, and A. Sezgin
(See online at https://doi.org/10.1109/TIT.2017.2694552) - On the binary input Gaussian wiretap channel with/without output quantization, Entropy, vol. 19, no. 2, 59, Feb. 2017
C. Qi, Y. Chen, A. J. Han Vinck
(See online at https://doi.org/10.3390/e19020059)
