Linear codes and the affine line
Dimension and infinite families
An optimal code C of type [n, k, d] achieves the highest possible dimension for its specified length and minimum distance For a set of optimal codes represented as {[ni, ki, di]} with increasing lengths, the limit of di/ni as it approaches δ defines α(δ) as the limit superior of ki/ni.
An optimal code must have at least one vector in each of its \( q^n - k \) cosets in \( F^n \) such that the distance \( d(y,0) < d \) The Gilbert-Varshamov bound establishes the lower limit for the dimension of an optimal code, expressed as \( q^n - k \leq |{y \in F^n : d(y,0) < d}| \).
1 nlog|{y ∈F n :d(y,0)< δn}|=Hq(δ) +o(1), whereHq(x) =xlog q (q−1)−xlog q x−(1−x) log q (1−x),for 0< x≤θ.
Theorem 1.1.(asymptotic Gilbert-Varshamov bound) For an infinite fam- ily of optimal codes with relative distance d/n=δ, α(δ)≥1−Hq(δ), for 0< δ ≤θ.
Lemma 1.2 For aq-ary linear code withk > m+1andn−k > m(q m+1 −
1)/(q−1) −(m+ 1)the information defect is at leastm.
To prove the theorem, we divide the coordinates into a subset of k−(m+ 1) independent coordinates and a complement consisting of n−k+ (m+ 1) coordinates, which is greater than m(q m+1 −1)/(q−1) Within the subcode that has zeros in the k−(m+ 1) coordinates, there exists a block of at least m+ 1 size where the nonzero coordinates are essentially repeated Consequently, the combined total of k−(m+ 1) and (m+ 1) coordinates contains only k−m information symbols.
In families of q-ary linear codes where both k and n-k approach infinity, the information defect and genus also increase indefinitely This leads to an upper bound on the dimension of an optimal code.
Theorem 1.3 (asymptotic Plotkin bound) For an infinite family of codes withk, n−k→ ∞, we haved≤θ(n−k)asn−→ ∞, or α(δ)≤1−δ/θ, for 0< δ ≤θ.
Duality and differentials
Let \( C \) be a linear code of length \( n \) By omitting the \( i \)-th coordinate, we obtain the punctured code \( P_i(C) \), which has a length of \( n-1 \) The shortened code \( S_i(C) \) consists of the subcode of \( P_i(C) \) that includes only those words where the omitted \( i \)-th coordinate is equal to zero.
In generalP(C) ⊥ =S(C ⊥ ).For a subset P ={a1, a2, , an}of the field
The codeC(< k,P) is a punctured version of the codeC(< k,F) The dual code is a shortened version of the codeC(< q−k,F).
Letp(x) = (x−a1)(x−a2)ã ã ã(x−an) and letx q −x =p(x)r(x) Then
−1 =p 0 (ai)r(ai), fori= 1,2, , n.Withf of the formf =rh,
We give a description of the dual code using differentials For a polynomial h∈F[x] of degree degh < n, let ω= h pdx= ( c1 x−a1
)dx be a differential with at most simple poles and with residuesc1, c2, , cn atx=a1, a2, , an,respectively Thenh(ai) =cip 0 (ai) and
C(< k,P) ⊥ ={(resa 1(ω),resa 2(ω), ,resa n(ω)) : ω=h pdx, degh < n−k}.
Minimum distance
Several useful inequalities exist for the parameters of codesA, B, C with
The Hadamard product, denoted as Leta∗b= (a1b1, a2b2, , anbn), represents the coordinate-wise multiplication of two vectors a and b The relationship among sets A, B, and C can be expressed as A∗B = {a∗b: a∈A, b∈B} ⊂ C⊥ This decomposition of the dual code using the Hadamard product is fundamental for establishing various bounds on the minimum distance.
Theorem 1.4 (Roos bound for linear codes) For a linear codeC, and for linear codes A andB withA∗B⊂C ⊥ , g(A)< d(B ⊥ )−1 ⇒ d(C)≥k(A) +d(B ⊥ )−1.
Proof It is enough to show that for every subset I of (k(A)−1) +
In the positions defined by (d(B ⊥ )−1), there exists a unique word a∗b in the set A∗B that has only one nonzero coordinate First, select an element a from A that has zeros in k(A)−1 positions within I Next, choose an element b from B that has a single nonzero coordinate in the remaining d(B ⊥ )−1 positions, ensuring that this nonzero coordinate aligns with a position where a is also nonzero This selection is feasible because a contains fewer than n−d(A) zeros, which is less than k(A)−1 plus d(B ⊥ )−1.
Theorem 1.5 (Symmetric Roos bound for linear codes) For a linear code
C, and for linear codes AandB withA∗B⊂C ⊥ , g(A)< k(B) andg(B)< k(A)
The two versions of the Roos bound can be used in combination, with different choices forAandB, to produce stronger results.
Theorem 1.6 (Shift bound or Coset bound) Let C be a linear code and let C1 ⊂ C be a maximal subcode If there exist vectors a1, , aw and b1, , bw such that
(ai∗bj∈C ⊥ for i+j≤w, ai∗bj∈C 1 ⊥ \C ⊥ for i+j=w+ 1, then words in C\C1 have weight at leastw.
In this proof, we establish that for all elements \( c \) in \( C \setminus C_1 \) and \( a^*b \) in \( C_1^\perp \setminus C^\perp \), the product \( P_{i}a_{i}b_{i}c_{i} \) is non-zero It is essential to demonstrate the existence of a vector \( a^*b \) in \( C_1^\perp \setminus C^\perp \) that vanishes in any chosen \( w-1 \) coordinates The linear independence of vectors \( a_1, \ldots, a_w \) implies there is a nonzero linear combination \( a \) of these vectors that equals zero in the specified coordinates If \( i \) is the highest index where \( a_i \) has a nonzero coefficient in this combination, then \( a^*b_{w+1-i} \) will also belong to \( C_1^\perp \setminus C^\perp \) and will vanish in the \( w-1 \) coordinates.
Theorem 1.7 (Iterated coset bound) Repeated application of the coset bound to a sequence Cr ⊂ ã ã ã ⊂ C1 ⊂ C0 = C gives the lower bound d(C)≥min{d1, d2, , dr, d(Cr)}, whered(Ci − 1/Ci)≥di is obtained with the coset bound.
Error correction
LetA,B, andC be nondegenerate linear codes such that
Ifk(A)> tandd(B ⊥ )> tthen (A, B) is called at-error-locating pair for
C For a given error-locating pair the error positions in a received word can be located by solving a suitable system of linear equations.
Theorem 1.8 Let(A, B) be at-error-locating pair for C For c∈C and for a vector e of weight at most t, let y =c+e Every vector a∈A with a∗y⊥b for allb∈B has the property a∗e= 0.
An error-locating pair for a code C is termed error-correcting if the sum of the distances d(A) and d(C) exceeds n With such an error-correcting pair, a codeword can be retrieved from the zeros present in an error-locating vector a ∈ A by resolving a corresponding system of linear equations.
Theorem 1.9 Let (A, B) be a t-error-correcting pair for C For c ∈ C and for a vector e of weight at most t, let y =c+e Let a∈A have the property a∗e = 0 Then c ∈ C is the unique solution to the system of equations c∈C and a∗c=a∗y.
The key equationa∗y ⊥b for all b ∈ B amounts to a linear system of dim (B) equations in dim (A) unknowns A different formulation gives a key equation withnlinear equations in dim (A) + dim (B ⊥ ) unknowns.
Theorem 1.10 For c ∈ C and for a vector e of weight at most t, let y=c+e For every pair of vectorsa∈A,ˆb∈B ⊥ witha∗y= ˆb, the vector c is the unique solution to the system of equationsc∈C anda∗c= ˆb.
Decoding is often incomplete with c ∈ C, as c serves only as an encoding of the relevant information symbols In these situations, it may be more effective to directly solve for the information symbols instead of computing c The t-error-correcting code C(< q−2t,F) features an error-correcting pair defined as (A = C(≤t,F), B = C(< t,F) The crucial equation for an error-locating vector involves determining g(x) ∈ F[x] ≤ t.
X i yig(xi)h(xi) = 0, for allh∈F[x]