Fact-checked by Grok 2 weeks ago

Linear code

In , a linear code is defined as a of the \mathbb{F}_q^n over a \mathbb{F}_q, where codewords are the vectors in this that represent encoded messages for over noisy channels. These codes are particularly efficient because they allow encoding and decoding operations to be performed using linear algebra, such as matrix multiplication, enabling the detection and correction of errors introduced during . The foundations of , including linear codes, were established by in his 1948 paper "," which demonstrated that reliable communication is possible over noisy channels by introducing controlled , though practical constructions were initially lacking. In , at Bell Laboratories developed the first explicit linear codes, known as Hamming codes, motivated by frustrations with error-prone that required manual restarts; these codes of length $2^[m](/page/M) - 1 and dimension $2^[m](/page/M) - 1 - [m](/page/M) can correct single errors and detect double errors. Further early advancements include the 1949 of the Golay codes by Marcel Golay, which expanded the class of perfect linear codes that achieve the theoretical limits of error correction as described by the sphere-packing bound. Linear codes are typically denoted as [n, k, d]-codes, where n is the code length (block size), k is the dimension (number of information symbols), and d is the minimum between any two distinct codewords, which determines the error-correcting capability t = \lfloor (d-1)/2 \rfloor. They can be generated using a k \times n G whose rows form a basis for the , such that any codeword is uG for a vector u \in \mathbb{F}_q^k, or equivalently defined via an (n-k) \times n parity-check matrix H where codewords satisfy Hx^T = 0. A fundamental property is that the minimum distance equals the minimum weight of nonzero codewords, simplifying distance computations. Notable bounds include the Singleton bound d \leq n - k + 1, with maximum distance separable (MDS) codes achieving equality, such as Reed-Solomon codes over \mathbb{F}_q with q \geq n. Applications of linear codes span digital communications, storage, and beyond; for instance, Hamming codes are used in computer memory like for single-error correction, while Reed-Solomon codes protect data in , DVDs, satellite communications, and deep-space missions such as NASA's Voyager probes. In modern contexts, they underpin error correction in wireless networks, systems, and even genetic data analysis to model errors.

Fundamentals

Definition

A linear code over a finite field \mathbb{F}_q of length n is defined as a k-dimensional subspace C \subseteq \mathbb{F}_q^n, where the codewords are the vectors belonging to C. The linearity of the code ensures that it is closed under vector addition and scalar multiplication: for any codewords \mathbf{c}_1, \mathbf{c}_2 \in C and any \alpha \in \mathbb{F}_q, both \mathbf{c}_1 + \mathbf{c}_2 and \alpha \mathbf{c}_1 are also in C. This structure distinguishes linear codes from nonlinear codes, as the former constitute vector spaces over \mathbb{F}_q, facilitating the application of algebraic tools like bases and linear transformations. The foundations of error-correcting codes, including linear variants, trace back to Claude Shannon's 1948 seminal paper establishing information theory, which demonstrated the possibility of reliable communication over noisy channels; linear codes were subsequently formalized by researchers such as Richard Hamming in the early 1950s. A fundamental property of a linear code C is its minimum d, which equals the smallest (number of nonzero coordinates) among all nonzero codewords in C.

Parameters

A linear code over a finite field \mathbb{F}_q is characterized by several key parameters that quantify its structure, efficiency, and error-correcting capabilities. The length n denotes the total number of symbols in each codeword, where each symbol is an element from \mathbb{F}_q. The dimension k represents the number of independent information symbols, which corresponds to the dimension of the code as a vector subspace of \mathbb{F}_q^n, resulting in exactly q^k codewords in the code C, so |C| = q^k. The redundancy, given by n - k, indicates the number of parity symbols or checks introduced to enable error detection and correction, as determined by the rank of the parity-check matrix. The rate R = k/n measures the of the , representing the of symbols that carry relative to the total ; higher rates imply less but potentially reduced error-correcting power. A fundamental performance metric is the minimum distance d, defined as the smallest between any two distinct codewords, which equals the minimum (number of nonzero symbols) among all nonzero codewords to the of the . This parameter governs the code's ability to detect up to d-1 errors and correct up to t = \lfloor (d-1)/2 \rfloor errors using standard . The weight distribution of a linear code provides further insight into its error-correcting properties, describing the number A_w of codewords of each possible weight w from 0 to n, with A_0 = 1, A_d the number of minimum-weight codewords, and \sum_{w=0}^n A_w = q^k. These values influence advanced decoding performance and bounds but are typically computed for specific codes rather than in general.

