Condition on Word Length of Signals and Coefficients for DC Lossless Property of DWT

1. Introduction

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 [1], 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 [7]. 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 [8].

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 [9]. It also brings about DC leakage which decreases the coding gain of a transform [10].

The regularity has been structurally guaranteed for a two channel quadrature mirror filter bank (QMF) [9] and the DCT [10] 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 [11].

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 x is expressed with a fixed point binary expression as

$$x={\displaystyle \sum _{p=-F}^{I-1}{b}_p{2}_{}^p},b_p\in \left\{\mathrm{0,1}\right\},I\ge \mathrm{1,}F\ge \mathrm{0,}I\in Z,F\in Z$$E1

where b_p, p$$\in$${-F,$$\cdots$$ ,I-1), is a set of binary digit for a value x. It has I bit integer part including one sign bit and F bit fraction part. Hereinafter, F is referred to as word length of a value x. This F bit value x has a range expressed as

$$x\in [-2^{I-1}{\mathrm{,2}}^{I-1}-2^{-F}]\in [-2^{I-1}{\mathrm{,2}}^{I-1})$$E2

.

For example, in case of I=1 and F=2, the maximum value is x=0.75 for [b₀ b_-1 b_-2]=[0 1 1], and the minimum value is x=-1.00 for [b₀ b_-1 b_-2]=[1 0 0].

When an F bit signal value is multiplied with a coefficient value, in a convolution of a filtering process in DWT for example, a resulting signal value has longer word length than its original value. Therefore it is rounded to F bit again. So far there are various types of rounding operations [16]. In this article, we deal with the rounding operation defined by

