Patent Abstract:
This invention efficiently converts normal pixel data into bit plane data. A sequence of pack, bitwise shuffle, masking, rotate and merging operations transform tile from pixel form to bit plane form. This enables downstream algorithms to read only the data for the bit plane of interest. This greatly reduces the memory bandwidth bottleneck and opens many new optimization pathways.

Full Description:
CLAIM OF PRIORITY  
       [0001]     This application claims priority under 35 U.S.C. 119(e)(1) to U.S. Provisional Application No. 60/484,395 filed Jul. 2, 2003. 
     
    
     TECHNICAL FIELD OF THE INVENTION  
       [0002]     The technical field of this invention is computer graphics.  
       BACKGROUND OF THE INVENTION  
       [0003]     A bit plane is a horizontal slice through the data, collecting the values of a given bit position from all of the data values in the set. For example, consider an array filled with 1000 elements of 16-bit data. This array can be divided this into 16 1000-bit arrays, the first of which would have all of bits for bit-position 0, the next would have all of the bits for bit-position 1, etc. Each of these 16 1000-bit arrays is a bit plane.  
         [0004]     The invention is embodied in a code sequence that converts a sequence of N bit numbers and produces a set of N bitmaps. The N bits of each number are generally stored together in a single storage unit such as a single memory location. Each bitmap contains one bit plane from the original data set.  
         [0005]     This invention effectively converts N-bit data (where N is a power of 2) into a set of bit planes. This operation is useful for multiple problems. Certain modulation schemes assert data in bit-plane order as a simple means of analog-to-digital conversion. A Digital Light Processor based on the Texas Instruments&#39; Digital Mirror Device uses this type of operation. In this context, the operation is sometimes referred to as corner turning. Certain image-coding schemes encode images in bit planes. These schemes would benefit from the planarized encoding. For 1-bit image data, this operation is equivalent to image transposition on N-bit wide tiles. This invention requires little modification to support this secondary use.  
         [0006]     Bit-plane oriented schemes usually make poor use of memory bandwidth. To read a given bit position across an entire data set, prior art schemes read the entire data set, extract the bit of interest and discard the other bits. This process must be repeated for each bit plane. These prior art schemes read about N times as much data as actually used for N-bit data elements.  
         [0007]     Traditional solutions to planarization can only effectively process one bit-plane at a time. The straight forward implementation reads the data N times. Even if all N bit planes are extracted the first time the data is read, the extraction process usually operates only one bit at a time.  
         [0008]     Thus there is a need in the art for an efficient conversion process from pixel format data to bit plane format data. Such an efficient conversion process would make other processes feasible that are now limited by the computation cost of this planarization.  
       SUMMARY OF THE INVENTION  
       [0009]     This invention efficiently converts normal pixel data into bit plane data. This enables downstream algorithms to read only the data for the bit plane of interest. This greatly reduces the memory bandwidth bottleneck and opens many new optimization pathways.  
         [0010]     This invention uses sequence of pack, bitwise shuffle, masking, rotate and merging operations to transform a 16-bit by 16-bit tile from pixel form to bit plane form at a rate of 1 tile in 12 instruction cycles. This is equivalent to planarizing sixteen 16-bit bins. Due to minor changes in memory addressing, full planarization requires approximately 14 cycles for an equivalent amount of data.  
         [0011]     This application illustrates the invention with an example of planarizing 16-bit data. Although this example operates on 16-bit data, the algorithm can be modified to work with smaller or larger data sizes. The most common pixel data sizes are 8-bit and 16-bit. The following includes a description of the algorithm together with example code for an inner loop.  
         [0012]     A bitwise shuffle instruction SHFL allows effective sort of the bit-planes in parallel. This achieves very high efficiency. The prior art approach employs the fundamentally information-losing activity of extracting one bit of interest and discarding the rest. Thus the prior art produces much greater memory traffic. This invention moves all the bits together. In each step all bits move closer to their final destination. As a result, this invention can corner turn or planarize data more than ten times faster than the estimated operational rate of the prior art approach.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]     These and other aspects of this invention are illustrated in the drawings, in which:  
         [0014]      FIG. 1  illustrates the starting bit arrangement of a set of example pixels in four data words in an example of use of this invention;  
         [0015]      FIG. 2  illustrates the data operation of a known instruction that packs the high bytes of the two half-words of two source operands into a destination operand;  
         [0016]      FIG. 3  illustrates the data operation of a known instruction that packs the low bytes of the two half-words of two source operands into a destination operand;  
         [0017]      FIG. 4  illustrates the results of the pack data instructions of the prior art illustrated in  FIGS. 2 and 3  as used in this invention on the data illustrated in  FIG. 1 ;  
         [0018]      FIG. 5  illustrates the operation of a shuffle instruction of the prior art used in this invention;  
         [0019]      FIG. 6  illustrates the pixel arrangement of four data words of the example of this invention following a first shuffle operation;  
         [0020]      FIG. 7  illustrates the pixel arrangement of four data words of the example of this invention following a second shuffle operation;  
         [0021]      FIG. 8  illustrates the pixel arrangement of eight data words of the example of this invention following a masking arrangement;  
         [0022]      FIG. 9  illustrates the pixel arrangement of four data words of the example of this invention following a shift operation;  
         [0023]      FIG. 10  illustrates the pixel arrangement of four data words of the example of this invention at the completion of this invention;  
         [0024]      FIG. 11  illustrates the data operation of a known instruction that packs the high half-words of two source operands into a destination operand;  
         [0025]      FIG. 12  illustrates the data operation of a known instruction that packs the low half-words of two source operands into a destination operand;  
         [0026]      FIG. 13  illustrates the data operation of a known instruction that swaps bytes of respective half-words of one source operand into a destination operand; and  
         [0027]      FIG. 14  is flow chart of the process of converting pixel data into bit plane data in accordance with this invention.  
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0028]     This invention uses sequence of pack, bitwise-shuffle, masking, rotate and merging operations available on a Texas Instruments TMS320C6400 digital signal processor to transform a 16-bit by 16-bit tile from pixel form to bit plane form at a rate of 1 tile in 12 instruction cycles. This is equivalent to planarizing sixteen 16-bit bins. Due to minor changes in memory addressing, full planarization requires approximately 14 cycles for an equivalent amount of data.  
         [0029]     This application will illustrate an example of planarizing 16-bit data. Although this example operates on 16-bit data, the algorithm can be modified to work with smaller or larger data sizes. The most common pixel data sizes are 8-bit and 16-bit. The following includes a description of the algorithm together with unscheduled code for an inner loop. This example code is correct except it omits the initial read of data into the registers and the final write out of the transformed data from the registers to memory. The example code uses mnemonics for the registers. These must be changed to actual, physical registers for scheduled code. One skilled in the art of digital signal processor programming would understand how to produce actual, scheduled code for a particular digital signal processor from this description.  
         [0030]     This invention converts packed pixels in normal format into packed data with the bit planes exposed. This invention will be described with an example beginning with 8 pixels p 7  to p 0 . These eight pixels each have 16 bits A through P.  FIG. 1  illustrates the initial configuration of pixels p 7  to p 0  in four 32-bit data words. The 16 bits of pixel p 7  are packed into the 16 most significant bits of data word  110  (p 7 p 6 ). The 16 bits of pixel p 6  are packed into the 16 least significant bits of data word  110  (p 7 p 6 ). Pixels p 5  and p 4  are packed into respective upper and lower halves of data word  112  (p 5 p 4 ). Pixels p 3  and p 2  are packed into respective upper and lower halves of data word  114  (p 3 p 2 ). Pixels p 1  and p 0  are packed into respective upper and lower halves of data word  116  (p 1 p 0 ).  
         [0031]      FIGS. 2 and 3  illustrate two known data manipulation instructions used in this invention. These instructions are available on the Texas Instruments TMS320C6400 family of digital signal processors.  FIG. 2  illustrates an instruction called PACKH 4  or pack high in four parts. As illustrated in  FIG. 2 , this instruction takes the upper byte (8 bits) from each 16-bit word of the two source operands source 1  and source 2  and stores them in respective bites of the destination operand. Specifically, the high byte  203  of the upper half-word of source 1  is moved to the upper byte of the upper half-word of the destination. The high byte  201  of the lower half-word of source 1  is moved to the lower byte of the upper half-word of the destination. The high byte  213  of the upper half-word of source 2  is moved to the upper byte of the lower half-word of the destination. The high byte  211  of the lower half-word of source 2  is moved to the lower byte of the lower half-word of the destination.  
         [0032]      FIG. 3  illustrates an instruction called PACKL 4  or pack low in four parts. The low byte  222  of the upper half-word of source 1  is moved to the upper byte of the upper half-word of the destination. The low byte  220  of the lower half-word of source 1  is moved to the lower byte of the upper half-word of the destination. The low byte  232  of the upper half-word of source 2  is moved to the upper byte of the lower half-word of the destination. The low byte  230  of the lower half-word of source 2  is moved to the lower byte of the lower half-word of the destination.  
         [0033]     The planarization applies these two instructions to the four starting registers as follows:  
                                                       PACKH4   p7p6, p5p4, p7654H           PACKL4   p7p6, p5p4, p7654L           PACKH4   p3p2, p1p0, p3210H           PACKL4   p3p2, p1p0, p32101                      
 
 Thus each pair of registers is transformed into another pair of registers. The data of each pair of initial registers in included in the corresponding destination pair of registers.  FIG. 4  illustrates the results of applying these four instructions to the four registers of  FIG. 1 . Data word  120  includes the first 8 bits (A to H) of pixels  4  to  7 . Data word  122  includes the last 8 bits (I to P) of pixels  4  to  7 . Data word  124  includes the first 8 bits (A to H) of pixels  0  to  3 . Data word  126  includes the last 8 bits (I to P) of pixels  0  to  3 . 
 
         [0035]     The algorithm next uses a shuffle instruction.  FIG. 5  illustrates the operation of this shuffle instruction. This resembles the shuffling of a deck of cards as the 16 most significant bits of a single operand register source 2  are interleaved with the 16 least significant bits of this register into the destination register. All bits of the original source 2  register appear in the destination register with a different bit order. Each of the four registers is shuffled using this instruction as follows:  
                                                       SHFL   p7654H, p7654H1           SHFL   p7654L, p7654L1           SHFL   p3210H, p3210H1           SHFL   p3210L, p3210L1                      
 
         [0036]      FIG. 6  illustrates the results of shuffling the four data word  120 ,  122 ,  124  and  126  resulting in respective data words  130 ,  132 ,  134  and  136 . These four intermediate registers are shuffled again using the same instruction as follows:  
                                                       SHFL   p7654H1, p7654H2           SHFL   p7654L1, p7654L2           SHFL   p3210H1, p3210H2           SHFL   p3210L1, p3210L2                        
         [0037]      FIG. 7  illustrates the results of this second shuffle operation of data words  130 ,  132 ,  143  and  136  resulting in respective data words  140 ,  142 ,  144  and  146 . As shown in  FIG. 7  the data for the individual planes (A, B, C, D, E, F, G, H, I, J, K, L, M, N, O and P) are mostly together but in upper pixels p 7  to p 4  and lower pixels p 3  to p 0 . Each of these four registers is then masked twice to produce eight intermediate register results. The first masking is accomplished with a logical AND instruction between the intermediate register and a constant mF0F0. This constant “11110000111100001111” is doubled to fill the 32 bits of the arithmetic logic unit. The second masking is accomplished with a logical ANDN instruction which uses the logical inverse of the constant mF0F0. These instructions are as follows:  
                                                       AND   p7654H2, mF0F0, p7654_ACEG           ANDN   p7654H2, mF0F0, p7654_BDFH —             AND   p7654L2, mF0F0, p7654_IKMO           ANDN   p7654L2, mF0F0, p7654_JLNP —             AND   p3210H2, mF0F0, p3210_ACEG —             ANDN   p3210H2, mF0F0, p3210_BDFH           AND   p3210L2, mF0F0, p3210_IKNO —             ANDN   p3210L2, mF0F0, p3210_JLNP                        
         [0038]      FIG. 8  illustrates the results of these masking instructions in data words  150 ,  151 ,  152 ,  153 ,  154 ,  155 ,  156  and  157 . Note that: data word  140  is masked twice producing data words  150  and  151 ; data word  142  is masked twice producing data words  152  and  153  ; data word  144  is masked twice producing data words  154  and  155 ; and data word  146  is masked twice producing data words  156  and  157 . Each four bit plane bits are now isolated within an 8-bit quarter of the data word. Half of these data words are shifted to align with the “0” bits of a corresponding data word. Two data words are right shifted four bits (SHRU) with the “U” indicating unsigned data so that the vacated bits are zero filled and two data words are left shifted four bits (SHL) with the vacated bits zero filled as follows:  
                                                       SHRU   p3210_ACEG_, 4, p3210_ACEG           SHL   p7654_SDFH_, 4, p7654_BDFH           SHRU   p3210_IKLO_, 4, p3210_IKMO           SHL   p7654_JLNP_, 4, p7654_JLNP                        
         [0039]     The four results of the shift operations are illustrated in  FIG. 9  as data words  160 ,  162 ,  164  and  166 . Data word  154  is right shifted 4 bits to become data word  160 . Data word  151  is left shifted 4 bits to become data word  162 . Data word  156  is right shifted 4 bits to become data word  164 . Data word  153  is right shifted 4 bits to become data word  166 . The pixel data for each bit plane are now in position for combining. Four data words  150 ,  152 ,  154  and  156  shown in  FIG. 8  are combined with corresponding data words  160 ,  162 ,  164  and  166  shown in  FIG. 9  as follows:  
                                                       ADD   p7654_ACEG, p3210_ACEG, p_ACEG           ADD   p7654_BDFH, p3210_BDFH, p_BDFH           ADD   p7654_IKMO, p3210_IKMO, p_IKMO           ADD   p7654_JLNP, p3210_JLNP, p_JLNP                      
 
  FIG. 10  illustrates the results of these ADD instructions as data words  170 ,  172 ,  174  and  176 . Because the masking places zeros of one operand opposite the data of the other operand, the result is combination of the data. A bit wise logical OR operation would also form this same combination. 
 
         [0041]     As shown in  FIG. 10  the result of these manipulations places the bit plane data for all pixels in contiguous locations. The plane bits are not in consecutive order, however, each bit plane is easily extracted. Data word  170  includes bit planes A, C, E and G. Data word  172  includes bit planes B, D, F and H. Data word  174  includes bit planes I, K, M and O. Data word  176  includes bit planes J, L, N and P.  
         [0042]     The listing below incorporates the algorithm just described. This listing shows that the Texas Instruments TMS320C6400 digital signal processor can operate on 16 16-bit pixels packed into 8 32-bit data words simultaneously. This listing incorporates additional instructions of the TMS320C6400 digital signal processor that will be described below in the comments. The data registers are given “A” and “B” prefixes denoting the A and B register files with the corresponding execution units of the TMS320C6400. Comments in this listing explain the operation performed.  
                                                                                                                                                                                                       /* Loading 8 data words each with 16 packed pixels via four        * double word load instructions */            &lt;1&gt; LDDW * A_i_ptr++[4],   B_p7p6:B_p5p4       &lt;1&gt; LDDW *−A_i_ptr[3],   B_p3p2:B_p1p0       &lt;2&gt; LDDW * B_i_ptr++[4],   A_p7p6:A_p5p4       &lt;2&gt; LDDW *−B_i_ptr[3],   A_p3p2:A_p1p0       /* First data swap by bytes */               PACKH4   B_p7p6, B_p5p4, B_p7654H          PACKL4   B_p7p6, B_p5p4, B_p7654L          PACKH4   B_p3p2, B_p1p0, B_p3210H          PACKL4   B_p3p2, B_p1p0, B_p3210L          PACKH4   A_p7p6, A_p5p4, A_p7654H          PACKL4   A_p7p6, A_p5p4, A_p7654L          PACKH4   A_p3p2, A_p1p0, A_p3210H          PACKL4   A_p3p2, A_p1p0, A_p3210L            /* First bit shuffle of each data word */               SHFL   B_p7654H, B_p7654H1          SHFL   B_p7654L, B_p7654L1          SHFL   B_p3210H, B_p3210H1          SHFL   B_p3210L, B_p3210L1          SHFL   A_p7654H, A_p7654H1          SHFL   A_p7654L, A_p7654L1          SHFL   A_p3210H, A_p3210H1          SHFL   A_p3210L, A_p3210L1            /* Second bit shuffle of each data word */               SHFL   B_p7654H1, B_p7654H2          SHFL   B_p7654L1, B_p7654L2          SHFL   B_p3210H1, B_p3210H2          SHFL   B_p3210L1, B_p3210L2          SHFL   A_p7654H1, A_p7654H2          SHFL   A_p7654L1, A_p7654L2          SHFL   A_p3210H1, A_p3210H2          SHFL   A_p3210L1, A_p3210L2            /* Masking nibbles to prepare for merge */               AND   B_p7654H2, B_mF0F0, B_p7654_ACEG          ANDN   B_p7654H2, B_mF0F0, B_p7654_BDFH —            AND   B_p7654L2, B_mF0F0, B_p7654_IKMO          ANDN   B_p7654L2, B_mF0F0, B_p7654_JLNP —            AND   B_p3210H2, B_mF0F0, B_p3210_ACEG —            ANDN   B_p3210H2, B_mF0F0, B_p3210_BDFH          AND   B_p3210L2, B_mF0F0, B_p3210_IKMO —            ANDN   B_p3210L2, B_mF0F0, B_p3210_JLNP          AND   A_p7654H2, A_mF0F0, A_p7654_ACEG          ANDN   A_p7654H2, A_mF0F0, A_p7654_BDFH —            AND   A_p7654L2, A_mF0F0, A_p7654_IKMO          ANDN   A_p7654L2, A_mF0F0, A_p7654_JLNP —            AND   A_p3210H2, A_mF0F0, A_p3210_ACEG —            ANDN   A_p3210H2, A_mF0F0, A_p3210_BDFH          AND   A_p3210L2, A_mF0F0, A_p3210_IKMO —            ANDN   A_p3210L2, A_mF0F0, A_p3210_JLNP            /* Rotate half the data words to prepare for merge */               ROTL   B_p3210_ACEG_, 28, B_p3210_ACEG          ROTL   B_p7654_BDFH_, 4, B_p7654_BDFH          ROTL   B_p3210_IKMO_, 28, B_p3210_IKMO          ROTL   B_p7654_JLNP_, 4, B_p7654_JLNP          ROTL   A_p3210_ACEG_, 28, A_p3210_ACEG          ROTL   A_p7654_BDFH_, 4, A_p7654_BDFH          ROTL   A_p3210_IKMO_, 28, A_p3210_IKMO          ROTL   A_p7654_JLNP_, 4, A_p7654_JLNP            /* Merge of nibble data */               ADD   B_p7654_ACEG, B_p3210_ACEG, B_p_ACEG          ADD   B_p7654_BDFH, B_p3210_ACEG, B_p_BDFH          ADD   B_p7654_IKMO, B_p3210_ACEG, B_p_IKMO          ADD   B_p7654_JLNP, B_p3210_ACEG, B_p_JLNP          ADD   A_p7654_ACEG, A_p3210_ACEG, A_p_ACEG          ADD   A_p7654_BDFH, A_p3210_ACEG, A_p_BDFH          ADD   A_p7654_IKMO, A_p3210_ACEG, A_p_IKMO          ADD   A_p7654_JLNP, A_p3210_ACEG, A_p_JLNP            /* Word (16 bit) shuffle to order bit plane data */               PACKH2   B_p_ACEG, A_p_ACEG, B_ACAC          PACK2   B_p_ACEG, A_p_ACED, B_EGEG          PACKH2   B_p_BDFH, A_p_BDFH, B_BDBD          PACK2   B_p_BDFH, A_p_BDFH, B_FHFH          PACKH2   A_p_IKNO, B_p_IKMO, A_IKIK —            PACK2   A_p_IKNO, B_p_IKMO, A_MOMO —            PACKH2   A_p_JLNP, B_p_JLNP, A_JLJL —            PACK2   A_p_JLNP, B_p_JLNP, A_NPNP —              /* Byte (8 bit) shuffle to order bit plane data */               PACKH4   B_ACAC, B_BDBD, B_AABB          PACKL4   B_ACAC, B_BDBD, B_CCDD          PACKH4   B_EGEG, B_FHFH, B_EEFF          PACKL4   B_EGEG, B_FHFH, B_GGHH          PACKH4   A_IKIK, A_JLJL_, A_IIJJ —            PACKL4   A_IKIK, A_JLJL_, A_KKLL —            PACKH4   A_MOMO_, A_NPNP_, A_MNNN —            PACKL4   A_MOMO_, A_NPNP_, A_OOPP —              /* Byte (8 bit) exchange to order bit planes */               SWAP4   A_IIJJ, A_IIJJ          SWAP4   A_KKLL_, A_KKLL          SWAP4   A_MMNN_, B_MMNN          SWAP4   A_OOPP_, B_OOPP            /* Storing 8 data words with 16 packed bit planes via four        * double word store instructions */            &lt;3&gt; STDW   B_AABB:B_CCDD, *+B_o_ptr[0]       &lt;3&gt; STDW   B_EEFF:B_GGHH, *+B_o_ptr[1]       &lt;3&gt; STDW   A_IIJJ:A_KKLL, *+B_o_ptr[2]       &lt;3&gt; STDW   B_MMNN:B_OOPP *+B_o_ptr[3]                  
 
         [0043]     This code uses rotate instructions RDTL rather than shift right unsigned (SHRU) and shift left (SHL) of the previous example. The RDTL by 28 bits corresponds to the shift right unsigned SHRU by 4 bits. The RDTL by 4 bits corresponds to the shift left SHL by 4 bits. Thus any instruction shifts the input data left and/or right by 4 bits without sign extension will work.  
         [0044]     The PACKH 2  and PACK 2  instructions are similar to the PACKH 4  and PACK 4  instructions except that they operate on data words (16 bits) rather than bytes.  FIG. 11  illustrates the operation of the pack high words PACKH 2  instruction. The high words (16 bits) of each source operand are packed into the destination. High word  241  of the first source operand source 1  becomes the high word of the destination operand. High word  251  of the second source operand source 2  becomes the low word of the destination operand.  FIG. 12  illustrates the operation of the pack low words PACK 2  instruction. The low words (16 bits) of each source operand are packed into the destination. Low word  260  of the first source operand source 1  becomes the high word of the destination operand. Low word  270  of the second source operand source 2  becomes the low word of the destination operand.  
         [0045]      FIG. 13  illustrates the operation of the swap bytes in each half word instruction SWAP 4 . As illustrated in  FIG. 13 , this instruction swaps the upper byte (8 bits) with the lower byte (8 bits) of each 16-bit word of the second source operand source 2 . Specifically, the high byte  243  of the upper half-word of source 2  is moved to the lower byte of the upper half-word of the destination. The low byte  242  of the upper half-word of source 2  is moved to the upper byte of the upper half-word of the destination. The high byte  241  of the lower half-word of source 2  is moved to the upper byte of the lower half-word of the destination. The low byte  241  of the lower half-word of source 2  is moved to the lower byte of the lower half-word of the destination.  
         [0046]      FIG. 14  illustrates the process of converting pixel data into bit plane data. The process begins at start block  301 . The process loads the next set of packed pixels (processing block  302 ). The number of packed pixel data words loaded depends on the register capacity of the data processing apparatus and the relationship between the pixel bit length and the data word length. In the previous examples, there are two 16-bit pixels packed into each 32bit data word and the apparatus loads 4 or 8 of these packed data words. Next each data word is shuffled via a pack high and a pack low instruction (processing block  303 ). The data width of the shuffled part is half the data width of the pixel data. The process subjects resulting data words to a first bit shuffle (processing block  304 ) and a second bit shuffle (processing block  305 ). The bit shuffle was described above in conjunction with  FIG. 5 . The process next masks, shits and merges the shuffled data words (processing block  307 ). The mask size corresponds to one quarter of the original pixel data length. In the examples of this application the mask length is four bits. The masking of this example is used because the target data processor (Texas Instruments TMS320C6400) does not have a set of pack instructions having 4-bit length. If such an instruction was available, it could be used here rather than the mask, shift and merge operations described above. The process next sorts the bit plane data words (processing block  307 ). Recall the original example produced bit plane data that was not sorted in the bit order ( FIG. 10 ). The second example shows how this bit plane data can be sorted into order from most significant to least significant bit planes. Decision block  309  determines if there is additional image data to be converted. If not (No at decision block  309 ), the process is complete and exits via end block  310 . If there is additional image data (Yes at decision block  309 ), the control returns to processing block  302  to load the next pixel data.  
         [0047]     The bitwise shuffle instruction SHFL allows effective sort of the bit-planes in parallel. This achieves very high efficiency. The prior art approach employs the fundamentally information-losing activity of extracting one bit of interest and discarding the rest. Thus the prior art produces much greater memory traffic. This invention moves all the bits together. In each step all bits move closer to their final destination. As a result, this invention can corner turn or planarize 256 bits in 12 cycles, for a rate of 21.33 bits/cycle. This is more than ten times faster than the estimated operational rate of the prior art approach.  
         [0048]     Another prior art approach employs custom hardware to transpose the data and produce the desired bit plane data. This custom hardware requires silicon area not devoted to general purpose data processing operations. This results in additional cost in manufacture and design of the digital signal processor incorporating this custom hardware. Use of this custom hardware would also require additional programmer training and effort to learn the data processing performed by the custom hardware. In contrast, this invention employs known instructions executed by hardware which could be used in other general purpose data processing operations.  
         [0049]     This technique is useful in many fields. The image data compression standards JPEG 2000 and MPEG4 both employ wavelet schemes that rely on zero-tree decomposition of the wavelets. These zero-tree schemes benefit from planarization of the data prior to processing. Pulse-modulated display devices, such as the Texas Instruments Digital Mirror Device (DMD) and various liquid crystal displays (LCD) often employ bit-plane-oriented display. In these processes one bit plane is sent to the display at a time and is held in the display for a time proportional to the bit&#39;s numeric value. These devices rely on corner-turning as a fundamental operation.

Technology Classification (CPC): 6