CN100391141C - An error-tolerant communication channel coding parameter blind identification method - Google Patents

Abstract

The present invention belongs to the field of intelligence communication and information safety technology, particularly to a coding parameter blind identification method of a fault-tolerant code communicating channel. In the fields of the future intelligent mobile communication, broadcast multipoint communication and communication acquisition, a channel coding mode needs changing at any time following the change of time and environment in order to obtain the optimal communication efficiency and service quality. In the communication environment, the synchronous communication of persons who need multi-party communication can not be realized by a protocol generally; therefore, multi-part rapid blind identification which can realize channel coding parameters only by signal contents needs receiving so as to achieve the purpose of intelligent communication. Aiming at the requirement of intelligent communication, the present invention provides a coding parameter blind identification model without a protocol of a fault-tolerant code communicating channel; the model is quickly solved by solving a Homogeneous Key Module Equation (HKME); consequently, the quick coding blind identification without the protocol communication of a fault-tolerant channel is realized.

Description

An error-tolerant communication channel coding parameter blind identification method

technical field

The invention belongs to the technical field of intelligent communication and information security, and in particular relates to an error-tolerant communication channel coding parameter blind identification method.

technical background

In the fields of intelligent mobile communication, multipoint broadcast communication and information interception in the future, it is necessary to change the channel coding method at any time with the change of time and environment in order to obtain the optimal communication efficiency and service quality. In this kind of communication environment, it is generally impossible to realize the synchronous communication of multi-party communicators through the protocol. Therefore, it is necessary for the receiving parties to realize fast blind identification of channel coding parameters only through the content of the signal, so as to achieve the purpose of intelligent communication.

Signal blind identification (Blind Identification) technology is the frontier of today's communication research. Its goal is to establish normal communication without training sequence (Training Sequence) equalization channel. Blind identification technology is widely used in communication, information theory, cybernetics and system It has broad application prospects in other fields.

Let F be a field, let Z be an integer ring, and N be a positive integer. The so-called blind recognition problem of convolutional codes is specifically described as follows: Assuming a part of the known convolutional code sequence, use the polynomial on the integer ring Z It means: C _i (D)=c _i0 +c _i1 D+c _i2 D ² +...+c _iN D ^N , i=1, 2...k. The generator polynomial g _i (D)=g _i,0 +g _i,1 D+...+g _i,t D ^t , i=1,2...k of the convolutional code encoder capable of generating the codeword sequence is required. For simplicity, let k=2.

The Gaussian elimination method can be used to solve g _i (D), but the Gaussian elimination method is error-tolerant, that is, each coefficient in the coefficient matrix in the equation system to be solved cannot have errors. In conventional communication, bit error rates between 10 ^-2 and 10 ^-3 often occur. In order to be able to realize the identification of convolutional codes and other channel coding parameters in the case of bit errors, it is usually necessary to use a large number of data collection experiments and calculations. Through hundreds or even tens of thousands of data collections and experimental calculations, it is possible to obtain A set of error-free data, and then solve the solution of the linear equation system. Moreover, the computational complexity of the Gaussian elimination method is O(N ³ ). For example, t=60 is usually estimated for 7/8 convolutional codes, therefore, at least about N=8×9×61=4392 consecutive error-free bits need to be collected. In this way, under the condition that the bit error rate is prob(e _ij =1)=0.005, 8×10 ⁹ times of data interception must be performed to select 4392 error-free bits with a probability of more than 95%. In order to make the Gauss elimination method have a unique solution, about 4×10 ¹⁰ times of data sampling and equation calculation are needed. It can be seen that the amount of collected data is very huge, and the computational complexity is more than 3.2×10 ²¹ per operation.

In order to realize the fast decoding of BCH codes, Berlekamp (1968) [Berl] proposed the key equation KE, and gave the famous KE solution algorithm whose computational complexity is O(N ² ). Massey (1969) [Mass] put The synthesis problem of linear recursive sequence (LRS) comes down to solving the KE equation, and an iterative algorithm is given. The above algorithm is now called Berlekamp-Massey algorithm (abbreviated as BM algorithm).

The so-called key equation KE is to solve the following element pair (f(x), L)∈F[x]×Z, satisfying:

f(x)C ₁ (x)≡b(x)modx ^N+1 ,

And make 0≤degb(x)<L, f(0)≠0, degf(x)≤L, and L reaches the minimum.

