Apparatus and machine implementable method for the dynamic rearrangement of plural bit equal-length records

A method for rearranging in a predetermined manner N identifiable 2m bit equal fixed length records `R.sub.i ` stored in N equal length shift register loops `L.sub.j `, one record to each loop, each loop having a latency of 2m bit times, said loops being connected by N-1 selectively operable dual mode switches `S.sub.k ` to form a linked linear ladder structure, said loops and switches from end-to-end being lexically designated L.sub.0 to L.sub.N.sub.-1 and S.sub.0 to S.sub.N.sub.-1 ;

• S.sub.0 being the switch coupling loop L.sub.0 to an input/output port, the switch S.sub.N.sub.-1 for loop L.sub.N.sub.-1 or switches S.sub.i and S.sub.i.sub.+1 bounding any given loop L.sub.i other than L.sub.N.sub.-1, upon being set into a first mode, maintains the given loop as a circulating path;
• any switch S.sub.i between any given pair of adjacent loops L.sub.i.sub.-1 and L.sub.i, upon being set into a second mode, provides a unidirectional crossover path connection between the adjacent loops, wherein the method comprises the steps of loading, rearranging and unloading records into and from the ladder structure;
• and further wherein the rearranging step comprises:
• moving a record in any given loop L.sub.j to any other given loop L.sub.i, j-i =D >
• 0, in (D+1)/2 loop latency times through a series of record exchanges such that starting at time T.sub.S and for k=0, 1, 2, . . . , (D-1), switch S.sub.j.sub.-k is set into the second mode during interval (T.sub.S +k/2;
• T.sub.S +k/2+1) and into the first mode otherwise.

A method for rearranging in a predetermined manner N identifiable 2m bit equal fixed length records `R.sub.1 ` stored in N equal length shift register loops `L.sub.j `, one record to each loop, each loop having a latency of 2m bit times, said loops being connected by N.sub.-1 selectively operable dual mode switches `S.sub.k ` to form a linked linear ladder structure, said loops and switches from end-to-end being lexically designated L.sub.0 to L.sub.N.sub.-1 and S.sub.0 to S.sub.N.sub.-1 ;

• S.sub.0 being the switch coupling loop L.sub.0 to an input/output port, the switch S.sub.N.sub.-1 for loop L.sub.N.sub.-1 or switches S.sub.i and S.sub.i.sub.+1 bounding any given loop L.sub.i other than L.sub.N.sub.-1, upon being set into a first mode, maintains the given loop as a circulating path;
• any switch S.sub.i between any given pair of adjacent loops L.sub.i.sub.-1 and L.sub.i, upon being set into a second mode, provides a unidirectional crossover path connection between the adjacent loops, wherein the method comprises the steps of loading, rearranging and unloading records into and from the ladder structure;
• and further wherein the rearranging step comprises:
• moving a record in any given loop L.sub.i to any other given loop L.sub.j, j-i = D>0, in (D+1)/2 loop latency times through a series of record exchanges such that starting at time T.sub.S and for k=0, 1, 2, . . . ,(D-1), switch S.sub.i.sub.+k is set into the second mode during interval (T.sub.S +k/2;
• T.sub.S +k/2+1) and into the first mode otherwise.

A method for rearranging in a predetermined manner 2M identifiable 2m bit equal fixed length records stored in 2m equal shift register loops `L.sub.j `, one record for each loop, each loop having a loop latency of 2m bit times, said loops being connected by 2M-1 selectively operable dual mode switches `S.sub.k ` to form a linked linear structure, said loops and switches from end-to-end being lexically designated L.sub.0 to L.sub.2M.sub.-1 and S.sub.1 to S.sub.2M.sub.-1 ;

• S.sub.0 being the switch coupling loop L.sub.0 to an input/output port, the switch S.sub.2M.sub.-1 for loop L.sub.2M.sub.-1 or switches S.sub.i and S.sub.i.sub.+1 bounding any given loop L.sub.i other than L.sub.2M.sub.-1 upon being set into a first mode, maintains the given loop as a circulating path;
• any switch S.sub.i between any given pair of adjacent loops L.sub.i.sub.-1 and L.sub.i, upon being set into a second mode, provides unidirectional crossover path connection between the adjacent loops, wherein the method comprises the steps of loading, rearranging and unloading records into and from the structure, and further wherein the rearranging step comprises:
• exchanging records in loops L.sub.0 to L.sub.M.sub.-1 with the records in loops L.sub.M to L.sub.2M.sub.-1 in M loop latency times through a series of record swaps such that starting at time T.sub.S and for latency times k=0, 1, 2, . . . , M-1, switch S.sub.2m is set into the first mode for the entire interval and that switches S.sub.M.sub.+k and S.sub.M.sub.-k are set into the second mode during the interval (T.sub.S +k/2, T.sub.S +M-k/2) and into the first mode otherwise.

