Digital Media Processing DSP Algorithms Using C Hazarathaiah Malepati AMSTERDAM•BOSTON•HEIDELBERG•LONDON NEWYORK•OXFORD•PARIS•SANDIEGO SANFRANCISCO•SINGAPORE•SYDNEY•TOKYO NewnesisanimprintofElsevier NewnesisanimprintofElsevier 30CorporateDrive,Suite400 Burlington,MA01803,USA TheBoulevard,LangfordLane Kidlington,Oxford,OX51GB,UK Copyright©2010ElsevierInc.Allrightsreserved. Nopartofthispublicationmaybereproducedortransmittedinanyformorbyanymeans,electronicormechanical,including photocopying,recording,oranyinformationstorageandretrievalsystem,withoutpermissioninwritingfromthepublisher. Detailsonhowtoseekpermission,furtherinformationaboutthePublisher’spermissionspoliciesandourarrangementswith organizationssuchastheCopyrightClearanceCenterandtheCopyrightLicensingAgency,canbefoundatourwebsite: www.elsevier.com/permissions. ThisbookandtheindividualcontributionscontainedinitareprotectedundercopyrightbythePublisher(otherthanasmaybe notedherein). Notices Knowledgeandbestpracticeinthisfieldareconstantlychanging.Asnewresearchandexperiencebroadenourunderstanding, changesinresearchmethods,professionalpractices,ormedicaltreatmentmaybecomenecessary. Practitionersandresearchersmustalwaysrelyontheirownexperienceandknowledgeinevaluatingandusinganyinformation, methods,compounds,orexperimentsdescribedherein.Inusingsuchinformationormethodstheyshouldbemindfuloftheirown safetyandthesafetyofothers,includingpartiesforwhomtheyhaveaprofessionalresponsibility. Tothefullestextentofthelaw,neitherthePublishernortheauthors,contributors,oreditors,assumeanyliabilityforanyinjury and/ordamagetopersonsorpropertyasamatterofproductsliability,negligenceorotherwise,orfromanyuseoroperationofany methods,products,instructions,orideascontainedinthematerialherein. LibraryofCongressCataloging-in-PublicationData Malepati,Hazarathaiah. Digitalmediaprocessing:DSPalgorithmsusingC/byHazarathaiahMalepati. p.cm. Includesbibliographicalreferencesandindex. ISBN978-1-85617-678-1(alk.paper) 1.Multimediasystems. 2.Embeddedcomputersystems—Programming. 3.Signalprocessing—Digitaltechniques. 4.C(Computerprogramlanguage). I.Title. QA76.575.M31522919 006.7–dc22 2009050460 BritishLibraryCataloguing-in-PublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary. ForinformationonallNewnespublications visitourwebsiteatwww.elsevierdirect.com PrintedintheUnitedStates 10 11 12 13 14 10 9 8 7 6 5 4 3 2 1 This book is dedicated to my late father Mastanaiah Malepati, whose vision and hard work shaped my career a lot. Thispageintentionallyleftblank Contents Preface ................................................................................... ix Chapter 1 Introduction ............................................................................. 1 1.1 DigitalMediaProcessing ................................................................................1 1.2 Media-ProcessingAlgorithms...........................................................................2 1.3 EmbeddedSystemsandApplications...................................................................4 1.4 AlgorithmImplementationonDSPArchitectures......................................................5 Part 1 Data Processing ....................................................... 13 Chapter 2 DataSecurity...........................................................................15 2.1 CryptographyBasics ................................................................................... 15 2.2 TripleDataEncryptionAlgorithm..................................................................... 24 2.3 AdvancedEncryptionStandard........................................................................ 37 2.4 Keyed-HashMessageAuthenticationCode........................................................... 50 2.5 Elliptic-CurveDigitalSignatureAlgorithm........................................................... 58 Chapter 3 Introduction toDataError Correction ..................................................87 3.1 Definitions.............................................................................................. 87 3.2 ErrorDetectionAlgorithms............................................................................ 88 3.3 BlockCodes ............................................................................................ 97 3.4 Hamming(72,64)Coder .............................................................................101 3.5 BCH Codes............................................................................................108 3.6 RS Codes ..............................................................................................112 3.7 ConvolutionalCodes ..................................................................................118 3.8 TrellisCodedModulation.............................................................................126 3.9 ViterbiAlgorithm .....................................................................................134 3.10 TurboCodes ...........................................................................................136 3.11 LDPC Codes...........................................................................................143 Chapter 4 ImplementationofError Correction Algorithms ........................................155 4.1 BCH Codes............................................................................................155 4.2 Reed-SolomonError-CorrectionCodes..............................................................166 4.3 RS ErasureCodes .....................................................................................179 4.4 ViterbiDecoder........................................................................................190 4.5 TurboCodes ...........................................................................................199 4.6 LDPC Codes...........................................................................................216 Chapter 5 Lossless DataCompression ............................................................225 5.1 EntropyCoding........................................................................................226 5.2 VariableLengthDecoding ............................................................................231 5.3 H.264VLC-BasedEntropyCoding ..................................................................242 5.4 MQ-Decoder...........................................................................................260 5.5 Context-Based AdaptiveBinaryArithmeticCoding ................................................269 vi Contents Part 2 Digital Signal and Image Processing ..................................283 Chapter 6 Signals and Systems....................................................................285 6.1 IntroductiontoSignals................................................................................285 6.2 Time-FrequencyRepresentationofContinuous-TimeSignals......................................299 6.3 SamplingofContinuous-TimeSignals...............................................................304 6.4 Time-FrequencyRepresentationofDiscrete-TimeSignals .........................................310 6.5 LinearTime-InvariantSystems.......................................................................312 6.6 GeneralizedFourierTransforms......................................................................317 Chapter 7 Transforms andFilters.................................................................321 7.1 FastFourierTransform................................................................................321 7.2 DiscreteCosineTransform ...........................................................................334 7.3 FilterBasics ...........................................................................................345 7.4 FiniteImpulse-ResponseFilters......................................................................352 7.5 InfiniteImpulse-ResponseFilters ....................................................................363 Chapter 8 Advanced SignalProcessing ............................................................381 8.1 AdaptiveSignalProcessing...........................................................................381 8.2 MultirateSignalProcessing...........................................................................405 8.3 WaveletSignalProcessing............................................................................415 8.4 SimulationandImplementationTechniques.........................................................431 Chapter 9 Digital Communications................................................................437 9.1 Introduction............................................................................................437 9.2 Single-andMulticarrierCommunicationSystems..................................................454 9.3 ChannelEstimation ...................................................................................464 9.4 ChannelEqualization .................................................................................472 9.5 Synchronization .......................................................................................491 9.6 SimulationTechniques................................................................................504 Chapter 10 Image Processing Tools ...............................................................509 10.1 ColorConversion......................................................................................509 10.2 ColorEnhancement ...................................................................................510 10.3 BrightnessandContrastAdjustment.................................................................510 10.4 EdgeEnhancement/SharpeningofEdges............................................................512 10.5 ImageFiltering ........................................................................................512 10.6 EdgeDetection ........................................................................................513 10.7 ImageScaling .........................................................................................525 10.8 ErosionandDilation ..................................................................................531 10.9 ObjectsCornerDetection.............................................................................534 10.10 HoughTransform......................................................................................536 10.11 SimulationofImageProcessingTools ...............................................................540 Chapter 11 Advanced Image Processing Algorithms...............................................553 11.1 ImageRotation ........................................................................................553 11.2 DigitalImageStabilization ...........................................................................562 11.3 ImageObjectsDetection..............................................................................568 11.4 2DImageFilters.......................................................................................575 11.5 FisheyeDistortionCorrection ........................................................................581 11.6 ImageCompression ...................................................................................584 Part 3 Digital Speech and Audio Processing..................................593 Chapter 12 Speech andAudio Processing .........................................................595 12.1 SoundWavesandSignals.............................................................................595 Contents vii 12.2 DigitalRepresentationofAudioSignals.............................................................596 12.3 SignalProcessingwithEmbeddedProcessor........................................................608 12.4 Speech Compression..................................................................................611 12.5 VoIPandJitterBuffer .................................................................................626 Chapter 13 Audio Coding.........................................................................637 13.1 PsychoacousticsandPerceptualCoding .............................................................637 13.2 AudioSignalsCoding.................................................................................642 13.3 MPEG-4AACCodec .................................................................................647 13.4 PopularAudioCodecs ................................................................................651 13.5 AudioPost-Processing................................................................................653 Part 4 Digital Video Processing ..............................................657 Chapter 14 Video Coding Technology .............................................................659 14.1 Introduction............................................................................................659 14.2 VideoCodingBasics..................................................................................661 14.3 MPEG-2Decoder .....................................................................................675 14.4 H.264Decoder ........................................................................................681 14.5 Scalable VideoCoding................................................................................709 Chapter 15 Video Post-Processing ................................................................713 15.1 VideoQualityMeasurement..........................................................................713 15.2 VideoScaling..........................................................................................713 15.3 VideoProcessing......................................................................................728 15.4 VideoTranscoding ....................................................................................737 Index ..............................................................................................745 viii Contents On the Website Part 5 Embedded Systems Chapter 16 EmbeddedSystems ..................................................................... 1 16.1 Introduction...............................................................................................1 16.2 EmbeddedSystemComponents.........................................................................1 16.3 EmbeddedVideoProcessingandSystemIssues...................................................... 20 16.4 Software–HardwarePartitioning ...................................................................... 37 16.5 EmbeddedProcessorsandApplicationRequirements ............................................... 39 Chapter 17 EmbeddedProcessing Applications...................................................... 1 17.1 AutomotiveApplications ................................................................................1 17.2 VideoSurveillanceSystems .............................................................................8 17.3 PortableEntertainmentSystems....................................................................... 11 17.4 DigitalCommunications............................................................................... 12 17.5 DigitalCamera ImagePipe ............................................................................ 20 17.6 HomelandSecurityandHealthCare .................................................................. 22 AppendixA Reference EmbeddedProcessor......................................................... 1 A.1 BlackfinArchitectureOverview.........................................................................1 A.2 OverviewofBlackfinInstructionSet.................................................................. 12 A.3 BlackfinDMA.......................................................................................... 23 A.4 CyclesEstimationwithBlackfin ...................................................................... 25 AppendixB Mathematical Computations onFixed-Point Processors ................................. 1 B.1 NumericDataFixed-PointComputing..................................................................1 B.2 GaloisFields............................................................................................ 10 AppendixC Look-upTables ......................................................................... 1 References........................................................................................... 1 Exercises ............................................................................................ 1 Preface The title of this book could well have been Digital Media Processing Algorithms: Efficient Implementation TechniquesinC,asitisnotonlyaboutdigitalmediaprocessingalgorithms,butalsocontainsmanyimplementa- tiontechniquesformostalgorithms.Themainpurposeofitistofillthegapbetweentheoryandtechniquestaught at universities and that are required by the software industry in the digital processing of data, signal, speech, audio, images,and video onan embedded processor. The book serves as a bridge totransitfrom thetechnical institute to the embedded software development industry. Many powerful algorithms in current cutting-edge technologiesareanalyzed, andsimulationandimplementationtechniquesarepresented. Digital media processing demands efficient programming in order to optimize functionality. Data, signal, image, audio, and video processing—some or all of which are present in all electronic devices today—are complexprogrammingenvironments.Optimizedalgorithms(step-by-stepdirections)aredifficulttocreate, but they can make all the difference when developing a new application. This book discusses the most recent algorithmsavailabletomaximizeyourprogramming,whilesimultaneouslykeepinginmindmemoryandreal- time constraints of the architecture with which you are working. General implementation concepts can be integratedintomanyarchitecturesthatyoufindyourselfworkingwithonaspecificproject. My interest in writing a book on digital media processing algorithms derives from reading literature in the fieldandworkingonthosealgorithms.Thisbookcannotreplacetheliteratureonthebackgroundtheoryrelated to the algorithms; in fact, what is written here is largely incomplete without it. Although I do not rigorously discuss the theory and derivation of equations and theorems, a brief introduction and basic mathematics are providedformostofthealgorithmspresented. Typically,developersofembeddedsoftwaremoduleswanttoknowthebasicfunctionalityofanalgorithmand simulationtechniques,inadditiontowhetheranytechniquesare availabletoefficientlyimplementaparticular algorithm.Mostdevelopersareproficientwithequationsandalgorithmsasaresultofuniversitytraining;however, theefficientimplementationofsuchalgorithmsrequiresindustryexperience. Butemployers,ofcourse, expect developers to immediately begin work. Often they provide training for writing quality software, but not for writingefficientsoftware.Softwareengineerslearnhowtodothisintime,suchasduringthecourseofworking onafewefficientlyimplementedmodulesorobservingaseniorengineer’simplementationmethods.Manysuch techniquestoefficientlysimulateandimplementdigitalmediaprocessingalgorithmsaredescribedinthisbook. Today many algorithmsare available on the Internet, and the software for a number of them isavailable in thepublicdomain.Buttheinformationavailableonthewebistheoryoriented,andwemayobtainonlypieces ofthesoftwarehereandthere andnotthecompletesolution.Sometimes,wecan obtainthecompletesoftware foraparticularalgorithmthatworkswell,butitmaybeinefficientforuseinaparticularproject.Consequently, usershave toenhance softwareefficiency bypurchasingitfroma third-partysource. What’shere providesthe informationneededtodevelopefficientsoftwareformanyalgorithmsfromscratch. Thebookisaimedatgraduateandpostgraduatestudentsinvariousengineeringsubdisciplinesandsoftware industryjunior-levelemployeesdevelopingembeddedsystemssoftware.Onlycollege-levelknowledgeofmath- ematics is required to understand the equations and calculations. Knowledge of ANSI C is a prerequisite for thisbook.Knowledgeofmicrocontroller,microprocessor,ordigitalsignalprocessing(DSP) architectureswill provideanaddedadvantagesothatyoucanunderstandimplementationskillsabitfaster. UnlikeotherDSPalgorithmbooksthatconcentratemainlyonbasicoperations,suchastheFouriertransforms anddigitalfilters,thisbookcoversmanyalgorithmscommonlyusedinmediaprocessing.Formostofthem,this book provides full details of flow, implementationcomplexity, and efficient implementationtechniques using ANSIC.Inaddition,simulationresultsareprovidedforselectedalgorithms. ThisbookusestheAnalogDevices,Inc.(ADI)Blackfinprocessor(BF5xxseries)asthereference embedded processor, and it discusses implementationcomplexity of all algorithmscovered with respect to this amazing general-purpose DSP processor. The Pcode notation (meaning pseudocode or program code) is used to flag simulationcode.