extfieldsofstudy:
Computer Science
Mathematics

text:
List Decoding Algorithm based on Voting in Groebner Bases for General One-Point AG Codes

We generalize the unique decoding algorithm for one-point AG codes over the Miura-Kamiya Cab curves proposed by Lee, Bras-Amor\'os and O'Sullivan (2012) to general one-point AG codes, without any assumption. We also extend their unique decoding algorithm to list decoding, modify it so that it can be used with the Feng-Rao improved code construction, prove equality between its error correcting capability and half the minimum distance lower bound by Andersen and Geil (2008) that has not been done in the original proposal except for one-point Hermitian codes, remove the unnecessary computational steps so that it can run faster, and analyze its computational complexity in terms of multiplications and divisions in the finite field. As a unique decoding algorithm, the proposed one is empirically and theoretically as fast as the BMS algorithm for one-point Hermitian codes. As a list decoding algorithm, extensive experiments suggest that it can be much faster for many moderate size/usual inputs than the algorithm by Beelen and Brander (2010). It should be noted that as a list decoding algorithm the proposed method seems to have exponential worst-case computational complexity while the previous proposals (Beelen and Brander, 2010; Guruswami and Sudan, 1999) have polynomial ones, and that the proposed method is expected to be slower than the previous proposals for very large/special inputs.

Introduction
We consider the list decoding of one-point algebraic geometry (AG) codes. Guruswami and Sudan (1999) proposed the well-known list decoding algorithm for one-point AG codes, which consists of the interpolation step and the factorization step. The interpolation step has large computational complexity and many researchers have proposed faster interpolation steps, see Beelen and Brander (2010, Figure 1).
By modifying the unique decoding algorithm (Lee et al., 2012) for primal onepoint AG codes, we propose another list decoding algorithm based on voting in Gröbner bases whose error correcting capability is higher than Guruswami and Sudan (1999) and whose computational complexity is empirically smaller than Beelen and Brander (2010); Guruswami and Sudan (1999) in many cases that are examined and reported in our computational experiments. It should be noted that as a list decoding algorithm the proposed method seems to have exponential worst-case computational complexity while the previous proposals (Beelen and Brander, 2010;Guruswami and Sudan, 1999) have polynomial ones, and that the proposed method is expected to be slower than the previous proposals for very large/special inputs. A decoding algorithm for primal one-point AG codes was proposed in Matsumoto and Miura (2000c), which was a straightforward adaptation of the original Feng-Rao majority voting for the dual AG codes (Feng and Rao, 1993) to the primal ones. The Feng-Rao majority voting in Matsumoto and Miura (2000c) for one-point primal codes was generalized to multi-point primal codes in Beelen and Høholdt (2008, Section 2.5). The one-point primal codes can also be decoded as multi-point dual codes with majority voting (Beelen, 2007;Duursma et al., 2011;Duursma and Park, 2010), whose faster version was proposed in Sakata and Fujisawa (2011) for the multipoint Hermitian codes. Lee, Bras-Amorós and O'Sullivan (2012) proposed another unique decoding (not list decoding) algorithm for primal codes based on the majority voting inside Gröbner bases. The module used by them (Lee et al., 2012) is a curve theoretic generalization of one used for Reed-Solomon codes in Ali and Kuijper (2011) that is a special case of the module used in Lee and O'Sullivan (2008). An interesting feature in Lee et al. (2012) is that it did not use differentials and residues on curves for its majority voting, while they were used in Beelen and Høholdt (2008); Matsumoto and Miura (2000c). The above studies (Beelen and Høholdt, 2008;Lee et al., 2012;Matsumoto and Miura, 2000c) dealt with the primal codes. We recently proved in Geil et al. (2013) that the errorcorrecting capabilities of Lee et al. (2012); Matsumoto and Miura (2000c) are the same. The earlier papers (Duursma, 1994;Pellikaan, 1993) suggest that central observations in Andersen and Geil (2008); Geil et al. (2013); Matsumoto and Miura (2000c) were known to the Dutch group, which is actually the case (Duursma, 2012). Chen (1999), Elbrønd Jensen et al. (1999) and Bras-Amorós and O'Sullivan

Notation, Preliminaries and the Statement of Problem
Our study heavily relies on the standard form of algebraic curves introduced independently by Geil and Pellikaan (2002) and Miura (1998), which is an enhancement of earlier results (Miura, 1993;Saints and Heegard, 1995). Let F/F q be an algebraic function field of one variable over a finite field F q with q elements. Let g be the genus of F. Fix n + 1 distinct places Q, P 1 , . . . , P n of degree one in F and a nonnegative integer u. We consider the following one-point algebraic geometry (AG) code where ev( f ) = ( f (P 1 ), . . . , f (P n )). The problem considered in this paper is as follows: We use a linear code C u (or its improved version C Γ defined in Eq. (4)). A codeword in C u (or C Γ ) is transmitted, and the receiver receives r ∈ F n q . A list-decoding algorithm with a decoding radius τ finds all the codewords in C u (or C Γ ) whose Hamming distances from r are within τ. Our aim is to propose another list-decoding algorithm based on Gröbner bases and demonstrate its computational complexity in a wide range of examples.
Suppose that the Weierstrass semigroup H(Q) at Q is generated by a 1 , . . . , a t , and choose t elements x 1 , . . . , x t in F whose pole divisors are (x i ) ∞ = a i Q for i = 1, . . . , t. We do not assume that a 1 is the smallest among a 1 , . . . , a t . Without loss of generality we may assume the availability of such x 1 , . . . , x t , because otherwise we cannot find a basis of C u for every u. Then we have that L(∞Q) = ∪ ∞ i=1 L(iQ) is equal to F q [x 1 , . . . , x t ] (Saints and Heegard, 1995). We express L(∞Q) as a residue class ring F q [X 1 , . . . , X t ]/I of the polynomial ring F q [X 1 , . . . , X t ], where X 1 , . . . , X t are transcendental over F q , and I is the kernel of the canonical homomorphism sending X i to x i . Geil and Pellikaan (2002); Miura (1998) identified the following convenient representation of L(∞Q) by using Gröbner basis theory (Buchberger, 1965) (See, for example, a textbook (Adams and Loustaunau, 1994)). The following review is borrowed from Matsumoto and Miura (2000b). Hereafter, we assume that the reader is familiar with the Gröbner basis theory in Adams and Loustaunau (1994).
Example 1 The Klein quartic over F 8 is given by the equation There exists a unique F 8 -rational place Q, namely (0 : 1 : 0), that is a unique pole of v. The numbers 3, 5 and 7 is the minimal generating set of the Weierstrass semigroup at Q. Define three functions Høholdt and Pellikaan (1995, Example 3.7). By Tang (1998, Theorem 4.1) we can see that the standard form of the Klein quartic is given by which is the reduced Gröbner basis with respect to the monomial order ≻. We can see that a 1 = 3, a 2 = 5, and a 3 = 7.
Example 2 Consider the function field This is the third function field in the asymptotically good tower introduced by Garcia and Stichtenoth (1995). Substituting v 2 with u 1 u 2 and v 3 with u 2 u 3 in Eq.
For i = 0, . . . , a 1 − 1, we define b i = min{m ∈ H(Q) | m ≡ i (mod a 1 )}, and L i to be the minimum element (m 1 , . . . , m t ) ∈ N t 0 with respect to ≺ such that a 1 m 1 + · · ·+a t m t = b i . Note that b i 's are the well-known Apéry set (Rosales and García-Sánchez, 2009, Lemmas 2.4 and 2.6) of the numerical semigroup H(Q). Then we have is not the leading monomial of any nonzero polynomial in I with respect to ≺}, and Then Ω 0 is a basis of L(∞Q) as an F q -linear space (Adams and Loustaunau, 1994), two distinct elements in Ω 0 have different pole orders at Q, and Equation (3) shows that L(∞Q) is a free F q [x 1 ]-module with a basis {y 0 , . . . , y a 1 −1 }. Note that the above structured shape of Ω 0 reflects the well-known property of every weighted reverse lexicographic monomial order, see the paragraph preceding to Eisenbud (1995, Proposition 15.12).
Remark 3 For a description of the proposed algorithm, only a 1 , b 1 , . . . , b a 1 −1 , y 1 , . . . , y a 1 −1 are absolutely necessary, and we can remove ϕ s , x 2 , . . . , x t , a 2 , . . . , a t , X 1 , . . . , X t , Y 1 , . . . , Y t from our presentation. However, we retain those notations for the following two reasons: Firstly, because s will be used as the iteration variable and our proposed algorithm will focus on the monomial in Ω 0 whose pole order at Q is s, the notation ϕ s clarifies the relation between s and the monomial in Ω 0 focused in the s-th iteration.
Secondly, the proposed algorithm needs to find the normal form of a function in L(∞Q) that is an F q -linear combination of monomials in Ω 0 . Functions in L(∞Q) are represented by multivariate polynomials over F q . The specific definition of X 1 , . . . , X t and the specific choice of the monomial order in F q [X 1 , . . . , X t ] enable us to compute the normal form just by the standard Gröbner basis division, and make implementation of our proposal easier in practice. Thirdly, Y 1 , . . . , Y t will be used to explain how we count the computational cost. They are necessary to allow readers to reproduce our experimental results presented later in this paper.
Let v Q be the unique valuation in F associated with the place Q. The semigroup (Rosales and García-Sánchez, 2009, Lemma 2.6). By Matsumoto and Miura (2000b, Proposition 3.18), for each nongap s ∈ H(Q) there is a unique monomial x i 1 y j ∈ Ω 0 with 0 ≤ j < a 1 such that −v Q (x i 1 y j ) = s, and let us denote this monomial by ϕ s . Let Γ ⊂ H(Q), and we may consider the one-point codes where · denotes the F q -linear space spanned by ·. Since considering linearly dependent rows in a generator matrix has no merit, we assume where H(Q) = {u ∈ H(Q) | C u C u−1 }. One motivation for considering these codes is that it was shown in Andersen and Geil (2008) how to increase the dimension of the one-point codes without decreasing the lower bound d AG for the minimum distance. The bound d AG (C Γ ) is defined for C Γ as follows (Andersen and Geil, 2008): For s ∈ Γ, let Then d AG (C Γ ) = min{λ(s) | s ∈ Γ}. It is proved in Geil et al. (2011) that d AG gives the same estimate for the minimum distance as the Feng-Rao bound (Feng and Rao, 1993) for one-point dual AG codes when both d AG and the Feng-Rao bound can be applied, that is, when the dual of a one-point code is isometric to a one-point code. Furthermore, it is also proved in Geil et al. (2011) that d AG (C Γ ) can be obtained from the bounds in Beelen (2007); Duursma et al. (2011); Duursma and Park (2010), hence d AG can be understood as a particular case of these bounds (Beelen, 2007;Duursma et al., 2011;Duursma and Park, 2010).

Overall Structure
Suppose that we have a received word r ∈ F n q . We shall modify the unique decoding algorithm proposed by Lee et al. (2012) so that we can find all the codewords in C Γ in Eq. (4) within the Hamming distance τ from r. τ is a parameter independent of r, and τ is chosen before reception of r. The overall structure of the modified algorithm is as follows: 1. Precomputation before getting a received word r, 2. Initialization after getting a received word r, 3. Termination criteria of the iteration, and 4. Main part of the iteration.
Steps 2 and 4 are based on Lee et al. (2012). Steps 1 and 3 are not given in Lee et al. (2012). Each step is described in the following subsections in Section 3. We shall analyze time complexity except the precomputation part of the algorithm.

Modified Definitions for the Proposed Modification
We retain notations from Section 2. In this subsection, we modify notations and definitions in Lee et al. (2012) to describe the proposed modification to their algorithm. We also introduce several new notations. Define a set Our Ω 1 is Ω in Lee et al. (2012). Recall also that Since the F q [x 1 ]-module L(∞Q)z ⊕ L(∞Q) has a free basis {y j z, y j | 0 ≤ j < a 1 }, we can regard Ω 1 as the set of monomials in the Gröbner basis theory for modules. We introduce a monomial order on Ω 1 as follows. For given two monomials x i 1 1 y j z i t+1 and x i ′ 1 1 y j ′ z i ′ t+1 , first rewrite y j and y j ′ by x 2 , . . . , x t defined in Section 2 and get Observe that the restriction of < s to Ω 0 is equal to ≺ defined in Section 2. In what follows, every Gröbner basis, leading term, and leading coefficient is obtained by considering the Gröbner basis theory for modules, not for ideals.
For f ∈ L(∞Q)z ⊕ L(∞Q), γ( f ) denotes the number of nonzero terms in f when f is expressed as an F q -linear combination of monomials in Ω 1 . γ 1 ( f ) denotes the number of nonzero terms whose coefficients are not 1 ∈ F q .
For each (i, j), express y i y j as an F q -linear combination of monomials in Ω 0 . Such expressions will be used for computing products and quotients in L(∞Q) as explained in Section 3.4.1. From the above data, we can easily know lc(y i y j ), which will be used in Eqs. (14) and (22).
Find elements ϕ s ∈ Ω 0 with s ∈ H(Q). There are n such elements, which we denote by ψ 1 , .

Multiplication and Division in an Affine Coordinate Ring
In both of the original unique decoding algorithm (Lee et al., 2012) and our modified version, we need to quickly compute the product gh of two elements g, h in the affine coordinate ring L(∞Q). In our modified version, we also need to compute the quotient g/h depending on the choice of iteration termination criterion described in Section 3.6. Since the authors could not find quick computational procedures for those tasks in L(∞Q), we shall present such ones here.

Multiplication in an Affine Coordinate Ring
The normal form of g, for g ∈ L(∞Q), is the expression of g written as an F q -linear combination of monomials ϕ s ∈ Ω 0 . g, h are assumed to be in the normal form. We propose the following procedure to compute the normal form of gh. Let the normal form of y i y j be , which is computed in Section 3.3. We denote by X 1 , Y 1 , . . . , Y a 1 −1 algebraically independent variables over F q .
1. Assume that g and h are in their normal forms. Change y i to Y i and x 1 to X 1 in g, h for i = 1, . . . , a 1 − 1. Recall that y 0 = 1. Denote the results by G, H.
2. Compute GH. This step needs Therefore, the total number of multiplications in F q is at most Define Eq. (11) as multi(g, h). We emphasize that when the characteristic of F q is 2 and all the coefficients of defining equations belong to F 2 , which is almost always the case for those cases of interest for applications in coding theory, then γ 1 ( a 1 −1 k=0 y k f i, j,k (x 1 )) in Eq. (11) is zero. This means that L(∞Q) has little additional overhead over F q [X] for computing products of their elements in terms of the number of F q -multiplications and divisions.

Remark 5 Define
The right hand side of Eq. (9) can be written as By using Eq. (12) instead of Eq. (9), we have another upper bound on the number of multiplications as we have Eq. (13) ≤ Eq. (11). However, Eq. (13) is almost always the same as Eq.
(11) over the curve in Example 2, and Eq. (13) will not be used in our computer experiments in Section 5.

Computation of the Quotient
Assume h 0. The following procedure computes the quotient g/h ∈ L(∞Q) or declares that g does not belong to the principal ideal of L(∞Q) generated by h.
If not, declare that g does not belong to the principal ideal of L(∞Q) generated by h, and finish the procedure.
Computation of tϕ s needs one multiplication and one division in

