Foundations of Coding E-Book

Jean-Guillaume Dumas

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

Seitenzahl: 616

Veröffentlichungsjahr: 2015

Beschreibung

Offers a comprehensive introduction to the fundamental structures and applications of a wide range of contemporary coding operations

This book offers a comprehensive introduction to the fundamental structures and applications of a wide range of contemporary coding operations. This text focuses on the ways to structure information so that its transmission will be in the safest, quickest, and most efficient and error-free manner possible. All coding operations are covered in a single framework, with initial chapters addressing early mathematical models and algorithmic developments which led to the structure of code. After discussing the general foundations of code, chapters proceed to cover individual topics such as notions of compression, cryptography, detection, and correction codes. Both classical coding theories and the most cutting-edge models are addressed, along with helpful exercises of varying complexities to enhance comprehension. 

• Explains how to structure coding information so that its transmission is safe, error-free, efficient, and fast
• Includes a pseudo-code that readers may implement in their preferential programming language
• Features descriptive diagrams and illustrations, and almost 150 exercises, with corrections, of varying complexity to enhance comprehension

Foundations of Coding: Compression, Encryption, Error-Correction is an invaluable resource for understanding the various ways information is structured for its secure and reliable transmission in the 21st-century world.

Leseprobe

Table of Contents

Cover

Title Page

Copyright

List of Figures, Tables, Algorithms and Acronyms

Foreword

Introduction

Chapter 1: Foundations of Coding

1.1 From Julius Caesar to Telecopy

1.2 Stream Ciphers and Probabilities

1.3 Block Ciphers, Algebra, and Arithmetic

1.4 Decoding, Decryption, Attacks

Chapter 2: Information Theory and Compression

2.1 Information Theory

2.2 Statistical Encoding

2.3 Heuristics of Entropy Reduction

2.4 Common Compression Codes

2.5 Lossy Compression

Chapter 3: Cryptology

3.1 General Principles

3.2 Secret Key Cryptography

3.3 Key Exchange

3.4 Public Key Cryptography

3.5 Authentication, Integrity, Nonrepudiation, Signatures

3.6 Key Management

Chapter 4: Error Detection and Correction

4.1 Principle of Error Detection and Error Correction

4.2 Error Detection by Parity—CRC Codes

4.3 Distance of a Code

4.4 Linear Codes and Cyclic Codes

4.6 Convolutional Codes and Turbo Codes

Compression, Encryption, Correction: As a Conclusion

Problem Solutions

Solutions for Chapter 1

Solutions for Chapter 2

Solutions for Chapter 3

Solutions for Chapter 4

SOLUTION FOR THE “CASINO” EXERCISE

Bibliography

Index

End User License Agreement

Pages

xvii

xviii

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

Guide

Cover

Table of Contents

Foreword

Introduction

Chapter 1: Foundations of Coding

List of Illustrations

Figure I.2

Figure 1.1

Figure 1.2

Figure 1.3

Figure 1.4

Figure 1.5

Figure 1.6

Figure 1.7

Figure 1.8

Figure 1.9

Figure 1.10

Figure 1.11

Figure 1.12

Figure 1.13

Figure 1.14

Figure 1.15

Figure 1.16

Figure 1.17

Figure 1.18

Figure 1.19

Figure 1.20

Figure 1.21

Figure 2.1

Figure 2.2

Figure 2.3

Figure 2.4

Figure 2.5

Figure 2.6

Figure 2.7

Figure 2.8

Figure 2.9

Figure 2.10

Figure 2.11

Figure 3.1

Figure 3.2

Figure 3.3

Figure 3.4

Figure 3.5

Figure 3.6

Figure 3.7

Figure 3.8

Figure 3.9

Figure 3.10

Figure 3.11

Figure 3.12

Figure 3.13

Figure 3.14

Figure 3.15

Figure 3.16

Figure 3.17

Figure 3.18

Figure 3.19

Figure 3.20

Figure 3.21

Figure 3.22

Figure 3.23

Figure 3.24

