A STUDY OF THE MEMORY REQUIREMENTS OF SEQUENTIAL SWITCHING CIRCUITS

Abstract

The number of elementary binary memory devices necessary for the realization of an arbitrary asynchronous sequential switching circuit is considered. The least upper bound is discovered to be approximately equal to twice the greatest lower bound. The minimum conceivable interstate transition time for a sequential circuit is the reaction time of a single memory element. A solution which achieves this minimum time is derived and its relationship to the Hamming single-error correcting code is shown. The fundamental limitations of error correction schemes which compensate for malfunctioning of memory elements are discussed. These schemes are feasible in synchronous circuits but have slightly impaired practicability in asynchronous circuits. I. MEANS FOR THE TERMINAL DESCRIPTION OF SWITCHING CIRCUITS A switching circuit has the property that binary signals appear on each of its input leads and on each of its output leads (Fig. 1). The two possible values of each variable are customarily assigned the notations 0 and 1. The meanings of these two symbols depend upon the physical nature of the binary variables represented. Thus, in one