1
$\begingroup$

I'm looking to use something close to the following as a definition for a circuit class. This is obviously semi-informal. I am curious if any one sees any potential problems with it, or where something in it's informal nature can potentially be a problem when it is tightened up to something more formal. Also, I'm not aware of any vetted and accepted circuit class "like this", so pointers to something I missed are welcome as well. In particular, the use of time is critically important to what I'm working on. TIA.

The circuit class TLU, or Table Look Up, is defined as taking $n \ge 1$ $\{0,1\}$ inputs that produces a single $\{0,1\}$ output.

An individual $n$ input TLU gate is defined as an indexed array of $\{0,1\}^{2^n}$, where $n$ represents the index that selects a particular $\{0,1\}$ from the array. For example, $\{1,1,1,0\}$ would represent the common $\text{NAND}$ gate. An individual $n$ input TLU gate has a depth of $1$, a gate count of $1$, and takes atomically $O\left(1\right)$ time to produce an output from a given input. For each $n$ input TLU gate set, there are $2^{2^n}$ possible indexed arrays. All TLU gates advance in time atomically with respect to all other TLU gates.

For some large value of $n$, one may wish to map a large $n$ input TLU gate to a set of $\lt n$ input TLU gate primitives. A common example would be the set of $\le 2$ input $\{\text{AND}, \text{OR}, \text{NOT}\}$ gates. In The synthesis of two-terminal switching circuits, Shannon proved maximum worst case bounds for gates and depth for the $\{\text{AND}, \text{OR}, \text{NOT}\}$ set. This result can be extended to make the following claim: As long as the set of primitives contains a complete boolean basis, there is guaranteed to be a maximum worst case bounds for gates and depth for that set of primitives.

Improve this question
$\endgroup$
12
  • $\begingroup$ I'm not sure I understand what you mean by "maximum worst case bound"? In what sense would such a bound not exist? $\endgroup$
    – mhum
    Jan 4, 2011 at 2:54
  • $\begingroup$ When the set of primitives to reduce to does not contain a complete boolean basis. $\endgroup$
    – johne
    Jan 4, 2011 at 10:10
  • $\begingroup$ I'm sorry, but I'm afraid I may still be having trouble understanding your question. Is the question something like "If the set of primitive, k-input gates (where k is a constant independent of n) contains a complete boolean basis (presumably of the space of k-input boolean functions), then every n-input boolean function can be computed by a circuit using these gates?" Is that what is meant by "maximum worst case bound"? $\endgroup$
    – mhum
    Jan 4, 2011 at 16:14
  • $\begingroup$ Sorry, perhaps you're more familiar with the term Functionally Complete. For example: $\{NAND\}$, $\{NOR\}$, $\{AND, NOT\}$, $\{OR, NOT\}$, $\{AND, OR, NOT\}$, $\{IMPLIES, NOT\}$, etc, but not $\{AND\}$, $\{OR\}$, $\{XOR\}$. See also Boolean algebras canonically defined. $\endgroup$
    – johne
    Jan 4, 2011 at 17:36
  • 1
    $\begingroup$ Ok, I think In understand now. Couldn't you simply use your new basis to simulate AND/OR/NOT to establish a bound? For example, if you can compute AND, OR, and NOT with at most $c$ gates from your new basis, then $c \lambda(n)$ is an upper bound on how many gates you'll need, where $\lambda(n)$ is defined as before. Similarly, if you can compute AND, OR, and NOT with in at most depth $d$ using your new gates, then $d \mu(n)$ is a bound on depth (with $\mu(n)$ as defined in the paper). $\endgroup$
    – mhum
    Jan 4, 2011 at 20:52

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.