Compute the normal form of tϕ s h, which requires at most multi(tϕ
5. Update σ ← σ + tϕ s and g ← g − tϕ s h. If the updated g is zero, then output the updated σ as the quotient and finish the procedure. Otherwise go to Step 2. This step has no multiplication nor division. Define quot(g, h) as ζ after finishing the above procedure. quot(g, h) is an upper bound on the number of multiplications and divisions in F q in the above procedure. The program variable ζ is just to define quot(g, h), and the decoding algorithm does not need to update ζ. Observe also that the above procedure is a straightforward generalization of the standard long division of two univariate polynomials (McKeague, 2012).

Initialization after Getting a Received Word r
Therefore, the total number of multiplications in the initialization is at most Let s = N and execute the following steps.

Three Termination Criteria of the Iteration
After finishing the initialization step in Section 3.5, we iteratively compute f (s) i and from larger s to smaller s. The single iteration consists of two parts: The first part is to check if an iteration termination criterion is satisfied. The second part is computation of f (s) We describe the first part in Section 3.6. Let In the following subsections, we shall propose three different procedures to judge whether or not iterations in the proposed algorithm can be terminated. In an actual implementation of the proposed algorithm, one criterion is chosen and the chosen one is consistently used throughout the iterations. The first one and the second one are different generalizations of Ali and Kuijper (2011, Theorem 12) from the case g = 0 to g > 0. Ali and Kuijper (2011, Theorem 12) proved that if the number δ of errors satisfies 2δ < d RS (C s ), where d RS (C s ) is the minimum distance n − s of the [n, s+1] Reed-Solomon code C s , then the transmitted information word is obtained by Ali-Kuijper's algorithm as −α 0 /α 1 . To one-point primal AG codes, d RS (C s ) can be generalized as either d AG (C s ) or n − s − g. The former generalization d AG (C s ) corresponds to the first criterion in Section 3.6.1 and the latter n − s − g corresponds to the second in Section 3.6.2.
The third one is almost the same as the original procedure in Lee et al. (2012). The first one was proposed in Geil et al. (2012) while the second and the third ones are new in this paper. We shall compare the three criteria in Section 5.2. Throughout this paper, wt( x) denotes the Hamming weight of a vector x ∈ F n q . The proposed decoding algorithm can perform both unique decoding and list decoding depending on whether or not d AG (C Γ (≤s) ) > 2τ. To provide a unified presentation of both variants of our proposal, we will include the condition d AG (C Γ (≤s) ) > 2τ in the following. Observe that the condition d AG (C Γ (≤s) ) > 2τ can be checked when one implements our proposal by an electronic circuit or a computer software, before executing the proposed algorithm.

If
• s ∈ Γ, • d AG (C Γ (≤s) ) > 2τ, and then do the following: multiplications and divisions in F q .
2. If α 0 /α 1 ∈ L(∞Q) and α 0 /α 1 can be written as a linear combination of monomials in {ϕ s ′ ∈ s ′ ∈ Γ (≤s) }, then do the following: into the list of transmitted information vectors, and avoid proceeding with the rest of the decoding procedure. When Γ (>s) = ∅, the summation over Γ (>s) is regarded as zero.
then include the coefficients of −α 0 /α 1 + s ′ ∈Γ (>s) w s ′ ϕ s ′ into the list of transmitted information vectors, and avoid proceeding with s. Otherwise, continue the iterations unless s < n − g − 2τ.
. This needs at most multiplications and divisions in F q .
5. Finish the iteration no matter what happened in the above steps.

Third Criterion for Judging Termination
The third criterion terminates the algorithm when it finds f (s) i at s = −1 for i = 0, . . . , a 1 − 1 in the main iteration presented in Section 3.7. If 2τ < d AG (C Γ ) then declare the vector (w s : s ∈ Γ) as the only transmitted information and finish.
If 2τ ≥ d AG (C Γ ) then do the following: 1. If α 0 = 0 and −v Q (α 1 ) ≤ τ then include the vector (w s : s ∈ Γ) into the list of transmitted information vectors. Finish the iteration.
3. Otherwise compute ev( s∈Γ w s ϕ s ). This needs at most multiplications and divisions in F q .
then include the vector (w s : s ∈ Γ) into the list of transmitted information vectors. Finish the iteration.

Iteration of Pairing, Voting, and Rebasing
The iteration of the original algorithm (Lee et al., 2012) consists of three steps, called pairing, voting, and rebasing. We will make a small change to the original. Our modified version is described below.

Pairing
Let and let ν (s) i = lc(d i,i ). We assume that lt( f (s) i ) = a i,i y i z and lt(g (s) i ) = d i,i y i . For 0 ≤ i < a 1 , as in Lee et al. (2012) there are unique integers 0 ≤ i ′ < a 1 and k i satisfying Note that by the definition above

Voting
For each i ∈ {0, . . . a 1 − 1}, we set where We remark that the leading coefficient µ i must be considered after expressing a i,i y i ϕ s by monomials in Ω 0 .
Observe that lc(y i ϕ s ) = lc(y i y s mod a 1 ) and that lc(y i y s mod a 1 ) is already precomputed as Section 3.3. By using that precomputed table, computation of µ i needs one multiplication. The total number of multiplications and divisions in Eq. (22) is 2a 1 excluding negation from the number of multiplication. Let We consider two different candidates depending on whether s ∈ Γ or not: • If s ∈ Γ, let w be one of the element(s) in F q with Let w s = w. If several w's satisfy the condition above, repeat the rest of the algorithm for each of them.

Rebasing
In all of the following cases, we need to compute the normal form of the product wϕ s × a 1 −1 j=0 a i, j y j , and the product wϕ s × a 1 −1 j=0 c i, j y j . For each i, the number of multiplications is ≤ multi(wϕ s , where multi(·, ·) is defined in Section 3.4.1.
• If w s,i = w, then let where the parentheses denote substitution of the variable z and let ν The number of multiplications in this case is bounded by Eq. (27).
• If w s,i w and c i > 0, then let Computation of needs one multiplication and one division. The product of and g (s) i ′ (z + wϕ s ) needs γ(g (s) i ′ (z + wϕ s )) multiplications, where γ is defined in Section 3.4.1. Thus, the number of multiplications and divisions is • If w s,i w and c i ≤ 0, then let needs one multiplication and one division. The product of where γ is defined in Section 3.4.1. Thus, the number of multiplications and divisions is ≤ Eq. (28).
After computing f (prec(s)) i and g (prec(s)) i as above, update the program variable s to prec(s) and return to the beginning of Section 3.6, that is, return to the step of the chosen termination criterion.

Difference to the Original Method
In this subsection, we review advantages of our modified algorithm over the original (Lee et al., 2012).
• Our version can handle any one-point primal AG codes, while the original can handle codes only coming from the C ab curves (Miura, 1993). This generalization is enabled only by replacing y j in Lee et al. (2012) by y j defined in Section 2.
• Our version can find all the codewords within Hamming distance τ from the received word r, while the original is a unique decoding algorithm.
• Our version does not compute f (s) i , g (s) i for a Weiestrass gap s H(Q), while the original computes them for N ≥ s H(Q).
• The original algorithm assumed u < n, where u is as defined in Eq. (1).
This assumption is replaced by another less restrictive assumption (5) in our version.
• Our version supports the Feng-Rao improved code construction (Feng and Rao, 1995), while the original does not. This extension is made possible by the change at Eq. (25).
• The first and the second termination criteria come from Ali and Kuijper (2011, Theorem 12) and do not exist in the original (Lee et al., 2012).
• The third termination criterion is essentially the same as the original (Lee et al., 2012), but examination of the Hamming distance between the decoded codeword and r is added when 2τ ≥ d AG (C Γ ).
• The original (Lee et al., 2012) is suitable for parallel implementation on electric circuit similar to the Kötter architecture (Kötter, 1998). Our modified version retains this advantage.
We use C u with u = 4 for decoding. Then Γ = {0, 2, 3, 4} and d AG (C Γ ) = 4. We shall try to correct τ = 2 errors. Suppose that 0 was transmitted and r = (0, 0, 1, 1, 0, 0, 0, 0) was received. This received word r has four codewords within Hamming distance 2, and all of them are found by the proposed decoding algorithm. We shall show how one of the four codeword is found.
According to Section 3.5, we have h r = u 3 + u 2 + u, which implies N = −v Q (h r ) = 6. We start the iteration from s = 6(= N), and again according to Section 3.5 we have At the iteration for s = 6 none of the temination criteria is satisfied. Since 6 Γ, we do not need voting and set w 6 = 0, and we compute new polynomials as At the iteration for s = 5 none of the temination criteria is satisfied. Since 5 Γ, we do not need voting and set w 5 = 0, and we compute new polynomials as At the iteration for s = 4 none of the temination criteria is satisfied. We need voting at s = 4, and all the candidates 0, 1, β, β 2 in F 4 get zero vote. Therefore, the execution of the proposed algorithm splits to four branches at s = 4. Firstly we consider the choice w 4 = 1, which will result in an incorrect decoding.
The choice w 4 = 1 gives At the iteration for s = 3 only the first temination criterion is satisfied. We have α 0 = u 2 + u and α 1 = u, and the decoded codeword by the first criterion is (1, 1, 1, 1, 0, 0, 0, 0) which is at the Hamming distance 2 from r but not equal to the transmitted codeword.
The second or the third termination criterion is not satisfied. In the voting for s = 3, w 3 = 0 is chosen with two votes while other candidates get zero vote. The choice w 3 = 0 gives 1 .
At the iteration for s = 2 the second temination criterion is satisfied. The computation process and the decoded codeword by the second criterion at s = 2 are the same as those by first criterion at s = 3.
In the voting for s = 2, w 2 = 0 is chosen with two votes while other candidates get zero vote. The choice w 2 = 0 gives 1 .
In the voting for s = 1, w 1 = 1 is chosen with two votes while other candidates get zero vote. The choice w 1 = 0 gives In the voting for s = 0, w 0 = 1 is chosen with four votes while other candidates get zero vote. The choice w 0 = 1 gives At s = −1, we find α 0 = 0, α 1 = u and 2 = −v Q (α 1 ) ≤ τ = 2. Thus the algorithm outputs (w s ) s∈Γ as decoded information by the third termination criterion. The decoded codeword is again (1, 1, 1, 1, 0, 0, 0, 0). The three termination criterion give the same decoded codeword, but their numbers of iterations are different.
Recall that all of candidates w 4 = 0, 1, β, β 2 are chosen by voting at s = 4 because all the candidates have the same number of votes. Only w 4 = 0 gives the correct codeword, while w 4 = β and w 4 = β 2 give two other different incorrect codewords whose Hamming distances are both 2 from r. In this example, multiple candidates are chosen only at s = 4.

Theoretical Analysis of the Proposed Modification
In this section we prove that our modified algorithm can find all the codewords within Hamming distance τ from the received word r. We also give upper bounds on the number of iterations in Section 4.6.

Supporting Lemmas
In Section 4.1 we shall introduce several lemmas necessary in Sections 4.2-4.5. Recall that the execution of our modified algorithm can branch when there are multiple candidates satisfying the condition (26). For a fixed sequence of determined w s , define r (N) = r and recursively define r (prec(s)) = r (s) − ev(w s ϕ s ). By definition r (−1) = r − ev( s∈Γ w s ϕ s ).
The following lemma explains why the authors include "Gröbner bases" in the paper title. The module I r (N) where r (s) = (r (s) 1 , . . . , r (s) n ) . The following proposition shows that the original decoding algorithm Lee et al. (2012) can correct errors up to half the bound d AG (C Γ ), which was not claimed in Lee et al. (2012).

Proof. Let
where the third equality holds by Eq. (21). By the equalities above, we see which proves the equality ν(s) = λ(s). Lee et al. (2012) showed that their original decoding algorithm can correct up to ⌊(d LBAO (C u ) − 1)/2⌋ errors, where d LBAO (C u ) = min{ν(s) | s ∈ H(Q), s ≤ u}. Proposition 7 implies that d LBAO (C u ) is equivalent to d AG (C u ) for every one-point primal code C u , and therefore Andersen and Geil (2008, Theorem 8) implies Lee et al. (2012, Proposition 12). In another recent paper Geil et al. (2013) we proved that d AG and d LBAO are equal to the Feng-Rao bound as defined in Beelen and Høholdt (2008); Matsumoto and Miura (2000c) for C u .

Lower Bound for the Number of Votes
In Section 4.2 we discuss the number of votes (26) which a candidate w s,i receives. Since we study list decoding, we cannot assume the original transmitted codeword nor the error vector as in Lee et al. (2012). Nevertheless, the original theorems in Lee et al. (2012) allow natural generalizations to the list decoding context.  Matsumoto and Miura (2000a)).
Let {ǫ 0 , . . . , ǫ a 1 −1 } be a Gröbner basis for J e as an F q [x 1 ]-module with respect to < s (for any integer s), such that lm(ǫ j ) = x k j 1 y j . Under the above notations, we have for i with w s,i ω s , and for i with w s,i = ω s .
Proof. The proof is the same as those of Lee et al. (2012, Propositions 7 and 8), with replacing y j in Lee et al. (2012) by y j , δ(·) in Lee et al. (2012) The following lemma is a modification to Lee et al. (2012, Proposition 9) for the list decoding.

Lemma 9
We retain notations from Lemma 8. We have

Now we have a chain of inequalities
where at Eq. (30) we used the equality shown in Lee et al. (2012, Lemma 2 and Eq. (1)). Finally note that by Lee et al. (2012, Eq. ( 3)).
The following lemma is a modification to Lee et al. (2012, Proposition 10) for list decoding, and provides a lower bound for the number of votes (26) received by any candidate ω s ∈ F q , as indicated in the section title.

Correctness of the Modified List Decoding Algorithm with the Third Iteration Termination Criterion
In this subsection and the following sections, we shall prove that the proposed list decoding algorithm will find all the codewords within the Hamming distance τ from the received word r. Since the third iteration termination criterion is the easiest to analyze, we start with the third one. Fix a sequence w s for s ∈ Γ. If wt( r − ev( s∈Γ w s ϕ s )) ≤ τ then the sequence w s is found by the algorithm because of Proposition 10. When 2τ < d AG (C Γ ), by Proposition 7 the decoding is not list decoding, and the algorithm just declares the sequence w s as the transmitted information.
On the other hand, if 2τ ≥ d AG (C Γ ), then the found sequence could correspond to a codeword more distant than Hamming distance τ, and the algorithm examines the Hamming distance between the found codeword and the received word r.
Since computing ev( f ) for f ∈ L(∞Q) needs many multiplications in F q , the algorithm checks some sufficient conditions to decide the Hamming distance between the found codeword and the received word r. Let r (−1) = (r (−1) 1 , . . . , r (−1) n ). When α 0 = 0 in Section 3.6.3, by Lemma 6, we have because Eq. (29) and α 0 = 0 implies that v P i (α 1 ) ≥ 1 for r (−1) i 0. By the above equation, −v Q (α 1 ) ≤ τ implies that the found codeword is within Hamming distance τ from r. This explains why the algorithm can avoid computation of the evaluation map ev in Step 1 in Section 3.6.3.
In order to explain Step 2 in Section 3.6.3, we shall show that the condition of Step 2 in Section 3.6.3 implies that wt( r − ev( s∈Γ w s ϕ s )) > τ. Suppose that wt( r − ev( s∈Γ w s ϕ s )) ≤ τ. Then there exists β 1 ∈ L(∞Q) such that v P i (β) ≥ 1 for r (−1) i 0, −v Q (β) ≤ τ + g, and β 1 z ∈ I r (−1) . Because the leading term of β 1 z must be divisible by lt( f (−1) i ) for some i by the property of Gröbner bases, we must have −v Q (α 1 ) ≤ −v Q (β 1 ). This explains why the algorithm can avoid computation of the evaluation map ev in Step 2 in Section 3.6.3.
Otherwise, the algorithm computes the Hamming distance between the found codeword and r in Steps 3 and 4 in Section 3.6.3.

Correctness of the Modified List Decoding Algorithm with the Second Iteration Termination Criterion
We shall explain why the second criterion in Section 3.6.2 correctly finds the required codewords. For explanation, we present slightly rephrased version of facts in Beelen and Høholdt (2008).
i , and assume that g has the minimum pole order at Q among such elements in L(∞Q). Then −v Q (g) ≤ τ + g. One has that gz − f g ∈ I r (s) and lt(gz − f g) = lt(gz) with respect to < s . By the property of Gröbner bases, lt(gz) is divisible by lt We explain how the procedure in Section 3.6.2 works as desired. When the condition in Step 1 in Section 3.6.2 is true, then there cannot be a codeword within Hamming distance τ from r (s) by the same reason as Section 4.3. So the algorithm stops processing with r (s) .
When 2τ ≥ d AG (C Γ ), then the algorithm examines the found codeword close enough to r in Steps 4a and 4b in Section 3.6.2. When −v Q (α 1 ) ≤ τ we can avoid computation of the evaluation map ev by the same reason as Section 4.3, which is checked at Step 4a. Otherwise we compute the codeword vector at Step 4b and examine its Hamming distance to r (s) .

Correctness of the Modified List Decoding Algorithm with the First Iteration Termination Criterion
We shall explain why the first criterion in Section 3.6.1 correctly finds the required codewords. The idea behind the first criterion is that there cannot be another codeword within Hamming distance τ from r (s) when the algorithm already found one. So the algorithm can stop iteration with smaller s once a codeword is found as ev(−α 0 /α 1 + s ′ ∈Γ (>s) w s ′ ϕ s ′ ). The algorithm does not examine conditions when −v Q (α 1 ) > τ + g by the same reason as Sections 4.3 and 4.4. When 2τ < d AG (C Γ ), then the algorithm declares −α 0 /α 1 + s ′ ∈Γ (>s) w s ′ ϕ s ′ as the unique codeword.
When 2τ ≥ d AG (C Γ ), then the algorithm examines the found codeword close enough to r in Steps 2a-2c in Section 3.6.1. When −v Q (α 1 ) ≤ τ we can avoid computation of the evaluation map ev by the same reason as Section 4.3, which is checked at Step 2a.

Upper Bound on the Number of Iterations and the Worst Case Complexity
Observe that for s > max Γ we set always w s to 0. For each s ∈ Γ satisfying ν(s) ≤ 2τ, the number of accepted candidates satisfying Eq. (26) can be at most q.
On the other hand, for s with ν(s) > 2τ, the number of candidates is either zero or one, because at most one w ∈ F q can satisfy Eq. (26). Therefore, we have upper bounds for the number of iterations, counting executions of Rebasing in Section 3.7.3, as for the third criterion for judging termination, where exp q (x) = q x , and for the first and the second criteria for judging termination. We will use max H(Q) in place of N in Eqs. (31) and (32) for computation in Tables 1-4, because N depents on r and N ≤ max H(Q). The proposed algorithm processes 2a 1 polynomials (elements in L(∞Q)) in each iteration and each polynomial has O(n) terms. For a precise closed-form evaluation of Eqs. (31) and (32), we need a closed-form upper bound of ♯{s ∈ Γ | ν(s) ≤ 2τ} in terms of τ, but the authors could not find such one. Clearly n is an upper bound on ♯{s ∈ Γ | ν(s) ≤ 2τ}, and the number of iterations is O(exp q (n)). Therefore the worst-case complexity is O(a 1 n exp q (n)). Nonetheless, we will see that the actual computational cost can be lower than the existing list decoding algorithms in some cases in Section 5. We remark that when τ < d AG (C Γ ) the number of iterations is ≤ n and the worst case complexity is O(a 1 n 2 ) because the number of chosen candidate is at most one by voting at each iteration, and that the complexity O(a 1 n 2 ) is the same as the BMS algorithm (Sakata et al., 1995a,b).
Observe that the list decoding can be implemented as exp q (♯{s ∈ Γ | ν(s) ≤ 2τ}) parallel execution of the unique decoding. Therefore, when one can afford exp q (♯{s ∈ Γ | ν(s) ≤ 2τ}) parallel implementation, which increases the circuit size, the decoding time of list decoding is the same as that of the unique decoding.

Simulation Condition and Results
We have provided an upper bound on the number of multiplications and divisions at each step of the proposed algorithm. We simulated 1, 000 transmissions of codewords with the one-point primal codes on Klein quartic over F 8 with n = 23 by using Examples 1 and 4, the one-point Hermitian codes over F 16 with n = 64, and the one-point primal codes on the curve in Example 2 over F 9 with n = 77.
The program is implemented on the Singular computer algebra system (Decker et al., 2011). The program used for this simulation is available from http://arxiv.org/src/1203.6127v5/anc.
In  (27) and (28), and the number of codewords found. Note also that Eq. (11) instead of Eq. (13) is used.
The parameter τ is set to the same as the number of generated errors in each simulation condition. N or R in the number of errors in Tables 2 and 3 indicates that the error vector is generated toward another codeword nearest from the transmitted codeword or completely randomly, respectively. The distribution of codewords is uniform on C Γ . That of error vectors is uniform on the vectors of Hamming weight τ.
In the code construction, we always try to use the Feng-Rao improved construction. Specifically, for a given designed distance δ, we choose Γ = {s ∈ H(Q) | λ(s) = ν(s) ≥ δ}, and construct C Γ of Eq. (4). In the following, the designed distance is denoted by d AG (C Γ ). It can be seen from Tables 1-4 and the following subsections that the computational complexity of the proposed algorithm tends to explode when the number of errors exceeds the error-correcting capability of the Guruswami-Sudan algorithm (Guruswami and Sudan, 1999).

Comparison among the Three Proposed Termination Criteria
In Section 3.6 we proposed three criteria for terminating iteration of the proposed algorithm. From Tables 1-4, one can see the following. The first criterion has the smallest number of iterations, and the second is the second smallest. On the other hand, the first criterion has the largest number of multiplications and divisions.    The second and the third have the similar numbers. Only the first criterion was proposed in Geil et al. (2012) and we see that the new criteria are better than the old one. The reason is as follows: The computation of quotient α 0 /α 1 at Step 1 in Section 3.6.1 is costlier than updating f (s) i and g (s) i in Section 3.7.3 and the first criterion computes α 0 /α 1 many times, which cancels the effect of decrease in the number of iterations. On the other hand, the second criterion computes α 0 /α 1 only once, so it has the smaller number of multiplications and divisions than the first.
The second criterion is faster when 2τ < d AG (C Γ ), while the third tends to be faster when 2τ ≥ d AG (C Γ ). In addition to this, the ratio of the number of iterations in the second criterion to that of the third is smaller with 2τ < d AG (C Γ ) than with 2τ ≥ d AG (C Γ ). We speculate the reason behind them as follows: When 2τ ≥ d AG (C Γ ) and a wrong candidate is chosen at Eq. (26), after several iterations of Sections 3.6 and 3.7, we often observe in our simulation that no candidate satisfies Eq. (26) and the iteration stops automatically. Under such situation, the second criterion does not help much to decrease the number of iterations nor the computational complexity when a wrong candidate is chosen at Eq. (26), and there are many occasions at which a wrong candidate is chosen at Eq. (26) when 2τ ≥ d AG (C Γ ). On the other hand, when 2τ < d AG (C Γ ), the second criterion helps to determine the transmitted information earlier than the third.

Tightness of Upper Bounds (31) and (32)
In Table 4, we observe that the upper bounds (31) and (32) are much larger than the actual number of iterations for τ = 5. The disappearance of candidates satisfying Eq. (26) in the last paragraph may also explain the reason behind the large differences for τ = 5.

Klein
The code is C u with u = 20, dim C u = 18. There is no previously known algorithm that can handle this case. 5.6 Klein Quartic, (d AG (C Γ ), τ) = (10, 5) The code is C u with u = 13, dim C u = 11. According to Beelen and Brander (2010, Figure 1), we can use the original Guruswami-Sudan (Guruswami and Sudan, 1999) but it seems that its faster variants cannot be used. We need multiplicity 7 to correct 5 errors. We have to solve a system of 23(7 + 1)7/2 = 644 linear equations. It takes 644 3 /3 = 89, 029, 994 multiplications in F 8 . The proposed algorithm is much faster. 5.7 Klein Quartic, (d AG (C Γ ), τ) = (10, 6) The code is C u with u = 13, dim C u = 11. There is no previously known algorithm that can handle this case. 5.8 Hermitian, (d AG (C Γ ), τ) = (6, 2) or (20,9) We can use the BMS algorithm (Sakata et al., 1995a,b) for this case. The complexity of Sakata et al. (1995a,b) is estimated as O(a 1 n 2 ) and a 1 n 2 = 24, 576. The complexity of the proposed algorithm seems comparable to Sakata et al. (1995a,b). However, we are not sure which one is faster.

5.9
Hermitian, (d AG (C Γ ), τ) = (6, 3) or (6, 4) The code becomes the Feng-Rao improved code with designed distance 6. Its dimension is 55. In order to have the same dimension by C u we have to set u = 60, whose AG bound (Andersen and Geil, 2008) is 4 and the Guruwsami-Sudan can correct up to 2 errors. The proposed algorithm finds all codewords in the improved code with 3 and 4 errors.

5.10
Hermitian, (d AG (C Γ ), τ) = (20, 10) The code is C u with u = 44. The required multiplicity is 11, and the required designed list size is 14. The fastest algorithm for the interpolation step seems Beelen and Brander (2010). Beelen and Brander (2010, Example 4) estimates the complexity of their algorithm as O(λ 5 n 2 (log λn) 2 log(log λn)), where λ is the designed list size. Ignoring the log factor and assuming the scaling factor one in the big-O notation, the number of multiplications and divisions is λ 5 n 2 = 2, 202, 927, 104. The proposed algorithm needs much fewer number of multiplications and divisions in F 16 .

5.12
Garcia-Stichtenoth (Example 2), (d AG (C Γ ), τ) = (6, 2), (10, 4), or (20,9) We can use Beelen (2007); Beelen and Høholdt (2008); Duursma et al. (2011); Duursma and Park (2010); Matsumoto and Miura (2000c) to decode this set of parameters. It is essentially the forward elimination in the Gaussian elimination, and it takes roughly n 3 /3 multiplications. In this case n 3 /3 = 152, 177. The proposed algorithm has the lower complexity than Beelen (2007) This is a Feng-Rao improved code with dimension 58. In order to realize a code with the same dimension, we have to set u = 79 in C u . The Guruswami-Sudan algorithm (Guruswami and Sudan, 1999) can correct no error in this set of parameters. There seems no previously known algorithm that can handle this case.
5.14 Garcia-Stichtenoth (Example 2), (d AG (C Γ ), τ) = (10, 5) This is a Feng-Rao improved code with dimension 52. In order to realize a code with the same dimension, we have to set u = 73 in C u . The Guruswami-Sudan algorithm (Guruswami and Sudan, 1999) can correct 2 errors in this set of parameters. There seems no previously known algorithm that can handle this case.

Conclusion
In this paper, we modified the unique decoding algorithm for plane AG codes in Lee et al. (2012) so that it can support one-point AG codes on any curve, and so that it can do the list decoding. The error correction capability of the original (Lee et al., 2012) and our modified algorithms are also expressed in terms of the minimum distance lower bound in Andersen and Geil (2008). We also proposed procedures to compute products and quotients in coordinate ring of affine algebraic curves, and by using those procedures we demonstrated that the modified decoding algorithm can be executed quickly. Specifically, its computational complexity is theoretically the same as the BMS algorithm (Sakata et al., 1995a,b) for one-point Hermitian codes. It is also much faster than the standard list decoding algorithms (Beelen and Brander, 2010;Guruswami and Sudan, 1999) for many cases that are examined and reported in our computational experiments in which examined error-correcting codes have midium sizes. It should be noted that as a list decoding algorithm the proposed method seems to have exponential worstcase computational complexity while the previous proposals (Beelen and Brander, 2010;Guruswami and Sudan, 1999) have polynomial ones, and that the proposed method is expected to be slower than the previous proposal for very large/special inputs.
The original decoding algorithm (Lee et al., 2012) allows parallel implementation on circuits like the Kötter architecture (Kötter, 1998). Our modified algorithm retains this advantage. Moreover, if one can afford large circuit size, the proposed list decoding algorithm can be executed as quickly as the unique decoding algorithm by parallel implementation on a circuit.
the Villum Foundation through their VELUX Visiting Professor Programme 2011-


extfieldsofstudy:
Materials Science
Physics
Medicine

text:
Analytical and numerical study of particles with binary adsorption

Electro-oxidation of ethanol represents a key process in fuel-cells technology. We introduce a generalization of the random sequential adsorption model to study the long timescale and large length scale properties of the electro-oxidation process. We provide an analytical solution for one dimension and Monte Carlo results in two dimensions. We characterize the coverage and percolation properties of the jammed state and unveil the influence of quenched impurities in the selectivity of oxidation products.

I. INTRODUCTION
Ethanol has been considered for fuel cells given its low toxicity and abundance [1]. The electro-oxidation of ethanol on the surface of catalysts can follow multiple reaction pathways leading to several different products, which are strongly affected by, e.g., concentration, presence of impurities, and temperature. In this work, we introduce a model, inspired on the random sequential adsorption model (RSA) of dimers, to analyze properties of the oxidation process such as their dependence on the binding configuration, binding rates, and reaction pathway probabilities.
Ethanol electro-oxidation has recently been studied through density function theory [2,3], providing possible reaction pathways for the adsorption and catalysis of ethanol. However, the time-dependence of the coverage based on the various reaction pathways would become computationally prohibitive using density functional theory. Nonetheless, in the limit of low mobility of bound reaction products, large systems sizes, and long timescales a study based on the adoption of a square lattice to represent the (100) substrate for the various reaction products becomes appropriate. In this limit, ethanol electrooxidation can be described as adsorption of a dimer on the substrate, thus occupying two adjacent lattice sites, as it cleaves [2,3] or, in the presence of neighboring preadsorbed species, adsorb as a monomer. A key feature of the model is to provide a configuration dependent rule for the landing site and study the influence on the adsorption rates of the oxidation process. We also study the influence of immobile impurities and understand their role in achieving selectivity of adsorbed species. Our model can also be extended to analyze other cleavage mechanisms like, e.g., the one of sugars [4].
In this paper, we study the model above delineated both in one and two dimensions. In the one-dimensional study, we were able to establish a closed hierarchy of rate equations for which we could obtain exact, closed form solutions. To complement and extend the insight provided by this approach, we also performed a Monte Carlo based study for the relevant two-dimensional case.
The paper is organized as follows: in the next section we introduce the model, while in Section III an analytical derivation is exactly solved in three specific limits. Monte Carlo simulations extend the one-dimensional results to the more realistic case of a substrate as described in section IV with results provided in section V for substrates with and without impurities. Final remarks are presented in section VI.

II. MODEL
Ethanol oxidation is of great relevance to the society, since each molecule releases twice as much energy as one methanol molecule [29], posing it as a candidate to replace several sources of energy [30]. Recently, Wang and Liu [2] proposed a mechanism for ethanol electrooxidation on Pt(100) and Pt(111) substrates, which can be summarized in three pathways [3] FIG. 1. Schematic representation of the adsorption rules (1). The A-species (red) can deposit either as dimers, on two empty sites, yielding B-products (blue), or as monomers, on one empty site with at least one occupied neighbor, yielding C-products (green). In the ethanol oxidation, A is the ethanol, B stands for the two products (CH and CO), and C the acetyl.
3. The concerted path where the ethanol molecule looses two hydrogens followed by the desorption of acetaldehyde.
Wang and Liu have shown that for the Pt(100) surface (which can be mapped onto a square lattice) the relevant pathway is mainly the CH path [2], where ethanol adsorption leads to the formation of acetyl (CH 3 CO). The work of Wang and Liu [2] discloses that the adsorption mechanism is strongly influenced by the actual surface coverage. At low surface coverages, the acetyl dehydrogenates into CH 2 CO or CHCO, which leads to a C − C bond cleavage, yielding CH and CO fragments. At oxidative conditions, both fragments react with the oxygen, O, present on the surface and desorb as carbon dioxide CO 2 . Desorption of cleaved products can be neglected for non-oxidative conditions, which leads to a jammed state, whereas, when the surface coverage is high, the C − C bond cleavage is blocked, and the surface becomes poisoned by acetyl.
Based on the proposed mechanism, we introduce a model which can be summarized by the following rules, where A represents ethanol, v an empty site, 2B represents cleaved products, C is acetyl, and k d (k m ) stands for dimer (monomer) production rates. Note that, as discussed below, adsorption as a monomer (with product C) can only occur in the neighborhood of an occupied site. As cartooned in Fig. 1, dimers are uniformly formed on the substrate (lattice). Successful adsorption of dimers requires two neighboring empty sites. If only one is available, the species adsorbs as a monomer. When both sites are occupied, due to the excluded volume interaction, the adsorption attempt fails and the particle attempting adsorption is no longer considered. The model differs from traditional cooperative sequential adsorption models [5] since, for the latter, the rates of adsorption depend on the state of the nearest-neighbors but not, as in the present model, on the occupation of the local configuration provided by neighboring adsorbed sites. Despite the focus on the electro-oxidation of ethanol, the model could be utilized for the study of any other process dependent on the local configuration rather than on constant, configuration independent, deposition rates.

III. ANALYTICAL STUDY
The time dependence of the coverage and distribution of empty sites can be analytically obtained by establishing a closed hierarchy of rate equations as explained below. To account for different rates for monomer and dimer adsorption (see Eq. 1), we consider a competitive deposition of monomers and dimers, with different deposition rates (k m and k d , respectively), under the constraint that monomers can only deposit in the neighborhood of occupied sites. Results are divided into three limiting cases: equal rates for dimers and monomers (Section III A), preferential dimer site adsorption (Section III B), and different deposition rates for monomers and dimers (Section III C).
Let us start by considering a segment of empty sites with size n which is part of a larger (or equal) one with size ≥ n. Since the neighboring sites of this segment are not necessarily occupied, the possible adsorption events depend on the configuration of the neighbors. A segment can be reduced in size by adsorption of a monomer on the left-hand side of the segment (Fig. 2b), the right-hand side (Fig. 2c), or on both sides (Fig. 2e). It can also be split (or reduced in size) by the adsorption of a dimer on any site of the segment (Fig. 2a), the right-hand side (Fig. 2b), the left-hand side (Fig. 2c), or on both sides (Fig. 2d).
We define P n as the probability that a randomly selected site belongs to any segment n defined before. Each configuration of the catalog in Fig. 2 is obtained with a probability P [· · · ] given by, The proper set of rate equations depends on the case. Below, we describe this set for equal rates of dimers and monomers, adsorption of a preferential dimer site, and different rates for dimers and monomers.

A. Equal deposition rate of dimers and monomers
For equal deposition rates of monomers and dimers, the rate of both species is considered as k. Since P n refers to the probability that a randomly selected site belongs to any segment of n empty sites, which can be part of a larger one, this probability can never increase with time. The rate of change of P n due to the adsorption of dimers is given by, where (n − 1) corresponds to the destruction rate of a segment with, at least, n empty sites, which is zero for n = 1, see Fig. 2(a). The rate of change due to monomers adsorption is, From Eqs. (3) and (4), the total rate of change is given by, This result is equivalent to consider that, regardless the type of adsorption, a segment of n, or more, empty sites can be destroyed by adsorption on (n+1) different places. This equation gives P n (t) = exp [−(n + 1)kt]. The coverage θ can then be obtained from the probability that a certain site is part of a segment of size n ≥ 1, i.e., Defining s m (n) as the rate of monomers adsorption on a n-segment, i.e., s m (n) = − Ṗ n m , we obtain, The adsorption of monomers on a segment of size n ≥ 1, is given by, From the rate of adsorption, the coverage of monomers can be obtained fromθ m = s m for n = 1 giving, Defining now s d (n) as the rate of dimers adsorption on a n-segment, i.e., s d (n) = − Ṗ n d , we obtain, The adsorption of dimers on a segment of size n ≥ 1, is then given by, Knowing the rate of adsorption, the coverage of dimers can be obtained from the rate equation,θ d = s d (n = 1), B. Adsorption of a preferential dimer site Considering a preferential dimer site means that the symmetry is broken and the first adsorption on the substrate occurs through a specific compound of the dimer. The cleavage only takes place if there is a neighboring empty site, in any direction, to adsorb the other compound. In 1D, the left site of the dimer is considered as the preferred one. By symmetry, results are independent on the considered one. For this special case, the change on the P n by dimers is, For the total change on P n we obtain, Considering the relation between P n and P n+1 as P n+1 = Q n P n [31], theṅ and plugging it back into Eq. (15) we obtain, If we assume Q n+1 = Q n , then dQn Qn = −kdt. Therefore, Q n (t) = exp (−kt), which when replaced in Eq. (17) giveṡ P n = − [nk + k exp (−kt)] P n and so, Since the coverage θ is dependent on the evolution of the probability of finding a segment of size n ≥ 1, The independent rates of adsorption for dimers and monomers and the subsequent calculation of the coverage for each species are obtained as before.

C. Different deposition rates for dimers and monomers
To attempt a generic solution for the rules given by Eq. (1), it is necessary to consider different deposition rates for monomers (k m ) and dimers (k d ). Accounting for the rate of change of P n by dimers given by Eq. (3), while by monomers, The change on the the total P n over time is then given by, For the sake of simplicity, we define α n = (n−1)k d +2k m and β = k d − k m . In the same way as before, applying the relation P n+1 = Q n P n , the rate equation for P n+1 is, P n+1 =Q n P n + Q nṖn (23) = −α n+1 Q n P n − 2βQ n+1 Q n P n , and replacingṖ n by Eq. (21), Considering Q n+1 = Q n then Q n (t) = exp (−k d t).
From the above result, Eq. (22) simplifies asṖ n = − (α n − 2βQ n ) P n , which gives, From Eq. (6), which for k m = k d = k boils down to Eq. (6). If s m (n) is defined as the rate of monomers adsorption on a nsegment s m (n) = − Ṗ n m and so The relations y = exp (−k d t) and γ = km k d are considered and the adsorption of monomers on a segment of size n ≥ 1 is given by, From the rate of adsorption, the coverage of monomers is given byθ m = s m for n = 1, and so, The dimers rate of adsorption is then, For the sake of simplicity, the relation y = exp (−t) is used, and the adsorption of dimers on a segment of size n ≥ 1 is given by, For the rate of adsorption, the coverage of monomers can be given by,θ d = s d for n = 1, which by integrating over y gives,  (12). The preferential dimer site rule of adsorption is in Fig. 3(b), where despite the values of the deposition rates being given by k d = k m = 1, the results are equivalent to the ones for k d = 1 and k m = 0.5, since the deposition of a monomer by the non-favored dimer site is not allowed. For these rules of deposition, the exact results are given by Eqs. (19), (13), and (14). The final case, where a different deposition rate for dimers and monomers is considered, is plotted in Fig. 3(c), with deposition rates of k d = 0.5 and k m = 1. The exact solution is given by Eqs. (26), (29), and (32). For all cases, data points from Monte Carlo lay on the line given by the exact solution. observed. The dimers rate of adsorption, for instance, starts at a value of two for k d = 1 since dimers occupy two sites at each deposition. The monomers rate of adsorption starts at zero, and increases as it requires previously adsorption of, at least, one particle. The rate of monomers adsorption increases due to the large influence of the substrate coverage and reaches a maximum when the number of isolated empty sites start to decrease. Exact results are shown for each plot, consistent with the ones obtained with Monte Carlo simulations. Since desorption is neglected, a jamming limit is obtained where no further particles can be adsorbed. In Fig. 4, we see the coverage in the jamming limit θ ∞ as a function of the ratio between dimers and monomers deposition rates, R = k d /k m , where the solid line is the analytical solution, open circles are dimers, and full squares monomers. It can be observed that in the limit of R 1, a complete coverage of monomers is found, except for one dimer that always need to be adsorbed to start the monomers deposition. With the decrease in the coverage of monomers an increase in the coverage of dimers is observed, where equal coverage is reached for a ratio R = 0.207 ± 0.006. In the limit of R 1, a maximum coverage of dimers is obtained in agreement with the classical adsorption of dimers in a one-dimensional lattice [5]. Monte Carlo results are also in agreement with the analytical solution.

V. 2D MONTE CARLO SIMULATIONS
In two dimensions, even for the simplest case of dimer adsorption, no analytical solution have been found. However, it is a case of interest, specially the regular square  lattice which reproduces, for example, the topology of the Pt(100) surface. In this section, we study the proposed model on a square lattice through Monte Carlo simulations. We devote special attention to the percolation properties of aggregates of monomers and dimers [32].
Monte Carlo simulations have been performed on square lattices of linear sizes L = {128, 256, 512} in units of lattice sites, with periodic boundary conditions in both directions. Results have been averaged over 10 4 samples. To decrease the computational effort, a rejection free algorithm was implemented, where the next adsorption trial takes place on an empty site randomly selected from a list of available sites, where the weight of each configuration is properly taken into account. To accu-rately follow the time evolution, the entire population of events is considered as well as the rate of monomers and dimers adsorption.
Simulations have been performed on both clean and impurities-covered substrates. Impurities are considered quenched and to solely influence the adsorption process by purely geometrical restrictions.

A. Clean Substrate
On a clean substrate, the coverage of dimers is larger than the coverage of monomers and the rate of adsorption of monomers as a function of time has a maximum, as also observed in the one-dimensional case. However, the coverage of monomers is favored in two dimensions since each deposited dimer has a greater influence on monomer deposition than in one dimension, mainly due to a larger fraction of configurations with occupied and empty neighboring sites. This can be observed on the inset of Fig. 4, where we plot the jamming limit θ ∞ as a function of the ratio R. In this case, the point of equal coverage for dimers and monomers occurs for a ratio R ≈ 0.6, which is larger than in one dimension, corroborating that monomers are favored. The percolation properties are analyzed by identifying clusters with the Hoshen-Kopelman algorithm [33]. While for lower values of R the system is dominated by monomers, as discussed for 1D, for higher values of R dimers dominate. Percolation of monomers or dimers is then observed with R as a control parameter. In Fig. 5(a) we plot the spanning probability R L defined as the probability of having a percolation cluster touching opposite borders of the lattice. At the percolation transition of both monomers and dimers, the fraction of sites occupied by the specie under study is compatible with the percolation threshold for site percolation in the considered topology [34]. In the inset of Fig. 5(a) is the fraction of sites belonging to the largest cluster P ∞ (the order parameter of the percolation transition).
The percolation threshold R c can be estimated analyzing the maximum value on the standard deviation of the spanning probability. It can be observed in Fig. 5(b), that the percolation threshold scales linearly with the inverse of the lattice lateral size, L. Obtaining for dimers R c (L ∞ ) = 0.98 ± 0.01, and for monomers R c (L ∞ ) = 0.41 ± 0.01.
The scaling of the average size of the largest cluster s max at R c is in Fig. 6(a) 8. Wrapping probability as a function of the ratio R, in 2D, for a) monomers with impurities coverage from right to left of 0%, 10%, 20%, 30% and, 40%, and b) dimers with impurities coverage from left to right of 0%, 10%, 20%, and 30%. Simulation of a system size of 512 2 . Fraction of sites belonging to the largest cluster P∞ on the inset. 91/48 = 1.8958 of the classical percolation universality class [34].
Another important parameter to be taken into account is the second momentum of the cluster-size distribution given by, where s is the cluster size, N is the total number of lattice sites, and the sum runs over all clusters excluding the largest one. The variable M 2 at R c as a function of the system size is in the inset of Fig. 6(a), where another scaling behavior is observed consistent with M 2 ∼ L γ ν , with γ ν = 1.80 ± 0.02, in agreement with the scaling relation γ ν = 2D f − d. We measured the correlation function, also known as connectivity correlation function, defined as where δ ij is 1 if both sites i and j are occupied by the same cluster and zero otherwise and s max is the size of the largest cluster. Figure 6(b) shows that at R c both correlation functions are power laws with an exponent consistent with the one for random percolation [34].

