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 73 Syndrome
Definition 74 Standard Array
Definition 77 Perfect Code
Definition 80 GCD of Polynomials
Definition 83 Irreducible Polynomials
Definition 84 Quotient of a Polynomial Ring
Definition 85 Characteristic of a Field
Definition 86 Prime Subfield
Definition 87 Zech’s Log Table
Definition 96 GRS Codes
Definition 97 RS Codes
Subsection Algorithms
Algorithm 24 Efficient Decoding Algorithm for 1-error Correcting Linear Codes
Algorithm 28 Syndrome Decoding
Algorithm 75 Standard Array Decoding
Algorithm 81 Euclid’s Algorithm
Algorithm 94 Error Trapping Decoding for Cyclic Codes
Algorithm 95 Error Trapping for Cyclic Burst-Error Codes
Algorithm 99 Sugiyama’s Algorithm for GRS Decoding
Algorithm 100 Extended Euclidean Algorithm
Algorithm 101 Berlekamp-Welch Decoding for GRS Codes
Algorithm 106 Decoding Algorithm for the Double-Error-Correcting Alternant Code over GF(2)
Algorithm 107 Step-by-step Decoding Algorithm for Binary Linear Codes
