Dynamic memory arrangement for providing noncyclic data permutations4030078Abstract Circuit arrangement for noncyclic data permutations between the memory cells of a dynamic memory including a permutation network for transferring the contents of a predetermined memory cell into the access port or read-write cell of the memory and an access control system for producing a permutation sequence. The permutation network is comprised of 2.sup.k -1 memory cells which are arranged in a tree-like structure in k of 0 to k-1 numbered planes so that plane i is formed of 2.sup.i memory cells. Each memory cell of plane i is connected to two adjacent interconnected memory cells of plane i+1 so that these three memory cells form a triangle in which the contents of these cells can be cyclically interchanged in a clockwise direction. Each memory cell of the planes 1 .ltoreq. i .ltoreq. k-2 belongs to two triangles while the one memory cell of plane 0, which acts as the access port or read-write cell, and the memory cells of plane k-1 belong to but one triangle. The access control system provides for the simultaneous transfer of the contents of the memory cells disposed in even numbered planes to the associated memory cells of the next higher odd numbered planes (permutation A) or for the simultaneous transfer of the contents of the memory cells disposed in odd numbered planes to the associated memory cells of the next higher even numbered plane (permutation B) to effect either permutation A or permutation B. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
______________________________________
Sequence Address Sequence Address
______________________________________
A 2' + AA 3' +
AB 2' + AAB 3' +
ABA 8' AABA 9'
ABAA 12' AABAA 13'
ABAAA ---- 2' + AABAAA ----
3' +
ABB 2' + AABB 3' +
ABBA 10' AABBA 11'
ABBAA 14' AABBAA 15'
ABBAAA ----
2' + AABBAAA ----
3' +
ABBB ---- 2' + AABBB ----
3' +
AAA ---- 1' +
______________________________________
The symbol+ indicates all those sequences which either do not change the contents of the read-write cell 1' or at which the contents of the read-write cell 1' do not correspond to one of the memory cells of plane 3. The table shows that with this permutation sequence no more than two cell contents of the desired plane are brought to the read-write cell 1' by immediately successive permutations and that these two permutations are followed by at least two further permutations in which the contents of the read-write cell 1' do not coincide with that from one of the cells of plane 3. As shown in FIG. 2, this applies for all planes. The total number of permutations performed for plane 3 is 21; this exactly corresponds to the number of edges or paths of the network in the area between the read-write cell 1' and plane 3 through which the original contents of the read-write cell 1' pass exactly once in the given permutation sequence in the clockwise direction. Consequently, it generally applies that the shortest possible permutation sequence for access to all 2.sup.i cells in plane i requires exactly 3(2.sup.1 -1) permutations. The permutation properties of the memory structure shown in FIG. 2 can be used with particular advantage in a so-called "paging" system in which the virtual memory space is realized by a dynamic memory. During "paging", data blocks which correspond to the contents of 2.sup.g consecutively addressed memory cells of which the first one must have an address n 2.sup.g are transported between the (virtual) dynamic memory and the (real) main memory of the system. Such a data block, also called a "page", may be stored in the 2.sup.g cells of plane g of the given memory structure. Since every cell of plane g is itself the root of a subtree extending to a depth of k-g planes at a capacity of 2.sup.k-g -1 cells, a total of 2.sup.k-g -1 complete pages can be stored in the memory so that data belonging to the same page are always disposed in the same cells of these subtrees when the memory is at the starting state .phi.. Between planes 0 and g-1 there is an incomplete page of 2.sup.g -1 cells. Each complete page can thus be permutated to plane g by means of a so-called prefix sequence which in the conventional sense corresponds to the page address in the virtual memory and can be read out or written in from there according to the given minimal algorithm. Since this access sequence usually takes place according to consecutive cell addresses it is advisable to change the cell addresses appropriately from the numbering given in FIG. 2. The property of a permutation sequence required for access to a page of the length 2.sup.g and positioned in plane g, that two successive permutations which transport a cell content of this page into the reading head be followed immediately by at least two permutations which provide data not required by the reading head is utilized to double the total available memory capacity without significant expansion of the access control system as well as double the data access rate during "paging". This is done in that two permutation networks of the same capacity are operated simultaneously so that the permutation sequence fed to the first network is also used in the second network with a delay of exactly two permutation clock times. The performance of the permutation sequence required for sequential access to the cells of plane g then brings the result that, during the gap of at least two permutation clock times in read-write cell of the second network produced directly after access to two cell contents in plane g of the first network, exactly two cell contents of plane g of the second network will appear. With the appropriate numbering of the cells in both networks it is thus possible to access exactly eight consecutively numbered cells in immediate succession before an access gap occurs. This doubles the access rate, i.e., compared to a single network, exactly 3(2.sup.g- -1) permutation periods are required for access to the 2.sup.g cells of a page of which one half if now disposed in plane g-1 of each of the simultaneously operated permutation memory networks. FIG. 3 is a schematic illustration of such a permutation network in a tandem tree structure whose cells are consecutively numbered so that when the shortest permutation sequence for a plane i is used the cell contents appear in the respective read-write cells 2 and 3 alternatingly in the sequence of monotonously increasing addresses. The law of development for such numbering is given in that in network I, beginning with plane i=1, each cell is one plane i with an address x.sub.i is associated with two cells in plane i+1 with the respective addresses x.sub.i +2.sup.i.sup.+1 and the address x.sub.i +2.sup.i.sup.+2. For example, cell 4 of plane 1, i.e., i=1, is associated with cells in plane 2 with the respective addresses 8 and 12. In network II cell addresses are always higher by 2 than the addresses of corresponding cells in network I. This brings the direct result that, aside from the address of the respective read-write cells 2 or 3, the binary codes of the addresses in network I have a zero in their 2-value bit while in network II all addresses have a 1 in their 2-value bit. This association of the cell addresses and the permutation sequences required for access to the respective cells determines the structure and function of the access system required to operate the memory. The operationally significant components of such an access control system are shown in the block diagram of FIG. 4. A permutation status register SAR represents the actual permutation state of the network in binary coded form. The desired address of the memory cell whose content is to be transported next into the read-write cells is fed to a memory address register MAR. With the support of several auxiliary registers, a logic network COMP compares the contents of registers MAR and SAR and produces from this comparison the permutation sequence required for this transport and the corresponding control signal sequence. The distribution of the addresses over the two simultaneously operated networks directly indicates that the address bit of value 2 holds special significance in that it is not required to initiate the permutation sequence since addresses which differ only in this bit require the same permutation sequence. This bit is only required to make a selection as to which read-write cell 2 or 3 access is to be made whenever the required cell contents appear in the read-write cell of the respective network. Per definition this is, in the case of a 0, the read-write cell 2 of network I and, in the case of a 1, the read-write cell 3 of network II. The address bit with the value 2 is therefore not fed into register MAR but into a one-position binary register MFE e.g., an RS flip-flop. The code suitable for describing the permutation state of the network is derived from the fact that due to the above-discussed limitation of the permissible permutation sequences, every cell content can reach the read-write cell within one permutation sequence. To indicate the permutation state of a network comprising 2.sup.k -1 cells, as shown in FIG. 2, a k-location register is thus sufficient which contains in binary coded the address of that cell whose content presently is in the read-write cell. In the case of a permutation network in tandem structure as shown in FIG. 3, whose total capacity is 2(2.sup.k -1 ) cells, a k-position register is also sufficient since here, as in the case of the address register, the bit of binary value 2 is irrelevant. The control problem of the network is then reduced to bringing the contents of permutation status register SAR into coincidence with the contents of memory address register MAR suitable permutations. The algorithm required for this and its circuitwise implementation results from the relation between the binary codes of the cell addresses and the permutation sequences required for access to the cells. This connection will be explained with the aid of two examples. Access to cell 56 which is present in network I of the tandem memory of FIG. 3 is made, as can be easily seen from the structure, by means of sequence BBAABA. If as agreed upon permutation A is coded by a 1 and permutation B by a 0, the following relationship results between address code and permutation code:
______________________________________
Address code 1 1 1 0
##STR3##
0
I - I - I I
Permutation code 00 11 0 1
______________________________________
The highest valued bit 1 in the address code, hereinafter also called the pilot bit, identifies the plane in which the addressed cell is disposed and thus the first permutation to be performed. In this case the cell belongs to the fourth plane and the first permutation is thus B, shown by a 0 in the permutation code. The number of bits to the right of the pilot bit, except for the framed bit of value 2 (which since it is a 0 indicates the addressed cell is in network I) provides the number of changes required, increased by 1, between the permutations A and B since every bit constitutes a plane in the tree. In the example, three changes are required, beginning with permutation B, i.e., BABA. This also shows the correspondence between the bits in the address code and those in the permutation code. If the address bit is a 1, then the associated permutation is performed twice, if the address bit is a 0, however, then the associated permutation is performed only once. This is also shown in the example for access to cell 39, which is in network II, with the aid of sequence BABBAA.
______________________________________
Address code:
1 0 0 1
##STR4##
1
I I I - I -
Permutation code: 0 1 00 11
______________________________________
The pilot bit in the address code again points toward the fourth plane, i.e., the first permutation must be B. Since the first bit to the right of the pilot bit contains a 0, this permutation is performed only once. The same applies to the next-following permutation A while the successive permutations B and A each need be performed only twice. This association of the address codes with the permutations required for access to the respective cells results in the access control system shown schematically in FIG. 4, and basically includes the following components: a memory address register MAR which is designed as a forward/backward shift register comprising k binary positions corresponding to a memory capacity of 2(2.sup.k -1) cells in a tandem network and to which the address code, consisting of k+1 bits, is fed - except for the bit of value 2 - so that the i.sup.th bit of the address is in the i.sup.th binary position of the register, the binary positions being numbered from the right toward the left in the sequence 0,2,3,4, . . . , k-1,k (this is abbreviated as MAR (k:2,0)); an overflow one position binary register or flipflop HM which is connected together with register MAR to form a ring shift register so that with a shift to the right of the data in register MAR the contents of binary position MAR(0) are transferred to flipflop HM via a line 80 and the contents of flipflop HM are transferred to binary position MAR(k) via a line 81, while conversely with a shift to the left of the data in register MAR, the overflow from binary position MAR(k) is shifted to flipflop HM via a line 82 and its contents to binary position MAR(0) via a line 83; a one-position binary register or flip-flop MFF into which the bit of value 2 of the address code is fed; a permutation status register SAR(k: 2,0) which is likewise designed as a forward/backward shift register and which in each permutation state contains the binary code of the address of that cell (except for the bit of value 2) whose content happens to be at the read-write cell 2 of network I; an overflow one-position binary register or flip-flop HS which upon a shift to the right of the data in permutation status register SAR takes over the contents of binary position SAR(0) via line 84 while its own content is lost, and which upon a shift to the left of the data in register SAR transfers its contents to binary position SAR(0) via line 85 while itself taking over the content of overflow flipflop HM via line 86; a pointer register (forward/backward shift register) SPR(k: 2,0) which contains a pointer in that always only one binary position SPR(i) has the binary value 1 while all other binary locations have the binary value 0; a one-position binary register or flip-flop SFF which indicates the type of the last performed permutation so that SFF=1 corresponds to permutation A and SFF=0 corresponds to permutation B; a one-position binary register or flip-flop MHF in which is recorded whether the position of the pilot bit directly after writing of a new address code in memory register MAR corresponds to a first permutation A (MHF=1) or a first permutation B (MHF=0) to be performed for access to the respective cell; a flip-flop or one-binary control register HH in which the contents of register HS can be duplicated if required; a one-position binary register or flip-flop SHF in which the first permutation of the permutation sequence contained in register SAR is recorded; an m-position binary counter CNT(m- 1:0) in which the number of shifts to the right and shifts to the left performed by register MAR are counted; a g-position binary counter ADCT(g- 1:0) which is used for the consecutive addressing of cells of one page so that the counter state - beginning with the value 0 - is counted upward in steps of 1 until the value 0 has been reached again and after each counting up the contents of this counter are transferred to the last g binary positions of memory address register MAR; a shift register DEL(0:2) comprising three binary positions into whose bit DEL(0) a 1 is entered from the one bit register SFF if permutation A is performed and a 0 is entered if permutation B is performed, whose contents are shifted to the right by one binary position with each permutation and from whose bit DEL(2) the control signals for network II can be derived after exactly two permutation clock times; a shift register READ(0:2) which is also shifted to the right with each permutation and into whose bit position READ(0) a 1 is written if flipflop MFF is set at 1 and if simultaneously the contents of registers MAR and SAR have been brought to coincide, and whose bit position READ(2) controls the read-write cell of network II if the cell contains a 1; a first logic network COMP which evaluates the contents of registers MAR, SAR and SPR and produces various control signals; and a second logic control network specifically shown in FIG. 5 which controls the register shifting as well as the permutations within the memory network. The exchange of data with the first control network is shown in the block circuit diagram of FIG. 4 by arrows S.sub.in and S.sub.out. It receives various control signals from the network COMP, the settings of the one bit or positions registers MHF, SHF, HH, SFF, a signal from the pointer register SPR which indicates whether the pointer coincides with the 0 bit position, and a signal from the counter CNT which indicates counter contents different from zero. From these input signals, the logic control network generates the signals for left/right shifts of the registers MAR, SAR, SPR, for counting up and down the counter CNT, and a signal which sets the one bit register SFF, from which the permutation signal C.sub.I for the memory network I and the input signal for the delay line DEL of memory network II is taken. The operation of the first control network of FIG. 4 is as follows: The actual permutation state of the memory network of FIG. 3 is given by the contents of the permutation status register SAR which provide the address of the cell content presently in the read-write cell 2 of network I as well as by the content of the one position register SHF which indicates the first permutation of the permutation sequence required to reach this state. Furthermore, the last performed permutation is stored in register SFF. When a new address is fed into memory address register MAR via line 90, the procedure described below is used to bring the content of this cell into the reading head of the respective memory network. With the aid of logic network COMP the pointer in SPR is first set to that binary position which corresponds to the higher valued one of the two pilot bits in registers MAR and SAR. At the same time a signal IMAX in the logic network COMP determines whether the pointer position coincides with the pilot bit in MAR and a signal KMAX in the logic network COMP determines whether the pointers position coincides with the pilot bit in register SAR. If IMAX= 1 and KMAX= 0, the higher valued pilot bit belongs to register MAR. It is now determined, with the aid of the pointer position in register SPR whether this pilot bit is at a position with corresponds to a permutation A or to a permutation B and this is recorded by the corresponding setting of register MHF. Then the indicator in register SPR is moved in steps to the right simultaneously with the contents of register MAR that are circulated in the manner mentioned above, respectively, until IMAX= 1 as well as KMAX= 1. Now the pilot bits in registers MAR and SAR are in the same position. If however, in the starting state IMAX= 0 and KMAX=1, the content of register SAR is initially shifted in steps to the right together with the content of register SPR. With each step the bit transferred to one-position overflow register HS is evaluated as follows: since a logic 1 indicates that the permutation given in register SFF was performed twice, the same permutation must be performed exactly once more to compensate it in order to verify the shift to the right of register SAR by the corresponding shortening of the permutation sequence. if, however, HS containes a logic 0 which means that the respective permutation in SFF was performed only once, this one permutation is compensated in that the same is performed exactly twice more. This is done with the aid of the one-position binary register HH into which the contents of register HS are duplicated and where it is interpreted. If register HH contains a logic 1, the permutation is interrupted after its one-time performance. If, however, register HH contains a logic 0, register HH is set to logic 1 after the performance of a first permutation and the same permutation is performed once more. After the permutation identified by register SFF has been supplemented to three and thus the effective permutation sequence has been correspondingly shortened, the contents of register SFF a inverted. Now register SFF contains the permutation which corresponds with the bit transferred into register HS by the next shift to the right of permutation status register SAR. This shift to the right is initially repeated in steps until IMAX= 1 as well as KMAX= l. At the moment when IMAX takes on the logic value 1, register MHF is set since the pointer position set in pointer register SPR now also coincides with the pilot bit in memory address register MAR. If the pilot bits already coincide in the starting position, the separate shifting of register MAR and SAR is not required. Now registers MAR and SAR are shifted to the right together with the indicator in register SPR which now points to the pilot bits in both registers. As before, the bits exiting register MAR from the right are now re-entered into register MAR from the left while the bits exiting from register SAR toward the right are lost after having been interpreted in registers, HS and HH, as already described. If the contents of the one-position registers MHF and SHF, which indicate the first permutation of the permutation sequence required for the address stored in register MAR or the first permutation sequence required to realize the actual permutation state, respectively, are identical, parts of the two permutation sequences may be identical under certain circumstances. The network COMP therefore compares the contents of register SAR and MAR after each shift to the right between the indicator position and binary position 0. If the contents are not identical a further shift to the right is performed; if they are identical, shifting to the right is terminated. In the case where the contents of MHF registers and SHF are not identical, no identical partial sequences exist and the shift to the right of registers MAR, SAR and SPR must be repeated until the pointer position, and thus the respective pilot bits, have reached binary position 0. In this way the network is reset to its starting state. With each shift to the right in which register MAR participates, binary counter CNT is simultaneously counted up by one so that at the end of the shifting to the right CNT contains that number of shifts to the lift which must be performed with respect to MAR to reinstate the starting situation. When register MHF is equal to register SHF the content of register SFF remains intact upon completion of the shift to the right, while when register MHF is unequal to register SHF, the content of register MHF is transferred to register SFF. Now registers MAR, SAR and SPR are all shifted to the left together in steps. With each step the bit appearing in the overflow register HM for register MAR is simultaneously also transferred to registers HS and HH. A logic 1 in register HH is converted into a double performance of the permutation indicated in register SFF and a logic 0 in register HH is converted to a single performance of the permutation. Upon completion of this action, the content of register SFF is inverted, counter CNT is counted down by one and the registers are shifted to the left. The procedure is stopped when the content of counter CNT has counted down to 0, i.e. the cell address fed into MAR has reattained its original position. Since the bit contained in register HM was duplicated in register HS with every step and the corresponding permutations were performed, when CNT= 0 the contents of registers MAR and SAR are identical and the cell content identified by the address contained in register MAR appears in the read-write cell of the network I. If a cell content of network II is addressed, which is given by the status of the one-position binary register MFF, a logic 1 is fed into the delay register READ when CNT has been reset to 0 to permit access to the reading head of network II after two further permutation cycles. This procedure realizes a minimum permutation sequence for access to two arbitrary, consecutively addressed cell contents corresponding to the example for access to cells 22 and 26 of the network shown in FIG. 2. Since the cells of the network of FIG. 3 are numbered so that access to 2.sup.g consecutively numbered cells is minimal once all cell contents have been transported to planes g-1 of the tandem network, this access sequence can be produced in the given access system in that the g-position binary counter ADCT is counted up by 1, beginning with counter position 0, until the counter state 0 has been reached again. The respective counter position is transferred to the last g binary positions of register MAR, whereupon the required permutation sequence for the shortest possible transport of the contents of the addressed cell into the read-write cell is effected. Particular measures for addressing the cells of network II are not required if the control bit in register MFF continues to remain at logic 1 during this process. A significant component of the access control system is logic network COMP which correlates the contents of registers MAR, SAR and SPR with one another. Corresponding to the k- 1 binary positions of these registers, the network contains k-1 cells which are connected together in cascade so that logic signals are propagated from the left to the right, i.e., from the higher-valued to the lower-valued binary positions. Such a cell which corresponds to binary position i is shown in FIG. 5. Immediately after charging of register MAR with a new address, logic network COMP sets the pointer position in SPR so that it coincides with the higher-valued one of the two pilot bits in register MAR and SAR. Moreover, this network produces a signal IMAX which indicates coincidence of the pointer position in register SPR with the pilot bit in register MAR and a signal KMAX which indicates coincidence of the position in SPR with the pilot bit in SAR. Additionally, this circuit determines the identity of the contents of register MAR and SAR between the indicator position and binary position 0. For this purpose the contents of binary position MAR(i) are fed through a line 60 (which is one of n lines of a bus 161 of FIG. 4) and the contents of binary position SAR(i) through a line 61 (which is one of n lines of a bus 163 of FIG. 4) to respective inputs of AND gate 62 and EXCLUSIVE-OR gate 63. At the same time, a control line 64 which is common to all cells and carries a signal SET is connected to a third input of AND gate 62. A further AND gate 65 receives via line 66 a signal OUT(i+ l) from the neighboring cell i+1 to the left and at the same time via line 67 (which is one of n lines of a bus 162 of FIG. 4) the inverted contents of binary position SPR(i) of the pointer register SPR. The outputs of gates 62, 63, 65 are connected to the inputs of an OR gate 68 whose output line 69 transmits a signal, which corresponds to the signal OUT(i+ 1) received through line 66 from the left-hand cell i+1, to the adjacent cell i-1 to the right. At the same time line 69 is connected to a first input of AND gate 70 whose second and third inputs are connected to the control line 64 as well as, in inverted form, the output of AND gate 65. The output line 71 of gate 70 is connected to the input of binary position SPR(i) of the indicator register SPR and is part of the bus 164 of FIG 4. The signal present at output line 69 is formed by the logic interconnection OUT(i)= MAR(i).sym. SAR(i)+ MAR(i)SAR(i )SET+OUT(i+1)SPR(i)) (1) The signal formed at output line 71 is produced by the logic interconnection SPR(i)= OUT(i+1)OUT(i)SET (2) this part of the network can be used to set the initial pointer position as follows: Before setting register SPR, SPR(i)= 0 applies for all positions, i.e., SPR(i)= 1. When the pointer position is set, signal SET is set to logic 1 so that, according to equation (1), the signal OUT(i)= MAR(i)+ SAR(i)+ OUT(i+1) is present on line 69. Per definition, the pointer must be set exactly to binary position i for which OUT(i+1)= 0 but OUT(i )= 1, i.e., register MAR as well as register SAR contain only logic 0 to the left of i, but MAR(i)= 1. This state is determined by AND gate 70 at whose output, according to equation (2) signal SPR(i)= OUT(i+1)OUT(i) is present under the condition that SET= 1, which signal can have the logic value 1 for only exactly one binary position. The entire signal pattern SPR(i) is inserted into pointer register SPR and thus the pointer position is fixed. Now SPR.noteq. 0. When SET= 0 is applied to line 64, output 69 of each cell, according to equation (1) carries the signal OUT(i)= (MAR(i).sym. SAR(i)+ OUT(i)+1)(SPR(i)) Consequently, a signal 0 will appear at the output of cell 0 only when MAR(i ).sym. SAR(i) 0 for all binary positions i between the actual pointer position SPR(i)=1 and position 0, i.e., when the cell contents of the two register segments MAR(i:2,0) and SAR(i: 2,0) are identical. AND gate 72 interconnects lines 67 and 60, i.e., pointers position SPR(i) and the contents of binary position MAR(i), so that a logic 1 will be present at the output of AND gate 72 whenever MAR(i)=1 as well as SPR(i)=1, the latter being the case, per definition, for exactly one binary position. This signal is permanently wired via a protective diode 73 to all the corresponding gate outputs of all other cells to produce the OR function IMAX= .SIGMA. MAR(i)SPR(i) (3) in collecting line 74. The same function is realized with the aid of AND gate 75 and protective diode 76 on collecting line 77 for the contents of register SAR and SPR as follows: KMAX= .SIGMA. SAR(i )(SPRi) (4) Since the contents of register MAR and STAR as agreed upon are shifted in synchronism with the pointer, position in SPR as soon as the pointers, coming from the left, arrives at the pilot bits of registers MAR or SAR, respectively, IMAX= 0 only as long as the pointers is still to the left of the pilot bit in MAR, in the other case IMAX= 1. Per definition, the conditions for controlling the shifts in registers MAR and STAR are thus determined. In order to determine whether the position of the pilot bit in register MAR requires a first permutation A or a first permutation B, the even numbered binary positions of the pointer register SPR are permantently wired, via protective diodes, to a further collecting line SMF not shown in FIG. 4 to form an OR function so that a logic 1 signal is always present when the pointer coincides with an even numbered position and a logic 0 signal when the pointers, is at an odd numbered position. At the moment when the pointer, coming from the left, arrives at the pilot bit in register MAR, i.e., when IMAX switches from 0 to 1, the signal on SMF, which indicates the pointer position, is transferred to the one-position register MHF. The operation of the first control network of FIG. 4 is supported by a second control network shown in FIG. 6 which generates from various control signals received from the first control network and an internal clock pulse generator the pulses sequences for left and right shifts of the registers MAR, SAR, SPR and for the counter CNT, and a signal for the setting of the one bit register SFF which determines the type of permutation to be executed in the memory. A first combinatorial logic network 101 receives at its four input lines 120, 121, 122, 123 the settings of the one bit or position binary registers MHF and SHF, the signals OUT(0) from the network COMP and the pointer position SPR(0), respectively, to complete at its output line 124 the logical function ID= (MHF.sym. SHF)OUT+ (MHF.sym. SHF)SPR(0) which is responsible for right shifts if ID= 0, and for left shifts if ID= 1. The signal ID is, together with the signals IMAX on line 125 and KMAX on line 126 furnished to a second combinatorial logic network, 102 which computes the conditions for a right shift of register MAR as RMAR= IMAX ID on line 127, a right shift of register SAR as RSAR= KMAX ID on line 129 and for a right shift of register SPR as RSPR= ID on line 128. The signals RMAR, RSAR, RSPR are at the AND gates 103, 104, 105, respectively, superimposed with a clock pulse sequence P which is supplied via a line 138. The output 130 of gate 103 drives register MAR, the output 131 of gate 104 drives register SPR, the output 132 of gate 105 drives register SAR on right shifts. The AND gate 109 computes the signal SHL= CNT ID which provides the condition for a common left shift of the registers MAR, SPR, SAR. The output of gate 109 is clocked with the pulse sequence P at the AND gate 108, whose output 136 drives register MAR, SPR, SAR on left shifts. Simultaneously, the pulses sequence of the output 130 is furnished to the `countup` input of the counter CNT to count the right shifts of the register MAR, and the pulse sequence of the output 136 is furnished to the `countdown` input of the counter CNT. One embodiment of the contents of the logic networks 101 and 102 is shown in FIGS. 7 and 8. As shown in FIG. 7, the network 101 includes an exclusive OR gate 201, an OR gate 202 with one inverted input and an inverted output, and AND gate 203 with one inverted input, and an OR gate 204. The exclusive OR gate 201 compares the contents of registers MHF and SHF on lines 120 to 121 respectively, to decide whether the first permutations of the sequence represented by the contents of registers MAR and SAR are identical, in which case the output of gate 201 is 0, or not indentical, in which case the output gate 201 is 1. This signal is combined in the OR gate 202 with the signal OUT(o) on line 122 from the logic network COMP which signal is a 1 if the contents of registers MAR and STAR from the pointer position to the right differ, and is a 0 if the contents of these registers are identical. As the signal on line 122 is inverted at the input of gate 202, the output is 1 if MHF= SHF and as long as there is no identity according to the signal on line 122. The output of the AND gate 203 is 1 if MHF SHF and as long as the signal SPR(0) supplied by line 123 is 0. Hence, the output 124 of logic network 101 carries a signal 1 as long as one or all of the registers MAR, SAR, SPR must be shifted right. This output signal on line 124 is received by the logic network 102 which as shown in FIG. 8 includes two AND gates 206 and 207. In the AND gate 206 the signal RMAR supplied to line 127 is formed from the signal on line 124 and the IMAX signal on 125. The signal RSPR supplied to output line 128 of logic network 102 is identical with the signal on line 124. The signal RSAR on output line 129 is formed in the AND gate 207 from the signal on line 124 and the KMAX signal on line 126. As shown in FIG. 6, these signals on lines 127-129 are clocked in gates 103, 104, 105, respectively with the clock signal P generated with the help of gate 110 to form the output signals on lines 130, 131, 132, respectively. Returning now to FIGS. 4 and 6 the setting of the permutation register SFF is furnished, via-line 134 to the AND gate 112 and, in inverted form, to the AND gate 111. The output 141 of gate 111 carries a set signal for register SFF if SFF=0, and the output 142 of gate 112 carries a reset signal for register SFF if SFF=1, upon the occurrence of a clock pulse P. The clock pulse sequence P is derived from the output 140 of the clock pulse generator T' with the help of the combinatorial logic networks 106, 107, the AND gate 110 and the two-digit binary counter CT. The network 106 serves to set up in the current CT the number of permutations to be performed without changing the contents of register SFF. This number is derived from the setting of the one bit or position binary register HH, and from the signals RSAR and SHL, which are furnished to the network 106 via the input lines 143, 129, 135, respectively. The bits CT(0) and CT(1) for counter CT are set as follows by the network 106: CT(0)= (RSAR HH+ SHL HH) P CT(1)= (RSAR HH+ SHL HH)P The counter CT is counted down with the clock sequence T on line 140. The network 107 checks the counter CT for the contents 0 and, if so, furnishes via the output 139 a 1 to the AND gate 110 to compute the pulse sequence P= CT T. The clock pulse sequence T drives, via the line 140, the shift registers DEL and READ, and, most importantly, the memory permutations. FIG. 9 shows one embodiment of the circuitry for the logic networks 106, 107 and the two digit binary counter CT which controls the generation of the clock pulse P. As shown the network 106 includes a plurality of AND gates which are connected to the input lines 129, 135, 138 and 143 and to each other to form the bits CT(0) and CT(1) for the two positions 0 and 1 of the counter CT. Whenever a right shift of SAR takes place, then on inputs 129 and 135 respectively RSAR= 1 and SHL= 0. The network 106, then transforms the setting of register HH on input 143 so that the counter register stage 0, which is realized by flip-flop FFO, is set to 1 and counter register stage 1, i.e., flip-flop FF1, is set to 0 if HH= 0, and so that stage FFO is set to 0 and stage FF1 is set to 1 if HH= 1. Whenever a left shift of SAR takes place, then RSAR= 0 and SHL= 1. and SHL= 1. Then, the network 106 transforms the setting of register HH as follows: stage FFO is set to 1 and stage FF1 is set to 0 if HH= 1, and stages FFO is set to 0 and stage FF1 is set to 1 if HH= 0. The contents of the register CT are incremented on every clock pulse T generated in the clock pulse of the counter register CT for the appearance of a setting FFO= 1 and FFI= 1, and then allows the clock pulse T to pass through gate 110 to form the signal P. Another variation of the permutation network consists in that in the tandem network of FIG. 3, the control of the second network II is modified so that the permutations B and A are interchanged with respect to the planes of this network. Thus when both networks are operated in synchronism the first network I will always introduce a new cell content into the read-write cell 2 when permutation A is performed while the second network II changes the read-write cell contents whenever permutation B is performed. The performance of the algorithm described for the "paging" process in such a tandem network then has the result that with the appropriate numbering of the cells, data structures arranged in the pattern of a tree and stored in a suitable manner can be traversed according to the so-called "pre-order" or "end-order" principle. It a further conceivable to connect a peripheral processor ahead of such a dynamic background memory with rapid direct access to data with any desired address as well as rapid sequential access to data blocks stored in 2.sup.g successively addressable cells. Such a peripheral processor relieves the central unit of part of its workload in that if performs various activities, such as processing of lists and similar administrative functions, for example, directly by means of the background memory. Furthermore, such a processor should be able to take on the function of a channel if data transport between the background memory and the operating memory of the central unit should become necessary. It will be understood that the above description of the present invention is susceptible to various modifications, changes and adaptations, and the same are intended to be comprehended within the meaning and range of equivalents of the appended claims.
|
Same subclass Same class Consider this |
||||||||||