DenseQMC: an efficient bit-slice implementation of the Quine-McCluskey algorithm

Reference : DenseQMC: an efficient bit-slice implementation of the Quine-McCluskey algorithm


	Document type :	E-prints/Working papers : Already available on another site
	Discipline(s) :	Engineering, computing & technology : Computer science
	Focus Areas :	Computational Sciences
	To cite this reference:	http://hdl.handle.net/10993/54526

Title :	DenseQMC: an efficient bit-slice implementation of the Quine-McCluskey algorithm
Language :	English
Author, co-author :	Udovenko, Aleksei [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux]
Publication date :	Feb-2023
Peer reviewed :	No
Keywords :	[en] Boolean minimization ; Two-level minimization ; Quine-McCluskey ; Implementation ; Bit-slice
Abstract :	[en] This note describes a new efficient bit-slice implementation DenseQMC of the Quine-McCluskey algorithm for finding all prime implicants of a Boolean function in the dense case. It is practically feasible for n <= 23 when run on a common laptop or for n <= 27 when run on a server with 1 TiB RAM. This note also outlines a very common mistake in the implementations of the Quine-McCluskey algorithm, leading to a quadratic slowdown. An optimized corrected implementation of the classic approach is also given (called SparseQMC). The implementation is freely available at https://github.com/hellman/Quine-McCluskey .
Funders :	Fonds National de la Recherche - FnR
Target :	Researchers ; Professionals ; Students ; General public
Permalink :	http://hdl.handle.net/10993/54526
Other URL :	https://eprint.iacr.org/2023/201
source URL :	https://eprint.iacr.org/2023/201
FnR project :	FnR ; FNR13641232 > Alex Biryukov > APLICA > Analysis And Protection Of Lightweight Cryptographic Algorithms > 01/01/2021 > 31/12/2023 > 2019

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Open access	2023-201.pdf		Author preprint	1.13 MB	View/Open

All documents in ORBi^lu are protected by a user license.