ECE Seminar - A New Decoding Method for Reed–Solomon Codes Based on FFT and Modular Approach
Abstract: Decoding algorithms for Reed–Solomon (RS) codes are of great interest for both practical and theoretical reasons. In this talk, an efficient algorithm, called the modular approach (MA), is devised for solving the Welch–Berlekamp (WB) key equation. We propose a new decoding algorithm for systematic RS codes by taking the MA as the key equation solver. For (n, k) RS codes, where n is the code length, and k is the code dimension, the proposed decoding algorithm has both the best asymptotic computational complexity O(n log(n − k) + (n − k) log2(n − k)), and the smallest constant factor achieved to date. By comparing the required field operations, we show that the new algorithm is significantly superior to the existing methods in terms of computational complexity when decoding practical RS codes. When decoding the (4096, 3584) RS code defined over F212 , the new algorithm is ten times faster than a conventional syndrome-based method. Furthermore, the new algorithm has a regular architecture and is thus suitable for hardware implementation.
Yunghsiang S. Han received B.Sc. and M.Sc. degrees in electrical engineering from the National Tsing Hua University, Taiwan, in 1984 and 1986, respectively, and a Ph.D. degree from the School of Computer and Information Science, Syracuse University, NY, in 1993. He was with Hua Fan College of Humanities and Technology, National Chi Nan University, and National Taipei University, Taiwan. From August 2010 to January 2017, he was with the Department of Electrical Engineering at the National Taiwan University of Science and Technology. He was with the School of Electrical Engineering & Intelligentization at Dongguan University of Technology, China, from February 2017 to February 2021. Now, he is with the Shenzhen Institute for Advanced Study at the University of Electronic Science and Technology of China. He is also a Chair Professor at National Taipei University since February 2015. Dr. Han’s research interests include error-control coding, wireless networks, and security. Dr. Han has been conducting state-of-the-art research in decoding error-correcting codes for more than twenty years. He first developed a sequential-type algorithm based on Algorithm A* from artificial intelligence. At the time, this algorithm drew a lot of attention since it was the most efficient maximum-likelihood decoding algorithm for binary linear block codes. Dr. Han has also successfully applied coding theory in wireless sensor networks. He has published several highly cited works on wireless sensor networks, such as random key pre-distribution schemes. He also serves as the editor of several international journals. Dr. Han was the winner of the Syracuse University Doctoral Prize in 1994 and a Fellow of IEEE. One of his papers won the prestigious 2013 ACM CCS Test-of-Time Award in cybersecurity to recognize its significant impact on the security area over ten years.