$$R_0[x]=\lfloor x+2^{-1}\rfloor or{R}_0[x]=x\text{'}-(x{\text{'}}^{}{\mathrm{mod}}^{}1)forx\text{'}=x+2^{-1}$$E3

as an example. This rounding operation generates a rounding error. We denote it as

$${\Delta }_0[x]=x-R_0[x]or{\Delta }_0[x]=\left\{{(x+2^{-1})}^{}{\mathrm{mod}}^{}1\right\}-2^{-1}$$E4

.

Expanding these expressions to an F bit case, we can define the rounding operation and the rounding error as

$$\{\begin{array}{l}{R}_F[x]=R_0[x{2}^F]2^{-F}\\ {\Delta }_F[x]={\Delta }_0[x{2}^F]2^{-F}\end{array}$$E5

for an F bit word length implementation case.

Fig.1 illustrates rounding operations expressed by these equations. The term R_F[x] is a quotient, and Δ_F[x] (= x - R_F[x]) is related to a remainder. The former is an actual value treated in a digital system under a finite word length implementation, and the latter is a rounding error. We are now trying to develop an algebraic expression approach to exactly trace a practical value and a rounding error in a convolution processing inside a DWT.

Fig. 1. Definition of the rounding operation and the rounding error. (a) An integer implementation case. (b) An F bit word length implementation case.

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 x and y. Resulting value is R_F[x+y] and its rounding error is Δ_F[x+y]. A multiplication result R_F[xy] and its error Δ_F[xy] should be also investigated.

First of all, let's derive basic properties of the rounding operation starting with an obvious property;

$$y\in Z\to R_0[x+y]=R_0[x]+yforx\in R$$E6

.

It represents that only a real number x can be rounded if y is an integer to calculate a rounded value of x+y. In this case, its rounding error becomes

$$y\in Z\to {\Delta }_0[x+y]={\Delta }_0[x]forx\in R$$E7

.

It suggests that an integer y can be ignored when only the rounding error is considered in an analysis. There is another obvious property;

$$R_0[x]=0\leftrightarrow x\in [-2^{-1}{\mathrm{,2}}^{-1})$$E8

.

Since the range of a rounding error is

$${\Delta }_0[x]\in [-2^{-1}{\mathrm{,2}}^{-1})$$E9

,

we can add two more identities;

$$\{\begin{array}{l}{R}_0\left[{\Delta }_0[x]\right]=\mathrm{0,}\\ {\Delta }_0\left[{\Delta }_0[x]\right]={\Delta }_0[x].\end{array}$$E10

The equations above for F=0 can be straightforwardly extended to an F≠0 case as follows.

$$y{2}^F\in Z\to \{\begin{array}{l}{R}_F[x+y]=R_F[x]+y\\ {\Delta }_F[x+y]={\Delta }_F[x]\end{array}forx\in R$$E11

$$R_F[x]=0\leftrightarrow x\in [-2^{-1-F}{\mathrm{,2}}^{-1-F})$$E12

$${\Delta }_F[x]\in [-2^{-1-F}{\mathrm{,2}}^{-1-F})$$E13

$$\{\begin{array}{l}{R}_F\left[{\Delta }_F[x]\right]=0\\ {\Delta }_F\left[{\Delta }_F[x]\right]={\Delta }_F[x]\end{array}$$E14

In addition, Eq.(12) can be extended to a more general case with an integer n as

$$R_F[x]=n{2}^{-F}\leftrightarrow x{2}^F{\in }_{}^{{}^{{}^{}}}[-2^{-1}+n,2^{-1}+n)forn\in Z$$E15

.

2.3. Basic formulas of the rounding operation

Utilizing the basic properties in Eqs.(11)-(14), we can derive an addition formula and a multiplication formula of a practical value (quotient) of the rounding operation as follows.

Addition formula

$$R_F[x+y]=R_F[x]+R_F\left[y+{\Delta }_F[x]\right]forx,y\in R$$E16

Proof:

$$\begin{array}{l}{R}_F{\left[x+y\right]}^{}\\ =R_F\left[R_F[x]+{\Delta }_F[x]+y\right]\leftarrow (4)\\ =R_F[x]+R_F\left[{\Delta }_F[x]+y\right]\leftarrow (11)\end{array}$$

Q.E.D.

Multiplication formula

$$R_F[xy]=R_F\left[x{R}_F[y]\right]+R_F{\left[x{\Delta }_F[y]+{\Delta }_F{\left[x{R}_F[y]\right]}^{}\right]}^{}forx,y\in R$$E17

Proof:

$$\begin{array}{l}{R}_F[xy]\\ =R_F\left[x{\Delta }_F[y]+x{R}_F[y]\right]\leftarrow (4)\\ =R_F\left[x{\Delta }_F[y]+{\Delta }_F\left[x{R}_F[y]\right]+R_F{\left[x{R}_F[y]\right]}^{}\right]\leftarrow (4)\\ =R_F\left[x{\Delta }_F[y]+{\Delta }_F{\left[x{R}_F[y]\right]}^{}\right]+R_F\left[x{R}_F[y]\right]\leftarrow (11)\end{array}$$

Q.E.D.

Formulas for a rounding error (remainder) can be also derived as

$$\{\begin{array}{c}{\Delta }_F[x+y]={\Delta }_F\left[{\Delta }_F[x]+{\Delta }_F[y]\right]\\ {\Delta }_F[xy]={\Delta }_F{\left[{\Delta }_F[x]R_F[y]+R_F[x]{\Delta }_F[y]+{\Delta }_F[x]{\Delta }_F[y]\right]}^{}\end{array}$$E18

for real numbers x and y. These formulas have following variations;

Addition formula

$$y{2}^F\in Z\to \{\begin{array}{l}{R}_F[x+y]=R_F[x]+y\\ R_F[x+y]=-{\Delta }_F[x]+x+y\\ {\Delta }_F[x+y]={\Delta }_F[x]\end{array}$$E19

Multiplication formula

$$y{2}^F\in Z\to \{\begin{array}{l}{R}_F[xy]=R_F\left[{\Delta }_F[x]y\right]+R_F[x]y\\ R_F[xy]=-{\Delta }_F\left[{\Delta }_F[x]y\right]+xy\\ {\Delta }_F[xy]={\Delta }_F\left[{\Delta }_F[x]y\right]\end{array}$$E20

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 [17].

$$R_{F_2}{\left[x{R}_{F_1}[y]\right]}^{}=R_{F_2}[xy]+R_{F_2}{\left[-x{\Delta }_{F_1}[y]+{\Delta }_{F_2}[xy]\right]}^{}$$E21

Proof:

$$\begin{array}{l}{R}_{F_2}{\left[x{R}_{F_1}[y]\right]}^{}\\ =R_{0^{}}\left[-x{\Delta }_{F_1}[y]2^{F_2}+xy{2}^{F_2}\right]2^{-F_2}\\ =R_{0^{}}\left[-x{\Delta }_{F_1}[y]2^{F_2}+{\Delta }_0[xy{2}^{F_2}]+R_0[xy{2}^{F_2}]\right]2^{-F_2}\\ =R_{0^{}}\left[-x{\Delta }_{F_1}[y]2^{F_2}+{\Delta }_0[xy{2}^{F_2}]\right]2^{-F_2}+R_0{[}^x{2}^{-F_2}\\ =R_{F_2}{\left[-x{\Delta }_{F_1}[y]+{\Delta }_{F_2}[xy]\right]}^{}+R_{F_2}[xy]\end{array}$$

Q.E.D.

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 x with a coefficient value h. As illustrated in Fig.2(a), this processing maps an input value x to an output value y^* with an ideal (infinite word length) coefficient value h. Note that x has F bit word length. Output value of the multiplication is also rounded to F bit (y^* has F bit word length). In implementation, as illustrated in Fig.2(b) , a coefficient value h is also rounded to W bit word length (h' has W bit word length). We aim at finding the minimum word length W of a coefficient h' such that the mapping is invariant (y -y^* =0).

Figure 1.

Scaling of a signal value x with a coefficient value h. (a) This processing maps x to y^* with h under a given F. (b) A mapped y should be equal to y^* even though h is rounded to h'.

In case of Fig.2(b), an input value x is multiplied by a rounded value R_W[h] (=h') of a given coefficient h. The result R_W[h]x is rounded to R_F[R_W[h]x] (=y). When it is the same as R_F[hx] (=y^* ), the mapping of x is invariant. It means that effect of rounding of h is nullified. This mapping invariant case is expressed as

$$E_m=0\begin{array}{ccc}& for& \end{array}\{\begin{array}{l}{E}_m=R_F\left[R_W[h]x\right]-R_F[hx]\\ R_W[h]=h-{\Delta }_W[h]\end{array}$$E22

.

From the basic properties, the mapping invariant condition is derived as

$${\Delta }_W[h]x-{\Delta }_F[hx]\in {\left(-2^{-1-F},2^{-1-F}\right]}^{}$$E23

.

Proof:

$$\begin{array}{l}{R}_F\left[R_W[h]x\right]-R_F[hx]\\ =R_F{\left[hx-{\Delta }_W[h]x\right]}^{}-R_F[hx]\\ =R_F{\left[{\Delta }_F[hx]-{\Delta }_W[h]x\right]}^{}+R_F[hx]-R_F[hx]\\ =R_F{\left[{\Delta }_F[hx]-{\Delta }_W[h]x\right]}^{}\\ =0\end{array}$$

$$\begin{array}{cc}\therefore & \end{array}{\Delta }_F[hx]-{\Delta }_W[h]x\in {\left[-2^{-1-F},2^{-1-F}\right)}^{}$$

Q.E.D.

The Eq.(23) also means

$$\{\begin{array}{l}{\Delta }_W[h]\in \left(\frac{{\Delta }_F[hx]-2^{-1}}{x},\frac{{\Delta }_F[hx]+2^{-1}}{x}\right]\begin{array}{cc},& x>0\end{array}\\ {\Delta }_W[h]\in \left[\frac{{\Delta }_F[hx]+2^{-1}}{x},\frac{{\Delta }_F[hx]-2^{-1}}{x}\right)\begin{array}{cc},& x<0\end{array}\end{array}$$E24

which gives tolerance to the rounding error of a coefficient [8]. This is the mapping invariant condition on word length W of a coefficient under a given word length F of signals. It represents exact (not approximated) behavior of rounding errors.

Unlike the condition above, a sufficient condition can be derived by substituting the upper bound of errors and signals;

$$\left|{\Delta }_W[h]\right|<2^{-1-W},\left|{\Delta }_F[hx]\right|<2^{-1-F},\left|x\right|<2^{I-1}$$E25

,

to Eq.(23). It results in the condition described as

$$W>F+I-1$$E26

.

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 F of signals.

3.2. Lossless condition on a scaling pair

Fig.3 illustrates a pair of two multipliers. In Fig.3(a), an input signal x has F₂ bit word length. It is scaled with a coefficient h₁, and its output value y is rounded to F₁ bit. It is re-scaled with a coefficient h₂ (=1/h₁), and its final output value w is rounded to F₂ bit. This scheme is embedded in a forward transform and a backward transform of DWT for example. It is required to regain w exactly the same as x, under a given word length set of F₁ and F₂. Note that rounding errors due to finite word length expression of coefficients h₁ and h₂ can be ignored as far as the mapping invariant condition is satisfied.

Figure 2.

Scaling pair has two coefficients h₁ and h₂ (=1/h₁). (a) Output w is exactly the same as its original x. (b) This lossless property is guaranteed under a condition on F₁ and F₂.

We apply the formulas and the properties to derive the condition on F₁ and F₂. The lossless case in Fig.3(b) is described as

$$E_p=0\begin{array}{ccc}& for& \end{array}\{\begin{array}{l}{E}_p=R_{F_2}{\left[h_2{R}_{F_1}[h_{1}x]\right]}^{}-x\\ h_1{h}_2=1\end{array}$$E27

.

From the basic properties, the lossless condition on a scaling pair is derived as

$$h_2{\Delta }_{F_1}[h_{1}x]\in {\left(-2^{-1-F_2}{,}^{}{2}^{-1-F_2}\right]}^{}$$E32

.

Proof:

$$\begin{array}{l}{R}_{F_2}{\left[h_2{R}_{F_1}[h_{1}x]\right]}^{}-x\\ =R_0{\left[-h_2{\Delta }_{F_1}[h_{1}x]2^{F_2}+h_2{h}_{1}x{2}^{F_2}\right]}^{}{2}^{-F_2}-x\\ =R_0{\left[-h_2{\Delta }_{F_1}[h_{1}x]2^{F_2}\right]}^{}{2}^{-F_2}+x-x\\ =R_{F_2}{\left[-h_2{\Delta }_{F_1}[h_{1}x]\right]}^{}\\ =0\end{array}$$

$$\therefore -h_2{\Delta }_{F_1}[h_{1}x]\in {\left[-2^{-1-F_2}{,}^{}{2}^{-1-F_2}\right)}^{}$$

Q.E.D.

This condition determines the word length F₁ and F₂ of signals for an input value x. It represents exact condition such that total accumulated rounding error is nullified by the rounding just after the final multiplier with h₂. As a result, the original value x is recovered as the final output without any loss.

Unlike the exact condition above, a sufficient condition can be derived by analyzing the upper bound as follows.

$$\left|h_2{\Delta }_{F_1}{[h_{1}x]}^{}\right|<\left|h_2{}^{}\right|2^{-1-F_1}<2^{-1-F_2}$$E29

As a results, when the sufficient condition given by

$$F_1>F_2+{\log }_2\left|h_2\right|$$E30

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 [1]. The forward transform in Fig.4(a) decomposes an input signal x(n), n$$\in$$N, N={n | 1,2, $$\cdots$$, L} into band signals y₁(m) and y₂(m), m$$\in$$M, M={m | 1,2, $$\cdots$$, L/2}. The backward transform in Fig.4(b) reconstructs the signal w(n) from the band signals. In the figure, z^-1 and ↓2 indicate the delay and the down sampler respectively.

Figure 3.

The irreversible 9-7 DWT of the JPEG 2000 standard.

The multiplier coefficients c_i, i$$\in$$I, I={i | 1,2, $$\cdots$$, 6} are designed under the word length long enough to be treated as real numbers. When the DWT is implemented, coefficient values are rounded to the length as short as possible to minimize total hardware complexity. Similarly, signal values are also rounded. In the figure, fraction part of each signal is shortened to F_S, F_B or F_X [bit] by a rounding operation illustrated as a circle.

Denoting the integer part as I_S [bit], total word length W_S [bit] of a signal s is defined as

$$W_S=I_S+F_S+1$$E31

including 1 [bit] for the sign part. Similarly, total word length W_C [bit] of a coefficient c is defined as

$$W_C=I_C+F_C+1$$E32

.

In Fig.4, fraction part of the input signal x(n) is given as F_X [bit]. Inside the DWT, fraction part of the signals are rounded to F_S [bit] just after each of all the multiplications with c_i, i$$\in$$I. Output signals from the forward and backward transforms are rounded to F_B [bit] and F_X [bit] respectively. Note that we do not truncate integer part of signals and that of coefficients. We are determining F_S and F_C such that the DC lossless property is satisfied.

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:

$$\forall n\in \text{N},\forall m\in \text{M}\left(x(n)=d\to y_1(m)=d\wedge y_2(m)=0\right)$$E33

$$\forall n\in \text{N},\forall m\in \text{M}\left(y_1(m)=d\wedge y_2(m)=0\to w(n)=d\right)$$E34

for a given constant value d with F_X [bit] fraction part. When the proposition in Eq.(33) holds, the DWT has no DC leakage for the DC input signal with value d. Similarly, when the proposition in Eq.(34) is true, the reconstructed signal w(n) contains no checker board artifact for the DC input signal. In the following chapters, we investigate the minimum fraction part of signals F_S [bit] which guarantees the DC lossless for given F_X and F_B [bit]. We also investigate the minimum fraction part $$F_{C_i}$$ [bit] of a coefficient c_i, i$$\in$$I with flexibility of trading off the signal error and the coefficient error.

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.

Figure 4.

The DC lossless property is useful for white balancing in a video system.

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) [9]. 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 [20]. The regularity was structurally guaranteed for a biorthogonal linear phase filter bank [21,22] and the DCT [10] 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 F_S [bit] fraction part and multiplied by a coefficient c'. The coefficient is originally designed as a real number c. It is rounded to a rational number c' in implementation. It produces the coefficient error:

$$\Delta c=c-c\text{'}$$E35

.

Just after the multiplication, the signal is rounded to s' with F_S [bit] fraction part as

$$s\text{'}=R_{F_S}[c\text{'}s]=c\text{'}s+e\text{'}$$E36

where e' is the signal error. From Eq.(35) and (36), the final output becomes

$$s\text{'}=cs-\Delta cs+e\text{'}$$E42

.

where cs is the ideal output. This conventional model, illustrated in Fig.6(b), describes the coefficient error $$\Delta c$$ as multiplicative to the signal s [13-15], and the signal error e' as additive [7,12]. In addition, these errors are treated independently as mutually uncorrelated noises.

Unlike these existing approaches, as illustrated in Fig.6(c), we describe the coefficient error e'' as

$$\{\begin{array}{l}s\text{'}=R_{F_S}[cs]+e\text{'}\text{'},\\ e\text{'}\text{'}=R_{F_S}\left[{\Delta }_{F_S}[cs]-{\Delta }_{F_C}[c]s\right].\end{array}$$E38

From Eq.(15), we utilize the fact that e'' is observed as a 'particle';

$$e\text{'}\text{'}\cdot 2^{F_S}=p$$E39

where p is an integer. Given the tolerable maximum to an integer p, word length of the coefficient c can be controlled independently of other coefficients in other sections inside the DWT. Furthermore, denoting the signal error as e' similarly to Eq.(36), the output value is described as

$$\{\begin{array}{l}s\text{'}=cs+e\\ e=e\text{'}+e\text{'}\text{'}\end{array}$$E40

where

$$\{\begin{array}{l}e\text{'}=-{\Delta }_{F_S}[cs]\\ e\text{'}\text{'}=R_{F_S}{\left[{\Delta }_{F_S}[cs]-{\Delta }_{F_C}[c]s^{}\right]}^{}\end{array}$$E41

as illustrated in Fig.6(d). In this new model, both of the coefficient error e'' and the signal error e' are unified to the error e. Utilizing Eqs.(13) and (15), its absolute value is limited to

$$\left|e\right|\le (p+2^{-1})2^{-F_S}$$E42

.

Note that the parameter p to control word length of a coefficient c is included in this equation. It is equivalent to

$$2^{-F_C+F_S+I_S-1}\le p$$E43

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.

Figure 5.

A multiplier in the DWT and its models for error analysis.

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$$2^{-1-F_B}$$, 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, x(n) can be described as a scalar x independent of n. The delay z^-1 can be treated as 1 and (1+z^-1) can be replaced by 2. Therefore, instead of the circuits in Fig.4, we can use their equivalent circuits for a DC input signal in Fig.7 to derive the condition.

In Fig.7(a) , a scalar x with F_X [bit] fraction part is multiplied by the rational numbers c_i, i$$\in$$I and rounded to F_S [bit]. Finally, the signals are rounded to F_B [bit] at its output to produce two scalars [y₁ y₂]. The unified errors inside the circuit are described as

$$e_i=e_i\text{'}+e_i\text{'}{\text{'}}^{}{,}^{}i\in \text{I}$$E44

where

$$\{\begin{array}{l}{e}_i\text{'}=-{\Delta }_{F_S}{[}_{c_i}^{s_i}\\ e_i\text{'}\text{'}=R_{F_S}{\left[{\Delta }_{F_S}[c_i{s}_i]-{\Delta }_{F_C}[c_i]s_i\right]}^{}\end{array}$$

$$\left[\begin{array}{ccc}{s}_1& s_3& s_5\\ s_2& s_4& s_6\end{array}\right]=\left[\begin{array}{ccc}2x& 2(x+s{\text{'}}_2)& s_4\\ 2(x+s{\text{'}}_1)& 2(s_2+s{\text{'}}_3)& s_3+s{\text{'}}_4\end{array}\right]$$

$$s{\text{'}}_i=c_i{s}_i+e_i=R_{F_S}[c_i{s}_i]$$

.

Similarly, for the backward transform in Fig.7(b), errors are described as

$$f_i=f_i\text{'}+f_i\text{'}{\text{'}}^{}{,}^{}i\in \text{I}$$E45

where

$$\{\begin{array}{l}{f}_i\text{'}=-{\Delta }_{F_S}{[}_{c_i}^{t_i}\\ f_i\text{'}\text{'}=R_{F_S}{\left[{\Delta }_{F_S}[c_i{t}_i]-{\Delta }_{F_C}[c_i]t_i\right]}^{}\end{array}$$

$$\left[\begin{array}{ccc}{t}_1& t_3& t_5\\ t_2& t_4& t_6\end{array}\right]=\left[\begin{array}{ccc}2(t_3-t{\text{'}}_2)& 2(t{\text{'}}_5-t{\text{'}}_4)& y_1\\ 2(t_4-t{\text{'}}_3)& 2t{\text{'}}_6& y_2\end{array}\right]$$

$$t{\text{'}}_i=c_i{t}_i+f_i=R_{F_S}[c_i{t}_i]$$E52

.

Similarly to Eq.(42), these errors are described with the parameters p_i and q_i to control word length of coefficients as

$$\left|e_i\right|\le (p_i+2^{-1})2^{-F_S},i\in \text{I}$$E46

$$\left|f_i\right|\le (q_i+2^{-1})2^{-F_S},i\in \text{I}$$E47

for a given word length F_s [bit] of signals.

Figure 6.

Equivalent circuits of the DWT for a DC input signal.

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, Y₁₂=[y₁ y₂]^T is described as

$$\begin{array}{l}{Y}_{12}=R_{F_B}{[{}_{{}_{{}_{}^{}}}^{{}^{}}{I}_U{e}_6+I_L{e}_5+K({}_{}^{{}^{}}{I}_U{e}_4+H_4({}_{}^{}{I}_L{e}_3}^{}\\ {+H_3{\left({}^{}{I}_U{e}_2+H_2\left(I_L{e}_1+H_1{I}_{UL}x\right)\right)}^{}))}^{}]\end{array}$$E48

where

$$I_U={[\begin{array}{cc}1& 0\end{array}]}^T{,}^{}{I}_L={[\begin{array}{cc}0& 1\end{array}]}^T{,}^{}{I}_{UL}=I_U+I_L$$

$$H_{i\in \left\{\mathrm{1,3}\right\}}=\left[\begin{array}{cc}1& 0\\ 2c_i& 1\end{array}\right]{,}^{}{H}_{j\in \left\{\mathrm{2,4}\right\}}=\left[\begin{array}{cc}1& 2c_j\\ 0& 1\end{array}\right]{,}^{}K=\left[\begin{array}{cc}{c}_6& 0\\ 0& c_5\end{array}\right].$$

It is described with the unified error matrices E₁ and E₂ as

$$Y_{12}=R_{F_B}{\left[(H_{e1}{E}_1+H_{e2}{E}_2)+K{H}_{4321}x\right]}^{}$$E49

where

$$\{\begin{array}{l}{H}_{e1}=\left[\begin{array}{ccc}{I}_U& K{I}_U& K{H}_{43}{I}_U\end{array}\right]\\ H_{e2}=\left[\begin{array}{ccc}{I}_L& K{H}_4{I}_L& K{H}_{432}{I}_L\end{array}\right]\\ H_{43\cdots }^{}=H_4^{}{H}_3^{}\cdots \end{array}$$,

and

$$\{\begin{array}{l}{E}_1={[}^{\begin{array}{ccc}{e}_6& e_4& e_2\end{array}}\\ E_2={[}^{\begin{array}{ccc}{e}_5& e_3& e_1\end{array}}.\end{array}$$

Similarly, output values W₁₂=[w₁ w₂]^T from the backward transform in Fig.7(b) are

$$W_{12}=R_{F_X}[{}^{}(H_{e3}{E}_3+H_{e4}{E}_4)+{{(K{H}_{4321})}^{-1}{Y}_{12}]}^{}$$E50

where

$$\{\begin{array}{l}{H}_{e3}=-[\begin{array}{ccc}{H}_1^{-1}{I}_U& H_{123}^{-1}{I}_U& H_{1234}^{-1}{I}_U\end{array}]\\ H_{e4}=-[\begin{array}{ccc}{I}_L& H_{12}^{-1}{I}_L& H_{1234}^{-1}{I}_L\end{array}]\\ H_{12\cdots }^{-1}=H_1^{-1}{H}_2^{-1}\cdots \end{array}$$

and

$$\{\begin{array}{l}{E}_3={[}^{\begin{array}{ccc}{f}_2& f_4& f_5\end{array}}\\ E_4={[}^{\begin{array}{ccc}{f}_1& f_3& f_6\end{array}}.\end{array}$$

When the DWT is DC lossless, output values of the transforms are

$$\left[\begin{array}{c}{\widehat{Y}}_{12}\\ {\widehat{W}}_{12}\end{array}\right]=\left[\begin{array}{c}K{H}_{4321}x\\ {(K{H}_{4321})}^{-1}{\widehat{X}}_{12}\end{array}\right]=\left[\begin{array}{c}{I}_U\\ I_{UL}\end{array}\right]x.$$E51

Using this equation, the accumulated errors are defined as

$$\left[\begin{array}{c}{E}_{y12}\\ E_{w12}\end{array}\right]=\left[\begin{array}{c}{Y}_{12}\\ W_{12}\end{array}\right]-\left[\begin{array}{c}{\widehat{Y}}_{12}\\ {\widehat{W}}_{12}\end{array}\right].$$E52

Substituting Eqs.(49), (50), (51) and using the property in Eq.(6), we have

$$\left[\begin{array}{c}{E}_{y12}\\ E_{w12}\end{array}\right]=\left[\begin{array}{c}{R}_{F_B}{\left[(H_{e1}{E}_1+H_{e2}{E}_2)\right]}^{}\\ R_{F_X}{\left[(H_{e3}{E}_3+H_{e4}{E}_4)\right]}^{}\end{array}\right].$$E53

Applying Eq.(12), it becomes clear that when the conditions;

$$\{\begin{array}{l}\left|H_{e1}{E}_1+H_{e2}{E}_2\right|\le I_{UL}{2}^{-1-F_B}\\ \left|H_{e3}{E}_3+H_{e4}{E}_4\right|\le I_{UL}{2}^{-1-F_X}\end{array}$$E54

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 E₁, E₂, E₃ and E₄ have the maximum in Eqs.(46) and (47) described with the parameters p_i and q_i, the DC lossless condition is also described with the parameters by substituting

$$\{\begin{array}{l}{E}_1=\left({[\begin{array}{ccc}{p}_6& p_4& p_2\end{array}]}^T+I_3\cdot 2^{-1}\right)2^{-F_S}\\ E_2=\left({[\begin{array}{ccc}{p}_5& p_3& p_1\end{array}]}^T+I_3\cdot 2^{-1}\right)2^{-F_S}\\ E_3=\left({[\begin{array}{ccc}{q}_2& q_4& q_5\end{array}]}^T+I_3\cdot 2^{-1}\right)2^{-F_S}\\ E_4=\left({[\begin{array}{ccc}{q}_1& q_3& q_6\end{array}]}^T+I_3\cdot 2^{-1}\right)2^{-F_S}\end{array}$$E55

for

$$I_3={[\begin{array}{ccc}1& 1& 1\end{array}]}^T$$

into Eq.(54). This is the condition we derived based on the new model described in section 5.1. We investigate the fraction part F_Ci [bit] of a coefficient c_i, i$$\in$$I as the minimum word length under the condition for a DC value x at the word length F_s [bit] of signals.

6.2. Sufficient condition on word length

As an example, in case of all the parameter in Eq.(55) are given as p_i = q_i = p and F_Ci = F_C for $$\forall$$i$$\in$$I, the condition in Eq.(54) becomes

$$\{\begin{array}{l}\left({\Vert H_{e1}\Vert }_{L^1}+{\Vert H_{e2}\Vert }_{L^1}\right)\cdot 2^{-F_S}(p+2^{-1})\le I_{UL}{2}^{-1-F_B}\\ \left({\Vert H_{e3}\Vert }_{L^1}+{\Vert H_{e4}\Vert }_{L^1}\right)\cdot 2^{-F_S}(p+2^{-1})\le I_{UL}{2}^{-1-F_X}\end{array}$$E56

where $${\Vert H\Vert }_{L^1}$$ 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 [1] into Eq.(56), we have

$$\{\begin{array}{l}p\le 2^{-1+F_S-G_E}-2^{-1}\\ G_E=2.66[\text{bit}]\end{array}$$E57

for F_X = F_B = 0. As a result, the DC lossless condition on the word length is given as

$$-{\log }_2(2^{-\Delta W_C}+2^{-\Delta W_S})\ge G_E$$E58

where

$$[\begin{array}{cc}\Delta W_C& \Delta W_S\end{array}]=[F_C-\begin{array}{cc}{I}_S& F_S\end{array}]$$

and G_E 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 J=2^-1(F_C +F_S). The cost J is minimized for three examples. Ex.1 trades the word length between F_C and F_S, namely F_C + F_S = constant. Ex.2 and Ex.3 are F_C = F_S and W_C = W_S respectively. Results are summarized in table 1. Table 2 summarizes word length of signals and coefficients for an 8 bit system with W_x=8 (I_x=7 and F_x=0). Ex.1 requires (F_S, F_C)=(4, 12) [bit] for signals and coefficients respectively. Ex.2 and Ex.3 require F_S =F_C =11 [bit] and W_S =W_C =14 [bit] respectively. The condition in Eq.(58) is plotted as a solid line in Fig.8. According to the sufficient condition, it is impossible to be DC lossless for

$$\{\begin{array}{l}{F}_C\le G_E+I_S\\ F_S\le G_E\end{array}$$E59

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.

Table 1.

Theoretically derived word length under the sufficient condition for DC lossless. F_S and F_C denote fraction part of signals and coefficients. I_S and I_C denote integer part of signals and coefficients. W_S=I_S+F_S+1, W_C=I_C+F_C+1, J is a cost function.

Table 2.

Word length calculated with equations in table 1 for W_x=8 [bit].

7.2. Word length under the critical condition

In Fig.8, a cross "$$\times$$" indicates a pair (F_S, F_C) which satisfies the critical condition in section 6.1 for any 8 bit integer x with W_X=I_X=8 and F_X=0. Here in after, we denote an input DC value to a video system as

$$x_{in}=x-2^{I_X-1}$$E60

where x is an input value to the DC equivalent circuit in Fig.7. The minimum of F_C for each F_S is indicated as a broken line. It is clear that the word length derived by the critical condition is shorter than that determined by the sufficient condition. For example in Fig.8(a), the fraction part F_S (= F_C) is reduced from 11 [bit] to 9 [bit] for Ex.2. The word length is not shortened for Ex.1 and Ex.3. In case of Fig.8(b), F_S (= F_C) is reduced from 13 [bit] to 12 [bit] for Ex.2. (F_S, F_C) is reduced from (14, 4) to (13, 3) or (12, 4) for Ex.1. W_S (= W_C) is reduced from 16 [bit] to 15 [bit] for Ex.3. It is confirmed that the word length is shortened due to the analysis in this article.

Figure 8.

Word length under the two conditions. "$$\times$$" indicates (F_S, F_C) such that the DWT becomes DC lossless.

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 [19]. For example, (F_S, F_C) 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 [23]. 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 F_C of coefficients for an input value x at a given word length F_S of signals. This is an example at (F_S, W_X)=(3, 8). The sufficient condition gives the same word length for any of input values. Unlike this conventional statistical analysis, our analysis gives the minimum word length shorter than that determined by the sufficient condition for each of input DC values.

Figure 9.

Word length under the two conditions for a specific value used in white balancing.

Figure 10.

The minimum word length of coefficients for each of input DC values at (F_S, W_X)=(3, 8). According to the sufficient condition, the word length is too long.

Table 3.

The minimum word length for a specific value for white balancing of a video system.

7.4. Optimum word length assignment

Since we described tolerance for the unified errors as parameters p_i and q_i 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 F_S=2 [bit] as an example. It indicates that [p₁ p₂ $$\cdots$$ p₆] in Eq.(46) are [0 0 0 0 0 1] for the word length of coefficients at F_C=9 [bit]. In this case, all the coefficients c_i in the forward transform have the same length. It is worth paying attention to the fact that the parameter p₁ is the same for F_C=9, 8 and 7 [bit] for example. It means that word length of the coefficient c₁ can be reduced from 9 to 7 [bit] without any influence to the errors. Therefore, word length [F_C1 F_C2$$\cdots$$F_C6] of coefficients [c₁ c₂ $$\cdots$$ c₆] can be reduced from [9 9 9 9 9 9] to [7 9 7 4 6 4] according to the table.

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 x_in=16. Table 6 summarizes results for the backward transform. In this case, the word length is furthermore shortened. It is observed that c₆ and c₄ can be omitted since y₂ is equal to zero under the DC lossless. Fig.11 illustrates image signals reconstructed by the DWT which does not satisfy the DC lossless condition. It demonstrates the checker board artifact for reference. It is confirmed that total word length is furthermore shortened utilizing the tolerance parameters p_i and q_i introduced in this article.

Table 4.

Tolerance parameters in Eq.(46) and (47) for x_in=16 and F_S=2 as an example.

Table 5.

The minimum word length of coefficients in the forward transform for a specific values x_in for a given word length of signals F_S.

Table 6.

The minimum word length of coefficients in the backward transform for a specific values x_in for a given word length of signals F_S.

Figure 11.

Example of reconstructed images for 128² pixel DC input image with x=10. Intensity is multiplied by 16.

8. Conclusions

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.

9. Appendix

Proof of Eq.(43)

Eq.(39) with Eq.(41) means

$$\left|{\Delta }_{F_S}[cs]-{\Delta }_{F_C}[c]s\right|\le (p+2^{-1})2^{-F_S}$$EA1

according to Eqs.(13) and (15). Applying the triangle inequality to the left hand side, we have

$$\left|{\Delta }_{F_{\text{S}}}[cs]-{\Delta }_{F_{\text{C}}}[c]s\right|\le \left|{\Delta }_{F_{\text{S}}}[cs]\right|+\left|{\Delta }_{F_{\text{C}}}[c]\right|\left|s\right|$$A2

.

According to Eq.(13), each terms in the right hand side are described as

$$\{\begin{array}{c}{}^{}\left|{\Delta }_{F_{\text{S}}}[cs]\right|\le 2^{-1-F_S}\\ {}^{}\left|{\Delta }_{F_{\text{C}}}[c]\right|\cdot \left|s\right|\le 2^{-1-F_C}{2}^{I_S}\end{array}$$A3

Therefore (A.2) and (A.3) under (A.1) means

$$2^{-1-F_S}+2^{-1-F_C}{2}^{I_S}<(p+2^{-1})2^{-F_S}$$

and finally we have Eq.(43) as

$$2^{-F_C+F_S+I_S-1}\le p$$

.

Q.E.D.