Memory system for image processing having address calculating circuitry permitting simultaneous access to block horizontal sequence and vertical sequence subarrays of an array of data
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention generally relates to memory systems for image processing systems; and more particularly to memory systems for image processing operations which require that a digitized image or partial image array be stored in a memory system that permits access to p×q (block), 1×pq (horizontal sequence), and pq×1 (vertical sequence) subarrays of the digitized image array, where p and q are design parameters. 
     2. Description of the Related Art 
     In general, many image data, such as analog image signals from a TV camera which can be converted into digital signals by an A/D converter, are processed by an image processor or a computer. An image can be represented by a two-dimensional array of image points, which are sets of integers that each describes the color and intensity of a portion of the image. These image data are first stored in a memory system, and then, are retrieved from the memory system to be processed by an image processor or computer. 
     If image data in a desired subarray are stored in the same memory module within the memory system, serial access to these data may slow down the image processing operations because one memory module can respond only to one access at a given time. Because there are many image points to be processed, a special memory system is required to reduce the overall access time. In image processing, frequently used shapes of subarrays are horizontal sequence (1×pq), vertical sequence (pq×1), and block (p×q), where p and q are design parameters. In order to reduce overall access time of these data, several authors have studied methods which distribute many data in different memory modules and which access these data in parallel. 
     A number of authors have described several methods that permit simultaneous access to data elements in a row, a column, a diagonal, and/or a rectangular area of a two-dimensional array. See the following publications: C. D. Coleman, et al, &#34;Bank of Memories System for Multiword Access&#34;, IBM Technical Disclosure Bulletin, Vol. 9, pp. 1182-1183, February 1967; A. Weinberger, &#34;Multiword, Multidirectional Random Access Memory System&#34;, IBM Technical Disclosure Bulletin, Vol. 10, pp. 997-998, December 1967; D. J. Kuck, &#34;ILLIAC IV Software and Application Programming&#34;, IEEE Transactions Computers, Vol. C-17, pp. 758-770, August, 1968; D. H. Lawrie, &#34;Access and Alignment of Data in an Array Processor&#34;, IEEE Transactions Computers, Vol. C-24, pp. 1145-1155, December, 1975; D. C. Van Voorhis et al., &#34;Memory Systems for Image Processing, IEEE Transactions Computers, Vol. C-27, pp. 113-125, February, 1978; B. C. Lee et al., &#34;A Study on the Image Processor Memory Architecture&#34;, Proceedings International Computer Symposium 1980, Vol. II, pp. 954-960; P. Budnik et al., and &#34;The Organization and Use of Parallel Memories&#34;, IEEE Transactions Computers, Vol. C-20, pp. 1566-1569, December 1971. 
     In particular, the Van Voorhis et al article discloses several memory systems which permit simultaneous access to image points in a row, a column and a rectangular area of an image array. Such simultaneous access is necessary for many image processing operations. Van Voorhis et al essentially solved the problem of deciding how to assign image points to memory locations. The Van Voorhis et al article discusses: (1) six memory module assignment functions which distribute the image points among memory modules; (2) two address assignment functions which determine the addresses of the image points; and (3) circuitry that both calculates the addresses within memory modules simultaneously and routes these addresses to the memory modules. The memory module assignment functions provide memory systems with m=pq+1, 2pq and pq 2  memory modules. In order to speed up the memory system, Van Voorhis et al have restricted all of the parameters p, q and s of the function to powers of two. 
     However, the Van Voorhis et al article discloses that the memory system with m=pq+1 memory modules requires a number of modulo-(pq+1) operations and that these operations may make the described system too slow for some applications. The memory systems with m=2pq and pq 2  are suggested by Van Voorhis et al in order to avoid divisions (and modulo operations) involving a divisor that is not a power of 2. Because these two memory systems require many memory modules and many hardware components in the circuitry (the addressing circuitry calculates m addresses), they have the disadvantages of high hardware cost and high complexity in controlling the route and enabling circuitry. 
     SUMMARY OF THE INVENTION 
     The present invention provides an efficient memory system with m=pq+1 memory modules. In accordance with the present invention, the Van Voorhis et al addressing circuitry is divided into separate address calculating circuitry and address routing circuitry, so that the calculation of addresses of the subarray elements (image points) is separated from the movement of the addresses. In the address calculating circuitry of the present invention, only pq addresses are calculated, and they are calculated efficiently by using the relationships among the addresses of image data in a subarray, with no modulo-(pq+1) operations required. Using the relationships among the addresses and the index numbers of the memory modules results in simplified address calculating, address routing, and enabling circuitry. The address calculating circuitry of the present invention can be used in conjunction with any of the memory module assignment functions described in the above mentioned Van Voorhis et al article. Only one modulo-(pq+1) operation for MN (i, j, t), required in the address routing and enabling circuitry, needs to be performed during an address calculation. 
     The separation of the calculation of addresses of image points from the movement of the addresses results in a simple, memory system which is more efficient in speed and hardware cost, and less complex to control than the Van Voorhis et al system it replaces. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic block diagram of the general design of a memory system in accordance with the invention. 
     FIG. 2 is a schematic block diagram of address calculating circuitry in the memory system of FIG. 1 for block subarrays. 
     FIG. 3 is a schematic block diagram of address calculating circuitry in the memory system of FIG. 1 for horizontal sequence subarrays. 
     FIG. 4 is a schematic block diagram of address calculating circuitry in the memory of FIG. 1 for vertical sequence subarrays. 
     FIG. 5 is a schematic block diagram of combined address calculating circuitry for block, horizontal sequence, and vertical sequence subarrays in which the adder array is used in common in order to reduce hardware cost. 
     FIGS. 6(a), 6(b), and 6(c) respectively diagrammatically illustrate a DH(b) pattern for calculating horizontal sequence subarray element addresses in parallel; and transformations of the DH(b) pattern into corresponding matrix arrays. 
     FIG. 7 diagrammatically illustrates the operations for arranging vertical sequence subarray elements for routing. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In a memory system constructed in accordance with the present invention, modulo -, divide -, and multiply - operations are required only for the &#34;p-i//p&#34;, &#34;q-j//q&#34;, α(i, j) (i.e., (i/p)s+j/q), and MN(i, j, t) (i.e., ((iq+j)+pq-EQ (t, 3)*(q-1))//(q+1)) computations described hereinafter. Using special high speed digital units (e.g., the high-speed digital divider unit proposed in [8]) by J. H. P. Zurawski et al in &#34;Design of High-Speed Digital Divider Units&#34;, IEEE Transactions Computers, Vol. C-30, pp. 691-699, September, 1981 for these operations can eliminate the restriction that the parameters p, q, and s all be powers of 2. 
     Referring to FIG. 1, a general design for memory systems in accordance with the present invention that use m=pq+1 memory modules will now be described. 
     An image can be represented by an M×N array I (*, *) of image points, where each element I(i, j) for 0≦i&lt;M and 0≦j&lt;N is a set of integers that represents the color and intensity of a portion of the image. Image processing operations require a memory system that permits simultaneous access to the pq image points in blocks, in horizontal sequences, and in vertical sequences in an image array I(*, *) as follows: ##EQU1## 
     In order to distribute the elements of the M×N image array I (*, *) among the m=pq+1 memory modules, a memory module assignment function must place in distinct memory modules the array elements that are to be accessed simultaneously. Also, an address assignment function must allocate different addresses to array elements assigned to the same memory module. 
     A memory module assignment function is: 
     
         μ (i, j)=(iq+j)//(pq+1). 
    
     This function provides the memory system with m=pq+1 memory modules and permits access to all of p×q, 1×pq, and pq×1 subarrays, as described in the above mentioned Van Voorhis et al article. 
     In the above equation, the notation &#34;x//y&#34; is used to denote the nonnegative remainder that results from the integer division of x by y. 
     The address assignment function 3  which determines the address of an element within a memory module is: 
     
         α(i, j)=(i/p) s+j/q, 
    
     where s can be any integer satisfying 
     
         s≧N/q 
    
     s M/p≦c=capacity of each memory module. 
     As used herein, the notation &#34;x/y&#34; denotes the quotient that results from the integer division of x by y, and the notation &#34;x&#34; indicates the smallest integer greater than or equal to x. 
     The address assignment function is also described in the above mentioned Van Voorhis et al article. 
     Referring to FIG. 1, the memory system of the present invention generally comprises control circuitry and enabling circuitry (shown as combined circuitry (CEC)); pq+1 memory modules (D) each having a memory address register (MAR) and a memory buffer register (MBR); address calculating circuitry (ACC); separate address routing circuitry (R3); data routing circuitry (R1, R2); a data register (DR); t-, i- and j- input registers B0, B1 and B2, respectively; and several gates (not shown). The control circuitry controls the overall system operation in response to t, i, j inputs. The enabling circuitry enables only pq of the memory modules (D). The address calculating circuitry (ACC) calculates the addresses of image data in block, horizontal sequence and vertical sequence for block, horizontal sequence and vertical sequence subarrays, respectively, in response to control signals from the control circuitry, and temporarily stores the addresses in an address register (AR). The address routing circuitry (R3) moves the calculated addresses in register (AR) to the memory address registers (MAR) of the appropriate memory modules (D) in response to control signals from the control circuitry. The data routing circuitry (R1, R2) moves the image data between the data register (DR) and the memory buffer registers (MBRs) of the appropriate memory modules (D) in response to further control signals from the control circuitry. 
     When a particular subarray is stored, the memory system shown in FIG. 1 performs the following operations sequentially: 
     (1) the t-, i-, and j - registers (B0, B1 and B2, respectively) are respectively set to indicate the shape (p×q, 1×pq, or pq×1) and to indicate the coordinates of the upper lefthand element I (i, j) of the desired subarray, and the subarray is placed in a data register (DR) in row - major order; 
     (2) the address calculating circuitry (ACC) computes the appropriate address for each element; 
     (3) routing control circuitry including in control and enabling circuitry (CEC) causes data routing circuit R1 and address routing circuit R3 to route each element and each address to the memory modules (D). The enabling circuitry (CEC) enables only the desired modules to be accessed; and 
     (4) a write signal (WE) causes the subarray elements to be stored simultaneously, in the pq enabled modules (D). 
     Similarly, when a subarray is to be retrieved from the memory system: 
     (1) the t-, i-, and j-registers (B0, B1, B2) are set; 
     (2) the address calculating circuitry (ACC) calculates the addresses; 
     (3) the routing control circuitry causes address routing circuit (R3) to route the addresses to the memory modules (D) and the enabling circuitry (CEC) enables the pq memory modules that contain elements of the subarray; 
     (4) a read signal (RD) causes the pq subarray elements to be retrieved from the enabled modules; and 
     (5) the routing control circuitry causes data routing circuit R2 to route the elements to the data register to arrange the elements in row - major order. 
     In order to explain the address calculating circuitry for block subarrays (FIG. 2), the difference between the address of the upper left-hand element (i.e., α(i, j)) and the addresses of the remaining elements (i.e., α(i+a, j+b)) is discussed. When the desired subarray is a block, the addresses are ##EQU2## From the address of the upper lefthand element in any block, the addresses of the remaining elements in that block can be calculated easily by adding DB(a, b) to α(i, j). 
     In order to calculate pq addresses in parallel, one &#34;global logic (10), one &#34;column logic&#34; (20), one &#34;row logic&#34; (30), pq adders (41) and address registers (42) preferred as follows: 
     (1) The global logic (10) calculates α(i, j). 
     (2) The column logic (20) consists of a circuit (21) which calculates &#34;q-j//q&#34; one decoder (22) and (q-2) OR gates (23), and it prepares the DB(0, b) pattern for 0≦b≦q-1. The outputs of the decoder, whose input is the output of circuit 21 determine the position &#34;b&#34; from which DB(0, b)=1, and the OR gates (23) make the DB(0, b) pattern for 0≦b≦q-1. 
     (3) The row logic (30) consists of a circuit 31 which calculates &#34;p-i//p&#34;, one decoder (32), (p-2) OR getes (35), and (p-1) registers (33) that hold an integer &#34;s&#34;. The row logic prepares the DB(a, 0) pattern for 0≦a≦p-1. The outputs of the decoder (32), whose input is the output of circuit 31, determine the position &#34;a&#34; from which DB(a, 0)=s, and the outputs of the OR gates (35) determine which registers are to be enabled. 
     (4) There are three inputs to each adder (41), designated as A, B, and C. Input A is 0 when the output of the appropriate OR gate (35) in the row logic (30) is 0, or s when 1. Input B is α(i, j) and carry input C is the output of the appropriate OR gate (23) in the column logic (20). Each address assignment function storage unit (42) stores the address assignment function which determines the address within a memory module as discussed above. 
     Using procedures similar to those for a block subarray, addresses of the elements in horizontal sequence can be calculated in parallel. In horizontal sequence, the addresses of the elements are: 
     
         α(i, j+b)=(i/p)*s+(j+b)/q, 0≦b&lt;pq. 
    
     The difference between α(i, j) and α(i, j+b) is: ##EQU3## DH(b) can be represented as follows: ##EQU4## 
     The DH(b) pattern presented above is illustrated in FIG. 6(a). This pattern can be transformed into p rows with q columns each, FIG. 6(b). Further this pattern can be transformed as shown in FIG. 6(c) which results in simple circuitry. Address calculating circuitry for a horizontal sequence is shown in FIG. 3. The column logic (20) in this circuitry is the same as that for a block. Each adder (41) receives k, α(i, j), and 0/1 as the inputs A, B, and C respectively. The global logic (10) is the same as that for a block. The row logic(30A) consists of (p-1) registers (34). 
     In vertical sequence, addresses of elements are: 
     
         α(i+a, j)=((i+a)/p)*s+j/q, 0≦a&lt;pq. 
    
     This difference between α(i, j) and α(i+a, j) is: ##EQU5## DV(a) can be represented as follows: ##EQU6## 
     FIG. 4 represents address calculating circuitry for a vertical sequence. The row logic (30) in FIG. 4 determines the position &#34;p-i//p&#34; and it makes a DV(a) pattern for 0≦a≦p-1. Input A of each adder (40) in the first row is ks for 0≦k≦q-1, and Input A of each adder (40) in the other rows is s or 0. Input B of each adder (40) in the first row is α(i, j) and input B of each adder (40) in the other rows is the output of the adder in the first row. Input C is 0. 
     The global logic (10) is the same as that for a block. The column logic (20A) consists of (q-1) registers (24). 
     The global logic (10) and the adder array (40) are the same for a block (FIG. 2), horizontal sequence (FIG. 3), and vertical sequence (FIG. 4). The column logics (20) for a block and horizontal sequence are same. The row logics (30) for a block and vertical sequence are same. So, the three address calculating circuitries can be combined into the circuitry of FIG. 5 wherein the enable inputs of the decoders (22, 32) and registers (24, 34) are used as the selection inputs for the desired subarray. Decoder 1(22) is enabled for block and horizontal sequences. Decoder 2(32) is enabled for block and vertical sequences. The column registers (24) are enabled for a vertical sequence. The row registers 2(34) are enabled for a horizontal sequence. 
     The control and enabling circuitry must determine which pq memory modules are selected and it must control the address calculating circuitry, the data routing circuitry, and address routing circuit. 
     The p q memory modules, which are accessed for the case of BL(i, j), HR(i, j), and VR(i, j) are: ##EQU7## Therefore, the index number of the memory module, which is not accessed, is 
     
         MN (i, j, t)=(iq+j+pq-EQ (t, 3)*(q-1))//(pq+1). 
    
     (t=1 for accesses to blocks, t=2 for horizontal sequences, t=3 for vertical sequences and EQ(t, 3)=1 if t=3) 
     One decoder (input: MN (i, j, t)) is used to implement this enabling circuitry. Inverted outputs are used as pq enabling signals for the selected pq memory modules. One disabling signal is also obtained from the inverted outputs for the other memory module. 
     Index numbers of the pq memory modules which are accessed for BL(i, j) and HR(i, j), are (iq+j)//(pq+1), (iq+j+1)//(pq+1), . . . , (iq+j+pq-1)//(pq+1). Therefore, the data routing circuit R1 must rotate the data register right by (iq+j-1)//(pq+1) times for BL(i, j) and HR(i, j), which is the same as MN(i, j, t). 
     For the case of VR(i, j), the data routing circuit R1 must arrange the data register such that the index numbers of the memory modules of the elements are aligned continuously like those of BL(i, j) and HR(i, j). 
     The index numbers of the memory modules which are accessed for VR(i, j), are: ##EQU8## Let A (k)=(kq)//(pq+1), 0≦k≦pq-1. From the identity k=k/p*p+k//p, 
     A(k)=(k/p*p*q+k//p*q)//(pq+1). 
     Let k/p=k1 and k//p=k2, so that A(k)=B(k1, k2). ##EQU9## Therefore, the following FORTRAN - like program can arrange A(k) continuously from (1-q)//(pq+1) to ((p-1) q)//(pq+1): 
     Integer k, p, q 
     D0 1 k=0, pq-1 
     K1=k/p 
     k2=k//p 
     B(k2, k1)=A(k); elements are stored in column-major order 
     1 Continue 
     D0 2 k2=0, p-1 
     D0 2 k1=0, q-1 
     2 A(k2* q+k1)=B(k2, q-k1-1) 
     This can be performed in parallel as shown in FIG. 7. 
     The index numbers of the memory modules are arranged from (μ (i, j)+1-q)//(pq-1) to (μ (i, j)+(p-1) q)//(pq+1). Then, the number of times required for right-rotation is (iq+j-q)//(pq+1), which is the same as MN (i, j, t). 
     Let the inputs to the data routing circuit R1 be labeled D(0), D(1), . . . , D(pq), where D(0), . . . , D(pq-1) are positions of the data register and D(pq)=0. Let the outputs of R1 be labeled M(0), M(1), . . . , M(pq). Then the data routing circuit R1 performs the following patterns: 
     (1) A two-way selector is required to achieve the routing pattern: 
     
         D&#39; (k)←D(k//q)*p+k/q)*EQ(t, 3)+EQ(t, 3)*D(k), 0≦k≦pq-1; 
    
     
         D&#34; (k)←D&#39; ((k/q)*q+q-1-k//q)*EQ(t, 3)+EQ(t, 3)*D&#39;(k), 0≦k≦pq-1. 
    
     (2) A variable right rotate permuter is required to achieve the following pattern: 
     
         M(k)←D&#34; ((k-MN(i, j, t)-1)//(pq+1)), 0≦k≦pq. 
    
     Similarly, the data routing circuit R2 must be able to perform the inverses of these routing patterns. The address routing circuit R3 must be able to perform the above routing patterns of R1 except that the data register is replaced by the address register. 
     The memory system described hereinabove permits simultaneous access to the image points in block, horizontal sequence, and vertical sequence subarrays in a digitized image array. This system is more efficient and less expensive than those it replaces. 
     REFERENCES 
     [1] C. D. Coleman and A. Weinberger, &#34;Bank of Memories system for multiword access&#34;, IBM Tech. Disclosure Bulletin, Vol. 9, pp. 1182-1183, Feb. 1967. 
     [2] A. Weinberger, &#34;Multiword, multidirectional random access memory system&#34;, IBM Tech. Disclosure Bulletin, Vol. 10, pp. 997-998, Dec. 1967. 
     [3] D. J. Kuck, &#34;ILLIAC IV software and application programming&#34;, IEEE Trans. Comput., vol. C-17, pp. 758-770, Aug. 1968. 
     [4] D. H. Lawrie, &#34;Access and alignment of data in an array processor&#34;, IEEE Trans. Comput., vol. C-24, pp. 1145-1155, Dec. 1975. 
     [5] D. C. Van Voorhis and T. H. Morrin, &#34;Memory systems for image processing&#34;, IEEE Trans. Comput., vol. C-27, pp. 113-125, Feb. 1978. 
     [6] B. C. Lee and J. W. Park, &#34;A study on the image processor memory architecture&#34;, Proc. of Int. Comput. symp. 1980. vol. II, pp. 954-960. 
     [7] P. Budnik and D. J. Kuck, &#34;The organization and use of parallel memories&#34;, IEEE Trans. Comput., vol. C-20, pp. 1566-1569, Dec. 1971. 
     [8] J. H. P. Zurawski and J. B. Gosling, &#34;Design of high-speed digital divider units&#34;, IEEE Trans. Comput., vol. C-30, pp. 691-699, Sep. 1981.