B. Substrate with impurities
To account for the presence of impurities (e.g., Pb atoms [35]), quenched impurities are randomly distributed on the substrate. These impurities do not react and remain immobile, influencing only the adsorption, as an occupied site, which promotes the adsorption of monomers.
Since impurities geometrically favor the coverage of monomers, the value of θ m − θ d as a function of impurities coverage θ imp is plotted in Fig. 7. A maximum is observed at a specific value of the coverage by impurities. The position at which the maximum occurs depends on the ratio R; low values of R favor monomers leading to an earlier maximum while a high ratio disfavors monomers, thus, shifting the position of the maximum to larger values. These results open up the possibility of tuning the production of monomers by controlling the fraction of impurities.
Additionally, impurities also shift the percolation threshold. Figures 8(a) and (b), show the spanning probability R L as a function of the ratio R for different values of impurities coverage. The monomers percolation transition is mainly affected at larger impurities coverage and is shifted to lower values of R. The dimer percolation transition, on the other hand, is shifted to higher values of R. At higher values of impurities coverage, the clusters of impurities predominate on the surface and neither monomers nor dimers percolate. The insets of Figs. 8(a) and (b) show the fraction of sites belonging to the largest cluster P ∞ as a function of R, with P ∞ = smax N (1−θimp) , where N is the total number of lattice sites, and θ imp is the coverage of impurities. In the case of monomers, as disclosed by the behavior of the spanning probability, the size of the largest cluster is only significantly affected by impurities for values of impurities coverage above 30%. In the case of dimers, impurities have a larger effect on R L and P ∞ .