Due to the importance of solving KE, exploring new algorithms and revealing the various internal connections of existing algorithms is a long-standing research topic in the fields of information theory [Chen], [Heyd], [Kail], [Kuij]. Yes The efficiency parameters of the LRS-related algorithms are one of the important evaluation criteria for cryptanalysis. The BM algorithm is also used as a standard decoding algorithm for RS codes and made into a dedicated chip, which is widely used in various communications and multimedia storage. quality of life for everyone.

In the present invention, the problem of rapid blind recognition of error-tolerant channel coding without protocol communication is reduced to a homogeneous key module equation HKME, and the homogeneous key module equation is described by the homogeneous ideal of the polynomial ring F[x, y] with two variables.

HKME promotes KE. But its promotion direction is different from that of G.L.Feng[Feng] and S, Sakata[Saka]. This new direction of research holds exciting promise. It has important applications in the fields of intelligent communication, information interception, and cryptanalysis.

references

[Adam] W.W.Adams and P.Loustaunau, An Introduction to Gr\″obner Bases, Amer.Math.Society, 1994.

[Berl] E.R. Berlekamp, Algebraic Coding Theory, McGrw-Hill, New York, 1968.

[Chen] M.H.Cheng, Generalized Berlekamp-Massey Algorithm, IEE Proceedings Communications, Vol.149(4), 207-210, August 2002.

[Feng] G.L.Feng, K.K.Tzeng, A New Procedure for Decoding Cyclic and BCH Codes up to Actual MinimunDistance, IEEE Trans.on Inform.Theory, vol.40, No.5, 1994, pp1364-1374.

[Heyd] A.E.Heydtmann and J.M.Jensen, ON the Equivalence of the Berlekamp-Massey and the Euclidean Algorithms for Decoding, IEEE Trans.Inform.Theory, vol.46(7), 2614-2624, 2000.

[Kail] T. Kailath, Encounters with the Berlekamp-Massey Algorithm, in Communication and Cryptography, edited by R.E. Blahut, etl. Kluwer Academic Publisher, pp.209-220, 1994.

[Kuij]] M.Kuijper and J.C.Willems, "On constructing a shortest linear recurrence relation," IEEE Trans.Automat.Contr.vol.42, No.11, p1554-1558, 1997.

[Lu05] Lu Peizhong, Shen Li, Zou Yan, Luo Xiangyang, Blind recognition of deleted convolutional codes, Chinese Science Series E, 35(2), 173-185, 2005.

[Mass] Massey, J L, Shift-Register Synthesis and BCH Decoding, IEEE Trans. Info. Theory, 15(1): 122-127, 1969.

[Saka]S.Sakata, Synthesis of Two-Dimensional Linear Feedback Shift-Registers and Groebner Basis, LectureNotes in Comput.Sci.356, Springer-Verlag, Berlin, 1989.

Contents of the invention

The purpose of the present invention is to propose a method for blind identification of error-tolerant communication channel coding parameters with low computational complexity and wide applicability for non-protocol communication.

The method for blind recognition of error-tolerant communication channel coding parameters proposed by the present invention includes designing a structured model for blind recognition of fault-tolerant channel coding without protocol connection, establishing the homogeneous key module equation HKME of the structured model; and proposing to solve the method The SY2SY double-combination algorithm of the homogeneous key model equation HKME can quickly solve this model, so as to realize the fast blind identification of error-tolerant channel coding without protocol communication.

1. Model

The problem of sequence synthesis can be described as: given the sequence c=(c ₀ , c ₁ ,...,c _N ), find the characteristic polynomial with the smallest degree that can generate the sequence c. The traditional linear recursive sequence synthesis model is shown in Figure 3.

Because the original signal obtained under the background of information interception must have serious bit errors. Therefore, it is necessary to find a new method to solve the problem of blind identification of signal parameters, quickly distinguish the signal data format, disordered form, error correction coding method and frame structure format, etc. Fault-tolerant synthetic analysis of sequences is a fundamental problem in cryptanalysis.

The hard part of the problem is fault tolerance. Unlike the problem of solving linear equations with errors over finite fields, there is no limit to the series of linear recurrence relations. Therefore, if the series of the linear recurrence relation is too long, it is not feasible to use the discrete Walsh spectrum method to study the subject.

