##### Document Text Contents

Page 1

Prelims-P373624.tex 7/8/2006 13: 3 Page ix

Preface

Since the book, Discrete Cosine Transform by K. R. Rao and P. Yip (Academic Press,

Boston) was published in 1990, the discrete cosine transform (DCT) has increasingly

attracted the attention of scientific, engineering and research communities. The DCT is used

in many applications and in data compression in particular. This is due to the fact that the

DCT has excellent energy-packing capability and also approaches the statistically optimal

Karhunen–Loéve transform (KLT) in decorrrelating a signal. The development of various

fast algorithms for the efficient implementation of the DCT involving real arithmetic only,

further contributed to its popularity. In the last several years there have been significant

advances and developments in both theory and applications relating to transform processing

of signals. In particular, digital processing motivated the investigation of other forms of

DCTs for their integer approximations. International standards organizations (ISO/IEC

and ITU-T) have adopted the use of various forms of the integer DCT. At the same time,

the investigation of other forms of discrete sine transforms (DSTs) has made a similar

impact. There is therefore a need to extend the coverage to include these techniques. This

book is aimed at doing just that.

The authors have retained much of the basic theory of transforms and transform processing,

since the basic mathematics remains valid and valuable. The theory and fast algorithms

of the DCTs, as well as those for the DSTs, are dealt with in great detail. There is also an

appendix covering some of the fundamental mathematical aspects underlying the theory

of transforms. It is no exaggeration to say that applications using DCT are numerous and

it is with this in mind that the authors have decided not to include applications explicitly.

Readers of this book will either have practical problems requiring the use of DCT, or

want to examine the more general theory and techniques for future applications. There

is no practical way of comprehensively dealing with all possible applications. However,

it must be emphasized that implementation of the various transforms is considered an

integral part of our presentation. It is the authors’hope that readers will not only gain some

understanding of the various transforms, but also take this knowledge to apply to whatever

processing problems they may encounter.

The book Discrete Cosine and Sine Transforms: General properties, Fast algorithms and

Integer Approximations is aimed at both the novice and the expert. The fervent hopes and

aspirations of the authors are that the latest developments in the general DCT/DST field

ix

Page 2

Prelims-P373624.tex 7/8/2006 13: 3 Page x

x Preface

further lead into additional applications and also provide the incentive and inspiration to

further modify/customize these transforms with the overall motivation to improve their

efficiencies while retaining the simplicity in implementations.

V. Britanak

P. C. Yip

K. R. Rao

February 2006

Page 176

Ch05-P373624.tex 7/8/2006 13: 1 Page 171

Integer Discrete Cosine/Sine Transforms 171

Table 5.2. The computational complexity of fast CMT8 (a, b, c, d, e, f , g, h, i, j, k).

CMT8 (a, b, c, d, e, f , g, h, i, j, k) Mults/adds Adds/shifts

CMT8 (13, 12, 5, 12, 0, 0, 12, 4, 3, 3, 4) 18/34 50/26

CMT8 (34, 30, 16, 31, 1, 7, 25, 13, 5, 19, 11) 20/38 64/32

CMT8 (39, 36, 15, 35, 2, 8, 30, 16, 6, 19, 14) 22/38 54/30

The computational complexity of fast CMT8 (a, b, c, d, e, f , g, h, i, j, k) in terms of the

number of integer multiplications/additions and multiply-free implementation in the

form of additions/shifts with respect to the signal flow graph in Fig. 5.6 is shown in

Table 5.2.

Note 1: From the relation between DCT-II and DST-II matrices given by (4.11) the

fast SMT8 (a, b, c, d, e, f , g, h, i, j, k) for the DST-II computed via WHT can be easily

obtained.

Note 2: From the set of DCTs/DSTs (see Chapter 4), the symmetric cosine transform

(SCT) and symmetric sine transform (SST) defined by (4.9) and (4.10), respectively,

are EOTs and therefore they can be approximated by the same method. However, the

conversion matrix TN for SCT and SST in contrast to the DCT-II will have the following

structure [19]

TN =

U

(1)

N

2

0

0 U(2)N

2

,

i.e., the block matrices U(1)N

2

and U(2)N

