JISE


  [1] [2] [3] [4] [5] [6]


Journal of Information Science and Engineering, Vol. 4 No. 1, pp. 35-47


A Systolic Design to Generate Combinations


CHAU-JY  LIN AND JONG-CHUANG  TSAY
Department of Applied  Mathematics and  Institute of Computer Engineering
National Chiao Tung University
Hsinchu,Taiwan, Republic of China

 


    Design of a linear systolic array for generating all combinations of m  items out of  n  given items in a lexicographic order is presented. The algorithm of the systolic array is very simple only consists of two If-Then-Else statements. Its time complexity is O(2*Cmm 一1), and the required number of processing elements is m. This algorithm can be modified to generate all combinations of, at most m items out of  n  items. Also it can be combined with an m! generation algorithm to generate all the  nPm  permutations.


Keywords: Linear systolic array, parallel algorithm, lexicographic order, combination , verification of correctness

  Retrieve PDF document (JISE_198801_03.pdf)