An efficient hardware implementation of a combinations generator
Tomasz Mazurkiewicz
Abstract
In this paper an area-efficient hardware implementation of a Bincombgen algorithm was presented. This algorithm generates all (n,k) combinations in the form of binary vectors. The generator was implemented using Verilog language and synthesized using Xilinx and Intel-Altera software. Some changes were applied to the original code, which allows our FPGA implementation to be more efficient than in the previously published papers. The usage of chip resources and maximum clock frequency for different values of n and k parameters are presented.
Keywords:
information technology, generator of combinations, field programmable gate array (FPGA)References
AKL S.G. 1987. Adaptive and Optimal Parallel Algorithms For Enumerating Permutations and Combinations. The Computer Journal, 30: 433–436. Google Scholar
BUBNIAK G., GÓRALCZYK M., KARP M., KOKOSIŃSKI Z. 2004. A Hardware Implementation of a Generator of (N,K)-Combinations. IFAC Proceedings Volumes, 37(20): 228–231. Google Scholar
CHEN G.H., CHERN M.-S. 1966. Parallel Generation of Permutations and Combinations. BIT Numerical Mathematics, 26(3): 277–283. Google Scholar
HOUGH T., RUSKEY F. 1988. An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm. Journal of Combinatorial Mathematics and Combinatorial Computing, 4:. 79–86. Google Scholar
KNUTH D.E. 2006. The Art of Computer Programming. 4, Fasc. 4, Addison-Wesley. Google Scholar
KOKOSIŃSKI Z. 1997a. An Associative Processor for Multicomparand Parallel Searching and Its Selected Applications. Proc. of Int. Conf. on Parallel and Distributed Processing Techniques and Applications PDPTA, pp. 1434–1442. Google Scholar
KOKOSIŃSKI Z. 1997b. On Parallel Generation of Combinations in Associative Processor Architectures. Proc. of IASTED Int. Conf. on Parallel and Distributed Systems Euro-PDS, pp. 283–289. Google Scholar
LEHMER D.H. 1960. Teaching combinatorial tricks to a computer. Proc. of Symposium Appl. Math, 10: 179–193. Google Scholar
LEHMER D.H. 1964. The machine tools of combinatorics. Applied combinatorial mathematics, pp. 5–31, John Wiley. Google Scholar
MAZURKIEWICZ T., ŁUBA T. 2017. Redukcja liczby zmiennych do reprezentacji funkcji generowania indeksów. Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, 8-9: 795–798. Google Scholar
RUSKEY F., WILLIAMS A. 2009. The Coolest Way to Generate Combinations. Discrete Mathematics, 309(17): 5305–5320. Google Scholar
STOJMENOVIC I. 1992. A Simple Systolic Algorithm for Generating Combinations in Lexicographic Order. Computers Math. Applic., 34(4): 61–64. Google Scholar
TAKAOKA T. 1999. O(1) Time Algorithms for Combinatorial Generation by Tree Traversal. The Computer Journal, 42(5): 400–408. Google Scholar
WEI Y. 2014. The Grouping Combination Generating Algorithm. Proc. of International Conference on Computer, Network Security and Communication Engineering, pp. 670–674. Google Scholar
