USING HOMING, SYNCHRONIZING AND DISTINGUISHING INPUT SEQUENCES FOR THE ANALYSIS OF REVERSIBLE FINITE STATE MACHINES

Martin Lukac, Michitaka Kameyama, Marek Perkowski, Pawel Kerntopf

DOI Number
10.2298/FUEE1903417L
First page
417
Last page
438

Abstract


A digital device is called reversible if it realizes a reversible mapping, i.e., the one for which there exist a unique inverse. The field of reversible computing is devoted to studying all aspects of using and designing reversible devices. During last 15 years this field has been developing very intensively due to its applications in quantum
computing, nanotechnology and reducing power consumption of digital devices. We present an analysis of the Reversible Finite State Machines (RFSM) with respect to three well known sequences used in the testability analysis of the classical Finite State Machines (FSM). The homing, distinguishing and synchronizing sequences are
applied to two types of reversible FSMs: the converging FSM (CRFSM) and the nonconverging FSM (NCRFSM) and the effect is studied and analyzed. We show that while only certain classical FSMs possess all three sequences, CRFSMs and NCRFSMs have properties allowing to directly determine what type of sequences these machines possess.

Keywords

Reversible Logic, Finite State Machines, Testing

Full Text:

PDF

References


E. F. Moore, “Gedanken-experiments on sequential machines,” vol. 34, pp. 129–153.

A. Gill, Introduction to the Theory of Finite-state Machines. New York: McGraw-HillQ.

F. Hennie, “Fault detecting experiments for sequential circuits,” in In Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 95–110.

I. Kohavi and Z. Z. Kohavi, “Variable-length distinguishing sequences and their application to the design of fault-detection experiments,” vol. C-17, pp. 792–795.

A. D. Friedman and P. R. Menon, Fault Detection in Digital Circuits. Englewood Cliffs, NJ: Prentice-Hall, Inc.

E. P. Hsieh, “Checking experiments for sequential machines,” vol. C-20, no. 10, pp. 1152–1166.

M. N. Sokolovskii, “Diagnostic experiments with automata,” vol. 6, pp. 44–49.

S. M. Gobershtein, “Check words for the states of a finite automaton,” vol. 1, pp. 46–49.

M. Chen, Y. Choi, and A. Kershenbaum, “Approaches utilizing segment overlap to minimize test sequences,” in In Proceedings of the 10th International Symposium on

Protocol Specification, Testing and Verification, pp. 67–84.

T.-F. Lee, A. C.-H. Wu, and Y.-L. Lin, “A transformation-based method for loop folding,” vol. 13, no. 4, pp. 439–.

Z. Kohavi and N. Jha, Switching and Finite Automata Theory, 3rd edition. Cambridge University Press.

I. Pomeranz and S. Reddy, “Application of homing sequences to synchronous sequential circuit testing,” in Test Symposium, 1993., Proceedings of the Second Asian, pp.

–329.

R. L. Rivest and R. E. Schapire, “Inference of finite automata using homing sequences,” in Proceedings of the Twenty-first Annual ACM Symposium on Theory of

Computing, ser. STOC ’89. New York, NY, USA: ACM, pp. 411–420.

Y. Freund and R. Schapire, “A decision-theoretic generalization of on-line learning and an application to boosting,” vol. 55, no. 1, pp. 119 – 139. [Online]. Available:

http://www.sciencedirect.com/science/article/pii/S002200009791504X

M.-l. Chuang and C.-y. Wang, “Synthesis of Reversible Sequential Elements *,” pp. 420–425.

M. Ueda, “Optimization of reversible sequential circuits,” vol. 2, no. 6, pp. 208–214, 2010.

V. K. Siva Kumar Sastry Hari, Shyam Shroff, Sk. Noor Mahammad and E. Group, “Efficient Building Blocks for Reversible Sequential Circuit Design,” in 49th IEEE

International Midwest Symposium on Circuits and Systems, 2006, pp. 437–441.

S. Dhaarinee and N. Rajeswaran, “Implementation of Reversible Sequential Circuits Using Conservative Logic Gates,” vol. 3, no. 5, pp. 500–505, 2014.

