A residue number system on reconfigurable mesh with applications to prefix sums and approximate string matching
Several new number representations based on a Residue Number System are presented which use the smallest prime numbers as moduli and are suited for parallel computations on a reconfigurable mesh architecture. The bit model of linear reconfigurable mesh with exclusive write and unit-time delay for broadcasting on a subbus is assumed. It is shown how to convert in O(1) time any integer. ranging between O and n - 1, from any commonly used representation to any new representation proposed in this paper land vice verse) using an n x O(log(2)n/loglogn) reconfigurable mesh. In particular, some of the previously known conversion techniques are improved. Moreover, as a byproduct, it is shown how to compute in O(1) time the Prefix Sums of n bits by a reconfigurable mesh having the above mentioned size, thus improving previously known results. Applications to the Prefix Sums of N h-bit integers and to Approximate String Matching with cu mismatches are also considered. The Summation and the Prefix Sums can be computed in O(1) time using O(h log N + log(2)N/loglogN) x Nh and O(h(2)+log(2)N/log(t)h+logN) x O(N(h + log N)) reconfigurable meshes, respectively. Moreover, it is shown for the first time how to find in O(1) time all the occurrences of a pattern of length m in a text of length n, allowing less than alpha mismatches, using a reconfigurable mesh of size O(m log \Sigma\) x O(n(log \Sigma\ + log(2)alpha /loglog alpha)). where the pattern and the text are strings over a finite alphabet Sigma and alpha   n.
residue number system reconfigurable mesh prefix sums number representation string matching with k mismatches vlsi