Constructions and Representations

Generator Matrix

In coding theory, a generator matrix for a linear code C \subseteq \mathbb{F}_q^n of length n and dimension k is a k \times n matrix G over the finite field \mathbb{F}_q whose rows form a basis for the vector subspace C. The rows of G are linearly independent and span C, ensuring that every codeword in C can be expressed as a unique linear combination of these rows. The encoding process using the generator matrix transforms a message vector u \in \mathbb{F}_q^k, treated as a $1 \times k row vector, into a codeword c = uG \in \mathbb{F}_q^n, which is also a row vector. This operation represents a linear transformation from the k-dimensional message space to the n-dimensional code space, embedding the information bits into the codeword while adding redundancy for error correction. All codewords are thus generated by taking all possible linear combinations of the rows of G with coefficients from \mathbb{F}_q. A generator matrix is said to be in systematic form if it can be arranged as G = [I_k \mid P], where I_k is the k \times k identity matrix and P is a k \times (n-k) matrix. In this form, the first k columns correspond directly to the message bits in the codeword, with the remaining n-k columns providing the parity or check bits, facilitating straightforward encoding where the codeword's initial segment matches the message u. Any generator matrix for a linear code can be transformed into systematic form through elementary row operations over \mathbb{F}_q, such as row addition or scaling, without altering the row space. Key properties of the generator matrix include its full row rank, which equals k and matches the dimension of the code, confirming that the rows are linearly independent. Two k \times n matrices generate the same linear code if and only if one can be obtained from the other by a sequence of elementary row operations, establishing their equivalence in representing the code subspace. The generator matrix provides a constructive representation complementary to the parity-check matrix, which describes the dual code.

Parity-Check Matrix

In , the parity-check matrix of a linear code C \subseteq \mathbb{F}_q^n of length n and dimension k is an (n-k) \times n H over the \mathbb{F}_q such that C = \{ c \in \mathbb{F}_q^n \mid H c^T = 0 \}. The rows of H form a basis for the dual code C^\perp, which is the orthogonal complement of C with respect to the standard inner product over \mathbb{F}_q. This matrix thus defines C as the kernel (nullspace) of H, and any full-rank (n-k) \times n matrix whose kernel is C serves as a parity-check matrix. The parity-check matrix relates to the generator matrix G of C, a k \times n matrix whose rows C, via the condition G H^T = 0. This ensures that every codeword, as a of the rows of G, lies in the of H. Conversely, the rows of H the dual code, and H can be viewed as a for C^\perp. For error detection, given a received vector r = c + e \in \mathbb{F}_q^n where c \in C is the transmitted codeword and e is the vector, the is computed as s = H r^T \in \mathbb{F}_q^{n-k}. The s = 0 r is a codeword (i.e., e = 0); otherwise, s depends only on e and provides information about the pattern. A common representation is the systematic (or standard) form of H, obtained via row and column permutations, where the rightmost n-k columns form the (n-k) \times (n-k) I_{n-k}, and the leftmost k columns form an arbitrary (n-k) \times k P. Thus, H = [P \mid I_{n-k}], which facilitates explicit of corresponding to the systematic encoding. A key property of the parity-check matrix is its role in determining the minimum distance d of the code: d is the smallest integer such that some d columns of H are linearly dependent, or equivalently, the minimum number of columns of H that sum to the zero vector. No fewer than d columns are linearly dependent, ensuring that the code can detect up to d-1 errors.

