Essentials of Error Control Coding

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

ESSENTIALS OF

ERROR-CONTROL

CODING

Jorge Castiñeira Moreira

University of Mar del Plata, Argentina

Patrick Guy Farrell

Lancaster University, UK

iii

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

ii

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

ESSENTIALS OF

ERROR-CONTROL

CODING

i

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

ii

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

ESSENTIALS OF

ERROR-CONTROL

CODING

Jorge Castiñeira Moreira

University of Mar del Plata, Argentina

Patrick Guy Farrell

Lancaster University, UK

iii

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

Copyright C 2006 John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester,

West Sussex PO19 8SQ, England

Telephone (+44) 1243 779777

Email (for orders and customer service enquiries): [email protected]

Visit our Home Page on www.wiley.com

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, scanning or

otherwise, except under the terms of the Copyright, Designs and Patents Act 1988 or under the terms of a

licence issued by the Copyright Licensing Agency Ltd, 90 Tottenham Court Road, London W1T 4LP, UK,

without the permission in writing of the Publisher. Requests to the Publisher should be addressed to the

Permissions Department, John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19

8SQ, England, or emailed to [email protected], or faxed to (+44) 1243 770620.

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.

Other Wiley Editorial Offices

John Wiley & Sons Inc., 111 River Street, Hoboken, NJ 07030, USA

Jossey-Bass, 989 Market Street, San Francisco, CA 94103-1741, USA

Wiley-VCH Verlag GmbH, Boschstr. 12, D-69469 Weinheim, Germany

John Wiley & Sons Australia Ltd, 42 McDougall Street, Milton, Queensland 4064, Australia

John Wiley & Sons (Asia) Pte Ltd, 2 Clementi Loop #02-01, Jin Xing Distripark, Singapore 129809

John Wiley & Sons Canada Ltd, 6045 Freemont Blvd, Mississauga, ONT, L5R 4J3, Canada

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

not be available in electronic books.

British Library Cataloguing in Publication Data

A catalogue record for this book is available from the British Library

ISBN-13 978-0-470-02920-6 (HB)

ISBN-10 0-470-02920-X (HB)

Typeset in 10/12pt Times by TechBooks, New Delhi, India.

Printed and bound in Great Britain by Antony Rowe Ltd, Chippenham, England.

This book is printed on acid-free paper responsibly manufactured from sustainable forestry in which at least two

trees are planted for each one used for paper production.

iv

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

We dedicate this book to

my son Santiago José,

Melisa and Belén,

Maria, Isabel, Alejandra and Daniel,

and the memory of my Father.

J.C.M.

and to all my families and friends.

P.G.F.

v

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

vi

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

Contents

Preface xiii

Acknowledgements xv

List of Symbols xvii

Abbreviations xxv

1 Information and Coding Theory 1

1.1 Information 3

1.1.1 A Measure of Information 3

1.2 Entropy and Information Rate 4

1.3 Extended DMSs 9

1.4 Channels and Mutual Information 10

1.4.1 Information Transmission over Discrete Channels 10

1.4.2 Information Channels 10

1.5 Channel Probability Relationships 13

1.6 The A Priori and A Posteriori Entropies 15

1.7 Mutual Information 16

1.7.1 Mutual Information: Definition 16

1.7.2 Mutual Information: Properties 17

1.8 Capacity of a Discrete Channel 21

1.9 The Shannon Theorems 22

1.9.1 Source Coding Theorem 22

1.9.2 Channel Capacity and Coding 23

1.9.3 Channel Coding Theorem 25

1.10 Signal Spaces and the Channel Coding Theorem 27

1.10.1 Capacity of the Gaussian Channel 28

1.11 Error-Control Coding 32

1.12 Limits to Communication and their Consequences 34

Bibliography and References 38

Problems 38

vii

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

viii Contents

2 Block Codes 41

2.1 Error-Control Coding 41

2.2 Error Detection and Correction 41

2.2.1 Simple Codes: The Repetition Code 42

2.3 Block Codes: Introduction and Parameters 43

2.4 The Vector Space over the Binary Field 44

2.4.1 Vector Subspaces 46

2.4.2 Dual Subspace 48

2.4.3 Matrix Form 48

2.4.4 Dual Subspace Matrix 49

