Printer Friendly

Skew Constacyclic Codes over Finite Fields and Finite Chain Rings.

1. Introduction

Reliable communication has been an unavoidable problem for a long time. Before 1948, communication was strictly an engineering discipline. However, there was very little scientific to develop a system to understand it. In 1948, Shannon's (1) landmark paper "A Mathematical Theory of Communication" [1] on the mathematical theory of communication, which showed that good codes exist, gave birth to information theory and coding theory. Coding theory is applicable in many situations that involve a common feature that a sender wants to send a message to a receiver through a noisy-channel. When the receiver has a message, it might contain some errors. Therefore, rather than sending it directly, the sender will encode it and send it to a decoder that estimates the message to give the receiver. Figure 1 describes a communication channel that transmits information from a source to a destination through a system.

Shannon's noisy-channel coding theorem ensures that our hopes of getting the correct messages to the users will be fulfilled a certain percentage of the time. Based on the characteristics of the communication channel, it is possible to build the right encoders and decoders so that this percentage, although not 100%, can be made as high as we desire. However, the proof of Shannon's noisy-channel coding theorem is probabilistic and only guarantees the existence of such good codes. No specific codes were constructed in the proof that provides the desired accuracy for a given channel. The main goal of coding theory is to establish good codes that fulfill the assertions of Shannon's noisy-channel coding theorem. During the last 50 years, while many good codes have been constructed, but only from 1993, with the introduction of turbo codes (2), the rediscoveries of LDPC codes (3), and the study of related codes and associated iterative decoding algorithms, researchers started to see codes that approach the expectation of Shannon's noisy-channel coding theorem in practice.

In real life, the noise is unavoidable, so we want to DETECT if there is an error and CORRECT if there is one. In 1950, a colleague of Shannon, Hamming (4), developed a ground-breaking idea in his famous paper "Error Detecting and Error Correcting Codes" [2]. The ground-breaking idea in Hamming's paper describes a single error correcting code. (5) A simple extension of this code is also discovered by Hamming in [2]. For more details, we refer the readers to [2].

The classes of cyclic and negacyclic codes in particular, and constacyclic codes in general, play a very significant role in the theory of error correcting codes. All [lambda]-constacyclic codes of length n are classified as ideals <f(x)> of F[x]/<[x.sup.n] - [lambda]), where f(x) is a divisor of [x.sup.n] - [lambda]. Due to their rich algebraic structure, constacyclic codes can be efficiently encoded using shift registers, which explains their preferred role in engineering.

In fact, cyclic codes are the most studied of all codes. Many well-known codes, such as BCH, Kerdock, Golay, Reed-Muller, Preparata, Justesen, and binary Hamming codes, are either cyclic codes or constructed from cyclic codes. Cyclic codes over finite fields were first studied in the late 1950s by Prange [4-7], while negacyclic codes over finite fields were initiated by Berlekamp in the late 1960s [8, 9]. The case when the code length n is divisible by the characteristic p of the field yields the so-called repeated-root codes, which were first studied since 1967 by Berman [10] and then in the 1970s and 1980s by several authors such as Massey et al. [11], Falkner et al. [12], Roth and Seroussi [13], Castagnoli et al. [14], and van Lint [15].

In 2007, Boucher et al. initiated [3] the study of skew cyclic codes. They generalized the notion of cyclic codes by using generator polynomials in noncommutative skew polynomial rings. In 2008 and 2011, Boucher and Ulmer [16, 17] continued to study skew [THETA]-[lambda]-constacyclic codes over Galois rings and codes as modules over skew polynomial rings.

In [16], Boucher et al. generalized the construction of linear codes via skew polynomial rings by using Galois rings instead of finite fields as coefficients. If finite fields are replaced by Galois rings, then the technical difficulty in studying from finite fields alphabet to Galois rings alphabet is that the skew polynomial rings are not Ore rings. They are neither left nor right Euclidean rings. However, left and right divisor can be defined for some suitable elements. Therefore, in [16], self-dual codes over GR(4 (2)) are constructed and used for three applications: self-dual Euclidean codes give self-dual [Z.sub.4] codes by projection on a trace orthogonal basis, self-dual Hermitian codes build 3-modular lattices, and self-dual Hermitian codes yield self-dual quasi-cyclic codes over [Z.sub.4] by the cubic construction. For more details, we refer the readers to [16] and the references therein. Boucher and Ulmer also studied the factorization of skew polynomial in skew polynomial rings [18]. These results allowed them to study the skew self-dual cyclic codes with length 2s.

The class of finite rings of the form [mathematical expression not reproducible] has been widely used as alphabets of certain constacyclic codes. For example, the structure of [F.sub.2] + u[F.sub.2] is interesting; it is lying between [F.sub.4] and [Z.sub.4] in the sense that it is additively analogous to [F.sub.4] and multiplicatively analogous to [Z.sub.4]. It has been studied by a lot of researchers (see, e.g., [19-24]). The classification of codes plays an important role in studying their structures, but, in general, it is very difficult. Only some codes of certain lengths over certain finite fields or finite chain rings are classified. All constacyclic codes of length 2s over the Galois extension rings of [F.sub.2] + u[F.sub.2] are classified and their detailed structures are also established in [25].

In 2012, Jitman et al. [26] introduced the notion of skew [THETA]-[lambda]-constacyclic (or skew constacyclic) codes over finite chain rings. They studied the structure of skew [THETA]-[lambda]-constacyclic, the Euclidean, and Hermitian dual codes of skew [THETA]-cyclic and negacyclic codes over finite chain rings. The goal of this survey is to study skew [THETA]-[lambda]-constacyclic codes over finite fields and finite chain rings.

This paper is arranged as follows. Basic concepts are reviewed in Section 2. After presenting preliminary concepts in Section 2, we study skew [THETA]-negacyclic, cyclic, and [THETA]-[lambda]-constacyclic codes over finite fields in Section 3. We also introduce some results for Euclidean and Hermitian self-dual codes over finite fields. In Section 4, general decoding procedure for decoding skew BCH codes with designed distance is provided. We also discuss an algorithm for decoding skew BCH codes. Finally, in Section 5, we consider the structure of skew [THETA]-[lambda]-constacyclic codes over finite chain rings. The Euclidean and Hermitian dual codes over finite chain rings are also exhibited in this section.

2. Preliminaries

2.1. Finite Fields and Their Automorphisms. In this subsection, we will not give entire properties of finite fields and their automorphisms; rather we will only introduce without proofs some properties of finite fields and their automorphisms that are needed in our consideration later.

Definition 1. Let F be a finite field with multiplicative identity 1. The characteristic of F is the least positive integer p such that p x 1 = 0. Such p always exists for a finite field and it is well known that the characteristic p must be a prime.

Theorem 2. A finite field F of characteristic p contains [p.sup.n] elements for some integer n [greater than or equal to] 1. For every element [beta] of a finite field F with [p.sup.m] elements, we have [mathematical expression not reproducible].

Definition 3. An element a in a finite field [mathematical expression not reproducible] is called a primitive element (or generator) of [mathematical expression not reproducible].

Example 4. [F.sub.5] has 2 primitive elements, namely, 2 and 3. [F.sub.4] has 2 primitive elements. In fact, expressing [F.sub.4] as [F.sub.2](a) = {0, 1, [alpha], [alpha] + 1}, where [[alpha].sup.2] + [alpha] + 1 = 0, then [alpha] and [alpha] + 1 are primitive elements of [F.sub.4].

Note that an automorphism [phi] of a field F is a bijection [phi] : F [right arrow] F such that [phi](a + b) = [phi](a) + [phi](b) and [phi](ab) = [phi](a)[phi}(b) for all a, b [member of] F. Suppose that [mathematical expression not reproducible] is a finite field of characteristic p > 0, and then the map [mathematical expression not reproducible] is defined by [[phi].sub.p](x) = [x.sup.p], the Frobenius automorphism of [mathematical expression not reproducible]. Since Fpm is a field of characteristic p, we have [[phi].sub.p](a + b) = [(a+b).sup.p] = [a.sup.p] + [b.sup.p] = [[phi].sub.p](a) + [[phi].sub.p](b). From [[phi].sub.p](ab) = [(ab).sup.p] = [a.sup.p]. [b.sup.p] = [[phi].sub.p](a)[[phi].sub.p](b), we can see that [[phi].sub.p] is a field homomorphism. Similarly, the map [mathematical expression not reproducible] defined by [mathematical expression not reproducible] is also a field homomorphism. The set of automorphisms of [mathematical expression not reproducible] forms a group under composition which we denote as [mathematical expression not reproducible]. Next, we give the following theorem characterizing this group.

Theorem 5 (see [27, Theorem 3.6.1]). (i) If [mathematical expression not reproducible] is a finite field, then [mathematical expression not reproducible] is a cyclic group of order m and is generated by Frobenius automorphism [[phi].sub.p].

(ii) The prime subfield of [mathematical expression not reproducible] is precisely the set of elements in [mathematical expression not reproducible] such that [[phi].sub.p]([alpha]) = [alpha].

(iii) The subfield [mathematical expression not reproducible] is precisely the set of elements in [mathematical expression not reproducible] such that [[phi].sub.p]([alpha]) = [alpha], where q = [p.sup.m].

Theorem 6 (see [27, Theorem 3.6.2]). If [mathematical expression not reproducible], then Aut([F.sub.2]/[F.sub.1]) is a cyclic group of order n/k and is generated by [mathematical expression not reproducible].

2.2. Codes, Cyclic Codes, Generator, and Parity-Check Matrices. Let [mathematical expression not reproducible] be a finite field. A linear (n, k)-code over [mathematical expression not reproducible] is a k-dimensional vector subspace C of the vector space

[mathematical expression not reproducible]. (1)

In this paper, all codes are assumed to be linear codes unless otherwise stated. We use polynomial representation of the code C, where we identify codewords ([a.sub.0], ..., [a.sub.n-1]) [member of] C with coefficient tuples of polynomials:

[mathematical expression not reproducible]. (2)

Those polynomials can also be seen as elements of a quotient ring [mathematical expression not reproducible], and any code C of length n over [mathematical expression not reproducible] corresponds to a subset of [mathematical expression not reproducible].

Example 7. The polynomial f(x) = [a.sub.0] + [a.sub.1]x + [a.sub.2][x.sup.2] + ... + [a.sub.n-1][x.sup.n-1] of degree at most n - 1 over finite field [mathematical expression not reproducible] may be regarded as the word v = [a.sub.0][a.sub.1][a.sub.2] ... [a.sub.n-1] of length n in [mathematical expression not reproducible]. If n = 6, then the polynomial 1 + x + [x.sup.2] + [x.sup.3] + [x.sup.5] may be regarded as the word c = 111101. Similarly, the polynomial 1 + [x.sup.3] + [x.sup.4] + [x.sup.5] may be regarded as the word v = 100111.

Definition 8. Let c be a word of length n, and the cyclic shift [tau](c) the word of length n:

[tau]([c.sub.0], [c.sub.1], ... [c.sub.n-1]) = ([c.sub.n-1], [c.sub.0], ..., [c.sub.n-2]). (3)

A code C is said to be cyclic if [tau](c) [member of] C, for all c [member of] C.

Example 9. Let C = {000, 111, 121, 222, 012, 120, 201, 021, 102, 210} be a linear code over [Z.sub.3]. It is easy to see that [tau](c) [member of] C, [for all] c [member of] C. This implies that C is a linear cyclic code over [Z.sub.3].

Let [C.sub.1] = {021, 012, 000, 112, 121, 100, 212, 221, 200} be a linear code over [Z.sub.3]. Since [tau](112) = 211 [not member of] [C.sub.1], we can conclude that [C.sub.1] is not cyclic code.