We start with analyzing the global properties of recursive sequences and algebraic ideals, and find many methods to solve this problem. The invention adopts a new mathematical model to characterize the comprehensive problem of error sequence. Transform the key equation originally used to describe the BM algorithm into a homogeneous ideal equation. A relational ideal is used to record the linear recurrence relations of various local sequences reflecting all the different starting points of a sequence. The model of the present invention therefore greatly broadens the meaning of Berlekamp's (1968) mathematical model of the key equations for sequence synthesis. Our goal is to quickly calculate this homogeneous relational ideal and further analyze its graded algebraic structure. Since the rigid structure of the ideal relation has strong fault tolerance, the most reasonable linear The recursive ideal generator leads to the correct solution to the error-involved linear recursive sequence synthesis problem. The data analysis of a large number of real experiments shows that the problem of fault-tolerant synthesis of linear recursive sequences can be transformed into a pure computational algebraic geometry problem. The algebraic structure and algorithm rules of computational algebraic geometry can be used to characterize the global properties of linear recurrence relations. In this way, the difficulty that random variables on finite fields cannot reveal global properties by statistical methods can be overcome.

Fig. 4 shows a structural model of blind recognition of error-tolerant channel coding without protocol contact proposed by the present invention. That is, for the received signal sequence, the homogeneous ideal structure of all recursive relations related to each part of the sequence is found through the confluence decomposition algorithm, and then the optimal solution is obtained by the fractional ideal resolution algorithm.

2. Homogeneous key equation

We use the following equation to describe the structural model of blind recognition of fault-tolerant channel coding without protocol communication:

Let F be a field and F[x,y] be a polynomial ring on F; let

C _i (x, y) = c _i0 y ^N + c _i1 xy ^N-1 + c _i2 x ² y ^N-2 + ... + c _iN x ^N , i = 1, 2, ..., k (1) is F t homogeneous polynomials in [x, y]; let I=<x ^N+1 , y ^N+1 > be the ideal of F[x, y] generated by x ^N+1 , y ^N+1 .

Homogeneous key modular equation HKME: find F[x, y]-module

Γ ^(k) ={(H ₁ ,...,H _k )∈F[x,y] ^k |H ₁ C ₁ (x,y)+...+H _k C _k (x,y)≡0modI} The minimal standard generator of (2).

In the above key modulus equation, when k=1, the problem becomes a sequence synthesis problem. As shown in Figure 2, the synthesis problem of the linear recursive sequence (LRS) is a special case of the recognition problem of the convolutional code. At this time, as long as the linear recursive sequence is regarded as a codeword of the convolutional code, the LRS is the I(D) information The output sequence, and the all 0 sequence is the output sequence of the verification path of the coding sequence, because it is omitted when outputting the identity sequence. This is the codeword of a systematic convolutional code.

3. Fast algorithm

To facilitate the understanding of the algorithm in this section, we briefly introduce the GB basis theory [Adam].

Suppose F is a field, and F[x ₁ ,...,x _n ] is a polynomial ring with n undetermined elements x ₁ ,...,x _n on the field F. Define an item order ">" on the single item set of F[x ₁ ,...,x _n ]. Thus, for f∈F[x ₁ ,…,x _n ], f can be expressed as $f={\mathrm{\&alpha;}}_1{x}^{{\mathrm{\&alpha;}}_1}+{\mathrm{\&alpha;}}_2{x}^{{\mathrm{\&alpha;}}_2}+\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;+{\mathrm{\&alpha;}}_r{x}^{{\mathrm{\&alpha;}}_r},$

where 0≠α _i ∈ F, α _i = (e _i1 ,..., e _in )∈ Z ₊ ⁿ , $x^{{\mathrm{\&alpha;}}_i}={x_1}^{e_{i1}}\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;{x_{\mathrm{no}}}^{e_{\mathrm{in}}}$ ,and $x^{{\mathrm{\&alpha;}}_1}>x^{{\mathrm{\&alpha;}}_2}>\&CenterDot;\&Center\; Dot;\&Center\; Dot;>x^{{\mathrm{\&alpha;}}_r}$ . At this time, said $\mathrm{lp}\left(f\right)=x^{{\mathrm{\&alpha;}}_1}$ Is the first power product of f; lc(f)=α _i is the first term coefficient of f; $\mathrm{lt}\left(f\right)=a_1{x}^{{\mathrm{\&alpha;}}_1}$ is the first term of f.

