Two algorithms for obtaining fixed polarity arithmetic expansion representation of quaternary functions

• Autorzy: Lozano C. C. , Falkowski B. J. , Łuba T.
• Języki publikacji: EN

Abstrakty

EN

Multiple-valued logic has attracted research interests as one way to improve and overcome the limitations encountered in circuits employing two-valued (binary) logic. In particular, much attention has been paid to the three-valued (ternary) and four-valued (quaternary) logic which form the smallest multiple-valued fields. In this article two algorithms for efficient calculation of quaternary fixed polarity arithmetic expansions (QFPAEs) representation of quaternary functions are presented. The first algorithm operates on disjoint cubes array representation of the input function and is suitable for obtaining selected spectral coefficients. The second algorithm starts from QFPAE in polarity zero and is advantageous for deriving either all QFPAE spectra or QFPAE coefficient vector in nonzero polarities. Both algorithms are simple and have high possibilities of parallel implementation. In order to show the advantage of the proposed algorithm, the computational costs for the second algorithm have been derived and compared with the fast transform method. The comparison shows that the algorithm has lower computational cost for generating the complete polarity matrix.

Słowa kluczowe

EN

fixed polarity arithmetic expansions; quaternary functions; spectral techniques; disjoint cubes; recursive algorithm

PL

arytmetyka; algorytm rekursywny; metoda spektraln

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2008
• Tom: Vol. 54, No 2
• Strony: 149--166
• Opis fizyczny: Bibliogr. 20 poz., tab.

Twórcy

autor

Lozano C. C.

autor

Falkowski B. J.

autor

Łuba T.

• Nanyang Technological University School of Electrical and Electronic Engineering, Singapore,

Bibliografia

• l. N. Abu-Khader, P. Siy: Multiple-Valued Logic Approach for a Systolic AB2 Circuit in Galois Field. 35th IEEE International Symposium on Multiple-Valued Logic, Calgary, Canada, 2005, pp. 88-93.
• 2. A. N. Al Rabadi: Reversible Logic Synthesis: From Fundamentals to Quantum Computing. Springer-Verlag, New York, 2004.
• 3. J. T. Astola, R. S. Stankovic: Fundamentals of Switching Theory and Logic Design: A Hands on Approach. Springer, Dordrecht, 2006.
• 4. H. Chang, L. Cooke, M. Hunt, G. Martin, A. McNelly, L. Todd: Surviving the SOC Revolution, a Guide to Platform-Based Design. Kluwer Academic Publishers, Boston, 1999.
• 5. M. Davio, J. P. Deschamps, A. Thayse: Discrete and Switching Functions. McGraw-Hill, New York, 1978.
• 6. E. Dubrova: Multiple-Valued Logic in VLSI: Challenges and Opportunities. 17th IEEE Norchip Conference, Oslo, Norway, 1999, pp. 340-350.
• 7. B. J. Falkowski, S. Rahardja: Efficient Computation of Quaternary Reed-Muller Expansions. IEE Proc. On Computers and Digital Techniques, vol. 142, No. 5, September, 1995, pp. 345-352.
• 8. B. J. Falkowski, C. C. Lozano, S. Rahardja: Generation of Disjoint Cubes for Multiple-Valued Functions. 37th IEEE International Symposium on Circuits and Systems, Vancouver, Canada, 2004, pp. 133-136.
• 9. B. J. Falkowski, C. C. Lozano: Quaternary Fixed Polarity Reed-Muller Expansion Computation Through Operations on Disjoint Cubes and Its Comparison with Other Methods. Computers and Electrical Engineering, An International J., vol. 31, No. 2, March, 2005, pp. 112-131.
• 10. B. J. Falkowski, C. C. Lozano, T. Luba: Efficient Algorithmfor Calculation of Quaternary Fixed Polarity Arithmetic Expansions. 37th IEEE International Symposium on Multiple-Valued Logic, Oslo, Norway, 2007, CD publication.
• 11. G. P. Gavrilov, A. A. Sapozhenko: Problems and Exercises on Course of Discrete Mathematics. Science, Moscow, 1992, in Russian.
• 12. D. H. Green: Reed-Muller Expansions with Fixed and Mixed Polarities over GF(4). IEE Proc. on Computers and Digital Techniques, vol. 137, No. 5, September, 1990, pp. 380-388.
• 13. M. Kameyama, T. Hanyu,T. Higuchi: Design and Implementation of Quaternary NMOS Integrated Circuits for Pipelined Image Processing. IEEE J. of Solid-State Circuits, vol. 22, No. 1, February, 1987, pp. 20-27.
• 14. M. G. Karpovsky, R. S. Stankovic, C. Moraga: Spectral Techniques in Binary and Multiple- Valued Switching Theory: A Review of Results in The Decade 1991-2000. 31st IEEE International Symposium on Multiple-Valued Logic, Warsaw, Poland, 2001, pp. 41-46.
• 15. S. Rahardja, B. J. Falkowski: Efficient Algorithm to Calculated Reed-Muller Expansions over GF(4). IEE Proc. on Circuits, Devices, and Systems, vol. 148, No. 6, December, 2001, pp. 289-295.
• 16. T. Sasao, M. Fujita: Representations of Discrete Functions. Kluwer Academic Publishers, Boston, 1996.
• 17. T. Sasao: Design Methods for Multiple-Valued Input Address Generators. 36th IEEE International Symposium on Multiple-Valued Logic, Singapore, 2006, CD publication.
• 18. A. Srinivasan, T. Kam, S. H. Malik, R. K.Brayton: Algorithms for Discrete Function Manipulation. 8th IEEE International Conference on Computer-Aided Design, Santa Clara, CA, USA, 1990, pp. 92-95.
• 19. S. N. Yanushkevich, D. M. Miller, V. P. Shmerko, R. S. Stankovic: Decision Diagram Techniques for Micro- andNanoelectronic Design. CRC Press, Boca Raton, 2006.
• 20. Y. Yuminaka, T. Morishita, T. Aoki, T. Higuchi: Multiple-Valued Data Recovery Techniques for Band-Limited Channels in VLSI. 32nd IEEE International Symposium on Multiple-Valued Logic, Boston, MA, USA, 2002, pp. 54-60.