Computation of Galois field expressions for quaternary logic functions on GPUs

Dusan B. Gajic
Dept. of Computer Science, Faculty of Electronic Engineering, University of Nis, Aleksandra Medvedeva 14, 18000 Nis, Serbia
Serbian Journal of Electrical Engineering, 2014


   title={Computation of Galois field expressions for quaternary logic functions on GPUs},

   author={Gaji{‘c}, Du{v{s}}an B},

   journal={Serbian Journal of Electrical Engineering},





Download Download (PDF)   View View   Source Source   



Galois field (GF) expressions are polynomials used as representations of multiple-valued logic (MVL) functions. For this purpose, MVL functions are considered as functions defined over a finite (Galois) field of order p – GF(p). The problem of computing these functional expressions has an important role in areas such as digital signal processing and logic design. Time needed for computing GF-expressions increases exponentially with the number of variables in MVL functions and, as a result, it often represents a limiting factor in applications. This paper proposes a method for an accelerated computation of GF(4)-expressions for quaternary (four-valued) logic functions using graphics processing units (GPUs). The method is based on the spectral interpretation of GF-expressions, permitting the use of fast Fourier transform (FFT)-like algorithms for their computation. These algorithms are then adapted for highly parallel processing on GPUs. The performance of the proposed solutions is compared with referent C/C++ implementations of the same algorithms processed on central processing units (CPUs). Experimental results confirm that the presented approach leads to significant reduction in processing times (up to 10.86 times when compared to CPU processing). Therefore, the proposed approach widens the set of problem instances which can be efficiently handled in practice.
Rating: 2.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: