A Systolic Architecture with Linear Space Complezity for Longest Common Subsequence Problem

摘要：

The longest common subsequence (LCS) problem is to find an LCS of two strings and the length of the LCS (LLCS).Many previous works focused on reducing the processing time.However,most require too large memory space in total,resulting in being not suitable for hardware implementation.In this paper,we propose a hardwareimplementable algorithm and its systoliC architecture. The algorithm achieves linear space complexity,and the systoliC architecture is feasible for hardware implementation. For two given strings with their lengths of m and n,the algorithm consumes less time complexity when the LLCS is approaching to the minimum of m and n.Furthermore,a scalable architecture is proposed to deal with the LCS problems of two huge strings,whose lengths are far more than m and n. Therefore,our scalable systolic architecture with linear space complexity for the LCS problem is suitable for hardware implementation,and the synthesized results show that our architecture is more efficient.

关键词： Longest common subsequence systolic algorithm systolic architecture scalable architecture

作者: Chuanpeng Chen Zhongping Qin

作者单位: School of Computer,Wuhan University,Wuhan 430072,Hubei,China School of Computer,Wuhan University,Wuhan 430072 Hubei,China Huazhong University of Science and Tech

会议类型: 国际会议

会议名称: 2009 IEEE 8th International Conference on ASIC(第八届IEEE国际专用集成电路大会)

会议地点: 长沙

会议语种:英文

页码: 33-36

在线出版日期: 2009-10-20（万方平台首次上网日期，不代表论文的发表时间）