VI. FINAL REMARKS
We introduced a model based on random sequential adsorption of monomers and dimers, representing, acetyl and cleaved products, respectively, in the low desorption limit. The kinetic rules based on recent results by Wang and Liu are dependent on the local configuration provided by the neighboring adsorbed sites instead of configuration-independent rates.
The properties of the model were studied in the 1D lattice and also extended to a 2D square lattice. In the latter case, the model describes the mechanisms of ethanol electro-oxidation on a Pt(100) surface, suggested by Wang and Liu [2]. In 1D, we have analytically solved the model in three different cases: same deposition rate for dimer and monomer adsorption, preferential dimer site adsorption, and different deposition rates. Monte Carlo simulations are in agreement with the analytical solution. In 2D we have studied the jammed state and percolation transition through Monte Carlo simulations. The percolation properties of the adsorbed species reveal that, while monomers percolate at low ratios of dimers/monomers deposition rate, dimers percolate at high ratios. The influence of impurities has also been monitored, disclosing that the coverage of monomers is significantly improved by their presence.
In the present work, we restricted ourselves to study a system as simplified as proposed in the Introduction. One can clearly devise extensions to the basic model to include desorption and reaction pathways not included in the present paper. Molecular dynamics studies could, in principle, provide a more complete picture of the particles arrangements on the surface, but at a shorter timescale. It would certainly be interesting to study the atomistic mechanisms based on cooperative thermal effects that could affect some of the reaction pathways.


