Open access peer-reviewed chapter - ONLINE FIRST

Z2Z2[u]-Linear and Z2Z2[u]-Cyclic Codes

By Ismail Aydogdu

Submitted: January 18th 2019Reviewed: April 10th 2019Published: October 23rd 2019

DOI: 10.5772/intechopen.86281

Downloaded: 14

Abstract

Additive codes were first introduced by Delsarte in 1973 as subgroups of the underlying abelian group in a translation association scheme. In the case where the association scheme is the Hamming scheme, that is, when the underlying abelian group is of order 2n, the additive codes are of the form Z2α×Z4β with α+2β=n. In 2010, Borges et al. introduced Z2Z4-additive codes which they defined them as the subgroups of Z2α×Z4β. In this chapter we introduce Z2Z2[u]-linear and Z2Z2[u]-cyclic codes where Z2=01 is the binary field and Z2u=01u1+u is the ring with four elements and u2=0. We give the standard forms of the generator and parity-check matrices of Z2Z2[u]-linear codes. Further, we determine the generator polynomials for Z2Z2u-linear cyclic codes. We also present some examples of Z2Z2[u]-linear and Z2Z2[u]-cyclic codes.

Keywords

  • Z2Z2[u]-linear codes
  • cyclic codes
  • generator matrix
  • duality
  • parity-check matrix
  • minimal spanning set

1. Introduction

In coding theory, the most important class of error-correcting codes is the family of linear codes, because the encoding and decoding procedures for a linear code are faster and simpler than those for arbitrary nonlinear codes. Many practically important linear codes have also an efficient decoding. Specifically, a linear code Cof length n is a vector subspace of Fqn, where Fqis a finite field with q elements. Among all the codes over finite fields, binary linear codes (linear codes over F2) have a very special and important place because of their easy implementations and applications. In the beginning, researchers were mainly studying on linear codes over fields, especially binary fields. However, in 1994, a remarkable paper written by Hammons et al. [1] brought a new direction to studies on coding theory. In this paper, they showed that some well-known nonlinear codes, the Nordstrom-Robinson code, Kerdock codes, and Delsarte-Goethals code, are actually binary images of some linear codes over the ring of integers modulo, 4, i.e., Z4. Such connections motivate the researchers to study on codes over different rings even over other structural algebras such as groups or modules. Even though the structure of binary linear codes and quaternary linear codes (codes over F4or Z4) have been studied in details for the last 50 years, recently, in 2010, a new class of error-correcting codes over the ring Z2α×Z4βcalled additive codes that generalizes the class of binary linear codes and the class of quaternary linear codes have been introduced by Borges et al. in [2]. A Z2Z4-additive code Cis defined as a subgroup of Z2α×Z4β, where αand βare positive integers and α+2β=n. Despite the fact that Z2Z4-additive codes are a new type of codes, they have shown to have some applications in fields such as the field of steganography. Another important ring of four elements which is not isomorphic to Z4 is the ring Z2+uZ2=01u1+u=R=Z2uwhere u2=0. Working with the ring Rhas some advantages compared to the ring Z4. For example, the Gray images of linear codes over Rare always binary linear codes which is not always the case for Z4. Further, since the finite field F2is a subring of the ring R, the factorization of polynomials over Ris the same with the factorization of polynomials over F2, so we do not need Hensel’s lift for factorization. Moreover, decoding algorithm of cyclic codes over Ris easier than that over Z4. In this chapter of the book, we introduce Z2Z2u-linear and Z2Z2u-cyclic codes. The original study about linear and cyclic codes over Z2Z2uwas done by Aydogdu et al. in [3, 4]. So, this chapter is a survey on Z2Z2u-linear and Z2Z2u-cyclic codes which were introduced in [3, 4].

2. Z2Z2[u]-linear codes

Let Z2=01be the finite field and R=Z2+uZ2=01u1+u, u2=0be the finite ring of four elements. Since Z2is a subring of R, we define the following set:

Z2R=c1c2c1Z2andc2R

This set is not well defined with respect to the usual multiplication by uR. So it is not an R-module. Hence the set Z2Rcannot be endowed with an algebraic structure directly. Therefore we introduce a new multiplication to make it well defined and enriched with an algebraic structure.

Let dR; then d can be expressed in the form d=r+uqwith r,qZ2. We define the following map:

η:RZ2ηd=r=d¯

as η0=0,η1=1,ηu=0andη1+u=1. It is easy to see that the mapping ηis a ring homomorphism. Now, using this map we define the following R-scalar multiplication on Z2R. For any element dR:

dc1c2=ηdc1dc2=d¯c1dc2

This new multiplication is well defined and also can be extended over Z2α×Rβas follows. Let dRand v=a0a1aα1b0b1bβ1Z2α×Rβ; then define

dv=ηda0ηda1ηdaα1db0db1dbβ1=d¯a0d¯a1d¯aα1db0db1dbβ1.

Lemma 2.1. Z2α×Rβis an R-module with respect to the multiplication defined above.

Definition 2.2. Let Cbe a non-empty subset of Z2α×Rβ. Cis called a Z2Z2u-linear code if it is an R-submodule of Z2α×Rβ.

Note that the ring Ris isomorphic to Z22as an additive group. Therefore, any Z2Z2u-linear code Cis isomorphic to a group of the form Z2k0+k2×Z22k1, for some k0,k1,k2Z+. Now let us consider the following sets:

CβF=abZ2α×Rβbis free overRβ

where if b=Rβ, then bis called free over Rβ:

C0=aubZ2α×Rβa0C\CβF
C1=aubZ2α×Rβa=0C\CβF

Now, denote the dimension of C0, C1, and CβFas k0, k2, and k1, respectively. Hence, if CZ2α×Rβis a Z2Z2u-linear code group isomorphic to Z2k0+k2×Z22k1, then we say Cis of type αβk0k1k2. We can consider any Z2Z2u-linear code Cas a binary code under the special Gray map.

Definition 2.3. Let a0a1aα1b0b1bβ1Z2α×Rβwith bi=pi+uqi. We define the Gray map as follows:

Ψ:Z2α×RβZ2nΨa0a1aα1p0+uq0p1+uq1pβ1+uqβ1=a0a1aα1q0q1qβ1p0+q0p1+q1pβ1+qβ1

where n=α+2β. The Gray map Ψis an isometry which transforms the Lee distance in Z2α×Rβto the Hamming distance in Z2n. The Hamming and the Lee distance between two codewords is the Hamming weight and the Lee weight of their differences, respectively. The Hamming weight of a codeword is defined as the number of its non-zero entries, and the Lee weights of the elements of Rare defined as wtL0=0,wtL1=1,wtLu=2,wtL1+u=1. It is worth mentioning that the Gray map Ψis linear, i.e., for a Z2Z2u-linear code C, we have ΨCas a binary linear code which is not the case for Z2Z4-additive codes in general. We can extend the definition of the Lee weight of a codeword in Rto the Lee weight of a codeword v=v1v2Z2α×Rβas follows:

wtv=wtHv1+wtLv2

where wtHv1is the Hamming weight of v1and wtLv2is the Lee weight of

v2. Further, the minimum distance of the Z2Z2u-linear code C, denoted by dC, is naturally defined as

dC=mindc1c2c1c2Csuch thatc1c2

where dc1c2=wtc1c2. If Cis a Z2Z2u-linear code of type αβk0k1k2, then Gray image ΨCis a binary linear code of length n=α+2βand size 2n. It is also called a Z2Z2u-linear code.

2.1 Generator matrices of Z2Z2u-linear codes

A generator matrix for a linear code Cis the matrix G with rows that are formed by a minimal spanning set of C. All linear combinations of the rows of the generator matrix G constitute the linear code C. We can produce an equivalent code to the Cby applying elementary row and column operations on the generator matrix G. For given two linear codes, if one can be obtained from the other by permutation of their coordinates or (if necessary) changing the coordinates by their unit multiples, then these codes are said to be permutation equivalent code or only equivalent code. Furthermore, the standard form of the matrix G is a special form which is obtained by applying elementary row operations to G. Having the standard form of the generator matrix is very useful that we can easily determine the type of the code and then calculate its size directly. Note that the generator matrices in the standard form of linear codes over a ring contain the minimum number of rows. The theorem below determines the standard form of the generator matrix of a Z2Z2u-linear code C.

Theorem 2.1.1. [3] Let Cbe a Z2Z2u-linear code of type αβk0k1k2. Then Cis a permutation equivalent to a Z2Z2u-linear code with the following generator matrix of the standard form:

Gs=Ik0A100uT0SIk1AB1+uB2000uIk2uDE1

where A,A1,B1,B2,T,and Dare matrices with all entries from Z2and Ik0,Ik1,and Ik2are identity matrices with given sizes. Further Chas 2k0+2k1+k2codewords.