Definition 10. A code C is said to be a [lambda[-constacyclic code of length n if it is closed under the [lambda]-constacyclic shift [mathematical expression not reproducible] defined by

[[tau].sub.[lambda]] ([c.sub.0], [c.sub.1], ..., [c.sub.n-1]) = ([lambda][c.sub.n-1], [c.sub.0], ..., [c.sub.n-2]). (4)

In particular, when [lambda] = 1 or [lambda] = -1, such codes are called cyclic and negacyclic codes, respectively.

We now give some properties of cyclic code. The following results are well known (cf. [27]).

Theorem 11 (see [27, Theorem 4.2.1]). Let C be a nonzero cyclic code in [mathematical expression not reproducible]. There exists a polynomial g(x) [member of] C with the following properties:

(i) g(x) is the unique monic polynomial of minimum degree in C, and it is called the generating polynomial for C.

(ii) C = <g(x)>.

(iii) The generating polynomial g(x) divides [x.sup.n] - 1.

(iv) If deg g(x) = r, then C has dimension n - r and {g(x), xg(x), ..., [x.sup.n-r-1]g(x)} is a basis for C.

(v) Every element of C is uniquely expressible as a product f(x)g(x), where f(x) = 0 or deg f(x) < n - r, that is, C = <g(x)) = {f(x)g(x) | deg f(x) < n - r}.

(vi) If g(x) = [g.sub.0] + [g.sub.1]x + ... + [g.sub.r][x.sup.r], then [g.sub.0] [not equal to] 0 and C has the following generator matrix:

[mathematical expression not reproducible]. (5)

From this theorem, we can see that C is a nonzero cyclic code in [mathematical expression not reproducible] and g(x) is the monic polynomial of minimum degree in C if and only if C = <g(x)>, and [x.sup.n] - 1 is divisible by g(x).

Let C be a cyclic code in [mathematical expression not reproducible] with generator polynomial g(x), such that deg g(x) = r. Let h(x) = ([x.sup.n] - 1)/g(x) = [[summation].sup.n-r.sub.i=0] [h.sub.i][x.sup.i]. Then a parity-check matrix for C is given by

[mathematical expression not reproducible]. (6)

Example 12. Let C be a cyclic code of length n = 9 over the binary field [F.sub.2]. Put g(x) = [x.sup.6] + [x.sup.3] + 1. Then we have h(x) = [x.sup.3] - 1. We can see that C has dimension 3 and generating matrix is given by

[mathematical expression not reproducible]. (7)

Hence, a parity-check matrix for C is given by

[mathematical expression not reproducible]. (8)

Definition 13. (i) The Hamming distance [d.sub.H](x, y) between two vectors [mathematical expression not reproducible] is defined to be the number of coordinates in which x and y differ.

(ii) The Hamming weight [w.sub.H](x) of a vector [mathematical expression not reproducible] is the number of nonzero coordinates in x.

(iii) For a code C containing at least two words, the minimum distance of a code C, denoted by d(C), is

d (C) = min {d, (x, y), (x, y [member of] C, x [not equal to] y}. (9)

It is easy to see that the definition of distance satisfies nonnegativity, symmetry, and the triangle inequality, so our code C is living in a metric space.

Example 14. Let C = {00000, 00111, 11111} be a binary code. Then we have

[d.sub.H] (00000, 00111) = 3;

[w.sub.H] (00111) = 3. (10)

We can see that

d(00000, 00111) = 3;

d(00111, 11111) = 2;

d(00000, 11111) = 5. (11)

This shows that d(C) = 2.

The following theorem gives a relationship between minimum distance d and the minimum weight of the nonzero codewords of a linear code C.

Theorem 15 (see [27, Theorem 1.4.2]). If x, y [member of] [mathematical expression not reproducible], then d(x, y) = wt(x, y). If C is a linear code, the minimum distance d is the same as the minimum weight of the nonzero codewords of C.

2.3. The Skew Polynomial Ring [mathematical expression not reproducible]. Now let [THETA] be an automorphism of [mathematical expression not reproducible]. We consider the set [mathematical expression not reproducible] of formal polynomials where coefficients are written on the left of the variable x. The set [mathematical expression not reproducible] forms a ring under the usual addition of polynomials and the multiplication is defined by the following basic rule: xa = [THETA](a)x. The multiplication is extended to all elements in [mathematical expression not reproducible] by associativity and distributivity. The ring [mathematical expression not reproducible] is called a skew polynomial ring over [mathematical expression not reproducible], and each element in [mathematical expression not reproducible] is called a skew polynomial. It is easy to see that the ring [mathematical expression not reproducible] is noncommutative unless [THETA] is the identity automorphism on [mathematical expression not reproducible] with [a.sub.n] = 0, then we say that f(x) has degree n, denoted by deg(f(x)). The following facts are straightforward for the skew polynomial ring [mathematical expression not reproducible]: (i) It has no nonzero zero-divisors,

(ii) the units of [mathematical expression not reproducible] are the units of [mathematical expression not reproducible],

(iii) deg(f + g) [less than or equal to] max{deg(f), deg(g)},

(iv) deg(f x g) = deg(f) + deg(g).

Recall that a left (right) ideal I of a ring R is called a left (right) principal ideal if there exists an element g [member of] I such that I = <g>, where = {r x j(g x r): r [member of] R}. The element g is called a generator of I and I is said to be generated by A ring R is called a left (right) principal ideal ring if every left (right) ideal of R is principal. The skew polynomial ring [mathematical expression not reproducible] is left and right Euclidean ring whose left and right ideals are principal. For [mathematical expression not reproducible] which are nonzero, there exists unique polynomial [mathematical expression not reproducible] such that f(x) = h(x)g(x) + r(x). If r(x) = 0, then g(x) is a right divisor of [mathematical expression not reproducible]. The definition of left divisor in [mathematical expression not reproducible] is similar.

The centre [mathematical expression not reproducible] of the skew polynomial ring [mathematical expression not reproducible] is the set of all elements that commute with all other elements of [mathematical expression not reproducible]. An element [mathematical expression not reproducible] is called a central element. An automorphism [THETA] [member of] Aut[mathematical expression not reproducible] is said to fix an element a [mathematical expression not reproducible]. We denote [mathematical expression not reproducible] the subfield of elements of [mathematical expression not reproducible] which are fixed by [THETA]. Then the ring [mathematical expression not reproducible] is a commutative subring of [mathematical expression not reproducible]. A polynomial [mathematical expression not reproducible] is central element if and only if / is both in [mathematical expression not reproducible], where [mathematical expression not reproducible]. In other words, a polynomial[mathematical expression not reproducible] is central element (i.e., commutes with all elements of [mathematical expression not reproducible] if and only if [mathematical expression not reproducible], where is the order of [THETA] [28, Theorem II.12].

3. Structure and Duals of Skew Constacyclic Codes over Finite Fields

In this section, we study skew [THETA]-[lambda]-constacyclic codes over finite fields. We extend the work of Boucher et al. (in 2007) [3] on skew cyclic codes. For more details, we refer the readers to [3] and the references therein. We first introduce the definition of skew [THETA]-[lambda]-constacyclic codes over finite fields.

Definition 16. Given an automorphism [mathematical expression not reproducible] and a unit A in [mathematical expression not reproducible], a code C is said to be skew [THETA]-[lambda]-constacyclic of length n if it is closed under the skew [THETA]-[lambda]-constacyclic shift [mathematical expression not reproducible] defined by

[[tau].sub.[THETA],[lambda]]([c.sub.0], [c.sub.1], ..., [c.sub.n-1]) = ([THETA] ([lambda][c.sub.n-1]), [THETA]([c.sub.0]), ..., [THETA]([c.sub.n-2])). (12)

In particular, when [lambda} = 1 or [lambda] = -1, such codes are called skew [THETA]-cyclic and skew [THETA]-negacyclic codes, respectively. When [THETA] is the identity automorphism, they become classical constacyclic cyclic, cyclic, and negacyclic codes. A right factor of degree n - k of [x.sup.n] - [lambda] generates [n, k] linear code. While the ring [mathematical expression not reproducible] is a commutative ring, so every ideal in [mathematical expression not reproducible] is two-sided ideal, the skew polynomial ring [mathematical expression not reproducible] is noncommutative. Therefore, we need to have conditions of [THETA] and [lambda] to ensure that <[x.sup.n] - [lambda]) is a two-sided ideal of [mathematical expression not reproducible]. If n is divisible by the order of [THETA] and [lambda] is fixed by [THETA], then <[x.sup.n] - [lambda]) is a two-sided ideal of [mathematical expression not reproducible]. Indeed, for all [mathematical expression not reproducible], we can see that

[mathematical expression not reproducible]. (13)

Since n is divisible by the order of [THETA] we have [[THETA].sup.n]([h.sub.i]) = [h.sub.i], [for all]i = {1, ..., t}. If [lambda} is fixed by [THETA], then we have ([x.sup.n] - [lambda])([[summation].sup.t.sub.i=0] [h.sub.i][x.sup.i])= ([[summation].sup.t.sub.i=0] [h.sub.i][x.sup.i])([x.sup.n] - [lambda]]), proving that [x.sup.n] - [lambda] is in Z([mathematical expression not reproducible]). This implies that <[x.sup.n] - [lambda]) is a two-sided ideal of [mathematical expression not reproducible], which makes the quotient ring [mathematical expression not reproducible] well defined. If [THETA] is not the identity, then [mathematical expression not reproducible] is in general not a unique factorization ring. In this case, there are typically many more right factors than in the commutative case, producing many [THETA]-[lambda]-constacyclic codes.

Example 17. Let [alpha] be a generator of the multiplicative group of [F.sub.4]; that is, [alpha] is a zero of [z.sup.2] + z + 1 [member of] [F.sub.2] [z]. Let [THETA] be the automorphism a [??][a.sup.2] of [F.sub.4]. We consider the polynomial [x.sup.6] + [alpha][x.sup.3} [member of] [F.sub.4]. We have

[x.sup.6] +[alpha][x.sup.3] = ([x.sup.4] + [alpha]x)[x.sup.2] = ([x.sup.4] + [alpha][x.sup.3])([x.sup.2] + [alpha]x + 1) = ([x.sup.4] + [alpha][x.sup.3] + [x.sup.2])([x.sup.2] + [alpha]x).

This shows that the ring [F.sub.4] [x; [THETA]] is not a unique factorization ring.

Lemma 1 in [3] can be extended as follows.

Lemma 18 (extending [3, Lemma 1]). Let [THETA] be an automorphism of [mathematical expression not reproducible] integer divisible by the order of [THETA], and [lambda] a unit in [mathematical expression not reproducible] which is fixed by [THETA]. The ring [mathematical expression not reproducible] is a principal left ideal ring, in which the left ideals are generated by g(x), where g(x) is a right divisor of [x.sup.n] - [lambda] in [mathematical expression not reproducible].

Consider a codeword c(x) = [c.sub.0] + [c.sub.1]x+ ... + [c.sub.n-1][x.sup.n-1]. Then

[mathematical expression not reproducible]. (15)

Thus, xc(x) is corresponding to a [THETA]-[lambda]-constacyclic shift of c(x), proving that the code C is a skew [THETA]-[lambda]-constacyclic code if and only if C is a left ideal [mathematical expression not reproducible], where g(x) is a right divisor of [x.sup.n] - [lambda]. We summarize this discussion by the following theorem, which is an extension of [3, Theorem 1].

Theorem 19 (extending [3, Theorem 1]). Let [THETA] be an automorphism of [mathematical expression not reproducible], n an integer divisible by the order of [THETA], and [lambda] a unit in [mathematical expression not reproducible] which is fixed by [THETA]. Then the code C is a skew [THETA]-[lambda]-constacyclic code if and only if C is a left ideal [mathematical expression not reproducible], where g(x) is a right divisor of [x.sup.n] - [lambda].

Given a monic right divisor of degree n - k of [x.sup.n] - [lambda] : g(x) = [[summation].sup.n-k-1.sub.i=0] [g.sub.i](x) + [x.sup.n-k], then a generator matrix of the [THETA]-[lambda]-constacyclic code C generated by g(x) is given by

[mathematical expression not reproducible]. (16)

Lemma 20 (see [29, Lemma 17]). Let [THETA] be an automorphism of [mathematical expression not reproducible], n an integer divisible by the order of [THETA], and [lambda] a unit in [mathematical expression not reproducible] which is fixed by [THETA]. Let C be the [THETA]-[lambda]-constacyclic code generated by amonic right divisor g(x) of <[x.sup.n] - [lambda] and h(x) := ([x.sup.n] - [lambda])/g(x). If h = [h.sub.0] + [h.sub.1]x + ... + [x.sup.n-r], then the following matrix

mathematical expression not reproducible] (17)

is a parity-check matrix for C.

Since [THETA](1) = 1 for any [mathematical expression not reproducible], we have [THETA](-1) = -1. This shows that [mathematical expression not reproducible] is fixed by [THETA]. The following two corollaries are direct consequences of Theorem 19.

