AN EFFICIENT AND HARDWARE-IMPLEMENTABLE SYSTOLIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM
The problem of longest common subsequence is defined as finding the longest common subsequence of two input sequences. It can be employed in many fields such as speech and signal processing, data compression, syntactic pattern recognition, string processing, and genetic engineering. Usually, lengths of both input sequences are very long, resulting in long processing time. Many previous algorithms have been proposed to reduce the processing time. Previous systolic algorithms can achieve linear time complexity with linear number of processing elements. However, each processing element needs linear memory-space to store intermediate results and then the system needs too large memory-space in total, resulting in being not suitable for being implemented on VLSI. Hence, to design an efficient and hardware-implementable algorithm is an important issue.This paper proposes a hardware-implementable and efficient systolic algorithm for the longest common subsequence problem. At first, we investigate the property of overlapped-contours. By employing divide and conquer technique, we can find a longest common subsequence from the overlapped-contours. It needs a little more time complexity with only linear memory-space in total. Furthermore, the number of physical processing elements can be fixed by employing the concept of virtual processing elements. Therefore, our proposed systolic algorithm is not only hardware-implementable on VLSI but also efficient.
Longest common subsequence systolic algorithm divide and conquer virtual processing elements
SHU-HUA HU CONG-WEI WANG HSING-LUNG CHEN
Department of Computer Science and Information Engineering, Jiwen University of Science and Tech., T Department of Electronic Engineering, National Taiwan University of Science and Technology, Taipei,
国际会议
2008 International Conference on Machine Learning and Cybernetics(2008机器学习与控制论国际会议)
昆明
英文
3150-3155
2008-07-12（万方平台首次上网日期，不代表论文的发表时间）