Let 0≠f, g∈F[x ₁ ,…, x _n ], L=lcm(lp(f), lp(g)), that is, L is the least common multiple of lp(f), lp(g), then called $S(f,g)=\frac{L}{\mathrm{lt}\left(f\right)}f-\frac{L}{\mathrm{lt}\left(g\right)}g$ is the S polynomial of f and g.

Given two polynomials f, h in F[x ₁ ,…,x _n ] and a subset G={f ₁ ,…,f _t }, if h=f-(c ₁ X ₁ f ₁ +…+ c _t X _t f _t ), where c _i ∈ F, X _i is a power product term, satisfying lp(f)=X _i lp(f _i ), lp(h)<lp(f), then it is recorded as $f\stackrel{G}{\&Right\; Arrow;}h.;$ If there exists h _i ∈ F[x ₁ ,…,x _n ] such that $f\stackrel{G}{\&Right\; Arrow;}{h}_1\stackrel{G}{\&Right\; Arrow;}\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;\stackrel{G}{\&Right\; Arrow;}{h}_{\mathrm{the\; s}}\stackrel{G}{\&Right\; Arrow;}h,$ is recorded as $f{\stackrel{G}{\&Right\; Arrow;}}_{+}h.$

For K={f ₁ , f ₂ ,...,f _k }∈F[x ₁ ,...,x _n ], the resultant impulse of K is a finite generating module on F[x ₁ ,...,x _n ] as follows:

Syzygy(K)={(h ₁ ,...,h _k )∈F[x ₁ ,...,x _n ] ^k |h ₁ f ₁ +...+h _k f _k ＝0}

The following fast algorithm finds the GB basis of the homogeneous ideal <K> and the corresponding combined Syzygy(K).

The specific steps of Sy2Sy double combination algorithm:

Input: strictly sorted homogeneous set K={f ₀ , f ₁ ,...,f _l }

Output: GB base G such that <G>=<K>, and the generator set of Syzygy(K).

(1) Initial:

Let (f _0,0 , f _1,0 , . . . , f _l,0 )=(f ₀ , f ₁ , . . . , f _l ). And set:

(deg _y lp(f ₀ ), deg _x lp(f ₀ ))=min _{i=0, 1, . . . , l} (deg _y lp(f _i ), deg _x lp(f _i )), here, Integer vector (n ₁ , m ₁ )≤(n ₂ , m ₂ ), if and only if n ₁ <n ₂ , or n ₁ =n ₂ and m ₁ ≤m ₂ ; let g ₀ =f ₀ , A ^{( 0)} =I is the identity matrix, G={g ₀ }, K ₀ ={f ₁ , . . . , f _l }.

(2) Assume that step k has completed the following algorithm:

The selected set G and the remaining polynomial set K _k reduced by G satisfy the following relationship:

<G∪K _k >=<K>,

where k=0, 1, ..., lG = {g ₀ , g ₁ , ..., g _k }, K _k = {f _{1, k} , f _{2, k} , ..., f _{l, k} },

And the coefficient matrix A ^(k) has been calculated to satisfy

$\left(\begin{array}{c}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}\\ {\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; .</span>\mathrm{<span\; class="notranslate">\; k</span>}}\end{array}\right)<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; A</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}\left(\begin{array}{c}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 0,0</span>}}\\ {\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 1,0</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; .</span>\mathrm{<span\; class="notranslate">\; 0</span>}}\end{array}\right)<span\; class="notranslate">\; ,</span>$

Also note that A _i ^(k) is the ith row of matrix A ^(k) , i=0, 1, . . . , l.

(3) Step k+1 needs to be calculated as follows:

1) Selecting f _{0, k+1} , f _{0, k+1} is a special polynomial f _{s, k} in K _k , satisfying

$<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; deg</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}\mathrm{<span\; class="notranslate">\; lp</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; deg</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}\mathrm{<span\; class="notranslate">\; lp</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; min</span>}}_{\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; K</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; deg</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}\mathrm{<span\; class="notranslate">\; lp</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; deg</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}\mathrm{<span\; class="notranslate">\; lp</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$

${\mathrm{<span\; class="notranslate">\; g</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\stackrel{\mathrm{<span\; class="notranslate">\; \&Delta;</span>}}{<span\; class="notranslate">\; =</span>}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\stackrel{\mathrm{<span\; class="notranslate">\; \&Delta;</span>}}{<span\; class="notranslate">\; =</span>}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; G</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; G</span>}<span\; class="notranslate">\; \&cup;</span><span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; g</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; \}</span>$

2) calculate $S(g_k,g_{k+1}){\stackrel{G}{\&Right\; Arrow;}}_{+}{f}_{\mathrm{the\; s},k+1}={\mathrm{the\; y}}^{l_{k+1}}{f}_{0,k}-q_{\mathrm{the\; s},k}{f}_{0,k+1}$

