Variable length shift register

A programmable computer shift register or other time delay means of variable length that provides time delays that are integral multiples of a predetermined time delay unit .DELTA.t, that uses relatively few switches, that controls time delays introduced by passage of signals through multiple-state switches that are in different states.

FIELD OF THE INVENTION 
This invention relates to computer shift registers whose length is 
variable. 
BACKGROUND OF THE INVENTION 
Time delay elements or shift registers are easily fabricated in integrated 
circuit technology. An input signal, delivered to the input terminal of a 
shift register, will not appear at the output terminal of the shift 
register until one cycle of the applicable clock has occurred. If one 
strings together a series of n such shift register modules, as illustrated 
in FIG. 1 where n=5, a signal, delivered to the input terminal of a first 
register D.sub.1 will appear n clock cycles later at the output terminal 
of register D.sub.n. Substantially all of the shift registers or delay 
lines built and offered for sale by various manufacturers have a fixed 
length or time delay, usually ranging from a time delay of as low as eight 
time units to as high as many thousands of time units. 
A shift register or delay line that has a programmable length that varies 
over a sequence of times n.DELTA.t, wherein equals 1,2, . . . ,N, would be 
a useful component in the design of general purpose and special purpose 
computers. FIG. 2 illustrates one straightforward approach to provision of 
such a switch register. If switch SW1 is closed and all other switches are 
open, the output signal will be delayed one time unit .DELTA.t relative to 
the input signal. If switch SW5 is closed and all other switches are open, 
the output signal will be delayed by a time 5.DELTA.t relative to the 
input signal, for example. 
This variable delay shift register is straightforward and easy to 
understand, but it carries with it certain problems. First, for a shift 
register of maximum length N, where N is a positive integer, N switches 
are needed to implement this shift register. This introduces a significant 
amount of additional circuitry and logic to select which switch is to be 
closed. Second, the output signal from each time delay element or shift 
register module must be routed to two places; to the input of the next 
time delay element, which is easy to do, and to the switch matrix, which 
may be much more difficult. This carries with it a chip area penalty and 
forces a substantial increase in cost for such a shift register vis-a-vis 
a standard, fixed length shift register. Third, the output terminal is 
connected to N switches. Although only one of these switches is in the 
"on" position, the remaining N-1 "off" switches represent a significant 
parasitic load that would limit the performance of such a shift register. 
One example of this approach is disclosed in U.S. Pat. No. 4,330,750, 
issued to Mayor for "Variable Delay Circuits." 
FIG. 3 illustrates another approach to a variable length shift register 
from the prior art that allows time delays from .DELTA.t to 32.DELTA.t in 
integral multiples of the unit .DELTA.t. For example, with (only) switches 
SW1, SW2, SW3, SW4 and SW5 activated so that bypasses 1, 2 and 3 are not 
used but the remaining bypasses are used, the total delay would be 
.DELTA.t+2.DELTA.t+4.DELTA.t=7.DELTA.t. As another example, if switches 
SW2, SW3, SW6 and SW7 are activated so that bypasses number 2 and number 4 
are not used, the corresponding time delay is 
2.DELTA.t+8.DELTA.t=10.DELTA.t. All combinations of times from .DELTA.t to 
32.DELTA.t may be implemented using the prior art device shown in FIG. 3. 
For a maximum time delay of M=2.sup.K time units .DELTA.t, (K=1,2,3, . . . 
) precisely 2K switches are needed; K=5 in the example shown in FIG. 3. 
Where a combination of time delays up to 1024.DELTA.t= 2.sup.10 .DELTA.t, 
twenty switches would be required. The device shown in FIG. 3 offers a 
more compact implementation of a variable length shift register, using a 
reduced number of switches. A configuration incorporating the technique of 
FIG. 3 is disclosed in U.S. Pat. No. 4,016,511, issued to Ramsey and Post 
for a "Programmable Variable Length High Speed Digital Delay Line." 
However, certain disadvantages are evident from the configuration 
illustrated in FIG. 3. First, the individual switches are more complex 
because, for example, switches SW2 and SW3 must work in unison. Second, 
implementation of the switches will cause each switch to have its own 
characteristic time delay, and the time delay (for passage through the 
switch itself) may be different for a switch in the activated or in the 
inactivated state. This will introduce variable incremental time delay (a 
fraction of .DELTA.t) on top of the variable time delay sought by use of 
the apparatus shown in FIG. 3. Third, if the length of the shift register 
is changed during operation of the device ("on the fly"), it is a matter 
of some complexity to determine the number of clock cycles required before 
the device has cleared itself for subsequent operation. 
An interesting variation on this general approach is disclosed by U.S. Pat. 
No. 4,530,107, issued to Williams for a "Shift Register Delay Circuit," 
wherein one set of registers is used to determine coarse time delay 
(integral time units) and a second set of registers is used to determine 
fine time delay (fractions of a time unit). 
SUMMARY OF THE INVENTION 
The invention provides a variable length shift register for time delay of 
signals that uses a reduced number of switches and does not require 
coordination of the states of two or more switches. 
Other objects of the invention and advantages thereof will become clear by 
reference to the detailed description and the accompanying drawings. 
The objects of this invention may be realized in accordance with the 
invention in one embodiment by: 
a first time delay means having an input terminal, a clock input terminal, 
an output terminal and having a first plurality of programmable switch 
means, for producing a time delay of any of the lengths .DELTA.t, 
2.DELTA.t, 3.DELTA.t, . . . , M.DELTA.t, where M is a predetermined 
positive integer, by programming of the first plurality of programmable 
switch means, where each of the programmable switch means has a first 
state and a second state and where the signal to be time delayed is 
received at the input terminal of the first time delay means; 
a second time delay means having an input terminal, a clock input terminal, 
an output terminal and a second plurality of programmable switch means, 
for producing a time delay of any of the lengths 0, M.DELTA.t, 2M.DELTA.t, 
. . . , (N-1)M.DELTA.t, where N is a predetermined positive integer, where 
each programmable switch means has a first state and a second state, where 
the input terminal of the second time delay means is connected to the 
output terminal of the first time delay means, where the time delayed 
signal is issued at the output terminal of the second time delay means, 
and where precisely one of the first plurality of programmable switch 
means and one of the second plurality of programmable switch means is in 
the first state for any operation of the apparatus; and 
a source of periodic clock pulses having a clock cycle of length 
substantially .DELTA.t that is connected to the clock input terminal of 
each of the first time delay means and the second time delay means. 
The objects of this invention may be realized in accordance with this 
invention in a second embodiment by: 
a first time delay means having an input terminal, a clock input terminal, 
an output terminal and a first plurality of programmable switch means, for 
producing a time delay of any of the lengths 0, .DELTA.t, 2.DELTA.t, . . . 
, M.DELTA.t by programming of the first plurality of programmable switch 
means, where each programmable switch means has a first state and a second 
state and where the signal that is to be time delayed is received at the 
input terminal; 
a second time delay means having an input terminal, a clock input terminal, 
an output terminal and a second plurality of programmable switch means, 
for producing time delays of any of the lengths (M+1).DELTA.t, 
2(M+1).DELTA.t, . . . , N(M+1).DELTA.t by programming of the second 
plurality of programmable switch means, with each programmable switch 
means having a first state and a second state, where the input terminal of 
the second time delay means is connected to the output terminal of the 
first time delay means, where the signal that is to be time delayed issues 
from the output terminal of the second time delay means, and where at most 
one programmable switch means from the first plurality and precisely one 
programmable switch means from the second plurality is programmed to be in 
the first state for any operation of the apparatus; and 
a source of periodic clock pulses having a clock cycle of length 
substantially of .DELTA.t that is connected to the clock input terminals 
of the first time delay means and the second time delay means.

DETAILED DESCRIPTION 
FIG. 4 illustrates one embodiment of the invention, wherein a shift 
register of variable length .DELTA.t, 2.DELTA.t, 3.DELTA.t . . . , 
16.DELTA.t is provided using seven two-state switches that are not 
coordinated with one another, as would be required in the device shown in 
FIG. 3. For example, if one desires a time delay of 1166 t, switch SW1 
would be set in the "on" position, switches SW2 and SW3 would be set in 
the "off" position, switches SW'1, SW'2 and SW'4 would be set in the "off" 
position and switch SW'3 would be set in the "on" position to produce a 
total time delay of 
.DELTA.t+.DELTA.t+.DELTA.t+4.DELTA.t+4.DELTA.t=11.DELTA.t as desired. 
In a more general approach using this embodiment, one would provide a first 
module having a linear array of 2.sup.n.sbsp.1 time delay units connected 
together, each of which introduces a time delay .DELTA.t; and one would 
provide 2.sup.(n.sbsp.2.sup.-n.sbsp.1.sup.) -1 additional modules, with 
each such module having a linear array of 2.sup.n.sbsp.1 time delay units 
connected together therein. The entire configuration would then provide 
variable length time delays .DELTA.t, 2.DELTA.t, 3.DELTA.t, . . . , 
2.sup.n.sbsp.2 .DELTA.t, as illustrated in FIG. 5. The configuration shown 
in FIG. 5 requires 2.sup.(n.sbsp.2.sup.-n.sbsp.1.sup.) +2 two-state 
switches and 2.sup.n.sbsp.2 time delay units to implement this shift 
register. For the particular configuration shown in FIG. 4, n.sub.2 =4, 
n.sub.1 =2 and seven switches are required. In order to minimize the total 
number of switches needed, one would choose n.sub.1 =n.sub.2 /2 or 
(n.sub.2 .+-.1)/2 according as n.sub.2 is an even integer or an odd 
integer. In the embodiment shown generally in FIG. 5 one has: (1) 
2.sup.n.sbsp.1 first input positions, each being separated by one time 
unit (.DELTA.t) of delay; and (2) 2.sup.(n.sbsp.2.sup.-n.sbsp.1.sup.) -1 
second input positions, each being separated by 2.sup.n.sbsp.1 units of 
time delay. 
The general embodiment shown in FIG. 5 uses a linear array of 
2.sup.n.sbsp.2 individual time delay units D, where n.sub.2 is an integer 
greater than or equal to 2. A first module, comprises 2.sup.n.sbsp.1 time 
delay units D, numbered k.sub.1 =1,2,3, . . . ,2.sup.n.sbsp.1 and arranged 
linearly so that the output terminal of unit k.sub.1 is adjacent to the 
input terminal of delay unit k.sub.1 +1 for k.sub.1 =1, 2, . . . , 
2.sup.n.sbsp.1 -1. A two-state switch SW k.sub.1 connects the input 
terminal of delay unit k.sub.1 +1 to either the output terminal of delay 
unit k.sub.1 (the "off" state) or to the input terminal of the apparatus 
(the "on" state) for k.sub.1 =1, 2, . . . , 2.sup.n.sbsp.1 -1. The input 
terminal of time delay unit k.sub.1 =1 is directly connected to the input 
terminal of the apparatus. The remaining time delay units in the apparatus 
are arranged in modules numbered r=2, 3, . . . , 
2.sup.(n.sbsp.2.sup.-n.sbsp.1.sup.), each module having a linear array of 
2.sup.n.sbsp.1 time delay units D, where the individual time delay units 
for module r are numbered k.sub.r =1, 2, . . , 2.sup.n.sbsp.1 for 
convenient reference. Within module r=2, 3, . . . , 
2.sup.(n.sbsp.2.sup.-n.sbsp.1.sup.), the output terminal of time delay 
unit no. k.sub.r is connected to the input terminal of time delay unit no. 
k.sub.r +1 for k.sub.r =1, 2, . . . , 2.sup.(n.sbsp.2.sup.-n.sbsp.1.sup.) 
-1; and the terminal of time delay unit no. k.sub.r =2.sup.n.sbsp.1 of 
module r=2, 3, . . . ,2.sup.(n.sbsp.2.sup.-n.sbsp.1.sup.) -1 is connected 
to the input terminal of time delay unit no. k.sub.r+1 =1 of module r+1. 
The output terminal of time delay unit no. k.sub.r =2.sup.n.sbsp.1 of 
module r=2, 3, . . . ,2.sup.(n.sbsp.2.sup.-n.sbsp.1.sup.) is connected to 
the output terminal of the apparatus by a two-state switch SW'(r+1); a 
first state of the switch provides a direct connection of the input 
terminal of that time delay unit to the apparatus output terminal; and a 
second state of the switch breaks or disrupts this direct connection so 
that no signal can flow directly from the said input terminal to the 
apparatus output terminal. A switch SW'2 that is substantially identical 
to the other switches SW' connects the input terminal of time delay unit 
k.sub.r =1 in the second module (r=2) to the output terminal of the 
apparatus. Finally, each time delay unit D receives a clock signal at its 
clock input terminal. The embodiment shown in FIG. 5 can provide time 
delay of a signal entering the apparatus input terminal by amounts 
.DELTA.t, 2.DELTA.t, 3.DELTA.t, . . . , 2.sup.n.sbsp.2 .DELTA.t, if the 
cycle of the clock signal has length .DELTA.t. The total number of 
switches required, 2.sup.(n.sbsp.2.sup.-n.sbsp.1.sup.) +2.sup.n.sbsp.1, is 
minimized with the choice n.sub.1 .apprxeq.n.sub.2. 
The embodiment shown generally in FIG. 5 provides a variable length shift 
register with reduced requirements for the number of switches so that both 
chip size and cost are lowered correspondingly. Second, for any length 
.DELTA.t, 2.DELTA.t, . . . , 2.sup.n.sbsp.2 .DELTA.t, one or at most two 
switches are in the "on" position between the input terminal and the 
output terminal, one in module no. 1 and one in the collection of other 
modules. This produces a uniform time delay due to passage through the 
switch element itself. Third, the state of the shift register is easily 
determined and is predictable when the shift register length is changed 
from one value to another. 
Another general embodiment is shown in FIG. 6 and comprises a linear 
arrangement of M individual time delay units D (numbered 1, 2, . . . ,M), 
each with associated time delay .DELTA.t, together with N-1 time delay 
modules D.sub.M (numbered 2, 3, . . . ,N), each with associated time delay 
M.DELTA.t. The individual time delay units D and time delay modules 
D.sub.M each have an input terminal, a clock input terminal and an output 
terminal. With reference to the individual time delay units D, a two-state 
switch SWk similar to the switches SW in FIG. 5 connects the input 
terminal of delay unit k+1 to either the input terminal of the apparatus 
(the "on" or first state) or to the output terminal of individual time 
delay unit k (the "off" or second state) for k=1,2, . . . ,M-1. The input 
terminal of time delay unit (D) number k=1 is directly connected to the 
input terminal of the apparatus. With reference to the time delay modules 
D.sub.M , the output terminal of module m=2,3, . . . ,N is connected to 
the output terminal of the apparatus by a two-state switch SW'm that 
provides a direct connection to the apparatus output terminal in one 
position (first state) and provides a broken or disrupted connection in a 
second state; a similar switch SW'1 connects the output terminal of 
individual time delay unit (D) number k=M to the apparatus output 
terminal. Individual time delay unit (D) number k=M is directly connected 
to the input terminal of time delay module (D.sub.M) number m=2, and the 
output terminal of time delay module m is directly connected to the input 
terminal of time delay module m+1 for m=2, 3, . . . , N-1. The individual 
time delay units D and the time delay modules D.sub.M all receive a clock 
signal from a clock source CLK at their respective clock input terminals. 
The embodiments shown in FIGS. 5 and 6 may be realized more generally by a 
first module with first programmable switch means that produces a time 
delay of .DELTA.t, 2.DELTA.t, 3.DELTA.t, . . . , M.DELTA.t, connected to a 
second module with second programmable switch means that produces a time 
delay of 0, M.DELTA.t, 2M.DELTA.t, 3M.DELTA.t, . . . , (N-1)M.DELTA.t, 
where M and N are predetermined positive integers with N.gtoreq.2 and 
precisely one switch in each of the first and second programmable switch 
means is in the "on" position for any choice of total time delay .DELTA.t, 
2.DELTA.t, 3.DELTA.t, . . . , MN.DELTA.t. The embodiment shown in FIG. 6 
can introduce a delay of .DELTA.t, 2.DELTA.t, 3.DELTA.t, . . . , 
NM.DELTA.t by appropriate setting of the switches SW and SW', if the cycle 
of the clock signal has length .DELTA.t. Again, the signal that enters the 
input terminal of the apparatus passes through one or at most two switches 
in the "on" or first state before this signal, now time delayed, passes 
through the output terminal of the apparatus. With the embodiment 
illustrated in FIG. 6, the total number of switches M+N required is 
minimized for M.apprxeq.N. 
FIG. 7 illustrates another embodiment of the invention, using M individual 
time delay units D that are connected together as in FIGS. 5 and 6 and 
using N time delay modules D.sub.M+1, each with associated time delay 
(M+1).DELTA.t, which are connected together as are the time delay modules 
D.sub.M in FIG. 6. In FIG. 7, the input terminal of the first time delay 
module D.sub.M+1 is associated with individual time delay unit D number M 
through a two-state switch SWM; where in a first state of the switch the 
input terminal of the apparatus is directly connected to the input 
terminal of the time delay module D.sub.M+1 number m=2; and in a second 
state of this switch the output terminal of individual time delay unit M 
is directly connected to the input terminal of the time delay module 
D.sub.M+1 number m=2. Using the configuration shown in FIG. 7, a time 
delay of 0,.DELTA.t,2.DELTA.t, . . . ,[(M+1)(N+1)-1].DELTA.t is obtained 
by suitable programming of the switches. Again, the number of switches is 
minimized if M and N are chosen to be substantially equal. 
In order to assure that the output signal of the overall apparatus has 
passed through precisely two switches in the "on" position or first state 
in each of FIGS. 5, 6 and 7, another two-state switch might be inserted 
between the input terminal of the apparatus and the input terminal of the 
first of the individual time delay units D in those Figures. By way of 
example, FIG. 9 illustrates the change in the embodiment of FIG. 6 with 
this additional two-state switch SWO included between the input terminal 
of the apparatus and the input terminal of the first time delay unit D; in 
the second state, of the switch SWO, the connection between these two 
input terminals is disrupted or broken. 
Although the preferred embodiment of the invention has been shown and 
described herein, variation and modification may be made without departing 
from the scope of the invention.