Abstract: Many application scenarios have been revealed with Wireless Sensor Networks (WSNs). An Error Correcting Code (ECC) will be advantageous to communications in these applications. With the different expecting on efficiency, security, usability, etc., different codes have been constructed for various purposes. The methods based on algebra theory can work well for constructing simple and usability codes. The theory of algebraic geometry can help construct more complex codes with different properties. With the applications of these codes, it is convenient to arrive the purpose in digital communications.
INTRODUCTION
The history of Error Correcting Coding (ECC) started with the work Error Detecting and Error Correcting Codes (Hamming, 1950), at or about the same time as the seminal work A mathematical theory of communication (Shannon, 1948). Error correcting codes play an important role in many digital technologies, from modems to cell phones to compact disk players. Recently, with the rapid growth, Wireless Sensor Networks (WSNs) have been brought to many applicable scenarios (Akyildiz et al., 2007; Akyildiz et al., 2002; Zhou et al., 2010; Wei et al., 2009, 2010). It is important to construct corresponding error correcting codes. In some scenarios, such as environmental monitoring, the efficiency is more expected while the security is more expected in some other scenarios such as identity verify. More proper error correcting codes will be advantageous to the applications. There are many approaches about error correcting codes in the past years (Momihara and Buratti, 2009; Liu and Yang, 2007).
In practice, almost everyone of the ECCs is linear. Considering the differences in the structure and the processing of information sequences, the codes can be divided into block codes and convolutional codes. Algebra is the important basis in theory. With the algebraic principle, most good properties of the codes can be represented in formulas.
Attributing to the approaches of Hocquenghem, Bose and Ray-Chaudhuri, BCH codes are presented as important cyclic codes. They are simple and easy to be constructed for certain error correcting capability. Also they are easy to be decoded and it is a common code in linear block codes. Reed-Solomon codes are also important and widely applied cyclic codes.
Algebraic geometry codes (Goppa, 1981) came as a result of many years of thinking over the possible generalizations of Reed-Solomon codes, BCH codes and classical Goppa codes. Surprised relation between coding theory and algebraic geometry theory is found and some curves helpful to construct some linear codes over a finite field.
Turbo codes are proposed in the article Near Shannon limit error-correcting coding and decoding: Turbo codes (Berrrou et al., 1993) and the shannon bound can be approximated. It has been found that the principle of turbo codes is similar as the Low density pairty check codes, namely, LDPC codes (Gallager, 1962). Turbo codes can be applied in many communications especially the mobile communications or personal communications.
Many nonlinear codes have been discovered such as Nordstrom-Robinson codes, Kerdock codes, Preparata codes, Delsarte-Goethals codes, Goethals codes and so on. Each of these codes holds stronger error correcting capability and has more words than any known linear code. Hammons found that above four codes can be denoted as the ideals of polynomial ring over Z4. More approaches have been processed on codes over common rings.
FUNDAMENTAL MATHEMATICAL FORMULATIONS
Now we consider the BCH error correcting codes. Supposed that (n, q) = 1, βεFqm and β is n-th order, integer l>0, 2≤δ≤n-1, then a BCH code with the design distance δ can be denoted as following:
| (1) |
If the minimal polynomials of βl, βl+1, ..., βl+δ-2 are denoted as m0(x), m1(x), ..., mδ-2 (x), then it is easy to be found that the generator polynomial of above code C is the Lowest Common Multiple(LCM) of m0(x), m1(x), .., mδ-2 (x). In fact, we can say more about the code C such as the minimal distance d≥δ. Introducing Euler function and Mφbius function, the dual code of C, periodic distributions and the calculating formulas about non-cyclic equivalent classes can be deduced.
Then we look at the Goppa codes. Assumed that g(z)εFqm[z], αiεFim (I = 1, 2, ..., n), L = {α1, α2, ..., αn}, αi≠αj (i≠j), g(αi)≠0 (i = 1, 2, ..., n). A classical Goppa code can be defined as following:
| (2) |
Obviously, the Goppa codes are linear codes. After construct all the reasonable function f(z) with several properties over the Goppa function g(z), a new linear code can be obtained. Moreover these, with the introducing of Reed-Solomon codes, the other algebraic geometry codes can be constructed.
CONSTRUCTING A BCH CODE WITH THE DESIGN DISTANCE 11
Cyclotomic coset plays an important role in the constructing of BCH codes. Assumed that nonnegative integer s<pm -1, ms = min {rεZ+|pr+1 s ≡ s mod pm -1}, then the Cyclotmic coset including s modulo pm-1 can be denoted as:
| (3) |
The least element of Cs means the representative element. The set {0, 1, ..., pm-1} can be divided into several disjoint cyclotomic cosets.
The Euler function and Möbius function can be defined as:
| (4) |
and
| Table 1: | Cyclotomic cosets, minimal polynomials and conjunagte roots |
| (5) |
where, pi (i = 1, 2, ..., k) are all primes and pi≠pj (i≠j).
Based on the Möbius inversion formula, periodic distributions and the calculating formulas about non-cyclic equivalent classes can be proved. The cyclotomic cosets, minimal polynomials and the conjugate roots of binary BCH code (31, 11, d≥11) are shown in follow Table 1. The primitive polynomial is p(x) = x5+x2+1.
Table 1 Cyclotomic cosets, minimal polynomials and conjunagte roots.
So, the generator polynomial g(x) = LCM {m(1), m(3), m(5), m(7)} that is:
| (6) |
Coding and decoding can be achieved based on the generator polynomial, Berlekamp-Massey algorithm and Chien search algorithm.
Example: The sent code word is 1001111011110100011 10001111011 while the received code word is 10111110011011100001110011111011. It means the received polynomial is:
| (7) | |
The misplacement polynomial can be obtained after the implementation of Berlekamp-Massey algorithm as following:
| (8) |
The error polynomial can be obtained after the implementation of Chien search algorithm:
| (9) |
Then the message polynomial can be computed as:
| (10) |
It is the same as the sent code word. Error correcting succeed.
CONCLUSIONS
In this study, we explore the error correcting codes in Wireless Sensor Networks. Algebra theory can work well for constructing simple and usability codes such as BCH codes. The theory of algebraic geometry can help construct more complex codes with different properties. For different purpose of digital communications, it is need to construct different codes. Möbius function Euler function can be used to obtain the periodic distributions and the calculating formulas about non-cyclic equivalent classes. Based on cyclotomic cosets, minimal polynomials and conjugate roots, the coding and decoding process can be completed efficiently as shown in the example. More useful codes can be constructed with the help of algebraic geometry theory such as binary BCH codes (31, 11, d≤11) shown above. All these codes are advantageous and convenient to be applied in digital communication systems such as Wireless Sensor Networks.
ACKNOWLEDGMENTS
This study is supported by National Natural Science Foundation of China (No. 10926055). The authors would like to thank the anonymous reviewers for their valuable comments.