An efficient hardware implementation of a combinations generator

Tomasz Mazurkiewicz




Abstrakt

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.


Słowa kluczowe:

information technology, generator of combinations, field programmable gate array (FPGA)


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


Opublikowane
02-10-2017

Cited By /
Share

Mazurkiewicz, T. (2017). An efficient hardware implementation of a combinations generator. Technical Sciences, 20(4), 405–413. https://doi.org/10.31648/ts.5436

Tomasz Mazurkiewicz 








-->