D. S. Shubham Gupta, Vishal Pareek, “Low Cost Design of Sequential Reversible Counters,” INTERNATIONAL JOURNAL OF SCIENTIFIC & ENGINEERING RE-SEARCH,, vol. 4, no. 11, pp. 1234–1240, 2013.

M. Lukac, M. Perkowski, and M. Kameyama, “Quantum finite state machines - a circuit based approach,” International Journal of Unconvetional Computing, vol. 9, no. 3-4, pp. 267–301.

V. Singh and A. Sharma, “Implementation of Sequential Circuit using Reversible Fredkin gate on FPGA,” International Research Journal of Engineering and Technol-

ogy (IRJET), vol. 03, no. 08, pp. 1873–1878, 2016.

H. Thapliyal, S. Member, and N. Ranganathan, “Design of Testable Reversible Sequential Circuits,” vol. 21, no. 7, pp. 1201–1209, 2013.

N. Kumar, S. Wairya, and B. Sen, “Design of conservative , reversible sequential logic for cost efficient emerging nano circuits with enhanced testability,” Ain Shams Engineering Journal, 2017. [Online]. Available:

http://dx.doi.org/10.1016/j.asej.2017.02.005

M. Mohammadi, M. Eshghi, and M. Haghparast, “On Design of Multiple-Valued Sequential Reversible Circuits for Nanotechnology Based Systems,” in TENCON, 2008, pp. 1–6.

J. Pin, “On the languages accepted by finite reversible automata,” in Automata, Lan-guages and Programming, ser. Lecture Notes in Computer Science, T. Ottmann, Ed.

Springer Berlin Heidelberg, vol. 267, pp. 237–249.

J.-E. Pin, “On reversible automata,” in LATIN ’92, ser. Lecture Notes in Computer Science, I. Simon, Ed. Springer Berlin Heidelberg, vol. 583, pp. 401–416.

R. Ali, M. Gooding, T. Szilagyi, B. Vojnovic, M. Christlieb, and M. Brady, “Automatic segmentation of adherent biological cell boundaries and nuclei from brightfield microscopy images,” vol. 23, no. 4, pp. 607–621, 2011.

M. Soeken, R. Wille, C. Otterstedt, and R. Drechsler, “A Synthesis Flow for Sequential Reversible Circuits,” in 2012 IEEE 42nd International Symposium on Multiple-

Valued Logic, may 2012, pp. 299–304.

M. H. A. Khan, “Design of Reversible Synchronous Sequential Circuits Using Pseudo Reed-Muller Expressions,” IEEE Transactions on Very Large Scale Integra-

tion (VLSI) Systems, vol. 22, no. 11, pp. 2278–2286, nov 2014.

S. Gupta, “Synthesis of Sequential Reversible Circuits through Finite StateMachine,” CoRR, vol. abs/1410.2, 2014. [Online]. Available: http://arxiv.org/abs/1410.2370

N. Margolus, “Physics-like models of computation,” vol. 10, no. 1-2, pp. 81 – 95. [Online]. Available:

http://www.sciencedirect.com/science/article/pii/0167278984902525

G. Y. Vichniac, “Simulating physics with cellular automata,” vol. 10, no. 112, pp. 96 – 116. [Online]. Available:

http://www.sciencedirect.com/science/article/pii/0167278984902537

K. Morita, Handbook of Natural Computing. Springer Berlin Heilderberg, ch. Reversible Cellular Automata, pp. 231–257.

——, “Reversible computing and cellular automata a review,” vol. 395, pp. 101–131.

——, “Reversible computing systems, logic circuits and cellular automata,” in Proceedings of the 3rd International Conference on Networking and Computing, pp. 1–8.

S. Wolfram, A New Kind of Science. Wolfram Media Inc.

B. Anuradha and S. Sivakumar, “A Fault Analysis in Reversible Sequential Circuits,” IOSR Journal of VLSI and Signal Processing, vol. 4, no. 2, pp. 36–42, 2014.

Z. Kohavi, Switching and Finite Automata Theory. Mc Graw-Hill.


Refbacks

  • There are currently no refbacks.


ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626