講座題目👌🏼：A Novel Polynomial basis and Fast Fourier Transform for Finite Fields
講座人：韓永祥 教授
講座時間：2019年5月23（周四） 13:00-14:30
講座地點🔌：信息樓246
講座內容簡介：
Finding an n-point Fast Fourier Transform (FFT) algorithm over an arbitrary finite field with additive and multiplicative complexity O(n log(n)) has been a long standing open problem in the coding area. It has been known for a long time that a better FFT algorithm can improve the encoding and decoding complexity of Reed-Solomon (RS) codes, one of the most popular codes in the world. Even though an FFT algorithm over a complexity field with additive and multiplicative complexity O(n log(n)) was invented decades ago, it remains unknown whether such an algorithm exists over finite fields. In this talk, we present the first FFT algorithm over finite fields with additive and multiplicative complexity O(n log(n)). A new basis of polynomial over finite fields is invented and then apply it to the FFT over finite fields. The proposed polynomial basis allows that n-point FFT can be computed in O(n log(n)) finite field operations with extremely small leading constant. Based on this novel FFT algorithm, we then develop the encoding 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)) or O(n log2(n-k) finite field operations. As the complexity of leading factor is small, the algorithms are advantageous in practical applications such as encoding/decoding of Reed-Solomon codes and polynomial multiplications in cryptography.
講座人簡介❤️：
韓永祥博士1984年畢業於臺灣清華大學電機工程學系並於1986年於同系取得碩士學位。1993年韓博士於紐約州雪城大學獲得計算機與信息科學博士。他曾於華梵人文科技意昂3，暨南國際大學，以及臺北大學任教。從2010年8月起，他任教於臺灣科技大學電機工程系並於2011年6月起榮任學校講座教授。臺灣科技大學退休後，目前他是東莞理工意昂3教授🏉。
韓博士的研究興趣主要是在糾錯碼，無線網絡和信息安全。韓博士已從事最先進的糾錯碼譯碼研究超過29年👨🏻🌾。29年前他首先開發了基於A *算法的連續型譯碼算法💁🏽✦。當時，該算法吸引了大量的關註🛰，因為它是對二進製線性分組碼最有效的最大似然軟判決譯碼算法🧑🎓。此譯碼算法已被收錄於糾錯碼的經典教科書中。
韓博士還成功地應用編碼理論於無線傳感器網絡的研究領域🌎。他已出版幾個關於無線傳感器網絡研究的高被引用著作。其中一篇關於隨機密鑰預分配方案著作被引用超過兩千次。他還擔任多個國際學術刊物的編輯。
韓博士是1994年雪城大學博士論文獎得主，同時也是IEEE院士。2013年他的一個論文贏得了久負盛名的ACM CCS Test of Time獎🔥。此獎項為 ACM 信息安全領域的年度最有影響力論文獎。
歡迎廣大師生參加！