2.5 Linear Block Codes 50

2.5.1 Generator Matrix G 51

2.5.2 Block Codes in Systematic Form 52

2.5.3 Parity Check Matrix H 54

2.6 Syndrome Error Detection 55

2.7 Minimum Distance of a Block Code 58

2.7.1 Minimum Distance and the Structure of the H Matrix 58

2.8 Error-Correction Capability of a Block Code 59

2.9 Syndrome Detection and the Standard Array 61

2.10 Hamming Codes 64

2.11 Forward Error Correction and Automatic Repeat ReQuest 65

2.11.1 Forward Error Correction 65

2.11.2 Automatic Repeat ReQuest 68

2.11.3 ARQ Schemes 69

2.11.4 ARQ Scheme Efficiencies 71

2.11.5 Hybrid-ARQ Schemes 72

Bibliography and References 76

Problems 77

3 Cyclic Codes 81

3.1 Description 81

3.2 Polynomial Representation of Codewords 81

3.3 Generator Polynomial of a Cyclic Code 83

3.4 Cyclic Codes in Systematic Form 85

3.5 Generator Matrix of a Cyclic Code 87

3.6 Syndrome Calculation and Error Detection 89

3.7 Decoding of Cyclic Codes 90

3.8 An Application Example: Cyclic Redundancy Check Code for the Ethernet Standard 92

Bibliography and References 93

Problems 94

4 BCH Codes 97

4.1 Introduction: The Minimal Polynomial 97

4.2 Description of BCH Cyclic Codes 99

4.2.1 Bounds on the Error-Correction Capability of a BCH Code: The Vandermonde

Determinant 102

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

Contents ix

4.3 Decoding of BCH Codes 104

4.4 Error-Location and Error-Evaluation Polynomials 105

4.5 The Key Equation 107

4.6 Decoding of Binary BCH Codes Using the Euclidean Algorithm 108

4.6.1 The Euclidean Algorithm 108

Bibliography and References 112

Problems 112

5 Reed–Solomon Codes 115

5.1 Introduction 115

5.2 Error-Correction Capability of RS Codes: The Vandermonde Determinant 117

5.3 RS Codes in Systematic Form 119

5.4 Syndrome Decoding of RS Codes 120

5.5 The Euclidean Algorithm: Error-Location and Error-Evaluation Polynomials 122

5.6 Decoding of RS Codes Using the Euclidean Algorithm 125

5.6.1 Steps of the Euclidean Algorithm 127

5.7 Decoding of RS and BCH Codes Using the Berlekamp–Massey Algorithm 128

5.7.1 B–M Iterative Algorithm for Finding the Error-Location Polynomial 130

5.7.2 B–M Decoding of RS Codes 133

5.7.3 Relationship Between the Error-Location Polynomials of the Euclidean and

B–M Algorithms 136

5.8 A Practical Application: Error-Control Coding for the Compact Disk 136

5.8.1 Compact Disk Characteristics 136

5.8.2 Channel Characteristics 138

5.8.3 Coding Procedure 138

5.9 Encoding for RS codes CRS(28, 24), CRS(32, 28) and CRS(255, 251) 139

5.10 Decoding of RS Codes CRS(28, 24) and CRS(32, 28) 142

5.10.1 B–M Decoding 142

5.10.2 Alternative Decoding Methods 145

5.10.3 Direct Solution of Syndrome Equations 146

5.11 Importance of Interleaving 148

Bibliography and References 152

Problems 153

6 Convolutional Codes 157

6.1 Linear Sequential Circuits 158

6.2 Convolutional Codes and Encoders 158

6.3 Description in the D-Transform Domain 161

6.4 Convolutional Encoder Representations 166

6.4.1 Representation of Connections 166

6.4.2 State Diagram Representation 166

6.4.3 Trellis Representation 168

6.5 Convolutional Codes in Systematic Form 168

6.6 General Structure of Finite Impulse Response and Infinite Impulse Response FSSMs 170

6.6.1 Finite Impulse Response FSSMs 170

6.6.2 Infinite Impulse Response FSSMs 171

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

x Contents

6.7 State Transfer Function Matrix: Calculation of the Transfer Function 172

6.7.1 State Transfer Function for FIR FSSMs 172

6.7.2 State Transfer Function for IIR FSSMs 173