Corollary 21. Let [THETA] be an automorphism of [mathematical expression not reproducible] and n an integer divisible by the order of [THETA]. Then the code C is a skew [THETA]-negacyclic code if and only if C is a left ideal [mathematical expression not reproducible], where g(x) is a right divisor of [x.sup.n] + 1.

Corollary 22 (see [3, Lemma 1]). Let [THETA] be an automorphism of [mathematical expression not reproducible] and n an integer divisible by the order of [THETA]. Then the code C is a skew [THETA]-cyclic code if and only if C is a left ideal [mathematical expression not reproducible], where g(x) is a right divisor of [x.sup.n] - 1.

We give an example to illustrate these results.

Example 23. Let a be a generator of the multiplicative group of [F.sub.4]; that is, a is a zero of [z.sup.2] + z + 1 [member of] [F.sub.2][z]. Let [THETA] be the automorphism a [??] [a.sup.2] of [F.sub.4]. To list all [4,1] skew [THETA]-cyclic codes over [F.sub.4], we find all monic degree 1 right factors of [x.sup.4] -1 [member of] [F.sub.4] [x; [THETA]]. They are

[f.sub.1] = x + 1

[f.sub.2] = x + [alpha],

[f.sub.3] = x + [[alpha].sup.2]. (18)

Similarly, to list all [4, 2] skew [THETA]-cyclic codes over [F.sub.4], we find all monic degree 2 right factors of [x.sup.4] - 1 [member of] [F.sub.4][x; [THETA]]. They are

[mathematical expression not reproducible]. (19)

Let g be a right divisor of [x.sup.n] - 1 of degree r. Then the skew [THETA]-cyclic code is [n, n - r] linear code with generator matrix

[mathematical expression not reproducible]. (20)

A right factor of degree n - k of [x.sup.n] - 1 generates a linear code with parameters (n, k). If [THETA] is not the identity, then the skew polynomial ring F[mathematical expression not reproducible] is in general not a unique factorization. In this case, we have more right factors than in the commutative case. For small values of n, all right skew factors of [x.sup.n] - 1 can be found by a computational algebra system such as MAGMA (cf. [30]). Minimum distance of a code can be also calculated by using the MAGMA procedures. However, these procedures must be spent a long time for larger codes to check them. Therefore, the process will only find the smaller codes. The code parameters and the number of codes are introduced with these parameters (n, k, [d.sub.min]) because many different codes with the same minimum distance can be found. A generating polynomial for one code respected the class of parameters (n, k, [d.sub.min]) is also exhibited. Table 1, computed by Bosma et al. [30], provides parameters and generating polynomials of skew [THETA]-cyclic codes over [F.sub.4], where [THETA] is the Frobenius automorphism and a is a generator of the multiplicative group of [F.sub.4].

Given n-tuples x = ([x.sub.0], [x.sub.1], ..., [x.sub.n-1]) and [mathematical expression not reproducible], their inner product or dot product is defined in the usual way:

x [omicron] y = [x.sub.0][y.sub.0] + [x.sub.1][y.sub.1] + ... + [x.sub.n-1][y.sub.n-1], (21)

evaluated in [mathematical expression not reproducible]. Two codewords x, y are called orthogonal if x [omicron] y = 0. For a linear code C over [mathematical expression not reproducible], its dual code [C.sup.[perpendicular to]] is the set of n-tuples over [mathematical expression not reproducible] that are orthogonal to all codewords of C; that is,

[c.sup.[perpendicular to]] = {x| x [omicron] y = 0, [for all]y [member of] C}. (22)

A code C is called self-orthogonal if C [subset] [C.sup.[perpendicular to]], and it is called self-dual if C = [C.sup.[perpendicular to]]. The following result is well known (cf. [29]).

Lemma 24 (see [29, Corollary 18]). Let [THETA] be an automorphism of [mathematical expression not reproducible], n an integer divisible by the order of [THETA], and [lambda] a unit in [mathematical expression not reproducible] which is fixed by [THETA]. Let g(x) = [[summation].sup.r-1].sub.i=0] [g.sub.i][x.sup.i] + [x.sup.r] and h(x) = [[summation].sup.n-r-1.sub.i=0] [h.sub.i][x.sup.i]+ [x.sup.n-r] such that h(x)g(x) = [x.sup.n] - 1. The dual of the skew [THETA]-cyclic code generated by g(x) in [mathematical expression not reproducible] is the skew [THETA]-cyclic code generated by

[g.sup.[perpendicular to]] = 1 + [THETA]([h.sub.n-r-1]) x + ... + [[THETA].sup.n-r]([h.sub.0][x.sup.n-r]. (23)

We give an example to illustrate how we use Lemma 24 to determine Euclidean self-dual [THETA]-cyclic codes.

Example 25. Let [alpha] be a generator of the multiplicative group of [F.sub.4]; that is, [alpha] is a zero of [z.sup.2] + z + 1 [member of] [F.sub.2][z]. Let [THETA] be the automorphism a [??] [a.sup.2] of [F.sub.4]. We find all Euclidean self-dual [THETA]-cyclic codes over [F.sub.4] in [F.sub.4][x; [THETA]]/([x.sup.4] - 1). From Example 23, we can list all monic degree 2 right factors of [x.sup.4] - 1 [member of] [F.sub.4] [x; [THETA]]. Put [h.sub.i] (i = {1, ..., 7}) to be all monic degree 2 right factors such that [h.sub.i] x [g.sub.i] = [x.sup.4] - 1, [for all]i [member of]{1, ..., 7}. Then we have

[mathematical expression not reproducible]. (24)

Applying Lemma 24, we have

[mathematical expression not reproducible], (25)

where the dual of the skew [THETA]-cyclic code generated by [g.sub.i](x) in [F.sub.4][x; [THETA]]/([x.sup.n] - 1) is the [THETA]-cyclic code generated by [g.sup.[perpendicular to]]. Suppose that [C.sub.i], the skew [THETA]-cyclic code generated by [g.sub.i](x) in [F.sub.4][x; [THETA]]/<[x.sup.n] - 1), is an Euclidean self-dual [THETA]-cyclic code. Then we have C = [C.sup.[perpendicular to]]. This implies that [g.sup.[perpendicular to]] is a constant multiple of [g.sub.i]. From this, the skew [THETA]-cyclic codes generated by [g.sub.1] (x), [g.sub.2](x), [g.sub.3](x) are Euclidean self-dual [THETA]-cyclic codes.

We now turn our attention to Euclidean self-dual [THETA]-cyclic codes over [F.sub.4] (cf. [29]). Suppose that [THETA] is the Frobenius automorphism and a is a generator of [F.sub.4]. It is easy to see that n must be an even number. In fact, by Lemma 24, if n is odd, then there are no Euclidean self-dual codes. Therefore, n = 2r for some r [member of] [Z.sup.+]. Let C be a self-dual code. Applying Lemma 24, the coefficients of the generating polynomial [g.sup.[perpendicular to]] of [C.sup.[perpendicular to]] is expressed. Since C = [C.sup.[perpendicular to]], and g must differ by a constant multiple and deg(g) = deg([g.sup.[perpendicular to]]). Now assume that g = [[summation].sup.r-1.sub.i=0] [g.sub.i][x.sup.i] + [x.sup.r] with [g.sub.0] [not equal to] 0 is the generator polynomial of the self-dual [THETA]-cyclic code C. Assume that h = [x.sup.r] + [[summation].sup.r-1.sub.i=0] such that gh = [x.sup.n] - 1. From Lemma 24, the code [C.sup.[perpendicular to]] is generated by [g.sup.[perpendicular to]] = 1 + [[THETA].sup.r]([h.sub.0])g. Since [g.sup.[perpendicular to]] is a constant multiple of g, [g.sup.[perpendicular to]] = [[THETA].sup.r]([h.sub.0])g. This implies that if the coefficients of both polynomials g and [g.sup.[perpendicular to]] are compared, then system (26) is built as follows:

1 = [[THETA].sup.r]([h.sub.0])[g.sub.0],

[[THETA].sup.i]([h.sub.r-i]) = [[THETA].sup.r]([h.sub.0])[g.sub.i], i = 0, 1, ..., r - 1. (26)

Since [[THETA].sup.2] ([alpha]) = [alpha], it is easy to see that [THETA] = [[THETA].sup.-1]. By assumption, [g.sub.0] [not equal to] 0. This implies that [g.sup.-1.sub.0] = [g.sup.2.sub.0]. Hence, system (26) becomes

[h.sub.0] = [[THETA].sup.r]([g.sup.2.sub.0]), ([h.sub.r-i) = [[THETA].sup.i]([g.sup.2.sub.0] x [g.sub.i]), i = 0, 1, ..., r - 1. (27)

System (27) allows expressing the coefficients of h as follows:

h = [[THETA].sup.2]([g.sup.2.sub.0]) + [r.summation over (i=1)][[THETA].sup.r-i]([G.sub.r-i])[x.sup.i]. (28)

From [mathematical expression not reproducible], (28) becomes

[mathematical expression not reproducible]. (29)

where powers of [g.sub.i] are of degree less than 4. By using the rule [mathematical expression not reproducible] and expanding the skew product ([x.sup.n] - 1) - (h x g) = 0, (2r + 1) polynomial equations in the coefficients [g.sub.i] of degree less than 4 in each variable can be determined. From [g.sub.i] [member of] [F.sub.4], [g.sup.4.sub.i] - [g.sub.i] = 0 for any i = 1, ..., r. Adding r equations - [g.sup.4.sub.i] - [g.sub.i] = 0 to 2r + 1 polynomial equations in r variables of degree less than 4 to have a system, then the solutions of this system can be found by using Groebner bases in MAGMA system because the solution set must be finite. This shows that all polynomials g corresponding to a solution will be listed and hence the linear code which it generates and its minimum Hamming distance can be computed. Then all Euclidean self-dual [THETA]-cyclic codes of length n [less than or equal to] 40 in [F.sub.4][x; [THETA]] will be exhibited. In [29], Boucher and Ulmer gave the table of Euclidean self-dual codes over [F.sub.4] and n [less than or equal to] 40. We refer the readers to [29] for more details.

Recall that Hermitian inner product is denoted and calculated by [<u, v).sub.H] = [[summation].sup.n-1.sub.i=0] [u.sub.i][THETA]([v.sub.i]), for all u = ([u.sub.0], ..., [u.sub.n-1]) and v = ([v.sub.0], ..., [v.sub.n-1]) in [mathematical expression not reproducible]. Then we give the definition of the Hermitian dual code of a code C as follows:

[mathematical expression not reproducible]. (30)

If [mathematical expression not reproducible], then C is said to be a Hermitian self-dual code. It is easy to check that if n is odd, then there is no Hermitian self-dual of [THETA]-cyclic codes. Therefore, n must be an even number. Suppose that the order m of [THETA] divides n = 2r. Let g = [[summation].sup.r.sub.j=0][g.sub.j][x.sub.j] and h = [[summation].sup.r.sub.i=0] [h.sub.i][x.sup.i] be elements of [mathematical expression not reproducible] such that h x g = [x.sup.2r] - 1. The Hermitian dual of a [THETA]-cyclic code generated by g in [mathematical expression not reproducible] is again [THETA]-cyclic code and is generated by [g.sup.H] = [THETA]([h.sub.r]) + [[THETA].sup.2]([h.sub.r-1])x + ... + [[THETA].sup.r+1]([h.sub.0])[x.sup.r] [29, Lemma 21]. Similar to the case of Euclidean self-dual codes, all the Hermitian self-dual [THETA]-cyclic codes of length n [less than or equal to] 40 in [F.sub.4] [x; [THETA]] can be found. The polynomial h of Hermitian self-dual code in [F.sub.4][x; [THETA]] can be expressed as follows:

h = [x.sup.r] + [r - 1.summation over (i=1)]([[THETA].sup.r-i+1]([g.sup.2.sub.0])[[THETA].sup.r-i+1]([g.sub.r-i)[x.sup.i]) + [[THETA].sup.r+1]([g.sup.2.sub.0]). (31)

In this case, the coefficient of (31) is shifted by [[THETA].sup.m-1] = [THETA]. Expanding the skew product [x.sup.2r] - 1 - h x g = 0 which gives again a polynomial system of equations, the solutions of this system can be also computed by using Groebner bases in MAGMA because the solution set must be finite. Similar to the case of Euclidean self-dual codes, in [29], Boucher and Ulmer also gave the table of Hermitian self-dual codes over [F.sub.4] and n [less than or equal to] 40. For more details we refer the readers to [29].

4. Decoding Skew [THETA]-Cyclic Codes over Finite Fields

In coding theory, BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem and independently in 1960 by Raj Bose and D. K. Ray-Chanahuri. General decoding procedure for decoding BCH codes with designed distance is introduced in [31]. In this section, we first give the algorithm for decoding with cyclic codes in [mathematical expression not reproducible]. After that, we will modify the algorithm for decoding skew BCH codes.

Let C be [n, k, d] cyclic code over [mathematical expression not reproducible] with generator polynomial g(x) of degree n - k. Suppose that c(x) [member of] C is transmitted and = y(x) + c(x) + e(x) is received, where e(x) = [e.sub.0] + [e.sub.1]x + ... + [e.sub.n-1] [x.sup.n-1] is the error vector with wt(e(x)) [less than or equal to] t and t = (d - 1)/2. Let [R.sub.g(x)] be the unique remainder when h(x) is divided by g(x) according to the Division Algorithm; that is, [R.sub.g(x)](h(x)) = r(x), where h(x) = g(x)/(x) + r(x), with r(x) = 0 or deg r(x) < n - k. Then the function [R.sub.g(x)] satisfies the following properties.

Theorem 26 (see [27, Theorem 4.6.1]). With the preceding notation the following statements hold:

(i) [mathematical expression not reproducible],

(ii) [R.sub.g(x)](h(x) + a(x)([x.sup.n] - 1)) = [R.sub.g(x)](h(x)),

(iii) [R.sub.g(x)(h(x)) = 0 if and only if h(x) (mod([x.sup.n] - 1)) [member of] C,

(iv) If c(x) [member of] C, then [R.sub.g(x)](c(x) + e(x)) = [R.sub.g(x)](e(x)),

(v) If [R.sub.g(x)](e(x)) = [R.sub.g(x)](e'(x)), where e(x) and e'(x) each have weight at most t, then e(x) = e'(x),

(vi) [R.sub.g(x)](h(x)) = h(x) if deg h(x) < n - k.

Theorem 27 (see [27, Theorem 4.6.2]). Let g(x) be a monic divisor of [x.sup.n] - 1 of degree n - k. If [R.sub.g(x)](h(x)) = s(x), then [R.sub.g(x)](xh(x)(mod([x.sup.n] - 1)) = [R.sub.g(x)](xs(x)) = xs(x) g(x)[s.sub.n-k-1], where [s.sub.n-k-1] is the coefficient of [x.sup.n-k-1] in s(x).

Define the syndrome polynomial S(h(x)) of any h(x) to be

S(h(x)) = [R.sub.g(x)] ([x.sup.n-k]h(x)). (32)

We now describe the first version of the Meggitt Decoding Algorithm and we provide an example to illustrate each step.

Step 1. Find the syndrome polynomial S(e(x)) of error patterns e(x) = [[summation].sup.n-1.sub.i=0] such that wt(e(x)) [less than or equal to] t and [e.sub.n-1] [not equal to] 0.

Example 28 (see [27, Example 4.6.3]). Let C be the [15, 7, 5] binary cyclic code with a generating polynomial g(x) = 1 + [x.sup.4] + [x.sup.6] + [x.sup.7] + [x.sup.8] = (x - [xi])(x - [x.sup.2])(x - [[xi].sup.3])(x - [[xi].sup.4])(x - [[xi].sup.6])(x - [[xi].sup.8])([[xi].sup.9])(x - [[xi].sup.12]), where [xi], is a 15th root of unity in [F.sub.16]. Then the syndrome polynomial of e(x) is S(e(x)) = [R.sub.g(x)]([x.sup.8]e(x)). The syndrome polynomial for polynomial 1 + [x.sup.14] can be computed as follows. First, it is easy to see that [R.sub.g(x)]([x.sup.8]) = 1 + [x.sup.4] + [x.sup.6] + [x.sup.7]. Then S(1 + [x.sup.14]) = [R.sub.g(x)]([x.sup.8](1 + [x.sup.14])) = [R.sub.g(x)]([x.sup.8]) + [R.sub.g(x)]([x.sup.7]) = 1 + [x.sup.4] + [x.sup.6]. Applying Theorem 26, [R.sub.g(x)]([x.sup.9]) = [R.sub.g(x)]([xx.sup.8]) = [R.sub.g(x)](x + [x.sup.5] + [x.sup.7]) + [R.sub.g(x)] ([x.sup.8]) = x + [x.sup.5] + [x.sup.7] + 1 + [x.sup.4] + [x.sup.6] + [x.sup.7] = 1 + x + [x.sup.4] + [x.sup.5] + [x.sup.6]. Similarly, by applying Theorems 26 and 27, all syndrome polynomials will be determined. Table 2 shows all syndrome polynomials.

Step 2. Assume that y(x) is the received polynomial. Then the syndrome polynomial S(y(x)) = [R.sub.g(x)]([x.sup.n-k]y(x)) can be computed. Applying Theorem 26(iv), S(y(x)) = S(e(x)), where y(x) = c(x) + e(x) and c(x) [member of] C.

Example 29 (see [27, Example 4.6.4]). We give an example for Step 2. We continue Example 28. Suppose that y(x) = 1 + [x.sup.4] + [x.sup.7] + [x.sup.9] + [x.sup.10] + [x.sup.12] is a received polynomial. This implies that S(y(x)) = x + [x.sup.2] + [x.sup.6] + [x.sup.7].

Step 3. If S(y(x)) is in list computed in Step 1, then the error polynomial e(x) can be computed and it can be subtracted from y(x) to the corrected codeword c(x) = y(x) - e(x). If S(y(x)) is not appearing in the list computed in Step 1, then the process will continue to Step 4.

Step 4. It is continuing to compute the syndrome polynomial of xy(x), [x.sup.2]y(x), ... until the syndrome polynomial is in the list from Step 1. If S([x.sup.i]y(x)) is in this list and it is associated with the error polynomial [e.sup.*](x), then the received vector is decoded as y(x) - [x.sup.n-i], [e.sup.*](x). By using Theorem 27, [mathematical expression not reproducible].

We finish this part by the following example.

Example 30 (see [27, Example 4.6.6]). We can see that S(y(x)) = x + [x.sup.2] + [x.sup.6] + [x.sup.7] is not in the list computed in Step 1, then we continue to compute S(xy(x)) = x(x + x + [x.sup.6] + [x.sup.7]) - 1 x g(x) = 1 + [x.sup.2] + [x.sup.3] + [x.sup.4] + [x.sup.6], which is not also appearing in the list in Step 1. It is easy to check that S([x.sup.2]y(x)) = x(1 + [x.sup.2] + [x.sup.3] + [x.sup.4] + [x.sup.6])-0 x g(x) = x + [x.sup.3] + [x.sup.4] + [x.sup.5] + [x.sup.7] is in the list in Step 1. This implies that y(x) is decoded as y(x) - ([x.sup.2] + [x.sup.12]) = 1 + [x.sup.2] + [x.sup.4] + [x.sup.7] + [x.sup.9] + [x.sup.10].

Suppose that [alpha] [member of] [F.sub.q] is a primitive (q - 1)th root of unity, n is even, q = [2.sup.m], and [THETA] is an automorphism of [F.sub.q] such that [THETA]([alpha]) = [[alpha].sup.2]. We give two results in [3] and use them later.

Lemma 31 (see [3, Proposition 1]). For P = [[summation].sup.n-1.sub.k=0] [a.sub.k][x.sup.k] [member of] [F.sub.q][x; [THETA]], [beta] [member of] [F.sub.q] and r [member of] [F.sub.q] the remainder of the right division of P by x - [beta], then r = [bar.P] is a (classical) polynomial given by [mathematical expression not reproducible].

Lemma 32 (see [3, Proposition 2]). Let n be even, q = [2.sup.n], and [alpha] a primitive (q - 1)th root of unity. Let C be a [THETA]-cyclic code with [THETA]([alpha]) = [[alpha].sup.2]. Let G [member of] [F.sub.q] [x; [THETA]] be its generating polynomial such that G is a right divisor of [x.sup.n] - 1 in [F.sub.q][x; [THETA]] and x - [[alpha].sup.k] is a right factor of G for k e {1, ..., d - 1}. The distance of the code C is equal to its designed distance d.

We now introduce the procedure for decoding skew BCH codes. Assume that [mathematical expression not reproducible] is the error polynomial with [i.sub.1] < [i.sub.2] < ... < [i.sub.r], where r [less than or equal to] (d - 1)/2. The polynomial [mathematical expression not reproducible] is called a syndrome polynomial of e. Note that Rem(e, x - [[alpha].sup.k]) is to be computed in the skew polynomial [mathematical expression not reproducible]. Hence,

[S.sub.d](z) = [d-1.summation over (i=1)] Rem (e, x - [[alpha].sup.k][z.sup.k-1] = [d-1.summation over (k=1)][bar.e]([alpha].sup.k])[z.sup.k-1], (33)

where [mathematical expression not reproducible]. The polynomials [mathematical expression not reproducible] are called pseudolocator polynomial and evaluator polynomial, respectively. Let

[mathematical expression not reproducible]. (34)

This implies that [sigma](z)S(z) = w(z). This equation can be written to become [sigma](z) + [S.sub.d](z) + v(z)[z.sup.d-1] = w(z), where v(Z) = [sigma](z) [[summation].sup.[infinity].sub.k=1][bar.e]([[alpha].sup.k+1+d])[z.sup.k].

Applying the Euclidean Algorithm to the polynomials [mathematical expression not reproducible], three sequences ([r.sub.i](z)), ([u.sub.i](z)), and ([v.sub.i] (z)) are defined as follows:

[r.sub.-1](z) = [z.sup.d-1],

[r.sub.0] = [S.sub.d](z),

[u.sub.-1](z) = 0,

[u.sub.0](z) = 1,

[v.sub.-1](z) = 1,

[v.sub.0](z) = 0 (35)

and [r.sub.i](z) = [r.sub.i-2](z)-[q.sub.i](z)[r.sub.i-1](z), [u.sub.i](z) = [u.sub.i-2](z) - [q.sub.i](z)[u.sub.i-1](z), and [v.sub.i](z) = [v.sub.i-2](z) - [q.sub.i](z)[v.sub.i-1](z) with deg([r.sub.i](z)) < deg([r.sub.i-1])(z). The process will stop whenever k can be determined satisfying deg([r.sub.k-1]) [greater than or equal to] (d-1)/2 and deg([r.sub.k]) < (d-1)/2. From this, [r.sub.k](z), [sigma](z), and w(z) can be computed by three equations as follows:

[u.sub.k](z)[S.sub.d](z) + [v.sub.k](z)[z.sup.d-1] = [r.sub.k](z);

[sigma](z) = [u.sub.k](z)/[u.sub.k](0);

w(z) = [r.sub.k](z)/[r.sub.k](0). (36)

From the roots of the pseudolocator polynomial [sigma](z), all [j.sub.l], l [member of] {1, 2, ..., r}, will be listed. This shows that

[mathematical expression not reproducible]. (37)

From the equation above, all coefficients of e are also determined. For each [j.sub.l], finite number of possibilities [i.sub.l] solutions to the equation [mathematical expression not reproducible] (mod n) can be found. Similarly to the procedure for decoding BCH codes, this process will test until the skew polynomial e is determined. Since e is unique, the decoded word can be exhibited, as required.

We conclude this section by an example provided by Boucher et al. in [3] to illustrate this process in detail.

Example 33 (see [3]). Let a be such that [mathematical expression not reproducible]. Suppose that m = n = 10. Then the polynomial g(x) = [x.sup.6] + [[alpha].sup.345][x.sup.5] + [[alpha].sup.643][x.sup.4] + [[alpha].sup.878][x.sup.3] + [[alpha].sup.670][x.sup.2] + [[alpha].sup.1020]x + [[alpha].sup.777] is a divisor of [x.sup.10] + 1 in [mathematical expression not reproducible]. This implies that g(x) is the generator polynomial of a [THETA]-cyclic code of length 10 over [mathematical expression not reproducible]. We can see that x -[[alpha].sup.k] is a right factor of g(x) for all k [member of] {1, ..., 6}. Hence, the designed distance of the code C is d = 7. Now we consider [mathematical expression not reproducible] and an error e = [[alpha].sup.341][x.sup.9] + [[alpha].sup.682][x.sup.8] + [[alpha].sup.682]. The pertubed codeword h is

[mathematical expression not reproducible]. (38)

Since d = 7 and polynomial h, we have the syndrome polynomial

[S.sub.7](z) + [[alpha].sup.404][z.sup.5] + [[alpha].sup.403][z.sup.4] + [[alpha].sup.601][z.sup.3] + [[alpha].sup.645][z.sup.2] + [[alpha].sup.614]z + [[alpha].sup.406]. (39)

Applying Euclid Algorithm to [S.sub.7](z) and [z.sup.6] in [mathematical expression not reproducible] with (d-1)/2 = 3, we can get the pseudolocator polynomial [sigma](z) = [[alpha].sup.766][z.sup.3] + [[alpha].sup.642][z.sup.2] + [[alpha].sup.241][z + 1] and the evaluator polynomial w(z) = [[alpha].sup.84][z.sup.2] + [[alpha].sup.185]z + [[alpha].sup.406]. The roots of the polynomial [sigma](z) are 1, [[alpha].sup.512], and [[alpha].sup.768]. From this, we have r = 3, [j.sub.1] = 0, [j.sub.2] = 511, and [j.sub.3] = 255. By the polynomial w(z), we can find [mathematical expression not reproducible]. Combining this result and the equations [mathematical expression not reproducible], we have [i.sub.1] - 0 (mod 10), [i.sub.2] = 1, 5, 9 (mod 10), and [i.sub.3] =4, 8 (mod 10). Then we can list all possible errors as follows:

[mathematical expression not reproducible]. (40)

It is easy to find that e = [[alpha].sup.341][x.sup.9] + [[alpha].sup.682][x.sup.8] + [[alpha].sup.682].

5. Skew [THETA]-[lambda]-Constacyclic Codes over Finite Chain Rings

Constacyclic codes have practical applications as they can be efficiently encoded using simple shift registers. They have rich algebraic structures for efficient error detection and correction, which explains their preferred role in engineering. Classically, the algebraic structures of constacyclic codes are determined by ideals in the polynomial rings over finite fields, Galois rings, and finite chain rings. In [3], Boucher et al. generalized the notion of cyclic codes by using generator polynomial in noncommutative skew polynomial rings. Since there are much more skew cyclic codes, the new class of codes allowed them to systematically search for codes. Later on, the approach has been extended to codes over Galois rings [29]. In 2012, Jitman et al. [26] studied skew [THETA]-[lambda]-constacyclic codes over finite chain rings. These codes have been studied for a particular case when codes are generated by monic right divisors of [x.sup.n] - [lambda], where [lambda] is a unit in the finite chain rings fixed by a given automorphism. Similarly to the case of skew [THETA]-[lambda]-constacyclic codes over finite fields, when [THETA] is the identity automorphism, they become classical constacyclic codes over finite chain rings. Therefore, skew [THETA]-[lambda]-constacyclic codes over finite chain rings can be considered as a generalization of classical constacyclic codes over finite chain rings. This is the reason why the study of skew [THETA]-[lambda]-constacyclic codes over finite chain rings is important. In this section, we overview the study of skew [THETA]-[lambda]-constacyclic codes over finite chain rings studied by Jitman et al. [26].

A finite commutative ring with identity is called a finite chain ring if its ideals are linearly ordered by inclusion or, equivalently, its ideals are principal and its maximal ideal is unique. In [32], it is known that a finite chain ring is local and its unique maximal ideal is principal. Constacyclic codes over a finite commutative chain ring have been studied by many authors (see, e.g., [23, 33-36]). The structure of constacyclic codes is also introduced over a special family of finite chain rings of the form [mathematical expression not reproducible]. Recently, skew [THETA]-codes over finite fields and Galois rings were studied by Boucher et al. Motivated by these results, in [26], Jitman et al. generalized the concept of skew [THETA]-[lambda]-constacyclic codes over finite fields and Galois rings to that over finite chain rings. The structure of all skew [THETA]-[lambda]-constacyclic codes over a finite chain ring is determined. Moreover, Euclidean and Hermitian dual codes of skew [THETA]-cyclic and negacyclic codes are considered. They also studied skew [THETA]-[lambda]-constacyclic codes over a special case [mathematical expression not reproducible] of a finite chain ring.

In this section, let R be a finite chain ring with unique maximal ideal <[gamma]>. Then [gamma] is a nilpotent ideal of R and we denote its nilpotency index by t. Hence, the ideals of R form the following chain:

[mathematical expression not reproducible]. (41)

Analogous to the case of finite fields, the set of automorphisms of R forms a group under composition, denoted by Aut(R). Many classes of finite chain rings have nontrivial automorphism groups. For examples, Aut(GR([p.sup.e], m)) is nontrivial if and only if m [greater than or equal to] 2 (cf. [16]) and Aut[mathematical expression not reproducible]) is nontrivial if and only if m [greater than or equal to] 2 or p is odd or e [greater than or equal to] 3 (cf. [37, Proposition 1]).

We know that [mathematical expression not reproducible] is left and right Euclidean ring whose left and right ideals are principal. Unlike the ring [mathematical expression not reproducible], if R is a finite chain ring, then the skew polynomial ring R[x; [THETA]] is neither left nor right Euclidean ring. Therefore, we need to define left and right divisions. Suppose that f(x) = [[summation].sup.s.sub.i=0] [a.sub.i][x.sup.i] and g(x) = [[summation].sup.t.sub.j=0][b.sub.j][x.sup.j], where [b.sub.t] is a unit in R and s [greater than or equal to] t. We can see that the degree of polynomial

f(x) - [a.sub.s] x [[THETA].sup.s-t] ([b.sup.-1.sub.t])[x.sup.s-t]g(x) (42)

is less than the degree of f(x). By the inductive method, we can obtain skew polynomials q(x) and r(x) such that f(x) = q(x)g(x) + r(x) with deg(r(x)) < deg(g(x)) or r(x) = 0. If r(x) = 0, then we say that g(x) is a right divisor of f(x). The skew polynomials q(x) and r(x) are unique. They are called the right quotient and right remainder, respectively. Note that if s < t, then we put f(x) = 0 x g(x) + f(x). This algorithm is called the Right Division Algorithm in R[x; [THETA]]. The Left Division Algorithm in R[x; [THETA]] can be defined similarly, using the fact that the degree of

f(x) - g(x) [[THETA].sup.-t]([a.sub.s][b.sup.-1.sub.t])[x.sup.s-t] (43)

is less than the degree of f(x). Now we recall the definition of skew [THETA]-[lambda]-constacyclic codes in R[x; [THETA]]. Given an automorphism [THETA] of R and a unit in R, a linear code C is said to be skew [THETA]-[lambda]-constacyclic if C is closed under the [THETA]-[lambda]-constacyclic shift [[tau].sub.[THETA],[lambda]] : [R.sup.n] [right arrow] [R.sup.n] defined by

[[tau].sub.[THETA],[lambda]]([c.sub.0], [c.sub.1], ..., [c.sub.n-1]) =([THETA]([lambda][c.sub.n-1]), [THETA]([c.sub.0]), ..., [THETA]([c.sub.n-2])). (44)

5.1. Skew [THETA]-[lambda]-Constacyclic Codes over Finite Chain Rings. For a skew polynomial g(x) in R[x; [THETA]], then a left ideal generated by g(x), denoted by (g(x)), is in general not a two-sided ideal. However, if g(x) = [x.sup.t]h(x) (t [member of] [N.sub.0]) such that h(x) is central (i.e., commutes with all elements of R[x; [THETA]]), then <f(x)> is a principal two-sided ideal in R [x; [THETA]]. From this remark, the following corollary is a direct consequence.

Corollary 34 (see [26, Corollary 2.2]). If f(x) is a monic central skew polynomial of degree n, then the skew polynomials of degree less than n are canonical representatives of the elements in R[x; [THETA]]/<f(x)>.

Analogous to classical constacyclic codes, we study skew [THETA]-[lambda]-constacyclic codes as left ideals in R[x; [THETA]]/<[x.sup.n] - [lambda]>. Note that R [x; [THETA]] is a noncommutative ring. So we need to have the conditions of [THETA] and [lambda] which ensure that ([x.sup.n] - [lambda]) is a two-sided ideal.

Lemma 35 (see [26, Proposition 2.2]). Let n be a positive integer and [lambda] a unit in R. Then the following statements are equivalent:

(i) [x.sup.n] - [lambda] is central in R[x; [THETA]].

(ii) <[x.sup.n] - [lambda]> is a two-sided ideal.

(iii) n is a multiple of the order of [THETA] and [lambda] is fixed by [THETA].

For [THETA]-[lambda]-constacyclic codes over finite fields, a code C is a skew [THETA]-[lambda]-constacyclic code if and only if C is a left ideal [mathematical expression not reproducible], where g(x) is right divisor of [x.sup.n] - [lambda]. In the case finite chain rings, the following theorem is analogous to that for [THETA]-[lambda]-constacyclic codes over finite fields.

Theorem 36 (see [26, Theorem 2.2]). Let [THETA] be an automorphism of R, n an integer divisible by the order of [THETA], and [lambda] a unit in R which is fixed by [THETA]. Then the code C is a skew [THETA]-[lambda]-constacyclic code if and only if C is a left ideal <g(x)) [subset or equal to] R[x; [THETA]]/<[x.sup.n] - [alpha]), where g(x) is a right divisor of [x.sup.n] - [lambda].

From this theorem, we can find a skew [THETA]-[lambda]-constacyclic code as a left ideal <g(x)) [subset or equal to] R[x; [THETA]]/<[x.sup.n] - [lambda]), where g(x) is a right divisor of [x.sup.n] - [lambda]. However, it is not easy to list all skew [THETA]-[lambda]-constacyclic codes because R[x; [THETA]] is not unique factorization ring. Therefore, there are many more right factors than in the commutative case, which in turn produces many more skew [THETA]-[lambda]-constacyclic codes.