Decoding Algorithms

Syndrome Decoding

Syndrome decoding is a algebraic for error correction in linear codes over a \mathbb{F}_q, leveraging the parity-check matrix H to detect and correct without exhaustive search over all possible codewords. The method computes a vector from the received word, which identifies the error pattern by mapping to precomputed error vectors of low weight. This approach exploits the linear structure of the code, making it efficient for codes with small redundancy. The core of syndrome decoding lies in the syndrome s = H r^T, where r is the received vector and H is the (n-k) \times n parity-check matrix of the [n, k] linear code C. Since r = c + e for some codeword c \in C and error vector e, the linearity implies s = H e^T, which depends only on the error and not the transmitted codeword. If s = 0, then r is a codeword (no detectable error); otherwise, s identifies the coset of C in \mathbb{F}_q^n to which r belongs. The decoding procedure involves looking up the coset leader \hat{e}, the minimum-weight error vector in that coset such that H \hat{e}^T = s, and correcting via \hat{c} = r - \hat{e}. This corrects all errors of weight at most the error-correcting capability t = \lfloor (d-1)/2 \rfloor, where d is the minimum distance. To enable fast lookup, a syndrome table is precomputed, mapping each possible syndrome (there are q^{n-k} syndromes, corresponding to the q^{n-k} cosets) to its coset leader, typically the lowest-weight vector in the coset. Coset leaders are chosen as the error patterns of weight up to t that minimize the decoding error probability under typical channel models. For implementation, the table stores only entries for correctable errors, assuming higher-weight errors are either undetected or lead to decoding failure. The decoded codeword \hat{c} is then the information bits from the first k positions of r - \hat{e}, assuming systematic form. The arises from building and querying the : constructing coset leaders requires enumerating low-weight vectors, with time as O(q^{n-k}) in the worst case to the number of cosets, though feasible when the n-k is small (e.g., n-k \leq 10 for q=2). Lookup is then O(1) with hashing or direct indexing, making the overall decoding linear in n after preprocessing. This efficiency contrasts with brute-force methods but is limited for large n-k. A key limitation is that syndrome decoding provides complete coverage—correcting all error patterns up to weight t for every received word—only for perfect codes, which saturate the : the spheres of radius t around codewords exactly fill the space \mathbb{F}_q^n. Non-perfect codes leave gaps, where some low-weight errors map to s without assigned leaders, potentially causing decoding failures or miscorrections. Examples of perfect codes include Hamming and Golay codes, but most linear codes are imperfect, requiring bounded-distance decoding that corrects only a of errors. As an alternative, nearest-neighbor decoding uses distance metrics directly, bypassing s for non-algebraic approaches.

Nearest Neighbor Decoding

Nearest neighbor decoding, also referred to as minimum-distance decoding, is a maximum-likelihood decoding for linear codes over symmetric channels such as the binary symmetric channel (BSC). Given a received r \in \mathbb{F}_q^n, the decoder selects the codeword c \in C that minimizes the d_H(r, c), where C is the code subspace of dimension k. This approach interprets the codewords as points in the n-dimensional Hamming space, with decision regions forming Voronoi cells centered at each codeword; the received falls into the cell of its closest codeword, ensuring optimal decoding under the assumption of equally likely messages and independent errors. A bounded-distance variant restricts the search to codewords within a radius t = \lfloor (d-1)/2 \rfloor, where d is the minimum distance of the code, decoding successfully only if a unique codeword exists in this sphere and declaring a decoding failure otherwise. This guarantees correction of up to t errors without exhaustive search beyond the bound, leveraging the sphere-packing property that such spheres around codewords are disjoint. Implementation typically involves exhaustive enumeration over the q^k codewords for small codes, though for larger ones, it may employ sphere-packing-based methods like ordered statistics or lattice decoding adaptations to prune the search space geometrically. Under maximum-likelihood nearest neighbor decoding, the probability of decoding error for good linear code ensembles, such as low-density parity-check codes, approaches the Shannon capacity limit as block lengths n grow large, achieving rates arbitrarily close to capacity with vanishing error probability. This performance is analyzed via tight exponential bounds like the tangential sphere bound, which demonstrate gaps as small as 0.33 dB for moderate n. Nearest neighbor decoding for block codes is analogous to the Viterbi algorithm for convolutional codes, both pursuing maximum likelihood but treating fixed-length vectors versus dynamic sequences. Syndrome decoding serves as a faster algebraic alternative for correcting small numbers of errors in structured linear codes.