Figure 3.25

Figure 3.26

Figure 3.27

Figure 3.33

Figure 3.28

Figure 3.29

Figure 3.30

Figure 3.31

Figure 3.32

Figure 3.34

Figure 3.35

Figure 4.1

Figure 4.2

Figure 4.3

Figure 4.4

Figure 4.5

Figure 4.8

Figure 4.9

Figure 4.10

Figure 4.11

Figure 4.12

Figure 3

List of Tables

Table 1.1

Table 1.2

Table 1.3

Table 1.4

Table 1.5

Table 1.6

Table 1.7

Table 1.8

Table 1.9

Table 2.1

Table 2.2

Table 2.3

Table 2.4

Table 2.5

Table 3.1

Table 3.2

Table 3.3

Table 3.4

Table 3.5

Table 3.6

Table 3.7

Table 3.8

Table 3.9

Table 3.10

Table 3.11

Table 3.12

Table 3.13

Table 3.14

Table 3.15

Table 4.1

Table 4.2

Table 4.3

Table 4.4

Table 4.5

Table 4.6

Table 4.7

Table 2

Foundations of Coding

Compression, Encryption, Error Correction

Jean-Guillaume Dumas

Université de Grenoble

Jean-Louis Roch

Université de Grenoble

Éric Tannier

Inria, Université de Lyon

Sébastien Varrette

Université du Luxembourg

Copyright © 2015 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

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 as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Dumas, Jean-Guillaume.

Foundations of coding : compression, encryption, errorcorrection / Jean-Guillaume Dumas, Jean-Louis Roch, Eric Tannier, Sebastien Varrette.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-88144-6 (cloth)

1. Coding theory. I. Roch, Jean-Louis (Mathematician) II. Tannier, Eric. III. Varrette, Sebastien. IV. Title.

TK5102.92.D86 2015

003′.54–dc23

2014039504

List of Figures, Tables, Algorithms and Acronyms

List of Figures

I.1 Fundamental coding scheme

I.2 Notions introduced in Chapter 1

1.1 Spartan Scytale principle to transmit the text “ HELLOWORLD”

1.2 Bitwise encryption (Stream cipher)

1.3 Block ciphers: ECB mode

1.4 Block ciphers: CBC mode

1.5 Block ciphers: CFB mode

1.6 Block ciphers: OFB mode

1.7 Block ciphers: CTR mode

1.8 Principle of a one-way function

1.9 (a) Elliptic curve addition and (b) doubling on

1.10 Functional diagram of an LFSR

1.11 Bluetooth encryption

1.12 Example of a Huffman tree

1.13 Principle of a hash function

1.14 Compression function of a hash function

1.15 Merkle–Damgård construction

1.16 Davies–Meyer construction

1.17 Miyaguchi–Preneel construction

1.18 Fourier transform

1.19 Discrete Fourier Transform (DFT)

1.20 Discrete Cosine Transform (DCT)

1.21 Floyd's cycle detection, in the form of a rho

2.1 Huffman encoding: beginning of the algorithm

2.2 Huffman's encoding: first step ()

2.3 Example of a construction of the Huffman code

2.4 Fax code

2.5 BWT on COMPRESSED

2.6 bzip2

2.7 The RGB image with white background (here in gray-levels)

2.8 JPEG zigzag scan

2.9 JPEG compression

2.10 MPEG-1 compression

2.11 MP3 sound compression

3.1 Fundamental relation of cryptography

3.2 Principle of an integrity checking algorithm

3.3 Principle of symmetric cryptography

3.4 Stream cipher

3.5 Block cipher

3.6 One round of DES

3.7 DES: Function f

3.8 DES key derivation

3.9 Matricial representation of a 16-byte block

3.10 SubBytes operation in AES

3.11 ShiftRows stage in AES

3.12 MixColumns operation in AES

3.13 KeySchedule operation in AES

3.14 Representation of the expanded key W as a sequence of columns

3.15 Kerberos authentication steps

3.16 Principle of public key encryption