Example 37. Let R = [F.sub.3] + u[F.sub.3] be a finite chain ring. We consider the automorphism [[THETA].sub.id,2] of [F.sub.3] + u[F.sub.3], where [[THETA].sub.id,2](a + ub) = a + 2bu. Then we have two irreducible factorizations of [x.sup.6] - 1 in ([F.sub.3] + u[F.sub.3])[x; [[THETA].sub.id,2]]:

[x.sup.6] - 1 = [(x + 1).sup.3][([x + 2).sup.3] = [([x.sup.2] + ux + 2).sup.3]. (45)

Given a monic right divisor of degree n - k of [x.sup.n] - [lambda] : g(x) = [[summation].sup.n-k-1.sub.i=0] [g.sub.i](x) + [x.sup.n-k], then a generator matrix of the [THETA]-[lambda]-constacyclic code C generated by g(x) is given by

[mathematical expression not reproducible]. (46)

The rows of G are linearly independent. Then we have the following result.

Proposition 38 (see [26, Proposition 3.1]). Let g(x) be a right divisor of [x.sup.n] - [lambda]. Then the [THETA]-[theta]-constacyclic code C generated by g(x) is a free R-module with [absolute value of C] = [[absolute value of R].sup.n-deg(g(x)).

Similarly, in the case of finite fields, we denote [R.sup.[THETA]], the subring of R fixed by [THETA]. Then we have the following result.

Proposition 39 (see [26, Proposition 3.2]). Let g(x) be a monic right divisor of [x.sup.n] - [lambda] in R[x; [THETA]]. The skew [THETA]-[lambda]-constacyclic code generated by is [lambda]-constacyclic if and only if g(x) [member of] [R.sup.[THETA]][x; [THETA]].

Let C be a [THETA]-[lambda]-constacyclic code. In the following lemma, the parity-check matrix for C is introduced.

Lemma 40 (see [26, Proposition 3.3]). Let C be the [THETA]-[lambda]-constacyclic code generated by a monic right divisor of [x.sup.n] - [lambda] and h(x) := ([x.sup.n] - [lambda])/g(x). Then the following statements hold:

(i) For c(x) [member of] R[x; [THETA]], c(x) [member of] C if and only if c(x)h(x) = 0 in R[x; [THETA]]/<[x.sup.n] - [lambda]).

(ii) If h(x) = [[summation].sup.k-1.sub.i=0] [h.sub.i][x.sup.i] + [x.sup.k], then the matrix

[mathematical expression not reproducible] (47)

is a parity-check matrix for C.

In the next part, we study the Euclidean and Hermitian dual codes of skew [THETA]-[lambda]-constacyclic codes over finite chain rings. Suppose that the length n of codes is divisible by the order of [THETA], and [lambda] is a unit in R which is fixed by [THETA]. Euclidean inner product is defined by <u, v> = [[summation].sup.n-1.sub.i=0] [u.sub.i][v.sub.i], for u = ([u.sub.0], [u.sub.1], ..., [u.sub.n-1]) and v = ([v.sub.0], [v.sub.1], ..., [v.sub.n-1]) in [R.sup.n]. In special case, if the order of [THETA] is 2, then we can also give the Hermitian inner product, denoted by [<u, v>.sub.H] = [[summation].sup.n-1.sub.i=0] [u.sub.i][THETA]([v.sub.i]). If 0 (resp., [<u, v>.sub.H] = 0), then u and v are called Euclidean orthogonal (resp., Hermitian orthogonal). The Euclidean and Hermitian dual code of a code C are defined to be

[C.sup.[perpendicular to]] = {v [member of] [R.sup.n] | <v, c> = 0, [for all]c [member of] C}, (48)

[mathematical expression not reproducible], (49)

respectively. If [mathematical expression not reproducible], then C is said to be Euclidean (Hermitian) self-dual code. We get a main result which describes the relationship between a skew [THETA]-[lambda]-constacyclic code and its dual.

Lemma 41 (see [26, Lemma 3.1]). Let C be a code of length n over R. Then C is skew [THETA]-[lambda]-constacyclic if and only if [C.sup.[perpendicular to]] is [THETA]-[[lambda].sup.-1-constacyclic. In particular, if [[lambda].sup.2] = 1, then C is [THETA]-[lambda]-constacyclic ifand only if [C.sup.[perpendicular to]] is [THETA]-[lambda]-constacyclic.

5.2. Euclidean Dual Codes. We denote that R[[x; [THETA]].sup.S-1] is the right localization of R[x; [THETA]]. The following theorem will discuss the necessary and sufficient conditions for R[x; [THETA]] to have the right localization.

Theorem 42 (see [26, Theorem 2.1]). Let S = {[x.sup.i] | i [member of] N}. Then R [x; [THETA]] has the right localization at S ifand only if both the following conditions hold:

(i) For all [x.sup.i] [member of] S and a(x) [member of] R[x; [THETA]], there exist [x.sup.j] [member of] S and b(x) [member of] R[x; [THETA]] such that a(x)[x.sup.i] = [x.sup.j]b(x).

(ii) Given a(x) [member of] R[x; [THETA]] and [x.sup.i] [member of] S, if [x.sup.i] a(x) = 0, then there exists [x.sup.j] [member of] S such that a(x)[x.sup.j] = 0.

Before determining the structure of dual codes, we get the following result.

Lemma 43 (see [26, Proposition 2.4]). Let [phi] : R[x; [THETA]] [right arrow] R[x; [THETA]][S.sup.-1] defined by

[phi]([k.summation over (i=0)] [a.sub.i][x.sup.i]) = [k.summation over (i=0)] [x.sup.-i] [a.sub.i]. (50)

Then [phi] is a ring antimonomorphism.

From Lemma 41, it is easy to verify that the Euclidean dual of a skew [THETA]-[lambda]-constacyclic code C is again a skew [THETA]-[lambda]-constacyclic code. We introduce a result about Euclidean dual codes. To do that, we need the following lemma.

Lemma 44 (see [26, Lemma 3.2]). Assume that [[lambda].sup.2] = 1. Let a(x) = [a.sub.0] + [a.sub.1]x + ... + [a.sub.n-1][x.sup.n-1] and b(x) = [b.sub.0] + [b.sub.1]x + ... + [b.sub.n-1][x.sup.n-1] be polynomials in R[x; [THETA]]. Then the following statements are equivalent:

(i) The coefficient vector of a(x) is Euclidean orthogonal to the coefficient vector of [x.sup.i]([x.sup.n-1][phi](b(x))) for all i [member of] {0,1, ..., n - 1}, where ([phi]: R[x; [THETA]] [right arrow] R[x; [THETA]][S.sup.-1] is a ring antimonomorphism defined in Lemma 43.

(ii) ([a.sub.0], [a.sub.1], ..., [a.sub.n-1]) is Euclidean orthogonal to ([[THETA].sup.-1], ([b.sub.n-1]), ([b.sub.n-2]), ..., [[THETA].sup.n-2]([b.sub.0])) and all its [THETA]-[lambda]-constacyclic shifts.

(iii) a(x)b(x) = 0 in R[x; [THETA]]/<[x.sup.n] - [lambda]>.

Theorem 45 (see [26, Theorem 3.3]). Assume that [[lambda].sup.2] = 1. Let g(x) be a right divisor of [x.sup.n] - [lambda] and h(x) := ([x.sup.n] - [lambda])/g(x). Let C be the [THETA]-[lambda]-constacyclic code generated by g(x). Then the following statements hold:

(i) The skew polynomial [x.sup.deg(h(x)] [phi](h(x)) is a right divisor of [x.sup.n] - [lambda].

(ii) The Euclidean dual [C.sup.[perpendicular to]] is a [THETA]-[lambda]-constacyclic code generated by [x.sup.deg(h(x))][phi](h(x)).

Theorem 46 (see [26, Theorem 3.4]). Assume that [[lambda].sup.2] = 1 and n is even, denoted by n = 2k. Let g(x) = [[summation].sup.k-1.sub.i=0] [g.sub.i[x.sup.i] be a right divisor of [x.sup.n] - [lambda]. Then the [THETA]-[lambda]-constacyclic code generated by g(x) is Euclidean self-dual if and only if

[mathematical expression not reproducible]. (51)

Theorem 46 provided the necessary and sufficient conditions for a skew [THETA]-[lambda]-constacyclic code to be Euclidean self-dual code. By applying Theorem 46, we can see that if the order of [THETA] divides k and [lambda] [not equal to] -1, then there are no Euclidean self-dual skew constacyclic codes of length 2k. Moreover, if [THETA] is the identity automorphism and [lambda] [not equal to] -1, then there are no Euclidean self-dual codes.

5.3. Hermitian Dual Codes. The Hermitian inner product is defined only when the order of [THETA] is 2. Therefore, in this subsection, we always suppose that the order of [THETA] is 2. We first have some characterizations of Hermitian duality.

Lemma 47 (see [26, Lemma 3.5]). Let C be a code of length n over R. Then C is skew [THETA]-[lambda]-constacyclic if and only if [mathematical expression not reproducible] is [THETA]-[[lambda].sup.-1]-constacyclic. In particular, if [[lambda].sup.2] = 1, then C is [THETA]-[lambda]-constacyclic if and only if [mathematical expression not reproducible] is [THETA]-[lambda]-constacyclic.

Let [phi] be a ring automorphism of R[x; [THETA]] defined by [phi]([[summation].sup.s.sub.i=0][a.sub.i][x.sup.i]) = [[summation].sup.s.sub.i=0] [THETA]([a.sub.i])[x.sup.i]. Then we have the following result.

Lemma 48 (see [26, Lemma 3.6]). Assume that [[lambda].sup.2] = 1. Let a(x) = [a.sub.0] + [a.sub.1]x + ... + [a.sub.n-1][x.sup.n-1] and b(x) = [b.sub.0] + [b.sub.1]x + ... + [b.sub.n-1][x.sup.n-1] be polynomials in R[x; [THETA]]. Then the following statements are equivalent:

(i) The coefficient vector of a(x) is Euclidean orthogonal to the coefficient vector of [x.sup.i]<p([x.sup.n-1] [phi](b(x))) for all i [member of] {0, 1, ..., n - 1}, where [phi]: R[x; [THETA]] [right arrow] R[x; [THETA]][S.sup.-1] is a ring antimonomorphism defined in Lemma 43.

(ii) ([a.sub.0], [a.sub.1], ..., [a.sub.n-1]) is Hermitian orthogonal to ([[THETA].sup.-1]([b.sub.n-1]),([b.sub.n-2]), ..., [[THETA].sup.n-2]([b.sub.0])) and all its [THETA]-[lambda]-constacyclic shifts.

(iii) a(x)b(x) = 0 in R[x; [THETA]]/<[x.sup.n] - [lambda]).

Theorem 49 (see [26, Theorem 3.7]). Assume that [[lambda].sup.2] = 1. Let g(x) be a right divisor of [x.sup.n] - [lambda] and h(x) := ([x.sup.n] - [lambda])/g(x). Let C be the [THETA]-[lambda]-constacyclic code generated by g(x). Then the following statements hold:

(i) The skew polynomial 0([x.sup.deg(h(x))][phi](h(x))) is a right divisor of [x.sup.n] - [lambda].

(ii) The Hermitian dual [C.sup.[perpendicular to]]H is a [THETA]-[lambda]-constacyclic code generated by 0([x.sup.deg(h(x)))][phi](h(x))).

Similar to the case of the Euclidean self-dual code, we have the necessary and sufficient conditions for a [THETA]-[lambda]-constacyclic code to be Hermitian self-dual.

Theorem 50 (see [26, Theorem 3.8]). Assume that [[lambda].sup.2] = 1 and n is even, denoted by n = 2k. Let g(x) = [[summation].sup.k-1.sub.i=0][g.sub.i][x.sup.i] + [x.sup.k] be a right divisor of [x.sup.n] - [lambda]. Then the [THETA]-[lambda]-constacyclic code generated by is Hermitian self-dual if and only if

([k-1.summation over (i=0)][g.sub.i][x.sup.i] + [x.sup.k]) x ([[THETA].sup.-k-1]([g.sup.-1.sub.0]) + [k-1.summation over (i=0)][[THETA].sup.i-k-1]([g.sup.-1.sub.0][g.sub.k-i])[x.sup.i] + [x.sup.k]) = [x.sup.n] - [lambda]. (52)

From this theorem, if k is odd and [lambda] [not equal to] -1, then there are no Hermitian self-dual [THETA]-[lambda]-constacyclic codes of length 2k.

5.4. Skew Constacyclic Codes over [mathematical expression not reproducible]. The class of finite chain rings of the form [mathematical expression not reproducible] has been used widely as alphabets in certain constacyclic codes. It has been studied by many researchers (see, for more details, [23-25, 33, 35, 38]). In recent years, we have studied constacyclic codes of length [p.sub.s] over [mathematical expression not reproducible]. All constacyclic codes of length [p.sup.s] over the ring [mathematical expression not reproducible] are considered. The purpose of this subsection is to investigate the structure of all skew [THETA]-[lambda]-constacyclic codes over [mathematical expression not reproducible], where [lambda] is fixed by [THETA] and the length n of codes is a multiple of the order of [THETA]. Note that the set of automorphisms of [mathematical expression not reproducible] forms a group under composition, denoted by Aut[mathematical expression not reproducible]. The group Aut[mathematical expression not reproducible] is completely characterized by Alkhamees [37] as follows.

Theorem 51. For [alpha] [member of] Aut[mathematical expression not reproducible] and [mathematical expression not reproducible], let

[mathematical expression not reproducible] (53)

be defined by

[mathematical expression not reproducible]. (54)

In the next part, the structure of skew [THETA]-cyclic and negacyclic codes over [mathematical expression not reproducible] is studied. We refer the readers to [26, 38] for more details.

Assume that C is a nonzero left ideal in [mathematical expression not reproducible]. Let A be the set of all nonzero skew polynomials of minimal degree in C. Then the classifications of [THETA]-[lambda]-constacyclic codes are given in terms of generators of left ideals in [mathematical expression not reproducible].

Theorem 52 (see [26, Theorem 4.1]). Let C and A be as above. Then consider the following:

(i) If there exists a monic skew polynomial in A, then it is unique in A. In this case, C = <g(x)), where g(x) is such unique skew polynomial.

(ii) If there are no monic skew polynomials in C, then there exists a unique skew polynomial = g(x) = u[g.sub.1](x) in A with leading coefficient u. In this case, C = <g(x)>.

(iii) If there are no monic skew polynomials in A but there exists a monic skew polynomial in C, then there exists a unique skew polynomial g(x) = u[g.sub.1] in A with leading coefficient u and a unique monic skew polynomial f(x) = [f.sub.0](x) + u[f.sub.1](x) of minimal degree in C such that deg([f.sub.1](x)) < deg([g.sub.1](x)). In this case, C = <g(x), f(x)>.

We categorize the left ideals of [mathematical expression not reproducible] into three types: Type LI-1 refers to the trivial ideal (<0>, <1>) or a left ideal satisfying part (i) of the theorem above. Similarly, LI-2 and LI-3 refer to a left ideal satisfying Theorem 52 ((ii) and (iii)), respectively. Next, we provide some properties of left ideals of each type LI-i (i = 1, 2, 3.) First, we consider type LI-1 by the following lemmas.

Lemma 53 (see [26, Proposition 4.1]). A left ideal of type LI-1 is principal and generated by a monic right divisor of [x.sup.n] - [lambda] in [mathematical expression not reproducible]. Moreover, if we view g(x) = [g.sub.0](x) + [ug.sub.1](x), where [mathematical expression not reproducible], then deg([g.sub.1] (x)) < deg([g.sub.0](x)) and [g.sub.0](x) is a monic right divisor of [x.sup.n] - [bar.[lambda]] in [mathematical expression not reproducible].

Lemma 54 (see [26, Proposition 4.2]). A left ideal of type LI-2 is principal and generated by g(x) = u[g.sub.1](x), where [g.sub.1](x) is a monic right divisor of [mathematical expression not reproducible] such that deg([g.sub.1](x)) < n.

We write [mathematical expression not reproducible] to indicate that [mathematical expression not reproducible] is the skew polynomial such that [mathematical expression not reproducible].

Lemma 55 (see [26, Proposition 4.3]). A left ideal of type LI-3 is generated by {g(x) = u[g.sub.1](x), f(x) = [f.sub.0](x) + u[f.sub.1](x)}, where [mathematical expression not reproducible] satisfy the following properties:

(i) [g.sub.1](x), [f.sub.0](x) are monic,

(ii) deg([f.sub.1](x)) < deg([g.sub.1](x)) < deg([f.sub.0](x)) < n,

(iii) [g.sub.1](x) is a right divisor of [f.sub.0](x) in [mathematical expression not reproducible],

(iv) [f.sub.0](x) is a right divisor of [mathematical expression not reproducible]. Moreover, if [mathematical expression not reproducible], then [g.sub.1](x) is a right divisor of [mathematical expression not reproducible].

Example 56. Let R = [F.sub.3] + u[F.sub.3] be a finite chain ring. We consider the automorphism [[THETA].sub.id,2] of [F.sub.3] + u[F.sub.3], where [[THETA].sub.id,2](a + ub) = a + 2bu for all a, b [member of] [F.sub.3]. We list all left ideals in three types LI-i (i = 1, 2, 3) in ([F.sub.3] + u[F.sub.3])[x; [[THETA].sub.id,2]]/<[x.sup.2] - 1>. All left ideals in type LI-1 are <0>, <1>, <x + 1>, <x + 2>, <x + 1 + u>, <x + 1 + 2u>, <x + 2 + u>, <x + 2 + 2u>. All left ideals in type LI-2 are <u>, <u(x + 1)>, <u(x + 2)>, and all left ideals in type LI-3 are <u, x + 1>, <u, x + 2>.

Applying Theorem 52, the structure of skew [THETA]-[lambda]-constacyclic codes over [mathematical expression not reproducible] is introduced. We have three types of the left ideals in the ring [mathematical expression not reproducible]. From this, we study the structure of the Euclidean dual codes of skew [THETA]-cyclic and negacyclic codes over [mathematical expression not reproducible].

Theorem 57 (see [26, Theorem 4.2]). Let [lambda] [member of] {-1, 1}.Then the Euclidean dual code of a left ideal in [mathematical expression not reproducible] is also a left ideal in [mathematical expression not reproducible] determined as follows:

([LI-1.sup.[perpendicular to]]) [mathematical expression not reproducible].

([LI-2.sup.[perpendicular to]]) [mathematical expression not reproducible].

([LI-3.sup.[perpendicular to]]) If C = (u[g.sub.1](x), [f.sub.0](x) + u[f.sub.1](x)), then there exists [mathematical expression not reproducible] such that [mathematical expression not reproducible] and

[mathematical expression not reproducible], (55)

where [phi] : R[x; [THETA]] [right arrow] R[x; [THETA]][S.sup.1] defined by [phi]([[summation].sup.k.sub.i=0][a.sub.i][x.sup.i]) = [[summation].sup.k.sub.i=0][x.sup.-i][a.sub.i].

For Hermitian dual codes, we assume that the order of [THETA] is 2. We have the structure of Hermitian dual codes of skew [THETA]-cyclic and negacyclic codes over [mathematical expression not reproducible] as follows.

Theorem 58 (see [26, Theorem 4.3]). Let [lambda] [member of] {-1, 1} and let [THETA] be an automorphism of order 2. Then the Hermitian dual code of a left ideal in [mathematical expression not reproducible] is also a left ideal in [mathematical expression not reproducible] determined as follows:

([LI-1.sup.[perpendicular to]]) [mathematical expression not reproducible].

([LI-2.sup.[perpendicular to]]) [mathematical expression not reproducible].

([LI-3.sup.[perpendicular to]]) If C = (u[g.sub.1](x), [f.sub.0](x) + u[f.sub.1](x)), then there exists [mathematical expression not reproducible] such that [mathematical expression not reproducible] and

[mathematical expression not reproducible], (56)

where [phi] : R[x; [THETA]] [right arrow] R[x; [THETA]][S.sup.-1] defined by [phi]([[summation].sup.k.sub.i=0][a.sub.i][x.sup.i]) = [[summation].sup.k.sub.i=0][x.sup.-i][a.sub.i].

Finally, we give an example for Euclidean and Hermitian dual codes.

Example 59. We knew in previous example that all left ideals of type LI-1 in <[F.sub.3] + u[F.sub.3]>[x; [[THETA].sub.id,2]/<[x.sup.2] - 1> are <0>, <1>, <x + 1>, <x + 2>, <x + 1 + u>, <x + 2 + u>, <x + 1 + 2u>, <x + 2 + 2u>. Then their Euclidean dual codes are <1>, <0>, <x + 2>, <x + 1>, <x + 2 + u>, <x + 1 + u>, <x + 2 + 2u>, <x + 1 + 2u>, respectively. Similarly, Hermitian dual codes are <1>, <0>, <x + 2>, <x + 1>, <x + 2 + 2u>,<x + 2 + u>,<x + 1 + 2u>,<x + 1 + u>. All left ideals in type LI-2 are <u>, <u(x + 1)>, <u(x + 2)>. The Euclidean dual codes coincided with the Hermitian dual codes of all left ideals in type LI-2. They are <u>, <u, x + 2>, and <u, x + 1>,respectively. Similarly, the Euclidean dual codes also coincided with the Hermitian dual codes of all left ideals in type LI-3. They are <u(x + 1)>, <u(x + 2)>. We summarize discussion above in Table 3.

Disclosure

The main part of this paper was written during the visits of Bac T. Nguyen to Hai Q. Dinh at Department of Mathematical Sciences, Kent State University, USA, from November 2014 to January 2015, and Hai Q. Dinh to Songsak Sriboonchitta at Faculty of Economics, Chiang Mai University, Thailand, in January 2015.

http://dx.doi.org/10.1155/2016/3965789

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors are grateful for the Department of Mathematical Sciences, Kent State University; Faculty of Economics, Chiang Mai University; and Department of Mathematics, Mahidol University, for their hospitality and financial support. The authors' thanks are extended to the Centre of Excellence in Econometrics, Faculty of Economics, Chiang Mai University, for partial financial support. Bac T. Nguyen was supported by Postgraduate Student Exchange Scholarship, Mahidol University, to visit Department of Mathematical Sciences, Kent State University, USA.

Endnotes

(1.) Claude Elwood Shannon (April 30, 1916-February 24, 2001) was an American mathematician, electronic engineer, and cryptographer, who is referred to as "the father of information theory" [39]. Shannon is also known as the founder of both digital computer and digital circuit design theory, when, as a 21-year-old M.S. student at MIT in 1937, he wrote a thesis establishing that electrical application of Boolean algebra could construct and resolve any logical, numerical relationship [40]. It has been claimed that this was the most important M.S. thesis of all time. Shannon contributed to the field of cryptanalysis during World War II and afterwards, including basic work on code breaking.

(2.) Turbo codes were first introduced and developed in 1993 by Berrou et al. [41]. Turbo codes are a class of high-performance forward error correction codes, which were the first practical codes to closely approach the channel capacity, a theoretical maximum for the code rate at which reliable communication is still possible given a specific noise level. Turbo codes are widely used in deep space communications and other applications where designers seek to achieve reliable information transfer over bandwidth-constrained or latency-constrained communication links in the presence of data-corrupting noise. The first class of turbo code was the parallel concatenated convolutional code. Since the introduction of the original parallel turbo codes in 1993, many other classes of turbo code have been discovered, including serial versions and repeat-accumulate codes. Iterative turbo decoding methods have also been applied to more conventional forward error correction systems, including Reed-Solomon corrected convolutional codes.

(3.) LDPC (low-density parity-check) codes were first introduced in 1963 by Gallager in his doctoral dissertation at MIT [42]. At that time, it was impractical to implement and LDPC codes were forgotten, but they were rediscovered in 1996. LDPC code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel, and is constructed using a sparse bipartite graph. LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set arbitrarily close on the binary erasure channel to the Shannon limit for a symmetric memoryless channel. The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative belief propagation techniques, LDPC codes can be decoded in time linear to their block length.

(4.) Richard Wesley Hamming (February 11, 1915-January 7, 1998) was an American mathematician whose work had many implications for computer science and telecommunications. His contributions include the Hamming code (which makes use of a Hamming matrix), the Hamming window, Hamming numbers, sphere-packing (or Hamming bound), and the Hamming distance.

(5.) During the late 1940s at Bell laboratories, Richard Hamming decided that a better system was needed. As folklore has it, Richard Hamming was working for Bell Labs. He was allowed to use the computer for research over the weekends. He would put together his punch cards during the week and submit them to be run over the weekend. This would work great as long as his punch cards were completely error-free; however, a single error would cause the computer to pass the job over and move on to the next. He would have to make corrections and resubmit his program at a later time. Richard Hamming thought that if the computer was smart enough to know that there was a mistake, why not have the computer find the mistake, correct it, and continue running the program. He then created the first error correction code, the Hamming Code. This not only solved an important problem in telecommunications and computer science, it opened up a whole new field of study.

References

[1] C. E. Shannon, "A mathematical theory of communication," The Bell System Technical Journal, vol. 27, no. 3, pp. 379-423, 1948.

[2] R. W. Hamming, "Error detecting and error correcting codes," The Bell System Technical Journal, vol. 29, no. 2, pp. 147-160, 1950.

[3] D. Boucher, W. Geiselmann, and F. Ulmer, "Skew-cyclic codes," Applicable Algebra in Engineering, Communication and Computing, vol. 18, no. 4, pp. 379-389, 2007.

[4] E. Prange, "Cyclic error-correcting codes in two symbols," Tech. Rep. TN-57-103, Air Force Cambridge Research Labs, 1957.

[5] E. Prange, "Some cyclic error-correcting codes with simple decoding algorithms," Tech. Rep. TN-58-156, Air Force Cambridge Research Center, 1958.

[6] E. Prange, "The use of coset equivalence in the analysis and decoding of group codes," Tech. Rep. TN-59-164, 1959.

[7] E. Prange, "An algorithm for factoring xn1 over a finite field," Tech. Rep. TN-59-175, 1959.

[8] E. R. Berlekamp, "Negacyclic codes for the Lee metric," in Proceedings of the Conference on Combinatorial Mathematics and Its Applications, pp. 298-316, University of North Carolina Press, Chapel Hill, NC, USA, 1968.

[9] E. R. Berlekamp, Algebraic Coding Theory, Aegean Park Press, 1984.

[10] S. D. Berman, "Semisimple cyclic and Abelian codes. II," Kibernetika, vol. 3, pp. 21-30, 1967 (Russian), Translated as: Cybernetics, vol. 3, pp. 17-23, 1967.

[11] J. L. Massey, D. J. Costello, and J. Justesen, "Polynomial weights and code constructions," IEEE Transactions on Information Theory, vol. 19, pp. 101-110, 1973.

[12] G. Falkner, B. Kowol, W. Heise, and E. Zehendner, "On the existence of cyclic optimal codes," Atti del Seminario Matematico e Fisico dell'Universita di Modena, vol. 28, no. 2, pp. 326-341,1979.

[13] R. M. Roth and G. Seroussi, "On cyclic MDS codes of length q over GF(q)," IEEE Transactions on Information Theory, vol. 32, no. 2, pp. 284-285, 1986.

[14] G. Castagnoli, J. L. Massey, P. A. Schoeller, and N. von Seemann, "On repeated-root cyclic codes," IEEE Transactions on Information Theory, vol. 37, no. 2, pp. 337-342, 1991.

[15] J. H. van Lint, "Repeated-root cyclic codes," IEEE Transactions on Information Theory, vol. 37, no. 2, pp. 343-345, 1991.

[16] D. Boucher, P. Sole, and F. Ulmer, "Skew constacyclic codes over Galois rings," Advances in Mathematics of Communications, vol. 2, no. 3, pp. 273-292, 2008.

[17] D. Boucher and F. Ulmer, "A note on the dual codes of module skew codes," in Cryptography and Coding, vol. 7089 of Lecture Notes in Computer Science, pp. 230-243, Springer, Berlin, Germany, 2011.

[18] D. Boucher and F. Ulmer, "Self-dual skew codes and factorization of skewpolynomials," Journal of Symbolic Computation, vol. 60, pp. 47-61, 2014.

[19] E. Bannai, M. Harada, T. Ibukiyama, A. Munemasa, and M. Oura, "Type II codes over [F.sub.2] + 11[F.sub.2] and applications to Hermitian modular forms," Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, vol. 73, no. 1, pp. 13-42,2003.

[20] M. M. Al-Ashker, "Simplex codes over the ring [F.sub.2] + u[F.sub.2]," The Arabian Journal for Science and Engineering, Section A: Sciences, vol. 30, no. 24, pp. 277-285, 2005.

[21] W. C. Huffman, "On the decomposition of self-dual codes over [F.sub.2] + u[F.sub.2] with an automorphism of odd prime order," Finite Fields and their Applications, vol. 13, no. 3, pp. 681-712, 2007.

[22] I. Siap, "Linear codes over [F.sub.2] + u[F.sub.2] and their complete weight enumerators," in Codes and Designs, Columbus, OH, 2000, vol. 10 of Ohio State University Mathematical Research Institute Publications, pp. 259-271, De Gruyter, Berlin, Germany, 2002.

[23] A. Bonnecaze and P. Udaya, "Cyclic codes and self-dual codes over [F.sub.2]u[F.sub.2]" IEEE Transactions on Information Theory, vol. 45, no. 4, pp. 1250-1255, 1999.

[24] P. Udaya and A. Bonnecaze, "Decoding of cyclic codes over [F.sub.2] + m[F.sub.2]," IEEE Transactions on Information Theory, vol. 45, no. 6, pp. 2148-2157, 1999.

[25] H. Q. Dinh, "Constacyclic codes of length 2s over Galois extension rings of [BBF.sub.2] + u[BBF.sub.2]" IEEE Transactions on Information Theory, vol. 55, no. 4, pp. 1730-1740, 2009.

[26] S. Jitman, S. Ling, and P. Udomkavanich, "Skew constacyclic codes over finite chain rings," Advances in Mathematics of Communications, vol. 6, no. 1, pp. 39-63, 2012.

[27] V. Pless and W. C. Huffman, Handbook of Coding Theory, Elsevier, Amsterdam, The Netherlands, 1998.

[28] B. R. McDonald, Finite Rings with Identity, Marcel Dekker, New York, NY, USA, 1974.

[29] D. Boucher and F. Ulmer, "Coding with skew polynomial rings," Journal of Symbolic Computation, vol. 44, no. 12, pp. 1644-1656, 2009.

[30] W. Bosma, J. Cannon, and C. Playoust, "The Magma algebra system I: the user language," Journal of Symbolic Computation, vol. 24, no. 3-4, pp. 235-265, 1997.

[31] S. A. Vanstone and P. C. van Oorschot, An Introduction to Error Correcting Codes with Applications, Kluwer Academic, 1989.

[32] H. Q. Dinh and S. R. Lopez-Permouth, "Cyclic and negacyclic codes over finite chain rings," IEEE Transactions on Information Theory, vol. 50, no. 8, pp. 1728-1744, 2004.

[33] M. C. V. Amarra and F. R. Nemenzo, "On (1u)- cyclic codes over [mathematical expression not reproducible]," Applied Mathematics Letters, vol. 21, no. 11, pp. 1129-1133, 2008.

[34] G. H. Norton and A. Salagean, "On the structure of linear and cyclic codes over a finite chain ring," Applicable Algebra in Engineering, Communication and Computing, vol. 10, no. 6, pp. 489-506, 2000.

[35] J. F. Qian, L. N. Zhang, and S. X. Zhu, "(1 + u) constacyclic and cyclic codes over [F.sub.2] + u[F.sub.2] constacyclic and cyclic codes over," Applied Mathematics Letters, vol. 19, no. 8, pp. 820-823, 2006.

[36] R. Sobhani and M. Esmaeili, "Cyclic and negacyclic codes over the Galois ring GR([p.sup.2], m)," Discrete Applied Mathematics, vol. 157, no. 13, pp. 2892-2903, 2009.

[37] Y. Alkhamees, "The determination of the group of automorphisms of a finite chain ring of characteristic p," The Quarterly Journal of Mathematics, vol. 42, no. 1, pp. 387-391,1991.

[38] H. Q. Dinh, "Constacyclic codes of length [p.sup.s] over F[p.sup.m] + wF[p.sup.m]," Journal of Algebra, vol. 324, no. 5, pp. 940-950, 2010.

[39] I. James, "Claude elwood shannon 30 April 1916-24 February 2001," Biographical Memoirs of Fellows of the Royal Society, vol. 55, pp. 257-265, 2009.

[40] C. E. Shannon, A symbolic analysis of relay and switching circuits [M.S. thesis], Massachusetts Institute of Technology, Cambridge, Mass, USA, 1937.

[41] C. Berrou, A. Glavieux, and P. Thitimajshima, "Near Shannon limit error-correcting coding and decoding: turbo-codes," in Proceedings of the IEEE International Conference on Communications, pp. 1064-1070, Geneva, Switzerland, May 1993.

[42] R. G. Gallager, Low Density Parity-Check Codes, MIT Press, Cambridge, Mass, USA, 1963.

Hai Q. Dinh, (1) Bac T. Nguyen, (2,3) and Songsak Sriboonchitta (4)

(1) Department of Mathematical Sciences, Kent State University, 4314 Mahoning Avenue, Warren, OH 44483, USA

(2) Department of Mathematics, Faculty of Science, Mahidol University, Bangkok 10400, Thailand

(3) Department of Basic Science, University of Economics and Business Administration, Thai Nguyen University, Thai Nguyen Province, Vietnam

(4)Faculty of Economics, Chiang Mai University, Chiang Mai, Thailand

Correspondence should be addressed to Hai Q. Dinh; hdinh@kent.edu

Received 5 August 2015; Revised 13 November 2015; Accepted 2 December 2015

Academic Editor: Haipeng Peng

Caption: Figure 1
Table 1: Generating polynomial of skew [THETA]-cyclic codes over
[F.sub.4] with their parameters (n, k, [d.sub.min]), where n [less
than or equal to] 56. This result is given by Boucher et al. [3].

(n, k,         Number   g
[d.sub.min])

(30,16,9)       422     [x.sup.14] + [alpha] [x.sup.13] +
                        [alpha][x.sup.11] + [x.sup.10] + [x.sup.9]
                        + [x.sup.8] + [alpha][x.sup.7] + [x.sup.6]
                        + [alpha][x.sup.5] +
                        [[alpha].sup.2][x.sup.4] +
                        [[alpha].sup.2][x.sup.2] + [alpha]x
                        + [[alpha].sup.2]

(36,20,10)       13     [mathematical expression not reproducible]

(40,16,15)       6      [mathematical expression not reproducible]

(42,23,11)       92     [mathematical expression not reproducible]

(42,17,16)       3      [mathematical expression not reproducible]

(48,25,13)       2      [mathematical expression not reproducible]

(48,19,17)       2      [mathematical expression not reproducible]

(56,30,14)       1      [mathematical expression not reproducible]

Table 2

e(x)                                        S(e(x))

[x.sup.14]                                 [x.sup.7]

[x.sup.13] + [x.sup.14]              [x.sup.6] + [x.sup.7]

[x.sup.12] + [x.sup.14]              [x.sup.5] + [x.sup.7]

[x.sup.11] + [x.sup.14]              [x.sup.4] + [x.sup.7]

[x.sup.10] + [x.sup.14]              [x.sup.3] + [x.sup.7]

[x.sup.10] + [x.sup.14]              [x.sup.3] + [x.sup.7]

[x.sup.9] + [x.sup.14]               [x.sup.2] + [x.sup.7]

[x.sup.8] + [x.sup.14]                   x + [x.sup.7]

[x.sup.7] + [x.sup.14]                   1 + [x.sup.7]

e(x)                                        S(e(x))

[x.sup.6] + [x.sup.14]         [x.sup.3] + [x.sup.5] + [x.sup.6]

[x.sup.5] + [x.sup.14]       [x.sup.2] + [x.sup.4] + [x.sup.5] +
                                     [x.sup.6] + [x.sup.7]

[x.sup.4] + [x.sup.14]      x + [x.sup.3] + [x.sup.4] + [x.sup.5] +
                                           [x.sup.7]

[x.sup.3] + [x.sup.14]     1 + [x.sup.2] + [x.sup.3] + [x.sup.4] +
                                           [x.sup.7]

[x.sup.2] + [x.sup.14]     x + [x.sup.2] + [x.sup.3] + [x.sup.4] +
                                           [x.sup.7]

[x.sup.2] + [x.sup.14]       x + [x.sup.2] + [x.sup.5] + [x.sup.6]

x + [x.sup.14]            1 + x + [x.sup.4] + [x.sup.5] + [x.sup.6] +
                                           [x.sup.7]

1 + [x.sup.14]                     1 + [x.sup.4] + [x.sup.6]

Table 3

                                                    [mathematical
                                                    expression not
c                     [C.sup.[perpendicular to]]    reproducible]

[<0>.sub.1]                  [<1>.sub.1]             [<1>.sub.1]
[<1>.sub.1]                  [<0>.sub.1]             [<0>.sub.1]
[<x + 1>.sub.1]            [<x + 2>.sub.1]         [<x + 2>.sub.1]
[<x + 2>.sub.1]             [<x + 1>.sub.1]        [<x + 1>.sub.1]
[<x + 1 + u>.sub.1]      [<x + 2 + u>.sub.1]     [<x + 2 + 2u>.sub.1]
[<x + 1 + 2u>.sub.1]    [<x + 2 + 2u>.sub.1]     [<x + 2 + u>.sub.1]
[<x + 2 + u>.sub.1]      [<x + 1 + u>.sub.1]     [<x + 1 + 2u>.sub.1]
[<x + 2 + 2u>.sub.1]     [<x +1 + 2u>.sub.1]     [<x + 1 + u>.sub.1]
[<u>.sub.2]                  [<u>.sub.2]             [<u>.sub.2]
[<u(x + 1)>.sub.2]       [<u(x + 2)>.sub.3]       [<u(x + 2)>.sub.3]
[<u(x + 2)>.sub.2]       [<u(x + 1)>.sub.3]       [<u(x + 1)>.sub.3]
[<u, x + 1>.sub.3]       [<u(x + 2)>.sub.2]       [<u(x + 2)>.sub.2]
[<u, x + 2>.sub.3]       [<u(x + 1)>.sub.2]       [<u(x + 1)>.sub.2]

Note that the subscripts 1, 2, and 3 indicate the types of ideals LI-1,
LI-2, and LI-3, respectively.
COPYRIGHT 2016 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Dinh, Hai Q.; Nguyen, Bac T.; Sriboonchitta, Songsak
Publication:Mathematical Problems in Engineering
Date:Jan 1, 2016
Words:16126
Previous Article:Determination of Optimal Opening Scheme for Electromagnetic Loop Networks Based on Fuzzy Analytic Hierarchy Process.
Next Article:DRSCRO: A Metaheuristic Algorithm for Task Scheduling on Heterogeneous Systems.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters