Two axis fast access memory

• US 4,667,190 A
• Filed: 06/20/1983
• Issued: 05/19/1987
• Est. Priority Date: 07/30/1982
• Status: Expired due to Term

• Current Assignee: Theseus Research, Inc.
• Original Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Inventors: Fant, Karl M.
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US06/505,630
• Time in Patent Office: 1,429 Days
• Field of Search: 340/727, 340/729, 340/747, 340/750, 340/798, 340/799, 340/800, 340/801
• US Class Current: 345/568
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G09B 9/301 by computer-processed or -generated image

Abstract

The disclosure relates generally to a computer generated synthesized imaging system. More particularly, the invention relates to a method and apparatus for providing fast access to a two axis memory wherein consecutive data elements in both row and column orientation of a data set represented as a matrix may be obtained at a rate faster than the access time of memory elements utilized. A speed-up of access speed by a factor N may be achieved, where N is a power of 2 (2, 4, 8, 16 . . . ). The memory elements are organized in N independently addressable banks of data memories. The matrix oriented data is mapped into these N banks such that any N contiguous data elements of any row or any column reside in different memory banks. Any N contiguous data elements of any row or column may then be accessed within the access time of any one memory bank. The N contiguous data elements may then be read from memory in a single memory cycle. These N data elements can then be multiplexed in the proper sequence into a data stream operating N times faster than the basic access speed of the memory elements used.

Claims

1. A method for image address to memory address mapping comprising the steps of demultiplexingly mapping pixels of a two axis (A×

A) square array image into 2^N memory banks such that memory elements corresponding to any 2^N consecutive pixels of any row and any column of said image reside in different banks and can be accessed simultaneously, said mapping yielding a stream of corresponding row or column oriented pixels with each pixel being identified by its image row and column positions, assigning a designated memory bank and an address therein to each of said pixels by demultiplexing said stream wherein said demultiplexing further comprises processing each said image pixel address to obtain (1) a modulo 2^N number for said designated memory bank by derivation from the lower N bits of said image row and column pixel address, and (2) said address in said designated memory bank as one of a sequence of numbers according to the sum of the image row plus twice a number equal to the result of ANDING binary bits of the image column number and respective binary bits of a number equal to A/2^N.

2. A method for address mapping between an image and a memory comprising the steps of demultiplexingly mapping pixels of two axis (A×

A) square array image into 2^N memory banks such that memory elements coresponding to any 2^N consecutive pixels of any row and any column of said image reside in different banks and can be accessed simultaneously, multiplexingly scanning said banks to sequentially output sets of memory elements corresponding to sets of 2^N consecutive pixels of said image rows or columns, said memory elements in each said set being output simultaneously, said scanning yielding a stream of memory elements with each of said memory elements being identified by the particular bank in which it resides and its address therein, assigning corresponding image row and column positions to each of said memory elements by multiplexing said sets, said multiplexing further comprising processing each of said memory elements to obtain an output number used in determining the coresponding image column by a rotation function determined by the recurring sequential relationship between the binary bits of said particular bank and the lower N binary bits of said particular address in said bank, said image column being determined as the sum of the output number of said rotation function and a number equal to the result of ANDING binary bits of the particular address in the memory bank with binary bits of A and dividing the resultant by A/2^N, and processing each said memory element to obtain the corresponding image row by ANDING binary bits of the particular address in the memory bank with binary bits of a number equal to A-1.

3. Circuit means for image address to memory address mapping of a two axis (A×

A) square array, comprising, 2^N independently accessible memory banks, row counter means and column counter means to provide horizontal or vertical address scanning of said array, and demultiplexing means for mapping pixels of said array into said banks so that any 2^N consecutive pixels of any row and any column of said image reside in different banks so that they can be accessed simultaneously, said demultiplexing means including means for assigning bank designations and addresses therein to each of said image elements by (1) determining a modulo 2^N number for said memory bank designation by derivation from the lower N bits of said image row and column image element address, and (2) said address in said designated memory bank as one of a sequence of numbers according to the sum of the image row plus twice a number equal to the result of ANDING binary bits of the image column number and respective binary bits of a number equal to A/2^N.

4. Circuit means for address mapping between image address and memory address of a two axis (A×

A) square array, comprising, 2N independently accessible memory banks, row counter means and column counter means to provide horizontal or vertical address scanning of said array, demultiplexing means for mapping pixels of said array into said banks so that any 2^N consecutive pixels of any row and any column of said image reside in different banks so that they can be accessed simultaneously, multiplexing means for row scanning said banks to sequentially output sets of memory elements corresponding to sets of 2^N consecutive pixels of said image rows or columns, means for outputting said memory elements in each of said sets simultaneously, said multiplexing means including computer means for assigning output image row and column positions to said bank elements, said computing means including a rotation function means for obtaining an output number used in determining the corresponding image column by a rotation function determined from the relationship between the binary bits of said particular bank and the lower N binary bits of said particular bank address, means for determining the corresponding image column by summing the output number of said rotation function and a number equal to the result of ANDING binary bits of the particular address in the memory bank with binary bits of A and dividing the resultant by A/2^N, and means for determining the corresponding image row by ANDING binary bits of the particular address in the memory bank with binary bits of a number equal to A-1.