Examples

Hamming Codes

Hamming codes form a family of binary linear error-correcting codes capable of correcting single errors, introduced by Richard Hamming to address reliability issues in early computing machinery. The binary Hamming code of order m \geq 2 has length n = 2^m - 1, dimension k = n - m = 2^m - 1 - m, and minimum distance d = 3, defined over the finite field \mathbb{F}_2. The code is constructed via its parity-check matrix H, an m \times n matrix whose columns consist of all distinct nonzero binary vectors of length m, arranged in any order. This ensures that the columns are linearly independent in pairs, guaranteeing the minimum distance d = 3. The generator matrix G is a k \times n systematic matrix whose rows form a basis for the kernel (null space) of H, typically obtained by placing an identity matrix in the information positions corresponding to non-parity columns of H. Hamming codes are perfect codes, achieving in the (sphere-packing bound) for single-error correction (t = [1](/page/1)), where the spheres of around codewords exactly fill the entire space \mathbb{F}_2^n without overlap. For example, the [7,4,3]_2 has $2^4 = 16 codewords, and the number of vectors at at most from each is $1 + 7 = 8, totaling $16 \times 8 = 128 = 2^7, saturating the bound. An extended binary Hamming code is obtained by appending an overall parity-check bit to the standard code, resulting in n' = 2^m, k' = 2^m - 1 - m, and minimum d' = 4. This modification enables single-error correction and double-error detection. For m=3, the extended [8,4,4]_2 code is a well-known instance. Hamming codes satisfy the Singleton bound but are not maximum distance separable (MDS) codes, as their relative distance d/n \approx 3/(2^m) falls short of the MDS requirement d = n - k + 1 = m + 1. In applications, these codes were among the first implemented for error correction in 1950s digital computers, such as relay-based machines at Bell Laboratories, enabling reliable unattended operation despite noise-induced single-bit errors.

Hadamard Codes

Hadamard codes are binary linear codes of length n = 2^m, dimension k = m + 1, and minimum distance d = 2^{m-1}, obtained as the row space over \mathbb{F}_2 of a normalized of order n. These codes achieve the optimal relative minimum distance of $1/2 among binary codes of length $2^m and dimension m+1. The minimum weight of nonzero codewords is $2^{m-1}. The construction relies on the Sylvester method for generating Hadamard matrices recursively. Starting with the $2 \times 2 matrix H_1 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, higher-order matrices are built as H_m = \begin{pmatrix} H_{m-1} & H_{m-1} \\ H_{m-1} & -H_{m-1} \end{pmatrix}. To form the linear code, the entries of H_m are mapped from \{\pm 1\} to \{0,1\} by replacing +1 with $0 and -1 with $1, and a is formed from any m+1 linearly independent rows over \mathbb{F}_2, such as the rows corresponding to and the vectors in the Walsh-Hadamard transform basis. This yields $2^{m+1} codewords, spanning the space of affine linear functions on \mathbb{F}_2^m. Key properties include the code's equivalence to the first-order Reed-Muller code \mathrm{RM}(1,m), which shares the same parameters and structure. Puncturing the Hadamard code by deleting one coordinate position produces the simplex code of length $2^m - 1, dimension m, and distance $2^{m-1}, whose dual is the Hamming code. Additionally, the codewords exhibit ideal autocorrelation properties in their \pm 1 representation—zero off-peak correlation—enabling their use in spread-spectrum systems for orthogonal signaling and interference rejection. These traits support applications in multi-user communications where low cross-correlation between signals is essential. Hadamard codes were developed in the 1950s as part of early efforts in coding theory for simplex signaling schemes, where orthogonal codewords facilitate efficient transmission over noisy channels. The foundational work tied their construction to Reed-Muller codes, introduced by D. E. Muller and I. S. Reed for multiple-error correction in binary alphabets. This integration of combinatorial matrix constructions with linear algebra laid the groundwork for their role in both error control and signal processing.