extfieldsofstudy:
Physics
Computer Science

text:
Unitary Transformation in Probabilistic Teleportation

We proposed a general transformation in probabilistic teleportation, which is based on different entanglement matching coefficients $K$ corresponding to different unitary evolution which provides one with more flexible evolution method experimentally. Through analysis based on the Bell basis and generalized Bell basis measurement for two probabilistic teleportation, we suggested a general probability of successful teleportation, which is not only determined by the entanglement degree of transmission channels and measurement methods, but also related to the unitary transformation in the teleportation process.

Introduction
Quantum entanglement is one of the most fascinating characteristic of quantum physics, a fantastic application of entanglement [1,2,3] is quantum teleportation, which plays a key role in the field of quantum communication. Since the seminal work of Bennett et al. [4], teleportation has been the research interest of researchers and a number of work both in theory and experiments has been devoted to it [5,6,7,8,9,10,11].
Up to now the teleportation has been studied in different branches, such as directly and network controlled teleportation [12,13,14,15]; discrete-variables and continuous-variables teleportation [16,17,18]; prefect and probabilistic teleportation [19,20] and so on. In fact, one of the key problem of teleportation is how to construct an usefulness quantum channel, different channels will yield different results, some channels can be used to realize perfect teleportation, while some others can only enable probabilistic teleportation. Because of the inevitable interaction with its surroundings, correlations in quantum states are difficult to maintain [21,22], therefore the probabilistic teleportation [23,24,25,26,27] has been widely discussed in recent years.
A necessary and sufficient condition for realizing perfect teleportation and successful teleportation has been given in [28,29,30,31]. Based on the Bell basis measurement, we found that if the channel parameter matrix (CPM) is unitary, then one can always realize a perfect teleportation (i.e., the successful probability p = 1), if the CPM is invertible but not unitary, however, one can only realize a probabilistic teleportation (i.e., the successful probability p < 1).
Motivated by the idea of Ref. [19], in which the authors introduced an auxiliary qubit to realize probabilistic teleportation, we propose some unitary transformation methods in probabilistic teleportation in this work. These methods are based on different entanglement matching coefficients K which corresponding to different unitary transformations. Through detailed analysis with the Bell basis and generalized Bell basis measurement in two probabilistic teleportation processes, we suggest a general probability of successful teleportation, which is not only determined by the entanglement degree of transmission channel and measurement methods, but also related to the unitary transformation in the teleportation process. For example, if we teleport the unknown one-qubit state |ϕ 1 via the channel state |ϕ 2,3 = a|00 + b|11 , then the whole probability of successful teleportation is P = 2(Kab) 2 , where 0 < K ≤ min( 1 |a| , 1 |b| ). Our conclusion covers and complements the results of Ref. [19]. As different K will give different kinds of evolution methods, one can have more flexible and selectable evolution method experimentally.