3.17 History of the main hash functions

3.18 Rounds 1, 2, 3, and 4 in MD5 ()

3.19 Round i in SHA-1 ()

3.20 Keccak's sponge construct (SHA-3)

3.21 Integrity check with hash functions using a secure channel

3.22 Integrity check with hash functions using an encryption function

3.23 Optimal Asymmetric Encryption Padding (OAEP)

3.24 Principle of the use of an MAC

3.25 MAC using symmetric encryption

3.26 Principle of public key signatures and verification

3.27 Principle of the creation of certificates

3.28 Issuing a certificate

3.29 Generation and content of an X.509 certificate

3.30 Verification of certificate and public key extraction

3.31 PKI model for X-509 certificates

3.32 Authenticated registration

3.33 Authentication via public key cryptography

3.34 An example of the PGP trust

3.35 Format of an SSH packet

4.1 Binary Symmetric Channel (BSC) with error probability p

4.2 The EAN-128 code for foundations of coding

4.3 Example of a (10,5) regular LDPC code and its representation by a Tanner graph. The six bold edges show a length-6 cycle in the graph

4.4 Example of the bit-flipping decoding over the Hamming code (7,4) for the received word when the codeword has been transmitted. (a) Step 2: parity checks, (b) step 3: codeword update, and (c) stopping criteria (success)

4.5 Illustration of the extrinsic information passed to compute the messages (a, step 2) and (b, step 3)

4.6 QR-code and pattern locations

4.7 3-L, , QR-code for http://foundationsofcoding.imag.fr

4.8 State diagram of the convolutional code of generator polynomials and

4.9 Lattice of the convolutional code generated by and

4.10 Systematic convolutional code of constraint length 3 transformed into a RSC code

4.11 Parallel composition and interleaving of two RSC encoders

4.12 Iterative decoding of a turbo code

1 Encoding of a message M

2 Decoding of a message

3 Viterbi's algorithm on the message 10010010011101111010

List of Tables

1.1 Letter Distribution in this LaTeX Script

1.2 Typical Complexity Bounds Obtained from an Algorithm Analysis

1.3 Extract of the ASCII Code

1.4 Zech's Construction on Invertible Elements in Odd Characteristic

1.5 Discrete Logarithm and Exponentiation in Finite Fields and Generic Groups

1.6 Group Laws in Characteristics 2 and 3 with and

1.7 Table (Extract)

1.8 Distribution of the Multiples of p Modulo m

1.9 Quadratic Sieve for

2.1 Arithmetic Encoding of “bebecafdead”

2.2 Arithmetic Decoding of “0.15633504500”

2.3 Integer Arithmetic Encoding of “bebecafdead”

2.4 Integer Arithmetic Decoding of “156335043840”

2.5 Comparison of the Compression of an Email File (15.92 Mo: Text, Images, Programs, etc.) with Several Algorithms, on a PIV 1.5 GHz

3.1 Frequency of the Letters in French

3.2 Frequency Analysis of the Ciphertext

3.3 Rabbit Stream Internal State Evolution and Bit Extraction

3.4 Complexities of Cryptanalysis Methods on DES

3.5 Cost and Efficiency of Attacks on DES in 1996

3.6 Performance of Several Block Ciphers

3.7 Configurations for AES

3.8 Value of the Shift According to the Value of in ShiftRows

3.9 Man-in-the-Middle Attack on the Diffie–Hellman Protocol

3.10 Sending of a Message Intercepted by the Man-in-the-Middle

3.11 Frequential Repartition of Symbols in a Text Written in French

3.12 Conjectured Compared Security of Block Ciphers

3.13 Main Differences between W and Rijndael

3.14 SHA-3 Candidates Speed (Cycles/Byte) on an Intel i7

3.15 Resistance to Collisions for the Most Famous Hash Functions

4.1 Order of Magnitude of Raw Error Rates

4.2 Encoding with a Parity Bit

4.3 Error Correction using Parity Bits

4.4 Examples of CRC Codes