2

are of the same order. Note that the SCT and SST do

not have a recursive structure. Consequently, the conversion matrix TN cannot be generated

recursively.

5.4.2 Integer cosine/sine transforms

In this section, we will discuss the method to integer approximation of the DCT-II matrix

originally reported in Refs. [25–37]. The main idea of the method was partially utilized

to construct the new CMTs in the previous section. In essence, the method is to directly

replace the real-valued elements of DCT-II matrix by integers as opposed to the CMT

case where the DCT-II matrix is approximated indirectly through the conversion matrix.

In general, the method can be applied to any DCT and DST [31, 33] although the integer

solutions may not always exist. The resulting integer transforms are referred to as integer

cosine/sine transforms of order N (ICTN /ISTN ).

Let AN be the real-valued DCT/DST matrix with elements {aij}, i, j = 0, 1, . . . , N − 1, and

ĀN its integer approximation with elements {āij}. The integer approximated ICTN /ISTN

Page 177

Ch05-P373624.tex 7/8/2006 13: 1 Page 172

172 Discrete Cosine and Sine Transforms

should satisfy the following additional properties [28, 33, 36, 37]:

• The orthogonality property: Rows (columns) of the integer transform matrix are

orthogonal to each other.

• The integer property: Elements of the approximated transform matrix are integers. In

fact, the elements are approximated by rational numbers, i.e., ratios of integers. The

unitary nature of these matrices prevents the elements to be just integers.

• The relationship with real-valued transform matrix:

(a) if |aij| ≥ |aik|, then |āij| ≥ |āik|, i, j, k = 0, 1, . . . , N − 1;

(b) sign(aij) = sign(āij), i, j = 0, 1, . . . , N − 1.

The orthogonality property ensures that the forward and inverse ICTN /ISTN have the

same transform structure. The integer property eliminates the need for many floating-

point arithmetic operations in computing the transform, since the elements of integer

transform matrix can be represented by finite number of bits. The orthogonal integer

transform matrix it can further be made orthonormal by multiplying it by an appropriate

diagonal matrix. The approximation method guarantees that all mathematical properties

and the recursive structure (if exists) are preserved in the integer approximated transform

matrix. This fact allows any existing fast algorithm to efficiently implement ICTN /ISTN .

Moreover, the energy packing ability and performance will be close to the original

transform. Thus, ICTsN /ISTsN are functionally compatible to corresponding real-valued

DCTs/DSTs.

The method at first is illustrated in detail on the approximation of DCT-II matrix for

N = 8 together with its possible improvements and simplifications. Since in the recursive

sparse matrix factorization (4.50), the DCT-II matrix CIIN requires DCT-II and DCT-IV

matrices of half size, the integer approximation of DCT-IV is also presented. Finally, the

construction of integer transforms for other DCTs and DSTs is discussed.

5.4.2.1 Integer approximation of DCT-II matrix CII8

In the following we describe all the steps to convert the real-valued DCT-II matrix CII8

to an integer matrix. Let CICT-IIN be the integer approximation of C

II

8 and ICT8-II be

resulting integer 8-point DCT-II. We will search for the approximated matrix CICT-II8 in

the form:

CICT-II8 = Q8 V8, (5.53)

where Q8 is a diagonal matrix with normalization factors on its main diagonal, and V8 is

an integer matrix (V8 is frequently called the prototype matrix). The procedure to construct

the approximated matrix CICT-II8 from the corresponding DCT-II matrix C

II

8 includes the

Page 352

Index-P373624.tex 7/8/2006 13: 4 Page 348

348 Index

M

Markov-1 process, 162

Matrix

Cross-indentity (reflection), 76

Diagonal odd-sign changing, 76

Eigenorthogonal, 143

Hermitian, 318

Involutory, 76

Non-eigenorthogonal, 143

Skew-Hermitian, 318

Symmetric positive definite, 327

Unitary, 318

Matrix eigenvalue problem, 314, 316

Matrix factorization

LDU, 150

LU, 150

PLUS, 151

QR, 149

Matrix norms, 144

1-norm, 145

�-norm, 145

Canonical, 145

Frobenius, 145, 336

MDCT/MDST, 1

