Specification in XDI model.
.
(Not available for general k)
Parameterized definitions are not possible in VERDECT,
but this sketch gives the general idea:
Specification in Verdect:
define TOGGLE( a?, b0!, .., b(k1)! ) =
pref *[ a?; b0!; .. ; a?; b(k1)! ]
end
Also available through this link
Pure DI Algebra does not allow a generalized specification.
The following specification therefore needs
instantiation before interpretation:
Specification in DI Algebra:
T(k) = T(k,0)
where
T(k,i) = a?; bi!; T(k,(i+1) mod k)
Also available through this link.
The specification of the case k=3 is as follows:
Specification in DI Algebra:
# Generated by expexp.pl
NAME ="T"
I = { a? }
O = { b0!, b1!, b2! }
T_0_3 = a?; b0!; T_1_3
T_1_3 = a?; b1!; T_2_3
T_2_3 = a?; b2!; T_0_3
Also available through this link.
XDI Report for the case k=3.
(Not available for general k)
T_{k}(a; b_{0}, b_{1}...,
b_{k1)} /
a b_{0} =
T_{k}(a; b_{1}, ...,
b_{k1}, b_{0})
The kToggle satisfies Rules Y' and Z'.
DI Decompositions

A kToggle with k=1
is a Wire.

A kToggle with k=2
is a Toggle.

A kToggle can be implemented as a small
state machine
using a Latch
by feeding output i to input (i+1) mod k
(cf. Toggle Implementations).

For m>0 and n>0,
a kToggle with k=mn
can be implemented with one
kToggle with k=m
and m
kToggles with k=n
[ZoomFIG]
 For k>0,
a kToggle with k=m can be implemented by
feeding back one output, say b_{k},
of a kToggle with k=m+1
with a Merge:
[ZoomFIG]
 By suitably combining implementation schemes 2, 4 and 5
one can obtain implementations of
kToggles
for arbitrary k>0,
in terms of Toggles and
Merges.
When k is a power of 2, only scheme 4 is needed
(the result does not depend on whether
kToggles with k=2
are introduced `on the left' or `on the right':
the scheme is commutative for powers of 2 constructed in this way).
The implementation of
a kToggle with k=2^m
requires 2^m1 Toggles (no Merges).
When k is not a power of 2 (hence, k>2),
also scheme 5 is needed.
In this case,
the resulting implementation does depend on the order.
For instance, consider the implementation of
a kToggle with k=5.
One can start with
a kToggle with k=8.
to reduce it to
a kToggle with k=5.
This results in an implementation with
7 Toggles and
3 Merges.
Alternatively,
we can first implement
a kToggle with k=3
by reducing
a kToggle with k=4
once according to scheme 5.
This costs three Toggles and
one Merge.
Using scheme 4, the
kToggle with k=3
can be made into
a kToggle with k=6
by adding three Toggles `on the right'.
The kToggle with k=6
can then be reduced to
a kToggle with k=5
This implementation consists of
6 Toggles and
2 Merges.
Using scheme 4 to make
a kToggle with k=6
from one Toggle (`on the left') and
two kToggles with k=3
results in yet another implementation, costing
7 Toggles and
3 Merges.
Theorem: When constructing
a kToggle with
t Toggles and
m Merges we must have
k=tm+1 and,
hence, t>=k1.

For m>0, n>0, and m and n relatively
prime,
a kToggle with k=mn
can be implemented with one
kToggle with k=m,
one kToggle with k=n, and
a DecisionWait:
[ZoomFIG]
Using Boolean Gates
No information available
Using Transistors
No information available
The kToggle can be further generalized to
a LPattern Generator
that cycles through an arbitrary pattern over its outputs.
A kToggle is a
(b_{0}...b_{k1})Pattern Generator.
In [Ebergen89, p. 140],
a decomposition of
a kToggle with k=3
is presented.
Exercise:
What is an optimal implementation scheme
for
kToggles
in terms of Toggles and
Merges.
The cost function can either be size or `average response time'.
[Ebergen89, p. 140]
Last modified at Fri Nov 20 10:11:40 1998
Encyclopaedia of DelayInsensitive Systems
Copyright © 19951998
Tom Verhoeff /
Tom.Verhoeff@acm.org