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 2 n , the additive codes are of the form Z 2 α × Z 4 β with α + 2 β = n . In 2010, Borges et al. introduced Z 2 Z 4 -additive codes which they defined them as the subgroups of Z 2 α × Z 4 β . In this chapter we introduce Z 2 Z 2[u]-linear and Z 2 Z 2[u]-cyclic codes where Z 2 = 0 1 is the binary field and Z 2 u = 0 1 u 1 + u is the ring with four elements and u 2 = 0 . We give the standard forms of the generator and parity-check matrices of Z 2 Z 2[u]-linear codes. Further, we determine the generator polynomials for Z 2 Z 2 u -linear cyclic codes. We also present some examples of Z 2 Z 2[u]-linear and Z 2 Z 2[u]-cyclic codes.
- Z2Z2[u]-linear codes
- cyclic codes
- generator matrix
- parity-check matrix
- minimal spanning set
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 of length n is a vector subspace of , where is a finite field with q elements. Among all the codes over finite fields, binary linear codes (linear codes over ) 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.  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., 4. 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 or 4) have been studied in details for the last 50 years, recently, in 2010, a new class of error-correcting codes over the ring 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 . A 2 4-additive code is defined as a subgroup of , where and are positive integers and . Despite the fact that 2 4-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 4 is the ring where . Working with the ring has some advantages compared to the ring 4. For example, the Gray images of linear codes over are always binary linear codes which is not always the case for 4. Further, since the finite field is a subring of the ring , the factorization of polynomials over is the same with the factorization of polynomials over , so we do not need Hensel’s lift for factorization. Moreover, decoding algorithm of cyclic codes over is easier than that over 4. In this chapter of the book, we introduce -linear and -cyclic codes. The original study about linear and cyclic codes over was done by Aydogdu et al. in [3, 4]. So, this chapter is a survey on -linear and -cyclic codes which were introduced in [3, 4].
2. 2 2[u]-linear codes
Let be the finite field and , be the finite ring of four elements. Since is a subring of , we define the following set:
This set is not well defined with respect to the usual multiplication by . So it is not an -module. Hence the set cannot 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 ; then d can be expressed in the form with . We define the following map:
as . It is easy to see that the mapping is a ring homomorphism. Now, using this map we define the following -scalar multiplication on . For any element :
This new multiplication is well defined and also can be extended over as follows. Let and ; then define
Lemma 2.1. is an -module with respect to the multiplication defined above.
Definition 2.2. Let be a non-empty subset of . is called a -linear code if it is an -submodule of .
Note that the ring is isomorphic to as an additive group. Therefore, any -linear code is isomorphic to a group of the form , for some . Now let us consider the following sets:
where if , then is called free over β:
Now, denote the dimension of , , and as k 0, k 2, and k 1, respectively. Hence, if is a -linear code group isomorphic to , then we say is of type . We can consider any -linear code as a binary code under the special Gray map.
Definition 2.3. Let with . We define the Gray map as follows:
where . The Gray map is an isometry which transforms the Lee distance in to the Hamming distance in . 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 are defined as . It is worth mentioning that the Gray map is linear, i.e., for a -linear code , we have as a binary linear code which is not the case for -additive codes in general. We can extend the definition of the Lee weight of a codeword in to the Lee weight of a codeword as follows:
where is the Hamming weight of and is the Lee weight of . Further, the minimum distance of the -linear code , denoted by , is naturally defined as
where . If is a -linear code of type , then Gray image is a binary linear code of length and size . It is also called a -linear code.
2.1 Generator matrices of [u]-linear codes
A generator matrix for a linear code is the matrix G with rows that are formed by a minimal spanning set of . All linear combinations of the rows of the generator matrix G constitute the linear code . We can produce an equivalent code to the by 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 -linear code .
Theorem 2.1.1.  Let be a -linear code of type . Then is a permutation equivalent to a -linear code with the following generator matrix of the standard form:
where and are matrices with all entries from and and are identity matrices with given sizes. Further has codewords.
Proof. It is well known that any linear code of length over the ring has the generator matrix of the form . Moreover, any binary linear code of length can be generated by the matrix . Since is a -linear code of length , then can be generated by the following matrix:
with all binary entries. By applying the necessary row operations to the above matrix, we have the desired form.
Example 2.1.2. Let be a -linear code with the generator matrix First, adding the second row to the first row, we have
Then multiplying the second row by u and adding it to first row, we have the following standard form of the generator matrix:
is of type .
Moreover, the Gray image of is 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 [u]-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 is a linear code over , the dual code of in is the set of all codewords that are orthogonal to every codeword of . A generator matrix for is called a parity-check matrix of . In this part, we determine the standard form of the parity-check matrix of a -linear code . Let us begin with the definition of an inner product over .
Definition 2.2.1 Let and be the two elements in . The inner product of and is defined by
Further, the dual code of a -linear code is defined in the usual way with respect to this inner product as
Hence, if is a -linear code, then is also a -linear code. It is worth mentioning that any two codewords of a -linear code may be orthogonal to each other, but the binary parts of the codewords may not be orthogonal. For example, are orthogonal to each other, whereas the binary or -components are not orthogonal. Moreover, the Gray map preserves the orthogonality.
We give the standard form of the parity-check matrices of -linear codes with the following theorem.
Theorem 2.2.2.  Let be a -linear code of type with the standard form generator matrix (1). Then the parity-check matrix of (the generator matrix of the dual code ) is given by
Proof. It can be easily checked that . 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, has codewords. Hence, . So, the rows of the matrix are not only orthogonal to , but also they generate all dual space.
Example 2.2.3. Let be a -linear code of type with the standard form of the generator matrix in (2). Then the parity-check matrix of is
Therefore, is of type and has codewords. The Gray image is a well-known Hamming code with parameters .
Corollary 2.2.4. If is a -linear code of type , then is of type .
3. 2 2[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 2 2[u]-linear cyclic codes for a positive odd integer . We give the generator polynomials and the spanning sets for a 2 2[u]-linear cyclic code .
Definition 3.1. An -submodule of is called a 2 2[u]-linear cyclic code if for any codeword , its cyclic shift is also in .
Lemma 3.2. If is a 2 2[u]-linear cyclic code, then the dual code is also a 2 2[u]-linear cyclic code.
Proof. Let be a 2 2[u]-linear cyclic code and . We will show that . Since , for , we have
Now, let . Since is cyclic, then , and . Therefore,
Hence, and so is also cyclic.
Let and . can be identified with a module element consisting of two polynomials each from different rings in such that
This identification gives a one-to-one correspondence between elements in and elements in .
Definition 3.3. Let and . We define the following scalar multiplication:
This multiplication is well defined, and moreover, is a -module with respect to this multiplication.
The codewords of may be represented as polynomials in by using the above identification. Thus, if is a cyclic code, then the element can be viewed as
Further, the property translates to
Hence we give the following theorem.
Theorem 3.4. A code is a -linear cyclic code if and only if is an -submodule of .
3.1 The generators and the spanning sets of [u]-linear cyclic codes
Let be a -linear code. We know that both and [x]/〈xβ − 1〉 are -modules. Then we define the following map:
It is clear that is a module homomorphism where the is an [x]-submodule of [x]/〈xβ − 1〉 and is a submodule of . Since is an ideal of the ring [x]/〈xβ − 1〉, we have
Further the kernel of is
Now, define the set
It is clear that I is an ideal and hence a cyclic code in the ring . So, by the well-known results about the generators of binary cyclic codes, I is generated by f(x), i.e., .
Now, let . So, we have , and hence for some polynomial . Therefore , and this implies that is a submodule of generated by one element of the form with . Then by the First Isomorphism Theorem, we have
Let such that . This discussion shows that any -linear cyclic code can be generated as a [x]-submodule of α,β by two elements of the form (f(x),0) and such that
where . Since the polynomial can be restricted to a polynomial in , we can write
with binary polynomials and where and .
Theorem 3.1.1.  Let be a -linear cyclic code in . Then can be identified uniquely as where , , and is a binary polynomial satisfying and .
Proof. We can easily see from the above discussion and Theorem 11 in  that with the polynomials and are as stated in the theorem. So, we need to only show the uniqueness of the generator polynomials. Since and are cyclic codes over and over , respectively, this implies the uniqueness of the polynomials and . Now suppose that with . Let
Therefore . On the other hand,
So, and hence .
Definition 3.1.2. Let be an -module. A linearly independent subset of that spans is called a basis of . If an -module has a basis, then it is called a free -module.
Note that for a -linear cyclic code , if , then is a free -module. However, if and , then it is not a free -module. But we can still present with the minimal spanning sets. The following theorem determines the minimal spanning sets for a -linear cyclic code .
Theorem 3.1.3.  Let be a -linear cyclic code in with and in Theorem 3.1.1. Let
where and . Then forms a minimal spanning set for as an -module. Furthermore, has codewords.
Proof. Please see the proof of the Theorem 4 in .
Example 3.1.4. Let be a -linear cyclic code in with the following generator polynomials:
Therefore, we have and . Hence by using the minimal spanning sets in Theorem 3.1.3, we can write the generator matrix for the -linear cyclic code as follows:
It is worth mentioning that the Gray image of is a linear binary code with the parameters [21, 5, 10], which are optimal. If the code has the best minimum distance compared to the existing bounds for fixed length and the size, then is called optimal or good parameter code.
Example 3.1.5. Let us consider the cyclic code in with generators:
Again by using the minimal spanning sets in the above theorem, we have the following generator matrix for :
The Gray image of is a [25, 11, 4] linear binary code. Moreover we can write the standard form of this generator matrix as
Hence is of type and has codewords.
In this chapter we introduced 2 2[u]-linear and 2 2[u]-cyclic codes. We determined the standard forms of the generator and parity-check matrices of 2 2[u]-linear codes. We further gave the generator polynomials and minimal spanning sets for 2 2[u]-linear cyclic codes. We also presented some illustrative examples of both 2 2[u]-linear codes and 2 2[u]-cyclic codes.
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.