6.8 Relationship Between the Systematic and the Non-Systematic Forms 175

6.9 Distance Properties of Convolutional Codes 177

6.10 Minimum Free Distance of a Convolutional Code 180

6.11 Maximum Likelihood Detection 181

6.12 Decoding of Convolutional Codes: The Viterbi Algorithm 182

6.13 Extended and Modified State Diagram 185

6.14 Error Probability Analysis for Convolutional Codes 186

6.15 Hard and Soft Decisions 189

6.15.1 Maximum Likelihood Criterion for the Gaussian Channel 192

6.15.2 Bounds for Soft-Decision Detection 194

6.15.3 An Example of Soft-Decision Decoding of Convolutional Codes 196

6.16 Punctured Convolutional Codes and Rate-Compatible Schemes 200

Bibliography and References 203

Problems 205

7 Turbo Codes 209

7.1 A Turbo Encoder 210

7.2 Decoding of Turbo Codes 211

7.2.1 The Turbo Decoder 211

7.2.2 Probabilities and Estimates 212

7.2.3 Symbol Detection 213

7.2.4 The Log Likelihood Ratio 214

7.3 Markov Sources and Discrete Channels 215

7.4 The BCJR Algorithm: Trellis Coding and Discrete Memoryless Channels 218

7.5 Iterative Coefficient Calculation 221

7.6 The BCJR MAP Algorithm and the LLR 234

7.6.1 The BCJR MAP Algorithm: LLR Calculation 235

7.6.2 Calculation of Coefficients γi(u

, u) 236

7.7 Turbo Decoding 239

7.7.1 Initial Conditions of Coefficients αi−1(u

) and βi(u) 248

7.8 Construction Methods for Turbo Codes 249

7.8.1 Interleavers 249

7.8.2 Block Interleavers 250

7.8.3 Convolutional Interleavers 250

7.8.4 Random Interleavers 251

7.8.5 Linear Interleavers 253

7.8.6 Code Concatenation Methods 253

7.8.7 Turbo Code Performance as a Function of Size and Type of Interleaver 257

7.9 Other Decoding Algorithms for Turbo Codes 257

7.10 EXIT Charts for Turbo Codes 257

7.10.1 Introduction to EXIT Charts 258

7.10.2 Construction of the EXIT Chart 259

7.10.3 Extrinsic Transfer Characteristics of the Constituent Decoders 261

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

Contents xi

Bibliography and References 269

Problems 271

8 Low-Density Parity Check Codes 277

8.1 Different Systematic Forms of a Block Code 278

8.2 Description of LDPC Codes 279

8.3 Construction of LDPC Codes 280

8.3.1 Regular LDPC Codes 280

8.3.2 Irregular LDPC Codes 281

8.3.3 Decoding of LDPC Codes: The Tanner Graph 281

8.4 The Sum–Product Algorithm 282

8.5 Sum–Product Algorithm for LDPC Codes: An Example 284

8.6 Simplifications of the Sum–Product Algorithm 297

8.7 A Logarithmic LDPC Decoder 302

8.7.1 Initialization 302

8.7.2 Horizontal Step 302

8.7.3 Vertical Step 304

8.7.4 Summary of the Logarithmic Decoding Algorithm 305

8.7.5 Construction of the Look-up Tables 306

8.8 Extrinsic Information Transfer Charts for LDPC Codes 306

8.8.1 Introduction 306

8.8.2 Iterative Decoding of Block Codes 310

8.8.3 EXIT Chart Construction for LDPC Codes 312

8.8.4 Mutual Information Function 312

8.8.5 EXIT Chart for the SND 314

8.8.6 EXIT Chart for the PCND 315

8.9 Fountain and LT Codes 317

8.9.1 Introduction 317

8.9.2 Fountain Codes 318

8.9.3 Linear Random Codes 318

8.9.4 Luby Transform Codes 320

8.10 LDPC and Turbo Codes 322

Bibliography and References 323

Problems 324

Appendix A: Error Probability in the Transmission of Digital Signals 327

Appendix B: Galois Fields GF(q) 339

Answers to Problems 351

Index 357

OTE/SPH OTE/SPH

JWBK102-FM JWBK102-Farrell June 19, 2006 18:0 Char Count= 0

xii