讲座信息
04.19 | Novel FFT over Binary Finite Fields and Its Application to Reed-Solomon Erasure Codes
2018.04.18

演讲人:韩永祥博士 东莞理工学院

时间:2019年4月19日(星期四) 下午14:00-15:00

地点:张江校区第二教学楼207室

联系人:王新 xinw@fudan.edu.cn

 

摘要:

代数中的一个基本课题是减少在多项式计算的复杂性。快速傅里叶变换(FFT)作为一种有效的途径,被广泛应用于构建许多的快速和高效的多项式算法,例如Reed-Solomon编码的编解码过程。然而,从算法的角度来看,传统的快速傅里叶变换很难直接应用到当前常见的二值有限域算法。根据我们的调研,当前还没有在O(h*log2(h))操作内,就可以完成二值有限域的傅里叶变换和多项式乘法的算法。在这个讲座中,我们展示了一个二值有限域的基准并且将其应用到了Reed-Solomon编码纠删编码的编解码过程。在较小首项常数值(leading constant)情况下,我们提出的多项式基准实现了在O(h*log2(h))有限域运算操作下完成h位的多项式点乘算法。相较于canonical多项式基准,我们的基准将多项式的加法、乘法和确定多项式度数的确定算法复杂度从O(h*log2(h)*log2(log2(h))) 下降到了O(h*log2(h))。基于以上的理论,我们开发了一个Reed-Solomon编码的编解码算法。在编码参数(n = 2^r; k)时,我们的算法实现了在O(n*log2(k))个有限域操作的复杂度下完成编码操作,并且在O(n*log2(n))个有限域操作下完成解码操作。根据我们的调研,这是第一个纠删编码的编解码方案可以同时在加法和乘法操作上,实现O(n*log2(n))的计算复杂度。对于首项常数值较小的多项式计算场景,我们提出的方案具有较好的实际应用前景。

本项研究工作已经发表在了FOCS 2014 (the 55th Annual Symposium on Foundations of Computer Science)。

报告人简介:

韩永祥博士1984 年毕业于台湾清华大学电机工程学系并于1986 年于同系取得硕士学位。1993 年韩博士于纽约州雪城大学获得计算机与信息科学博士。他曾于华梵人文科技学院,暨南国际大学,以及台北大学任教。从2010 年8 月起,他任教于台湾科技大学电机工程系并于2011 年6 月起荣任学校讲座教授。目前他也是东莞理工学院杰出人才特聘教授。

韩博士的研究兴趣主要是在纠错码,无线网络和信息安全。韩博士已从事最先进的纠错码译码研究超过29 年。29年前他首先开发了基于A * 算法的连续型译码算法。当时,该算法吸引了大量的关注,因为它是对二进制线性分组码最有效的最大似然软判决译码算法。此译码算法已被收录于纠错码的经典教科书中。

韩博士还成功地应用编码理论于无线传感器网络的研究领域。他已出版几个关于无线传感器网络研究的高被引用著作。其中一篇关于随机密钥预分配方案著作被引用超过两千次。他还担任多个国际学术刊物的编辑。韩博士是1994 年雪城大学博士论文奖得主,同时也是IEEE Fellow。2013 年他的一个论文赢得了久负盛名的ACM CCS Test of Time 奖。此奖项为ACM 信息安全领域的年度最有影响力论文奖。

© 2018 复旦大学计算机科学技术学院 地址:上海市张衡路825号 Tell:+86-21-51355555 Fax:+86-21-51355558 Emall:cs_school@fudan.edu.cn
复旦大学计算机科学技术学院
扫一扫了解学院