Proof. It is well known that any linear code of length βover the ring R=Z2+uZ2has the generator matrix of the form Ik1A'B1'+uB2'0uIk2'uD'. Moreover, any binary linear code of length αcan be generated by the matrix Ik0'A1'. Since Cis a Z2Z2u-linear code of length α+β, then Ccan be generated by the following matrix:

Ik0'A1'S01S11S02S12αT01T02T03Ik1A'B1'+uB2'0uIk2'uD'β

with all binary entries. By applying the necessary row operations to the above matrix, we have the desired form.

Example 2.1.2. Let Cbe a Z2Z2u-linear code with the generator matrix 1011011+u11+u1+u.First, adding the second row to the first row, we have

100111u101+u.

Then multiplying the second row by u and adding it to first row, we have the following standard form of the generator matrix:

10011101u1+u=Ik00A1S0Ik1uTB1+uB2E2

Therefore,

  • Cis of type 32110.

  • Chas 21+21=8codewords:

C=000001010u01111+u11011,0111+u1,1101+u1+u000uu101u0.

Moreover, the Gray image ΨCof Cis a simplex code of length 7 with parameters [7, 3, 4] which is the dual of the well-known [7, 4, 3] Hamming code.

2.2 Duality on Z2Z2u-linear codes and parity-check matrices

In the literature, there is a very well-known concept for the duals of the codes over finite fields and rings. If Cis a linear code over Fqn, the dual code Cof Cin Fqnis the set of all codewords that are orthogonal to every codeword of C. A generator matrix for Cis called a parity-check matrix of C. In this part, we determine the standard form of the parity-check matrix of a Z2Z2u-linear code C. Let us begin with the definition of an inner product over Z2α×Rβ.

Definition 2.2.1 Let vand wbe the two elements in Z2α×Rβ. The inner product of vand wis defined by

vw=ui=1αvıwi+j=α+1α+βvjwjR.

Further, the dual code Cof a Z2Z2u-linear code Cis defined in the usual way with respect to this inner product as

C=wZ2α×Rβvw=0forallvC.

Hence, if Cis a Z2Z2u-linear code, then Cis also a Z2Z2u-linear code. It is worth mentioning that any two codewords of a Z2Z2u-linear code may be orthogonal to each other, but the binary parts of the codewords may not be orthogonal. For example, 111+uu,01uuZ22×R2are orthogonal to each other, whereas the binary or R-components are not orthogonal. Moreover, the Gray map Ψpreserves the orthogonality.

We give the standard form of the parity-check matrices of Z2Z2u-linear codes with the following theorem.

Theorem 2.2.2. [3] Let Cbe a Z2Z2u-linear code of type αβk0k1k2with the standard form generator matrix (1). Then the parity-check matrix of C(the generator matrix of the dual code C) is given by

Hs=A1tIαk0uSt00Tt0B1+uB2t+DtAtDtIβk1k200uAtuIk20.

Furthermore, C=2αk022βk1k22k2.

Proof. It can be easily checked that GsHst=0. Therefore every row of Hs is orthogonal to the rows of Gs. Further, since the generator matrices in the standard form of linear codes contain the minimum number of rows, Chas 2αk022βk1k22k2codewords. Hence, CC=2k022k12k22αk022βk1k22k2=2α+2β. So, the rows of the matrix Hsare not only orthogonal to C, but also they generate all dual space.

Example 2.2.3. Let Cbe a Z2Z2u-linear code of type 32110with the standard form of the generator matrix in (2). Then the parity-check matrix of Cis

A1tTtI310uStB1+uB2t+DtAt0I210=011100100uu1+u001.

Therefore, Cis of type 32210and has 2222120=16codewords. The Gray image ΨCis a well-known Hamming code with parameters 743.

Corollary 2.2.4. If Cis a Z2Z2u-linear code of type αβk0k1k2, then Cis of type αβαk0βk1k2k2.

3. Z2Z2[u]-linear cyclic codes

Cyclic codes form a very small but highly structured and important subset of the set of linear codes. In general, these codes are much easier to implement, and hence they have a very rich algebraic structure that allows them to be encoded and decoded in a relatively easier way. Since cyclic codes can be identified as ideals in a certain ring, they are also of considerable interest from an algebraic point of view. Cyclic codes over finite fields were first introduced by E. Prange in 1957 and 1959 with two Air Force Cambridge Research Laboratory reports. In this section we study the structure of Z2Z2[u]-linear cyclic codes for a positive odd integer β. We give the generator polynomials and the spanning sets for a Z2Z2[u]-linear cyclic code C.