A method for rearranging in a predetermined manner N identifiable 2m bit equal fixed length records `R.sub.i `, the record format having front and back halves, the records being storable in corresponding ones of N equal length shift register loops `L.sub.j `, each loop having a latency of 2m bit times, said loops being connected by N-1 selectively operable dual mode switches `S.sub.k ` to form a linked linear ladder structure, said loops and switches from end-to-end being lexically designated L.sub.0 to L.sub.N.sub.-1 and S.sub.0 to S.sub.N.sub.-1, the switch S.sub.N.sub.-1 for a loop L.sub.N.sub.-1 or switches S.sub.i and S.sub.i.sub.+1 bounding any given loop L.sub.i other than L.sub.N.sub.-1, upon being set into a first mode, maintains the given loop as a circulation path;

• any switch S.sub.i between any given pair of adjacent loops L.sub.i-1 and L.sub.i upon being set into a second mode, provides a unidirectional crossover path connection between the adjacent loops, wherein the method comprises the steps of loading, idling and unloading records into and from the ladder network on a last-in, first-out basis;
• and further wherein
• adjacent loops L.sub.2k and L.sub.2k.sub.-1, 0.ltoreq. k <
• N/2 representing PUSH DOWN levels P.sub.k and P.sub.N.sub.-k.sub.-1 such that records occupying the respective loops, each straddle both loops evenly with a half-record in each loop;
• when poised for loading the contents of P.sub.N.sub.-k.sub.-1 point with the front half toward loop L.sub.N.sub.-1 while the contents of P.sub.k point with the front half toward loop L.sub.0 ;
• when poised for unloading the contents of P.sub.N.sub.-k.sub.-1 will point with the front half toward loop L.sub.0, while the contents of P.sub.k will point with the front half toward loop L.sub.N.sub.-1 ;
• for loading a record at time T.sub.s, switches S.sub.0 through S.sub.N.sub.-1 are set into the second mode for one loop latency time (FIG. 9a, b, c);
• for unloading a record at time T.sub.s +1/2+k switches S.sub.0 through S.sub.N.sub.-1 are set into the second mode for one loop latency time (FIG. 9d, e, f);
• for idling switches S.sub.0 through S.sub.N.sub.-1 are set into the first mode for an integral number of loop latency times between the loading and unloading of the structure and vis a' vis.

An improved externally controllable permutation network for reordering N identifiable 2m bit equal fixed length records comprising:

• N equal length shift register loops L.sub.0 to L.sub.N.sub.-1, each loop having a latency of 2m bit times;
• N selectively operable dual mode switches S.sub.0 to S.sub.N.sub.-1, the switches being connected to the loops so as to form a linked linear ladder structure;
• switch S.sub.N.sub.-1 for loop L.sub.N.sub.-1 or switches S.sub.i and S.sub.i.sup.+1 bounding any given loop L.sub.i other than L.sub.N.sub.-1, upon being set into the first mode by a control signal maintains the given loop as a reentrant path;
• furthermore, any switch S.sub.i between any given pair of adjacent loops L.sub.i.sub.-1 and L.sub.i upon being set into the second mode by a control signal, provides a unidirection crossover path connection between the adjacent loops L.sub.i.sub.-1 and L.sub.i ;
• loop L.sub.0 being operative as a record input/output port;
• the loops and switches being lexically ordered in the same direction;
• and
• clocking means for causing all loops to move their contents, if any, in synchronism.

A method for rearranging in a predetermined manner N identifiable 2m bit equal fixed length records `R.sub.i ` stored in N equal length shift register loops `L.sub.j `, one record to each loop, each loop having a latency of 2m bit times, said loops being connected by N-1 selectively operable dual mode switches `S.sub.k ` to form a linked linear ladder structure, said loops and switches from end-to-end being lexically designated L.sub.0 to L.sub.N.sub.-1 and S.sub.0 to S.sub.N.sub.-1 ;

• S.sub.0 being the switch coupling loop L.sub.0 to an input/output port, the switch S.sub.N.sub.-1 for loop L.sub.N.sub.-1 or switches S.sub.i and S.sub.i.sub.+1 bounding any given loop L.sub.i other than L.sub.N.sub.-1, upon being set into a first mode, maintains the given loop as a circulating path;
• any switch S.sub.i between any given pair of adjacent loops L.sub.i.sub.-1 and L.sub.i, upon being set into a second mode, provides a unidirectional crossover path connection between the adjacent loops, wherein the method comprises the steps of loading, rearranging and unloading records into and from the ladder structure, and further wherein the loading step comprises:
• serially filling the ladder structure with records R.sub.N.sub.-1, R.sub.N.sub.-2, . . . , R.sub.0 in N loop latency times such that for k = 0, 1, 2, 3, 4, . . . , N-1, each switch S.sub.k is set into the second mode starting at time T.sub.s during the interval (T.sub.s +k/2, T.sub.s + N - k/2) and into the first mode otherwise;
• and still further wherein the unloading step comprises:
• serially emptying the ladder structure in the rearranged record order starting with the contents of loop L.sub.0 to loop L.sub.N.sub.-1, said emptying occurring in N loop latency times such that for k = 0, 1, 2, . . . N=1, each switch S.sub.k is set into a second mode starting at time T.sub.s ' during the interval (T.sub.s '+k/2, T.sub.s +N-k/2) and into the first mode otherwise.