A Modern Approach to the Asynchronous Sequential Circuit Synthesis

• Autorzy: Czekalski P. , Tokarz K. , Pochopień B.

Warianty tytułu

PL

Synteza asynchronicznych układów cyfrowych : nowe horyzonty

• Języki publikacji: EN

Abstrakty

EN

This paper presents novel approach to the Huffman’s asynchronous sequential circuit two valued Boolean switching system design. The algorithm is implemented as software using distributed, service oriented application model with means of the web service component design. It considers method implementation challenges, both towards Moore and Mealy structures with particular respect to the estimation of the Huffman’s minimization algorithm computational complexity. The paper provides implementation details, theoretical model estimation and experimental results that acknowledge the theoretical approach in practice. This paper also examine the multistep design process implementation and its problems inherent in web service based environment both for development and educational purposes.

PL

Synteza asynchronicznych układów cyfrowych w logice szytej, bazująca na dwuwartościowej algebrze Boole’a, doczekała się licznych modeli i metod implementacji. Najpopularniejsze z nich to metoda Huffmana [2] oraz metoda Tablicy Kolejności Łączeń [3]. Metody te, jakkolwiek powstały w połowie XX wieku, są stosowane również obecnie, zarówno w procesie projektowania przemysłowego jak i w edukacji [10][11][14]. Metoda Huffmana pozwala na syntezę układów o strukturach Moore’a (Fig.1) i Mealy’ego (Fig.2). Proces projektowania z wykorzystaniem metody Huffmana jest wieloetapową metodą o deterministycznym przebiegu. W niniejszym opracowaniu przedstawiono nowatorskie podejście do zagadnienia automatycznego projektowania cyfrowych układów asynchronicznych, bazujące na wytworzeniu oprogramowania o budowie komponentowej oraz z zastosowaniem zunifikowanej komunikacji w sieci WEB z wykorzystaniem protokołu SOAP. Na podstawie teoretycznego modelu opracowano rozwiązanie programowe, składające się z bezstanowego serwisu obliczeniowego oraz aplikacji sieciowej WWW, która służy, jako interfejs użytkownika dla usługi obliczeniowej. W zastosowaniach edukacyjnych przewidziano zwracanie szczegółowych informacji z wszystkich etapów syntezy układów metodą Huffmana, co umożliwia ich wizualizację oraz poruszanie się po nich w przód i w tył, w celu prezentacji zależności i sposobu działania, co stanowi również element zdalnego nauczania - aplikacja WWW jest bowiem widoczna w globalnej sieci Internet (adres znajduje się w Appendix A). Ponieważ metoda Huffmana udostępnia wyniki w postaci zredukowanej i zakodowanej siatki bloku pamięci i bloku kombinacyjnego wyjściowego, serwis obliczeniowy korzysta z uprzednio przygotowanej, zewnętrznej usługi, implementującej funkcjonalność minimalizacji funkcji Boolowskiej metodą Kazakowa. W ramach prowadzonych badań przeanalizowano teoretyczną, pesymistyczną złożoność obliczeniową poszczególnych etapów metody Huffmana, a także łączną, pełną złożoność obliczeniową metody, w szczególności względem liczby sygnałów wejściowych, liczby stanów wewnętrznych oraz liczby sygnałów wyjściowych, otrzymując pełny model złożoności obliczeniowej metody Huffmana. Przeprowadzono szereg eksperymentów, aby potwierdzić oszacowaną teoretycznie złożoność obliczeniową w sposób doświadczalny (Tab. 2-4). Przeprowadzone eksperymenty potwierdziły zgodność z teoretycznie wyznaczonym modelem złożoności obliczeniowej, zarówno dla układów Moore’a jak i Mealy’ego (Tab. 5, Fig. 5 i 6). Na potrzeby sformalizowania zapisu wykresu czasowego opracowano gramatykę zapisu przełączania sygnałów (Appendix B). Stanowi ona format wewnętrzny danych wejściowych dla usługi obliczeniowej implementującej metodę Huffmana.

Słowa kluczowe

EN

logic circuits; automatic control; web service

PL

układy logiczne; kontrola automatyczna; serwis internetowy

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2014
• Tom: Vol. 26, No. 1-2
• Strony: 25--37
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Czekalski P.

• Institute of Informatics Silesian University of Technology ul. Akademicka 16, Gliwice, Poland

autor

Tokarz K.

• Institute of Informatics Silesian University of Technology ul. Akademicka 16, Gliwice, Poland

autor

Pochopień B.

• Institute of Informatics Silesian University of Technology ul. Akademicka 16, Gliwice, Poland

Bibliografia

• [1] M. Karnaugh: The Map Method for Synthesis of Combinational Logic Circuits.,in Transactions of the American Institute of Electrical Engineers part I, 72(9), pp. 593–599,1953.
• [2] D. A. Huffman: The Synthesis of Sequential Switching Circuits., in Journal of The Franklin Institute, 257(3-4), 1954.
• [3] J. Siwiński: Układy przełączające w automatyce., WNT, 1968.
• [4] V. D. Kazakov: Minimalizacija łogiczeskich funkcji bolszogo czisła pieriemiennych. In Awtomatika i Telemechanika., 9, 1962.
• [5] P. Kerntopf, A. Michalski: Wybrane zagadnienia syntezy kombinacyjnych układów logicznych. PWN, 1972.
• [6] E. J. McCluskey Jr.: Introduction to the Theory of Switching Circuits., McGraw-Hill Book Co., 1965.
• [7] E. J. McCluskey Jr.: Minimization of the Boolean Functions., Bell Systems Tech. J., pp. 1417-1444, 1956.
• [8] M. V. Quine: The Problem of Simplifying Truth Functions., in Amer. Math. Monthly, 59, pp. 521-531, 1952.
• [9] R. Brayton, G.D. Hachtel, L. Hemanchandra, R. Newton, A. Sangiovanni-Vincentelli: A Comparison of Logic Minimization Strategies Using ESPRESSO: An APL Program Package for Partitioned Logic Minimization. in Proc. of the Int. Symposium on Circuits and Systems, Rome, pp. 42-48, 1982.
• [10] H. Kamionka-Mikuła., H. Małysiak, B. Pochopień: Teoria układów cyfrowych, T. I. Układy kombinacyjne, T. II. Układy sekwencyjne. Wydawnictwo Politechniki Śląskiej, 2013.
• [11] U. Stańczyk, K. Cyran, B. Pochopień: Theory of logic circuit. Vol. 1. Fundamental issues.Vol. 2. Circuit design and analysis. Silesian University of Technology, 2007.
• [12] World Wide Web Consortium, SOAP Specification. W3C, 2004. [Online]. Available:http://www.w3.org/TR/soap/
• [13] P. Mroczkowski: System ZMITACSim – Implementacja metody Huffmana dla układów Moore’a i Mealy’ego. M.S. Thesis, Dept. Aut. Control, Electron. and Comp. Science, Silesian University of Technology, 2013.
• [14] T. Łuba: Synteza układów logicznych. Oficyna Wydawnicza Politechniki Warszawskiej, 2005.
• [15] R. Fuhrer, M. Nowick: Sequential Optimization of Asynchronous and Synchronous Finite-State Machines. Kluwer, Boston, 2001.
• [16] J. Brzozowski, C. Seger: Asynchronous Circuits. Springer Verlag, New York 1995.
• [17] C. J. Myers: Asynchronous Circuit Design. John Wiley and Sons, New York 2001.
• [18] S. H. Unger: Asynchronous Sequential Switching Circuits. Wiley-Interscience, New York,1969.
• [19] B. Sheikh, R. Manohar: An Operand-Optimized Asynchronous IEEE 754 Double-Precision Floating-Point Adder. in Proc. of the 2010 IEEE Symp. on Async. Circuits and Systems, Grenoble, pp. 151-162, 2010.
• [20] N. Jamadagni, J. Ebergen: An Asynchronous Divider Implementation. in Proc. of the 2012 IEEE 18th Int. Symp. on Async. Circuits and Systems, Lyngby, pp. 97-104, 2012.
• [21] T. Liu, J. Rabaey: Statistical Analysis and Optimization of Asynchronous Digital Circuits. In Proc. of the 2012 IEEE 18th Int. Symp. on Async. Circuits and Systems, Lyngby, pp. 1-8,2012.
• [22] N. Onizawa, W. Gross, T. Hanyu: A Low-Energy Variation-Tolerant Asynchronous TCAM for Network Intrusion Detection Systems. in Proc. of the 2013 IEEE 19th Int. Symp. on Async. Circuits and Systems, Santa Monica (CA), pp. 8-15, 2013.
• [23] M. Davies, A. Lines, J. Dama et al.: A 72-Port 10G Ethernet Switch/Router Using Quasi-Delay-Insensitive Asynchronous Design. in Proc. of the 2014 IEEE 20th Int. Symp. on Async.Circuits and Systems, Potsdam, pp. 103-104, 2014.