3) calculate $f_{i,k}{\stackrel{G}{\&Right\; Arrow;}}_{+}{f}_{i,k+1}=f_{i,k}-q_{i,k}{f}_{0,k+1},$ where i≠0, i≠s.

The above steps have been completed as follows

$\left(\begin{array}{c}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\end{array}\right)<span\; class="notranslate">\; =</span>\left(\begin{array}{c}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; .</span>\mathrm{<span\; class="notranslate">\; k</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\end{array}\right)<span\; class="notranslate">\; ,</span>$

K _k+1 = {f _{1, k+1} ,..., f _{l, k+1} }

4) Corresponding to the above steps, calculate the coefficient matrix:

${\mathrm{<span\; class="notranslate">\; A</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\left[\begin{array}{c}{{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\end{array}\right]<span\; class="notranslate">\; =</span>\left[\begin{array}{c}{{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}{{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{{\mathrm{<span\; class="notranslate">\; l</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}}{{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}{{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ {{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}{{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span>}\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\\ <span\; class="notranslate">\; .</span>\end{array}\right]$

(4) Stop condition: until step 1, so that f _1,l =f _2,l =...=f _l,l =0.

(5) Output: G and coefficient matrix A ^(l) .

Sy2Sy realizes that by calculating the GB base G of K, along with calculating the generators A ₁ ^(l) ,..., A _l ^(l) of the combined Syzygy (K), pick out the smallest polynomial degree in each row vector A _i ^(l) OK, it is the solution needed for the synthesis (Synthesis) construction problem.

In this way, the problem of blind recognition of convolutional codes is transformed into a computing problem of Syzygy, and the computing complexity of the Sy2Sy algorithm is O(N ² ).

If it is a sequence synthesis, to find the characteristic ideal of the sequence C ₁ (x, y), then find the following ideal GB basis and the corresponding Syzygy:

K={f ₀ =x ^N+1 , f ₁ =C ₁ (x,y), f ₂ =y ^N+1 }

If blind recognition of convolutional codes is required, the following ideal GB basis and corresponding Syzygy are obtained:

K={x ^N+1 , C ₁ (x, y), . . . , C _k (x, y), y ^N+1 }

As long as the GB basis is calculated, the corresponding Syzygy will be obtained at the same time, and the main item of computational complexity is the computational complexity of calculating the GB basis.

We have proved theoretically that the computational complexity of the SY2SY algorithm is O(N ² ), where N is the observed amount of sampled input data. Therefore, the SY2SY algorithm is almost perfect in terms of computational complexity and space complexity.

To sum up, the present invention proposes a structured model for blind recognition of fault-tolerant channel coding without protocol communication, establishes a homogeneous key equation (HKME) describing the structured model, and provides a fast SY2SY algorithm for solving the HKME. The algorithm utilizes the algebraic structure of HKME, and determines the ideal combination that accompanies the calculation process through the calculation process of solving the ideal GB basis of the binary polynomial, and achieves the comprehensive structure from the combination.

The significant key equation KE proposed by Berlekamp is a special case of HKME of the present invention when k=1.

The BM algorithm proposed by Berlekamp and Massey is a special case of the SY2SY algorithm of the present invention when k=1.

The present invention has developed HKME and SY2SY algorithms into application software and chips. And, it is made into various products in the field of communication and information security, including: using limited observed sampling data to realize the comprehensive constructor of the minimum linear recursive generation device, the key generation synthesis device of the stream cipher, and the algebraic encoding parameter The application software for blind identification, cyclic code decoder, and fast solution of large-scale sparse linear equations involved in the decomposition of large numbers.

Description of drawings

Figure 1 Encoding of convolutional codes. g ₁ (D), g ₂ (D) are unknown polynomials that need to be solved, I(D) is an unknown information sequence polynomial, and C ₁ (D), C ₂ (D) are known finite-length codes word sequence polynomial. How to deduce the generator polynomial g ₁ (D) of convolutional code only from sequence C ₁ (D) of finite length, C ₂ (D), g ₂ (D) is what the homogeneous key module equation proposed by the present invention will describe question.

Figure 2 shows that the LRS synthesis problem is a special case of the blind recognition problem of convolutional codes.

Figure 3. Conventional fault-tolerant synthetic construction model.

Figure 4. Schematically shows a model for blind recognition of error-tolerant channel coding without protocol contact.

Detailed ways

The calculation process of the present invention is described below through an actual calculation example.

Calculation example

We have obtained two sequences: 111110111000001101

001011110010000111

Find the generator polynomial that can generate the 1/2 code rate convolutional code of these two sequences. set for this

f ₀ ＝x ¹⁷ +x ¹⁶ y+x ¹⁵ y ² +x ¹⁴ y ³ +x ¹³ y ⁴ +x ¹¹ y ⁶ +x ¹⁰ y ⁷

+x ⁹ y ⁸ +x ³ y ¹⁴ +x ² y ¹⁵ +y ¹⁷

f ₁ =x ¹⁸

f ₂ =x ¹⁵ y ² +x ¹³ y ⁴ +x ¹² y ⁵ +x ¹¹ y ⁶ +x ¹⁰ y ⁷

+x ⁷ y ¹⁰ +x ² y ¹⁵ +xy ¹⁶ +y ¹⁷

f ₃ =y ¹⁸

Step 0

f _0,0 ＝f ₀ , this step corresponds to step (1) of double-combination algorithm

(1,0) f_{0, 0}＝f₀ ＝x¹⁷+x¹⁶y+x¹⁵y²+x¹⁴ y³+x¹³y⁴+x¹¹y⁶+x< sup>10</sup>y⁷+x⁹y⁸+x³y¹⁴+x²y¹⁵+y¹⁷ (0,0)-(x+y)(1,0) f_1,0＝f_1,-1-(x+y)f₀ ＝x¹³y⁵+x¹²y⁶+x⁹y< sup>9</sup>+x⁴y⁴+x²y¹⁶+xy¹⁷ (0,1) f_{2, 0}＝f₂ ＝x¹⁵y²+x¹³y⁴+x¹²y< sup>5</sup>+x¹¹y⁶+x¹⁰y⁷+x⁷y¹⁰+x²y¹⁵+xy¹⁶+y<sup>17< /sup> (0,0) f_{3, 0}＝f₃ ＝y¹⁸

Wherein the first column of the table in the kth step represents the 1st column and the 3rd column of the matrix A ^(k+1) .

Step 1

f _{0, 1} = f _{2, 0} = f ₂ , this step corresponds to SY2SY algorithm step (3), step 1)

(0,1) f_{0, 1} = f_{2, 0} ＝x¹⁵y²+x¹³y⁴+x¹²y< sup>5</sup>+x¹¹y⁶+x¹⁰y⁷+x⁷y¹⁰+x²y¹⁵+xy¹⁶+y^{17< /sup> (0,0)-(x+y,0) f_{1, 1} = f_{1, 0} ＝x¹³y⁵+x¹²y⁶+x⁹y< sup>9}+x⁴y⁴+x²y¹⁶+xy¹⁷ y²(1, 0)+(x²+xy)(0, 1) f_{2, 1}＝y²f_{0, 0}+(x²+xy)f_2,0 ＝x¹⁴y⁵+x¹³y⁶+x¹⁰y< sup>9</sup>+x⁸y¹¹+x⁴y¹⁵+x³y¹⁶+x²y¹⁷ (0,0) f_{3, 1} = f_{3, 0} ＝y¹⁸

Step 2

f _{0, 2} = f _{1, 1} , this step corresponds to SY2SY algorithm step (3), step 1)

(x+y, 0) f_{0, 2} = f_{1, 1} ＝x¹³y⁵+x¹²y⁶+x⁹y< sup>9</sup>+x⁴y⁴+x²y¹⁶+xy¹⁷ y³(0, 1)+(x²+xy)(x+y, 0) f_{1, 2}＝y³f_{0, 1}+(x²+xy)f_{1, 1} corresponds to (3), 2) steps in the algorithm ＝x¹²y⁸+x⁷y¹³+x⁶y< sup>14</sup>+x⁵y¹⁵+x⁴y¹⁶ (y²，x²+xy)+x(x+y，0) f_{2, 2}＝f_{2, 1}+xf_{1, 1} corresponds to step (3), 3) in the algorithm ＝x⁸y¹¹+x⁴y¹⁵+x⁵y< sup>14</sup> (0,0) f_{3, 1} = f_{3, 0} ＝y¹⁸

Step 3

f _0,3 =f _1,2

(x³+xy²，y³) f_{0, 3}=f_{1, 2} ＝x¹²y⁸+x⁷y¹³+x⁶y< sup>14</sup>+x⁵y¹⁵+x⁴y¹⁶ y³(x+y, 0)+(x+y)(x³+xy², y^{3</ sup>) f_{1, 3}=y³f_{0, 2}+(x+y)f_{1, 2} ＝x⁹y¹¹+x⁸y¹³ (y²+x²+x²，x²+xy) f_{2, 3}＝f_{2, 2} ＝x⁸y¹¹+x⁴y¹⁵+x⁵y< sup>14} (0,0) f_{3, 3}＝f_{3, 2} ＝y¹⁸

Step 4

f _0,4 =f _2,3

(y²+x²+xy，x²+xy) f_{0, 4} = f_{2, 3} ＝x⁸y¹¹+x⁴y¹⁵+x⁵y< sup>14</sup> (x⁴+x²y²+x³y+y⁴ ，xy³+y⁴)+(xy+y²)(y²+x²+xy, x²+xy) f_{1, 4}＝f_{1, 3}+(xy+y²)f_{2, 3} ＝x⁶y¹⁵+x⁴y¹⁷ y³(x³+xy²，y³)+(x<sup>4</sup >+xy³+y⁴)(y²+x²+xy, x²+xy) f_{2, 4}＝y³f_{0, 3}+(x⁴+xy<sup>3< /sup>+y⁴)f_2,3 ＝x⁷y¹⁶ (0,0) f_{3, 4}＝f_{3, 3} ＝y¹⁸

Step 5

f _0,5 =f _1,4

(x⁴+x²y², y⁴+x³y ) f_{0, 5} = f_{1, 4} ＝x⁶y¹⁵+x⁴y¹⁷ y⁴(y²+x²+xy, x²+xy)+(x²+y²)(x⁴+x²y², y⁴+x³y) f_{1, 5}＝y⁴f_{0, 4}+(x²+y<sup>2< /sup>)f_{1, 4} =0 (xy⁵+x⁴y²+x⁶+x⁵y +y⁶，y⁶+x⁶+x⁵y+x<sup>3</sup >y³+xy⁵)+xy(x⁴+x²y² sup>，y⁴+x³y) f_{2, 5} = f_{2, 4}+xyf_{1, 4} =0 (0,0) f_{3, 4} = f_{3, 3} ＝y¹⁸

Step 6

f _0,6 = f _3,5

(0,0) f_{0, 6} = f_{3, 5} ＝y¹⁸ (x⁶+xy⁵+y⁶, x⁵y+x<sup>3</sup >y³+xy⁵+y⁶) f_{1, 6}＝f_{1, 5} ＝0 (x⁶+x⁴y²+x³y³+xy ⁵+y⁶, x⁶+x⁵y+x⁴y ²+x³y³+y⁶) f_{2, 6}＝f_{2, 5} ＝0 y³(x⁴+x²y², y⁴+yx ³) f_{3, 6}＝y³f_{0, 5}+(x⁶+x<sup>2< /sup>y⁴)f_{3, 5} ＝0

Get the GB base G={f _0,0 , f _0,1 , f _0,2 , f _0,3 , f _0,4 , f _0,5 , f _0,6 }, in the above box, the first column constitutes The matrix A ^(l) is obtained. Selecting the row with the smallest number of times (i.e. the second row) in A ^(l) is the solution of the SY2SY algorithm, here, the generator polynomial of the convolutional code is also obtained:

H ₁ ＝x ⁶ +x ⁴ y ² +x ³ y ³ +xy ⁵ +y ⁶ , H ₂ ＝x ⁶ +x ⁵ y+x ⁴ y ² +x ³ y ³ +y ⁶ .

Claims (2)

1. the communication channel blind identification method for coding parameters of an error-tolerant code, it is characterized in that designing the structural model of the blind identification of fault-tolerant chnnel coding of a no-protocol contact, set up the homogeneous crucial modular equation HKME of this structural model, the SY2SY pairing algorithm of this homogeneous crucial modular equation HKME is found the solution in proposition, this model is carried out rapid solving, thereby realize the quick blind identification of the fault-tolerant chnnel coding of no-protocol contact; Wherein homogeneous crucial modular equation HKME is:

Ask F[x, y]-Mo

Γ ^(k)＝{(H ₁，...，H _k)∈F[x，y] ^k|H ₁C ₁(x，y)+…+H _kC _k(x，y)≡0mod I} (2)

Minimum standard generator:

Wherein, F is a territory, F[x, y] be the polynomial ring on the F;

C _i(x，y)＝c _i0y ^N+c _i1xy ^N-1+c _i2x ²y ^N-2+…+c _iNx ^N，i＝1，2，…，k (1)

Be F[x, y] in t quantic; I=＜x ^N+1, y ^N+1Be F[x, y] by x ^N+1, y ^N+1Generated ideal;

The concrete steps of said SY2SY pairing algorithm are as follows:

Input: the homogeneous set K={f of strict ordering ₀, f ₁..., f _l}

Output: GB base G makes＜G 〉=＜K〉and the generators set of syzygies Syzygy (K);

(1) initial:

If (f _0,0, f _1,0..., f _{L, 0})=(f ₀, f ₁..., f _l), and establish:

(deg _ylp(f ₀)，deg _xlp(f ₀))＝min _{i＝0，1，...，l}(deg _ylp(f _i)，deg _xlp(f _i))，

If g ₀=f ₀, A ⁽⁰⁾=I is a unit matrix, G={g ₀, K ₀={ f ₁..., f _l;

(2) suppose that k step finished following algorithm:

Selected go out to gather G and by G reduction residual polynomial set K _k, satisfy following relation:

<G∪K _k>＝<K>，

K=0 wherein, 1 ..., l. G={g ₀, g ₁..., g _k, K _k={ f _{1, k}, f _{2, k}..., f _{L, k},

And calculated coefficient matrices A ^(k)Satisfy

$\left(\begin{array}{c}{f}_{0,k}\\ f_{1,k}\\ .\\ .\\ .\\ f_{l,k}\end{array}\right)=A^{\left(k\right)}\left(\begin{array}{c}{f}_{\mathrm{0,0}}\\ f_{1,0}\\ .\\ .\\ .\\ f_{l,0}\end{array}\right),$

And note A _i ^(k)It is matrix A ^(k)I capable, i=0,1 ..., l,

(3) the k+1 step will be carried out following calculating:

1. select f _{0, k+1}, f _{0, k+1}, be K _kIn a special polynomial f _{S, k}, satisfy

$({\mathrm{deg}}_y\mathrm{lp}\left(f_{s,k}\right),{\mathrm{deg}}_x\mathrm{lp}\left(f_{s,k}\right))={\min }_{f\&Element;K_k}({\mathrm{deg}}_y\mathrm{lp}\left(f_{i,k}\right),{\mathrm{deg}}_y\mathrm{lp}\left(f_{i,k}\right)),$

$g_{k+1}\stackrel{\mathrm{\&Delta;}}{=}{f}_{0,k+1}\stackrel{\mathrm{\&Delta;}}{=}{f}_{s,k},G=G\&cup;\left\{g_{k+1}\right\}$

2. calculate $S(g_k,g_{k+1}){\stackrel{G}{\&RightArrow;}}_{+}{f}_{s,k+1}=y^{l_{k+1}}{f}_{0,k}-q_{s,k}{f}_{0,k+1}$

3. calculate $f_{i,k}{\stackrel{G}{\&RightArrow;}}_{+}{f}_{i,k+1}=f_{i,k}-q_{i,k}{f}_{0,k+1},$ I ≠ 0 wherein, i ≠ s;

1., 2., 3. above-mentioned steps has finished following calculating

K _k+1＝{f _1，k+1，…，f _l，k+1)

4) corresponding above-mentioned steps 1., 2., 3., the design factor matrix:

(4) stop condition:, make f up to l step _{1, l}=f _{2, l}=...=f _{L, l}=0;

(5) output: GB base G and coefficient matrices A ^(l), be separating of homogeneous key equation HKME, wherein, coefficient matrices A ^(l)Generators set for syzygies Syzygy (K).

2. method according to claim 1 is characterized in that at the vectorial A of each row _i ^(l)In pick out the row of degree of polynomial minimum, promptly get separating of synthesis structure problem.

Images