Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
298 words
In an apparatus for rearranging N identificable 2m bit equal fixed length records, said apparatus including an externally controllable permutation network; and information handling means adapted to respond to the records in the order of their arrival for loading the records into the network, for developing and applying control signals to the network so as to effectuate the physical rearrangement of the records, and for unloading the records from the network, the control signals being derived from comparisons of record indicia according to a predetermined algorithm; wherein the improved permutation network comprises: q sorting ladders, each of whose sorting time being a linear function of the number of records to be sorted, where q≧ 1+log 3 (N+1)/4 , the ith ladder i≦q includes: n i equal length shift register loops, n i being constrained such that ##EQU4## Q i being the remainder after assigning n i to the ith ladder, if Q i ≦3, then n i+1 can be set equal to Q i , the ith ladder further includes: a plurality of selectively operable dual mode switches connecting the loops such that each loop has no more than two adjacent switchable neighboring loops, and upon any boundary switch being set into a first mode responsive to a control signal, then the adjacent loops are cross connected in order to facilitate an exchange of any records circulating therein, upon the boundary switches to any loop being set into a second mode also responsive to a control signal, then the loop is maintained as a circulation path, one end loop of the ladder and the associated boundary switch coupling the information handling means and being operative as an input/output port; and the permutation network further comprising: clocking means for causing all the loops to move their contents in synchronism.
Claim 2
Dependent Claim
298 words
In an apparatus for rearranging N identificable 2m bit equal fixed length records, said apparatus including an externally controllable permutation network; and information handling means adapted to respond to the records in the order of their arrival for loading the records into the network, for developing and applying control signals to the network so as to effectuate the physical rearrangement of the records, and for unloading the records from the network, the control signals being derived from comparisons of record indicia according to a predetermined algorithm; wherein the improved permutation network comprises: q sorting ladders, each of whose sorting time being a linear function of the number of records to be sorted, where q≧ 1+log 3 (N+1)/4 , the ith ladder i≦q includes: n i equal length shift register loops, n i being constrained such that ##EQU4## Q i being the remainder after assigning n i to the ith ladder, if Q i ≦3, then n i+1 can be set equal to Q i , the ith ladder further includes: a plurality of selectively operable dual mode switches connecting the loops such that each loop has no more than two adjacent switchable neighboring loops, and upon any boundary switch being set into a first mode responsive to a control signal, then the adjacent loops are cross connected in order to facilitate an exchange of any records circulating therein, upon the boundary switches to any loop being set into a second mode also responsive to a control signal, then the loop is maintained as a circulation path, one end loop of the ladder and the associated boundary switch coupling the information handling means and being operative as an input/output port; and the permutation network further comprising: clocking means for causing all the loops to move their contents in synchronism.
Claim 3
Dependent Claim
48 words
In an apparatus according to claim 1, wherein the information handling means includes means for serially loading and unloading N records into and from the aggregate of the q ladders, said q ladders being all respectively loaded or all respectively unloaded in the order of decreasing record capacity.
Claim 4
Dependent Claim
22 words
In an apparatus according to claim 1, the information handling means includes means for q way merging the records from the ladders.
Claim 5
Dependent Claim
20 words
In an apparatus according to claim 1, each loop has a capacity greater than or equal to the record size.
Claim 6
Dependent Claim
255 words
In an apparatus for rearranging N identifiable 2m bit equal fixed length records, said apparatus including an externally controllable permutation network; and information handling means adapted to respond to the records in the order of their arrival for loading the records into the network, for developing and applying control signals to the network so as to effectuate the physical rearrangement of the records, and for unloading the records from the network, the control signals being derived from comparisons of record indicia according to a predetermined algorithm; wherein the improved permutation network comprises: a first and a second sorting ladder, the ladders respectively including n i and n 2 equal length shift register loops, where n i +n 2 ≧N, n i ≧ (3N-1)/4 , n 2 ≧ (n+1)/4 ; each ladder further includes a plurality of dual mode switches; said switches connecting the loops such that each loop has no more than two adjacent switchable neighboring loops, and upon any boundary switch being set into a first mode by a control signal, then the adjacent loops are cross connected in order to facilitate an exchange of any records circulating therein, upon the boundary switches to any loop being set into a second mode also responsive to a control signal, then the loop is maintained as a circulation path; one end loop of each ladder and the associated boundary switch coupling the information handling means and being operative as an input/output port; and clocking means for causing all th loops to move their contents in synchronism.
Claim 7
Dependent Claim
255 words
In an apparatus for rearranging N identifiable 2m bit equal fixed length records, said apparatus including an externally controllable permutation network; and information handling means adapted to respond to the records in the order of their arrival for loading the records into the network, for developing and applying control signals to the network so as to effectuate the physical rearrangement of the records, and for unloading the records from the network, the control signals being derived from comparisons of record indicia according to a predetermined algorithm; wherein the improved permutation network comprises: a first and a second sorting ladder, the ladders respectively including n i and n 2 equal length shift register loops, where n i +n 2 ≧N, n i ≧ (3N-1)/4 , n 2 ≧ (n+1)/4 ; each ladder further includes a plurality of dual mode switches; said switches connecting the loops such that each loop has no more than two adjacent switchable neighboring loops, and upon any boundary switch being set into a first mode by a control signal, then the adjacent loops are cross connected in order to facilitate an exchange of any records circulating therein, upon the boundary switches to any loop being set into a second mode also responsive to a control signal, then the loop is maintained as a circulation path; one end loop of each ladder and the associated boundary switch coupling the information handling means and being operative as an input/output port; and clocking means for causing all th loops to move their contents in synchronism.