The discrete cosine transform (DCT) does not enable one to directly merge two equal sized transforms into one double size transform, nor to split double size transform in halves. The equal sized splitting and merging is desirable for communicating transformed packets in smaller divisible packets. As such, the DCT is not a true merge and split transformation process. When used to split or merge, a mirror inverse DCT transform does not provide for lossless transformation. The only way for the DCT to perform a merge process is to inversely transform two equal sized DCT transforms back into the time domain, and merge in the time domain, and finally forward transform the combined double size block into a double size DCT transform. This disadvantageously required additional inverse transformations and forward transformations prior to transmission, while degrading the transformed data when additionally inverse and forward again transforming the data, and hence, the DCT is not a true direct split or merge transform. Another problem with the fast discrete cosine transform is that there is no decimation-in-time DCT separate flow process compatible with the DCT decimation-in-time combine flow process. That is, prior DCT processes do not have mirror block and flow processes. In prior art, the T(N/2), type-II DCT and D(N/2) type-IV DCT blocks are DCT transforms of the sum and the difference of two equal sized blocks processing first and second halves of the input data prior to combining the two halves into a double size DCT output. In both forward and inverse DCT transforms, the prior art requires operations on two different types of discrete cosine transforms T(N/2) and D(N/2), which are incompatible with true merge and split transform processing.
Another disadvantage of the prior DCT transforms is that the DCT are processed with integer operations that always incurred large errors in the resulting transformed data that is very lossy, whereas floating-point operations have minimum amount of loss. The term lossy means that the resulting data from transform to inverse transform losses data fidelity. In the content of image compression and decompression, the lossy image would have lower fidelity that the original uncompressed image. There are no completely lossless integer operated type-II or type-IV discrete cosine transforms. Yet another disadvantage in the prior art type-II DCT and type-IV DCT is that the DCTs are implemented with single function. As such, the DCTs do not share resources with other transforms, for example, a Haar transform. A 2×2 rotator, whether lossy or lossless, has two bit-parallel serial word inputs X1 and X2 that are rotated in radians into two outputs Y1, and Y2. The first output of the 2×2 rotator is the first input weighted by the cosine of the rotating angle adding to the second input weighted by the sine of the same rotating angle. The second output of a 2×2 rotator is the first input weighted by the sine of the same rotating angle subtracted from the second input weighted by the cosine of the same rotating angle. That is, Y1, =cos θX1+sin θX2 and Y2=cos θX1+sin θX2. An integer lossy 2×2 rotator has two integer outputs for two integer inputs. An integer lossy 2×2 rotator has been implemented using traditional lifting stages. The unweighted input in each lifting stage is always used for addition but not used for subtraction. Rotators have been used in DCT transforms. Rounding errors cannot be cancelled during continuous use of additions in lifting stages. The total rounding error of the traditional lifting method used in prior arts is very large because the accumulation of rounding errors throughout lifting stages. As such, the use of traditional lifting method produces lossy rotators.
Most linear discrete transforms including DCT, produce non-integer coefficients. The DCT coefficients have to be quantized into integers. The rounding off or quantizing of the DCT coefficients into integers cause information loss that can never be completely recovered by inverse transformations. In many applications, it is often desirable to approximate the original linear DCT with a nonlinear DCT that may produce integer outputs from integer inputs, while retaining the reversibility property of a transform. However, this reversibility still suffers of loss of data fidelity during the transformation and inverse transformation processes. Discrete cosine transforms (DCTs) are widely used by JPEG, MPEG and other international data compression standards to perform lossy compressions on digital image, audio, and video data. These compression methods divide the data into blocks, each of which is first transformed by a linear orthogonal transform, such as, the DCT. The DCT matrix consists of real numbers. The DCT outputs are floating point numbers, and the floating point number have to be quantized in order to convert to integers for transform domain processing. Most of the existing integer discrete cosine transforms are either lossy or unfavorably causing the dynamic range of transform coefficients to increase. There is no lossless integer DCT that still retains the transform fidelity as of the floating point DCT. The quantization process will cause information loss in the inverse transform. The DCT has been used by the current international still-image compression standard JPEG for many years. Yet the international still-image compression standard JPEG2000 has adopted the wavelet transforms. The JPEG2000 does not use the Haar wavelet transform. Also, there is no compatibility between the DCT and JPEG2000 standard wavelet transforms. As such, there are no common processes shared by these two transforms.
The modulated lapped transform is a special form of the cosine-modulated subband filter banks. The modulated lapped transform is also called modified discrete cosine transform in MPEG, the international data compression standards for audio and video data. The modulated lapped transform compression method divides the data into windowed overlapped blocks, each of the overlapped portion is first transformed by a linear orthogonal transform, i.e., the type-IV discrete cosine transform (DCT-IV). The coefficients are quantized into integers. The rounding off or quantizing of the modulated lapped transform coefficients into integers causes information loss that can never be completely recovered by inverse transforms. It is desirable to approximate the original linear modulated lapped transform with a nonlinear modulated lapped transform that may produce integer outputs from integer inputs, while retaining the reversibility property of a transform. The window function and the DCT-IV matrix consist of real numbers. The DCT-IV outputs are floating point numbers that have to be quantized in order to convert to integers. The quantization process causes information loss that may never be recovered in the inverse transform. In many applications, it is desirable to approximate the linear modulated lapped transform with a nonlinear transform that produces integer coefficients from which the original integer data can be reconstructed losslessly. Both the DCT-IV and Haar wavelet transform are exact in floating point operations. However, in many applications the inputs are integer-valued data sequences. These DCT-IV transforms and Haar wavelet transforms are approximated by nonlinear transforms producing integer outputs as close as possible to the true outputs, but still include lossy data. These nonlinear operations may be regarded as a quantization process. But the nonlinear transform is reversible while the quantization is nonreversible.
The random numbers generators are used in many applications. Random numbers produced by digital electronic random number generators are not truly random. The resulting random numbers, especially integer random numbers, either have certain correlations between the generated numbers or have some pseudo periodic structures. Typical examples are the pseudo random sequences found in wireless communications systems. The Haar transform cannot be used to accurately decorrelate the pseudo random sequences for use as a random number generator. The Haar transform has been used for data compression and edge detection in medical images. But, the performance of the regular Haar transform is limited by the lack of sufficient decorrelation power of the Haar transform. These and other disadvantages are solved or reduced using the invention.
USPTO Backgrounds
USPTO Backgrounds