Apparatus and method for compact Haar transform

Abstract

An apparatus and method are provided for performing both forward and inverse Haar transforms of a sequence of n-bit data samples. The forward Haar transform apparatus has sum-and-truncate logic and a plurality of coefficient generators. The sum-and-truncate logic generates a plurality of n-bit intermediate terms. The plurality of coefficient generators is coupled to the sum-and-truncate logic. The plurality of coefficient generators generate a plurality of spectral coefficients, where at most n+1 bits are required to represent each of the plurality of spectral coefficients. The inverse Haar transform apparatus has index signal and inverse transform logic. The index signal indicates a specific n-bit sample, the specific n-bit sample being one of a sequence of n-bit samples corresponding to the Haar transform. The inverse transform logic is coupled to the index signal. The inverse transform logic computes the specific n-bit sample, where the specific n-bit sample is derived from selected spectral coefficients, and where at most n+1 bits are required to represent each of the selected spectral coefficients.

What is claimed is:  
     
         1 . A compact Haar transform apparatus, for executing a spectral transformation corresponding to a sequence of n-bit samples, the compact Haar transform apparatus comprising: 
 sum-and-truncate logic, configured to generate a plurality of intermediate terms, wherein at most n bits are required to represent each of said plurality of intermediate terms;    a plurality of coefficient generators, coupled to said sum-and-truncate logic, configured to generate a plurality of spectral coefficients, wherein at most n+1 bits are required to represent each of said plurality of spectral coefficients.    
     
     
         2 . The compact Haar transform apparatus as recited in  claim 1 , wherein pairs of the n-bit samples are summed to produce a first rank of said plurality of intermediate terms.  
     
     
         3 . The compact Haar transform apparatus as recited in  claim 2 , wherein pairs of said first rank of said plurality of intermediate terms are summed to produce a second rank of said plurality of intermediate terms.  
     
     
         4 . The compact Haar transform apparatus as recited in  claim 3 , wherein a first rank of said plurality of the spectral coefficients is derived by taking differences between pairs of the n-bit samples.  
     
     
         5 . The compact Haar transform apparatus as recited in  claim 4 , wherein a second rank of said plurality of the spectral coefficients is derived by taking differences between pairs of said first rank of said plurality of intermediate terms.  
     
     
         6 . The compact Haar transform apparatus as recited in  claim 5 , wherein said sum-and-truncate logic truncates the least significant bit of a generated n+1-bit sum to form an n-bit intermediate term.  
     
     
         7 . The compact Haar transform apparatus as recited in  claim 6 , wherein said n-bit intermediate term corresponds to one of said plurality of spectral coefficients, said one of said plurality of spectral coefficients indicating whether said generated n+1-bit sum was even or odd.  
     
     
         8 . The compact Haar transform apparatus as recited in  claim 7 , wherein said n+1-bit sum is restored by adding the least significant bit of said one of said plurality of spectral coefficients to said n-bit intermediate term.  
     
     
         9 . The compact Haar transform apparatus as recited in  claim 8 , wherein said sum-and-truncate logic comprises a plurality of n+1-bit adders.  
     
     
         10 . The compact Haar transform apparatus as recited in  claim 9 , wherein said plurality of coefficient generators comprises a plurality of n+1-bit subtractors.  
     
     
         11 . The compact Haar transform apparatus as recited in  claim 10 , further comprising: 
 inverse transform logic, coupled to said plurality of spectral coefficient generators, configured to reproduce the sequence of n-bit samples, wherein each of the n-bit samples is derived from particular spectral coefficients, said particular spectral coefficients being selected based upon an n-bit sample index.    
     
     
         12 . The compact Haar transform apparatus as recited in  claim 11 , wherein said inverse transform logic comprises: 
 a rank decoder, configured to receive said n-bit sample index, and to provide one of said particular spectral coefficients, said one of said particular specific spectral coefficients corresponding to a rank of the spectral transformation;    a coefficient negator, coupled to said rank decoder, configured to negate said one of said particular spectral coefficients based upon the state of a bit of said n-bit sample index; and    LSB restoral logic, coupled to said rank decoder, configured to add a least significant bit of said one of said particular spectral coefficients into an n-bit sample computation.    
     
     
         13 . An apparatus for executing a compact Haar transform, comprising: 
 an index signal, for indicating a specific n-bit sample, said specific n-bit sample being one of a sequence of n-bit samples corresponding to the compact Haar transform; and    inverse transform logic, coupled to said index signal, for computing said specific n-bit sample, wherein said specific n-bit sample is derived from selected spectral coefficients, and wherein at most n+1 bits are required to represent each of said selected spectral coefficients.    
     
     
         14 . The apparatus as recited in  claim 13 , wherein said inverse transform logic comprises: 
 a rank decoder, for decoding said index signal to provide one of said selected spectral coefficients, said one of said selected spectral coefficients corresponding to a compact Haar spectral rank.    
     
     
         15 . The apparatus as recited in  claim 14 , wherein said inverse transform logic further comprises: 
 coefficient negation logic, coupled to said rank decoder, for negating said one of said selected spectral coefficients based upon the state of a bit of said index signal, wherein the state of said bit of said index signal indicates whether a Haar basis function corresponding to said one of said selected spectral coefficients is positive or negative; and    LSB restoral logic, coupled to said rank decoder, for adding a least significant bit of said one of said selected spectral coefficients into an n-bit sample computation, said n-bit sample computation being required to compute said n-bit sample.    
     
     
         16 . The apparatus as recited in  claim 15 , wherein said rank decoder comprises a read-only memory (ROM).  
     
     
         17 . The apparatus as recited in  claim 16 , wherein said ROM comprises memory locations, each of said memory location having a width in bits that corresponds to the number of bits required to represent an associated spectral coefficient.  
     
     
         18 . The apparatus as recited in  claim 15 , further comprising: 
 forward transform logic, for generating said selected spectral coefficients from said sequence of n-bit samples.    
     
     
         19 . The apparatus as recited in  claim 18 , wherein said forward transform logic comprises: 
 a plurality of coefficient generators, for computing said selected spectral coefficients.    sum-and-truncate logic, coupled to said coefficient generators, for computing intermediate terms, wherein at most n bits are required to represent each of said intermediate terms.    
     
     
         20 . The apparatus as recited in  claim 19 , wherein said sum-and-truncate logic truncates the least significant bit of a particular n+1-bit intermediate sum to form a particular n-bit intermediate term.  
     
     
         21 . The apparatus as recited in  claim 20 , wherein said particular n-bit intermediate term corresponds to a particular spectral coefficient, said particular spectral coefficient indicating whether said particular n+1-bit intermediate sum is even or odd.  
     
     
         22 . The apparatus as recited in  claim 21 , wherein said n+1-bit intermediate sum is restored in an inverse transformation by said LSB restoral logic.  
     
     
         23 . The apparatus as recited in  claim 22 , wherein said sum-and-truncate logic comprises an n+1-bit adder.  
     
     
         24 . The apparatus as recited in  claim 23 , wherein said plurality of coefficient generators comprises a plurality of n+1-bit subtractors.  
     
     
         25 . A computer program product for use in describing a compact Haar transform circuit, the computer program product comprising: 
 a storage medium, having computer readable instructions embodied thereon, for causing a computer upon which said computer readable instructions are executed to describe the compact Haar transform circuit, said computer readable instructions comprising: 
 first instructions, for causing said computer to describe forward Haar transform logic, said forward Haar transform logic being configured to compute spectral coefficients that correspond to a sequence of n-bit data samples, wherein at most n+1 bits are required to represent each of said spectral coefficients.  
   
     
     
         26 . The computer program product as recited in  claim 25 , wherein said forward Haar transform logic comprises: 
 sum-and-truncate logic, for computing intermediate terms, wherein at most n bits are required to represent each of said intermediate terms.    a plurality of coefficient generators, coupled to said sum-and-truncate logic, for generating said spectral coefficients.    
     
     
         27 . The computer program product as recited in  claim 26 , wherein said sum-and-truncate logic truncates the least significant bit of a generated n+1-bit sum to form an n-bit intermediate term.  
     
     
         28 . The computer program product as recited in  claim 27 , wherein said n-bit intermediate term corresponds to one of said spectral coefficients, said one of said spectral coefficients indicating whether said generated n+1-bit sum is even or odd.  
     
     
         29 . A computer program product for use in designing, simulating, fabricating, or testing a compact Haar transform circuit, the computer program product comprising: 
 a storage medium, having computer readable instructions embodied thereon, for causing a computer upon which said computer readable instructions are executed to describe the compact Haar transform circuit, said computer readable instructions comprising: 
 first instructions, for causing said computer to describe inverse Haar transform logic, said inverse Haar transform logic being configured to compute n-bit samples, wherein each of said n-bit samples is derived from spectral coefficients, and wherein at most n+1 bits are required to represent each of said spectral coefficients.  
   
     
     
         30 . A computer program product as recited in  claim 29 , wherein said inverse transform logic comprises: 
 a rank decoder, for receiving an index signal from a source thereof, and for providing one of said spectral coefficients, said one of said specific spectral coefficients corresponding to a rank of a compact Haar spectrum;    a coefficient negator, coupled to said rank decoder, for negating said one of said spectral coefficients based upon the state of a bit of said index signal; and    LSB restoral logic, coupled to said rank decoder, for adding a least significant bit of said one of said spectral coefficients into an n-bit sample computation, said n-bit sample computation being required to generate a particular n-bit sample.    
     
     
         31 . A method for executing a forward compact Haar transform, comprising: 
 a) providing a sequence of M n-bit data samples; and    b) generating corresponding n-bit intermediate spectral terms.    
     
     
         32 . The method as recited in  claim 31 , wherein said generating comprises: 
 i) summing pairs of the n-bit data samples to form n+1-bit intermediate sums corresponding to a first rank of a compact Haar spectrum; and    ii) truncating the least significant bits of each of the n+1-bit intermediate sums corresponding to the first rank of the compact Haar spectrum to form n-bit intermediate spectral terms corresponding to the first rank of the compact Haar spectrum.    
     
     
         33 . The method as recited in  claim 32 , wherein said generating further comprises: 
 iii) summing pairs of the form n-bit intermediate spectral terms corresponding to the first rank of the compact Haar spectrum to form n+1-bit intermediate sums corresponding to a next rank of the compact Haar spectrum; and    iv) truncating the least significant bits of each of the n+1-bit intermediate sums corresponding to the next rank of the compact Haar spectrum to form n-bit intermediate spectral terms corresponding to the next rank of the compact Haar spectrum.    
     
     
         34 . A method for executing a forward compact Haar transform of a sequence of n-bit data samples, comprising: 
 a) generating n-bit intermediate spectral terms; and    b) computing n+1-bit spectral coefficients.    
     
     
         35 . The method as recited in  claim 34 , wherein said generating comprises: 
 i) summing pairs of the n-bit data samples to form n+1-bit intermediate sums corresponding to a first rank of a compact Haar spectrum; and    ii) truncating the least significant bits of each of the n+1-bit intermediate sums corresponding to the first rank of the compact Haar spectrum to form n-bit intermediate spectral terms corresponding to the first rank of the compact Haar spectrum.    
     
     
         36 . The method as recited in  claim 35 , wherein said generating further comprises: 
 iii) summing pairs of the form n-bit intermediate spectral terms corresponding to the first rank of the compact Haar spectrum to form n+1-bit intermediate sums corresponding to a next rank of the compact Haar spectrum; and    iv) truncating the least significant bits of each of the n+1-bit intermediate sums corresponding to the next rank of the compact Haar spectrum to form n-bit intermediate spectral terms corresponding to the next rank of the compact Haar spectrum.    
     
     
         37 . The method as recited in  claim 36 , wherein said computing comprises: 
 i) taking the difference between pairs of the n-bit data samples to form n+1-bit spectral coefficients corresponding to the first rank of the compact Haar spectrum;    ii) taking the difference between pairs of n-bit intermediate spectral terms corresponding to the first rank of the compact Haar spectrum to form n+1-bit spectral coefficients corresponding to the next rank of the compact Haar spectrum.    
     
     
         38 . A method for executing an inverse compact Haar transform, comprising: 
 a) decoding an index to select n+1-bit spectral coefficients, the n+1-bit spectral coefficients being required to compute a specific n-bit data sample;    b) negating those n+1-bit spectral coefficients whose corresponding Haar basis function is negative for the index in a);    c) computing a sum of the negated n+1-bit spectral coefficients with the n+1-bit spectral coefficients selected in a) which are not negated by b); and    d) adding the least significant bits of all of the n+1-bit spectral coefficients selected in a) to the sum computed in c).    
     
     
         39 . The method as recited in  claim 38 , further comprising: 
 e) dividing the result of d) by 2 to generate the specific n-bit data sample.    
     
     
         40 . The method as recited in  claim 39 , further comprising: 
 f) altering the value of the index to indicate a next n-bit data sample; and    g) repeating a) through f) until all n-bit data samples within an original sequence are computed.