Entanglement matching and probabilistic teleportation
Suppose Alice wants to send an unknown one-qubit state |ϕ 1 to Bob where R i R * i = |α| 2 +|β| 2 = 1, with i being taken to be 0 or 1 and a repeated index denotes summation. The general two-qubit state |ϕ 2,3 used as the quantum channel can be expressed as follows where X jk X * jk = 2. If Alice adopts the standard Bell basis measurement (BM) φ λ ij (λ = 1, 2, 3, 4) on her particles, i.e., φ 1,2 ij = (|00 ± |11 )/ √ 2 and φ 3,4 ij = (|01 ± |10 )/ √ 2. Then with the denotation of Bell basis [28,29,30], the total state of the system can be rewritten as where σ After Alice's measurement, the total state will collapse to Obviously, based on the BM method, all the T α are unitary. So if the CPM X is unitary, one can always realize the perfect teleportation (i.e., the whole probability p = 1), if X is invertible but not unitary, one can only realize a probabilistic teleportation (i.e., the whole probability p < 1). In Ref. [19]. Li et al. presented a protocol of probabilistic teleportation by introducing an auxiliary qubit state |0 A and performing an unitary transformation on Bob's state. They employ a partially entangled state as the quantum channel, that is with a, b being real numbers and a 2 + b 2 = 1. The CPM X = √ 2diag(a, b) is obviously invertible but not unitary, so Bob cannot directly retrieve the state by acting (σ α ) −1 on the collapsed state |Ψ α B . With the standard Bell basis φ λ ij (λ = 1, 2, 3, 4), the total state of the system can be rewritten as After Alice's BM φ 1 12 , Bob will get the unnormalized state as follows In order to obtain the original state, one can introduce an auxiliary qubit state |0 A [19] in Bob's state, now Bob's state can be express as With the standard two-qubit basis (|00 , |01 , |10 , |11 ) A,3 , we propose an unitary transformation U with parameter K for the particles (A,3) where we called K the entanglement matching coefficient of Bob's evolution. To ensure the transformation U to be unitary, we demand 0 < K ≤ min( 1 |a| , 1 |b| ). There are different unitary transformation methods with different K.
After Bob's evolution, the state |Ψ 1 A,3 turns out to be Certainly, |Ψ 1 A,3 is not normalized. Now Bob performs measurement on the auxiliary qubit A, if the measurement outcome is |1 A , the teleportaton fails, if the measurement outcome is |0 A , the teleportation is successfully accessed and Bob's state becomes Now we discuss the probability of successful teleportation, which contains both Alice's P A and Bob's P B probability. From Eq. (7) one can obtain the Bell state φ 1 1,2 occurring probability as Similarly, the Bell state φ 2 1,2 , φ 3 1,2 and φ 4 1,2 occurring probability are If , which is just the prefect teleportation. Now we compute the probability of Bob for obtaining the original state from the state |Ψ 1 A,3 . The normalized state corresponding to the state in Eq. (11) is After Bob's successful measurement on |0 A , the probability P 1 B of obtaining the original state from the state |Ψ 1 A,3 is We consider Alice's measurement and Bob's different operations in the teleportation process. For Alice's each measurement and Bob's operation, the probability of obtaining the initial state is where P 1 AB is just the square of coefficient of the state |Ψ 1 3 in Eq. (12). Summing all the contributions of P 1 AB = P 2 AB = P 3 AB = P 4 AB = 1 2 (Kab) 2 , we obtain the whole probability of successful teleportation as where 0 < K ≤ min( 1 |a| , 1 |b| ). If a > b, we take K = K max = 1 a , then the optimal probability is P = 2b 2 . When a = b = 1 √ 2 , then P max = 1, which is just the case for prefect teleportation, and for this special case U is the same as that in Ref. [19], i.e.
For different matching coefficients K, one can adopt different kinds of unitary transformation. FOr example, when K = 1 the whole probability of successful teleportation is P = 2(ab) 2 and our unitary transformation matrix turns out to be Next we discuss some difference between the probability P = 2b 2 and P = 2(Kab) 2 for two kinds of unitary transformation. For arbitrary a 2 +b 2 = 1 and a = b, there are always P = 2b 2 > 2(ab) 2 . So Eq. (20) is an unitary transformation for obtaining the optimal probability. However, the condition a 2 + b 2 = 1 and a > b yields b 2 < 1/2, and therefore one can only obtain probability P < 1. When K = 1 we have P = 2(ab) 2 , and the normalization condition a 2 + b 2 = 1 gives rise to P max = 1/2 with a 2 = b 2 = 1/2, thus one can only attain the probability P = 2(ab) 2 < 1/2 for a = b.

Probabilistic teleportation with generalized BM
Considering now Alice makes a generalized Bell basis measurement (GBM), these are where a ′2 + b ′2 = 1 and a ′ = b ′ . The transformation matrix T between the generalized Bell basis and computation basis {|00 , |01 , |10 , 11 } is Let us reconsider the aforementioned one-qubit teleportation, under the generalized Bell basis, the total state of the system is After Alice's GBM φ λ 12 , Bob will get the corresponding unnormalized state as follows When Bob introduced an auxiliary qubit state |0 A for |Ψ α B , and make an unitary transformation U 1 to the state |Ψ 1 A,3 , with If Bob's measurement outcome is |0 A , the teleportation is successfully implemented. Considering Alice's Bell basis measurement φ 1 and Bob's evolution on |Ψ 1 A,3 , the probability of successful teleportation is Similarly, After Bob's U 2 , U 3 and U 4 transformation to the corresponding states and measurement on the auxiliary qubit, the probability of successful teleportation respectively are Thus the whole probability of successful teleportation is Next we discuss the optimal probability of successful teleportation by entanglement matching for the following two cases: (1) |a| ≥ |a ′ | ≥ |b ′ | ≥ |b|. For this case, |aa ′ | ≥ |bb ′ |, |ab ′ | ≥ |ba ′ |, so we take K = 1 |aa ′ | in U 1 and U 3 , K = 1 |ab ′ | in U 2 and U 4 , for which one can obtain P 1 The optimal whole probability is (2) |a ′ | ≥ |a| ≥ |b| ≥ |b ′ |. In this case, |aa ′ | ≥ |bb ′ |, |ba ′ | ≥ |ab ′ |, so we take The optimal whole probability is From the above analysis, one can see that the optimal probability of successful teleportation is determined by the smaller value of |b| and |b ′ |, i.e., the optimal probability is determined by the entanglement degree of Alice's measurement or the quantum channel. However, for K < K max = min( 1 |aa ′ | , 1 |bb ′ | ), the whole probability of successful teleportation is P = 4(Kaba ′ b ′ ) 2 . Therefor, the general probability of successful teleportation is not only determined by the factors of the channel and measurement, but also related to the unitary transformation during teleportation process.

Conclusion
The unavoidable influence of environment always induces degradation of quantum correlations, therefor the study of probabilistic teleportation is significant for quantum information processing. In this paper, we generalized the protocol of probabilistic teleportation by introducing an auxiliary qubit and the unitary transformation methods. Moreover, through the analysis based on the Bell basis and generalized Bell basis measurement in two probabilistic teleportation, we suggested a general probability of successful teleportation, which is not only determined by both the entanglement degree of transmission channels and the measurement methods, but also related to unitary transformation in teleportation process, i.e., P = 2(Kab) 2 , Although P = 2(Kab) 2 < 2(b) 2 (the optimal U transformation). However in experiment, it is more important to realize successful teleportation. As different entanglement matching coefficients K will give different U evolution methods, so one can have more flexible selectable evolution method experimentally.


Environmental Modeling for Traffic Noise in Urban Area

Traffic noise can be classified among the worst factors in terms of damage to people’s health and wellbeing. The trend of noise pollution modeling variable from the smart result of classic regressive models in the performance of many assessment models based on mathematical expressions, genetic algorithms and neural networks (of GRNN type, General Regression Neural Network). A methodological approach for the quantitative analysis of traffic noise in urban settings was proposed in the study. We present an analysis of the acoustic data measured in the city of Villa S. Giovanni (Italy), simultaneous measurement is of noise levels and vehicle flow and composition were done. Different prediction models were compared and a classification for the best assessment tool in the analysis of the equivalent level of noise Leq was given. The results show how the neural network approach provides better performance than the classical solution based on statistical analyses. The GRNN network is best suited to the simulation of the phenomenon seems and for the application in more complex areas, with greater variability in the traffic patterns, such as the case considered.

INTRODUCTION
Traffic noise is considered one of the most invasive type of noise pollution and often the most intrusive of all and has become an issue of immediate concern for public administrations and authorities. The sources of traffic noise are primarily vehicle engines, exhaust systems, tyre-pavement interaction and aerodynamic friction. Therefore, traffic noise prediction models are essential as supports in the design of roads and highways and in the assessment of existing or envisaged changes in traffic noise conditions (Steele, 2001). The researches conducted on noise level prediction, in different countries, have led to the development of various models. Suksaard et al. (1999) studied a model to predict the environmental impact of traffic noise based on two vehicles classes. A road traffic noise prediction method for northern European countries was discussed by Bendtsen (1999). A noise prediction model based on Monte-Carlo approach was proposed by Lam and Tam (1998). Li et al. (2002) developed a GIS based road traffic noise prediction model. Pamanikabud and Tansatcha (2003) have also used GIS for analyzing highway traffic noise.
A statistical model to estimate road traffic noise in an urban setting was applied by Calixto et al. (2003). Cirianni and Leonardi (2011) proposed an ANFIS model to estimate the traffic noise in urban condition in an Italian context. An exhaustive discussion on early and recent traffic noise prediction models can be found in the review by Steele (2001). Cammarata et al. (1995) used a neural network scheme as a substitute for the linear regression of earlier models and comparing the results with some classical regressive models found significant improvements with the use of the neural network. This approach has shown to be particularly interesting and was followed by other authors (El Mallawany et al., 1999;Avsar et al., 2004;Parbat and Nagarnaik, 2008). Gundogdu et al. (2005) and Rahmani et al. (2011) have developed a model by using a genetic algorithm as optimization method.
In these models, vehicles are mostly classified in two groups, heavy and light vehicles, occasionally in three groups, light, medium and heavy vehicles.

