Digital Switching and Finite Automata Theory (BEC515B)

Digital Switching and Finite Automata Theory

Course Code BEC515B 
CIE Marks 50
Teaching Hours/Week (L:T:P:S) 3:0:0:0 
SEE Marks 50
Total Hours of Pedagogy 42 
Total Marks 100
Credits 3 
Exam Hours 3

Module-1

Logic design: Design with basic logic gates, Logic design with integrated circuits, NAND and NOR

circuits, Design of high-speed adders, Metal-oxide semiconductor (MOS) transistors and gates(5.1 to

5.6 of Text1) Threshold Logic: Introductory Concepts: Threshold element, capabilities and limitations

of threshold logic, Elementary Properties, Synthesis of Threshold networks: Unate functions,

Identification and realization of threshold functions, The map as a tool in synthesizing threshold

networks. (Sections 7.1, 7.2 of Text 1)

Module-2

Testing for Combinational circuits

Fault models, Structural testing, IDDQ testing, Delay fault testing, Synthesis for testability, Testing

for nanotechnologies (8.1 to 8.6 of Text1)

Module-3

Finite-state machines: Introduction to synchronous sequential circuits and iterative networks,

Sequential circuits – introductory example, The finite-state model – basic definitions, Memory

elements and their excitation functions, Synthesis of synchronous sequential circuits, An example of a

computing machine, Iterative networks (9.1 to 9.6 of Text1)

Capabilities, minimization, and transformation of sequential machines

The finite-state model – further definitions, Capabilities and limitations of finite-state machines

State equivalence and machine minimization, Simplification of incompletely specified machines (10.1

to 10.4 Text1)

Module-4

Asynchronous sequential circuits: Modes of operation, Hazards, Synthesis of SIC fundamental-mode

circuits. Structure of Sequential Machines: Introductory example, State assignment using partitions:

closed partitions, The lattice of closed partitions, Reduction of output dependency, Input dependence

and autonomous clocks, Covers and generation of closed partitions by state splitting: Covers, The

implication graph, An application of state splitting to parallel decomposition. (Section 11.1, 11.2, 11.3,

12.1, 12.2, 12.3, 12.4, 12.5, 12.6 of Text1 )

Module-5

Memory, definiteness, and information loss lessness of finite automata

Memory span with respect to input–output sequences (finite-memory machines), Memory span with

respect to input sequences (definite machines), Memory span with respect to output sequences,

Information-lossless machines(14.1 to 14.4 of Text1)

Suggested Learning Resources:

Text Books:

1. Switching and Finite Automata Theory – Zvi Kohavi and Niraj K. Jha, Cambridge University

press, 3rd edition, 2010.

Reference Books:

2. Introduction to switching theory and logic design Fredriac J. Hill, Gerald Peterson, 3rd edition,

3. Fault Tolerant and Fault Testable Hardware Design-Parag K Lala, Prentice Hall Inc. 1985.

4. Digital Circuits and Logic Design. -Charles Roth Jr, Larry L. Kinney, Cengage Learning, 2014,

ISBN: 978-1-133-62847-7.