Apparatus for routing interpolator input data by performing a selective two's complement based on sets of lower and higher order bits of input data

Abstract

An apparatus for routing interpolator input data for a color space conversion from a RGB color space to a CMYK color space includes a selective two's complementer coupled to a hardware interpolator. The inputs to the selective two's complementer include three sets of four lower order bits, RL, GL, and BL of a twenty four bit RGB color space value and three least significant bits of three sets of four higher order bits, RH, GH, and BH. The inputs to the hardware interpolator include three outputs from the selective two's complementer and eight inputs for receiving interpolator input data from eight memory banks. The interpolation process can be regarded as determining a location within a cube of a cubic lattice formed from vertices represented by the interpolator input data values. The interpolator input data values are classified into one of eight classes based upon the evenness and oddness of the components of the vector formed from the three sets of higher order bits specifying the location of the corresponding vertex within the cubic lattice. Each of the eight memory banks stores one of the eight classes of interpolator input data values. The eight interpolator input data values corresponding to any cube within the cubic lattice are stored in the eight memory banks. To perform the interpolation, the eight interpolator input data values must be routed to computational blocks within the interpolator depending upon the evenness and oddness classification of each of the three sets of higher order bits corresponding to the interpolator input data value. By performing a two's complement on those sets of lower order bits corresponding to those sets of higher order bits classified as odd, the routing of the interpolator input data values is accomplished mathematically in the corresponding computational blocks.