Reed-Solomon Codes

Reed–Solomon codes are a prominent class of linear error-correcting codes defined over a finite field \mathbb{F}_q, where q is a prime power, with code length n \leq q, dimension k, and minimum distance d = n - k + 1. Introduced by Irving S. Reed and Gustave Solomon in their seminal 1960 paper, these codes evaluate polynomials of degree less than k at n distinct points in \mathbb{F}_q to form codewords, providing optimal error correction for symbol errors in non-binary alphabets. The generator matrix G for a Reed–Solomon code is constructed in Vandermonde form. Let \alpha_1, \alpha_2, \dots, \alpha_n be n distinct evaluation points in \mathbb{F}_q. The rows of G (a k \times n matrix) are given by \mathbf{g}_j = (\alpha_1^{j-1}, \alpha_2^{j-1}, \dots, \alpha_n^{j-1}) for j = 1, 2, \dots, k, ensuring the code's linearity. Systematic encoding can be achieved by column permutation so that the first k columns form an identity matrix. Encoding a message \mathbf{m} = (m_0, m_1, \dots, m_{k-1}) \in \mathbb{F}_q^k involves forming the polynomial p(x) = m_0 + m_1 x + \dots + m_{k-1} x^{k-1} and computing the codeword \mathbf{c} = (p(\alpha_1), p(\alpha_2), \dots, p(\alpha_n)). This evaluation-based construction guarantees that any k positions of a codeword uniquely determine the polynomial and thus the entire codeword. Reed–Solomon codes are maximum distance separable (MDS) codes, achieving equality in the Singleton bound d \leq n - k + 1, which bounds the trade-off between rate and error correction capability. They can correct up to t = \lfloor (n - k)/2 \rfloor symbol errors or detect up to n - k errors, with efficient decoding algorithms like Berlekamp–Massey leveraging the polynomial structure. For binary approximations, subfield subcodes such as binary BCH codes can be derived, though Reed–Solomon codes excel in q-ary settings. To adapt to lengths shorter than q, shortening reduces n and k by deleting symbols and adjusting the field, while puncturing deletes parity symbols to shorten n without changing k, preserving the MDS property in both cases. These codes have found widespread applications due to their optimal performance and simplicity. In deep-space communication, adopted Reed–Solomon codes starting in the 1960s for missions like Voyager (launched 1977), Galileo, and Cassini, enabling reliable from signals attenuated by billions of miles, often concatenated with convolutional codes for enhanced error resilience. In consumer technologies, they underpin error correction in compact discs () and DVDs, correcting burst errors from scratches to ensure audio and fidelity, and in QR codes, where up to 40 use Reed–Solomon for up to 30% error correction across four levels of redundancy.

Bounds and Properties

Singleton Bound

