Method and apparatus for accessing horizontal sequences, vertical sequences and rectangular subarrays from an array stored in a modified word organized random access memory system

Claim 2

A word organized random access memory system modified for image processing operations so that the memory system can store an image array comprising a predetermined number rpsq of image points arranged in a predetermined number rp of rows with a predetermined number sq of image points in each row, and modified so that every 1 × pq subarray, every pq × 1 subarray and every p × q subarray of the rp × sq image array can be accessed in a single memory cycle, the system comprising: memory means for storing rpsq image points in the cells of pq+1 different memory modules, each memory module being an entity capable of storing rs image points in distinguishable cells, only one cell of each module being accessible at any single instant of time; means for selectively designating, from all 1 × pq subarrays, all pq × 1 subarrays and all p × q subarrays stored in said memory means, which subarray is to be accessed; and accessing means responsive to said designating means for causing each image point in the designated subarray to be selectively read from or written into a predetermined cell of a predetermined memory module so that the entire designated subarray is accessed in a single memory cycle.

Claim 3

A memory system according to claim 1 wherein the accessing means include: a data register having a capacity of at least pq image points; routing circuitry for causing each image point to be routed between the data register and the predetermined memory module; and address calculation circuitry and enable circuitry coacting with the routing circuitry for causing each image point to be selectively retrieved from or written into the predetermined cell location of the predetermined module.

Claim 4

A memory system according to claim 1 wherein the designating means include: means for designating the shape of the subarray to be accessed; and means for designating the location of the starting point of the subarray to be accessed.

Claim 5

A memory system according to claim 1 wherein the memory modules are labeled as modules 0, 1, . . ., pq, and wherein the memory module predetermined for storing the jth image point on the ith row of the image array is given by the relation (iq+j)//(pq+1), which denotes the nonnegative remainder that results when the quantity (iq+j) is divided by (pq+1).

Claim 6

A memory system according to claim 1 wherein the cells of each memory module are labeled as cells 0, 1, . . ., (rs-1), and wherein the cell predetermined for storing the jth image point on the ith row of the image array is give by the relation (i/p)s+(j/q), which denotes the sum of two terms: s times the quotient when p is divided into i; and the quotient when q is divided into j.

Claim 7

The memory system according to claim 4 wherein the means for calculating the relation (iq+j)//(pq+1) comprises: a plurality of cells for performing a modulo-(pq+1) division, a plurality of adder means, means for coupling the cells and adder means in cascade to produce a calculating circuit, and means to enter signals corresponding to i and j as inputs to the calculating circuit so that the value (iq+j)//(pq+1) is produced.

Claim 8

The memory system according to claim 4 wherein the means for calculating the relation (iq+j)//(pq+1) comprises: a first plurality of cells for performing a modulo-(pq+1) division, on pq times any value between 0 and pq-1, a second plurality of cells for performing a modulo-(pq+1) division on any value between 0 and 2pq+1, means for coupling said first cells to receive input signals and means to couple the output of said first cells to a cascade of alternating adder means and said second cells to produce a calculating circuit, and means to enter signals corresponding to i and j as inputs to the calculating circuit so that the value (iq+j)//(pq+1) is produced.

Claim 9

A word organized random access memory system modified for image processing operations so that pq image points of all 1 × pq subarrays, all pq × 1 subarrays and all p × q subarrays of at most an rp × sq image array I(*,*) storable in the memory system can be selectively retrieved from or written into the system in a single memory cycle; each image point I(i,j) assuming a Boolean value when i and j lie in the respective ranges 0≦i<rp and 0≦j<sq, the system comprising: memory means for storing rpsq image points in the cells of pq+1 different memory modules, each memory module being an entity capable of storing rs image points in distinguishable cells, only one cell of each module being accessible at any single instant of time; means for designating the shape of a subarray to be accessed, as for example, with t=00 for a 1 × pq array, t=01 for a pq × 1 array and t=10 for a p × q array; means for designating the location of the starting point I(i,j) of the subarray to be accessed; a register for holding at least pq image points; routing circuitry for causing the appropriate subarray points to be routed between the kth memory module and position γ of the register, where k lies in the range 0≦k≦pq and where γ is defined by the relation γ=(k-iq-j)//(pq+1) if t=00, or if t=10; which denotes the nonnegative remainder that results when the quantity k-iq-j is divided by the quantity pq+1; γ=[-p(k-iq-j)]//(pq+1) if t=01, which denotes the nonnegative remainder that results when the product of minus p times the quantity k-iq-j is divided by the quantity pq+1; enabling circuitry for causing the kth memory module to store or retireve a subarray element if the previously defined value γ is less than pq and for inhibiting the kth memory module from storing or retrieving a subarray element if γ=pq; and addressing circuitry for determining the appropriate cell location 1(i,j,k,t) within the kth module according to the relation: 1(i,j,k,t)=(i/p)s+(j+γ)/q, if t=00, which denotes the sum of two terms: s times the quotient i/p and the quotient (j+γ)/q, where γ=(k-iq-j)//(pq+1) is the value previously defined for t=00, 1(i,j,k,t) = ([i+γ]/p)s+j/q, if t=01, which denotes the sum of two terms: s times the quotient (i+γ)/p and the quotient j/q, where γ=[-p(k-iq-j)]//(pq+1) is the value previously defined for t=01; 1(i,j,k,t) = ([i+γ/q]/p)s+(j+γ//q)/q, if t=10, which denotes the sum of two terms: s times the quotient that results when p is divided into i plus the quotient γ/p, and the quotient that results when q is divided into j plus the remainder when γ is divided by q, where γ = (k-iq-j)//(pq+1) is the value previously defined for t=10.

Claim 10

A word organized random access memory system modified for image processing operations so that pq image points of all 1 × pq subarrays, all pq × 1 subarrays and all p × q subarrays of at most an rp × sq image array I(*,*) storable in the memory system can be selectively retrieved from or written into the system in a single memory cycle; each image point I(i,j) assuming a Boolean value when i and j lie in the respective ranges 0≦i<rp and 0≦j<sq, the system comprising: memory means for storing rpsq image points in the cells of pq+1 different memory modules, each memory module being an entity capable of storing rs image points in distinguishable cells, only one cell of each module being accessible at any single instant of time; means for designating the shape of a subarray to be accessed, as for example, with t=00 for a 1 × pq array, t=01 for a pq × 1 array and t=10 for a p × q array; means for designating the location of the starting point I(i,j) of the subarray to be accessed; a register for holding at least pq image points; routing circuitry for causing the appropriate subarray points to be routed between the kth memory module and position γ of the register, where k lies in the range 0≦k≦pq and where γ is defined by the relation γ=(k-iq-j)//(pq+1) if t=00, or if t=10; which denotes the nonnegative remainder that results when the quantity k-iq-j is divided by the quantity pq+1; γ=[-p(k-iq-j)]//(pq+1) if t=01, which denotes the nonnegative remainder that results when the product of minus p times the quantity k-iq-j is divided by the quantity pq+1; enabling circuitry for causing the kth memory module to store or retireve a subarray element if the previously defined value γ is less than pq and for inhibiting the kth memory module from storing or retrieving a subarray element if γ=pq; and addressing circuitry for determining the appropriate cell location 1(i,j,k,t) within the kth module according to the relation: 1(i,j,k,t)=(i/p)s+(j+γ)/q, if t=00, which denotes the sum of two terms: s times the quotient i/p and the quotient (j+γ)/q, where γ=(k-iq-j)//(pq+1) is the value previously defined for t=00, 1(i,j,k,t) = ([i+γ]/p)s+j/q, if t=01, which denotes the sum of two terms: s times the quotient (i+γ)/p and the quotient j/q, where γ=[-p(k-iq-j)]//(pq+1) is the value previously defined for t=01; 1(i,j,k,t) = ([i+γ/q]/p)s+(j+γ//q)/q, if t=10, which denotes the sum of two terms: s times the quotient that results when p is divided into i plus the quotient γ/p, and the quotient that results when q is divided into j plus the remainder when γ is divided by q, where γ = (k-iq-j)//(pq+1) is the value previously defined for t=10.