What is claimed is: 
     
       1. An apparatus for routing interpolator input data used for a transformation of input data values each having n components to output data values each having i components, said n components represented by corresponding n sets of bits each partitioned to form n sets of higher order bits and n sets of lower order bits, said apparatus comprising: a means for performing a selective two's complement arranged for receiving said n sets of lower order bits and a least significant bit from each of said n sets of higher order bits; and   at least one means for interpolating arranged for receiving said interpolator input data, each of said means for interpolating coupled to said means for performing a selective two's complement.   
     
     
       2. The apparatus as recited in claim 1, wherein: said means for performing a selective two's complement includes a selective two's complementer for selectively performing a two's complement operation on each of said n sets of lower order bits responsive to a predetermined state of corresponding said least significant bit to generate n sets of selectively two's complemented lower order bits, said selective two's complementer includes n outputs corresponding to said n sets of lower order bits.   
     
     
       3. The apparatus as recited in claim 2, wherein: said means for interpolating includes a hardware interpolator.   
     
     
       4. The apparatus as recited in claim 3, wherein: said hardware interpolator includes eight interpolator inputs for receiving said interpolator input data and n inputs for receiving said n outputs from said selective two's complementer.   
     
     
       5. The apparatus as recited in claim 4, wherein: n equals 3, i equals 4, and each of said n sets of higher order and lower order bits includes 4 bits.   
     
     
       6. The apparatus as recited in claim 5, wherein: said selective two's complementer includes three two's complementers, each of said two's complementers includes four exclusive OR gates and a binary incrementer, each of said exclusive OR gates includes a first input, a second input, and an output coupled to said binary incrementer, each of said first inputs coupled to one of said lower order bits, each of said least significant bits coupled to said second inputs of said exclusive OR gates having corresponding lower order bits coupled to said first input, and said least significant bits coupled to said binary incrementer.   
     
     
       7. The apparatus as recited in claim 6, wherein: said hardware interpolator performs interpolation using parallel cascade processing.   
     
     
       8. A color space converter for converting color space input data from an input color space having n dimensions represented by n components to color space output data in an output color space having i dimensions represented by i components, said n components represented by n sets of bits each partitioned into a set of higher order bits and a set of lower order bits, m bits represent said n sets of higher order bits according to m 1  +m 2  + . . . m n  =m, said color space converter comprising: a means for generating addresses arranged for receiving said m bits, said means for generating addresses for generating at least {[2 m   1  +1]×[2 m   2  +1]× . . . ×[2 m   n  +1]} addresses;   a memory arranged to receive said addresses from said means for generating addresses, said memory including at least {[2 m   1  +1]×[2 m   2  +1]× . . . ×[2 m   n  +1]} storage locations and a means for outputting interpolator input data stored in said storage locations;   at least one means for performing interpolation, each of said means for performing interpolation connected to said means for outputting interpolator input data; and   a means for performing a selective two's complement connected to each of said means for performing interpolation, said means for performing a selective two's complement arranged for receiving said n sets of lower order bits and a least significant bit from each of said n sets of higher order bits, said means for performing a selective two's complement for selectively performing a two's complement of said n sets of lower order bits responsive to the state of corresponding said least significant bit and providing said selective two's complement of said n sets of lower order bits to each of said means for performing interpolation.   
     
     
       9. The color space converter as recited in claim 8, wherein: said input color space includes a color space selected from the group consisting of a RGB, a Lab, a XYZ, a HSV, a Luv, a HLS, and a CMY color space, said output color space includes a color space selected from the group consisting of a RGB, a Lab, a XYZ, a HSV, a Luv, a HLS color space, and a CMYK color space.   
     
     
       10. The color space converter as recited in claim 9, wherein: m equals 12.   
     
     
       11. The color space converter as recited in claim 10, wherein: m 1 , m 2 , and m 3  each equal 4.   
     
     
       12. The color space converter as recited in claim 11, wherein: said input color space includes a RGB color space and said output color space includes a CMYK color space;   said means for generating addresses generates at least ({[2 m   1  +1]×[2 m   2  +1]×[2 m   3  +1]}×4) of said addresses, said means for generating addresses includes a capability for receiving an additional 2 bits for successively selecting one component of said CMYK color space into which to convert said color space input data; and   said memory includes at least ({[2 m   1  +1]×[2 m   2  +1]×[2 m   3  +1]}×4) of said storage locations divided among eight memory banks each having a memory address input, assignment of said storage locations to said eight memory banks occurs according to the evenness and oddness categorization of said interpolator input data stored in said storage locations, said means for outputting interpolator input data includes a memory data output for each of said memory banks.   
     
     
       13. The color space converter as recited in claim 12, wherein: said means for generating addresses includes an address generator having eight address outputs each connected to one of said memory address inputs, said address generator generates eight of said addresses substantially simultaneously in response to receiving said m bits and said 2 bits;   said means for performing interpolation includes a hardware interpolator, said hardware interpolator includes eight interpolator inputs connected to each of said memory data outputs; and   said means for performing a selective two's complement includes a selective two's complementer.   
     
     
       14. In an apparatus for routing interpolator input data used for a transformation of input data values having n components from a first space having a corresponding n dimensions to output data values having i components in a second space having a corresponding i dimensions, said n components represented by corresponding n sets of bits each partitioned to form n sets of higher order bits each having a least significant bit and n sets of lower order bits, said apparatus includes a means for performing a selective two's complement arranged for receiving said n sets of lower order bits and n said least significant bits and a means for interpolating coupled to said means for performing a selective two's complement, a method for routing said interpolator input data, comprising the steps of: loading said n sets of lower bits and n said least significant bits into said means for performing a selective two's complement;   selectively performing a two's complement operation upon said n sets of lower order bits responsive to the states of n said least significant bits to generate n two's complementer output values;   loading said interpolator input data into said means for interpolating;   loading n said two's complementer output data values into said means for interpolating; and   interpolating using said interpolator input data and said n output values.   
     
     
       15. The method as recited in claim 14, wherein: said step of loading said interpolator input data and said step of loading n said two's complementer output data values occurs substantially simultaneously.   
     
     
       16. The method as recited in claim 15, wherein: said first space includes an input color space and said second space includes an output color space; and   said input color space includes 3 dimensions and said output color space includes 4 dimensions.   
     
     
       17. The method as recited in claim 16, wherein: said means for performing a selective two's complement includes a selective two's complementer and said means for interpolating includes a hardware interpolator.   
     
     
       18. The method as recited in claim 17, wherein: said input color space includes a RGB color space and said output color space includes a CMYK color space.