Linear Codes over Finite Fields
- Introduction
- Construction of Codes
- Construction of General Linear Codes
- Some Trivial Linear Codes
ZeroCode(R, n): FldFin, RngIntElt → CodeRepetitionCode(R, n): FldFin, RngIntElt → CodeZeroSumCode(R, n): FldFin, RngIntElt → CodeUniverseCode(R, n): FldFin, RngIntElt → CodeEvenWeightCode(n): RngIntElt → CodeEvenWeightSubcode(C): Code → CodeRandomLinearCode(K, n, k): FldFin, RngIntElt, RngIntElt → CodeCordaroWagnerCode(n): RngIntElt → Code- Example: Chain of Trivial Linear Codes
- Some Basic Families of Codes
- Invariants of a Code
- Operations on Codewords
- Construction of a Codeword
- Arithmetic Operations on Codewords
- Distance and Weight
- Vector Space and Related Operations
(u, v): ModTupRngElt, ModTupRngElt → RngEltInnerProduct(u, v): ModTupRngElt, ModTupRngElt → RngEltSupport(w): ModTupRngElt → { RngIntElt }Coordinates(C, u): Code, ModTupRngElt → [ RngFinElt ]Parent(w): ModTupRngElt → ModTupRngRotate(u, k): ModTupRngElt, RngIntElt → ModTupRngEltRotate(~u, k): ModTupRngElt, RngIntEltTrace(u, S): ModTupFldElt, FldFin → ModTupFldEltTrace(u): ModTupFldElt → ModTupFldElt- Example: Coordinates of a Code Word
- Predicates for Codewords
- Accessing Components of a Codeword
- Coset Leaders
- Subcodes
- The Subcode Constructor
sub<C | L>: Code, List → CodeSubcode(C, k): Code, RngIntElt → CodeSubcode(C, S): Code, { RngIntElt } → CodeSubcodeBetweenCode(C1, C2, k): Code, Code, RngIntElt → CodeSubcodeWordsOfWeight(C, S): Code, { RngIntElt } → Code- Example: Subcode between Two Codes
- Sum, Intersection, Duals, and Hulls
- Membership and Equality
- Properties of Codes
- The Weight Distribution
- The Minimum Weight
MinimumWeight(C: parameters): Code → RngIntEltMinimumDistance(C: parameters): Code → RngIntEltMinimumWeightBounds(C): Code → RngIntElt, RngIntEltResetMinimumWeightBounds(C): CodeVerifyMinimumDistanceLowerBound(C, d): Code, RngIntElt → BoolElt, RngIntElt, BoolEltVerifyMinimumDistanceUpperBound(C, d): Code, RngIntElt → BoolElt, RngIntElt, BoolEltVerifyMinimumWeightUpperBound(C, d: parameters): Code, RngIntElt → BoolElt, RngIntElt, BoolEltMinimumWord(C): Code → ModTupFldEltMinimumWords(C): Code → { ModTupFldElt }- Example: Verifying a Minimum Weight Lower Bound
IncludeAutomorphism(~C, p): Code, GrpPermEltIncludeAutomorphism(~C, G): Code, GrpPermKnownAutomorphismSubgroup(C): Code → GrpPerm
- The Weight Distribution
- The Weight Enumerator
- The MacWilliams Transform
MacWilliamsTransform(n, k, q, W): RngIntElt, RngIntElt, RngIntElt, [ <RngIntElt, RngIntElt> ] → [ <RngIntElt, RngIntElt> ]MacWilliamsTransform(n, k, K, W): RngIntElt, RngIntElt, FldFin, RngMPol → RngMPol- Example: MacWilliams Transform
- Words
Words(C, w: parameters): Code, RngIntElt → { ModTupFldElt }NumberOfWords(C, w): Code, RngIntElt → RngIntEltWordsOfBoundedWeight(C, l, u: parameters): Code, RngIntElt, RngIntElt → { ModTupFldElt }ConstantWords(C, i): Code, RngIntElt → { ModTupFldElt }NumberOfConstantWords(C, i): Code, RngIntElt → RngIntElt- Example: Words of a Given Weight
- Covering Radius and Diameter
- Families of Linear Codes
- Cyclic and Quasicyclic Codes
CyclicCode(u): ModTupRngElt → CodeCyclicCode(n, T, K): RngIntElt, [ FldFinElt ], FldFin → CodeCyclicCode(n, T, K): RngIntElt, { FldFinElt }, FldFin → CodeQuasiCyclicCode(n, Gen): RngIntElt, [ RngUPolElt ] → CodeQuasiCyclicCode(Gen): [ ModTupRngElt ] → CodeQuasiCyclicCode(n, Gen, h): RngIntElt, [ RngUPolElt ], RngIntElt → CodeQuasiCyclicCode(Gen, h): [ModTupRngElt], RngIntElt → CodeConstaCyclicCode(n, f, alpha): RngIntElt, RngUPolElt, FldFinElt → CodeQuasiTwistedCyclicCode(n, Gen, alpha): RngIntElt, [RngUPolElt], FldFinElt → CodeQuasiTwistedCyclicCode(Gen, alpha): [ModTupRngElt], FldFinElt → CodeQuasiTwistedCyclicCode(n, Gen, alpha, h): RngIntElt, [RngUPolElt], FldFinElt, RngIntElt → CodeQuasiTwistedCyclicCode(Gen, alpha, h): [ModTupRngElt], FldFinElt, RngIntElt → Code- Example: Chain of Cyclic Codes
- Example: Constacyclic Code
- BCH Codes and their Generalizations
BCHCode(K, n, d, b): FldFin, RngIntElt, RngIntElt, RngIntElt → CodeBCHCode(K, n, d): FldFin, RngIntElt, RngIntElt → Code- Example: BCH Code
GoppaCode(L, G): [ FldFinElt ], RngUPolElt → Code- Example: Goppa Code
ChienChoyCode(P, G, n, S): RngUPolElt, RngUPolElt, RngIntElt, FldFin → CodeAlternantCode(A, Y, r, S): [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin → CodeAlternantCode(A, Y, r): [ FldFinElt ], [ FldFinElt ], RngIntElt → Code- Example: Alternant Code
NonPrimitiveAlternantCode(n, m, r): RngIntElt, RngIntElt, RngIntElt → CodeFireCode(h, s, n): RngUPolElt, RngIntElt, RngIntElt → CodeGabidulinCode(A, W, Z, t): [ FldFinElt ], [ FldFinElt ], [ FldFinElt ], RngIntElt → CodeSrivastavaCode(A, W, mu, S): [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin → CodeGeneralizedSrivastavaCode(A, W, Z, t, S): [ FldFinElt ], [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin → Code
- Quadratic Residue Codes and their Generalizations
QRCode(K, n): FldFin, RngIntElt → CodeGolayCode(K, ext): FldFin, BoolElt → CodeDoublyCirculantQRCode(p): RngIntElt → CodeDoublyCirculantQRCodeGF4(m, a): RngIntElt, RngElt → CodeBorderedDoublyCirculantQRCode(p, a, b): RngIntElt, RngElt, RngElt → CodeTwistedQRCode(l, m): RngIntElt, RngIntElt → CodePowerResidueCode(K, n, p): FldFin, RngIntElt, RngIntElt → Code- Example: Quadratic Residue Code
- Reed–Solomon and Justesen Codes
ReedSolomonCode(K, d, b): FldFin, RngIntElt, RngIntElt → CodeReedSolomonCode(K, d): FldFin, RngIntElt → CodeReedSolomonCode(n, d): RngIntElt, RngIntElt → CodeReedSolomonCode(n, d, b): RngIntElt, RngIntElt, RngIntElt → CodeGRSCode(A, V, k): [ FldFinElt ], [ FldFinElt ], RngIntElt → CodeJustesenCode(N, K): Code, FldFinElt, RngIntElt → Code- Example: Generalized Reed-Solomon Code
- Maximum Distance Separable Codes
- New Codes from Existing
- Standard Constructions
AugmentCode(C): Code → CodeCodeComplement(C, C1): Code, Code → CodeDirectSum(C, D): Code, Code → CodeDirectSum(Q): [Code] → CodeDirectProduct(C, D): Code, Code → CodeProductCode(C, D): Code, Code → CodeExtendCode(C): Code → CodeExtendCode(C, n): Code, RngIntElt → CodePadCode(C, n): Code, RngIntElt → CodeExpurgateCode(C): Code → CodeExpurgateCode(C, L): Code, [ModTupFldElt] → CodeExpurgateWeightCode(C, w): Code, RngIntElt → CodeLengthenCode(C): Code → CodePlotkinSum(C1, C2): Code, Code → CodePlotkinSum(C1, C2, C3: parameters): Code, Code, Code → CodePunctureCode(C, i): Code, RngIntElt → CodePunctureCode(C, S): Code, { RngIntElt } → CodeShortenCode(C, i): Code, RngIntElt → CodeShortenCode(C, S): Code, { RngIntElt } → Code- Example: Constructing a [12,4,6] Code
- Changing the Alphabet of a Code
ExtendField(C, L): Code, FldFin → Code, MapLinearCode(C, S): Code, FldFin → Code, MapSubfieldRepresentationCode(C, K): Code, FldFin → CodeSubfieldRepresentationParityCode(C, K): Code, FldFin → CodeSubfieldSubcode(C, S): Code, FldFin → Code, MapRestrictField(C, S): Code, FldFin → Code, MapSubfieldSubcode(C): Code → Code, MapRestrictField(C): Code → Code, MapSubfieldCode(C, S): Code, FldFin → CodeTrace(C, F): Code, FldFin → CodeTrace(C): Code → Code
- Combining Codes
C1 cat C2: Code, Code → CodeJuxtaposition(C1, C2): Code, Code → CodeConcatenatedCode(O, I): Code, Code → Code- Example: Concatenated Code
ConstructionX(C1, C2, C3): Code, Code, Code → CodeConstructionXChain(S, C): [Code], Code → [Code]- Example: Construction X
ConstructionX3(C1, C2, C3, D1, D2): Code, Code, Code, Code, Code → Code, MapConstructionX3u(C1, C2, C3, D1, D2): Code, Code, Code, Code, Code → Code, Code- Example: Construction X3
ConstructionXX(C1, C2, C3, D2, D3): Code, Code, Code, Code, Code → Code- Example: Construction XX
ZinovievCode(I, O): [Code], [Code] → Code- Example: Zinoviev Code
ConstructionY1(C): Code → CodeConstructionY1(C, w): Code, RngIntElt → Code
- Bounds
- Best Known Bounds for Linear Codes
BKLCLowerBound(F, n, k): FldFin, RngIntElt, RngIntElt → RngIntEltBKLCUpperBound(F, n, k): FldFin, RngIntElt, RngIntElt → RngIntEltBLLCLowerBound(F, k, d): FldFin, RngIntElt, RngIntElt → RngIntEltBLLCUpperBound(F, k, d): FldFin, RngIntElt, RngIntElt → RngIntEltBDLCLowerBound(F, n, d): FldFin, RngIntElt, RngIntElt → RngIntEltBDLCUpperBound(F, n, d): FldFin, RngIntElt, RngIntElt → RngIntElt
- Bounds on the Cardinality of a Largest Code
EliasBound(K, n, d): FldFin, RngIntElt, RngIntElt → RngIntEltGriesmerBound(K, n, d): FldFin, RngIntElt, RngIntElt → RngIntEltJohnsonBound(n, d): RngIntElt, RngIntElt → RngIntEltLevenshteinBound(K, n, d): FldFin, RngIntElt, RngIntElt → RngIntEltPlotkinBound(K, n, d): FldFin, RngIntElt, RngIntElt → RngIntEltSingletonBound(K, n, d): FldFin, RngIntElt, RngIntElt → RngIntEltSpherePackingBound(K, n, d): FldFin, RngIntElt, RngIntElt → RngIntEltGilbertVarshamovBound(K, n, d): FldFin, RngIntElt, RngIntElt → RngIntEltGilbertVarshamovLinearBound(K, n, d): FldFin, RngIntElt, RngIntElt → RngIntEltVanLintBound(K, n, d): FldFin, RngIntElt, RngIntElt → RngIntElt- Example: Computed and Stored Cardinality Bounds
- Bounds on the Minimum Distance
- Asymptotic Bounds on the Information Rate
- Other Bounds
- Best Known Linear Codes
BKLC(K, n, k): FldFin, RngIntElt, RngIntElt → Code, BoolEltBestKnownLinearCode(K, n, k): FldFin, RngIntElt, RngIntElt → Code, BoolEltBLLC(K, k, d): FldFin, RngIntElt, RngIntElt → Code, BoolEltBestLengthLinearCode(K, k, d): FldFin, RngIntElt, RngIntElt → Code, BoolEltBDLC(K, n, d): FldFin, RngIntElt, RngIntElt → Code, BoolEltBestDimensionLinearCode(K, n, d): FldFin, RngIntElt, RngIntElt → Code- Example: Best Known Binary Codes
- Example: Best Known Quaternary Codes
- Example: Best Known Lengths of Binary Codes
- Example: Best Known Dimensions of Quaternary Codes
- Example: Reconstructing a Best Known Code
- Decoding
- Syndrome Decoding
- Euclidean Decoding
- Permutation Decoding
IsPermutationDecodeSet(C, I, S, s): CodeLinFld, [RngIntElt], [AlgMatElt], RngIntElt → BoolEltIsPermutationDecodeSet(C, I, S, s): CodeLinFld, [RngIntElt], [GrpPermElt], RngIntElt → BoolEltPermutationDecode(C, I, S, s, u): CodeLinFld, [RngIntElt], [AlgMatElt], RngIntElt, ModTupFldElt → BoolElt, ModTupFldEltPermutationDecode(C, I, S, s, u): CodeLinFld, [RngIntElt], [GrpPermElt], RngIntElt, ModTupFldElt → BoolElt, ModTupFldEltPermutationDecode(C, I, S, s, Q): CodeLinFld, [RngIntElt], [AlgMatElt], RngIntElt, [ModTupFldElt] → [BoolElt], [ModTupFldElt]PermutationDecode(C, I, S, s, Q): CodeLinFld, [RngIntElt], [GrpPermElt], RngIntElt, [ModTupFldElt] → [BoolElt], [ModTupFldElt]PDSetSimplexCode(K, m): FldFin, RngIntElt → SeqEnum, SeqEnum, SeqEnumPDSetHadamardCode(m): RngIntElt → SeqEnum, SeqEnum, SeqEnum- Example: Permutation Decoding of a Binary Code
- Example: Permutation Decoding of a Quaternary Code
- Transforms
- Mattson–Solomon Transforms
- Krawchouk Polynomials
KrawchoukPolynomial(K, n, k): FldFin, RngIntElt, RngIntElt → RngUPolEltKrawchoukTransform(f, K, n): RngUPolElt, FldFin, RngIntElt → RngUPolEltInverseKrawchouk(A, K, n): RngUPolElt, FldFin, RngIntElt → RngUPolElt
- Automorphism Groups
- Introduction
- Group Actions
v ^ x: ModTupFldElt, GrpPermElt → ModTupFldEltv ^ G: ModTupFldElt, GrpPerm → GSet{ ModTupFldElt }C ^ x: Code, GrpPermElt → CodeC ^ G: Code, GrpPerm → GSet{ Code }S ^ x: [ModTupFldElt], GrpPermElt → [ModTupFldElt]S ^ x: { ModTupFldElt }, GrpPermElt → { ModTupFldElt }S ^ x: [Code], GrpPermElt → [Code]S ^ x: { Code }, GrpPermElt → { Code }Fix(C, G): Code, GrpPerm → Code
- Automorphism Group
AutomorphismGroup(C: parameters): Code → GrpPerm, PowMap, MapMonomialGroup(C: parameters): Code → GrpPerm, PowMap, MapPermutationGroup(C): Code → GrpPerm, PowMap, MapAutomorphismSubgroup(C): Code → GrpPerm, PowMap, MapMonomialSubgroup(C): Code → GrpPerm, PowMap, MapAutomorphismGroupStabilizer(C, k): Code, RngIntElt → GrpPerm, PowMap, MapMonomialGroupStabilizer(C, k): Code, RngIntElt → GrpPerm, PowMap, MapAut(C): Code → Pow, MapAut(C, T): Code, MonStgElt → Pow, Map- Example: Automorphism Group of a Reed-Muller Code
- Example: Automorphism Group via Minimum Weight Words
- Equivalence and Isomorphism of Codes
- Bibliography