For an element x∈Z4, the Gray map φ: Z4 -> Z22 is defined by: 0 |-> 00, 1 |-> 01, 2 |-> 11, 3 |-> 10. This map is extended to a map from Z4n onto Z22n in the obvious way (by concatenating the images of each component). The resulting map is a weight- and distance-preserving map from Z4n (with Lee weight metric) to Z22n (with Hamming weight metric). See [Wan97, Chapter 3] for more information (but note that that author uses a different ordering of the components of the image of a vector).
Given a Z4-linear code C, this function returns the Gray map for C. This is the map φ from C to GF(2)2n, as defined above.
Given a Z4-linear code C, this function returns the image of C under the Gray map as a sequence of vectors in GF(2)2n. As the resulting image may not be a GF(2)-linear code, a sequence of vectors is returned rather than a code.
Given a Z4-linear code C, this function returns true if and only if the image of C under the Gray map is a GF(2)-linear code. If so, the function also returns the image B as a GF(2)-linear code, together with the bijection φ: C -> B.
> Z4 := IntegerRing(4);
> O8 := LinearCode<Z4, 8 |
> [1,0,0,0,3,1,2,1],
> [0,1,0,0,1,2,3,1],
> [0,0,1,0,3,3,3,2],
> [0,0,0,1,2,3,1,1]>;
> HasLinearGrayMapImage(O8);
false
> NR := GrayMapImage(O8);
> #NR;
256
> LeeWeightDistribution(O8);
[ <0, 1>, <6, 112>, <8, 30>, <10, 112>, <16, 1> ]
> {* Weight(v): v in NR *};
{* 0, 16, 6^^112, 8^^30, 10^^112 *}
After defining the code K8, the images of some codewords under
the Gray map are found.
> Z4 := IntegerRing(4); > K8 := LinearCode< Z4, 8 | > [1,1,1,1,1,1,1,1], > [0,2,0,0,0,0,0,2], > [0,0,2,0,0,0,0,2], > [0,0,0,2,0,0,0,2], > [0,0,0,0,2,0,0,2], > [0,0,0,0,0,2,0,2], > [0,0,0,0,0,0,2,2]>; > f := GrayMap(K8); > K8.1; (1 1 1 1 1 1 1 1) > f(K8.1); (0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) > K8.2; (0 2 0 0 0 0 0 2) > f(K8.2); (0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1)The image of K8 under the Gray map is a linear code over GF(2).
> l, B, g := HasLinearGrayMapImage(K8); > l; true > B; [16, 8, 4] Linear Code over GF(2) Generator matrix: [1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0] [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1] [0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1] [0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1] [0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1] [0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1] [0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1] [0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1] > g(K8.1) in B; true
This section presents some standard constructions for Z4-linear codes. Further constructions will become available in the near future.
Given an integer m≥2, return the quaternary Kerdock code K(m) of length 2m - 1 defined by a default primitive polynomial h∈Z4[x] of degree m.
Given an integer m≥2, return the quaternary Preparata code P(m) of length 2m - 1 defined by a default primitive polynomial h∈Z4[x] of degree m.
Given an integer m ≥2 and an integer r such that 0 ≤r ≤m this function returns the r-th order Reed-Muller code over Z4 of length 2m.
Given a positive integer m, where m must be an odd and greater than or equal to 3, return the Goethals code of length 2m.
Return the Delsarte-Goethals Code of length 2m.
Return the Goethals-Delsarte code of length 2m
Given a prime number p such that 2 is a quadratic residue modulo p, return the quadratic residue code of length p over Z4.
Return the Golay Code over Z4. If e is true then return the extended Golay Code
Return the simplex alpha code over Z4 of degree k.
Return the simplex beta code over Z4 of degree k.
> PreparataCode(3); (8, 256, 4) Linear Code over IntegerRing(4) Generator matrix: [1 0 0 0 3 1 2 1] [0 1 0 0 2 1 1 3] [0 0 1 0 1 1 3 2] [0 0 0 1 3 2 3 3] > MinimumLeeWeight($1); 6 > KerdockCode(4); [16, 5, 8] Linear Code over IntegerRing(4) Generator matrix: [1 0 0 0 0 1 1 3 0 3 3 0 2 1 2 3] [0 1 0 0 0 2 3 3 3 2 1 3 0 0 1 1] [0 0 1 0 0 3 1 0 3 0 3 1 1 3 2 2] [0 0 0 1 0 2 1 3 0 1 2 3 1 3 3 0] [0 0 0 0 1 1 3 0 3 3 0 2 1 2 1 3] > MinimumLeeWeight($1); 12 > KerdockCode(5); (32, 4096, 16) Linear Code over IntegerRing(4) Generator matrix: [1 0 0 0 0 0 3 3 3 2 0 3 2 2 0 3 0 1 0 1 3 1 1 0 3 1 2 3 2 2 3 3] [0 1 0 0 0 0 3 2 2 1 2 3 1 0 2 3 3 1 1 1 0 0 2 1 3 0 3 1 1 0 1 2] [0 0 1 0 0 0 1 0 3 0 1 3 1 3 0 3 3 2 1 0 2 3 3 2 2 2 2 0 3 3 1 3] [0 0 0 1 0 0 1 2 1 1 0 2 1 3 3 1 3 2 2 0 1 1 2 3 3 1 0 3 2 1 0 0] [0 0 0 0 1 0 0 1 2 1 1 0 2 1 3 3 1 3 2 2 0 1 1 2 3 3 1 0 3 2 1 0] [0 0 0 0 0 1 1 1 2 0 1 2 2 0 1 0 3 0 3 1 3 3 0 1 3 2 1 2 2 1 3 1] > MinimumLeeWeight($1); 28
Given an integer m≥1 and an integer δ such that 1≤δ ≤⌊(m + 1)/2 ⌋, return a Hadamard code over Z4 of length 2m - 1 and type 2γ 4δ, where γ=m + 1 - 2δ. Moreover, return a generator matrix with γ + δ rows constructed in a recursive way from the Plotkin and BQPlotkin constructions defined in Section New Codes from Old.A Hadamard code over Z4 of length 2m - 1 is a code over Z4 such that, after the Gray map, give a binary (not necessarily linear) code with the same parameters as the binary Hadamard code of length 2m.
Given an integer m≥2 and an integer δ such that 1≤δ ≤⌊(m + 1)/2 ⌋, return an extended perfect code over Z4 of length 2m - 1, such that its dual code is of type 2γ 4δ, where γ=m + 1 - 2δ. Moreover, return a generator matrix constructed in a recursive way from the Plotkin and BQPlotkin constructions defined in Section New Codes from Old.An extended perfect code over Z4 of length 2m - 1 is a code over Z4 such that, after the Gray map, give a binary (not necessarily linear) code with the same parameters as the binary extended perfect code of length 2m.
First, a Hadamard code C over Z4 of length 8 and type 2142 is defined. The matrix Gc is the quaternary matrix used to generate C and obtained by a recursive method from Plotkin and BQPlotkin constructions.
> C, Gc := HadamardCodeZ4(2,4); > C; ((8, 4^2 2^1)) Linear Code over IntegerRing(4) Generator matrix: [1 0 3 2 1 0 3 2] [0 1 2 3 0 1 2 3] [0 0 0 0 2 2 2 2] > Gc; [1 1 1 1 1 1 1 1] [0 1 2 3 0 1 2 3] [0 0 0 0 2 2 2 2] > HasLinearGrayMapImage(C); true [16, 5, 8] Linear Code over GF(2) Generator matrix: [1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0] [0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1] [0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1] [0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0] [0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1] Mapping from: CodeLinRng: C to [16, 5, 8] Linear Code over GF(2) given by a rule
Then, an extended perfect code D over Z4 of length 8 is defined, such that its dual code is of type 2142. The matrix Gd is the quaternary matrix which is used to generate D and obtained in a recursive way from Plotkin and BQPlotkin constructions. Note that the code D is the Kronecker dual code of C.
> D, Gd := ExtendedPerfectCodeZ4(2,4); > D; ((8, 4^5 2^1)) Linear Code over IntegerRing(4) Generator matrix: [1 0 0 1 0 0 1 3] [0 1 0 1 0 0 2 2] [0 0 1 1 0 0 1 1] [0 0 0 2 0 0 0 2] [0 0 0 0 1 0 3 2] [0 0 0 0 0 1 2 3] > Gd; [1 1 1 1 1 1 1 1] [0 1 2 3 0 1 2 3] [0 0 1 1 0 0 1 1] [0 0 0 2 0 0 0 2] [0 0 0 0 1 1 1 1] [0 0 0 0 0 1 2 3] > DualKroneckerZ4(C) eq D; true
Given an integer m≥2 and an integer r such that 0≤r≤m, the r-th order Reed-Muller code over Z4 of length 2m is returned.The binary image under the modulo 2 map is the binary linear r-th order Reed-Muller code of length 2m. For r=1 and r=m - 2, the function returns the quaternary linear Kerdock and Preparata code, respectively.
Given an integer m≥1 and an integer r such that 0≤r≤m, a set of r-th order Reed-Muller codes over Z4 of length 2m - 1 is returned.The binary image under the Gray map of any of these codes is a binary (not necessarily linear) code with the same parameters as the binary linear r-th order Reed-Muller code of length 2m. Note that for these codes neither the usual inclusion nor duality properties of the binary linear Reed-Muller family are satisfied.
Given an integer m≥1, an integer r such that 0≤r ≤m, and an integer s such that 0≤s ≤⌊(m - 1)/2 ⌋, return a r-th order Reed-Muller code over Z4 of length 2m - 1, denoted by RMs(r, m), as well as the generator matrix used in the recursive construction.The binary image under the Gray map is a binary (not necessarily linear) code with the same parameters as the binary linear r-th order Reed-Muller code of length 2m. Note that the inclusion and duality properties are also satisfied, that is, the code RMs(r - 1, m) is a subcode of RMs(r, m), r>0, and the code RMs(r, m) is the Kronecker dual code of RMs(m - r - 1, m), r<m.
> C1,G1 := ReedMullerCodeRMZ4(1,1,4); > C2,G2 := ReedMullerCodeRMZ4(1,2,4); > C1; ((8, 4^2 2^1)) Linear Code over IntegerRing(4) Generator matrix: [1 0 3 2 1 0 3 2] [0 1 2 3 0 1 2 3] [0 0 0 0 2 2 2 2] > C2; ((8, 4^5 2^1)) Linear Code over IntegerRing(4) Generator matrix: [1 0 0 1 0 0 1 3] [0 1 0 1 0 0 2 2] [0 0 1 1 0 0 1 1] [0 0 0 2 0 0 0 2] [0 0 0 0 1 0 3 2] [0 0 0 0 0 1 2 3] > C1 subset C2; true > DualKroneckerZ4(C2) eq C1; true
Let m be an integer m≥1, and s an integer such that 0≤s ≤⌊(m - 1)/2 ⌋. This function returns a sequence containing the family of Reed-Muller codes over Z4 of length 2m - 1, that is, the codes RMs(r, m), for all 0≤r≤m.The binary image of these codes under the Gray map gives a family of binary (not necessarily linear) codes with the same parameters as the binary linear Reed-Muller family of codes of length 2m. Note that RMs(0, m) ⊂RMs(1, m) ⊂ ... ⊂RMs(m, m)
> F := ReedMullerCodesRMZ4(0,3); > F; [((4, 4^0 2^1)) Cyclic Linear Code over IntegerRing(4) Generator matrix: [2 2 2 2], ((4, 4^1 2^2)) Cyclic Linear Code over IntegerRing(4) Generator matrix: [1 1 1 1] [0 2 0 2] [0 0 2 2], ((4, 4^3 2^1)) Cyclic Linear Code over IntegerRing(4) Generator matrix: [1 0 0 1] [0 1 0 1] [0 0 1 1] [0 0 0 2], ((4, 4^4 2^0)) Cyclic Linear Code over IntegerRing(4) Generator matrix: [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 1]] > F[1] subset F[2] and F[2] subset F[3] and F[3] subset F[4]; true
As well as the binary image of a quaternary code under the Gray map (see section The Gray Map), there are also two other associated canonical binary codes. They are known the residue and torsion codes, the former being a subcode of the latter.
From any binary code-subcode pair C1 ⊂C2, a quaternary code C can be constructed such that the residue and torsion codes of C will be C1 and C2 respectively. Note that this quaternary code is not unique.
Given a quaternary code C, return the binary code formed by taking each codeword in C modulo 2. This is known as the binary residue code of C.
Given a quaternary code C, return the binary code formed by the support of each codeword in C which is zero modulo 2. This is known as the binary torsion code of C.
Given binary code C1 and C2 such that C1 ⊂C2, return a quaternary code such that its binary residue code is C1 and its binary torsion code is C2.
> C := GolayCodeZ4(false); > C; (23, 4^12 2^0)) Cyclic Code over IntegerRing(4) Generator matrix: [1 0 0 0 0 0 0 0 0 0 0 0 3 1 0 0 2 3 3 3 0 3 2] [0 1 0 0 0 0 0 0 0 0 0 0 2 1 1 0 0 0 1 1 3 2 3] [0 0 1 0 0 0 0 0 0 0 0 0 3 3 1 1 2 3 3 0 1 2 0] [0 0 0 1 0 0 0 0 0 0 0 0 0 3 3 1 1 2 3 3 0 1 2] [0 0 0 0 1 0 0 0 0 0 0 0 2 2 3 3 1 3 0 1 3 2 1] [0 0 0 0 0 1 0 0 0 0 0 0 1 1 2 3 1 2 0 1 1 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 2 3 1 2 0 1 1 0] [0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 2 3 1 2 0 1 1] [0 0 0 0 0 0 0 0 1 0 0 0 1 3 0 1 3 3 0 2 2 1 3] [0 0 0 0 0 0 0 0 0 1 0 0 3 2 3 0 3 2 2 3 2 1 3] [0 0 0 0 0 0 0 0 0 0 1 0 3 0 2 3 2 2 1 1 3 1 3] [0 0 0 0 0 0 0 0 0 0 0 1 3 0 0 2 1 1 1 0 1 2 3] > > CRes := BinaryResidueCode(C); > CTor := BinaryTorsionCode(C); > CRes eq CTor; true > CRes:Minimal; [23, 12, 7] Linear Code over GF(2) > AreEq, _ := IsEquivalent( CRes, GolayCode(GF(2), false) ); > AreEq; trueNote that the canonical code over Z4 corresponding to the derived binary codes CRes and CTor is different to the initial Z4 code C.
> C1 := Z4CodeFromBinaryChain(CRes, CTor); > C1:Minimal; (23, 16777216) Linear Code over IntegerRing(4) > C eq C1; false
The functions described in this section produce a new code over Z4 by modifying in some way the codewords of some given codes over Z4.
Given matrices A and B both over the same ring and with the same number of columns, return the PAB matrix over the same ring of A and B, wherePAB = ( matrix( A & A
0 & B ) ).
Given codes C and D both over the same ring and of the same length, construct the Plotkin sum of C and D. The Plotkin sum consists of all vectors of the form (u | u + v), where u ∈C and v∈D.Note that the Plotkin sum is computed using generator matrices for C and D and the PlotkinSum function for matrices. Thus, this function returns the code over Z4 generated by the matrix PAB defined above, where A and B are the generator matrices for C and D, respectively.
Given two matrices A and B over Z4, both with the same number of columns, return the QPAB matrix over Z4, whereQPAB = ( matrix( A & A & A & A
0 & B & 2B & 3B ) ).
Given two codes C and D over Z4, both of the same length, construct the Quaternary Plotkin sum of C and D. The Quaternary Plotkin sum is a code over Z4 that consists of all vectors of the form (u, u + v, u + 2v, u + 3v), where u ∈C and v ∈D.Note that the Quaternary Plotkin sum is computed using generator matrices of C and D and the QuaternaryPlotkinSum function for matrices, that is, this function returns the code over Z4 generated by the matrix QPAB defined above, where A and B are generators matrices of C and D, respectively.
Given three matrices A, B, and C over Z4, all with the same number of columns, return the BQPABC matrix over Z4, where BQPABC = ( matrix( A & A & A & A
0 & B' & 2B' & 3B'
0 & 0 & hat(B) & hat(B)
0 & 0 & 0 & C
) ),B' is obtained from B replacing the twos with ones in the rows of order two, and hat(B) is obtained from B removing the rows of order two.
Given three codes D, E and F over Z4, all of the same length, construct the BQ Plotkin sum of D, E and F. Let Ge be a generator matrix for E of type 2γ 4δ. The code E' over Z4 is obtained from E by replacing the twos with ones in the γ rows of order two of Ge, and the code hat(E) over Z4 is obtained from E removing the γ rows of order two of Ge.The BQ Plotkin sum is a code over Z4 that consists of all vectors of the form (u, u + v', u + 2v' + hat(v), u + 3v' + hat(v) + z), where u ∈Gd, v' ∈Ge' hat(v) ∈hat(Ge), and z ∈Gf, where Gd, Ge', hat(Ge) and Gf are generator matrices for D, E', hat(E) and F, respectively.
Note that the BQPlotkin sum is computed using generator matrices of D, E and F and the BQPlotkinSum function for matrices. However, this function does not necessarily return the same code over Z4 as that generated by the matrix QPABC defined above, where A, B and C are generators matrices of D, E and F, respectively, as shown in Example H165E7.
Given four matrices A, B, C, and D over Z4, all with the same number of columns, return the DPABC matrix over Z4, where DPABCD = ( matrix( A & A & A & A
0 & B & 2B & 3B
0 & 0 & C & C
0 & 0 & 0 & D
) ).
Given four codes E, F, G and H over Z4, all of the same length, construct the Double Plotkin sum of E, F, G and H. The Double Plotkin sum is a code over Z4 that consists of all vectors of the form (u, u + v, u + 2v + z, u + 3v + z + t), where u ∈E, v ∈F, z ∈G and t ∈H.Note that the Double Plotkin sum is computed using generator matrices of E, F, G and H and the DoublePlotkinSum function for matrices, that is, this function returns the code over Z4 generated by the matrix DPABCD defined above, where A, B, C and D are generator matrices for E, F, G and H, respectively.
Given a code C over Z4 of length 2m, return its Kronecker dual code. The Kronecker dual code of C is C tensor perp = {x ∈Z42m : x .K2m .yt=0, forall y ∈C }, where K2m= tensor j=1m K2, K2=(matrix( 1 & 0
0 & 3
) ) and tensor denotes the Kronecker product of matrices. Equivalently, K2m is a quaternary matrix of length 2m with the vector (1, 3, 3, 1, 3, 1, 1, 3, ... ) in the main diagonal and zeros elsewhere.
> Z4:=IntegerRing(4); > Ga:=Matrix(Z4,1,2,[1,1]); > Gb:=Matrix(Z4,2,2,[1,2,0,2]); > Gc:=Matrix(Z4,1,2,[2,2]); > Ca:=LinearCode(Ga); > Cb:=LinearCode(Gb); > Cc:=LinearCode(Gc); > C:=LinearCode(BQPlotkinSum(Ga,Gb,Gc)); > D:=BQPlotkinSum(Ca,Cb,Cc); > C eq D; false
> Ga := GeneratorMatrix(ReedMullerCodeRMZ4(1,2,3)); > Gb := GeneratorMatrix(ReedMullerCodeRMZ4(1,1,3)); > Gc := GeneratorMatrix(ReedMullerCodeRMZ4(1,0,3)); > C := ReedMullerCodeRMZ4(1,2,4); > Cp := LinearCode(PlotkinSum(Ga, Gb)); > C eq Cp; true > D := ReedMullerCodeRMZ4(2,2,5); > Dp := LinearCode(BQPlotkinSum(Ga, Gb, Gc)); > D eq Dp; true