Mean square error (MSE), 162

Methods for integer approximation of

DCTs/DSTs, 163

Minimum-adder representation, 221

Modulated lapped transform (MLT), 1

MPEG, 289

Multi-dimensional (MDL) structure, 290

Multiplicative irreducibility, 221

N

Net equivalence, 63

Nets, 63

Neumann boundary condition, 30

Normalization factor, 76

Normalized integer transforms, 289

N-point

Reversible transform, 278

SCT, 75

SST, 75

N-point zero mean signal, 52

N-section, 63

O

Odd DCT, 34

Odd DST, 38

Optimal 1-D 8-point DCT algorithm, 124

Optimal 2-D 8 × 8 DCT-II algorithm, 124

Orthogonal, 308

Basis functions, 51

DCT/DST, 74

EOT matrix factorization, 284

Factorizations of DCT-II and DCT-IV

matrices, 264

Matrices, 332

Transformations, 146

Orthogonality, 308

Orthonormal

Basis set, 310

DCT/DST, 74

Orthonormality, 39

P

Perfectly correlated signal, 61

Periodic signals, 339

Permutation matrix, 85, 102, 118, 245, 326

Plane rotation matrices, 142

PL1UL2 matrix factorization, 289

PLUS-based factorization of DCT matrices,

258

PLUS-based structure, 261

PLUS factorization algorithm, 152

PLUS matrix factorization, 151

Points of symmetry (POS), 44

Power signals, 338

Principal component analysis (PCA), 51

Pseudoinverse matrix, 333

Q

QR-based factorization of DCT matrices, 248

QR-based structure, 252, 253

QR matrix factorization, 149, 328

Quantization, 199, 219, 223, 340

Quantum computing, 5

Quasi-

Diagonal matrix, 290

Triangular (lower) matrices, 290

Triangular (upper) matrices, 290

R

Random signals, 338

Recursive sparse matrix factorizations

DCT-I, 84

DCT-II, 96

DCT-IV, 112

DST-I, 91

Reversible DCT, 276

Rotation-based DCT/DST, 81

Rotation matrix, 88,102

Rounding, 245

Rounding procedure, 266

S

Sampling theorem, 343

Scalar multiplication, 305

Scaled DCT-II, 99

Scaling in time, 18, 24, 41

Page 353

Index-P373624.tex 7/8/2006 13: 4 Page 349

Index 349

Section, 63

Shift

in Frequency, 19, 25

in Time, 19, 25, 41

Signal and its representation, 337

SignDCT, 285

Signed DCT square wave transform, 285

Similarity of matrices, 319

Similarity transformation, 56, 319

Sinc function, 23, 28

Sine transform

Discrete, 35

Symmetric, 75

Singular value decomposition (SVD), 334

Skew-circular convolution, 46

Spectral

Mapping, 317

Radius, 316

Shift, 317

Spectral representations and asymptotic

equivalence, 64

Spectrum, 316

Split-radix

DCT-I algorithm, 86

DCT-II algorithm, 108

DST-I algorithm, 94

FFT algorithm, 217

Strong norm, 62

Symmetric convolution, 44

Symmetric cosine transform (SCT), 75

Symmetric periodic sequence (SPS), 45

Symmetric sine transform (SST), 75

T

Tchebyshev polynomials, 58, 69

Toeplitz matrix, 38, 56, 69–70, 162

Trace of a matrix, 163, 317

Transform coding gain, 163

Transform efficiency, 163

Triangular matrices, 143

U

ULD

Factorization, 157

Structures, 158

ULU

Factorization, 155

Structures, 156

Unitarity property, 38

Unitary matrix, 318

Unit rectangular pulse, 22, 27

Unit vector, 145

Upper quasi-triangular matrices, 290

V

Vector addition, 305

Vector norms, 144

Euclidean or 2-norm, 145, 336

Maximum, 145

p–norms, 145

Vector space, 305

Complex, 306

Euclidean, 309

Real, 306

W

Walsh–Hadamard transform (WHT), 102

Weak norm, 62

Whole sample

Antisymmetric (WA), 45

Symmetric (WS), 45

WHT, 102

Z

Zero order Bessel function, 23, 29

Prelims-P373624.tex 7/8/2006 13: 3 Page ix

Preface

Since the book, Discrete Cosine Transform by K. R. Rao and P. Yip (Academic Press,

Boston) was published in 1990, the discrete cosine transform (DCT) has increasingly

attracted the attention of scientific, engineering and research communities. The DCT is used

in many applications and in data compression in particular. This is due to the fact that the

DCT has excellent energy-packing capability and also approaches the statistically optimal

Karhunen–Loéve transform (KLT) in decorrrelating a signal. The development of various

fast algorithms for the efficient implementation of the DCT involving real arithmetic only,

further contributed to its popularity. In the last several years there have been significant

advances and developments in both theory and applications relating to transform processing

of signals. In particular, digital processing motivated the investigation of other forms of

DCTs for their integer approximations. International standards organizations (ISO/IEC

and ITU-T) have adopted the use of various forms of the integer DCT. At the same time,

the investigation of other forms of discrete sine transforms (DSTs) has made a similar

impact. There is therefore a need to extend the coverage to include these techniques. This

book is aimed at doing just that.

The authors have retained much of the basic theory of transforms and transform processing,

since the basic mathematics remains valid and valuable. The theory and fast algorithms

of the DCTs, as well as those for the DSTs, are dealt with in great detail. There is also an

appendix covering some of the fundamental mathematical aspects underlying the theory

of transforms. It is no exaggeration to say that applications using DCT are numerous and

it is with this in mind that the authors have decided not to include applications explicitly.

Readers of this book will either have practical problems requiring the use of DCT, or

want to examine the more general theory and techniques for future applications. There

is no practical way of comprehensively dealing with all possible applications. However,

it must be emphasized that implementation of the various transforms is considered an

integral part of our presentation. It is the authors’hope that readers will not only gain some

understanding of the various transforms, but also take this knowledge to apply to whatever

processing problems they may encounter.

The book Discrete Cosine and Sine Transforms: General properties, Fast algorithms and

Integer Approximations is aimed at both the novice and the expert. The fervent hopes and

aspirations of the authors are that the latest developments in the general DCT/DST field

ix

Page 2

Prelims-P373624.tex 7/8/2006 13: 3 Page x

x Preface

further lead into additional applications and also provide the incentive and inspiration to

further modify/customize these transforms with the overall motivation to improve their

efficiencies while retaining the simplicity in implementations.

V. Britanak

P. C. Yip

K. R. Rao

February 2006

Page 176

Ch05-P373624.tex 7/8/2006 13: 1 Page 171

Integer Discrete Cosine/Sine Transforms 171

Table 5.2. The computational complexity of fast CMT8 (a, b, c, d, e, f , g, h, i, j, k).

CMT8 (a, b, c, d, e, f , g, h, i, j, k) Mults/adds Adds/shifts

CMT8 (13, 12, 5, 12, 0, 0, 12, 4, 3, 3, 4) 18/34 50/26

CMT8 (34, 30, 16, 31, 1, 7, 25, 13, 5, 19, 11) 20/38 64/32

CMT8 (39, 36, 15, 35, 2, 8, 30, 16, 6, 19, 14) 22/38 54/30

The computational complexity of fast CMT8 (a, b, c, d, e, f , g, h, i, j, k) in terms of the

number of integer multiplications/additions and multiply-free implementation in the

form of additions/shifts with respect to the signal flow graph in Fig. 5.6 is shown in

Table 5.2.

Note 1: From the relation between DCT-II and DST-II matrices given by (4.11) the

fast SMT8 (a, b, c, d, e, f , g, h, i, j, k) for the DST-II computed via WHT can be easily

obtained.

Note 2: From the set of DCTs/DSTs (see Chapter 4), the symmetric cosine transform

(SCT) and symmetric sine transform (SST) defined by (4.9) and (4.10), respectively,

are EOTs and therefore they can be approximated by the same method. However, the

conversion matrix TN for SCT and SST in contrast to the DCT-II will have the following

structure [19]

TN =

U

(1)

N

2

0

0 U(2)N

2

,

i.e., the block matrices U(1)N

2

and U(2)N

2

