Patent Abstract:
An apparatus ( 20 ) and method ( 22 ) for transparently accessing and interpolating data are provided. Consecutive data values ( 24 ) of a function are generated and indexed. Even-indexed data values ( 24 ) are stored in an even-indexed table ( 30 ) and odd-indexed data values ( 24 ) are stored in an odd-indexed table ( 32 ). Adjacent-indexed data values ( 24 ) are acquired substantially simultaneously from even- and odd-indexed tables ( 30,32 ) with the first-indexed value (G n ) extracted from the even-indexed table ( 30 ) when an integral portion (A [N] ) of a memory address (A [N+F] ) is even and from the odd-indexed table ( 32 ) when the integral portion (A [N] ) is odd. A fractional portion (A [F] ) of the memory address (A [N+F] ) is converted into an incremental value (Δ). An interpolation circuit ( 102 ) then produces an output data value (G Out ) as a sum of the first-indexed value (G n ) plus a product of the incremental value (Δ) times a difference of the second-indexed value (G n+1 ) less the first-indexed value (G n ).

Full Description:
TECHNICAL FIELD OF THE INVENTION 
     The present invention relates to the field of mathematical interpolators. More specifically, the present invention relates to the use of mathematical interpolators in conjunction with computer memories. 
     BACKGROUND OF THE INVENTION 
     A computer memory often contains a table of continuous and/or cyclic data. Such data tables are typically used to provide mathematical functions, such as trigonometric and logarithmic functions. A typical such table may contain sine and/or cosine data for a fast Fourier transform function. 
     In order to realize a desired degree of accuracy, such tables tend to be large. Large tables require extensive use of computer memory. This increases the on-chip real estate and power consumption, thereby increasing the overall cost of the tables. 
     Some method is often used to reduce the overall size of the table and of the computer memory in which it is contained. The approach most often taken is that of using a smaller table in conjunction with an interpolator to approximate inter-tabular values. 
     One problem of conventional table-plus-interpolator schemes is that two sequential data-value accesses need be performed in order to obtain data values above and below the desired value. The interpolator then may interpolate the “correct” value between these two values. 
     Since the accessing computer must perform two accesses, such double-access schemes are non-transparent. That is, the computer is obliged to recognize the special nature of the table-plus-interpolator circuitry. This recognition is usually made in software. 
     The replacement of a large table with a smaller table plus an interpolator typically cannot be accomplished without an alteration of the software in order to accomplish the two sequential memory accesses. This inhibits the use of software intended for use with a single large table, thereby limiting the use of table-plus-interpolator schemes. 
     SUMMARY OF THE INVENTION 
     Accordingly, an advantage of the present invention is provided by a transparent data access and interpolation apparatus and method therefor. 
     Another advantage of the present invention is provided by a data access apparatus and method that are transparent to the accessing processor. 
     Another advantage of the present invention is provided by a data access apparatus and method that are usable with pre-existing software. 
     Another advantage of the present invention is provided by a data access apparatus and method that obtain two values for interpolation in a single access. 
     Another advantage of the present invention is provided by a data access and interpolation apparatus that significantly reduces on-chip memory area. 
     Another advantage of the present invention is provided by a data access and interpolation method that reduces power consumption during access. 
     The above and other advantages of the present invention are carried out in one form by a method of accessing and interpolating data, wherein the method incorporates producing first and second address portions, generating a plurality of data values of a function, storing a first half of the data values in a first table, storing a second half of the data values in a second table, accessing one of the data values in each of the first and second tables substantially simultaneously in response to said the address portion, and determining an output data value greater than or equal to one of the accessed data values in response to the second address portion. 
     The above and other advantages of the present invention are carried out in another form by an apparatus for accessing and interpolating data within a set of data values, the apparatus incorporating a first memory circuit containing a first table having a first half of the set of data values and configured to output a first table data value in response to a first address portion, a second memory circuit containing a second table having a second half of the set of data values and configured to output a second table data value in response to said first address portion, a routing circuit coupled to the first and second memories and configured to output a first-indexed data value and a second-indexed data value in response to the first and second table data values, and an interpolation circuit coupled to the routing circuit and configured to produce an output data value that combines the first-indexed data value and the second-indexed data value in response to a second address portion. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     A more complete understanding of the present invention may be derived by referring to the detailed description and claims when considered in connection with the Figures, wherein like reference numbers refer to similar items throughout the Figures, and: 
     FIG. 1 shows a schematic block diagram depicting a data access and interpolation apparatus in accordance with a preferred embodiment of the present invention; 
     FIG. 2 shows a flowchart depicting a process for accessing and interpolating data using the apparatus of FIG. 1 in accordance with a preferred embodiment of the present invention; 
     FIG. 3 shows an exemplary table having an integral-power-of-two number of data values to be emulated by the apparatus of FIG. 1 using the process of FIG. 2 in accordance with a preferred embodiment of the present invention; 
     FIG. 4 shows a reduced table derived from the emulated table of FIG. 3 in accordance with a preferred embodiment of the present invention; 
     FIG. 5 shows an even-indexed table derived from the reduced table of FIG.  4  and configured for use in the apparatus of FIG. 1 in accordance with a preferred embodiment of the present invention; 
     FIG. 6 shows an odd-indexed table derived from the reduced table of FIG.  4  and configured for use in the apparatus of FIG. 1 in accordance with a preferred embodiment of the present invention; 
     FIG. 7 shows an exemplary table having a non-integral-power-of-two number of data values to be emulated by the apparatus of FIG. 1 using the process of FIG. 2 in accordance with a preferred embodiment of the present invention; 
     FIG. 8 shows a reduced table derived from the emulated table of FIG. 7 in accordance with a preferred embodiment of the present invention; 
     FIG. 9 shows an even-indexed table derived from the reduced table of FIG.  8  and configured for use in the apparatus of FIG. 1 in accordance with a preferred embodiment of the present invention; 
     FIG. 10 shows an odd-indexed table derived from the reduced table of FIG.  8  and configured for use in the apparatus of FIG. 1 in accordance with a preferred embodiment of the present invention; 
     FIG. 11 shows a flowchart depicting a table-access subprocess of the process of FIG. 2 in accordance with a preferred embodiment of the present invention; and 
     FIG. 12 shows a flowchart depicting an output-determining subprocess of the process of FIG. 2 in accordance with a preferred embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1 shows a schematic block diagram depicting an apparatus  20  for and FIG. 2 depicts a flowchart depicting a process  22  for transparent data access and interpolation in accordance with a preferred embodiment of the present invention. FIGS. 3 through 6 show exemplary tables for emulation of an integral-power-of-two (IPOT) number of data values  24  by the apparatus of FIG. 1 using the process of FIG. 2 in accordance with a preferred embodiment of the present invention. FIG. 3 shows an emulated table  26 ′ having IPOT data values  24  to be emulated, FIG. 4 shows a reduced table  28 ′ derived from emulated table  26 ′, and FIGS. 5 and 6 show even-and odd-indexed tables  30 ′ and  32 ′ derived from reduced table  28 ′. Similarly, FIGS. 7 through 10 show exemplary tables for emulation of a non-integral-power-of-two (NPOT) number of data values  24  by the apparatus of FIG. 1 using the process of FIG. 2 in accordance with a preferred embodiment of the present invention. FIG. 7 shows an emulated table  26 ″ having NPOT data values  24  to be emulated, FIG. 8 shows a reduced table  28 ″ derived from emulated table  26 ″, and FIGS. 9 and 10 show even-and odd-indexed tables  30 ″ and  32 ″ derived from reduced table  28 ″. The following discussion refers to FIGS. 1 through 10. 
     The operation of transparent data access and interpolation apparatus  20  and process  22  therefor is demonstrated herein through the use of two related examples. A first example uses the data depicted in tables  26 ′,  28 ′,  30 ′, and  32 ′. Table  26 ′ is the table of data to be emulated, i.e., the table that the computer will think it is addressing. In the first example, table  26 ′ (FIG. 3) is composed of 2 V  data values  24 , where V is a positive integer. That is, table  26 ′ has an integral-power-of-two (IPOT) number of data values  24  and is therefore an IPOT table. The first example is hereinafter the IPOT example. 
     Similarly, a second example uses the data depicted in tables  26 ″,  28 ″,  30 ″, and  32 ″. In this case, table  28 ″ (FIG. 7) is the table of data to be emulated. In the second example, table  26 ″ is composed of 2 V  data values  24 , where V is a positive value but not an integer. That is, table  26 ″ has a non-integral-power-of-two (NPOT) number of data values  24  and is therefore an NPOT table. The second example is hereinafter the NPOT example. 
     For purposes of identification and simplicity of text, all items common to either both or neither of the IPOT and the NPOT examples have un-accented reference numbers, items peculiar to the IPOT example have prime reference numbers, and items peculiar to the NPOT example have double-prime reference numbers. For example, emulated table  26  references either IPOT emulated table  26 ′ or NPOT emulated table  26 ″ or both. 
     Data access and interpolation apparatus  20  is substantially transparent to a computer (not shown) to which it is coupled. That is, apparatus  20  appears to the computer as a single memory circuit containing a table of data values  24 . Emulated tables  26  (FIGS. 3 and 7) are typical of the tables the computer thinks it is addressing. The use of apparatus  20  allows the use of smaller tables and related circuitry, thereby realizing a significant savings in on-chip real estate over the original (emulated) table and memory circuit, with attendant reductions in power consumption. It is desirable, therefore, that table  26  be replaced by apparatus  20 . 
     In both the IPOT and NPOT examples, tables  26  contain a large number O V  of consecutive data values  24  derived from a function, e.g., cosine values for one-half cycle as may be used in fast Fourier transform (FFT) analyses. In the IPOT example, table  26 ′ contains an integral-power-of-two number of consecutive data values  24 . In the example of FIG. 3, V=16, and table  26 ′ has O V =2 V =2 16 =65 536 data values  24 . 
     In the NPOT example, table  26 ″ contains a non-integral-power-of-two number of consecutive data values  24 . In the example of FIG. 7, V=6.807 354 92 . . . , and table  26 ″ has O V =2 V =2 26.807 354 92 . . .  = 112  data values  24 . 
     In a task  34  (FIG.  2 ), process  22  generates data values  24  for reduced table  28 . Through the use of conventional techniques known to those skilled in the art, it may be determined that the data of table  26  may be reduced while maintaining acceptable interpolation accuracy. For simplicity, each of the reduced-table data values  24  may be computed as:                R   I     =         R   W     ·     O   I         O   V               (   1   )                                
     where: 
     O I  is the emulated-table data-value index; 
     O V  is the number of emulated-table data values; 
     R W  is the number of reduced-table data values; and 
     R I  is the reduced-table data-value index. 
     As depicted in FIGS. 3 and 7, reduced-table index R I  is composed of an integral part A n  and a fractional part A f . In the IPOT example (FIG.  3 ), the data of table  26 ′ may be reduced from O V =2 V =2 16 =65 536 data values  24  to R W =2 W =2 10 =1024 data values  24 . This may be demonstrated by an even sample  36 ′ where emulated-table index O I =6424 and an odd sample  38 ′ where emulated-table index O I =13 549. Using equation (1), even sample  36 ′ computes as:                R   I     =           R   W     ·     O   I         O   V       =         1024   ·   6424     65526     =     100        24   64                   (1-1)                                
     where integral part A n =100 and fractional part A f ={fraction (24/64)}. Similarly, odd sample  38 ′ computes as:                R   I     =           R   W     ·     O   I         O   V       =         1024   ·   13549     65526     =     211        45   64                   (1-2)                                
     where integral part A n =211 and fractional part A f ={fraction (45/64)}. 
     Fractional part A f  has a resolution of 2 −6 ={fraction (1/64)}. Since tables  26 ′ and  28 ′ both have an IPOT number of data values  24 , the resolution of fractional part A f  is also an integral power of two. 
     In the NPOT example, the data of table  26 ″ (FIG. 7) is reduced from O V =2 V =2 6.807 354 92 . . .  =112 data values  24  to R W =2 W =2 4 =16 data values  24 . This may be demonstrated by an even sample  36 ″ where emulated-table index O I =90 and an odd sample  38 ″ where emulated-table index O I =93. Using equation (1), even sample  36 ″ computes as:                R   I     =           R   W     ·     O   I         O   V       =         16   ·   90     211     =     12        6   7                   (1-3)                                
     where integral part A n =12 and fractional part A f ={fraction (6/7)}. Similarly, odd sample  38 ″ computes as:                R   I     =           R   W     ·     O   I         O   V       =         16   ·   93     112     =     13        2   7                   (1-4)                                
     where integral part A n =13 and fractional part A f ={fraction (2/7)}. 
     The integral parts A n  of reduced-table index R I  form the indices of the data values  24  in reduced table  28 ″ (FIG.  8 ). Reduced table  28 ″ therefore has R W =2 W =2 4 =16 data values  24  at a first approximation. 
     Fractional part A f  has a resolution of 2 −2.807 35 . . .  ={fraction (1/7)}. This is not an integral power of two and cannot readily be expressed as a simple binary number. To achieve a reasonable accuracy, therefore, the resolution of the fractional part would desirably be increased to some power of two small enough to achieve the desired accuracy. In the example of FIG. 7, the pseudo power of two is 2 −9 ={fraction (1/512)}. 
     Those skilled in the art will appreciate that the hereinbefore discussed methodology for determining data values  24  for reduced table  28  is exemplary only and assumes a common sampling method having the greatest interpolation errors midway between on-curve samples (i.e., samples coincident with the curve) where the function exhibits the greatest curvature. The use of other methods, e.g., a piecewise linear least-squares method, may produce other data values  24  having reduced interpolation errors. Such other methods are well known to those of ordinary skill in the art and are beyond the scope of this discussion. The use of such other methods does not depart from the spirit of the present invention. 
     Reduced tables  28  contain R W =2 W  data values  24 , which is fewer than the O V =2 V  data values  24  of emulated tables  26 . Each reduced-table index R I  has an integral part A n  and a fractional part A f . The difference between adjacent values A n  is interpolated by apparatus  20  to provide approximations of the original O V  data values  24 . To do this, two adjacent data values  24  A n  and A n +1, are used to provide the interpolation difference. 
     In the IPOT example, even sample  36 ′ where emulated-table index O I =6424 in emulated table  26 ′ (FIG. 3) produces a reduced-table index R I =100{fraction (24/64)}, i.e., where  100≦R   I &lt;101. Therefore, even sample  36 ′ at reduced table  28 ′ (FIG. 4) is at A n =100 and A n +1=101. 
     Similarly, odd sample  38 ′ where emulated-table index O I =13 549 in table  26 ′ produces a reduced-table index R I =211{fraction (45/64)}, i.e., where 211≦R I &lt;212. Therefore, odd sample  38 ′ at reduced table  28 ′ is at A n =211 and A n +1=212. 
     In the NPOT example, even sample  36 ″ where emulated-table index O I =90 in table  26 ″ (FIG. 7) produces a reduced-table index R I =12{fraction (6/7)}, i.e., where 12≦R I &lt;13. Therefore, even sample  36 ″ at reduced table  28 ″ (FIG. 8) is at A n =12 and A n +1=13. 
     Similarly, odd sample  38 ″ where emulated-table index O I =93 in table  26 ″ produces a reduced-table index R I =13{fraction (2/7)}, i.e., where 13≦R I &lt;14. Therefore, odd sample  38 ″ at reduced table  28 ″ is at A n =13 and A n +1=14. 
     Because of this dual-sample property, it is desirable that reduced table contain R W +1=2 W +1 rather than R W =2 W  data values  24 . The additional data value  24 , where R I =2 N , allows for dual sampling where sample A n =2 N −1 and sample A n +1=2 N . This is demonstrated in FIGS. 3 through 6 (tables  26 ′,  28 ′,  30 ′, and  32 ′) by maximum sample  40 ′. 
     In a task  42  (FIG.  2 ), process  22  indexes the 2 W +1 data values  24  of reduced tables  28  (FIGS. 4 and 8) from 0 to 2 N , where each index is integral part A n  of reduced-table index R I  for that data value  24 . Therefore, IPOT-example reduced table  28 ′ has R W +1=2 W +1=2 10 +1=1025 data values  24  indexed from 0 to 1024, and NPOT-example reduced table  28 ″ has R W +1=2 W +1=2 4 +1=17 data values  24  indexed from 0 to 16. 
     Reduced table  28  contains 2 W +1 data values  24  with consecutive indices from 0 to 2 W . In a task  44  (FIG.  2 ), process  22  stores even-indexed ones of data values  24  in even-indexed tables  30 . Even-indexed table  30  therefore contains 2 W−1 +1 data values having consecutive even indices from 0 to 2 W . 
     Similarly, in a task  46  (FIG.  2 ), process  22  stores odd-indexed ones of data values  24  in odd-indexed tables  32 . Odd-indexed table  32  therefore contains 2 W−1  data values having consecutive odd indices from 1 to 2 W −1. 
     Those skilled in the art will appreciate that, due to the limitations of flow charts, e.g., FIGS. 2,  11 , and  12 , a task sequence may be implied that is not a requirement of the present invention. For example, the order in which tasks  44  and  46  are performed is irrelevant to the present invention. 
     The computer (not shown) to which data access and interpolation apparatus  20  (FIG. 1) is coupled addresses apparatus  20  using a primary address B [M] . Because the computer only sees primary address B [M] , apparatus  20  is transparent, i.e., the computer believes itself to be addressing emulated table  26  using primary address B [M] . 
     In a task  48 , process  22  produces a direct address A [N+F]  from primary address B [M] . Direct address A [N+F]  has an integral address A [N]  as a first address portion and a fractional address A [F]  as a second address portion. 
     Primary address B [M]  contains M address bits from B 0  through B M−1 , where M is a positive integer. Integral address A [N]  represents the integral portion of direct address A [N+F]  and contains N address bits from A 0  through A N−1 , where N is a positive integer. Fractional address A [F]  represents the fractional portion of direct address A [N+F]  and contains F address bits from A −F  through A −1 , where F is a positive integer. Because fractional address A [F]  is fractional, i.e., contains the address of a fractional data value, address bit A −1 =2 −1 =½, address bit A −2 =2 −2 =¼, etc. 
     In the IPOT example of FIGS. 3 through 6 (tables  26 ′,  28 ′,  30 ′, and  32 ′), emulated table  26 ′ has O V =2 V =2 16 =65 536 data values  24 , reduced table  28 ′ has R W =2 W =2 10 =1024 data values  24 , and fractional part A f  has a resolution of 2 −F =2 −6 ={fraction (1/64)}. Therefore, V=M=16, W=N=10, and F=6. Indeed, where V and W are both integral powers of two: 
     
       
           M=N+F.   (2) 
       
     
     This allows a direct relationship to exist between the bits of primary address B [M]  and direct address A [N+F] . This direct relationship is: 
     
       
         
               
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 primary 
                 direct 
               
               
                   
                 address 
                 address 
               
               
                   
                 B [M]   
                 A [N+F]   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 B M−1   
                 B 15   
                 A 9    
                 A N−1   
               
               
                   
                   
                 B 14   
                 A 8   
               
               
                   
                   
                 . . .  
                 . . .  
               
               
                   
                   
                 B 1   
                 A 1   
               
               
                   
                   
                 B 6   
                 A 0    
                 integral address A [N]   
               
               
                   
                   
                 B 5   
                 A −1   
                 fractional address A [F]   
               
               
                   
                   
                 B 4   
                 A −2   
               
               
                   
                   
                 . . .  
                 . . .  
               
               
                   
                   
                 B 1   
                 A −5   
               
               
                   
                   
                 B 0   
                 A −6   
                 A −F   
               
               
                   
                   
               
             
          
         
       
     
     Because of this direct relationship between primary address B [M]  and direct address A [N+F] , an optional address converter  50 , shown in FIG. 1, is not required. 
     In the NPOT example of FIGS. 7 through 10 (tables  26 ″,  28 ″,  30 ″, and  32 ″), however, emulated table  26 ″ has O V =2 V =2 6.807 354 92 . . .  =112 data values  24 , reduced table  28 ″ has R W =2 W =2 4 =16 data values  24 , and fractional part A f  has a resolution of 2 −F =2 −2.807 35 . . .  ={fraction (1/7)}. This means that primary address B [M]  must have at least seven bits (M≧7) where values above 112 are ignored. Similarly, fractional address A [F]  must have at least three bits (F≧3), but preferably has more to reduce the rounding error to acceptability. For purposes of simplicity, in the NPOT example of FIG. 7, fractional address A [F]  has nine bits (F=9) to allow resolution to the nearest {fraction (1/512)}, i.e., {fraction (1/7)}≈{fraction (73/512)}, {fraction (2/7)}≈{fraction (146/512)}, {fraction (3/7)}≈{fraction (219/512)}, {fraction (4/7)}≈{fraction (293/512)}, {fraction (5/7)}≈{fraction (366/512)}, and {fraction (6/7)}≈{fraction (439/512)}. Therefore, where V is not an integral power of two: 
       M≦N+F.   (3) 
     Those skilled in the art will appreciate that a value of F=9 is purely arbitrary and was chosen here for simplicity. In actual applications, greater values of F may be used to improve accuracy, e.g., F=16 or F=20. 
     In both the IPOT and NPOT examples presented herein W is a positive integer, i.e., W=10 for the IPOT example and W=4 for the NPOT example. This results in reduced table  28  having an integral power of two entries, plus 1. In this case, W=N. This is not a requirement of the present invention, and those skilled in the art will appreciate that W, while positive, may not be an integer, i.e., reduced table  28  may have any desired number of entries. In such a case, W≦N. 
     Optional address converter  50  (FIG. 1) is used in the NPOT example to convert primary address B [M]  into direct address A [N+F] . Those skilled in the art will appreciate that optional address converter  50  may be any of a plurality of well-know converters, e.g., a simple M by N+F look-up table array, without departing from the spirit of the present invention. 
     FIG. 11 shows a flowchart depicting a table-access subprocess  52  of process  22  in accordance with a preferred embodiment of the present invention. The following discussion refers to FIGS. 1,  2 ,  5 ,  6 , and  11 . 
     In subprocess  52 , process  22  utilizes an address control circuit  60  (FIG. 1) to access the addressed data values  24  within even- and odd-indexed tables  30  and  32 . Even-indexed table  30  contains substantially the even-indexed half of data values  24  of reduced table  28  and odd-indexed table  32  contains substantially the odd-indexed half of data values  24  of reduced table  28 . Since each of even- and odd-indexed tables  30  and  32  contains substantially half of reduced table  28 , each of even-and odd-indexed tables  30  and  32  is addressable as a half-integral address A [N−1:1] , which is integral address A [N]  integer-divided by two:                A     [     N   -     1        :        1       ]       =       int        (       A     [   N   ]       2     )       .             (   4   )                                
     Half-integral address A [N−1:1]  is a partial address formed of the N−1 most-significant bits, A 1  through A N−1 , of integral address A [N] . A task  54  (FIG. 11) of subprocess  52  provides half-integral address A [N−1:1]  to address control circuit  60 . 
     Half-integral address A [N−1:1]  cannot differentiate between even-indexed table  30  and odd-indexed table  32 . To correct this, A [0]  is utilized. Even/odd-integral address A [0]  is a partial address formed of the 1 least-significant bit, A 0 , of integral address A [N] . A task  56  (FIG. 11) of subprocess  52  provides even/odd-integral address A [0]  to address control circuit  60 . 
     Those skilled in the art will appreciate that the order in which tasks  54  and  56  are performed is irrelevant to the present invention, and the sequence described herein is due to the limitations of flow charts. 
     A task  58  (FIG. 11) of subprocess  52  addresses even-indexed table  30 . That is, task  58  derives an even-table address A [T1]  from half-integral address A [N−1:1]  and even/odd-integral address A [0]  to through address control circuit  60  (FIG. 1) of data access and interpolation apparatus  20 . 
     Within address control circuit  60 , task  58  uses a summing circuit  62  to derive the sum of half-integral address A [N−1:1]  plus even/odd-integral address A [0] . The resultant sum passes through an optional address mask circuit  64  and an optional address offset circuit  68  to become even-table address A [T1] . 
     Similarly, a task  70  of subprocess  52  passes half-integral address A [N−1:1]  through optional address mask circuit  64  and optional address offset circuit  68  to become an odd-table address A [T2] . 
     Apparatus  20  incorporates a first memory circuit  72  and a second memory circuit  74 , each of which is coupled to address control circuit  60 . In the preferred embodiment of FIG. 1, first and second memory circuits  72  and  74  serve solely to contain even- and odd-indexed tables  30  and  32 , respectively. Therefore, even- and odd-indexed tables  30  and  32  are considered herein to be synonymous with first and second memory circuits  72  and  74 , and even- and odd-table addresses A [T1]  and A [T2]  are addresses of first and second memory circuits  72  and  74 , respectively. 
     Within address control circuit  60 , task  58  (FIG. 11) passes the sum of half-integral address A [N−1:1]  plus even/odd-integral address A [0]  through optional address mask circuit  64  and optional address offset circuit  68  to become even-table address A [T1] . Similarly, a task  70  of subprocess  52  passes half-integral address A [N−1:1]  through optional address mask circuit  64  and optional address offset circuit  68  to become an odd-table address A [T2] . Those skilled in the art will appreciate that optional address mask circuit  64  and optional address offset circuit  68  are not requirements of the present invention. Address mask circuit  64  and address offset circuit  68  may be used in manners well-known to one of ordinary skill in the art to cause reduced table  28 , realized within even- and odd-indexed tables  30  and  32 , to become circular. The inclusion or omission of either optional address mask circuit  64  or optional address offset circuit  68  does not depart from the spirit of the present invention. For purposes of simplicity, this discussion shall assume the omission of both optional address mask circuit  64  and optional address offset circuit  68 , in which case: 
     
       
           A   [T1]   =A   [N−1:1]   +A   [0] ,  (5) 
       
     
     and 
     
       
           A   [T2]   =A   [N−1:1]   (6) 
       
     
     The reason A [T1] =A [N−1:1] +A [0]  and A [T2] =A [N−1:1]  may be seen by following through address control circuit  60  with the IPOT example. In even sample  36 ′, A [N] =100 (FIG.  3 ). Therefore:                  A     [   T1   ]       =         int        (       A     [   N   ]       2     )       +     A     [   0   ]         =         int        (     100   2     )       +   0     =   50         ,   and           (5-1)                 A     [   T2   ]       =       int        (       A     [   N   ]       2     )       =       int        (     100   2     )       =   50.               (6-1)                                
     In FIGS. 5 and 6, it may be seen that task  58  (FIG. 11) addresses even-indexed table  30 ′ at A [T1] =50 where A [N] =100, and task  70  addresses odd-indexed table  32 ′ at A [T2] =50 where A [N] =101. Therefore, A n =100 and A n +1=101. An even-table data value G t1  is the A n  data value and an odd-table data value G t2  is the A n +1 data value. 
     Similarly, in odd sample  38 ′, A [N] =211 (FIG.  3 ). Therefore:                  A     [   T1   ]       =         int        (       A     [   N   ]       2     )       +     A     [   0   ]         =         int        (     211   2     )       +   1     =   106         ,   and           (5-2)                 A     [   T2   ]       =       int        (       A     [   N   ]       2     )       =       int        (     211   2     )       =   105.               (6-2)                                
     Task  58  (FIG. 11) addresses even-indexed table  30 ′ at A [T1] =106 where A [N] =212, and task  70  addresses odd-indexed table  32 ′ at A [T2] =105 where A [N] =211. Therefore, A n =211 and A n +1=212. Odd-table data value G t2  is the A n  data value and even-table data value G t1  is the A n +1 data value. 
     Those skilled in the art will appreciate that the order in which tasks  58  and  70  are performed is irrelevant to the present invention, and the sequence described herein is due to the limitations of flow charts. 
     Following even- and odd-indexed tables  30  and  32  in apparatus  20  is a routing circuit  76  (FIG. 1) coupled to both first and second memory circuits  72  and  74 . In a task  78  (FIG.  11 ), subprocess  52  provides a value of even/odd-integral address A [0]  to routing circuit  76 . In the preferred embodiment of FIG. 1, routing circuit  76  is made up of two cross-coupled multiplexers  80  and  82  configured to output a first-indexed (i.e., A n  indexed) data value G n  and a second-indexed (i.e., A n +1 indexed) data value G n+1 , respectively. 
     In a query task  84  (FIG.  11 ), subprocess  52  determines if even/odd-integral address A [0]  is even or odd. If task  84  determines that even/odd-integral address A [0]  is even, then a task  86  acquires first-indexed data value G n  from even-indexed table  30  and a task  88  acquires second-indexed data value G n+1  from odd-indexed table  32 . Conversely, if task  84  determines that even/odd-integral address A [0]  is odd, then a task  90  acquires first-indexed data value G n  from odd-indexed table  32  and a task  92  acquires second-indexed data value G n+1  from even-indexed table  32 . That is, G n =G t1  and G n+1 =G t2  when A [0] =0, and G n =G t2  and G n+1 =G t1  when A [N] =1. 
     Subprocess  52  (FIGS. 2 and 11) is thereby completed and control is returned to process  22  (FIG.  2 ). 
     FIG. 12 shows a flowchart depicting an output-determining subprocess  94  of process  22  in accordance with a preferred embodiment of the present invention. The following discussion refers to FIGS. 1,  2 ,  5 ,  6 ,  9 ,  10 , and  12 . 
     In subprocess  94  (FIG.  12 ), process  22  then utilizes an interpolation circuit  102  (FIG. 1) of apparatus  20  to produce an output data value G Out . In a task  96 , subprocess  94  provides the value A f  of fractional address A [F]  (FIG. 1) to interpolation circuit  102 . Fractional address A [F]  is made up of bits whose values are negative integral powers of two. That is, fractional address A [F]  has value A f  that is always fractional, i.e.: 
     
       
         0≦A f &lt;1.  (7) 
       
     
     Typically, data values  24  in tables  26 ,  28 ,  30 , and  32  are expressed as floating-point values, rather than binary values. This being the case, a task  98  of subprocess  94  converts value A f  of binary fractional address A [F]  into a floating-point incremental value Δ in a fixed to floating-point converter  100  of apparatus  20 , where: 
     
       
         0≦Δ&lt;1.  (8) 
       
     
     In interpolation circuit  102  of apparatus  20 , a task  104  of subprocess  94  uses a subtracting circuit  106  to subtract first-indexed data value G n  from second-indexed data value G n+1  to produce a data-difference value G Diff . That is: 
       G   Diff   =G   n+1   −G   n .  (9) 
     In a multiplying circuit  108  of interpolation circuit  102 , a task  110  of subprocess  94  multiplies data-difference value G Diff  by incremental value Δ to produce an interpolated data value G ΔDiff . That is: 
     
       
           G   ΔDiff   =Δ·G   Diff .  (10) 
       
     
     In a summing circuit  112  of interpolation circuit  102 , a task  114  of subprocess  94  adds interpolated data value G ΔDiff  to first-indexed data value G n  to produce output data value G Out . That is: 
     
       
           G   Out   =G   n   +G   ΔDiff . (11) 
       
     
     This completes subprocess  94  and process  22 . 
     The following discussion follows even sample  36 ′ of the IPOT example from beginning to end. 
     In emulated table  26 ′ (FIG.  3 ), even sample  36 ′ indicates a desired data value  24  whose emulated-table index O I =6424. This data value is          cos        (       6424   65536        π     )       =     0.952                 957                 956                 032                   …              .                              
     Using equation 1, the values A n  and A f  of the reduced-table integral address A [N]  and fractional address A [F]  may be computed:                R   I     =           R   W     ·     O   I         O   V       =         1024   ·   6424     65536     =     100        24   64                   (1-1)                                
     where integral part A n =100 and fractional part A f ={fraction (24/64)}. This being an IPOT example, a special relationship exists, where V=M, W=N, and M=N+F=10+6=16, and where primary address B [M] =6424 D =0001 1001 0001 1000 B  (sixteen bits), integral address A [N] =100 D =00 0110 0100 B  (ten most-significant bits of primary address B [M] ), and fractional address A [F] =0.375 D =0.0110 00 B  (six least-significant bits of primary address B [M] ). Since 100≦R I &lt;101, what will actually be fetched are:                  A     [   T   ]       =         int        (       A     [   N   ]       2     )       +     A     [   0   ]         =         int        (     100   2     )       +   0     =   50         ,   and           (5-1)                 A     [   T2   ]       =       int        (       A     [   N   ]       2     )       =       int        (     100   2     )       =   50.               (6-1)                                
     That is, the data values G t1  and G t2  in even- and odd-indexed tables  30 ′ and  32 ′ (FIGS. 5 and 6) whose addresses are A [T1] =50 and A [T2] =50, respectively. From even-indexed table  30 ′,          G   t1     =       cos        (       100   1024        π     )       =     0.953                 306                 040                 354                   …              .                                
     From odd-indexed table  32 ′,          G   t1     =       cos        (       101   1024        π     )       =     0.952                 375                 012                 720                   …              .                                
     In this case, A [0] =0, so first-indexed data value G n =G t1  and second-indexed data value G n+1 =G t2 . Using equation 9 to compute data-difference value G Diff :                      G   Diff     =       G     n   +   1       -     G   n                   =       0.952                 375                 012                 720                 …     -     0.953                 306                 040                 354                 …                   =       -   0.000                   931                 027                 634                 …                   (9-1)                                
     Ignoring fixed versus floating-point conversion so that incremental value Δ=A f =0.375, and using equation 10 to compute interpolated data value G ΔDIff :                      G     Δ                 Diff       =     Δ   ·     G   Diff                   =       (       -   0.000                   931                 027                 634                 …                )     ·   0.375                 =       -   0.000                   349                 135                 363                 …                   (10-1)                                
     Then using equation 11 to compute output data value G Out :                      G   Out     =       G   n     +     G     Δ                 Diff                     =       0.953                 306                 040                 354                 …     +     (       -   0.000                   349                 135                 363                 …                )                   =     0.952                 956                 904                 991                 …                   (11-1)                                
     Which varies by only −0.000 001 051 041 . . . from the desired emulated value of 0.952 957 956 032 . . . . 
     Similarly, the following discussion follows odd sample  38 ′ of the IPOT example from beginning to end. 
     In emulated table  26 ′ (FIG.  3 ), odd sample  38 ′ indicates a desired data value  24  whose emulated-table index O I =13 549. This data value is          cos        (       13549   65536        π     )       =     0.796                 388                 074                 554                   …              .                              
     Using equation 1:                R   I     =           R   W     ·     O   I         O   V       =         1024   ·   13549     65536     =     211        45   64                   (1-2)                                
     where integral part A n =211 and fractional part A f ={fraction (45/64)}=0.703 125. Since 211≦R I &lt;212, what will actually be fetched are:                  A     [   T1   ]       =         int        (       A     [   N   ]       2     )       +     A     [   0   ]         =         int        (     211   2     )       +   1     =   106         ,   and           (5-2)                 A     [   T2   ]       =       int        (       A     [   N   ]       2     )       =       int        (     211   2     )       =   105.               (6-2)                                
     That is, the data values G t1  and G t2  in even- and odd-indexed tables  30 ′ and  32 ′ (FIGS. 5 and 6) whose addresses are A [T1] =106 and A [T2] =105, respectively. From even-indexed table  30 ′,          G   t1     =       cos        (       212   1024        π     )       =     0.795                 836                 904                 609                   …              .                                
     From odd-indexed table  32 ′,          G   t2     =       cos        (       211   1024        π     )       =     0.797                 690                 840                 943                   …              .                                
     In this case, A [0] =1, so first-indexed data value G n =G t2  and second-indexed data value G n+1 =G t1 . Using equation 9 to compute data-difference value G Diff :                      G   Diff     =                  G     n   +   1       -     G   n                   =                  0.795                 836                 904                 609                 …     -     0.797                 690                 840                 943                 …                   =                  -   0.001                   853                 936                 334                 …                   (9-2)                                
     Using equation 10 to compute interpolated data value G ΔDiff :                      G     Δ                 Diff       =     Δ   ·     G   Diff                   =         (       -   0.001                   853                 936                 334                 …                )     ·   0.703                   125                 =       -   0.001                   303                 548                 980                 …                   (10-2)                                
     Then using equation 11 to compute output data value G Out :                      G   Out     =       G   n     +     G     Δ                 Diff                     =       0.797                 690                 840                 943                 …     +     (       -   0.001                   303                 548                 980                 …                )                   =     0.796                 387                 291                 963                 …                   (11-2)                                
     Which varies by only −0.000 000 782 591 .. . from the desired emulated value of 0.796 388 074 554 . . . . 
     With the NPOT example, the process for obtaining the results is substantially identical to that of the IPOT example, with the exception that the value of the fraction part A F  of reduced-table index R I  is not an integral power of two. The accuracy of the result therefore depends heavily upon the resolution of the integral-power-of-two equivalent of the fractional address A [F] . In the NPOT examples herein, a resolution of 2 −9 =1/512, where F=9, was used for simplicity. In practice, a resolution of 2 −16 ={fraction (1/65 536)} or 2 −20 =1/1 048 576 would not be uncommon. 
     Those skilled in the art will appreciate that certain timing considerations must be made within apparatus  20 . For this reason, a first delay circuit  116  has been added to apparatus  20  to effect a delay of incremental value Δ so that incremental value Δ and data-difference value G Diff  arrive at multiplying circuit  108  substantially simultaneously. Similarly, a second delay circuit  118  has been added to apparatus  20  to effect a delay of first-indexed data value G n  so that first-indexed data value G n  and interpolated data value G ΔDiff  arrive at summing circuit  112  substantially simultaneously. The use of these and/or other timing circuits does not depart from the spirit of the present invention. 
     In summary, the present invention teaches a transparent data access and interpolation apparatus  20  and method  22  therefor. Apparatus  20  and method  22  reduce power consumption during access. Apparatus  20  significantly reduces on-chip memory area. Method  22  is transparent to the accessing computer (not shown) and obtains two values A n  and A n +1 for interpolation in a single access operation. Being transparent, method  22  is usable with pre-existing software. 
     Although the preferred embodiments of the invention have been illustrated and described in detail, it will be readily apparent to those skilled in the art that various modifications may be made therein without departing from the spirit of the invention or from the scope of the appended claims.

Technology Classification (CPC): 6