A robust number theoretic transform with applications in error control and communication systems

• Main Author: Yanto, Jakop
• Other Authors: A. S. Madhukumar
• Format: Theses and Dissertations
• Published: 2008
• Subjects: DRNTU::Engineering::Computer science and engineering::Mathematics of computing
• Online Access: https://hdl.handle.net/10356/2552
• Institution: Nanyang Technological University

This thesis presents a novel modification for a number theoretic transform (NTT) called Robust Symmetrical Number System (RSNS) and addresses its applications in error control and communication systems. NTTs have very attractive properties, such as fault-tolerant features as well as a lower complexity in computer arithmetic. RSNS is one subclass of NTT that decomposes an integer into a set of parallel residues. Due to the carry free arithmetic and lack of ordered significance among the residue digits, operations to the residues can be carried out in parallel. RSNS has inherent features, such as short dynamic range and integer Gray property. Due to the short dynamic range, the difference between the representable range and the efficient information dynamic range is significant. This allows self-detection of errors without the need of additional residues as in Residue Number System (RNS). However, due to the integer Gray property of RSNS, high correlation exists between residue vectors of two consecutive integers. This results in a low error detection probability. To improve the error detection ability, several binary representations, such as binary, Gray and inverse Gray codes are studied for mapping the residues in the context of RSNS. Theoretical and numerical results show that RSNS coded with inverse Gray, referred to as inverse Gray RSNS (IGRSNS), outperforms binary and Gray RSNS and has a near-optimal error detection ability. IGRSNS is further studied for application in error correction. One redundant modulus is added to improve the error correction ability of IGRSNS. An efficient error correction algorithm is proposed. Studies show that IGRSNS with one redundant modulus can improve the error correction ability substantially compared to binary and Gray RSNS.