Muutke küpsiste eelistusi

E-raamat: Fundamentals of Classical and Modern Error-Correcting Codes

, (University of California, Davis)
  • Formaat: PDF+DRM
  • Ilmumisaeg: 09-Dec-2021
  • Kirjastus: Cambridge University Press
  • Keel: eng
  • ISBN-13: 9781009080569
Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 92,61 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Fundamentals of Classical and Modern Error-Correcting CodesSuurem pilt
  • Formaat: PDF+DRM
  • Ilmumisaeg: 09-Dec-2021
  • Kirjastus: Cambridge University Press
  • Keel: eng
  • ISBN-13: 9781009080569
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

"Using easy-to-follow mathematics, this textbook provides comprehensive coverage of block codes and techniques for reliable communications and data storage. It covers major code designs and constructions from geometric, algebraic, and graph-theoretic points of view, decoding algorithms, error control additive white Gaussian noise (AWGN) and erasure, and dataless recovery. It simplifies a highly mathematical subject to a level that can be understood and applied with a minimum background in mathematics, provides step-by-step explanation of all covered topics, both fundamental and advanced, and includes plenty of practical illustrative examples to assist understanding. Numerous homework problems are included to strengthen student comprehension of new and abstract concepts, and a solutions manual is available online for instructors. Modern developments, including polar codes, are also covered. An essential textbook for senior undergraduates and graduates taking introductory coding courses, students taking advanced full-year graduate coding courses, and professionals working on coding for communications and data storage"--

Arvustused

' masterfully provides a comprehensive treatment of both traditional codes as well as new and most promising coding families and decoding algorithms ' Bane Vasi, University of Arizona ' an excellent, unique, and valuable contribution to the teaching of the subject.' Ian Blake, University of British Columbia 'A highly readable introduction into the theory of block codes, including classical code constructions, an extensive treatment of LDPC codes, with emphasis on quasi-cyclic constructions, and an introduction to polar codes. Recommended for a beginning graduate course in coding, with enough material for either one or two semesters. Numerous examples and problems make the book very student friendly.' Daniel Costello, University of Notre Dame 'The book truly explains these highly mathematical subjects to a level that can be accessed and applied with as little background in mathematics as possible. It provides step-by-step explanation of all covered topics, both more theoretical or applied, and includes sufficient illustrative examples to assist understanding.' Nikolay Yankov, zbMATH

Muu info

