Near-Capacity Variable-Length Coding E-Book

Lajos L. Hanzo

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley - IEEE
• Sprache: Englisch

Seitenzahl: 891

Veröffentlichungsjahr: 2011

Beschreibung

Recent developments such as the invention of powerful turbo-decoding and irregular designs, together with the increase in the number of potential applications to multimedia signal compression, have increased the importance of variable length coding (VLC). Providing insights into the very latest research, the authors examine the design of diverse near-capacity VLC codes in the context of wireless telecommunications. The book commences with an introduction to Information Theory, followed by a discussion of Regular as well as Irregular Variable Length Coding and their applications in joint source and channel coding. Near-capacity designs are created using Extrinsic Information Transfer (EXIT) chart analysis. The latest techniques are discussed, outlining radical concepts such as Genetic Algorithm (GA) aided construction of diverse VLC codes. The book concludes with two chapters on VLC-based space-time transceivers as well as on frequency-hopping assisted schemes, followed by suggestions for future work on the topic. * Surveys the historic evolution and development of VLCs * Discusses the very latest research into VLC codes * Introduces the novel concept of Irregular VLCs and their application in joint-source and channel coding

Leseprobe

Contents

About the Authors

Other Wiley and IEEE Press Books on Related Topics

Preface

Acknowledgements

Chapter 1: Introduction

1.1 Historical Overview

1.2 Applications of Irregular Variable-Length Coding

1.3 Motivation and Methodology

1.4 Outline of the Book

1.5 Novel Contributions of the Book

Chapter 2: Information Theory Basics

2.1 Issues in Information Theory

2.2 Additive White Gaussian Noise Channel

2.3 Information of a Source

2.4 Average Information of Discrete Memoryless Sources

2.5 Source Coding for a Discrete Memoryless Source

2.6 Entropy of Discrete Sources Exhibiting Memory

2.7 Examples

2.8 Generating Model Sources

2.9 Run-Length Coding for Discrete Sources Exhibiting Memory

2.10 Information Transmission via Discrete Channels

2.11 Capacity of Discrete Channels [216, 223]

2.12 Shannon’s Channel Coding Theorem [220, 228]

2.13 Capacity of Continuous Channels [217, 223]

2.14 Shannon’s Message for Wireless Channels

2.15 Summary and Conclusions

Part I: Regular Concatenated Codes and Their Design

List of Symbols in Part I

Chapter 3: Sources and Source Codes

3.1 Introduction

3.2 Source Models

3.3 Source Codes

3.4 Soft Decoding of Variable-Length Codes

3.5 Summary and Conclusions

Chapter 4: Iterative Source–Channel Decoding

4.1 Concatenated Coding and the Turbo Principle

4.2 SISOAPP Decoders and their EXIT Characteristics

4.3 Iterative Source–Channel Decoding Over AWGN Channels

4.4 Iterative Channel Equalization, Channel Decoding and Source Decoding

4.5 Summary and Conclusions

Chapter 5: Three-Stage Serially Concatenated Turbo Equalization

5.1 Introduction

5.2 Soft-In Soft-Out MMSE Equalization

5.3 Turbo Equalization Using MAP/MMSE Equalizers

5.4 Three-Stage Serially Concatenated Coding and MMSE Equalization

5.5 Approaching the Channel Capacity Using EXIT-Chart Matching and IRCCs

5.6 Rate Optimization of Serially Concatenated Codes

5.7 Joint Source-Channel Turbo Equalization Revisited

5.8 Summary and Conclusions

Part II: Irregular Concatenated VLCs and Their Design

List of Symbols in Part II

Chapter 6: Irregular Variable-Length Codes for Joint Source and Channel Coding

6.1 Introduction

6.2 Over view of Proposed Scheme

6.3 Transmission Frame Structure

6.4 VDVQ/RVLC Encoding

6.5 APP SISO VDVQ/RVLC Decoding

6.6 Simulation Results

6.7 Summary and Conclusions

Chapter 7: Irregular Variable-Length Codes for EXIT-Chart Matching

7.1 Introduction

7.2 Overview of Proposed Schemes

