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 ldquodivide and conquerrdquo 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.