4.5 Comparison of MPAs

4.6 Initial Interleaving Table with Delay 2 for Codewords of Length 5

4.7 Interleaving Table with Delay 2 After One Round

1 Several Primitive Polynomials in

2 Die Simulation by Coin Toss

List of Algorithms

1.1 Simplified Fax Encoding for a Line of Pixels

1.2 Fax Decoding for a Decrypted and Checked Line

1.3 GCD: Euclidean Algorithm

1.4 GCD: Extended Euclidean Algorithm

1.5 Modular Exponentiation

1.6 Miller--Rabin Primality Test

1.7 Horner Polynomial Evaluation

1.8 Ben-Or's Irreducibility Test

1.9 Generation of a sparse irreducible polynomial

1.10 Test Primitive Root

1.11 Test Generator Polynomial

1.12 Discrete Fast Fourier Transform

1.13 Fast product of two polynomials

1.14 Berlekamp--Massey Algorithm

1.15 Yuval's birthday attack

1.16 Pollard's Factoring

1.17 Lenstra's elliptic curve factoring

1.18 Gordon's algorithm

2.1 Description of Huffman's Algorithm

2.2 Arithmetic Encoding

2.3 Arithmetic Decoding

2.4 Dynamic Huffman Algorithm: Compression

2.5 Dynamic Huffman's Algorithm Decompression

2.6 Inverse of BWT

2.7 LZW: compression

2.8 LZW: decompression

3.1 AES Encryption

3.2 Key Schedule in AES

3.3 GCM

3.4 Shamir's Trick for Simultaneous Double-And-Add

4.1 Hard-Decision Decoder by Bit-Flipping Algorithm

4.2 Generic BPA for LDPC Code Decoding

4.3 Decoding of a Reed-Solomon code

4.4 Viterbi's Algorithm (Decoding of Convolutional Codes)

1 AES Decryption

2 Factoring n from (n,e,d) in RSA (Special Case: e is Small)

3 Factoring n from (n,e,d) in RSA

4 RSA Cryptographic Pseudo-Random Generator

5 Repetition Code Decoding with Maximum Detection

6 Repetition Code Decoding with Maximum Correction

7 Repetition Code Decoding with Detection and Correction

8 Minimum Distance of a Code (|V|=2)

acronym

ADSL Asymmetric Digital Subscriber Line

AES Advanced Encryption Standard

AKS Agrawal--Kayal--Saxena

APP A posteriori probability

ARQ Automatic Repeat reQuest

BBAN Basic Bank Account Number

BCH Bose--Chaudhuri--Hocquenghem

BEC Binary Erasure Channel

BI-AWGNC Binary-input Additive White Gaussian Noise Channel

BPA Belief Propagation Algorithm

BSC Binary Symmetric Channel

BWT Burrows--Wheeler Transform

CA Certification Authority

CAIN Confidentiality, Authentication, Integrity, Nonrepudiation

CBC Cipher Block Chaining

CFB Cipher FeedBack

CIRC Cross-Interleaved Reed--Solomon Code

CML Coded Modulation Library

CRC Cyclic Redundancy Checks

CRL Certification Revocation List

CSS Content Scrambling System

CTR Counter Mode Encryption

CVV Card Verification Value

DCT Discrete Cosine Transform

DDF Distinct Degree Factorization

DES Data Encryption Standard

DFT Discrete Fourier Transform

DLP Discrete Logarithm Problem

DRM Digital Right Management

DSS Digital Signature Standard

DVB Digital Video Broadcasting

ECB Electronic Code Book

ECC Elliptic Curve Cryptography

ECDSA Elliptic Curve Digital Signature Algorithm

GCD Greatest Common Divisor

GCM Galois Counter Mode

GIF Graphics Interchange Format

GSM Global System for Mobile Communications

HDD Hard Disk Drives

JPEG Joint Photographic Experts Group

JPSEC Secure JPEG-2000

KDC Key Distribution Center

LCG Linear Congruential Generator

LDPC Low Density Parity Check

LFSR Linear Feedback Shift Register

LLR log-Likelihood Ratio

LR Likelihood Ratio

LZ77 Lempel-Ziv 1977

LZ78 Lempel-Ziv 1978

LZAP Lempel-Ziv All Prefixes

LZMA Lempel--Ziv--Markov-chain Algorithm

LZMW Lempel-Ziv-Miller-Wegman

LZO Lempel-Ziv-Oberhumer

LZW Lempel-Ziv-Welch

MAC Message Authentication Code

MD5 Message-Digest Algorithm 5

MDC Manipulation Detection Code

MDD Minimum Distance Decoding

MDS Maximum Distance Separable

MGF Mask Generating Function

MLD Maximum Likelihood Decoding

MPA Message Passing Algorithm

MPEG Motion Picture Experts Group

NESSIE New European Schemes for Signatures, Integrity, and Encryption

NIST National Institute of Standards and Technology

NSC Nonsystematic Convolutional code

OAEP Optimal Asymmetric Encryption Padding

OFB Output FeedBack

PGP Pretty Good Privacy

PKI Public Key Infrastructure

PKIX Public Key Infrastructure for X.509 certificates

PNG Portable Network Graphics

PRNG Pseudo-Random Number Generators

QR-code Quick Response code

RA Registration Authority

RAID Redundant Array of Independent Disks

RLE Run-Length Encoding

RSA Rivest--Shamir--Adleman

RSC Recursive Systematic Convolutional codes

RGB Red/Green/Blue

SDSI Simple Distributed Security Infrastructure

SHA Secure Hash Algorithm

SPA Sum-Product Algorithm

SPKI Simple Public Key Infrastructure

SSD Solid-State Drives

SSH Secure SHell

SSL Secure Sockets Layer

TA Trusted Authority

TGS Ticket Granting Service

TLS Transport Layer Security

UHF Ultra High Frequency

UMTS Universal Mobile Telecommunications System

UPC-A Universal Product Code

YUV Luminance/Chrominance color space

ZOI Zone of Influence

Foreword

This work has been initiated in spring 2000 with the creation of the joint ENSIMAG-ENSERG Telecommunication department at the National Polytechnic Institute of Grenoble (INPG–France) and the setting up of a general course (last year French Licence level in the Licence-Master-Doctorate scheme) providing an introduction to codes and their applications.

Although it was initially published as a handout, it evolved and became reference material for several courses in Grenoble universities–both in the INPG and in the Joseph Fourier University (UJF) at the master level.

We take this occasion to thank our colleagues who participated in these courses and helped us improve our material with their remarks: Gilles Debunne, Yves Denneulin, Dominique Duval, Grégory Mounié and Karim Samaké.

In 2007, a book was published in French by Dunod editions in their mathematics and computer science collection. It was then reprinted, with a few amendments, in the beginning of 2009, and edited in an augmented version in 2013.

Éric Bourre, Cécile Canovas-Dumas, Mélanie Favre, Françoise Jung, Madeline Lambert, Benjamin Mathon, Marie-Aude Steineur, and Antoine Taveneaux participated to these first two editions by reading the drafts and spotting some mistakes.

This English edition was started in 2009, when our colleagues Rodney Coleman and Romain Xu undertook the task of translating the 352 pages of the French edition in English. Let them be gratefully thanked here.

Compared to this translation, this book has been revised and significantly augmented (20% additional pages and 27 new exercises). We now cover modern and frequently used techniques, as elliptic curves, low density codes, or matrix bar-codes as well as new standards like the eSTREAM portfolio, Galois hashing and counter mode, and the new standard hashing algorithm 3, Keccak. In addition, we have updated several parts, including steganography and watermarking, maximum likelihood decoding, saturation attacks (on AES), and postquantum cryptography.

“Foundations of Coding: Compression, Encryption, Error Correction” comes now with a companion website http://foundationsofcoding.imag.fr. This web site provides access to tools, resources, and news about the book, and, more generally, about security. In particular, we propose interactive solutions to several exercises via worksheets, using the free mathematical software Sage.

