Digital Signal Processing for Multimedia Systems Signal Processing K. J. Ray Liu Series Editor University of Maryland College Park, Maryland Editorial Board Dr. Tsuhan Chen, Carnegie Mellon University Dr. Sadaoki Furui, Tokyo Institute of Technology Dr. Aggelos K. Katsaggelos, Northwestern University Dr. S. Y. Kung, Princeton University Dr. P. K. Raja Rajasekaran, Texas Instruments Dr. John A. Sorenson, Technical University of Denmark 1. Digital Signal Processing for Multimedia Systems, edited by Keshab K. Parhi and Tnkao Nis hitani Additional volumes in preparation Multimedia Systems, Standards and Networks, edited by Dr. Atul Pitri and Dr. Tsuhan Chen Compressed Video Over Networks, edited by Dr. Ming-Ting Sun and Dr. Anij~ Rie br n an Blind Equalization and Identification, Dr. Zhi Ding and Dr. Ye (Geoffrejg Li Interprocessor Communication Strategies for Application Specific Multiprocessors, Dr. Sunt/arcrrjan Srirarn and Dr. Shuvra S. Bhattachaqyta Digital Signal Processing for Multimedia Systems edited by Keshab K. Parhi University of Minnesota Minn eapolis, Minrz esota Takao Nishitani NEC Cor po r at ion Sagarnihara, Japan MARCEL MARCEDL EKKERIN, C. NEWY ORK BASEL 1) E K K E R ISBN: 0-8247-1924-7 This book is printed on acid-free paper. Headquarters Marcel Dekker, Inc. 270 Madison Avenue, New York, NY 10016 tel: 212-696-9000;f ax: 212-685-4540 Eastern Hemisphere Distribution Marcel Dekker AG Hutgasse 4, Postfach 812, CH-4001 Basel, Switzerland tel: 41-61-261-8482f;a x: 4 1-61-261-8896 World Wide Web http://www.dekker.com The publisher offers discounts on this book when ordered in bulk quantities. For more information. write to Special SalesProfessional Marketing at the headquarters address above. Copyright 0 1999 by Marcel Dekker, Inc. All Rights Reserved. Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, microfilming, and recording, or by any information storage and retrieval system, without permission in writing from the publisher. C u r r e nt pi i n t in g (1a st digit ) : 10 9 8 7 6 5 4 3 2 1 PRINTED IN THE UNITED STATES OF AMERICA Series Introduction Over the past 50 years, digital signal processing has evolved as a major engineering discipline. The fields of signal processing have grown from the origin of fast Fourier transform and digital filter design to statistical spectral analysis and array processing, and image, audio, and multimedia processing, and shaped developments in high-performance VLSI signal processor design. Indeed, there are few fields that enjoy so many applications-signal processing is everywhere in our lives. When one uses a cellular phone, the voice is compressed, coded, and modulated using signal processing techniques. As a cruise missile winds along hillsides searching for the target, the signal processor is busy processing the images taken along the way. When we are watching a movie in HDTV, millions of audio and video data are being sent to our homes and received with unbelievable fidelity. When scientists compare DNA samples, fast pattern recognition techniques are being used. On and on, one can see the impact of signal processing in almost every engineering and scientific discipline. Because of the immense importance of signal processing and the fast- growing demands of business and industry, this series on signal processing serves to report up-to-date developments and advances in the field. The topic of interests include but are not limited to the following: Signal theory and analysis Statistical signal processing Speech and audio processing Image and video processing Multimedia signal processing and technology Signal processing for communications Signal processing architectures and VLSI design 0 I hope this series will provide the interested audience with high-quality, state-of-the-art signal processing literature through research monographs, edited books, and rigorously written textbooks by esperts in their fields. I<. J. Ray Liu ... 111 This page intentionally left blank Preface Within a few years, multimedia will become part of everyone’s life. There has been tremendous growth in the field of communications and computing systems in this decade. Much of this growth has been fueled by the promise of multimedia- an exciting array of new products and services, ranging from video games, car naviga- tors and web surfing to interactive television, cellular and video phones, personal digital assistants, video on demand, desktop video conferencing, entertainment and education. In addition to conventional user interfaces and 1/0 operations, these multimedia applications demand real-time digital signal processing (DSP) to sup- port compression and decompression of audio, speech, and video signals, speech recognition and synthesis, and character recognition. These operations require in- tensive multiply and multiply-accumulate operations unique to DSP such as filter- ing, motion detection and compensation, discrete cosine transforms (DCTs), and fast Fourier transforms (FFTs). Although many of these algorithms have been known for decades, it is only in the last few years that VLSI technology has ad- vanced to the point where the enormous computing power required for multimedia applications can be met at very low costs. It is predicted that in the next decade the CMOS technology will scale down to 0.1 micron devices with corresponding improvements in density and speed. The number of transistors on single chips is expected to increase from current 6M to 200M by the year 2010. Digital TV transmission will begin in 1999. Consumers can then use the same device either as a digital TV or as a PC (in non-interlaced or progressive mode). The same device, along with a set-top box, can be used to watch television, listen to music CDs, access videos stored on CD-ROh4s and DVD-ROhls, and for VCRS and video games. This setup has been termed PC theater. The PC theater can allow the user to read several email messages or access the Internet in the middle of watching a TV program (for example during a commercial). This convergence of the TV and the PC will be the key in accessing multimedia information from homes. This book addresses applications of multimedia; programmable and custom architectures for implementation of multimedia systems; and arithmetic architec- tures and design methodologies. The first part (Chapters 1 to 8) begins with applications of multimedia. Video and audio compression are main enabling technologies for multimedia. Chapters 2 and 3 present overview of video and audio compression needed for multimedia ap- plications. Chapter 4 addresses system synchronization aspects. Chapter 5 presents digital versatile disks (DVDs) which will be the medium of storage for multime- dia information. To receive multimedia information at home using the telephone connections, subscriber loops will play an important role. In particular, the in- formation will be received by using asymmetric digital subscriber loops (ADSL) and very-high-data-rate digital subscriber loops (VDSL). Chapter 6 presents archi- V Vi PREFACE tectures for equalizers and modems for ADSL and VDSL applications. Chapter 7 presents cable modems while Chapter 8 presents an overview of wireless systems. One of the important design considerations when building new silicon archi- tectures is the choice between programmable and dedicated hardware. While ded- icated design methodology was popular for high-throughput applications (such as video), the power of current microprocessors and (programmable DSP based) media processors encourages use of these systems to meet the flexibility needed in various forms of computing. It may, however, be noted that the dedicated (or vertically- integrated) design style is still important for low-power applications such as personal digital assistants (PDAs). The second part of the book (Chapters 9 to 19) addresses programmable and custom architecture design of various multimedia components. Chapter 9 begins with programmable digital signal processors (PDSPs) which were first developed in the early 1980s to support iterative and computation-intensive real-time digital signal processing. PDSPs provide an interesting tradeoff between performance and flexibility. These DSP processors deviate from general-purpose mi- croprocessors by introducing specialized data paths to speed up the computations most common in DSP applications, i.e., fast multiply-accumulate operations, and by using multiple-access memories, etc. The first generation DSPs developed for high-throughput audio signal processing exhibited a 50: 1 (5M vs. lOOK multiply- add/s) performance advantage over the microprocessor of the day (M68000), for about the same cost and power. Multimedia computation deals with various forms of data ranging from video, audio, speech, graphics, and text. The type of computing and precision needed also differs for various forms of data. For example, 8-bit precision is sufficient for \ride0 data while 16-bit precision may be needed for audio data. Computer graphics operations need even higher precision. The varying precision requirements also add to the complexity of the design of the media processors. Multimedia processing will continue to be the driving force for the evolution of both microprocessors and DSPs. Recently the introduction of efficient audio and video compression techniques and their standardization has created a new category of devices referred to as media processors which are discussed in Chapter 10. These processors is a special group of DSP processors which are equipped with audio, video and graphics accelerators suitable for multimedia signal processing applications. The media processors can achieve high throughput using moderate clock speed by exploiting parallelism in the form of SIMD or sub-word parallelism (also referred to as split-word parallelism). hlost systems also contain coprocessors for computation-intensive tasks such as motion estimation, I/DCT and variable length coders (VLCs). Another approach to implernentation of media processors are based on a generalized hlMX instruction set for the microprocessors. These are also discussed in Chapter 10. Chapter 11 describes low-power PDSPs for wireless applications. Chapters 12 to 19 present various custom architectures for multimedia al- gorithms. Chapter 12 presents design of motion estimation systems. Chapter 13 describes architectures for wavelets. Chapter 14 addresses implementation of DCTs. Chapters 15 and 16, respectively, present lossless coders and Viterbi decoders used in many decoding applications. Chapter 17 presents an overview of watermarking applic.at,ions of rnultirnedia which are needcd for security in media systems. Chap- tcrs 18 and 19 present advanced recursive least square (RLS) adaptive filtering appronches which are essent ial for iIrii>lerncIit~~tioofn equalizers. PREFACE vii The third part of the book (Chapters 20 to 27) addresses arithmetic architec- tures which form the building blocks and design methodologies for implementations of media systems. Both high-speed and low-power implementations are considered. Chapter 20 addresses division and square-root architectures, Chapter 21 addresses finite field arithmetic architectures which are used for implementation of error con- trol coders and cryptography functions. Chapter 22 presents CORDIC rotation architectures which are needed for implementation of space-time adaptive process- ing systems and orthogonal filtering applications. Chapter 23 presents advanced systolic architectures. Reduction of power consumption is important for media sytems implemented using scaled technologies. Low power consumption increases battery life in portable computers and communications systems such as personal digital assistants. Power consumption reduction a!so leads to reduction of cool- ing and packaging costs. Chapter 24 addresses low power design methodologies while Chapter 25 presents approaches to power estimation. Chapter 26 addresses power reduction methodologies through memory management. Chapter 27 ad- dresses hardware description based synthesis based on custom as well as FPGA implementations which will form the main medium of system implementations in future decades. This book is expected to be of interest to application, circuit and system designers of multimedia systems. No book brings together such a rich variety of topics on multimedia system design as does this one. The editors are most grateful to all coauthors for their contributing excellent chapters. This book could not have been possible without their efforts. They are grateful to Ru-Guang Chen for his help in compiling this book. Thanks are also due to the National Science Foundation (NSF) and the NEC Corporation. A Japan Fellowship to KKP by the NSF was instrumental in bringing the editors together. The editors thank Dr. Ed Murdy and Dr. John Cozzens of NSF, Dr. hlos Kaveh of the University of Minnesota for their support and encouragement. The editors thank Graham Garratt, Rita Lazazzaro and Brian Black of hllarcel Dekker, Inc. It was truly a pleasure to work with them. Keshab I(. Parhi Takao Nishitani