are of the same order. Note that the SCT and SST do

not have a recursive structure. Consequently, the conversion matrix TN cannot be generated

recursively.

5.4.2 Integer cosine/sine transforms

In this section, we will discuss the method to integer approximation of the DCT-II matrix

originally reported in Refs. [25–37]. The main idea of the method was partially utilized

to construct the new CMTs in the previous section. In essence, the method is to directly

replace the real-valued elements of DCT-II matrix by integers as opposed to the CMT

case where the DCT-II matrix is approximated indirectly through the conversion matrix.

In general, the method can be applied to any DCT and DST [31, 33] although the integer

solutions may not always exist. The resulting integer transforms are referred to as integer

cosine/sine transforms of order N (ICTN /ISTN ).

Let AN be the real-valued DCT/DST matrix with elements {aij}, i, j = 0, 1, . . . , N − 1, and

ĀN its integer approximation with elements {āij}. The integer approximated ICTN /ISTN

Page 177

Ch05-P373624.tex 7/8/2006 13: 1 Page 172

172 Discrete Cosine and Sine Transforms

should satisfy the following additional properties [28, 33, 36, 37]:

• The orthogonality property: Rows (columns) of the integer transform matrix are

orthogonal to each other.

• The integer property: Elements of the approximated transform matrix are integers. In

fact, the elements are approximated by rational numbers, i.e., ratios of integers. The

unitary nature of these matrices prevents the elements to be just integers.

• The relationship with real-valued transform matrix:

(a) if |aij| ≥ |aik|, then |āij| ≥ |āik|, i, j, k = 0, 1, . . . , N − 1;

(b) sign(aij) = sign(āij), i, j = 0, 1, . . . , N − 1.

The orthogonality property ensures that the forward and inverse ICTN /ISTN have the

same transform structure. The integer property eliminates the need for many floating-

point arithmetic operations in computing the transform, since the elements of integer

transform matrix can be represented by finite number of bits. The orthogonal integer

transform matrix it can further be made orthonormal by multiplying it by an appropriate

diagonal matrix. The approximation method guarantees that all mathematical properties

and the recursive structure (if exists) are preserved in the integer approximated transform

matrix. This fact allows any existing fast algorithm to efficiently implement ICTN /ISTN .

Moreover, the energy packing ability and performance will be close to the original

transform. Thus, ICTsN /ISTsN are functionally compatible to corresponding real-valued

DCTs/DSTs.

The method at first is illustrated in detail on the approximation of DCT-II matrix for

N = 8 together with its possible improvements and simplifications. Since in the recursive

sparse matrix factorization (4.50), the DCT-II matrix CIIN requires DCT-II and DCT-IV

matrices of half size, the integer approximation of DCT-IV is also presented. Finally, the

construction of integer transforms for other DCTs and DSTs is discussed.

5.4.2.1 Integer approximation of DCT-II matrix CII8

In the following we describe all the steps to convert the real-valued DCT-II matrix CII8

to an integer matrix. Let CICT-IIN be the integer approximation of C

II

8 and ICT8-II be

resulting integer 8-point DCT-II. We will search for the approximated matrix CICT-II8 in

the form:

CICT-II8 = Q8 V8, (5.53)

where Q8 is a diagonal matrix with normalization factors on its main diagonal, and V8 is

an integer matrix (V8 is frequently called the prototype matrix). The procedure to construct

the approximated matrix CICT-II8 from the corresponding DCT-II matrix C

II

8 includes the

Page 352

Index-P373624.tex 7/8/2006 13: 4 Page 348

348 Index

M

Markov-1 process, 162

Matrix

Cross-indentity (reflection), 76

Diagonal odd-sign changing, 76

Eigenorthogonal, 143

Hermitian, 318

Involutory, 76

Non-eigenorthogonal, 143

Skew-Hermitian, 318

Symmetric positive definite, 327

Unitary, 318

Matrix eigenvalue problem, 314, 316

Matrix factorization

LDU, 150

LU, 150

PLUS, 151

QR, 149

Matrix norms, 144

1-norm, 145

�-norm, 145

Canonical, 145

Frobenius, 145, 336

MDCT/MDST, 1