Grenoble, Lyon, Luxembourg

Jean-Guillaume Dumas, Jean-Louis Roch,

Éric Tannier, Sébastien Varrette.

Introduction

This work is aimed at providing a textbook for master students in applied mathematics or computer science. It can be used as a reference book by teachers, researchers, or companies involved in telecommunication or information security. The book is, to a certain extent, self-contained, that is, all used concepts are introduced. However, some training in algebra, algorithmics, and probability theory will be helpful. Indeed, the originality of this book is to present fundamental structures and applications, covering all coding operations, in a single framework.

The subject is the automatic transmission of numerical information. We will focus on the structure of information, without regarding the type of transmission support. Information can be of any kind as long as we can give a numerical representation of it: for example texts, images, sounds, and videos. Transmission of this type of data is ubiquitous in technology, especially in telecommunications. Hence, it is necessary to rely on solid bases for that transmission to be reliable, the term “reliable” having several different meanings depending on the objectives that will guide us throughout this book.

Transmission channels can also be of any kind (wirenets or wavenets), possibly through data storage. We will not consider the physical issues coming with transmission, which are the subjects of the theory known as “ signal” theory. “ Coding” deals with information itself when it is meant to be transmitted or stored.

Figure I.1 Fundamental coding scheme

Communication of a piece of information begins with a sender writing it, goes on with its transmission through a channel and ends with the reconstruction of the message by the recipient. Sometimes, the sender is also the recipient: it is the case of a processor or a person saving data in a register, a memory, or a disk and reading it later on. Information has to be fully, safely, and quickly transmitted to its recipient. However, whatever the channel may be, with variations depending on the support, it can never be considered “ safe” in several ways: errors can appear during transmissions, and the message is likely to be read, and even modified, by a potentially malicious third party.

It is up to the sender to compose his messages in a form that allows the recipient to reconstruct them—considering potential alterations during the transfer or confidentiality of some information—while minimizing the size of data.

These constraints are the starting points of several fields in mathematics and computing that are often developed separately although they deal with the same subject. The purpose of this book is to gather them into one volume and to present a single theory whose subject is the form given to information during its transmission, namely a general coding theory.

In 1948, Claude Shannon layed the foundation stone of what he called a “ mathematical theory of communication.” It is said that his theory began with his comments on natural languages: Shannon used to hide some parts of the text he was reading and to recover them from the visible part. When removing a few words, he was able to determine the meaning of a sentence with absolute certainty. Actually, the hidden words were redundant, they did not add anything to the meaning of the message. If he removed too many words, he was unable to guess the message with certainty. Then Shannon developed a theory that would allow one to calculate the “ amount of information” of any kind of message, hence the determination of a redundancy rate.

Nowadays, the operation of reducing redundancy is called compression or “ information theory.” Here, we are not only looking for efficiency in terms of optimization of the storage space but mainly in terms of transmission speed: we are interested in having the shortest message by keeping only what is necessary, or even better, reformulating it without redundancy.

Another and older concern in the transmission of a piece of information is confidentiality. Assuming that roads (as well as numerical channels) are not safe—and that a message can be intercepted during the transmission—the text has to be transformed, uncorrelated from its signification, while guaranteeing that only its recipients are given the decryption keys. The history of societies and nations is full of secret code stories and battles between code inventors and code breakers (who wanted to recover the meaning of the message without knowing the key). Shannon also contributed in this field by giving the first theoretical proof of confidentiality in 1949.

Today, a scientific discipline is dedicated to secret codes—cryptology. Not only do current techniques guarantee the secrecy of a message, but they also allow one tosign documents and identify a sender.

