Error correction coding : mathematical methods and algorithms /: mathematical methods and algorithms. (2020)

• Record Type: Book
• Further Information: Note: Todd K. Moon.
• Authors: Moon, Todd K
• Contents: Preface v List of Program Files xxxiii List of Laboratory Exercises xxxiv List of Algorithms xxxvi List of Figures xliv List of Tables xlvi List of Boxes xlvii Part I Introduction and Foundations 1 1 A Context for Error Correction Coding 3 1.1 Purpose of This Book 3 1.2 Introduction: Where Are Codes? 3 1.3 The Communications System 5 1.4 Basic Digital Communications 11 1.4.1 Binary Phase-Shift Keying 11 1.4.2 More General Digital Modulation 12 1.5 Signal Detection 15 1.5.1 The Gaussian Channel 15 1.5.2 MAP and ML Detection 17 1.5.3 Special Case: Binary Detection 19 1.5.4 Probability of Error for Binary Detection 21 1.5.5 Bounds on Performance: The Union Bound 22 1.5.6 The Binary Symmetric Channel 24 1.5.7 The BSC and the Gaussian Channel Model 26 1.6 Memoryless Channels 26 1.7 Simulation and Energy Considerations for Coded Signals 26 1.8 Some Important Definitions 29 1.8.1 Detection of Repetition Codes Over a BSC 30 1.8.2 Soft-Decision Decoding of Repetition Codes Over the AWGN 33 1.8.3 Simulation of Results 34 1.8.4 Summary 35 1.9 Hamming Codes 35 1.9.1 Hard-Input Decoding Hamming Codes 36 1.9.2 Other Representations of the Hamming Code 38 1.9.2.1 An Algebraic Representation 39 1.9.2.2 A Polynomial Representation 39 1.9.2.3 A Trellis Representation 40 1.9.2.4 The Tanner Graph Representation 41 1.10 The Basic Questions 41 1.11 Historical Milestones of Coding Theory 42 1.12 A Bit of Information Theory 42 1.12.1 Definitions for Discrete Random Variables 43 1.12.1.1 Entropy and Conditional Entropy 43 1.12.1.2 Relative Entropy, Mutual Information, and Channel Capacity 44 1.12.2 Data Processing Inequality 46 1.12.3 Channels 47 1.12.3.1 Binary Symmetric Channel 47 1.12.3.2 Binary Erasure Channel 48 1.12.3.3 Noisy Typewriter 49 1.12.3.4 Symmetric Channels 49 1.12.4 Channel Capacity 49 1.12.5 Definitions for Continuous Random Variables 50 1.12.6 The Channel Coding Theorem 52 1.12.7 “Proof" of the Channel Coding Theorem 52 1.12.8 Capacity for the Continuous-Time AWGN Channel 57 1.12.9 Transmission at Capacity with Errors 58 1.12.10 The Implication of the Channel Coding Theorem 59 1.12.11 Non-Asymptotic Information Theory 59 1.12.11.1 Discrete Channels 61 1.12.11.2 The AWGN Channel 62 1.12.11.3 Comparison of Codes 63 Lab 1 Simulating a Communications Channel 63 Objective 63 Background 63 Use of Coding in Conjunction with the BSC 64 Assignment 65 Programming Part 65 Resources and Implementation Suggestions 66 1.13 Exercises 67 1.14 References 71 Part II Block Codes 73 2 Groups and Vector Spaces 74 2.1 Introduction 74 2.2 Groups 74 2.2.1 Subgroups 78 2.2.2 Cyclic Groups and the Order of an Element 79 2.2.3 Cosets 80 2.2.4 Lagrange’s Theorem 81 2.2.5 Induced Operations; Isomorphism 82 2.2.6 Homomorphism 86 2.3 Fields: A Prelude 87 2.4 Review of Linear Algebra 89 2.5 Exercises 95 2.6 References 96 3 Linear Block Codes 97 3.1 Basic Definitions 97 3.2 The Generator Matrix Description of Linear Block Codes 98 3.2.1 Rudimentary Implementation 100 3.3 The Parity Check Matrix and Dual Codes 100 3.3.1 Some Simple Bounds on Block Codes 103 3.4 Error Detection and Correction over Hard-Output Channels 104 3.4.1 Error Detection 104 3.4.2 Error Correction: The Standard Array 105 3.5 Weight Distributions of Codes and Their Duals 109 3.6 Binary Hamming Codes and Their Duals 112 3.7 Performance of Linear Codes 113 3.7.1 Error detection performance 114 3.7.2 Error Correction Performance 115 3.7.3 Performance for Soft-Decision Decoding 118 3.8 Erasure Decoding 119 3.8.1 Binary Erasure Decoding 120 3.9 Modifications to Linear Codes 121 3.10 Best Known Linear Block Codes 123 3.11 Exercises 123 3.12 References 128 4 Cyclic Codes, Rings, and Polynomials 129 4.1 Introduction 129 4.2 Basic Definitions 129 4.3 Rings 130 4.3.1 Rings of Polynomials 132 4.4 Quotient Rings 133 4.5 Ideals in Rings 135 4.6 Algebraic Description of Cyclic Codes 137 4.7 Nonsystematic Encoding and Parity Check 138 4.8 Systematic Encoding 141 4.9 Some Hardware Background 143 4.9.1 Computational Building Blocks 143 4.9.2 Sequences and Power series 144 4.9.3 Polynomial Multiplication 146 4.9.3.1 Last-Element-First Processing 146 4.9.3.2 First-Element-First Processing 146 4.9.4 Polynomial division 147 4.9.4.1 Last-Element-First Processing 147 4.9.5 Simultaneous Polynomial Division and Multiplication 149 4.9.5.1 First-Element-First Processing 149 4.10 Cyclic Encoding 152 4.11 Syndrome Decoding 155 4.12 Shortened Cyclic Codes 160 4.12.0.1 Method 1: Simulating the Extra Clock Shifts 161 4.12.0.2 Method 2: Changing the Error Pattern Detection Circuit 162 4.13 Binary CRC Codes 165 4.13.1 Byte-Oriented Encoding and Decoding Algorithms 167 4.13.2 CRC Protecting Data Files or Data Packets 171 Appendix 4.A Linear Feedback Shift Registers 172 Appendix 4.A.1 Basic Concepts 172 Appendix 4.A.2 Connection With Polynomial Division 175 Appendix 4.A.3 Some Algebraic Properties of Shift Sequences 178 Lab 2 Polynomial Division and Linear Feedback Shift Registers 179 Objective 179 Preliminary Exercises 179 Programming Part: BinLFSR 179 Resources and Implementation Suggestions 180 Programming Part: BinPolyDiv 180 Follow-On Ideas and Problems 180 Lab 3 CRC Encoding and Decoding 181 Objective 181 Preliminary 181 Programming Part 181 Resources and Implementation Suggestions 183 4.14 Exercises 184 4.15 References 189 5 Rudiments of Number Theory and Algebra 191 5.1 Motivation 191 5.2 Number Theoretic Preliminaries 195 5.2.1 Divisibility 195 5.2.2 The Euclidean Algorithm and Euclidean Domains 198 5.2.3 The Sugiyama Algorithm 203 5.2.4 Congruence 206 5.2.5 The ‑ Function 207 5.2.6 Some Cryptographic Payoff 208 5.2.6.1 Fermat’s Little Theorem 208 5.2.6.2 RSA Encryption 209 5.3 The Chinese Remainder Theorem 210 5.3.1 The CRT and Interpolation 213 5.3.1.1 The Evaluation Homomorphism 213 5.3.1.2 The Interpolation Problem 213 5.4 Fields 215 5.4.1 An Examination of R and C 216 5.4.2 Galois Field Construction: An Example 219 5.4.3 Connection with Linear Feedback Shift Registers 222 5.5 Galois Fields: Mathematical Facts 223 5.6 Implementing Galois Field Arithmetic 227 5.6.1 Zech Logarithms 227 5.6.2 Hardware Implementations 228 5.7 Subfields of Galois Fields 229 5.8 Irreducible and Primitive polynomials 230 5.9 Conjugate Elements and Minimal Polynomials 232 5.9.1 Minimal Polynomials 235 5.10 Factoring x n 1 238 5.11 Cyclotomic Cosets 241 Appendix 5.A How Many Irreducible Polynomials Are There? 241 Appendix 5.A.1 Solving for Im Explicitly: The Moebius Function 245 Lab 4 Programming the Euclidean Algorithm 246 &
• Edition: Second edition
• Publisher Details: Hoboken : John Wiley & Sons, Inc
• Publication Date: 2020
• Extent: 1 online resource
• Subjects: 621.3820285572; Engineering mathematics; Error-correcting codes (Information theory)
• Languages: English
• ISBNs: 9781119567493
• Related ISBNs: 9781119567486
• Notes: Note: Includes bibliographical references and index.; Note: Description based on CIP data; resource not viewed.
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.