Linear Codes Sample Clauses

Linear Codes. A linear q-ary code of length n and rank k is a subspace C with dimension k of the vector space Fn. The vectors in C are called codewords. The size of a code is the number of codewords it contains, and is thus equal to qk. The weight of a word w Fn is the number of its non-zero components, and the distance between two words is the Hamming distance between them (equivalently, the weight of their difference). The minimal distance d of a linear code C is the minimum weight of its non-zero codewords, or equivalently, the minimum distance between any two distinct codewords. A code for an alphabet of size q, of length n, rank k, and minimal distance d is called an (n, k, d)q-code. Such a code can be used to detect up to d − 1 errors (because if a codeword is sent and fewer than d− 1 errors occur, it will not get transformed to another codeword), and correct up to |(d − 1)/2∫ errors (because for any received word, there is a unique codeword within distance |(d − 1)/2∫). For linear codes, the encoding of a (row vector) word W ∈ Fk is performed by an algorithm C.Encode : Fk → Fn, which is the multiplication of W by a so-called “generating matrix” G ∈ Fk×n (which defines an injective linear map). This leads to a row-vector codeword W G =: c C Fn. The Xxxxxxxxx bound states that for any linear code, it holds that k + d n + 1. A maximum distance separable (or MDS) code satisfies k + d = n + 1. Since d = n k + 1, MDS codes are fully described by the parameters (q, n, k). Such an (n, k)q-MDS code can correct up to (n k)/2 errors; it can detect if there are errors whenever there are no more than n k of them. For a matrix G generating an MDS code, any set of k columns of G are linearly independent. For a thorough introduction to linear codes and proofs of all statements in this short overview we refer the reader to [Rot06]. Observe that a linear code, due to the linearity of its encoding algorithm, is not a primitive designed to hide anything about the encoded message (e.g., a popular choice for the generating matrix is G := (Ik ) with Ik being the k k identity matrix). However, we show in the following lemma how to turn an MDS code into a RSS scheme with additional smoothness guarantees.