Fast reconfiguring mesh-connected VLSI arrays

Mesh-connected VLSI array has a regular and modular structure and allows fast implementation of most signal and image processing algorithms. This paper aims to propose a fast reconfiguration algorithm for finding an maximum sized sub-array in two-dimensional degradable VLSI arrays. The older approach for row-selection is improved such that the time complexity in row-selection is reduced from O((1 - rho) (.) m (.) n) to O((1 - rho) (.) n) for a given array with size m x n, where p is the fault density. The proposed algorithm only reroutes a small sized sub-set of the logical arrays which possibly contains the maximal sized target array. The time complexity of the latest reconfiguration algorithm cited in the literature is reduced from O((1 - rho) (.) m(2) (.) n) to O((1 - rho) (.) k (.) m (.) n) without loss of performance, where k much less than m and k is nearly a constant for small rho.