Definition 3.1. An R-submodule Cof Z2α×Rβis called a Z2Z2[u]-linear cyclic code if for any codeword v=a0a1aα1b0b1bβ1C, its cyclic shift Tv=aα1a0aα2bβ1b0bβ2is also in C.

Lemma 3.2. If Cis a Z2Z2[u]-linear cyclic code, then the dual code Cis also a Z2Z2[u]-linear cyclic code.

Proof. Let Cbe a Z2Z2[u]-linear cyclic code and w=d0d1dα1e0e1eβ1C. We will show that TwC. Since wC, for v=a0a1aα1b0b1bβ1C, we have

vw=ua0d0+a1d1++aα1dα1+b0e0+b1e1++bβ1eβ1=0.

Now, let θ=lcmαβ. Since Cis cyclic, then Tθv=v, and Tθ1v=a1a2a0b1b2b0=zC. Therefore,

0=zw=ua1d0+a2d1++a0dα1+b1e0+b2e1++b0eβ1=ua0dα1+a1d0++aα1dα2+b0eβ1+b1e0++bβ1eβ2=vTw.

Hence, TwCand so Cis also cyclic.

Let CZ2α×Rβand v=a0a1aα1b0b1bβ1C. vCcan be identified with a module element consisting of two polynomials each from different rings in Rα,β=Z2x/xα1×Rx/xβ1such that

vx=a0+a1x++aα1xα1b0+b1x++bβ1xβ1=axbx.

This identification gives a one-to-one correspondence between elements in Z2α×Rβand elements in Rα,β.

Definition 3.3. Let dxRxand vxwxRa,β. We define the following scalar multiplication:

dxvxwx=dxvxmodudxwx

This multiplication is well defined, and moreover, Rα,βis a Rx-module with respect to this multiplication.

The codewords of Cmay be represented as polynomials in Rα,βby using the above identification. Thus, if CZ2α×Rβis a cyclic code, then the element v=a0a1aα1b0b1bβ1Ccan be viewed as

vx=a0+a1x++aα1xα1b0+b1x++bβ1xβ1Rα,β.

Further, the property Tv=aα1a0aα2bβ1b0bβ2Ctranslates to

xvx=aα1+a0x++aα2xα1bβ1+b0x++bβ2xβ1Rα,β.

Hence we give the following theorem.

Theorem 3.4. A code Cis a Z2Z2u-linear cyclic code if and only if Cis an Rx-submodule of Rα,β.

3.1 The generators and the spanning sets of Z2Z2u-linear cyclic codes

Let Cbe a Z2Z2u-linear code. We know that both Cand R[x]/⟨ − 1⟩ are Rx-modules. Then we define the following map:

Φ:CRx/xβ1Φf1xf2x=f2x.

It is clear that Φis a module homomorphism where the ImΦis an R[x]-submodule of R[x]/⟨ − 1⟩ and kerΦis a submodule of C. Since ΦCis an ideal of the ring R[x]/⟨ − 1⟩, we have

ΦC=gx+uaxwith axgxxβ1mod 2.

Further the kernel of Φis

kerΦ=fx0CfxZ2α×Rβ.

Now, define the set

I=fxZ2x/xα1fx0kerΦ.

It is clear that I is an ideal and hence a cyclic code in the ring Z2x/xα1. So, by the well-known results about the generators of binary cyclic codes, I is generated by f(x), i.e., I=fx.

Now, let mx0kerΦ. So, we have mxI=fx, and hence mx=kxfxfor some polynomial kxZ2x/xα1. Therefore mx0=kxfx0, and this implies that kerΦis a submodule of Cgenerated by one element of the form fx0with fxxα1mod 2. Then by the First Isomorphism Theorem, we have

C/kerΦgx+uax.

Let lxgx+uaxCsuch that Φlxgx+uax=gx+uax. This discussion shows that any Z2Z2u-linear cyclic code Ccan be generated as a R[x]-submodule of Rα,β by two elements of the form (f(x),0) and lxgx+uaxsuch that

d1xfx0+d2xlxgx+uax

where d1x,d2xRx. Since the polynomial d1xcan be restricted to a polynomial in Z2x, we can write

C=fx0lxgx+uax

with binary polynomials fxand lxwhere fxxα1mod 2and axgxxβ1mod 2.

Theorem 3.1.1. [4] Let Cbe a Z2Z2u-linear cyclic code in Rα,β. Then Ccan be identified uniquely as C=fx0lxgx+uaxwhere fxxα1mod 2, axgxxβ1mod 2, and lxis a binary polynomial satisfying deglx<degfxand fxxβ1axlxmodu.