The Singleton bound provides an upper limit on the minimum distance d of a linear code with length n and dimension k over an alphabet of size q, stating that d \leq n - k + 1. This bound applies more generally to any block code with M codewords, where M \leq q^{n - d + 1}, and for linear codes, M = q^k implies the dimension form of the inequality. To prove the bound, consider the projections of the codewords onto any set of n - d + 1 coordinates. These projections must all be distinct: if two distinct codewords agreed on such a set, they would differ in at most d - 1 positions overall, contradicting the minimum distance d. Thus, the number of codewords M is at most the number of possible distinct projections, which is q^{n - d + 1}. For linear codes, this yields q^k \leq q^{n - d + 1}, so k \leq n - d + 1, or equivalently d \leq n - k + 1. Linear codes achieving in the Singleton bound, d = n - k + 1, are known as maximum distance separable (MDS) codes. Examples include Reed-Solomon codes, which are widely used in applications like and communications due to their optimal distance properties, as well as trivial cases such as the full-space code (k = n, d = 1) and the repetition code (k = 1, d = n). The bound has significant implications for code design, constraining the rate R = k/n by R \leq 1 - (d-1)/n, which highlights the between correction capability and information efficiency. It was introduced by Robert C. Singleton in 1964 for q-ary codes, building on earlier ideas in error-correcting code theory.

Bonisoli's Theorem

Bonisoli's theorem provides a complete of linear codes over finite fields, which are precisely the constant-weight linear codes where all nonzero codewords have the same weight w. Introduced by Arrigo Bonisoli in 1984, the theorem builds on earlier work by Assmus and Key on the between linear codes and combinatorial designs, particularly in characterizing the supports of codewords as blocks in t-designs. The theorem states that every [n, k]_q linear code C over the finite field \mathbb{F}_q with constant nonzero weight w (and k \geq 1) satisfies q^{k-1} divides w, and C is monomially equivalent to the u-fold repetition code of the q-ary simplex code \mathrm{Sim}_q(k), where u = w / q^{k-1} and the length is n = u \cdot (q^k - 1)/(q - 1). The simplex code \mathrm{Sim}_q(k) itself has length (q^k - 1)/(q - 1), dimension k, and constant weight q^{k-1}, making its repetitions the only possible structures for such codes. This characterization implies that constant-weight linear codes correspond to disjoint direct sums (in the vector space sense) of simplex codes, where the supports of the codewords form disjoint unions of the block structures from multiple copies of the underlying design. In the context of linear codes, the theorem ties optimal constant-weight constructions to geometric designs, such as projective geometries. Specifically, the supports of the nonzero codewords in a simplex code \mathrm{Sim}_q(k) form the hyperplanes of the \mathrm{PG}(k-1, q), which is a 2-( (q^k - 1)/(q - 1), q^{k-1}, (q^{k-1} - 1)/(q - 1) ) design; repetitions preserve this structure across disjoint components, yielding optimal weights for parameters where the code achieves the maximum possible size. For example, Hadamard codes arise as special cases of these constructions when the simplex code is extended appropriately. A proof relies on theorems for the supports of codewords and their in designs. Assuming the code is , the constant implies that any two nonzero codewords have supports intersecting in a fixed size, leading to the code being a over the of scalars and decomposable into components via arguments and uniformity from Assmus-Key theory. Applications of the theorem include deriving bounds on A(n, d, w), the maximum size of a constant-weight of length n, minimum distance d, and weight w, particularly when seeking optimal subsets within linear codes; since non-simplex structures are ruled out, it limits candidates to these geometric constructions, often achieving tightness for parameters tied to projective dimensions.

Notation and Generalizations

Standard Notation