Mean square error (MSE), 162

Methods for integer approximation of

DCTs/DSTs, 163

Minimum-adder representation, 221

Modulated lapped transform (MLT), 1

MPEG, 289

Multi-dimensional (MDL) structure, 290

Multiplicative irreducibility, 221

N

Net equivalence, 63

Nets, 63

Neumann boundary condition, 30

Normalization factor, 76

Normalized integer transforms, 289

N-point

Reversible transform, 278

SCT, 75

SST, 75

N-point zero mean signal, 52

N-section, 63

O

Odd DCT, 34

Odd DST, 38

Optimal 1-D 8-point DCT algorithm, 124

Optimal 2-D 8 × 8 DCT-II algorithm, 124

Orthogonal, 308

Basis functions, 51

DCT/DST, 74

EOT matrix factorization, 284

Factorizations of DCT-II and DCT-IV

matrices, 264

Matrices, 332

Transformations, 146

Orthogonality, 308

Orthonormal

Basis set, 310

DCT/DST, 74

Orthonormality, 39

P

Perfectly correlated signal, 61

Periodic signals, 339

Permutation matrix, 85, 102, 118, 245, 326

Plane rotation matrices, 142

PL1UL2 matrix factorization, 289

PLUS-based factorization of DCT matrices,

258

PLUS-based structure, 261

PLUS factorization algorithm, 152

PLUS matrix factorization, 151

Points of symmetry (POS), 44

Power signals, 338

Principal component analysis (PCA), 51

Pseudoinverse matrix, 333

Q

QR-based factorization of DCT matrices, 248

QR-based structure, 252, 253

QR matrix factorization, 149, 328

Quantization, 199, 219, 223, 340

Quantum computing, 5

Quasi-

Diagonal matrix, 290

Triangular (lower) matrices, 290

Triangular (upper) matrices, 290

R

Random signals, 338

Recursive sparse matrix factorizations

DCT-I, 84

DCT-II, 96

DCT-IV, 112

DST-I, 91

Reversible DCT, 276

Rotation-based DCT/DST, 81

Rotation matrix, 88,102

Rounding, 245

Rounding procedure, 266

S

Sampling theorem, 343

Scalar multiplication, 305

Scaled DCT-II, 99

Scaling in time, 18, 24, 41

Page 353

Index-P373624.tex 7/8/2006 13: 4 Page 349

Index 349

Section, 63

Shift

in Frequency, 19, 25

in Time, 19, 25, 41

Signal and its representation, 337

SignDCT, 285

Signed DCT square wave transform, 285

Similarity of matrices, 319

Similarity transformation, 56, 319

Sinc function, 23, 28

Sine transform

Discrete, 35

Symmetric, 75

Singular value decomposition (SVD), 334

Skew-circular convolution, 46

Spectral

Mapping, 317

Radius, 316

Shift, 317

Spectral representations and asymptotic

equivalence, 64

Spectrum, 316

Split-radix

DCT-I algorithm, 86

DCT-II algorithm, 108

DST-I algorithm, 94

FFT algorithm, 217

Strong norm, 62

Symmetric convolution, 44

Symmetric cosine transform (SCT), 75

Symmetric periodic sequence (SPS), 45

Symmetric sine transform (SST), 75

T

Tchebyshev polynomials, 58, 69

Toeplitz matrix, 38, 56, 69–70, 162

Trace of a matrix, 163, 317

Transform coding gain, 163

Transform efficiency, 163

Triangular matrices, 143

U

ULD

Factorization, 157

Structures, 158

ULU

Factorization, 155

Structures, 156

Unitarity property, 38

Unitary matrix, 318

Unit rectangular pulse, 22, 27

Unit vector, 145

Upper quasi-triangular matrices, 290

V

Vector addition, 305

Vector norms, 144

Euclidean or 2-norm, 145, 336

Maximum, 145

p–norms, 145

Vector space, 305

Complex, 306

Euclidean, 309

Real, 306

W

Walsh–Hadamard transform (WHT), 102

Weak norm, 62

Whole sample

Antisymmetric (WA), 45

Symmetric (WS), 45

WHT, 102

Z

Zero order Bessel function, 23, 29