An accessible textbook that uses step-by-step explanations, relatively easy mathematics and numerous examples to aid student understanding.
List of Figures
xiii
List of Tables
xxi
Preface xxv
Acknowledgments xxviii
1 Coding for Reliable Digital Information Transmission and Storage
1(24)
1.1 Introduction
2(2)
1.2 Categories of Error-Correcting Codes
4(2)
1.3 Modulation and Demodulation
6(2)
1.4 Hard-Decision and Soft-Decision Decodings
8(1)
1.5 Maximum A Posteriori and Maximum Likelihood Decodings
9(3)
1.6 Channel Capacity on Transmission Rate
12(1)
1.7 Classification of Channel Errors
13(1)
1.8 Error-Control Strategies
14(2)
1.9 Measures of Performance
16(2)
1.10 Contents of the Book
18(5)
References
23(2)
2 Some Elements of Modern Algebra and Graphs
25(64)
2.1 Groups
25(6)
2.1.1 Basic Definitions and Concepts
25(1)
2.1.2 Finite Groups
26(3)
2.1.3 Subgroups and Cosets
29(2)
2.2 Finite Fields
31(8)
2.2.1 Basic Definitions and Concepts
32(3)
2.2.2 Prime Fields
35(1)
2.2.3 Finite Fields with Orders of Prime Powers
36(3)
2.3 Polynomials over Galois Field GF(2)
39(4)
2.4 Construction of Galois Field GF(2m)
43(8)
2.5 Basic Properties and Structures of Galois Field GF(2m)
51(7)
2.6 Computations over Galois Field GF(2m)
58(1)
2.7 A General Construction of Finite Fields
59(1)
2.8 Vector Spaces over Finite Fields
60(7)
2.8.1 Basic Definitions and Concepts
60(2)
2.8.2 Vector Spaces over Binary Field GF(2)
62(5)
2.8.3 Vector Spaces over Nonbinary Field GF(q)
67(1)
2.9 Matrices over Finite Fields
67(11)
2.9.1 Concepts of Matrices over GF(2)
67(2)
2.9.2 Operations of Matrices over GF(2)
69(4)
2.9.3 Matrices over Nonbinary Field GF(q)
73(1)
2.9.4 Determinants
74(4)
2.10 Graphs
78(5)
2.10.1 Basic Definitions and Concepts
78(4)
2.10.2 Bipartite Graphs
82(1)
Problems
83(3)
References
86(3)
3 Linear Block Codes
89(36)
3.1 Definitions
89(1)
3.2 Generator and Parity-Check Matrices
90(6)
3.3 Systematic Linear Block Codes
96(3)
3.4 Error Detection with Linear Block Codes
99(3)
3.5 Syndrome and Error Patterns
102(1)
3.6 Weight Distribution and Probability of Undetected Error
103(2)
3.7 Minimum Distance of Linear Block Codes
105(4)
3.8 Decoding of Linear Block Codes
109(1)
3.9 Standard Array for Decoding Linear Block Codes
110(8)
3.9.1 A Standard Array Decoding
110(6)
3.9.2 Syndrome Decoding
116(2)
3.10 Shortened and Extended Codes
118(2)
3.11 Nonbinary Linear Block Codes
120(1)
Problems
120(3)
References
123(2)
4 Binary Cyclic Codes
125(60)
4.1 Characterization of Cyclic Codes
125(2)
4.2 Structural Properties of Cyclic Codes
127(4)
4.3 Existence of Cyclic Codes
131(2)
4.4 Generator and Parity-Check Matrices of Cyclic Codes
133(3)
4.5 Encoding of Cyclic Codes in Systematic Form
136(6)
4.6 Syndrome Calculation and Error Detection
142(3)
4.7 General Decoding of Cyclic Codes
145(5)
4.8 Error-Trapping Decoding for Cyclic Codes
150(3)
4.9 Shortened Cyclic Codes
153(1)
4.10 Hamming Codes
154(4)
4.11 Cyclic Redundancy Check Codes
158(1)
4.12 Quadratic Residue Codes
159(2)
4.13 Quasi-cyclic Codes
161(15)
4.13.1 Definitions and Fundamental Structures
161(2)
4.13.2 Generator and Parity-Check Matrices in Systematic Circulant Form
163(1)
4.13.3 Encoding of QC Codes
164(4)
4.13.4 Generator and Parity-Check Matrices in Semi-systematic Circulant Form
168(8)
4.13.5 Shortened QC Codes
176(1)
4.14 Nonbinary Cyclic Codes
176(1)
4.15 Remarks
177(1)
Problems
177(5)
References
182(3)
5 BCH Codes
185(35)
5.1 Primitive Binary BCH Codes
185(5)
5.2 Structural Properties of BCH Codes
190(2)
5.3 Minimum Distance of BCH Codes
192(4)
5.4 Syndrome Computation and Error Detection
196(2)
5.5 Syndromes and Error Patterns
198(1)
5.6 Error-Location Polynomials of BCH Codes
199(1)
5.7 A Procedure for Decoding BCH Codes
200(1)
5.8 Berlekamp-Massey Iterative Algorithm
201(4)
5.9 Simplification of Decoding Binary BCH Codes
205(6)
5.10 Finding Error Locations and Error Correction
211(1)
5.11 Nonprimitive Binary BCH Codes
212(4)
5.12 Remarks
216(1)
Problems
216(2)
References
218(2)
6 Nonbinary BCH Codes and Reed-Solomon Codes
220(38)
6.1 Nonbinary Primitive BCH Codes
221(3)
6.2 Decoding Steps of Nonbinary BCH Codes
224(1)
6.3 Syndrome and Error Pattern of Nonbinary BCH Codes
225(1)
6.4 Error-Location Polynomial of Nonbinary BCH Codes
226(5)
6.5 Error-Value Evaluator
231(1)
6.6 Decoding of Nonbinary BCH Codes
232(3)
6.7 Key-Equation
235(1)
6.8 Reed-Solomon Codes
235(3)
6.8.1 Primitive Reed-Solomon Codes
236(1)
6.8.2 Nonprimitive Reed-Solomon Codes
237(1)
6.9 Decoding Reed--Solomon Codes with Berlekamp--Massey Iterative Algorithm
238(5)
6.10 Euclidean Algorithm for Finding GCD of Two Polynomials
243(4)
6.11 Solving the Key-Equation with Euclidean Algorithm
247(4)
6.12 Weight Distribution and Probability of Undetected Error of Reed-Solomon Codes
251(1)
6.13 Remarks
252(1)
Problems
252(3)
References
255(3)
7 Finite Geometries, Cyclic Finite-Geometry Codes, and Majority-Logic Decoding
258(45)
7.1 Fundamental Concepts of Finite Geometries
259(2)
7.2 Majority-Logic Decoding of Finite-Geometry Codes
261(5)
7.3 Euclidean Geometries over Finite Fields
266(11)
7.3.1 Basic Concepts and Properties
266(3)
7.3.2 A Realization of Euclidean Geometries
269(6)
7.3.3 Subgeometries of Euclidean Geometries
275(2)
7.4 Cyclic Codes Constructed Based on Euclidean Geometries
277(11)
7.4.1 Cyclic Codes on Two-Dimensional Euclidean Geometries
278(6)
7.4.2 Cyclic Codes on Multi-Dimensional Euclidean Geometries
284(4)
7.5 Projective Geometries
288(4)
7.6 Cyclic Codes Constructed Based on Projective Geometries
292(4)
7.7 Remarks
296(1)
Problems
297(3)
References
300(3)
8 Reed--Muller Codes
303(28)
8.1 A Review of Euclidean Geometries over GF(2)
304(1)
8.2 Constructing RM Codes from Euclidean Geometries over GF(2)
305(6)
8.3 Encoding of RM Codes
311(3)
8.4 Successive Retrieval of Information Symbols
314(5)
8.5 Majority-Logic Decoding through Successive Cancellations
319(5)
8.6 Cyclic RM Codes
324(1)
8.7 Remarks
325(1)
Problems
326(1)
References
327(4)
9 Some Coding Techniques
331(36)
9.1 Interleaving
332(2)
9.2 Direct Product
334(7)
9.3 Concatenation
341(6)
9.3.1 Type-1 Serial Concatenation
342(2)
9.3.2 Type-2 Serial Concatenation
344(2)
9.3.3 Parallel Concatenation
346(1)
9.4 |u|u + v|-Construction
347(1)
9.5 Kronecker Product
348(5)
9.6 Automatic-Repeat-Request Schemes
353(9)
9.6.1 Basic ARQ Schemes
353(5)
9.6.2 Mixed-Mode SR-ARQ Schemes
358(1)
9.6.3 Hybrid ARQ Schemes
359(3)
Problems
362(1)
References
363(4)
10 Correction of Error-Bursts and Erasures
367(39)
10.1 Definitions and Structures of Burst-Error-Correcting Codes
368(2)
10.2 Decoding of Single Burst-Error-Correcting Cyclic Codes
370(3)
10.3 Fire Codes
373(3)
10.4 Short Optimal and Nearly Optimal Single Burst-Error-Correcting Cyclic Codes
376(1)
10.5 Interleaved Codes for Correcting Long Error-Bursts
377(2)
10.6 Product Codes for Correcting Error-Bursts
379(1)
10.7 Phased-Burst-Error-Correcting Codes
380(2)
10.7.1 Interleaved and Product Codes
380(1)
10.7.2 Codes Derived from RS Codes
380(1)
10.7.3 Burton Codes
381(1)
10.8 Characterization and Correction of Erasures
382(8)
10.8.1 Correction of Errors and Erasures over BSECs
383(2)
10.8.2 Correction of Erasures over BECs
385(3)
10.8.3 RM Codes for Correcting Random Erasures
388(2)
10.9 Correcting Erasure-Bursts over BBECs
390(4)
10.9.1 Cyclic Codes for Correcting Single Erasure-Burst
391(3)
10.9.2 Correction of Multiple Random Erasure-Bursts
394(1)
10.10 RS Codes for Correcting Random Errors and Erasures
394(8)
Problems
402(1)
References
403(3)
11 Introduction to Low-Density Parity-Check Codes
406(58)
11.1 Definitions and Basic Concepts
407(3)
11.2 Graphical Representation of LDPC Codes
410(4)
11.3 Original Construction of LDPC Codes
414(2)
11.3.1 Gallager Codes
415(1)
11.3.2 MacKay Codes
416(1)
11.4 Decoding of LDPC Codes
416(11)
11.4.1 One-Step Majority-Logic Decoding
418(4)
11.4.2 Bit-Flipping Decoding
422(3)
11.4.3 Weighted One-Step Majority-Logic and Bit-Flipping Decodings
425(2)
11.5 Iterative Decoding Based on Belief-Propagation
427(12)
11.5.1 Message Passing
428(1)
11.5.2 Sum-Product Algorithm
429(7)
11.5.3 Min-Sum Algorithm
436(3)
11.6 Error Performance of LDPC Codes with Iterative Decoding
439(7)
11.6.1 Error-Floor
439(2)
11.6.2 Decoding Threshold
441(1)
11.6.3 Overall Performance and Its Determinating Factors
442(4)
11.7 Iterative Decoding of LDPC Codes over BECs
446(3)
11.8 Categories of LDPC Code Constructions
449(1)
11.9 Nonbinary LDPC Codes
450(3)
Problems
453(3)
References
456(8)
12 Cyclic and Quasi-cyclic LDPC Codes on Finite Geometries
464(54)
12.1 Cyclic-FG-LDPC Codes
465(7)
12.2 A Complexity-Reduced Iterative Algorithm for Decoding Cyclic-FG-LDPC Codes
472(8)
12.3 QC-EG-LDPC Codes
480(7)
12.4 QC-PG-LDPC Codes
487(2)
12.5 Construction of QC-EG-LDPC Codes by CPM-Dispersion
489(4)
12.6 Masking Techniques
493(3)
12.7 Construction of QC-FG-LDPC Codes by Circulant-Decomposition
496(7)
12.8 A Complexity-Reduced Iterative Algorithm for Decoding QC-FG-LDPC Codes
503(6)
12.9 Remarks
509(2)
Problems
511(2)
References
513(5)
13 Partial Geometries and Their Associated QC-LDPC Codes
518(44)
13.1 CPM-Dispersions of Finite-Field Elements
518(2)
13.2 Matrices with RC-Constrained Structure
520(2)
13.3 Definitions and Structural Properties of Partial Geometries
522(2)
13.4 Partial Geometries Based on Prime-Order Cyclic Subgroups of Finite Fields and Their Associated QC-LDPC Codes
524(7)
13.5 Partial Geometries Based on Prime Fields and Their Associated QC-LDPC Codes
531(7)
13.6 Partial Geometries Based on Balanced Incomplete Block Designs and Their Associated QC-LDPC Codes
538(18)
13.6.1 BIBDs and Partial Geometries
538(3)
13.6.2 Class-1 Bose (N, M, t, r, 1)-BIBDs
541(8)
13.6.3 Class-2 Bose (N, M, t, r, 1)-BIBDs
549(7)
13.7 Remarks
556(1)
Problems
556(3)
References
559(3)
14 Quasi-cyclic LDPC Codes Based on Finite Fields
562(66)
14.1 Construction of QC-LDPC Codes Based on CPM-Dispersion
563(1)
14.2 Construction of Type-I QC-LDPC Codes Based on Two Subsets of a Finite Field
564(12)
14.3 Construction of Type-II QC-LDPC Codes Based on Two Subsets of a Finite Field
576(4)
14.4 Masking-Matrix Design
580(6)
14.4.1 Type-1 Design
580(2)
14.4.2 Type-2 Design
582(2)
14.4.3 Type-3 Design
584(2)
14.5 A Search Algorithm for 2 × 2/3 × 3 SM-Constrained Base Matrices for Constructing Rate-1/2 QC-LDPC Codes
586(4)
14.6 Designs of 2 × 2 SM-Constrained RS Base Matrices
590(2)
14.7 Construction of Type-III QC-LDPC Codes Based on RS Codes
592(6)
14.8 Construction of QC-RS-LDPC Codes with Girths at Least 8
598(5)
14.9 A Special Class of QC-RS-LDPC Codes with Girth 8
603(5)
14.10 Optimal Codes for Correcting Two Random CPM-Phased Erasure-Bursts
608(4)
14.11 Globally Coupled LDPC Codes
612(7)
14.12 Remarks
619(1)
Problems
619(4)
References
623(5)
15 Graph-Theoretic LDPC Codes
628(56)
15.1 Protograph-Based LDPC Codes
629(11)
15.2 A Matrix-Theoretic Method for Constructing Protograph-Based LDPC Codes
640(15)
15.3 Masking Matrices as Protomatrices
655(15)
15.4 LDPC Codes on Progressive Edge-Growth Algorithms
670(6)
15.5 Remarks
676(1)
Problems
677(2)
References
679(5)
16 Collective Encoding and Soft-Decision Decoding of Cyclic Codes of Prime Lengths in Galois Fourier Transform Domain
684(37)
16.1 Cyclic Codes of Prime Lengths and Their Hadamard Equivalents
685(3)
16.2 Composing, Cascading, and Interleaving a Cyclic Code of Prime Length and Its Hadamard Equivalents
688(4)
16.2.1 Composing
688(1)
16.2.2 Cascading and Interleaving
689(3)
16.3 Galois Fourier Transform of ICC Codes
692(2)
16.4 Structural Properties of GFT-ICC Codes
694(2)
16.5 Collective Encoding of GFT-ICC-LDPC Codes
696(2)
16.6 Collective Iterative Soft-Decision Decoding of GFT-ICC-LDPC Codes
698(2)
16.7 Analysis of the GFT-ISDD Scheme
700(1)
16.7.1 Performance Measurements
700(1)
16.7.2 Complexity
701(1)
16.8 Joint Decoding of RS Codes with GFT-ISDD Scheme
701(5)
16.9 Joint Decoding of BCH Codes with GFT-ISDD Scheme
706(3)
16.10 Joint Decoding of QR Codes with GFT-ISDD Scheme
709(1)
16.11 Code Shortening and Rate Reduction
710(5)
16.11.1 Shortened GFT-ICC Codes
710(3)
16.11.2 Reductions of Code Rate
713(2)
16.12 Erasure Correction of GFT-ICC-RS-LDPC Codes
715(2)
16.13 Remarks
717(1)
Problems
717(2)
References
719(2)
17 Polar Codes
721(81)
17.1 Kronecker Matrices and Their Structural Properties
721(3)
17.2 Kronecker Mappings and Their Logical Implementations
724(11)
17.3 Kronecker Vector Spaces and Codes
735(3)
17.4 Definition and Polarized Encoding of Polar Codes
738(3)
17.5 Successive Information Retrieval from a Polarized Codeword
741(3)
17.6 Channel Polarization
744(22)
17.6.1 Some Elements of Information Theory
745(2)
17.6.2 Polarization Process
747(13)
17.6.3 Channel Polarization Theorem
760(6)
17.7 Construction of Polar Codes
766(2)
17.8 Successive Cancellation Decoding
768(11)
17.8.1 SC Decoding of Polar Codes of Length N = 2
770(3)
17.8.2 SC Decoding of Polar Codes of Length N = 4
773(5)
17.8.3 SC Decoding of Polar Codes of Length N = 2l
778(1)
17.9 Remarks
779(1)
Problems
780(1)
References
781(3)
Appendix A Factorization of Xn + 1 over GF(2)
784(1)
Appendix B A 2 × 2/3 × 3 SM-Constrained Masked Matrix Search Algorithm
785(1)
Appendix C Proof of Theorem 14.4
786(5)
Appendix D The 2 × 2 CPM-Array Cycle Structure of the Tanner Graph of CRS,n(2,n)
791(2)
Appendix E Iterative Decoding Algorithm for Nonbinary LDPC Codes
793(1)
E.1 Introduction
793(1)
E.2 Algorithm Derivation
794(6)
E.2.1 VN Update
795(1)
E.2.2 CN Update: Complex Version
795(1)
E.2.3 CN Update: Fast Hadamard Transform Version
796(4)
E.3 The Nonbinary LDPC Decoding Algorithm
800(2)
Index 802
Shu Lin is an Adjunct Professor in the Department of Electrical and Computer Engineering at the University of California, Davis, and an IEEE Life Fellow. He has authored and co-authored several books, including LDPC Codes Designs, Constructions, and Unification and Channel Codes: Classical and Modern (Cambridge 2016, 2009). Juane Li is Staff Systems Architect at Micron Technology Inc., San Jose, having previously completed her PhD at the University of California, Davis. She is also a co-author of LDPC Codes Designs, Constructions, and Unification (Cambridge University Press, 2009).
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97810090805692e.html
Märksõnad: