Harbin Institute of Technology Advanced Communications Technologies Forum 2018

Title 1： Efficient Decoding over Unknown Impulsive Noise Channels

Date and Time: 10:00-11:30, September 2, 2018

Location：ROOM 1011, BUILDING 2A, NO.2 YIKUANG STREET,

HARBIN, HEILONGJIANG, CHINA

Abstract:

It has been known from many researches that communication systems are susceptible to memoryless impulsive noise characterized by, for instance, the Bernoulli-Gaussian model. In order to combat this obstacle, channel coding has long served as an effective tool, especially in the context of moderately frequent occurrence of impulses, when the statistics of impulsive noise can be realized at the decoder. In this talk, irrespective of the statistics of impulses, an efficient decoding scheme is introduced by incorporating clipping-featured technique into the Viterbi algorithm. As a result, the proposed decoding scheme, while having a complexity at the same order as that of the Viterbi algorithm, is on a par with its optimal counterpart, for which statistics of impulses is assumed known at receiver, in terms of bit error probability. In addition, the Chernoff bounds of the bit error probabilities of the devised decoding algorithm are derived for both Bernoulli-Gaussian noise model and Middleton Class-A noise model. Comparisons between the bounds we derived and the simulated error rates under a variety of settings indicate that the ensuing analysis can provide critical insights for the efficacy of the proposed decoding approach when dealing with precarious frequent strong impulses.

Title 2： Novel FFT over Binary Finite Fields and Its Application to Reed-Solomon Erasure Codes

Date and Time: 10:00-11:30, September 7, 2018

Location：ROOM 1011, BUILDING 2A, NO.2 YIKUANG STREET,

HARBIN, HEILONGJIANG, CHINA

Abstract:

Abstract A fundamental issue in algebra is to reduce the computational complexities of arithmetic operations over polynomials. Many fast polynomialrelated algorithms, such as encoding/decoding of Reed-Solomon codes, are based on fast Fourier transforms (FFT). However, it is algorithmically harder as the traditional fast Fourier transform (FFT) cannot be applied directly over characteristic-2 finite fields. To the best of our knowledge, no existing algorithm for characteristic-2 finite field FFT/polynomial multiplication has provably achieved O(h log2(h)) operations. In this talk, we present a new basis of polynomial over finite fields of characteristic-2 and then apply it to the encoding/decoding of Reed-Solomon erasure codes. The proposed polynomial basis allows that h-point polynomial evaluation can be computed in O(h log2(h)) finite field operations with small leading constant. As compared with the canonical polynomial basis, the proposed basis improves the arithmetic complexity of addition, multiplication, and the determination of polynomial degree from O(h log2(h) log2 log2(h)) to O(h log2(h)). Based on this basis, we then develop the encoding and erasure decoding algorithms for the (n = 2r; k) Reed-Solomon codes. Thanks to the efficiency of transform based on the polynomial basis, the encoding can be completed in O(n log2(k)) finite field operations, and the erasure decoding in O(n log2(n)) finite field operations. To the best of our knowledge, this is the first approach supporting Reed-Solomon erasure codes over characteristic-2 finite fields while achieving a complexity of O(n log2(n)), in both additive and multiplicative complexities. As the complexity of leading factor is small, the algorithms are advantageous in practical applications.

This work was presented at the 55th Annual Symposium on Foundations of Computer Science (FOCS 2014).

Biography:

Prof. Yungh-Siang Han graduated from the Department of Electrical Engineering of Tsinghua University in Taiwan in 1984 and obtained a master’s degree in the same department in 1986. In 1993, Prof. Yungh-Siang Han received his Ph.D. in Computer and Information Science from Syracuse University, New York. He has taught at Hua Fan College of Humanities and Technology, Jinan International University, and Taipei University. From August 2010 to January 2017, he taught at the Department of Electrical Engineering of the Taiwan University of Science and Technology and was appointed as a lecturer in the school in June 2011. Since February 2015, he is also a lecturer at Taipei University. He is currently a Distinguished Professor of Distinguished Talents in the School of Electrical Engineering and Intelligence at Dongguan Institute of Technology.

Prof. Yungh-Siang Han’s research interests are mainly in error control codes, wireless networks and information security. He has been engaged in the most advanced error control code decoding research for over 20 years. Twenty years ago he first developed a continuous decoding algorithm based on the A* algorithm. At the time, the algorithm attracted a lot of attention because it was the most efficient maximum likelihood softness decision decoding algorithm for binary linear block codes. This decoding algorithm has been included in the classic textbook of error control codes.

Prof. Yungh-Siang Han also successfully applied coding theory to the research field of wireless sensor networks. He has published several highly cited works on wireless sensor network research. One of the random key pre-allocation schemes was cited more than two thousand times. He is also the editor of several international academic journals. Professor Han is the winner of the 1994 Ph.D. Thesis at Syracuse University and an IEEE Fellow. In 2013, one of his papers won the prestigious ACM CCS Test of Time award. This award is the most influential paper award of the year in ACM’s information security field.