An efficient hardware implementation of a combinations generator

• Autorzy: Mazurkiewicz T.
• Języki publikacji: EN

Abstrakty

EN

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

EN

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

• Wydawca: Wydawnictwo Uniwersytetu Warmińsko-Mazurskiego w Olsztynie
• Czasopismo: Technical Sciences / University of Warmia and Mazury in Olsztyn
• Rocznik: 2017
• Tom: nr 20(4)
• Strony: 405--413
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

Twórcy

autor

Mazurkiewicz T.

• Instytut Matematyki i Kryptologii, Wydział Cybernetyki, Wojskowa Akademia Techniczna, ul. Urbanowicza 2, 00-909 Warszawa

Bibliografia

• AKL S.G. 1987. Adaptive and Optimal Parallel Algorithms For Enumerating Permutations and Combinations. The Computer Journal, 30: 433–436.
• 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.
• CHEN G.H., CHERN M.-S. 1966. Parallel Generation of Permutations and Combinations. BIT Numerical Mathematics, 26(3): 277–283.
• 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.
• KNUTH D.E. 2006. The Art of Computer Programming. 4, Fasc. 4, Addison-Wesley.
• 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.
• 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.
• LEHMER D.H. 1960. Teaching combinatorial tricks to a computer. Proc. of Symposium Appl. Math, 10: 179–193.
• LEHMER D.H. 1964. The machine tools of combinatorics. Applied combinatorial mathematics, pp. 5–31, John Wiley.
• 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.
• RUSKEY F., WILLIAMS A. 2009. The Coolest Way to Generate Combinations. Discrete Mathematics, 309(17): 5305–5320.
• STOJMENOVIC I. 1992. A Simple Systolic Algorithm for Generating Combinations in Lexicographic Order. Computers Math. Applic., 34(4): 61–64.
• TAKAOKA T. 1999. O(1) Time Algorithms for Combinatorial Generation by Tree Traversal. The Computer Journal, 42(5): 400–408.
• WEI Y. 2014. The Grouping Combination Generating Algorithm. Proc. of International Conference on Computer, Network Security and Communication Engineering, pp. 670–674.

Uwagi

Opracowanie w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).