Proof. We can easily see from the above discussion and Theorem 11 in [5] that C=fx0lxgx+uaxwith the polynomials fx,lx,gxand axare as stated in the theorem. So, we need to only show the uniqueness of the generator polynomials. Since fxand gx+uaxare cyclic codes over Z2and over R, respectively, this implies the uniqueness of the polynomials fx,gxand ax. Now suppose that deglx>degfxwith deglxdegfx=t. Let

D=fx0lx+xtfxgx+uax=fx0lxgx+uax+xtfx0.

Therefore DC. On the other hand,

lxgx+uax=lx+xtfxgx+uaxxtfx0.

So, CDand hence D=C.

Definition 3.1.2. Let Nbe an R-module. A linearly independent subset Pof Nthat spans Nis called a basis of N. If an R-module has a basis, then it is called a free R-module.

Note that for a Z2Z2u-linear cyclic code C=fx0lxgx+uax, if gx0, then Cis a free R-module. However, if gx=0and ax0, then it is not a free R-module. But we can still present Cwith the minimal spanning sets. The following theorem determines the minimal spanning sets for a Z2Z2u-linear cyclic code C.

Theorem 3.1.3. [4] Let C=fx0lxgx+uaxbe a Z2Z2u-linear cyclic code in Rα,βwith fx,lx,gx,and axin Theorem 3.1.1. Let

S1=i=0deghfx1xifx0,S2=i=0deghgx1xilxgx+uax,S3=i=0degbx1xihgxlxuhgxax

where fxhfx=xα1,gxhgx=xβ1and gx=axbx. Then S=S1S2S3forms a minimal spanning set for Cas an R-module. Furthermore, Chas 2deghfx4deghgx2degbxcodewords.

Proof. Please see the proof of the Theorem 4 in [4].

Example 3.1.4. Let C=fx0lxgx+uaxbe a Z2Z2u-linear cyclic code in Z2x/x71×Rx/x71with the following generator polynomials:

fx=x71,lx=1+x2+x3gx=1+x+x2+x3+x4+x5+x6,ax=1+x2+x3.

Therefore, we have gx=axbxbx=1+x+x3and gxhgx=x71hgx=1+x. Hence by using the minimal spanning sets in Theorem 3.1.3, we can write the generator matrix for the Z2Z2u-linear cyclic code Cas follows:

G=10110001+u11+u1+u1111110100uuu0u0001110100uuu0u0001110100uuu0u.

It is worth mentioning that the Gray image ΦCof Cis a linear binary code with the parameters [21, 5, 10], which are optimal. If the code Chas the best minimum distance compared to the existing bounds for fixed length and the size, then Cis called optimal or good parameter code.

Example 3.1.5. Let us consider the cyclic code C=fx0lxgx+uaxin Z2x/x71×Rx/x91with generators:

fx=1+x2+x3+x4,lx=1+x+x3,gx=1+x+x2+x3+x4+x5+x6+x7+x8,ax=1+x+x2.

Again by using the minimal spanning sets in the above theorem, we have the following generator matrix for C:

G=10111000000000000101110000000000001011100000000011010001+u1+u1+u1111111011100u00u0000001011100u00u0000001011100u00u0001001011000u00u0011001010000u00u0111001000000u00u.

The Gray image ΦCof Cis a [25, 11, 4] linear binary code. Moreover we can write the standard form of this generator matrix as

Hence Cis of type 79316and has 211=2048codewords.

4. Conclusion

In this chapter we introduced Z2Z2[u]-linear and Z2Z2[u]-cyclic codes. We determined the standard forms of the generator and parity-check matrices of Z2Z2[u]-linear codes. We further gave the generator polynomials and minimal spanning sets for Z2Z2[u]-linear cyclic codes. We also presented some illustrative examples of both Z2Z2[u]-linear codes and Z2Z2[u]-cyclic codes.

Acknowledgments

The author would like to thank professors Irfan Siap and Taher Abualrub for their valuable comments and suggestions to improve the quality of the chapter.

Download

chapter PDF

© 2019 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Ismail Aydogdu (October 23rd 2019). Z<sub>2</sub>Z<sub>2</sub>[<em>u</em>]-Linear and Z<sub>2</sub>Z<sub>2</sub>[<em>u</em>]-Cyclic Codes [Online First], IntechOpen, DOI: 10.5772/intechopen.86281. Available from:

chapter statistics

14total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us