DYNAMIC MEMORY FOR EFFECTING NONCYCLIC DATA PERMUTATIONS

摘要

1518697 Digital data storage systems GES FUER MATHEMATIK UND DATENVERABBEITUNG mbH BONN 5 Dec 1975 [16 Dec 1974] 49968/75 Heading G4A In a dynamic memory in which the contents of a predetermined memory cell may be transferred into a write-read head of the memory by means a permutation sequence of data permutations between the contents of the memory cells, the memory comprises 2k-1 memory cells arranged in a tree-like structure in planes numbered 0 to k-1 so that plane i contains 2i memory cells, e.g. as in Fig. 2 where k=5, the memory cells 11-311 being coupled as shown to form triangles in each of which triangles the contents of the three associated memory cells may be cyclically interchanged in a clockwise direction, the memory cell 11 of plane O acting as the write-read head of the memory. An access control system coupled to the memory produces either a permutation A constituted by the simultaneous transfer of the contents of the memory cells, e.g. 41-71, disposed in even numbered planes to the associated memory cells of the next higher odd numbered planes, or a permutation B constituted by the simultaneous transfer of the contents of the memory cells, e.g. 81-151, disposed in odd numbered planes to the associated memory cells of the next higher even numbered planes, the permutation sequence constituting a sequence of permutation A and permutation B. The access control system may include a k-bit permutation status register SAR, Fig. 4, for identifying the actual permutation state of the memory by containing the binary code of the cell address of a first memory cell whose contents are presently in the write-read head 11, a k-bit memory address register MAR for receiving the binary code of the cell address of a second memory cell whose contents are to be read or written next, and a comparison logic network COMP for producing the shortest permutation sequence necessary to transfer the contents of the second memory cell to the write-read head 11. This is done by successively shifting the contents of registers MAR, SAR, which are forwards/backwards shift registers, until their contents are identical. The highest order 1 bits in registers MAR, SAR, which are termed pilot bits, and which represent the planes in which the addressed memory cells are disposed and hence which type of permutation A or B is to be performed first, are detected by comparison with a pointer held in a k-bit forward/backwards shift register or pointer register SPR. The pilot bits of registers MAR, SAR are first aligned by right-shifting the contents of registers MAR or SAR, depending on which has its pilot bit in a more significant position, in synchronism with the pointer in register SPR; the bits exiting from the righthand ends of registers MAR or SAR being used to generate appropriate permutations (see later) by means of registers HM, HS, HH, MHF, SHF, SFF, which permutations are applied to the memory, the contents of register MAR being recirculated whereas those of register SAR are lost following such use. When the pilot bits in registers MAR, SAR are aligned, the contents of these registers are right-shifted in synchronism with the pointer in register SPR until either the contents of registers MAR, SAR between the pointer position and position O are identical, indicating that the initial parts of the two permutations corresponding to the contents of registers MAR, SAR are identical and hence that the memory need not be restated to its starting state, wherein the contents of cell 11 are present in the write-read head, before effecting the desired transfer, or until the pointer reaches position O, indicating that a return to the starting state is necessary. During such right-shifting the bits of the address code existing from register MAR are converted into a permutation code using the rule, which follows from the addressing scheme used, that each 1 bit of the address code causes the associated permutation to be performed twice and each O bit of the address code causes the associated permutation to be performed once (the initial permutation being determined by the position of the pilot bit). A counter CNT records the number of right-shifts made by registers MAR, SAR, and when their right-shifting has ceased they are then left-shifted in synchronism with the pointer in register SPR until counter CNT reaches O, whereupon the contents of registers MAR, SAR are identical and the desired transfer is effected. The invention may be applied to a virtual memory system, a page comprising the contents of 2g memory cells being segmented and stored in planes numbered #g + 1 and being recalled to the 2g memory cells of plane numbered g by a prefix permutation sequence before being accessed using the above procedure. Successive access to the 2g memory cells of the plane numbered g may be achieved by a g-position binary counter ADCT feeding the g lowest order positions of register MAR. Two structures each similar to Fig. 2 may be connected to form a tandem memory, Fig. 3 (not shown), which also employs the apparatus of Fig. 4 for effecting data permutations, address codes now having k+ 1 bits but bit 2 being separated therefrom and fed to a one-position register MFF to control selection of a desired one of the two structures. Detailed circuitry of each cell of the logic network COMP, which contains k identical cells corresponding to those of the registers MAR, SAR and SPR, is given in Figs. 5, 6 (not shown). A peripheral processor may interconnect the memory with a central processing unit. The memory, it appears, may employ magnetic domain storage devices or charge coupled storage devices as the memory cells. In a modification, the permutations A, B of the second structure of the tandem memory of Fig. 3 (not shown) may be interchanged.