7.3 Parameter Design for the Proposed Schemes

7.4 Simulation Results

7.5 Summary and Conclusions

Chapter 8: Genetic Algorithm-Aided Design of Irregular Variable-Length Coding Components

8.1 Introduction

8.2 The Free Distance Metric

8.3 Overview of the Proposed Genetic Algorithm

8.4 Overview of Proposed Scheme

8.5 Parameter Design for the Proposed Scheme

8.6 Simulation Results

8.7 Summary and Conclusions

Chapter 9: Joint EXIT-Chart Matching of Irregular Variable-Length Coding and Irregular Unity-Rate Coding

9.1 Introduction

9.2 Modifications of the EXIT-Chart Matching Algorithm

9.3 Joint EXIT-Chart Matching

9.4 Overview of the Transmission Scheme Considered

9.5 System Parameter Design

9.6 Simulation Results

9.7 Summary and Conclusions

Part III: Applications of VLCs

Chapter 10: Iteratively Decoded VLC Space–Time Coded Modulation: Code Construction and Convergence Analysis

10.1 Introduction

10.2 Space–Time Coding Overview

10.3 Two-Dimensional VLC Design

10.4 VL-STCM Scheme

10.5 VL-STCM-ID Scheme

10.6 Convergence Analysis

10.7 Simulation Results

10.8 Non-Binary VL-STCM

10.9 Conclusions

Chapter 11: Iterative Detection of Three-Stage Concatenated IrVLC FFH-MFSK

11.1 Introduction

11.2 System Overview

11.3 Iterative Decoding

11.4 System Parameter Design and Results

11.5 Conclusion

Chapter 12: Conclusions and Future Research

12.1 Chapter 1: Introduction

12.2 Chapter2:Information Theory Basics

12.3 Chapter3: Sources and Source Codes

12.4 Chapter4: Iterative Source–Channel Decoding

12.5 Chapter5: Three-Stage Serially Concatenated Turbo Equalization

12.6 Chapter 6: Joint Source and Channel Coding

12.7 Chapters 7–9: EXIT-Chart Matching

12.8 Chapter 8: GA-Aided Design of Irregular VLC Components

12.9 Chapter 9: Joint EXIT-Chart Matching of IRVLCs and IRURCs

12.10 Chapter 10: Iteratively Decoded VLC Space–Time Coded Modulation

12.11 Chapter 11: Iterative Detection of Three-Stage Concatenated IrVLCFFH-MFSK

12.12 Future Work

12.13 Closing Remarks

Appendix A VLC Construction Algorithms

A.1 First RVLC Construction Algorithm

A.2 Second RVLC Construction Algorithm

A.3 Greedy Algorithm and Majority Voting Algorithm (MVA)

Appendix B SISO VLC Decoder

Appendix C APP Channel Equalization

Bibliography

Glossary

Subject Index

Author Index

This edition first published 2011©2011 John Wiley & Sons Ltd

Registered officeJohn Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ,United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the understanding that the publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Library of Congress Cataloging-in-Publication Data

Near-capacity variable length coding : regular and exit-chart aided irregular designs / L. Hanzo ... [et al.].p. cm.Includes bibliographical references and index.ISBN 978-0-470-66520-6 (cloth)1. Coding theory. I. Hanzo, Lajos, 1952-TK5102.92.N43 2011003’.54–dc222010004481

We dedicate this monograph to the numerous contributors of this field, many of whom are listed in the Author Index.

About the Authors

Lajos Hanzo FREng, FIEEE, FIET, DSc received his degree in electronics in 1976 and his doctorate in 1983. During his career he has held various research and academic posts in Hungary, Germany and the UK. Since 1986 he has been with the School of Electronics and Computer Science, University of Southampton, UK, where he holds the chair in telecommunications. He has co-authored 19 books on mobile radio communications totaling in excess of 10 000 pages, published in excess of 900 research papers, acted as TPC Chair of IEEE conferences, presented keynote lectures and been awarded a number of distinctions. Currently he is directing an academic research team, working on a range of research projects in the field of wireless multimedia communications sponsored by industry, the Engineering and Physical Sciences Research Council (EPSRC) UK, the European IST Programme and the Mobile Virtual Centre of Excellence (VCE), UK. He is an enthusiastic supporter of industrial and academic liaison and he offers a range of industrial courses. He is also an IEEE Distinguished Lecturer as well as a Governor of both the IEEE ComSoc and the VTS. He is the acting Editor-in-Chief of the IEEE Press. For further information on research in progress and associated publications please refer to http://www-mobile.ecs.soton.ac.uk