AJES
The main objective of this study, which was spurred by an infield campaign to measure traffic noise pollution, is the development of a General Regression Neural Networks (GRNN) approach to assess traffic noise. The approach taken on data led us to classify vehicles in five groups: motor vehicles, light goods vehicles, heavy good vehicles, motorcycles and buses.
A benchmarking of the proposed neural technique is done by application, as we measured the noise levels in the urban area of Villa S. Giovanni (Italy) and compared the results with the output of the neural model and of some traditional regressive models. 2

MATERIALS AND METHODS
Noise data were recorded at 14 survey sites of Villa S. Giovanni. The city was chosen for its territorial characteristics and its geographic location, being the gateway from Italy to Sicily. Also the area is at the center of the project of the Bridge over the Straits of Messina.
We carried out this survey with the following objectives: • To measure the equivalent noise levels generated by the traffic circulating in the principal roads • To estimate the noise level with traditional regressive models and with a neural network approach • To compare the measured values and the predicted ones, to verify the applicability of this neural technique The survey sites were chosen on the base of the traffic flow patterns of the cities, setting the sites along the route with the highest crossing flows, on urban roads, with medium to high traffic and therefore with medium speeds.
These 14 survey sites are at a reasonable distance from stop signs and intersections so that the effects of acceleration and deceleration of vehicles can be considered not relevant on the recordings. The noise data recording campaign was led using a Bruel & Kjar Type 2260 Modular Precision Sound Analyzer. It was located at a point with a distance of 15 m from the closest traffic flow direction and at a height of 1.2 m above ground level.
In order to assess the environmental noise, the parameters chosen were: equivalent noise level Leq, percentile levels: L10, L50 and L90, which are the parameters adopted by the main Italian Legislation DPR, 2004 for noise pollution. The measures were carried out during day hours, in an interval of time between 8:00 a.m. and 7:00 p.m. for all the 14 sites, obtaining a set consisting of 154 records.
Vehicles were classified in the following five categories: Motorcycles (M), Motor Vehicles (MV), Light Goods Vehicles (LGV), Heavy Goods Vehicles (HGV) and Buses (B). Table 1 presents the principal traffic parameters and their ranges.
A correlation analysis was led in order to determine the variables which mainly condition the measured noise levels and to find the most suitable prediction model.
Furthermore, to obtain a model that is able to predict the Leq, it is necessary for the model to (2003): • Be simple enough so it can be used by all professionals involved in urban planning and traffic management • Require only data which can be easily obtained for the noise level forecast • Incorporate accurate results according to the subjective perception of the noise Among the classical regression models, the following three ones best fit these characteristics Burgess (1977), García and Bernal (1985) and an evolution of the UK Department of Transport -CoRTN model (Cirianni and Leonardi 2011). These models are here briefly described:

Burgess Model
Requires characterizing parameters of the vehicular traffic (veh/h Q, percentage of heavy goods vehicles p) and the half width of the roadway d Eq. 1: Garcia and Bernal Model Eq. 2: where, the average flow speed V is introduced.

An Evolution of the Model CoRTN
From the CoRTN model, developed from the Department of Transport (UK), the following revised equation for the calculation of Leq is obtained by Cirianni and Leonardi (2011), where the half width of the roadway d is introduced Eq. 3:   where, the considered variables are: flow Q (veh/h); average speed V (km/h); composition of the vehicular traffic (in terms of percentage of heavy vehicles with an empty weight greater than 1525kg) p(%); slope of the road G(%). The models described in the previous paragraph were calibrated and the coefficients of the equations determined by the minimization of the objective function Root Mean Square Error: where, Li and Leq,i are respectively the measured and the calculated noise levels, at time instant i. Genetic Algorithms (GA) are used in the optimizations. The objective function is multimodal and hence was minimized using genetic algorithms. GAs is inspired by Darwin's theory about evolution and are adaptive heuristic search and optimization algorithms based on the principles of genetics and the theory of evolution. GAs is part of the group of Evolutionary Algorithms (EA).

AJES
Much of the terminology used in the GA theory borrowed from biology such as genes (orbits), individuals (chromosomes or bit strings) and a population of individuals (structures).
Researchers have successfully applied GAs to solve a variety of optimization engineering, scientific and economic problems that can possess mixed continuous and/or discrete variables, as well as discontinuous and non-convex objective functions.
Classical optimization techniques generate a deterministic sequence of computation based on the gradient or higher-order derivatives of the objective function. This point-to-point approach has the risk of falling in local optima. GAs search among a distributed population of points and use probabilistic rather than deterministic transition rules. Therefore they search more globally and have a good chance to find the global optimum.
A detailed discussion and description of the genetic algorithm theory and application can be found in Mitchell (1998); Goldberg (1989) and Sivanandam and Deepa (2007).
The a1, a2, .., an parameter of the three equations was determined from the genetic algorithm coded Goldberg's algorithm in MATLAB 2008 setting a population size with a string length of 80, a crossover probability of 0.001 and a mutation probability of 0.002.
Using this procedure, the following expressions of the models were obtained. Figure 1 shows comparisons between the measured Leq values and the calculated ones according to the mathematical models.
Observing Fig. 1, we can see how, even if the correlation coefficient is close to 0.78 for all the models, therefore giving overall a good approximation value, the evaluation quality is still insufficient, as seen in a point to point detail, especially for those values of Leq which greatly differ from the average trend.
To overcome the limits of traditional forecasting approaches, we examined the applicability of a neural approach for traffic noise forecasting and compared the results obtained with the classical regression models previously proposed.
A Neural Network (ANN) can be seen as a system which can answer a question or supply an output in reply to an input and is defined from a certain number of interconnected units of calculation, which operate as a parallel calculation structure and that acquire their knowledge from the experience supplied, that is, the transfer function of the network is not programmed, but is obtained through a process of training with empirical data. In other terms the network learns the function that ties the output with the input by means of the presentation of correct examples of input/output pairs (Specht, 1991;Filho et al., 2004).
Effectively, for every input introduced to the network, in the learning process, the network supplies an output that differs of a given δ amount from the desired output: the training algorithm modifies some parameters of the network in the desired direction. Every time that an example is introduced, therefore, the algorithm fits slightly the parameters of the network to the values optimal for the solution of the example: in this way the algorithm tries to please all the examples a little at a time.
In order that the comparison be satisfying and complete, it is necessary to consider the great number of analogies with the hypothesis underlying regressive models and neural approach. These analogies essentially consist of the number of variables on which the sound pressure level is made to depend. As illustrated, the independent variables assumed in the regression formulas are generally the vehicular flow, the average speed of the flow, the composition of the flow and, in particular, the percentage of heavy vehicles, defined, according to the Italian standard as the vehicles with an axis load weight exceeding 3.5 tons and the half width of the roadway; these same indicators were used as input data for the achievement of the network.   Table 2 and 3.
The chosen network typology for the best analysis of the problem was the General Regression Neural Network (from here on GRNN). The GRNN approximates any function between input and output and is based on the theory of the not linear regression for the estimation of the function.
The variable regression of one dependent variable X respect to one independent Y consists in the calculation of the Y value more probable given X, on the base of a series of pairs (X, Y), subject to experimental error, where X and Y can be also victorious. In the field of the identification of systems the dependent variable Y corresponds to the exit of the system corresponding to a given value X as input.
In order to develop models for the identification of the examined system it is necessary, following a classic regression methodology, to assume a functional shape for the relation between the variables, choosing a set of parameters which fit the experimental data. The values of these parameters are calibrated on the assumed function using the values registered in the field.
The neural network GRNN model doesn't require the predefinition of a functional shape and it defines directing the formulation from the recorded input, independently from any preliminary assumption. In Fig.  2 the scheme of the used GRNN is shown.
The input units supply the network with the elements of vector X, vector of which we want to calculate the corresponding expected value. Such values are sent to the neurons of the second layer (pattern units). Every node of the second layer corresponds to an available set and all together constitute a kind of memory of the network.
When a new vector X is introduced in order to estimate, Y(X) ⌢ its distance from every X i presents in the pattern units is calculated and the result is passed through an exponential function of activation exp 2 2 i (D / 2h ) to obtain a vector of equal dimension to the number of examples available, that constitutes the input for the successive layer (summation units). In correspondence to this layer it is calculated the scalar product between this vector and the weights of the connections and the result is therefore transmitted to the output units which supply the required estimate. The used value of h in the examined case is the one that minimizes the RMSE (root mean squared error) in the verification phase. Figure 3 shows the trend of RMSE with the variation of the coefficient of smoothing h.
The creation of example patterns, which enclose the case type of the chosen data, is the most delicate passage on the way to obtaining reliable results from the neural elaboration.
The available data are grouped by mostly random criteria in three sets: training-set, verification-set and test-set.
The first set, preponderant on the other two, trains the network on the specific problem and for the determination of the weights, the second (verification) estimates the performance and efficiency of the network and definition of the best architecture, lastly, the test data is for the validation of the network once the construction procedure is completed.

RESULTS AND DISCUSSION
The models (Table 4) are compared on the following statistic parameters: absolute mean error, standard deviation of error, correlation coefficient e Root Mean Square Error (RMSE).  Fig. 4. Graphic comparison L eq measured-estimated by the neural model Figure 4 shows a comparison between the trends of measured values and values forecast according to the neural models. It can be observed that the considered neural network succeeds in describing the problem adequately, in fact, the estimation error on the output is contained within acceptable values and, moreover, it always guarantees a greater precision than all the other considered regressive models.

AJES
This fact allows us to affirm that the GRNN is able to predict satisfactorily the equivalent noise level generated by vehicle flow in roads.

CONCLUSION
The first aim of the study presented was to define an analysis of different methodologies for the assessment of noise pollution related to road traffic.
The second aim was the development of a traffic noise prediction model that can be used in traffic planning, thus researching traffic noise reduction by redesigning traffic patterns and road layout.
An application with the use of classical regression models was led, opportunely recalibrating the parameters of the models with the aid of genetic algorithms and the results obtained compared with those obtained from a neural network of the GRNN type.
The GRNN model gave the best results in the analysis, also compared to other kinds of neural networks (i.e., the MLP Multilayer Layer Perceptrons network), because: • The network "learns" in a single step (one pass learning algorithm) and is in a position to generalize as soon as it stores in its "memory" the data available; • The assessment given is limited by the maximum and minimum values present in the used measurements; • There are no problems of convergence to solutions corresponding to local minimums of the surface of the errors (as instead happens in the case of Back propagation); • The version that uses the clustering technique of the data allows the reduction of the calculation time and the development of models that adapt in real time to eventual variations of the systems which they represent.
The results illustrated in the study show how the GRNN network approach is best suited to the simulation of the phenomenon and for the application in more complex areas, with greater variability in the traffic patterns, such as the case considered.
Undoubtedly, taking into account factors such as ground type, classification of vehicles, road surface, reflective surface, would give a more comprehensive model, at the price of more extensive data recording campaigns. However, the results of this study indicate that the neural model can be applied with satisfying results even using the restricted database.