Patent GB-1206701-A (GB)
Title: Shift registers
Inventor: ARNOLD THOMAS FREDERICK
IPC: G11C19/00
Filed: 1968-03-05
Abstract: 1,206,701. Shift register. WESTERN ELECTRIC CO. Inc. 5 March, 1968 [6 March, 1967], No. 10567/68. Heading G4C.  A shift register comprising a plurality of bistable stages each storing a data bit has stage intercoupling circuitry for re-organizing a sequence of data bits in the stages into a new sequence in closed loop fashion so that successive operations of the intercoupling circuitry result in sequences of data bits that have different shift spans relative to an initial sequence, which shift spans are equal to successive terms of a power series of a constant Q. A high speed shift register comprised of n transistor flip-flops 22-27 has two sets of gates Tx, Ty connected to each input. To one gate is connected the output of the preceding stage, to the other the output of a stage determined by the value of the constant Q which is such that Q and n have no common divisor other than 1. As shown gates Ty connect together successive stages. Tx gates 45, 46, 47 connect the outputs of flip-flops 22, 23, 24 spaced Q-1 flip-flops apart, i.e. flip-flop 22 is flip-flop number n, 23 is flip-flop number n 1  + Q and 24 is number n 1  + 2Q, to the inputs of successive flip-flops 25, 26, 27 respectively. In operation data is read into the register during a timing period # 1 . During a period # 2 , the first period of initial sequence a shift equivalent to Q = 1 occurs if by enabling gates Ty the Q-ary number of the shift required has a digit in the least significant place, i.e. for Q=2, hence binary numbers, a shift occurs during # 2  if total shifts of 1, 3, 5, 7, 9 &c. are required. During # 3  a re-organization occurs and gates Tx are enabled to re-organize the digits into a different order. During # 4  a shift occurs if the next to the least significant Q-ary digit of the required shift is other than zero. During # 5  a re-organization occurs  &c. For a given value of n a fixed value of re-organizations occurs equal to [log n] where [X] indicates the whole number portion of X. At the end of this number of re-organizations assuming no shifts the original order of digits is altered but known. If we consider a 7 bit register, Q=2 and an original number of a, b, c, d, e, f, g, after a first re-organization the number becomes a, c, e, g, b, d, f and after a second a, e, b, f, c, g, d. The output read lines are then arranged so that the word read out is again in correct order a, b, c, d, e, f, g, e.g. an initial number a<SP>1</SP>, b<SP>1</SP>, c<SP>1</SP>, d<SP>1</SP>, e<SP>1</SP>, f<SP>1</SP>, g<SP>1</SP> is entered in positions a, b, c, d, e, f, g. Assuming a shift of 6 places = 110 in Q-ary digits no shift occurs during # 2 . A re-organization during # 3  gives digits a<SP>1</SP>, c<SP>1</SP>, e<SP>1</SP>, g<SP>1</SP>, b<SP>1</SP>, d<SP>1</SP>, f<SP>1</SP>. During # 3  a shift occurs to give f<SP>1</SP>, a<SP>1</SP>, c<SP>1</SP>, e<SP>1</SP>, g<SP>1</SP>, b<SP>1</SP>, d<SP>1</SP>. A re-organization during # 4  gives f<SP>1</SP>, c<SP>1</SP>, g<SP>1</SP>, d<SP>1</SP>, a<SP>1</SP>, c<SP>1</SP>, b<SP>1</SP>. A shift during # 5  gives b<SP>1</SP>, f<SP>1</SP>, c<SP>1</SP>, g<SP>1</SP>, d<SP>1</SP>, a<SP>1</SP>, e<SP>1</SP> and a re-arranged readout gives b<SP>1</SP>, c<SP>1</SP>, d<SP>1</SP>, e<SP>1</SP>, f<SP>1</SP>, g<SP>1</SP>, a<SP>1</SP> which is a shift to the right of 6 places as required. Fig. 2 shows part of a seven-bit shift register connected to have a re-organization constant Q=2. The diagram is simplified so the flipflops and gates are incorporated in cells A, B, C. Data is read into the register via the parallel input circuit 102 during the period # 1 and the occurrence of a read in gate pulse. The re-organization and shift cycles are controlled by counters 104 reset by the read-in pulse. Counter 11 records the full transfer count equal to Q hence a single flip-flop U is sufficient. Counter 112 counts the number of data sequences that occur during each total shift operation and counts the number of times counter 111 recycles. The full sequence count is equal to 1 + [log n] = 3 so a two-stage counter V and W is used. Fig. 5 shows the timing signals for the counter. The counter outputs are connected such that the output clock inhibit NOR gate 114 disables the clock drive gate NOR gate 115 to prevent further counting when the flip-flops U, V, W read 101. Gate 105 passes the re-organization pulses at appropriate times and gates 106 connected to register 140 containing the Q-ary shift value produces shift pulses at the appropriate times. The counter can be adapted for larger registers and larger values of Q. For large registers various values of Q allow shifts to be performed much faster than a conventional one shift at a time register with less circuitry than registers having a plurality of shifts of differing values built in.