Robert G. Maunder has studied with the School of Electronics and Computer Science, University of Southampton, UK, since October 2000. He was awarded a first class honours BEng in Electronic Engineering in July 2003, shortly before beginning his current PhD studies in the Communications Research Group at the same university. His research interests include video coding, joint source–channel coding and iterative decoding. He has published a number of IEEE papers in these areas. In 2007 he joined the academic staff.

Jin Wang received the BE degree from the University of Science and Technology of China (USTC), Hefei, China, in 1999 and the ME degree in video signal processing from the Graduate School of the Chinese Academy of Sciences (GSCAS), Beijing, China, in 2002. He completed his PhD degree with the Communications Research Group at the School of Electronics and Computer Science, University of Southampton, UK, where he conducted research on source coding, channel coding and joint source–channel coding, as well as on iterative detection and decoding designed for digital communication systems. His research results were published in a dozen or so IEEE journal and conference papers. Upon completing his PhD he joined Imagination Technologies in the UK, and in 2008 he transferred to Aeroflex, Cambridge, UK, working on 3GPP LTE solutions.

Lie-Liang Yang received his BEng degree in communication engineering from Shanghai TieDao University, Shanghai, China in 1988, and his MEng and PhD degrees in communications and electronics from Northern Jiaotong University, Beijing, China, in 1991 and 1997 respectively. From June 1997 to December 1997 he was a visiting scientist at the Institute of Radio Engineering and Electronics, Academy of Sciences of the Czech Republic. Since December 1997 he has been with the Communications Research Group, School of Electronics and Computer Science, University of Southampton, UK, where he was first a Postdoctoral Research Fellow (December 1997–August 2002) and then a Lecturer (September 2002–February 2006), and currently holds the academic post of Reader. Dr Yang’s research has covered a wide range of areas in telecommunications, which include error control coding, modulation and demodulation, spread-spectrum communications and multiuser detection, synchronization, space-time processing and adaptive wireless systems, as well as wideband, broadband and ultra-wideband code-division multiple-access (CDMA). He has published around 150 papers in journals and conference proceedings, co-authored two Wiley–IEEE Press books and published his research monograph on Multicarrier Communications in 2009. He was awarded the Royal Society Sino-British Fellowship in 1997 and the EPSRC Research Fellowship in 1998. Dr Yang is currently an associate editor for both the Journal of Communications and Networks (JCN) and the Journal of Communications (JCM).

Other Wiley and IEEE Press Books on Related Topics1

