Check out my first novel, midnight's simulacra!
Combinatorial devices: Difference between revisions
(Created page with '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 p...') |
No edit summary |
||
| Line 4: | Line 4: | ||
* A ''functional specification'', detailing the value of each output for each of the possible combinations of input values; and | * 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> | * 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> | ||
Combinatorial devices are closed under combinatorial composition:<blockquote>A circuit is a combinatorial device if it consists of interconnected circuit elements such that: | ''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, | * 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 | * 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> | * 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. | |||
Revision as of 19:32, 22 March 2010
Lifting a definition from Ward and Halstead's Computation Structures (ISBN 0-262-23139-5), pp4--5:
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 tpd on the time required for the device to compute the specified output values from an arbitrary set of input values.
tpd 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 - tpd seconds. Combinatorial devices are closed under combinatorial composition:
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.
Each output of a composed combinatorial device has its own tpd, equal to the maxmium cumulative propagation delays encountered on any path from an input to that output.
