Section Definitions and Algorithms
This page contains definitions of important terms and algorithms used throughout the course.
Subsection Definitions
Definition 4 t-error correcting code
Definition 5 t-error detecting code
Definition 6 Maximum likelihood decoding
Definition 7 Nearest neighbor decoding
Definition 9 Hamming sphere
Definition 10 Span of vectors
Definition 11 Linear independence
Definition 12 Basis
Definition 13 Dimension
Definition 14 Rowspace
Definition 18 Generator Matrix
Definition 19 Parity-Check Matrix
Definition 20 Inner Product
Definition 21 Orthogonality
Definition 22 Orthogonal Complement/Dual Code
Definition 32 Maximum Distance Separable (MDS) Codes
Definition 47 Coset of a Subspace
Definition 48 Volume of a Hamming Sphere
Definition 51 Primitive Element
Definition 52 Extension Field/Subfield
Definition 53 Extension Degree
Definition 55 Syndrome Polynomial
Definition 56 Error Locator Polynomial
Definition 57 Error Evaluator Polynomial
Definition 58 Key Equation
Definition 62 Exponent of a Polynomial
Definition 63 Primitive Polynomial
Definition 68 Cyclic Codes
Definition 70 Cyclotomic Cosets
Definition 72 Syndrome
Definition 73 Standard Array
Definition 76 Perfect Code
Definition 79 GCD of Polynomials
Definition 82 Irreducible Polynomials
Definition 83 Quotient of a Polynomial Ring
Definition 84 Characteristic of a Field
Definition 85 Prime Subfield
Definition 86 Zech’s Log Table
Definition 95 GRS Codes
Definition 96 RS Codes
Subsection Algorithms
Algorithm 24 Efficient Decoding Algorithm for 1-error Correcting Linear Codes
Algorithm 28 Syndrome Decoding
Algorithm 74 Standard Array Decoding
Algorithm 80 Euclid’s Algorithm
Algorithm 93 Error Trapping Decoding for Cyclic Codes
Algorithm 94 Error Trapping for Cyclic Burst-Error Codes
Algorithm 98 Sugiyama’s Algorithm for GRS Decoding
Algorithm 99 Extended Euclidean Algorithm
Algorithm 100 Berlekamp-Welch Decoding for GRS Codes
Algorithm 105 Decoding Algorithm for the Double-Error-Correcting Alternant Code over GF(2)
Algorithm 106 Step-by-step Decoding Algorithm for Binary Linear Codes