R. Steele, L. Hanzo (Ed): Mobile Radio Communications: Second and Third Generation Cellular and WATM Systems, John Wiley and IEEE Press, 2nd edition, 1999, 1064 pagesL. Hanzo, T. H. Liew, B. L. Yeap: Turbo Coding, Turbo Equalisation and Space-Time Coding, John Wiley and IEEE Press, 2002, 751 pagesL. Hanzo, C. H. Wong, M. S. Yee: Adaptive Wireless Transceivers: Turbo-Coded, Turbo-Equalised and Space-Time Coded TDMA, CDMA and OFDM Systems, John Wiley and IEEE Press, 2002, 737 pagesL. Hanzo, L.-L. Yang, E.-L. Kuan, K. Yen: Single- and Multi-Carrier CDMA: Multi-User Detection, Space-Time Spreading, Synchronisation, Networking and Standards, John Wiley and IEEE Press, June 2003, 1060 pagesL. Hanzo, M. Münster, T. Keller, B.-J. Choi, OFDM and MC-CDMA for Broadband Multi-User Communications, WLANs and Broadcasting, John-Wiley and IEEE Press, 2003, 978 pagesL. Hanzo, S.-X. Ng, T. Keller and W. T. Webb, Quadrature Amplitude Modulation: From Basics to Adaptive Trellis-Coded, Turbo-Equalised and Space-Time Coded OFDM, CDMA and MC-CDMA Systems, John Wiley and IEEE Press, 2004, 1105 pagesL. Hanzo, T. Keller: An OFDM and MC-CDMA Primer, John Wiley and IEEE Press, 2006, 430 pagesL. Hanzo, F. C. A. Somerville, J. P. Woodard: Voice and Audio Compression for Wireless Communications, John Wiley and IEEE Press, 2007, 858 pagesL. Hanzo, P. J. Cherriman, J. Streit: Video Compression and Communications: H.261, H.263, H.264, MPEG4 and HSDPA-Style Adaptive Turbo-Transceivers John Wiley and IEEE Press, 2007, 680 pagesL. Hanzo, J. S. Blogh, S. Ni: 3G, HSDPA, HSUPA and FDD Versus TDD Networking: Smart Antennas and Adaptive Modulation John Wiley and IEEE Press, 2008, 564 pagesL. Hanzo, O. Alamri, M. El-Hajjar, N. Wu: Near-Capacity Multi-Functional MIMO Systems: Sphere-Packing, Iterative Detection and Cooperation, IEEE Press – John Wiley, 2009L. Hanzo, J. Akhtman, M. Jiang, L. Wang: MIMO-OFDM for LTE, WIFI and WIMAX: Coherent versus Non-Coherent and Cooperative Turbo-Transceivers, John Wiley and IEEE Press, 2010, 608 pages

1For detailed contents and sample chapters please refer to http://www-mobile.ecs.soton.ac.uk

Preface

Variable-Length Codes (VLCs) have as long a history as that of information theory. Shannon’s original lossless entropy codes adopted the conceptually appealing philosophy that a stream of binary source data may be partitioned into fixed-length data segments, where the segments having a low probability of occurrence may be assigned long codewords, while the high-probability ones must have short codewords assigned to them. This facilitates the reduction of the average number of bits that has to be transmitted. A further design criterion is that no shorter codeword may constitute a prefix, i.e. the initial segment of a longer codeword.

Naturally, the compressed data stream becomes more susceptible to the loss of synchronization in the presence of transmission errors, in the sense that the decoder cannot recognize a corrupted codeword and hence it is bound to read past the end of the original error-free codeword. This phenomenon potentially prevents the decoder from recognizing the next legitimate codeword, and hence can result in an avalanche-like error propagation. In order to circumvent this potential problem, numerous design alternatives have emerged. Examples include Variable-Length Error Correction (VLEC) codes and reversible VLCs (RVLCs) (which contain redundancy in the sense that they are constituted by a bit-pattern that is symmetric with respect to the middle, and hence may be decoded from both ends).

The family of VLCs has also found its way into virtually all video and audio compression standards, which are used by widespread consumer products, and yet there has been no dedicated book on the subject of VLCs. This volume aims to fill that gap, with the objective of reporting on the most recent research advances, including iterative turbo decoding and irregular designs based on EXtrinsic Information Transfer (EXIT) charts. The proposed code design principles are generic, and hence they may be applied to arbitrary code design problems.

Our intention with the book is:

First, to pay tribute to all the researchers, colleagues and valued friends who have contributed to the field. Hence this monograph is dedicated to them, since without their quest for improved VLCs it could not have been conceived. They are too numerous to name here, but they appear in the author index. Our hope is that the conception of this monograph on the topic will provide an adequate portrayal of the community’s research and will further fuel this innovation process.Second, to stimulate further research by exposing open research problems, and by collating a range of practical problems as well as design issues for the practitioners. The coherent further efforts of the wireless research community are expected to lead to the solution of a range of outstanding problems, ultimately providing us with flexible joint source- and channel-coded wireless transceivers exhibiting a performance close to the information theoretical limits.

Acknowledgements

We are indebted to our many colleagues who have enhanced our understanding of the subject. These colleagues and valued friends, too numerous to be mentioned individually, have influenced our views concerning the subject of the book. We thank them for the enlightenment gained from our collaborations on various projects, papers and books. We are particularly grateful to our academic colleagues Prof. Sheng Chen and Dr Soon-Xin Ng. We would also like to express our appreciation to Osamah Alamri, Dr Sohail Ahmed, Andreas Ahrens, Jos Akhtman, Jan Brecht, Jon Blogh, Nicholas Bonello, Marco Breiling, Marco del Buono, Peter Cherriman, Stanley Chia, Byoung Jo Choi, Joseph Cheung, Jin-Yi Chung, Peter Fortune, Thanh Nguyen Dang, Sheyam Lal Dhomeja, Lim Dongmin, Dirk Didascalou, Mohammed El-Hajjar, Stephan Ernst, Eddie Green, David Greenwood, Chen Hong, Hee Thong How, Bin Hu, Ming Jiang, Thomas Keller, Lingkun Kong, Choo Leng Koh, Ee Lin Kuan, W. H. Lam, Wei Liu, Kyungchun Lee, Xiang Liu, Fasih Muhammad Butt, Matthias Münster, Song Ni, C. C. Lee, M. A. Nofal, Xiao Lin, Chee Siong Lee, Tong-Hooi Liew, Noor Shamsiah Othman, Raja Ali Raja Riaz, Vincent Roger-Marchart, Redwan Salami, Prof. Raymond Steele, Shinya Sugiura, David Stewart, Clare Sommerville, Tim Stevens, Shuang Tan, Ronal Tee, Jeff Torrance, Spyros Vlahoyiannatos, Jin Wang, Li Wang, William Webb, Chun-Yi Wei, Hua Wei, Stefan Weiss, John Williams, Seung-Hwang Won, Jason Woodard, Choong Hin Wong, Henry Wong, James Wong, Andy Wolfgang, Nan Wu, Lei Xu, Chong Xu, Du Yang, Wang Yao, Bee-Leong Yeap, Mong-Suan Yee, Kai Yen, Andy Yuen, Jiayi Zhang, Rong Zhang, and many others with whom we have enjoyed an association.

We also acknowledge our valuable associations with the Virtual Centre of Excellence in Mobile Communications, in particular with its chief executive, Dr Walter Tuttlebee, and other members of its Executive Committee, namely Dr Keith Baughan, Prof. Hamid Aghvami, Prof. Mark Beach, Prof. John Dunlop, Prof. Barry Evans, Prof. Peter Grant, Dr Dean Kitchener, Prof. Steve MacLaughlin, Prof. Joseph McGeehan, Dr Tim Moulsley, Prof. Rahim Tafazolli, Prof. Mike Walker and many other valued colleagues. Our sincere thanks are also due to John Hand and Andrew Lawrence of EPSRC, UK for supporting our research. We would also like to thank Dr Joao Da Silva, Dr Jorge Pereira, Bartholome Arroyo, Bernard Barani, Demosthenes Ikonomou, and other valued colleagues from the Commission of the European Communities, Brussels, Belgium.

The authors of this book are particularly indebted to Peter Cherriman and Jurgen Streit for generously allowing them to use Chapter 1 of Hanzo, Cherriman and Streit: Wireless Video Communications, IEEE Press 2001 as Chapter 1 of this monograph. This chapter might be found helpful by readers, who are new to information theory. The inclusion of this chapter into this book was facilitated by transferring the copyright of the above-mentioned original source from the IEEE Press to the authors, namely to Hanzo, Cherriman and Streit.

Similarly, our sincere thanks are due to Mark Hammond, Sarah Tilley and their colleagues at Wiley in Chichester, UK. Finally, our sincere gratitude is due to the numerous authors listed in the Author Index – as well as to those whose work was not cited owing to space limitations – for their contributions to the state of the art, without whom this book would not have materialized.

Lajos Hanzo, Robert G. Maunder, Jin Wang and Lie-Liang YangSchool of Electronics and Computer ScienceUniversity of Southampton, UK