Table lookup addressing by dichotomy window generation

Abstract

Table lookup for an N.times.N image on an M.times.M 2D array is speeded by enhancing an address word to access table entries greater in number than the address word bit structure normally permits. This is done by organizing a 2D array (M.times.M) as a 8-interconnected array, decomposing the N.times.N array into N/M.times.N/M subimages, and generating and enhancing dichotomy windows of size K.times.K at the subimage level as table lookup addresses. For arbitrary combinations of M, N and K, the address word is broken into two dichotomies, and each dichotomy is altered by incrementing and decrementing. This provides multi-bit addressing for sufficient table entries to carry out in a single cycle the complex table lookup required for processing a multi-bit (i.e., 3.times.3) window. The output of a programmable logic array accesses four quadrants of memory. The current pixel number CPN is made available from the computer control. This is divided into two halves, HCPN and LCPN, which are incremented or decremented to form signals IHCPN, ILCPN, DHCPN and DLCPN. Carry and borrow signals CIH and BDH, respectively, are concatenated with the other signals to provide the requisite number of table addresses. Address 00, for example, is HCPN when CIH=0. Addresses for the other memory banks are derived similarly.