In addition to ill-intentioned third parties, all channels that are used in transmission of numerical information can suffer from perturbations that are likely to alter some parts of the messages, hence to modify their meaning. If the information is sent without redundancy, the least significant modification can lead to misunderstandings once at destination. As for natural languages, most of the errors will not alter the perception of the reader because redundancy will allow him to recover the initial message. Once again, Shannon presented a revolutionary result in 1948: even on channels with high error rate, it is still possible to add enough redundancy so that the message will be entirely received. But the proof is not constructive and this theorem keeps motivating the development of methods including ordered and optimized redundancy for the recipient to be able to detect modifications of the message (detection codes) and to correct potential errors himself (correction codes). All these methods are customizable—flexible—depending on the kind of support considered and its error rate.

Efficiency, security, and integrity are the three concerns for developers of information transmission methods. This book tackles those issues in one single volume through their common object—the code—which is used to structure the information on all current technological support.

The general theory of codes is based on a background coming from linear algebra, arithmetic, probability theory, algorithmic, and combinatorial analysis. In the first chapter of this book, we will present the mathematical models and the first algorithmic developments that structure the notion of code. The presentation of these models includes some introduction to useful mathematical concepts for the manipulation of codes, as well as general notions on the efficiency of calculation methods, which will be frequently used throughout the present work. Reading this chapter will require a basic theoretical knowledge of linear algebra (a first course in this field should be sufficient). Some elements go beyond the standard knowledge of nonmathematician students and are presented in detail here. The reader will soon be aware of their real practical importance, most of the time during their very introduction. Figure I.2 clarifies the usefulness of these notions and the dependencies between them.

Figure I.2 Notions introduced in Chapter 1

As linear reading is not necessary, this scheme will also allow a reader in a hurry – or only interested in a specific part of this book—to quickly find his way. Although the first chapter is meant to introduce the foundations of coding, it can also be used as a reference toolbox during the reading of the following chapters. Those chapters deal with the notions of compression, cryptography, detection, and correction codes separately. They present the fundamental theoretical results and the algorithms that follow from them. Each chapter is illustrated with concrete examples and training exercises in the field of telecommunications. We have striven to present both classical coding theories and the most recent developments dealing with them as far as such an introductory book allow us to.

Not only does this book gathers mathematical theories sharing the same subject, but its creed is also algorithmic. Here, the mathematical properties of the functions are used in order to make their calculation efficient. Computation methods are always detailed and can be immediately implemented in any programming language. Efficiency of the methods is always stated and debated. Existing implementations are compared.

These sciences are derived from both Greek mathematics—whose quality was based on their aesthetic nature—and oriental mathematics—which focused on usefulness and calculation. This is what can also bring together the foundations of coding, and one of their greatest merit is to call upon rigorous mathematics—which are appreciated by aesthetes—in order to build efficient methods applied to common communications. Hence, this book is at the confluence of these rivers and will attract technology and number theory enthusiasts, as well as all those whose imagination is still fired by stories of decryption of arcane languages, machines that correct their own errors and secret codes.

1Foundations of Coding

This first chapter is an introduction to the notion of code. It contains the mathematical background, necessary to manipulate the codes, and the coding operations. Through this chapter, the reader will understand the constraints of the transmission of information, starting from historical examples and eventually learning advanced techniques. The knowledge of some historical aspects is pedagogically useful to work first on simple structures. In cryptology, history is also essential for efficient protection against the whole range of known attacks.

The principle is always to start from examples of codes, showing step by step why some mathematical notions are useful so that the codes are short, safe, and efficient. While the following chapters describe recent, elaborate, and currently used protocols for coding, this chapter provides the foundations of this activity.

Simple objects from probability theory, algebra, or algorithmic are introduced along the lines of this chapter, when they become necessary. For example, block coding calls for the definition of structures in which elements can be added, multiplied, which justifies the introduction of groups and fields. The emphasis is always put on the effective construction of introduced structures. This calls for a section on algorithms, as well as polynomials and primitive roots.

This chapter is organized in four sections. The first three allow to focus on the three important mathematical notions related to coding: algorithms and their complexity, which is at the core of coding theory; probabilities, related to stream cipher; and algebra, related to block coding. Then, the last section of this chapter is devoted to the many facets of decoding, from ambiguity and information loss to secret code breaking.