Foundations of Coding
Compression, Encryption, Error Correction
1st Edition
Published on 17. February 2015
Book
Hardback
384 pages
978-1-118-88144-6 (ISBN)
Description
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.
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.
More details
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Dimensions
Height: 236 mm
Width: 160 mm
Thickness: 25 mm
Weight
658 gr
ISBN-13
978-1-118-88144-6 (9781118881446)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
Jean-Guillaume Dumas | Jean-Louis Roch | Éric Tannier
Foundations of Coding
Compression, Encryption, Error Correction
E-Book
01/2015
Wiley
€99.99
Available for download
Jean-Guillaume Dumas | Jean-Louis Roch | Éric Tannier
Foundations of Coding
Compression, Encryption, Error Correction
E-Book
01/2015
Wiley
€97.99
Available for download
Persons
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.
ERIC 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.
SEBASTIEN 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.
JEAN-LOUIS ROCH is Associate Professor at the National Polytechnique Institute of Grenoble (INPG), and teaches security, coding theory, cryptology, parallelism, and algorithms.
ERIC 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.
SEBASTIEN 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.
Content
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
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