In linear , a linear code over the \mathbb{F}_q is commonly denoted as an [n, k, d]_q code, where n is the of the codewords, k is the dimension of the code (the number of symbols, yielding q^k codewords), and d is the minimum between any two distinct codewords. This notation encapsulates the essential parameters of the code's and error-correcting capability, with the minimum distance d determining the code's ability to correct up to \lfloor (d-1)/2 \rfloor errors. The maximum possible number of codewords in a binary code of length n and minimum distance d is denoted by A(n, d), which represents the size of the largest such code and serves as a benchmark for code optimality. For a linear code C \subseteq \mathbb{F}_q^n, the weight enumerator is defined as W_C(x, y) = \sum_{c \in C} x^{n - \mathrm{wt}(c)} y^{\mathrm{wt}(c)}, where \mathrm{wt}(c) is the Hamming weight of the codeword c, providing a generating function that encodes the full weight distribution of the code. The dual code C^\perp is the set of all vectors u \in \mathbb{F}_q^n such that u \cdot c = 0 for every c \in C, where \cdot denotes the standard dot product over \mathbb{F}_q; this dual has dimension n - k and plays a central role in duality theorems. A between a and its is given by the MacWilliams identity, which for linear codes states that W_{C^\perp}(x, y) = \frac{1}{|C|} W_C(x + y, x - y), linking the weight enumerators and derivations of bounds from . For Bose-Chaudhuri-Hocquenghem (BCH) codes, the BCH bound provides a lower bound on the minimum distance: if the code is designed to correct t errors, then d \geq 2t + 1, ensuring the code meets or exceeds this distance based on the roots of its generator polynomial. The covering radius \rho of a C is the smallest nonnegative integer such that the union of Hamming balls of radius \rho centered at codewords covers the entire ambient space \mathbb{F}_q^n, quantifying the code's efficiency in approximating arbitrary vectors. The standardization of this notation traces its roots to Claude Shannon's seminal paper on , which laid the probabilistic foundations without explicit code parameters, evolving through mid-20th-century developments in algebraic to the comprehensive framework in modern references like the text by MacWilliams and Sloane.

q-ary Linear Codes

q-ary linear codes generalize linear codes by defining them over the \mathbb{F}_q, where q = p^m for a prime p and m \geq 1. A q-ary linear is a k-dimensional subspace of the \mathbb{F}_q^n, consisting of codewords that are vectors in \mathbb{F}_q^n closed under addition and scalar multiplication by elements of \mathbb{F}_q. The parameters of such a code are denoted [n, k, d]_q, where n is the length, k is the dimension (yielding q^k codewords), and d is the minimum Hamming distance. Unlike codes, which use symbols from \{0,1\}, q-ary codes employ symbols from \mathbb{F}_q, allowing for larger alphabets that scale the code's capacity and error-correcting potential with q. Key constructions for q-ary linear codes include () codes, which are built by evaluating functions from Riemann-Roch spaces on rational points of an over \mathbb{F}_q. For a curve of g and divisors D and G with \operatorname{supp}(G) \cap \operatorname{supp}(D) = \emptyset, the AG code C(L, D, G) has length n = \deg(D), dimension at least \deg(G) - g + 1, and minimum distance at least n - \deg(G). Goppa codes serve as q-ary analogs to BCH codes, constructed using a g(x) (the Goppa ) over \mathbb{F}_q and a set L of distinct elements in \mathbb{F}_q, defining the code as the kernel of a parity-check matrix derived from residues of powers of g^{-1}. Reed-Solomon codes exemplify prime-power q-ary linear codes, achieving the Singleton bound for lengths up to q. Properties of q-ary linear codes include the q-ary Hamming bound, which limits the size of an error-correcting code capable of correcting t = \lfloor (d-1)/2 \rfloor errors: q^k \sum_{i=0}^t \binom{n}{i} (q-1)^i \leq q^n. This sphere-packing bound arises from the non-overlapping volumes of Hamming balls of radius t around codewords in \mathbb{F}_q^n. For subfield subcodes, trace duality relates the dual of a trace code over \mathbb{F}_{q^m} to the trace of the dual code, providing a framework for analyzing dimensions and weights when restricting to a subfield \mathbb{F}_q. q-ary codes offer advantages such as higher rates for the same minimum distance d compared to binary codes, particularly in burst error correction, where a single erroneous symbol can represent multiple bit errors without amplifying the overall error count. The of q-ary linear codes marked a shift from the binary focus of the 1950s, exemplified by Hamming codes, to non-binary extensions in the with the introduction of Reed-Solomon codes, which enabled efficient correction over larger alphabets. This evolution continued in the and 1980s with Goppa's geometric constructions, leading to AG codes that asymptotically surpass previous bounds for sufficiently large q.