CN102882534B - The Parallel Implementation method of RS coding and device - Google Patents

Abstract

The invention discloses Parallel Implementation method and device that a kind of RS encodes, wherein, said method comprises the following steps: the generator polynomial G (x) determining RS code according to parameter m, n, k, and judges whether k and (n-k) can be divided exactly by H; Whether can be divided exactly by H according to (n-k), select corresponding parallel encoding implementation structure; The coefficient of constant coefficient multiplier in parallel encoding implementation structure is calculated according to generator polynomial G (x); Whether can be divided exactly by H according to k, determine whether to need zero padding and process of zero-suppressing; According to n, k, H parameter, determine feedback door control signal in parallel encoding implementation structure, input enable and export the control selecting signal; Export parallel encoding result.The present invention is applicable to GF(2 ^m) upper any RS pattern is not more than Parallel Implementation k) at any degree of parallelism H(H.

Description

The Parallel Implementation method of RS coding and device

Art

The present invention relates to optical communication technique, be specifically related to Parallel Implementation method and the device of RS coding.

Background technology

Along with optical communication is to ultrahigh speed, vast capacity future development, SDH (Synchronous Digital Hierarchy) (synchronous digitalhierarchy, referred to as SDH) structure, Dense Waveleng Division Multiplexing (Dense Wavelength DivisionMultiplexing, referred to as DWDM) system, the technology such as all optical network and optical cross connect constantly apply in fiber optic communication systems, makes line speed reach 10Gbps, 40Gbps and 100Gbps even higher.

The validity and reliability of transmission is conflict: on the one hand, the significantly raising of transmission rate, dispersion, nonlinear effect, receiver performance also becomes the principal element of system for restricting performance.On the other hand, the expansion of power system capacity also can cause the crosstalk between the light signal of a series of such as each roads, signal synchronous, regularly, recover problem, these problems all can cause the generation of error code in communication process, thus reduce the reliability of communication, the reduction of communication reliability finally constrains again the raising of communication quality, the prolongation of communication distance, multiplexed large-scale application, and the reduction of communication equipment cost, therefore greatly hinders further developing of optical communication.

Forward error correction (FEC) technology is one of key technology solved the problem, FEC technology increases certain redundant code according to certain coding rule before data transmission by coding side, the data originally without correlation are made to produce correlation, at decoding end then according to decoding rule, the data utilizing redundancy to produce are to correct the error code produced in channel, recover to send data, thus reach Optical Signal To Noise Ratio (the optical signal to noise ratio reducing receiving terminal, referred to as OSNR) tolerance limit, reduce the object of required transmitting power.Adopt the coding gain that FEC obtains, greatly reduce the error rate, effectively improve communication reliability thus reach and improve systematic function, reduce the object of system cost, and reed-solomon (Reed-Solomon, referred to as RS) code has multi-system Bo Sichadehulihuo elder brother lattice nurse code (the Bose Chaudhuri Hocquenghem of very strong error correcting capability as a class, referred to as BCH), the performance excellent because of it and high-throughput, be widely used in the various fields such as radio communication, optical transport.

At present, RS is coded in the method usually adopting serial code when realizing, as shown in Figure 1, in Fig. 1 for d type flip flop, with be respectively galois field GF(2 ^m) (Galois Field, referred to as GF, m be greater than zero integer, determine that galois field is GF(2 ^m)) on constant coefficient multiplier and adder (i.e. XOR gate), for the data selector of alternative, the information code element W exported as input is selected still to verify code element C by output_sel signal, for gate, feedback_gate and input_en signal is respectively as an input of two gates, for whether controlling the information code element of feedback signal and input by this gate, the implementation structure of method shown in Fig. 1 is mainly made up of the linear feedback shift register (LinearFeedback Shift Register, referred to as LFSR) of (n-k) level (n-k) individual d type flip flop and (n-k) individual constant coefficient multiplier and (n-k) individual XOR gate.In the method, a code element and then code element is encoded, a code element can only be processed at every turn, need to carry out the cataloged procedure that multi-shift just can complete a code word, this method not only code efficiency is not high, and the throughput of data is not high yet, seriously govern the raising of whole system transmission rate.

Summary of the invention

Technical problem to be solved by this invention is that solution RS code code efficiency is not high, the problem that restriction whole system transmission rate improves.

In order to solve the problems of the technologies described above, the technical solution adopted in the present invention is to provide a kind of Parallel Implementation method and device that RS encodes, can the multiple code element of single treatment, significantly improves the efficiency of RS code coding, meets the requirement of whole system transmission rate.

The Parallel Implementation method of RS coding comprises the following steps:

Determine the generator polynomial G (x) of RS code according to parameter m, n, k, m be greater than zero integer, determine that galois field is GF(2 ^m), n is the length of RS code word, and k is the length of information bit in RS code word, and H is the required degree of parallelism realized;

Whether can be divided exactly by H each feedback loop progression determining H linear feedback shift register LFSR according to (n-k); When (n-k) can be divided exactly by H, described feedback loop progression is (n-k)/H; When (n-k) can not be divided exactly by H, the feedback progression of feedback loop 0 to feedback loop r is A1, feedback loop (r+1) is (H-A1) to the feedback progression of feedback loop (H-1), and A1 rounds downwards for (n-k)/H, and r is (n-k) remainder divided by H gained;

According to formula $x^{n-k+j}\≡{\mathrm{\Σ}}_{i=0}^{n-k-1}{g}_i^j{x}^i\mathrm{mod}G\left(x\right)$ Obtain the coefficient of each constant coefficient multiplier i=0,1 ..., n-k-1; J=0,1 ..., H-1;

Whether can be divided exactly by H according to k, determine whether to need zero padding and process of zero-suppressing, when k can not be divided exactly by H, before residue R code element after T process, mend (H-R) individual zero symbol; When k can be divided exactly by H, without the need to zero padding and process of zero-suppressing; R is the remainder of k divided by H gained, k=T*H+R;

According to parameter n, k, H, determine corresponding feedback door control signal, input enable and export selection signal;

Parallel encoding result is exported by H road LFSR.

In the above-mentioned methods, described G (x) is according to parameter m, n, k and GF(2 ^m) origin multinomial, in conjunction with tabling look-up or utilizing matlab instrument to obtain.

In the above-mentioned methods, matlab instrument is utilized to obtain the coefficient of described constant coefficient multiplier according to G (x)

Present invention also offers a kind of RS code device, comprise H road LFSR and H × (n-k) individual GF(2 ^m) on constant coefficient multiplier, LFSR described in each road of described H road LFSR has (n-k) individual XOR gate of being connected in series and (n-k) individual d type flip flop, and described XOR gate and described d type flip flop interval are arranged; Every H LFSR is one group, in units of group, circulation connects described H road LFSR successively in order, when (n-k) can be divided exactly by H, the feedback loop progression of described LFSR is (n-k)/H, when (n-k) can not be divided exactly by H, the feedback loop progression of described LFSR is no longer consistent, the feedback progression of feedback loop 0 to feedback loop r is A1, A1=(n-k)/H rounds downwards (A1 is for being not more than the maximum integer of (n-k)/H), feedback loop (r+1) to the feedback progression of feedback loop (H-1) is H-A1, r is (n-k) remainder divided by H gained;

H × (n-k) individual GF(2 ^m) on constant coefficient multiplier the coefficient of each constant coefficient multiplier according to formula determine; Wherein: m be greater than zero integer, determine that galois field is GF(2 ^m); N is the length of RS code word; K is the length of information bit in RS code word; H is the required degree of parallelism realized; I=0,1 ..., n-k-1; J=0,1 ..., H-1.

The present invention, compared with traditional coding method and prior art, can a parallel processing H code element, but computing consumption or hardware implementing resource can not linearly increase, and the more important thing is, this structure or method go for GF(2 ^m) upper any RS pattern is not more than Parallel Implementation k) at any degree of parallelism H(H, thus have great flexibility.

Accompanying drawing explanation

Fig. 1 is existing GF(2 ^m) on realize the schematic diagram of RS code device;

Fig. 2 is the flow chart of RS coding Parallel Implementation method provided by the invention;

Fig. 3 is the first execution mode schematic diagram of RS code device provided by the invention;

Fig. 4 is RS code device the second execution mode schematic diagram provided by the invention;

Fig. 5 is the local detail schematic diagram of Fig. 4;

Fig. 6 is the course of work of the RS code device of Parallel Implementation;

Fig. 7 is instantiation schematic diagram during the second execution mode H=7 shown in Fig. 4.

Embodiment

Below in conjunction with accompanying drawing, the present invention is described in detail.

RS provided by the invention encodes Parallel Implementation method as shown in Figure 2, comprises the following steps:

Step S10, determines the generator polynomial G (x) of RS code according to parameter m, n, k, and judges whether k and (n-k) can be divided exactly by H.Wherein: m be greater than zero integer, determine that galois field is GF(2 ^m), n is the length of RS code word, and k is the length of information bit in RS code word, and H is the required degree of parallelism realized, and namely needs the he number of encoder single treatment.G (x) can according to parameter m, n, k and GF (2 ^m) origin multinomial, in conjunction with tabling look-up or utilizing matlab or other instrument to generate.

Whether step S20, can be divided exactly by H each feedback loop progression determining H road LFSR according to (n-k), thus determine to select corresponding parallel encoding implementation structure.

When (n-k) can be divided exactly by H, as shown in Figure 3, wherein the feedback loop progression of LFSR is (n-k)/H to its implementation structure.In Fig. 3: for d type flip flop, with be respectively GF(2 ^m) on constant coefficient multiplier and adder (i.e. XOR gate), for the data selector of alternative, the information code element W exported as input is selected still to verify code element C by output_sel signal, for gate, feedback_gate and input_en signal respectively as an input of two gates for whether controlling the information code element of feedback signal and input by this gate.Wherein (n-k) individual d type flip flop, H × (n-k) individual GF(2 ^m) on constant coefficient multiplier and (n-k) individual GF(2 ^m) on two input summers and (n-k) individual GF(2 ^m) on H input summer combine constitute H displacement feedback loop, Mei Tiao loop, this H loop all can see the LFSR of (n-k)/H level as, final stage output state by LFSR between loop is connected with each other, the LFSR concurrent working of H road.Like this when the Parallel Implementation device shown in Fig. 3 carries out a shifting function, be equivalent to the existing serial code device shown in Fig. 1 and carry out H shifting function, therefore, H information code element can be sent in the parallel encoding device shown in Fig. 3 simultaneously, thus once can complete the parallel processing of H information code element.

When (n-k) can not be divided exactly by H, its implementation structure as shown in Figure 4,5, with the Parallel Implementation device shown in Fig. 3 unlike: in H LFSR loop, the number of shift register stages in every bar loop is no longer consistent, the feedback progression of feedback loop 0 to feedback loop r is A1, A1=(n-k)/H rounds downwards, and feedback loop (r+1) to the feedback progression of feedback loop (H-1) is H-A1, r is (n-k) remainder divided by H gained.

S30, the coefficient of constant coefficient multiplier in the Parallel Implementation device according to generator polynomial G (x) calculating chart 3 or Fig. 4 i=0,1 ..., n-k-1; J=0,1 ..., H-1.As shown in Figure 3 and Figure 4, total H × (n-k) individual GF(2 in Parallel Implementation device ^m) on constant coefficient multiplier, need H × (n-k) individual coefficient according to formula calculated by coding or other instruments.

Whether S40, can be divided exactly by H according to k, and determining whether needs zero padding and process of zero-suppressing;

When k can not be divided exactly by H, R is made to be the remainder that k obtains divided by H, Parallel Implementation device processes H code element at every turn, after being through T process, (wherein R is the remainder of k divided by H gained to remain R code element, i.e. k=T × H+R), now need a code word W (k-1) before each coding, ..., W (1), a high position for k the code elements such as W (0) mends (H-R) individual zero symbol, so just he number in the code word of input can be gathered into (k+H-R), can be divided exactly by H, because in Parallel Implementation device, the state of LFSR is zero before encoding, therefore zero padding process can not affect the coding result of k information code element below, just need correspondingly the zero symbol mended before to be removed when exporting.When k can be divided exactly by H, without the need to zero padding and process of zero-suppressing.

S50, according to n, k, H parameter, determines feedback door control signal in Parallel Implementation device, inputs enable and export the control selecting signal;

In a particular application, when encode enable invalid time, Parallel Implementation device needs to carry out former state output to data, and the feedback gate-control signal feedback_gate now shown in Fig. 3 and Fig. 4 is invalid, input enable input_en invalid, export and select signal output_sel to select to export for input data; When encode enable effective time, Parallel Implementation device completes the cataloged procedure needs of a code word secondary feedback shift, front in secondary shifting process, feedback_gate is effective for feedback gate-control signal, inputs enable input_en effective, exports and selects signal output_sel to select to export for input data, ensuing in secondary shifting process, feedback gate-control signal feedback_gate is still effective, inputs enable input_en invalid, exports and selects signal output_sel to select to export as LFSR State-output.

S60, exports parallel encoding result by H road LFSR.

Step S60 comprises following steps:

S601: to input data carry out zero padding process (note zero padding processing module herein according to step S40 in above-mentioned Parallel Implementation flow process determine in embody rule the need of);

S602: by after zero padding process or without after zero padding process individual information code element is divided into group, often organize H information code element, send into successively in the structure shown in Fig. 3 or Fig. 4, each feeding one group of H code element, H road simultaneously in the encoder LFSR that walks abreast carries out a shifting function, now feed back gate-control signal feedback_gate effective, export simultaneously and select signal output_sel to select to export for input data, therefore in this process encoder export be input information code element, here corresponding with zero padding process, for some situation, may also need the information code element of output to carry out process of zero-suppressing;

Afterbody H of every primary Ioops neutral line feedback shift register LFSR exports q _n-k-1, q _n-k-2..., q _n-k-H-1, q _n-k-Hwith corresponding input W (k-1) ..., W (1), W (0), through GF(2 ^m) on add operation (XOR) after feed back to corresponding constant multiplier, again after multiplication and add operation, feed back to the different progression of the shift register in corresponding loop, thus change the state of linear feedback shift register.

S603: pass through after secondary shifting function, after zero padding process or without after zero padding process individual information code element has all moved in encoder, and now the enable closedown of encoder input input_en, no longer moves into information code element, exports and selects signal output_sel to select to export for LFSR State-output, and in this process, encoder can be by individual verification code element shifts out successively.

Therefore, see on the whole, in input while individual information code element, RS encoder also can export successively individual information code element and corresponding individual verification code element.

As shown in Figure 3, this device comprises the first execution mode of RS code device provided by the invention:

H road LFSR, LFSR described in each road has (n-k) individual XOR gate and (n-k) individual d type flip flop of being connected in series, described XOR gate and described d type flip flop interval are arranged, every H LFSR is one group, in units of group, circulation connects described H road LFSR successively in order, (n-k) can be divided exactly by H, and the feedback loop progression of described LFSR is (n-k)/H.

H × (n-k) individual GF(2 ^m) on constant coefficient multiplier the coefficient of each constant coefficient multiplier according to formula determine.Wherein: m be greater than zero integer, determine that galois field is GF(2 ^m); N is the length of RS code word; K is the length of information bit in RS code word; H is the required degree of parallelism realized; I=0,1 ..., n-k-1; J=0,1 ..., H-1.

Gate, for the control to whole code device, comprise and whether input data, whether LFSR feeds back, and selecting to export data is that information code element still verifies code element.

Fig. 4 is the second execution mode schematic diagram of RS code device provided by the invention, as shown in Figure 4, the difference of this execution mode and the first execution mode is: (n-k) can not be divided exactly by H, therefore the feedback progression of feedback loop 0 to feedback loop r is A1, feedback loop (r+1) is (H-A1) to the feedback progression of feedback loop (H-1), A1 rounds downwards for (n-k)/H, and r is (n-k) remainder divided by H gained.

Below in conjunction with example GF(2 ⁸) on the Parallel Implementation of RS (248,216) encoder under degree of parallelism H=7 be described in detail, as shown in Figure 7.

In this example, the exponent number m=8 of galois field, RS code code length n=248, k=216 is RS (255,223) shorten code, degree of parallelism H=7, the parallel encoder of realization is shifted at every turn and can processes 7 code elements (each code element 8bit binary number), namely 56bit, its specific implementation step is as follows:

Step S10: (generator polynomial can according to GF (2 here to determine the generator polynomial G (x) of RS code according to parameter m, n, k ⁸) origin multinomial combine and table look-up or utilize matlab or other instrument to obtain, just repeat no more here), simultaneously k=216, n-k=32, H=7, k and (n-k) all can not be divided exactly by H.

Step S20: due to n-k=32, H=7, (n-k) can not be divided exactly by H, thus should select the implementation structure shown in Fig. 4.

Step S30: according to the generator polynomial G (x) of the RS code determined in step S10, and the formula 1 described in summary of the invention, calculate GF (2 in structure shown in Fig. 4 ⁸) coefficient of upper constant coefficient multiplier wherein i=0,1 ..., 31, j=0,1 ..., 6, one has 192 coefficient (coefficients here matlab or other instrument can be used to calculate).

Step S40: due to k=216, H=7, k can not be divided exactly by H, therefore need to carry out zero padding operation to input data, and k=216 is 6 divided by H=7 gained remainder, so need benefit 1 zero symbol (each code element 8bit binary number), so just obtain 217 information code elements (comprising 1 zero symbol), similarly, also to carry out operation of zero-suppressing for the information code element exported, introduce before 1 zero symbol is removed.

Step S50: when encode enable invalid time, encoder needs to carry out former state output to data, and the feedback gate-control signal feedback_gate now shown in Fig. 4 is invalid, exports and selects signal output_sel to select to export for input data; When encode enable effective time, cataloged procedure encoder in this example being completed to a code word needs 36 feedback shifts, gate-control signal feedback_gate is fed back effective in front 31 shifting processes, export and select signal output_sel to select to export for input data, what now export is information code element, in ensuing 5 shifting processes, feedback_gate is still effective for feedback gate-control signal, export and select signal output_sel to select to export as LFSR State-output, what now export is verification code element.

Comprehensively above-described six steps, RS (248 as shown in Figure 6 can be obtained, 216) parallel realization structure of encoder under degree of parallelism H=7, in the structure shown here, one total H=7 displacement feedback loop works simultaneously, the progression of the linear feedback shift register LFSR in each loop is 5 or 4, the register of total total n-k=32 m=8bit, be equivalent to the LFSR of LFSR and 34 grades 32 of work in series in conventional implementation grades of LFSR being split into 45 grades of concurrent working, be connected with each other by the final stage output state in each loop between these 7 LFSR loops.In this example, k can not be divided exactly by H, thus to carry out zero padding process for input information code element, also correspondingly carry out process of zero-suppressing at output, in addition, n in this example can not be divided exactly by H, in actual applications, each timeticks process H code element, so during continuous process for multiple code word, last several code elements of each code word need and before next code word, several code element forms a beat of data, also will consider the Bonding Problem between code word.

The present invention is not limited to above-mentioned preferred forms, and anyone should learn the structural change made under enlightenment of the present invention, and every have identical or close technical scheme with the present invention, all falls within protection scope of the present invention.

Claims (5)

1. The Parallel Implementation method of 1.RS coding, is characterized in that, comprise the following steps:

   Determine the generator polynomial G (x) of RS code according to parameter m, n, k, m be greater than zero integer, determine that galois field is GF(2 ^m), n is the length of RS code word, and k is the length of information bit in RS code word, and H is the required degree of parallelism realized;

   Whether can be divided exactly by H each feedback loop progression determining H linear feedback shift register LFSR according to (n-k); When (n-k) can be divided exactly by H, described feedback loop progression is (n-k)/H; When (n-k) can not be divided exactly by H, the feedback progression of feedback loop 0 to feedback loop r is A1, feedback loop (r+1) is (H-A1) to the feedback progression of feedback loop (H-1), and A1 rounds downwards for (n-k)/H, and r is (n-k) remainder divided by H gained;

   According to formula obtain the coefficient of each constant coefficient multiplier i=0,1 ..., n-k-1; J=0,1 ..., H-1;

   Whether can be divided exactly by H according to k, determine whether to need zero padding and process of zero-suppressing, when k can not be divided exactly by H, before residue R code element after T process, mend (H-R) individual zero symbol; When k can be divided exactly by H, without the need to zero padding and process of zero-suppressing; R is the remainder of k divided by H gained, k=T*H+R;

   According to parameter n, k, H, determine corresponding feedback door control signal, input enable and export selection signal;

   Parallel encoding result is exported by H road LFSR.
2. 2. the Parallel Implementation method of RS coding as claimed in claim 1, is characterized in that,

   Described G (x) is according to parameter m, n, k and GF(2 ^m) origin multinomial, in conjunction with tabling look-up or utilizing matlab instrument to obtain.
3. 3. the Parallel Implementation method of RS coding as claimed in claim 1, is characterized in that,

   Matlab instrument is utilized to obtain the coefficient of described constant coefficient multiplier according to G (x)
4. 4.RS code device, is characterized in that, comprising:

   H road LFSR, LFSR described in each road have (n-k) individual XOR gate and (n-k) individual d type flip flop of being connected in series, and described XOR gate and described d type flip flop interval are arranged;

   H × (n-k) individual GF(2 ^m) on constant coefficient multiplier, every H LFSR is one group, in units of group in order successively circulation connect described H road LFSR; (n-k) can be divided exactly by H, and the feedback loop progression of described LFSR is the coefficient of (n-k)/H, each constant coefficient multiplier according to formula $x^{n-k+j}\≡{\mathrm{\Σ}}_{i=0}^{n-k-1}{g}_i^j{x}^i\mathrm{mod}G\left(x\right)$ Determine;

   Wherein: m be greater than zero integer, determine that galois field is GF(2 ^m); N is the length of RS code word; K is the length of information bit in RS code word; H is the required degree of parallelism realized; I=0,1 ..., n-k-1; J=0,1 ..., H-1.
5. The Parallel Implementation device of 5.RS coding, is characterized in that, comprising:

   H road LFSR, LFSR described in each road have (n-k) individual XOR gate and (n-k) individual d type flip flop of being connected in series, and described XOR gate and described d type flip flop interval are arranged;

   H × (n-k) individual GF(2 ^m) on constant coefficient multiplier, every H LFSR is one group, in units of group in order successively circulation connect described H road LFSR; (n-k) can not be divided exactly by H, and the feedback progression of feedback loop 0 to feedback loop r is A1, feedback loop (r+1) is (H-A1) to the feedback progression of feedback loop (H-1), and A1 rounds downwards for (n-k)/H, and r is (n-k) remainder divided by H gained; The coefficient of each constant coefficient multiplier according to formula $x^{n-k+j}\≡{\mathrm{\Σ}}_{i=0}^{n-k-1}{g}_i^j{x}^i\mathrm{mod}G\left(x\right)$ Determine;

   Wherein: m be greater than zero integer, determine that galois field is GF(2 ^m); N is the length of RS code word; K is the length of information bit in RS code word; H is the required degree of parallelism realized; I=0,1 ..., n-k-1; J=0,1 ..., H-1.