A discrete wavelet transform (DWT) has been widely applied to various digital signal processing techniques. It has been designed under a certain condition such as perfect reconstruction, aliasing cancellation, regularity, vanishing moment, etc. This article introduces a new condition referred to “DC lossless”. It guarantees lossless reconstruction of a constant input signal (DC signal) instead of rounding of signal values and coefficient values inside a transform. The minimum word length of the values under the new condition is theoretically derived and experimentally verified.
Since JPEG 2000 algorithm based on the discrete wavelet transform (DWT) was adopted as an international standard for digital cinema video coding , high speed and low power implementation of a DWT has been becoming an issue of great importance [2,3]. In designing a DWT, its coefficient values and signal values are assumed to be real numbers. However, in implementation, they are rounded to rational numbers so that they are expressed with finite word length representation in binary digit. Therefore it is inevitable to have rounding errors inside a DWT processing unit.
In this article, we derive a condition on word length of coefficient values and that of signal values of a DWT such that the transform becomes lossless for a DC signal. Under this condition (DC lossless condition), it is theoretically guaranteed that an output signal contains no error in spite of rounding of coefficients and signals inside the DWT. We treat the irreversible 9-7 DWT adopted by the JPEG 2000 for lossy coding of image signals as an example.
In case of the 5-3 DWT in JPEG 2000 for lossless coding, benefiting from its lifting structure [4-6], lossless reconstruction of any signal is guaranteed even though signals and coefficients are rounded. On the contrary, it does not hold for the 9-7 DWT because of scaling for adjusting DC gain of a low pass filter in a forward transform . However, we have pointed out that it became possible to be lossless for a DC signal under a certain condition on word length of coefficients and signals .
This DC lossless condition is a necessary condition for the regularity which has been analyzed by numerous researchers to improve coding performance of a transform. When the regularity is not satisfied, the DWT has some problems such as a checker board artifact which is observed in a reconstructed signal as unnecessary high frequency noise in flat or smooth region of a signal . It also brings about DC leakage which decreases the coding gain of a transform .
The regularity has been structurally guaranteed for a two channel quadrature mirror filter bank (QMF)  and the DCT  respectively. However, since these previous methods were based on the lattice structure, these are not directly applicable to the lifting structure of the 9-7 DWT. Beside these relations to the regularity, the DC lossless condition itself is also considered to be important for white balancing of a video system in which the DC signal is used as a reference input for calibration .
This article aims at deriving the DC lossless condition theoretically and clarifying the minimum word length of signals and coefficients. In conventional analysis, errors due to shortening of word length of signals (signal errors) were described as 'additive' to a signal [7,12]. They were treated as independent and uniformly distributed white noise. On the other hand, errors due to rounding of coefficients (coefficient errors) were described as 'multiplicative' to a signal and evaluated with the sensitivity [13-15]. It should be noted that the signal error and the coefficient error have been treated independently. Unlike those conventional approaches, we utilize mutual effect between rounding of signals and that of coefficients. Introducing a new model which unifies the coefficient error and the signal error, we define tolerance for those errors as a parameter to simultaneously control both of word length of signals and that of coefficients.
As a result of our theoretical analysis, the minimum word length of signals and that of coefficients inside the lifting 9-7 DWT are derived under the DC lossless condition. We confirm that the minimum word length derived by our analysis is shorter than that determined by a conventional approach. We also confirm that the DWT under the condition does not have the checker board for a DC signal.
This article is organized as follows. Chapter 2 defines a rounding operation and a rounding error, describes their basic properties in algebraic approach, and derives 'addition' formula and 'multiplication' formula of the rounding (modulo) operation. Application of these formulas to scaling of a signal value is introduced in chapter 3. Chapter 4 introduces the DC lossless DWT. Its usefulness is also described. Derivation process of conditions on word length of signals and coefficients is described in chapter 5. The new condition derived from the basic properties in chapter 2 is summarized in chapter 6. Other related condition derived from a conventional approach is also summarized. Theoretical results are verified and the minimum word length of the DC lossless DWT is clarified in chapter 7. This article is concluded in chapter 8.
2. Rounding operation and its basic formulas
This chapter introduces basic properties of the rounding operation focusing on 'quotient', rather than 'remainder', in modulo operation. So far, 'remainder' had been attracted numerous mathematicians' attention and various basic properties were found such as the Chinese remainder theorem in the commutative algebra (commutative ring theory). On the contrary, 'quotient' plays an important role as a 'practical' value in finite word length implementation in modern computer systems. This chapter introduces an algebraic approach of expressing 'quotient' as a practical value, and 'remainder' as a rounding error, so that it can be applied to analyzing exact behavior of rounding errors in a complex calculation procedure.
2.1. Definition of rounding operation and rounding error
In a digital calculation system, all the values of both of signals and coefficients are calculated and stored as a binary digit with finite word length. In this article, we treat a case such that a value
For example, in case of
as an example. This rounding operation generates a rounding error. We denote it as
Expanding these expressions to an
Fig.1 illustrates rounding operations expressed by these equations. The term
Fig. 1. Definition of the rounding operation and the rounding error. (a) An integer implementation case. (b) An
2.2. Basic properties of the rounding operation
Since a convolution includes additions and multiplications, we should know behavior of an addition of two values
First of all, let's derive basic properties of the rounding operation starting with an obvious property;
It represents that only a real number
It suggests that an integer
Since the range of a rounding error is
we can add two more identities;
The equations above for
In addition, Eq.(12) can be extended to a more general case with an integer
2.3. Basic formulas of the rounding operation
Formulas for a rounding error (remainder) can be also derived as
for real numbers
Especially when two kinds of word lengths are mixed in a signal processing, the following variation of the multiplication formula is conveniently applied to analyzing behavior of signals and errors in a pair of encoder and decoder .
3. Application of the formulas to basic signal processing
This chapter applies the formulas to some basic signal processing cases.
3.1. Mapping invariant condition
Fig.2 illustrates a scaling of a signal value
In case of Fig.2(b), an input value
From the basic properties, the mapping invariant condition is derived as
The Eq.(23) also means
which gives tolerance to the rounding error of a coefficient . This is the mapping invariant condition on word length
Unlike the condition above, a sufficient condition can be derived by substituting the upper bound of errors and signals;
to Eq.(23). It results in the condition described as
This condition is too strict and requires too long word length to guarantee the mapping invariance. In both cases of Eq.(24) and Eq.(26), the mapping invariant condition determines the minimum of word length W of a coefficient under a given word length
3.2. Lossless condition on a scaling pair
Fig.3 illustrates a pair of two multipliers. In Fig.3(a), an input signal
We apply the formulas and the properties to derive the condition on
From the basic properties, the lossless condition on a scaling pair is derived as
This condition determines the word length F1 and F2 of signals for an input value
Unlike the exact condition above, a sufficient condition can be derived by analyzing the upper bound as follows.
As a results, when the sufficient condition given by
holds, the scaling pair becomes lossless. However this condition is too strict and requires too long word length of signals.
4. Application of the formulas to DWT
This chapter introduces the DC lossless DWT [8, 18]. Definition and its usefulness are also described. The algebraic approach based on the formulas is applied to derive conditions on word length of signals and coefficients. Derivation process is described in chapter 5.
4.1. DWT and its word length of signals and coefficients
Fig.4 illustrates the irreversible 9-7 DWT of the JPEG 2000 standard . The forward transform in Fig.4(a) decomposes an input signal
The multiplier coefficients
Denoting the integer part as
including 1 [bit] for the sign part. Similarly, total word length
In Fig.4, fraction part of the input signal
4.2. Definition of DC lossless property and its necessity
In this article, we define the DC lossless as the conjunction of the following two propositions:
for a given constant value
Fig.5(a) illustrates an example of a video system. It contains an encoder and a decoder which are composed of a forward DWT and a backward DWT. In white balancing, a camera and a display are calibrated with a constant valued input signal (DC signal) [11,19]. Therefore, it is useful for this calibration if the forward DWT and its backward do not generate any error. In this case, the camera and the display can be calibrated ignoring existence of the encoder and the decoder as illustrated in Fig.5(b). Namely, the DC lossless condition provides a low complexity DWT useful for the white balancing.
In addition, the DC lossless condition is a necessary condition for the regularity which controls smoothness of basis functions and coding performance of a transform. A DWT under the regularity does not generate the checker board artifact or the DC leakage. Harada et. al. analyzed a condition for the regularity of a two channel quadrature mirror filter bank (QMF) . They confirmed that a QMF under the condition has reduced checker board artifact for an input step signal. It is expanded to a multirate system under short word length expression . The regularity was structurally guaranteed for a biorthogonal linear phase filter bank [21,22] and the DCT  respectively. However, since these previous methods are based on factorization of a transfer function including (1+z-1) or (1-z-1) in the lattice structure, these are not directly applicable to the lifting structure of the 9-7 DWT in Fig.4.
In this article, we derive the DC lossless condition theoretically in chapter 5, and determine the minimum word length of signals and that of coefficients under the condition in following chapters.
5. Derivation of condition for the DC lossless DWT
This chapter describes derivation process of the DC lossless condition.
5.1. New model for error analysis
Fig.6(a) illustrates a multiplier in the DWT circuit. An input value s has
Just after the multiplication, the signal is rounded to
where cs is the ideal output. This conventional model, illustrated in Fig.6(b), describes the coefficient error as multiplicative to the signal s [13-15], and the signal error
Unlike these existing approaches, as illustrated in Fig.6(c), we describe the coefficient error e'' as
From Eq.(15), we utilize the fact that
Note that the parameter
where its proof is given in appendix.
Benefitting from this inequality, it becomes possible to consider mutual effect of the coefficient error and the signal error.
Inside the forward DWT, the error e is propagated and added up with other errors from other multipliers. When its maximum absolute value is less than, the total error is nullified by the rounding at the final output of the forward DWT. In this article, we utilize this nullification of errors at output of the DWT to derive a condition on word length such that the DC lossless defined by Eq.(33) and (34) is satisfied.
5.2. DC equivalent circuit
When the input signal is restricted to a DC signal,
In Fig.7(a) , a scalar
Similarly, for the backward transform in Fig.7(b), errors are described as
Similarly to Eq.(42), these errors are described with the parameters pi and
for a given word length
5.3. Nullification of accumulated errors
In Fig.7(a), the unified errors in Eq.(46) are propagated and accumulated inside the circuit. When the accumulated errors are nullified by the rounding at output of the forward transform, Eq.(33) is satisfied. In the figure,
It is described with the unified error matrices
Similarly, output values
When the DWT is DC lossless, output values of the transforms are
Using this equation, the accumulated errors are defined as
Applying Eq.(12), it becomes clear that when the conditions;
are satisfied, the accumulated errors are nullified by the rounding operations at the final output of each of the forward transform and the backward transform.
6. Derived conditions on word length for the DC lossless DWT
This chapter summarizes the new condition derived from the basic properties in chapter 2, and other related condition derived from a conventional approach.
6.1. Critical condition on word length
Finally, we derive the condition on word length of coefficients and signals such that Eq.(54) is satisfied. Since the unified errors in
into Eq.(54). This is the condition we derived based on the new model described in section 5.1. We investigate the fraction part
6.2. Sufficient condition on word length
where denotes a column vector whose component is a sum of absolute value of all components in each row. Substituting coefficients of the 9-7 DWT  into Eq.(56), we have
and GE is the lower bound. This means a sufficient condition for the DC lossless. Since it is too strict, the word length under this condition is redundant. Unlike this sufficient condition, our critical condition given as Eq.(54) under Eq.(55) determines the word length minimum and necessary for the DC lossless.
7. Simulation results
This chapter verifies theoretically derived conditions, and clarifies the minimum word length of the DC lossless DWT.
7.1. Word length under the sufficient condition
Utilizing the sufficient condition in section 6.2, we calculated the optimized word length under the cost function defined as
and it is also confirmed by the figure. It guarantees the DC lossless, however the condition is too strict. Therefore the word length is redundant and there is room for further reduction.
7.2. Word length under the critical condition
In Fig.8, a cross "" indicates a pair (
7.3. Word length for a specific value
Fig.9(a) and Fig.9(b) illustrate the word length under the conditions for the black value "16" and the white value "235" respectively. These specific values are utilized in white balancing of an 8-bit video system . For example, (FS, FC) is reduced from (4, 12) in Fig.8(a) to (2, 9) in Fig.9(a) for Ex.1. Table 3 summarizes the minimum word length for these specific input DC values . It is observed that the word length can be reduced by limiting input DC signals to a specific value. Fig.10 indicates the minimum word length FC of coefficients for an input value x at a given word length FS of signals. This is an example at (
7.4. Optimum word length assignment
Since we described tolerance for the unified errors as parameters pi and qi in Eq.(46) and (47), it becomes possible to simultaneously control both of word length of signals and that of coefficients. Table 4 summarizes these parameters for an input value 16 and the word length of signals at
Table 5 summarizes results of this optimum word length assignment for the forward transform. Comparing to table 3, it is observed that word length of coefficients is reduced from 9.00 [bit] to 6.17 [bit] on average for an input value
Introducing a new model which unifies the coefficient error and the signal error, and utilizing the nullification of the accumulated errors, this article theoretically derived a condition on word length of signals and coefficients such that the 9-7 DWT of JPEG 2000 becomes lossless for a DC input signal. It was confirmed that the minimum word length derived by the newly introduced 'critical' condition was shorter than that determined by a conventionally well known 'sufficient' condition. It was also confirmed that the DWT under the condition does not have the checker board for a DC signal. Analysis in this article contributes to build a low complexity DC lossless DWT.
Proof of Eq.(43)
According to Eq.(13), each terms in the right hand side are described as
and finally we have Eq.(43) as