Abstract: In this study, the Gröbner bases of modules are employed as a tool to analyze block length of RS code. A coordinate permutation of a RS code, which is defined over GF(pm) in GF(p), the polynomial vector form of the result can be considered as a sub module. Based on the algebraic structure of quasi-cyclic codes, the Gröbner bases of such a sub-module shed light on block length and dimension of the original code. Thus, block length of the code can be estimated. Furthermore, the primitive polynomial and generator polynomial of the code are reconstructed through Galois Field Fourier Transform (GFFT) technique.
INTRODUCTION
In a context of non-cooperative communication or reverse-engineering of a communication system, it is of great interest to recognize the parameters, such as block length and parity check matrix of the codes in the intercepted bit stream. Due to the lack of prior information, the error bits exists in the bit stream. The problem of recognizing and reconstruction can be very tough in some cases.
Till now, the publications cope with this problem are scarce. Some of them focuses on identification and reconstruction of convolution codes (Filiol, 1997; Rice, 1995). As to the block codes, Valembois (2001) has formalized the problem of finding the nearest (for the Hamming distance) block code from bit stream and proved it is NP-complete. In other studies dealing with the problem, Chabot (2007) and Cluzeau (2006) are restricted to find the parity check matrix and may have limitations in applications, such as algorithm works efficiently only when the weight of the dual code is very low. Furthermore, all of these solutions considered only the case of binary codes.
Reed-Solomon (RS) code, a class of non-binary cyclic block codes, is a subfamily of the cyclic BCH codes (Shu et al., 2005). The RS code is optimal in the sense that the minimum distance has the maximum value possible for a linear code of size (n, k) which is known as the Singleton bound (Moreira and Farrell, 2006). It is widely used in mass storage systems, data transmission (such as CCSDS, DVB), as well as space transmission.
As an important subfamily of the cyclic BCH codes, its cyclic property in extension field GF(pm) ensures that RS code is quasi-cyclic in GF(p). The most useful RS codes in practice are those defined over GF(2m) (Ling and Sole, 2001). Also, this is the kind of RS codes which is going to be used for demonstration.
In this study, a new approach, which based on Gröbner bases of modules, is adopted to fully exploit the quasi-cyclic property of RS code in GF(2). After a coordinate permutation of a RS code, the polynomial vector form of the result can be treated as a submodule. Due to the algebraic structure of the original code, the Gröbner bases of the submodule have some distinctions which differentiate itself from the submodules of those incorrectly-estimated codes. Thus, the code can be detected. Through the triangularization of the Gröbner bases of the submodule, if there is no error bit, the dimension of the original code can be calculated at the same time according to the result of Lally and Fitzpatrick (2001). A further step is that GFFT is being used to reconstruct the primitive polynomial and generator polynomial of the original code.
BASIC STRUCTURES AND TOOLS
Modules and submodules: Among the structures in abstract algebra, a module is definitely a versatile one, whose concept derives from the attempt to conduct classical linear algebra with an arbitrary ring, instead of the traditional field (Hartley and Hawkes, 1970). However, this kind of generalization from vector spaces to module spaces at the same time entails a sacrifice because the scalars do not necessarily have inverses. For formal definition, a module has been presented by Shu et al. (2005).
In a submodule of an R-module, M will be a subset N of M such that the operations of M, when restricted to N, make N into an R-module. For example; let M be an R-module, Ø ≠ U⊂M is called a submodule of M if (UM1) (U, +)<(M, +) and (UM2) αεR, uεU⇒αuεU, that is, RU⊂U.
Gröbner bases of submodules: A Gröbner basis is a specific generating set of an ideal or submodule over a polynomial ring. It is not minimal in general but has extremely nice properties. It is reasonably easy to extract information about the ideal or submodule from a Gröbner basis. Here, the definition of Gröbner bases of submodules is given as a set of non-zero vectors G = {g1,…, gt} contained in the submodule M is called a Gröbner basis for M if fεM, there exists iε{1,ÿ, t} such that Im(gi) divide Im(f). The set G is called a Gröbner basis for the submodule (G). where, Im(f) is the leading monomial of f.
Gröbner basis can be obtained from Adams and Loustaunau (1994) and Buchberger and Winkler (1998).
Quasi-cyclic codes and Gröbner bases: Assuming C is a quasi-cyclic code whose index is l, code length is n = lxm. It is obvious that a coordinate permutation with a codeword c of C can be represented in a polynomial vector form of c = (c0(x), c1(x),… cI-1(x)), will be considered as element of R-submodule space of RI, where R = F(x)/(xm-1). The pre-image
(Lally and Fitzpatrick, 2001).
where,
Galois Field Fourier Transform (GFFT): Let a(x) = an-1xn-1+an-2xn-2+an-3xn-3+…+a0 be a polynomial over GF(q), where aiεGF(q), then the Mattson-Solomon (MS) polynomial of a(x) is defined as:
Where:
α is a primitive nth root of unity over GF(qm). A = (An-1, An-2, An-3,… A0) is Galois Field Fourier Transform (GFFT) of a = (an-1, an-2, an-3,… a0) (Lally and Fitzpatrick, 2001) which can be defined in matrix form as:
Let the Vandermonde matrix on the right side of equation be matrix V, the equation above can be written as:
Thus, according to the definition of RS code, the GFFT result of the polynomial form of its code word contains a series of successive zeros.
PROPOSED ALGORITHM
Coordinate permutation of original codes: In order to make use of Gröbner bases tool, the first step of the algorithm is to preprocess the intercepted code words to transform them into a specific submodule spaces. The coordinate permutation method is utilized within a codeword as explained below. Given a codeword c of a quasi-cyclic code C, whose index is l, code length is n = lxm, c can be represented as:
Through a coordinate permutation it can be expressed as:
Where:
Calculation of the Gröbner bases of derived submodule spaces: The process of computing a Gröbner is actually a generalization of three familiar methods: Gaussian elimination for solving linear systems of equations, the Euclidean algorithm for computing the greatest common divisor of two univariate polynomials and the Simplex Algorithm for linear programming. Buchberger and Winkler (1998) were first to give an algorithm for computing the Gröbner bases in dissertation in 1965. Currently, there are several Computer Algebra Systems (CAS) in hand to compute the Gröbner bases and the primary concern of this study is applying the Gröbner bases to estimate the parameters of RS codes but not the computation algorithm itself. One of the CAS, namely Macaulay2, is employed as a tool to compute the Gröbner bases of submodule spaces (http://math.uiuc.edu/Macaulay2/).
Estimating the parameters of the original code: According to the properties of the Gröbner bases of Quasi-cyclic codes as mentioned in above, whether or not a sequence of intercepted code-words belongs to a quasi-cyclic code can be detected by the properties of Gröbner bases of submodule spaces. Rather, the Gröbner bases of submodule spaces of incorrectly estimated codewords which can be considered as randomly generated bit sequence, is an identity matrix as:
or is very close to Ilx1. Here, ra which is the proportion of ei in the derived Gröbner base matrix, is defined to indicate its similarity to identity matrix:
where, num(ei) is the number of ei in the matrix.
Thus, if ra = 1, the matrix is completely an identity matrix. We choose nest whose corresponding ra = min {ra1, ra2,…, raj} as an estimation of block length n.
Moreover, if the intercepted code words contains no error bit, its dimension can be estimated directly that is information length k, directly by the corollary (estimating the parametesr of original code).
Subsequently, based on the block length nest of the original code which has been estimated above, GFFT is used to reconstruct the primitive polynomial and generator polynomial according to the characteristics. Let Ai be the GFFT result of the code word according to i primitive polynomial, then, pi over GF(2m):
If Ai1 = Ai2 = … = Aikest = 0, the estimated primitive polynomial pest = pi, information length kest = k’. Accordingly, the generator polynomial g can be reconstructed.
| Fig. 1: | Flow chart of the estimation of RS code |
The algorithm is showed in a flow chart (Fig. 1).
METHODOLOGY
RS(7, 3) code, whose primitive polynomial is x3+x2+1, is used for the demonstration of the reconstruction process. As a cyclic code in GF(2m), RS code is actually a quasi-cyclic code in GF(2). Like many other blind estimation methods, the assumption can be made in order to synchronize the intercepted code words sequence. Once synchronized the first step is to search for code length n. When nest is assumed, its correspondent code width mest can be identified.
After the coordinate permutation of the original code words, whether or not the code words belong to a quasi-cyclic code can be judged through the number of ei contained in the Gröbner bases of derived submodule space. For comparison, ra, the proportion of ei, is defined in order to measure how close the derived Gröbner base matrix is to be the identity matrix.
Once the search has been completed, the n’est with the Gröbner base matrix which contains least proportion of ei is chosen as the estimation of code length n as follows:
where, ra = 0.
If the code length nest is incorrect or there are too much error bits in the intercepted words sequence, the Gröbner base matrix is an identity matrix as follows:
where, ra = 1.
One step further, if the intercepted code words sequence contains no error bit. Estimating the parameters of the original code can be used to estimate the information length k from the triangularized form of Gröbner base matrix.
According to estimating the parameters of the original code:
Accordingly:
thus, the original code is an RS(7, 3) code.
However, error bits exist. So, here GFFT is used to estimate the primitive polynomial and generator polynomial of the original RS code. Under the estimated code length n’est, the possible primitive polynomials are determined. Each of them is used to do GFFT in GF(2m). According to successive zeros of the results, the primitive polynomials and generator polynomials can be estimated.
If the primitive polynomial is correctly assumed as x3+x2+1, the result is shown as follows:
From the number of the successive zeros in the results of GFFT, the information length of the original code can be estimated as k = 3. Thus, the original code is RS(7, 3) code, whose primitive polynomial is x3+x2+1, generator polynomial is g(x) = x4+4x3+5x2+1.
RESULTS
Some RS codes with comparatively larger block length and different number of code words are used in Monte Carlo simulation in order to verify the robustness of the reconstruction algorithm. They are RS(127, 63) with 7 code words, RS(255, 127) with 8 code words and RS(255, 127) with 25 code words and the corresponding performances of the estimating method are shown in Fig. 2-4, respectively as follows:
| Fig. 2: | Reed-Solomon (RS) (127, 63) with 7 code words |
| Fig. 3: | Reed-Solomon (RS) (255, 127) with 8 code words |
| Fig. 4: | Reed-Solomon (RS) (255, 127) with 25 code words |
Figure 2 shows that when block length is 127 and the number of intercepted code words is 7, the performance of the proposed method is satisfying that is, even when the bit error rate is 0.001, the successful reconstruction rate is 100%. While in Fig. 3, when the bit error rate is still 0.001, the successful reconstruction rate falls down to 0.74 approximately. This sharp difference illustrates that the block length of the RS code is a factor which has an impact on reconstruction performance.
Furthermore, through the comparison between Fig. 3-4, it has been suggested that the number of the code words used in the reconstruction process can affect the result even when other parameters stay the same.
| Fig. 5: | Relationship between number of codes and performance |
When the number of error bits in the intercepted code words sequence is considerable, the number of code words used plays an important role. In a certain scope, more data is used, more likely the estimating results are correct. The output of Monte Carlo simulation reflects the relationship in Fig. 5 as follows.
CONCLUSION
In this study, a reconstruction method of Reed-Solomon codes is given. The method can be mainly divided into two steps. In the first step, the tool of Gröbner base is used to efficiently identify the block length. This could be generalized to all the codes with quasi-cyclicity. In the second step, Galois Field Fourier Transform (GFFT) is employed to reconstruct the primitive polynomial and generator polynomial. Simulation results show that the method is both valid and robust.
ACKNOWLEDGMENTS
This study was supported by the NSAF of China (Grant No. 11176005).