Title of Invention

"A DATA CODEC SYSTEM FOR A DIGITAL COMMUNICATION SYSTEM"

Abstract

A data CODEC system for a digital communication system, characterized in that, said data CODEC system comprising: a decomposition stage for receiving an input data signal and generating a signal of transformed coefficients; an adaptive centroid based quantizer for receiving the transformed coefficients and generating optimal non-uniform spaced quantizers; wherein the adaptive centroid based quantizer has a least means square/(LMS) stage to generate a matrix of minimum error paths of the quantizers and a centroid computation stage for computing and updating a centroid calculation of the matrix of minimum error path. a coding stage for coding the quantizers into a coded signal; a channel for transmitting the coded signal; and a decoder for decoding the transmitted signal.

Full Text

The present invention relates to a data CODEC system for a digital communication system. TECHNICAL FIELD This invention relates in general to data compression and particularly to digital data compression. Specifically, the invention relates to a method and apparatus that provides improved quantization in systems utilizing a trellis coded quantizer. BACKGROUND With the advent of technologies and services related to teleconferencing and digital image storage, considerable progress has been made in the field of digital signal processing. As will be appreciated by those skilled in the art, digital signal processing typically relates to systems, devices, and methodologies for generating a sampled data signal, compressing the signal for storage and/or transmission, and thereafter reconstructing the original data from the compressed signal. Critical to any highly efficient, cost effective digital signal processing system is the methodology used for achieving compression. As is known in the art, data compression refers to the steps performed to map an original data signal into a bit stream suitable for communication over a channel or storage in a suitable medium. Methodologies capable of minimizing the amount of information necessary to represent and recover an original data are desirable in order to lower computational complexity and cost. In addition to cost, simplicity of hardware and software implementations capable of providing high quality data reproduction with minimal delay are likewisse desirable. Quantization refers to the technique of taking a bit stream of data and compressing it for later reproduction. There are several algorithms that may be used to achieve compression of a data signal. The most elementary methods take signal samples and quantize each signal sample into one of a small number of levels. A well-known quantizer is the Lloyd-Max optimal quantizer using nearest neighbor, minimum squared error (MSE) rules to classify an input into a specified number of levels. Quantization can be achieved through a variety of other approaches including vector, scalar, rounding, truncation, and trellis coded quantization (TCQ)) among other methods. Vector quantization is considered an efficient means of quantization, because it takes a group of samples and represents that group by only one symbol thus yielding improved compression and generating a high signal-to-noise (SNR). However, vector quantisation is computationally intensive and requires a look-up table (i.e. needs memory). Scalar quantization represents one sample per symbol and is less computationally extensive than vector quantization. However, scalar quantization has the disadvantage of lower compression rate. An alternative to quantization is the rounding off or truncating of the output signal but this may lead to resolution problems. To present, the next standard of JPEG 2000 (Joint Photographic Experts Group) systems for still images proposes algorithms which use a wavelet to achieve decomposition of an input signal and a trellis coded quantizer for signal compression. Trellis coded quantization is based on a Viterbi algorithm which provides a search to generate a minimum error path. Generally, the Viterbi works in conjunction with a lattice quantizer (uniform grid). While the lattice quantization operation is computationally effective, the result is not optimal for distortion. At high compression rates (low bits/sample) the SNR degrades. Hence, there remains a need for an improved TCQ technique and apparatus that operates to reduce the noise generated during data signal compression (quantization noise), and improve the achievable signal to noise ratio (quality) during data reconstruction. Accordingly, there is a need for an improved trellis coded quantization (TCQ) technique particularly as applied to digital signal processing systems. According to the present invention there is provided a data CODEC system for a digital communication system, characterized in that, said data CODEC system comprising: a decomposition stage for receiving an input data signal and generating a signal of transformed coefficients; an adaptive centroid based quantizer for receiving the transformed coefficients and generating optimal non-uniform spaced quantizers; wherein the adaptive centroid based quantizer has a least means square/(LMS) stage (202) to generate a matrix of minimum error paths of the quantizers and a centroid computation stage for computing and updating a centroid calculation of the matrix of minimum error path. a coding stage for coding the quantizers into a coded signal; a channel for transmitting the coded signal; and a decoder for decoding the transmitted signal. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram of a data CODEC in accordance with the preferred embodiment of the invention. FIG. 2 is an adaptive centroid based quantizer in accordance with the present invention. FIG. 3 a graphical representation of an example of the level distribution for each of the four quantizer states going through the first iteration of i=0 for the quantizer of FIG. 2 in accordance with the present invention. FIG. 4 is an example of a pictorial representation of stored indexes from the first iteration for the quantizer of FIG. 2 in accordance with the present invention. FIG. 5 a graphical representation of an example of the level distribution for each of the four quantizer states going through an arbitrary iteration of the quantizer of FIG. 2 in accordance with the present invention. FIG. 6 is a proposed implementation of a one dimensional data stream conversion prior to quantization in accordance with an alternative embodiment of the invention. FIG. 7 shows the 1-D data stream conversion step as part of a complete data CODEC system in accordance with the alternative embodiment of the invention. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT While the specification concludes with claims defining the features of the invention that are regarded as novel, it is believed that the invention will be better understood from a consideration of the following description in conjunction with the drawing figures, in which like reference numerals are carried forward. The invention to be described herein improves the quantization step which can be implemented as part of a data CODEC. Referring now to FIG. 1, there is shown a data CODEC block diagram 100 in accordance with the present invention. This data CODEC 100 can be applied to three-dimensional (3-D) systems, such as video, two-dimensional (2-D) systems, such as still images, as well as one-dimensional (1-D) systems, such as speech. Data CODEC 100 includes an encoder 110 and a decoder 120. Briefly, an input data signal S(n) 102, having a predetermined bit/sample resolution, goes through a transformation at decomposition stage 112. The: transformed signal x(n) 113 then goes through a quantization stage 114 for further compression in accordance with the present invention. In accordance with the present invention, the quantization stage 114 provides a centroid based quantization to generate non-uniform spaced quantizers. The quantized signal 115 is then coded through coding stage 116 preferably using one of a variety of well xnown coding schemes. A coded signal 118 is then communicated over or stored to channel 130. At the receiving end, decoder 120 employs an inverse coding stage 132, inverse quantization stage 133, and an inverse decomposition stage 134 to recreate the input data signal S(n) as output data signal S'(n) 136. The decomposition stage 112 is basically a frequency domain analyzer which performs data conversion through one of a variety of well known methods such as wavelet, FFT (Fast Fourier Transform), DCT (Discrete Cosine Transform), DFT (Discrete Fourier Transform), DST (Discrete Sine Transform) KLT (Karhunen-Loewe Transform), WHT (Walsh- Hadamard Transform). The transformation used here falls under what is called subband coding. In subband coding, whether 1-D, 2-D, or 3-D the input data signal 102 is repeatedly divided through a filter bank of low pass and high pass filters to produce an output of subband selected coefficients of the original signal. The transformed signal x(n) 113 will thus also be referred to as a signal of transformed coefficients, in the preferred embodiment of the invention, decomposition stage 112 may comprise a wavelet such as that proposed in the next standards for v" JPEG 2000 systems. The wavelet helps achieve csrtain multi-resolutional capabilities and minimizes blocking affects in the case of image data. Coding stags 116 and inverse coding stage 132 can operate through a variety of coding schemes including but not limited to arithmetic, Huffman, or other well known coding and decoding schemes. Channel 130 may include a wireless, wireline, acoustic, or optically linked path such as, for example, a radio frequency (RF) or fiber optic transmission path. The channel 130 may likewise be a storage medium such as those now known or later developed. Inverse quantization stage 133 can operate through a variety of inverse quantisation schemes including but not limited to trellis coded quantization, scalar, vector, or even an inverse version of the adaptive centroid based quantizer 114. Inverse decomposition stage 134 is preferably controlled by well known means such as inverse wavelet transformation or by a set of filter banks. In accordance with the present invention, the quantization stage 114 is a centroid-base quantizer which takes an entire range of coefficients (which represent all or some of the subbands) and generates optimal non-uniform allocation of the quantiser levels within the states. Referring now to FIG. 2, there is shown a block diagram of a four state trellis coded quantizing (TCQ) stage 114 in accordance with the preferred embodiment invention. Briefly, in accordance with the invention, a trellis path optimization 202 is performed on transformed coefficients signal x(n) 113 to generate an output configured as a path matrix 206 upon which a centroid computation is performed at stage 208. The centroids are then fed back to the trellis path optimization stage 202 to be used ;is the new adaptive centers for the quantizer levels for another iteration and generation of path matrix and updated centroid computation. The path matrix 206 is fomed of vector elements "nk,j", where k represents the quantization state from a total set of K states, and j represents the level from a total set of J levels per state. In accordance with the present invention, the steps of trellis path optimization 202, path matrix configuration 206, and centroid updating 208 are adaptively reiterated until an acceptable SNR, or other desired error measurement, entropy or bit rate is achieved 210, In accordance with the present invention, the trellis path optimization 202 is preferably achieved through a "least mean square" (LMS) algorithm for selecting transitions from quantizer to quantizer to obt.ain the path yielding a minimum error. However, other optimization schemes can also be used, such as a mini-max, to yield minimum error paths. An example of a basic implementation of path optimization 202 is shown in a preferred embod:_ment 209 where for a set of K quantizers referred to as states, each having J levels, the quantizers (states and levels) cover an entire range of input data. The states and levels may be obtained from a larger quantizer after splitting it into sub-sets that may initially be uniformly distributed. The quantization levels of each state define the quantization intervals by the mid-points, or centroids, between the levels. In the course of finding the best level and state corresponding to an input data sample, optimization entails finding the best sequence of states and levels as the data samples are Inputted to minimize a distortion, error measurement, entropy, or bit rate, 210. The trellis is optimized for a particular data set or sets, actually making it an adaptive quantizer with several states, each of which is in a particularly smaller and optimized quantizer. There is a match between the state sequence and a particular datci sequence. If, after optimization a different data set is inputted, even with the same probability density function (pdf) or histogram, most of the distortion reduction could disappear and a new optimization may be performed, thus resulting in an adaptive procedure. For a trellis quantizer of K states, select only one of the available J levels for each incoming data sample, Thus, if M represents the global number of quantization steps to each state in the trellis, M/K levels may be assigned. The first state and level for the first input data sample may be determined independently by finding the state that yields the lowest error. Subsequently, each incoming input value can only be assigned to one of 2f states of all K states following a transition table, such as the table 209 shown in FIG. 2. Therefore, it takes *f" bits to tell a decoder what transition path to follow. For example, as shown in 209, with f=l, from Qo, the next sample input can be quantized by either Qo (or Q1) and in addition, certain bits to tell the decoder which level to use. The four-state trellis path optimization 209 or any other K state trellis can also be implemented in another configuration that is basically its mirror image. For the purposes of example, an LMS algorithm known as the Viterbi algorithm will be the minimum error algorithm described- The Viterbi algorithm takes a whole range of data, say x(n) 113 where n can be 0 to N-1, and quantizes this data as part of a first iteration, to allow data to be allocated to the different levels for each state. Whatever data falls between the quantizers will be allocated to the nearest level. The Viterbi algorithm is a " least mean square" (LMS) way of finding the minimum error for all the different paths between the: quantizers. The Viterbi algorithm optimizes the path through the trellis, path Di(Q1) at the i-th iteration with quantizer set {Q1}, following the allowable transitions. For example/ while referring to the Viterbi shown in FIG. 2, the sample x(n) at t=0 is quantized to Q0(C), then at t=l the transition can only go to either Qc(l) or Qx(l)- At the end of the LMS algorithm, i.% the history of the path taken to yield minimum error is' succinctly extracted and represented in the form of a three dimensional path matrix 206. From the path matrix 206, the centroids are calculated at stage 208 which is then used to represent the data samples which fell within a particular quantization state and level. The centroid calculation is based on an average determined by the following equation: (Equation Removed) where nkj denotes vector and if nkj is empty, then (Equation Removed) The newly computed and updated, centroids; C X,(j(1+i) are then fed back to the trellis path optimization stage 202 where they are used as the new centers for the j-th level of the k-th state, for the start of the next (i+1)-th iteration. This is represented by the feedback dash arrow in FIG. 2. As an example consider a string of input data for x(n) 304 consisting of ten samples where: input data = x(n) = [10.0, 10.2, 0.5, 2.18, 1.9, 13.75, 10.40, 0,1, 11.2, 2.5] in other words, where x(0) = 10.0 x(l) = 10.2 x(3) - 0.5 x(9) = 2.5 and where [0, 1, 2, 3, ,..9] each represent an index that points to specific data sample value. (Note that the actual values of data samples are the transformed coefficients x(n).) Next, the transformed coefficients input x(n) 113 is quantized using trellis 202. In this example, trellis 202 is configured to have four states [QO, Ql, Q3, Q4] with each state having four levels (therefore there are sixteen quantization steps and sixteen centroids to be computed). Though shown and described in terms of a four state four level trellis, one skilled in the art appreciates, that trellis 202 can be formed in a variety of configurations having two or more states, each state having several levels. Typically, however, trellis quantizers utilize four states, the simplest case. Again, the four states of trellis 202 are quantisers QO, Ql, Q2, Q3 and each state has been assigned four levels. For the first iteration it will be assumed that a Viterbi algorithm is used to obtain the least mean square error yielding path in the quantizer assignment, however other LMS algorithms could also be utilized. For the first iteration, a uniform distribution of the levels is used, however, one skilled in the art also appreciates that the first iteration could also be performed using a non-uniform distribution of the levels as well. For instance, in the case of an initial quantizer allocation that uses the distribution of the input data to best assign quantization states and levels, a non-uniform distribution of levels may be more suitable. For example, for an input sample range which has a Laplacian type distribution (i.e. sharply peaked, zero-mean distribution), a shrink factor can be applied to quantization steps to achieve a non-uniform distribution of levels. Referring now to FIG. 3, there is shown a graphical representation of the level distribution for each of the four quantizer states going through the first iteration of i=0. Graph 300 represents a possible example of the first iteration of quantizer states QO, Ql, Q2, Q3 versus the four levels of data input ranges divided into sixteen quantization steps. The following table shows various ranges of input data and the allocation of quantizers states and levels for that given range (where "[" is inclusive and ")" is exclusive). (Table Removed) Referring back to the Viterbi trellis of FIG. 2, the trellis takes a sample x(n1) and if the sample was quantized to any of four levels of state QO (or Q2) at time t-t1, then the next sample x(n1+l) at time t=t1+l can only be quantized to any of the four levels of state QO or Ql. Similarly, if sample x(nA) was quantized to any of four levels of state Ql (or Q3) at t=tt, then the next sample x(ni+l) at time t=ti-t-l can only be quantized to any of the four levels of states Q2 or Q3. • So, for the input data x(n) given above, the data gets quantized through LMS stage 202 based not only on the value of the sampled data but also on the previous quantizer state. A path matrix 206 is then configured by storing the indexes pointing to the input data into the various matrix locations of n(state, level). The following table shows how the sampled data gets quantized and the indexes are assigned to the matrix locations. (Table Removed) The indexes stored in each matrix location represent the LMS (least mesan square) of the original data (i.e. the path of minimum error) . So, continuing through "he first iteration (which in this example started with a uniform distribution), the matrix 206 is formed of the following stored indexes: (Table Removed) A pictorial representation of the stored .ndexes is shown in FIG. 4 to .help illustrate that the path matrix 206 actually represents a 3-D configuration 400 of quantizer state, level, and index. Each input data point is represented by a.n index denoting the position .'In time at which the sample: input point occurs. In the path matrix 206 of FIG. 2, each element ni; consists of a vector whose elements are the indices of the particular input data samples that were quantized to State kf level j. In the case where no input sample was quantized to state k, level j, this matrix element nki would be empty. Continuing through the first iteration of i=0, the next step is to calculate the centroids. As shown in equations(l), (2) above, the calculation of the centroid is based on an average. Thus, the centroid computations for the first iteration (t=i) of this example produce: for n00 ==> c00 = x[7] =0.1 and, c01 = remains as previously set c02 = remains as previously set for n03==> C03 = x[8] = 11.2 and for nic ==> eu - .1/2 [x(3) +x(9)] - 1/2^(2-18 + 2.5) = 2.34 (note that prior to this iteration (at t=i-l) the centre id cio was 1.5 ) cu = remains as previously set for n12. ==> c12 = x[l] = 10.2 for n12 ==> c10 = x[5] = 13.75 c13 = remains as previously set and for n20 ==> c20 = 1/2 [x(2) + x(4)]- 1/2 [0.s + 1.9] = 1.2 (note that prior to this iteration (at t=i-l) the centre id c20 was 2.5 ) C21 = remains as previously set and for n,2 ==> c52 - 1/2 [x(0) + x(6)]= 1/2 [10.0 + 10.4] = 10.2 (note that prior to this iteration (at t=i-l) the centroid c2! was 10.5 ) c23 = remains as previously set c30 = remains as previously set c31 = remains as previously set c32 = remains as previously set C32 = remains as previously set c33 = remains as previously set Thus, where the previous centroids were all centered around 0.5, as shown in the example of FIG. 3, now a new centroid is available for each state and level of quantizer (which is now non-uniform). The same set of data x(n) gets reclassifled with the new centroids in the second iteration, and the iteration process is repeated until the error measurement for the given input signal reaches a predetermined desired value. FIG. 5 shows a graph 500 of an arbitrary exanple of how after one or several adaptive iterations, the various states and levels may change from a uniform distribution to one that may best fit the input data. This method described by the invention guarantees convergence to a lower error at each iteration. Thus, taking sampled data coefficients x(n) through the steps of trellis quantizing with a least mean square algorithm to form a matrix and calculating updated centroids for each quantization state provides a pruning algorithm which is reiterated until there is suitable convergence to generate a desired SNR. In the case of a new subband or a new set of input data, the quantizer can also be trained to commence the first iteration using centroid values computed from a previous data run. In this way, if similar input data is expected in the next input data range, the quantization can commence with centroid values which are. much closer to being optimized and thus fewer iterations will be needed to achieve full optimization of a SNR. In the case of prior art, the quantization schemes have basically stopped at the Viterbi algorithm stage because it was assumed that the delta between the quantization levels was uniform. By applying applicants quantization scheme 114 as described by the invention, the cen-troid calculation is dynamically adjusted as the distance between the quantization levels changes (as can be seen by comparing FIGs. 3 and 5). Hence, while the prior art operated on a uniformly spaced system, the. quantization scheme of the present invention allows for non uniformity and adaptation ba.sed on the input data. The quantizcttion stage 114 of the present invention adaptively allocg.tes the levels of the quantization states using updated centroids. The quantizers are thu optimized to the data distribution so as to achieve improved SNR. The quantizer outputs 115 get coded at stage 116 and transmitted to channel 130. The quantizers outputs 115 are thus adaptively aillocated based on the incoming signal. The adaptive centroid based quantizer described by the invention allows input signals, such as an image signal, to be optimized by adaptively allocating the quantizations base on the input signal. The quantization block 114 can also be trained so that for certain types of signals, such as facial images during teleconferencing, the quantisation step will commence at some predetermined state and level allocation to reduce processing time. The following steps summarize the adaptive centroid based quantization scheme in accordance with the invention: i) The input data range is divided into a predetermined number of steps. For the example described above there were 16 quantization steps for a 4 bit trellis. ii) The quantization steps are formed into a matrix of states. In the above example, steps 1, 5, 9, 13 go to state one, stepa 2, 6, 10, 14 to state two and so on. This is the initial sstate assignment. iii) A shrink factor may be introduced as previously described when the input data is expected to have a predetermined distribution, such as a Laplacian distribution- (qk1,k = 0; K - 1 } {O iv) Run trains with LMS algorithm, preferably a Viterbi algorithm.. v) Obtain first raw SNK. value or other error measurements by computing mean square error. vi) Compute centroid values for the data samples, one centreid for each level, per state. Obtain a refined higher SNR value by computing a new mean squared error. viii) Run trellis with LMS algorithm a second time using update c6ntroid values from step (iv). Recompute centroids, and obtain new values of SNR. The last veilue of SNR will be better than the first. The SNR increases in diminishing returns at each iteration cycle by centroid updating. x) Stop iterations when some predeterrained SNR criteria is met The advantages of the adaptive centroid based quantization scheme described by the invention include faster iteration process time (as compared to gradient methods) as well as convergence. One optional parameter was introduced in the above steps, a shrink factor. If the input data has a sharp distribution like a zero-mean Laplacian, the outermost levels will see few data samples. Therefore, a shrink factor can be applied concentrating all levels into the more active center of the input range. The resulting SNR increases monotonically at each iteration and converges towards an optimal SNR level. The effect of the shrink factor is to reduce the total number of iterations to attain the optima.l SNR value. The system application described thus far includes a transformation stage, quantization stage, coding, channel, inverse coding, and inverse decomposition stage. In another embodiment of the invention, vectorization (converting 2D to 1D data stream) and threshold stages will be performed prior to quantization 114 so that long strings v of repetitive data can be represented by a single code and a non-zero ID daxa stream is obtained. FIG. 6 is a proposed implementation in which the data x(n) is vectorized to 1-D at stage 602 to produce vector coefficients 604. These vector coefficients 604 are then compared to a threshold 606 prior quantization. Basically/ data samples of zero and/or values close to zero will be discarded by threshold 606 to obtain a modified one-dimensional input data array of non-zero elements as inputs for the adaptive centroid based quantizer 114. PIG. 7 shows the 1-D data stream conversion step as part of a complete CODEC system 700. once quantized there may be repetitive data which is preferably coded at coding stage 116 for further compression. This reduces transmission time and computation time. Again, the advantages achieved through the dynamic centroLd based quantization 114 will be achieved with the system 700 embodiment along with the additional benefit of efficient transmissions of repetitive data through coded signals. While the preferred embodiments of the invention have been illustrated and described, it will be clear that the invention is not so limited. Numerous modifications, changes, variations, substitutions and equivalents will occur to those skilled in the art without depa.rting from the spirit and scope of the present invention as defined by the appended claims. What is claimed is: WE CLAIM 1. A data CODEC system (100) for a digital communication system, characterized in that, said data CODEC system comprising: a decomposition stage (112) for receiving an input data signal (102) and generating a signal of transformed coefficients (113); an adaptive centroid based quantizer (114) for receiving the transformed coefficients and generating optimal non-uniform spaced quantizers (115); wherein the adaptive centroid based quantizer (114) has a least means square /(LMS) stage (202) to generate a matrix of minimum error paths (206) of the quantizers and a centroid computation stage (208) for computing and updating a centroid calculation of the matrix of minimum error path. a coding stage (116) for coding the quantizers into a coded signal; a channel (130) for transmitting the coded signal; and a decoder (120) for decoding the transmitted signal. 2. A data CODEC as claimed in claim 1, wherein the input data signal (102) is first converted into a one dimensional (1-D) data input stream meeting a predetermined threshold in which unwanted or repetitive data is discarded. 3. A data CODEC as claimed in claim 1, wherein the decoder (120) has an inverse of the adaptive centroid based quantizer (114) for converting the transmitted signal into a decoded signal. 4. A data CODEC as claimed in claim 1, wherein non-uniformly spaced quantizers (115) are generated until a predetermined error measurement or bit rate is achieved. 5. A data CODEC system substantially as hereinbefore described with reference to the accompanying drawings.

Documents:

584-del-1999-abstract.pdf

584-del-1999-claims.pdf

584-del-1999-correspondence-others.pdf

584-del-1999-correspondence-po.pdf

584-del-1999-description (complete).pdf

584-del-1999-drawings.pdf

584-DEL-1999-Form-1.pdf

584-del-1999-form-2.pdf

584-del-1999-gpa.pdf

584-del-1999-pct-210.pdf

584-del-1999-pct-220.pdf

584-del-1999-petition-137.pdf

584-del-1999-petition-138.pdf