View source for Combinatorial devices

Lifting a definition from Ward and Halstead's ''Computation Structures'' (ISBN 0-262-23139-5), pp4--5:<blockquote>A combinatorial device is a circuit element have the following properties:
* One or more discrete-valued ''input'' terminals;
* One or more discrete-valued ''output'' terminals;
* A ''functional specification'', detailing the value of each output for each of the possible combinations of input values; and
* A ''timing specification'', consisting (at minimum) of an upper bound ''t''<sub>pd</sub> on the time required for the device to compute the specified output values from an arbitrary set of input values.</blockquote>
''t''<sub>pd</sub> is known as the ''propagation delay'' of a device, and interpreted as a maximum time before outputs reflect the provided inputs (a minimum delay, if specified, is known as ''contamination delay''). Thus, inputs provided and maintained for ''t'' seconds can be read for at least ''t'' - ''t''<sub>pd</sub> seconds. Combinatorial devices are closed under combinatorial composition:<blockquote>A circuit is a combinatorial device if it consists of interconnected circuit elements such that:
* Each circuit element is itself combinatorial,
* Every node of the circuit is either designated as an input to the circuit or connects to exactly one output terminal of the circuit element, and
* The circuit contains no directed cycles.</blockquote>
Each output of a composed combinatorial device has its own ''t''<sub>pd</sub>, equal to the maxmium cumulative propagation delays encountered on any path from an input to that output.
[[CATEGORY: Hardware]]