Foundations of Coding Compression, Encryption, Error Correction

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.

JEAN-GUILLAUME DUMAS is Professor at the University of Grenoble, where he teaches security, programming languages, cryptology, and computer algebra.

JEAN-LOUIS ROCH is Associate Professor at the National Polytechnique Institute of Grenoble (INPG), and teaches security, coding theory, cryptology, parallelism, and algorithms.

ÉRIC TANNIER is Research Associate at the National French Institute for Computer Science (INRIA). He works in computational biology in the Biometry and Evolutionary Biology Laboratory (LBBE) of the University of Lyon.

SÉBASTIEN VARRETTE is Research Associate at the University of Luxembourg. He works in the High Performance Computing (HPC) area, in particular as regards the security of distributed and/or parallel executions.

List of Figures, Tables, Algorithms and Acronyms ix

Foreword xvii

Introduction 1

1 Foundations of Coding 5

1.1 From Julius Caesar to Telecopy 6

1.1.1 The Source: from an Image to a Sequence of Pixels 6

1.1.2 Message Compression 7

1.1.3 Error Detection 8

1.1.4 Encryption 9

1.1.5 Decryption 9

1.1.6 Drawbacks of the Fax Code 11

1.1.7 Orders of Magnitude and Complexity Bounds for Algorithms 12

1.2 Stream Ciphers and Probabilities 15

1.2.1 The Vernam Cipher and the One-Time-Pad Cryptosystem 15

1.2.2 Some Probability 16

1.2.3 Entropy 18

1.2.4 Steganography and Watermarking 23

1.2.5 Perfect Secrecy 24

1.2.6 Perfect Secrecy in Practice and Kerckhoffs’ Principles 24

1.3 Block Ciphers, Algebra, and Arithmetic 26

1.3.1 Blocks and Chaining Modes from CBC to CTR 27

1.3.2 Algebraic Structure of Codewords 30

1.3.3 Bijective Encoding of a Block 35

1.3.4 Construction of Prime Fields and Finite Fields 43

1.3.5 Implementation of Finite Fields 52

1.3.6 Curves Over Finite Fields 57

1.3.7 Pseudo-Random Number Generators (PRNG) 62

1.4 Decoding, Decryption, Attacks 68

1.4.1 Decoding without Ambiguity 68

1.4.2 Noninjective Codes 73

1.4.3 Cryptanalysis 84

2 Information Theory and Compression 99

2.1 Information Theory 100

2.1.1 Average Length of a Code 100

2.1.2 Entropy as a Measure of the Amount of Information 101

2.1.3 Shannon’s Theorem 102

2.2 Statistical Encoding 104

2.2.1 Huffman’s Algorithm 104

2.2.2 Arithmetic Encoding 109

2.2.3 Adaptive Codes 114

2.3 Heuristics of Entropy Reduction 117

2.3.1 Run-Length Encoding (RLE) 117

2.3.2 Move-to-Front 119

2.3.3 Burrows–Wheeler Transform (BWT) 120

2.4 Common Compression Codes 122

2.4.1 Lempel–Ziv’s Algorithm and gzip Variants 123

2.4.2 Comparisons of Compression Algorithms 126

2.4.3 GIF and PNG Formats for Image Compression 127

2.5 Lossy Compression 128

2.5.1 Deterioration of Information 128

2.5.2 Transformation of Audiovisual Information 128

2.5.3 JPEG Format 129

2.5.4 Motion Picture Experts Group (MPEG) Format 133

3 Cryptology 136

3.1 General Principles 137

3.1.1 Terminology 137

3.1.2 What is the Use of Cryptography? 138

3.1.3 Main Types of Threats 139

3.2 Secret Key Cryptography 141

3.2.1 Principle of Symmetric Cryptography 141

3.2.2 Classes of Symmetric Encryption Schemes 143

3.2.3 Data Encryption Standard (DES) System 145

3.2.4 Rijndael: Advanced Encryption Standard (AES) 151

3.3 Key Exchange 161

3.3.1 Diffie–Hellman Protocol and Man-in-the-Middle Attacks 161

3.3.2 Kerberos: a Secret Key Provider 163

3.4 Public Key Cryptography 167

3.4.1 Motivations and Main Principles 167

3.4.2 Rivest–Shamir–Adleman (RSA) Encryption 169

3.4.3 El Gamal Encryption 174

3.5 Authentication, Integrity, Nonrepudiation, Signatures 175

3.5.1 Cryptographic Hash Functions 176

3.5.2 Public Key Authentication 186

3.5.3 Electronic Signatures 187

3.6 Key Management 192

3.6.1 Generation of Cryptographically Secure Bits 192

3.6.2 Public Key Infrastructure (PKI) 192

3.6.3 Securing Channels with the SSH Tool 203

4 Error Detection and Correction 209

4.1 Principle of Error Detection and Error Correction 211

4.1.1 Block Coding 211

4.1.2 A Simple Example of Parity Detection 211

4.1.3 Correction Using Longitudinal and Transverse Parity 212

4.1.4 Encoding, Decoding, and Probability of Error 213

4.1.5 Shannon’s Second Theorem 214

4.2 Error Detection by Parity – CRC Codes 218

4.2.1 Parity Check on Integers: ISBN, EAN, LUHN 218

4.2.2 Cyclic Redundancy Checks (CRC) 221

4.3 Distance of a Code 222

4.3.1 Error Correction Code and Hamming Distance 222

4.3.2 Equivalent Codes, Extended Codes, and Shortened Codes 227

4.3.3 Perfect Codes 229

4.3.4 Binary Hamming Codes 230

4.4 Linear Codes and Cyclic Codes 232

4.4.1 Linear Codes and Minimum Redundancy 232

4.4.2 Encoding and Decoding of Linear Codes 234

4.4.3 Low Density Parity Check (LDPC) Codes 238

4.4.4 Cyclic Codes 250

4.4.5 Bose–Chaudhuri–Hocquenghem (BCH) Codes 254

4.4.6 Optimal BCH Codes: Reed–Solomon Codes 256

4.5 Bursts of Errors and Interleaving 262

4.5.1 Packets of Errors 262

4.5.2 Interleaving 263

4.5.3 Interleaving with Delay and Interleaving Table 264

4.5.4 Cross-Interleaved codes 265

4.6 Convolutional Codes and Turbo Codes 268

4.6.1 Encoding by Convolution 268

4.6.2 Shortest Path Decoding 269

4.6.3 Turbo Codes 273

Compression, Encryption, Correction: As a Conclusion 277

Problem Solutions 281

Bibliography 343

Index 345

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.