CN102025379B - Decoder of error correction code and its error correction value calculation device - Google Patents

Abstract

The invention relates to a decoder of an error correction code and an error correction value calculating device thereof. The decoder of the error correction code is used for generating error correction information according to a received signal, and the error correction information comprises a plurality of error correction values respectively corresponding to a plurality of error positions. The decoder of the error correction code comprises a syndrome calculation device and an error correction value calculation device. The syndrome calculation device is used for receiving the received signal and generating a plurality of syndromes according to the received signal. The error correction value calculating device comprises a first calculating module and a second calculating module; for each error position, the first calculation module obtains a syndrome finite body division result of each syndrome according to a specific power of an original root of a generator polynomial; the second calculation module obtains an error correction value of the error position according to the syndrome finite body division result.

Description

The decoder of error correcting code and error correction value calculation apparatus thereof

Technical field

The present invention relates to a kind of error correcting code (Error Correction Code, ECC) correlation technique, particularly relate to decoder and the error correction value calculation apparatus thereof of the error correcting code of a kind of application cycle code (cyclic code).

Background technology

In recent years, because the progress of digital storage technology and mechanics of communication, the speed of data access and transmission is more and more faster; But, in the process of data access and transmission, disturb because transmission medium or passage very easily are subject to noise, so error detection and corrigendum mechanism also become more and more important.Generally speaking, present Satellite Communication System, digital television system, various digital audio-video recording medium etc., be mistake in using more code to promote the reliability of data access and transmission.And in various error correcting codes, cyclic code is a kind of quite common application.

A kind of error detection method for correcting of existing application cycle code comprises the following step: (a) receive a signal; (b) obtain a plurality of syndromes (syndrome) according to this signal that has received; (c) according to described syndrome and utilize Bai Liken-Mei Xi algorithm (Berlekamp-MasseyAlgorithm), in the hope of an error location polynomial (error locator polynomial); And (d) carry out Qian Shi according to this error location polynomial and look for one's roots (Chien search), obtaining at least one errors present and to an error correction value that should errors present, and this signal that has received is carried out error correction.The theoretical foundation relevant with this existing method is at " The Art of ErrorCorrecting Coding, Robert H.Morelos-Zaragoza, Second Edition, JohnWiley﹠amp; Sons, 2006 " and in " Fundamentals Of Error-Correcting Codes, W.Cary Huffman and Vera Pless, CAMBRIDGE UNIVIVERSITY PRESS, 2003 " two works detailed explaining arranged all.

Yet above-mentioned existing method after trying to achieve syndrome, is to utilize Bai Liken-Mei Xi algorithm or other algorithms of equal value to obtain error location polynomial, cooperates Qian Shi to look for one's roots again and obtains iteratively errors present, and required time complexity is higher.Under this environment for use in the past, because the speed of data access and transmission is slower, usually can cause serious problem and delay; But because present computer system usefulness and transmission rate greatly promote, in order to meet existing environment for use, often need to utilize a large amount of circuit, or utilize the mode of the clock pulse frequency of raising data processing, can satisfy and in required time, finishing the decoding action; And these modes can improve hardware cost usually, or increase system power consumption.

Summary of the invention

The object of the invention is to, a kind of decoder and error correction value calculation apparatus thereof of novel error correcting code are provided, technical problem to be solved is to make it after trying to achieve required syndrome, and computing and circuit that can low complex degree be directly tried to achieve error correction value and errors present.

The object of the invention to solve the technical problems realizes by the following technical solutions.The decoder of a kind of error correcting code that proposes according to the present invention, produce an error correction information in order to receive signal according to one, for this reception signal is carried out error detection and corrigendum, this reception signal is after an original message is encoded into a circulation code word in a transmission end by a generation multinomial, to be received in a receiving terminal through a channel transfer; The decoder of this error correcting code comprises: a syndrome calculation element, in order to receive this reception signal and to produce according to this a plurality of syndromes with manipulative indexing; An and error correction value calculation apparatus, in order to receive described syndrome and to produce according to this this error correction information, this error correction information comprises respectively a plurality of error correction values of corresponding a plurality of errors presents, this error correction value calculation apparatus comprises one first computing module and one second computing module, this first computing module and this second computing module are to carry out following calculating, to produce this error correction value of corresponding each errors present: this first computing module is tried to achieve the limited body result of division of a syndrome of each syndrome according to a specific power of a primitive root of this generator polynomial, and this specific power is relevant with the manipulative indexing of this errors present and this syndrome; And this second computing module is tried to achieve a limited body addition results as this error correction value according to the limited body result of division of described syndrome.

The object of the invention to solve the technical problems also can be applied to the following technical measures to achieve further.

Preferably, the decoder of aforesaid error correcting code, wherein this syndrome calculation element is according to receiving the signal multinomial to receiving one of signal, try to achieve at least one known syndrome, try to achieve at least one unknown syndrome according to this known syndrome again, described syndrome comprises this known syndrome and this unknown syndrome.

Preferably, the decoder of aforesaid error correcting code, wherein for each syndrome, this first computing module is take this syndrome as dividend, and take this specific power of this primitive root as divisor, tries to achieve the limited body result of division of this syndrome.

Preferably, the decoder of aforesaid error correcting code, wherein this syndrome calculation element is according to receiving the signal multinomial to receiving one of signal, try to achieve at least one known syndrome, try to achieve at least one unknown syndrome according to this known syndrome again, described syndrome comprises this known syndrome and this unknown syndrome.

Preferably, the decoder of aforesaid error correcting code, wherein for each syndrome, this first computing module is take this syndrome as dividend, and take this specific power of this primitive root as divisor, tries to achieve the limited body result of division of this syndrome.

Preferably, the decoder of aforesaid error correcting code wherein is this circulation code word of n for length, with described error correction value and respectively corresponding described errors present with an error polynomial Expression, e _jRepresent this error correction value of j errors present, for each error correction value e _j, the limited body result of division of this syndrome of each syndrome that this first computing module of this error correction value calculation apparatus is obtained is S _i/ β ^Ji, S _iRepresent the i syndrome of this error polynomial, its manipulative indexing is i, and β is the primitive root of this generator polynomial.

Preferably, the decoder of aforesaid error correcting code, wherein this first computing module of this error correction value calculation apparatus comprises a limited body constant multiplier, this first computing module is to utilize this limited body constant multiplier to calculate i syndrome S _iWith default constant 1/ β ^JiProduct, to obtain S _i/ β ^Ji

Preferably, the decoder of aforesaid error correcting code, wherein this syndrome calculation element is all syndromes that produce this error polynomial, for each error correction value e _j, this second computing module of this error correction value calculation apparatus is to add up the limited body result of division of described syndrome, to obtain this error correction value $e_j=\underset{i=0}{\overset{n-1}{\mathrm{\Σ}}}(S_i/{\mathrm{\β}}^{j\·i}).$

Preferably, the decoder of aforesaid error correcting code, wherein each syndrome S of producing of this syndrome calculation element _iBelong to a generation and characterize the shape value set, i ∈ R, R are the set of the representative element of all n time cyclotomy coset.

Preferably, the decoder of aforesaid error correcting code is wherein for each error correction value e _j, this second computing module of this error correction value calculation apparatus is a mark mapping value Tr who calculates the limited body result of division of this syndrome of each syndrome _K/F(S _i/ β ^Ji), add up again described mark mapping value to obtain this error correction value $e_j=\underset{i\∈R}{\mathrm{\Σ}}{\mathrm{Tr}}_{K/F}(S_i/{\mathrm{\β}}^{j\·i}),$ F＝GF(2)，K＝GF(2 ^d)。

Preferably, the decoder of aforesaid error correcting code, wherein the primitive root β ∈ E=GF (2 of this generator polynomial ^m), for each error correction value e _jThe limited body result of division of this syndrome of each syndrome that this first computing module of this error correction value calculation apparatus is tried to achieve is to represent with a coefficient sequence, this second computing module of this error correction value calculation apparatus is to reach a mark coefficient sets of setting up in advance according to described coefficient sequence, obtains this error correction value

Be arbitrary coefficient of this coefficient sequence, c _lBe arbitrary coefficient of this mark coefficient sets, And this mark coefficient sets is to set up in advance according to the basis set of E.

Preferably, the decoder of aforesaid error correcting code, wherein this second computing module of this error correction value calculation apparatus comprises that a plurality of and arithmetic unit and a plurality of mutual exclusion exclusive disjunction device, this second computing module are to utilize describedly to calculate this error correction value with arithmetic unit and described mutual exclusion exclusive disjunction device $e_j=S_0+\underset{l=0}{\overset{m-1}{\mathrm{\Σ}}}\underset{i=1}{\overset{\left|R\right|}{\mathrm{\Σ}}}{a}_{\mathrm{jl}}^i{c}_l.$

The object of the invention to solve the technical problems also realizes by the following technical solutions.A kind of error correction value calculation apparatus according to the present invention's proposition, be applicable to the decoder of an error correcting code, one syndrome calculation element of the decoder of this error correcting code produces a plurality of syndromes with manipulative indexing according to a reception signal that has received, this reception signal is after an original message is encoded into a circulation code word in a transmission end by a generation multinomial, through a channel transfer and in the received person of a receiving terminal; Wherein: this error correction value calculation apparatus is in order to receive described syndrome and to produce according to this respectively a plurality of error correction values of corresponding a plurality of errors presents, this error correction value calculation apparatus comprises one first computing module and one second computing module, this first computing module and this second computing module are to carry out following calculating, to produce this error correction value of corresponding each errors present: this first computing module is tried to achieve the limited body result of division of a syndrome of each syndrome according to a specific power of a primitive root of this generator polynomial, and this specific power is relevant with the manipulative indexing of this errors present and this syndrome; And this second computing module is tried to achieve a limited body addition results as this error correction value according to the limited body result of division of described syndrome.

The object of the invention to solve the technical problems also can be applied to the following technical measures to achieve further.

Preferably, aforesaid error correction value calculation apparatus, wherein for each syndrome, this first computing module is take this syndrome as dividend, and take this specific power of this primitive root as divisor, tries to achieve the limited body result of division of this syndrome.

Preferably, aforesaid error correction value calculation apparatus wherein is this circulation code word of n for length, with described error correction value and respectively corresponding described errors present with an error polynomial

Expression, e _jRepresent this error correction value of j errors present, for each error correction value e _j, the limited body result of division of this syndrome of each syndrome that this first computing module is obtained is S _i/ β ^Ji, S _iRepresent the i syndrome of this error polynomial, its manipulative indexing is i, and β is the primitive root of this generator polynomial.

Preferably, aforesaid error correction value calculation apparatus, wherein this first computing module comprises a limited body constant multiplier, this first computing module is to utilize this limited body constant multiplier to calculate i syndrome S _iWith default constant 1/ β ^JiProduct, to obtain S _i/ β ^Ji

Preferably, aforesaid error correction value calculation apparatus is wherein for each error correction value e _j, this first computing module is to obtain in all syndromes of this error polynomial each syndrome S _iThe limited body result of division of this syndrome, i=0,1 ... n-1, this second computing module add up the limited body result of division of described syndrome, to obtain this error correction value

Preferably, aforesaid error correction value calculation apparatus, wherein this first computing module is to obtain to belong to each syndrome S that a generation characterizes the shape value set _iThe limited body result of division of this syndrome, i ∈ R, R are the set of the representative element of all n time cyclotomy coset.

Preferably, aforesaid error correction value calculation apparatus is wherein for each error correction value e _j, this second computing module of this error correction value calculation apparatus is a mark mapping value Tr who calculates the limited body result of division of this syndrome of each syndrome _K/F(S _i/ β ^Ji), add up again described mark mapping value to obtain this error correction value $e_j=\underset{i\∈R}{\mathrm{\Σ}}{\mathrm{Tr}}_{K/F}(S_i/{\mathrm{\β}}^{j\·i}),$ F＝GF(2)，K＝GF(2 ^d)。

Preferably, aforesaid error correction value calculation apparatus, wherein the primitive root β ∈ E=GF (2 of this generator polynomial ^m), for each error correction value e _jThe limited body result of division of this syndrome of each syndrome that this first computing module of this error correction value calculation apparatus is tried to achieve is to represent with a coefficient sequence, this second computing module of this error correction value calculation apparatus is to reach a mark coefficient sets of setting up in advance according to described coefficient sequence, obtains this error correction value

Be arbitrary coefficient of this coefficient sequence, c _lBe arbitrary coefficient of this mark coefficient sets, And this mark coefficient sets is to set up in advance according to the basis set of E.

Preferably, aforesaid error correction value calculation apparatus, wherein this second computing module of this error correction value calculation apparatus comprises that a plurality of and arithmetic unit and a plurality of mutual exclusion exclusive disjunction device, this second computing module are to utilize describedly to calculate this error correction value with arithmetic unit and described mutual exclusion exclusive disjunction device $e_j=S_0+\underset{l=0}{\overset{m-1}{\mathrm{\Σ}}}\underset{i=1}{\overset{\left|R\right|}{\mathrm{\Σ}}}{a}_{\mathrm{jl}}^i{c}_l.$

The present invention compared with prior art has obvious advantage and beneficial effect.By technique scheme, the decoder of error correcting code of the present invention and error correction value calculation apparatus thereof have following advantages and beneficial effect at least:

Beneficial effect of the present invention is: by this first computing module and this second computing module of this error correction value calculation apparatus of the present invention, after trying to achieve required syndrome, computing and circuit that can low complex degree be directly tried to achieve error correction value and errors present.

Above-mentioned explanation only is the general introduction of technical solution of the present invention, for can clearer understanding technological means of the present invention, and can be implemented according to the content of specification, and for above and other purpose of the present invention, feature and advantage can be become apparent, below especially exemplified by preferred embodiment, and the cooperation accompanying drawing, be described in detail as follows.

Description of drawings

Fig. 1 is a calcspar, and a preferred embodiment and the application thereof of the decoder of error correcting code of the present invention are described.

Fig. 2 A is a schematic diagram, illustrates at one first of an error correction value calculation apparatus of this preferred embodiment to implement in the aspect the employed wherein limited body constant multiplier of one first computing module.

Fig. 2 B is a schematic diagram, and one second computing module employed one limited body adder is described in this first enforcement aspect.

Fig. 3 is a schematic diagram, illustrates at one second of this error correction value calculation apparatus to implement in the aspect the employed a plurality of mark mappers of one second computing module and a limited body adder.

Fig. 4 is a schematic diagram, illustrates at one the 3rd of this error correction value calculation apparatus to implement in the aspect one second computing module employed a plurality of and arithmetic unit and a plurality of mutual exclusion exclusive disjunction device.

Embodiment

Reach technological means and the effect that predetermined goal of the invention is taked for further setting forth the present invention, below in conjunction with accompanying drawing and preferred embodiment, decoder and its embodiment of error correction value calculation apparatus, structure, feature and the effect thereof of the error correcting code that foundation the present invention is proposed are elaborated.

Suppose that a transmission end utilizes a generation multinomial G (x) that an original message is encoded into (a n, k, d) after the circulation code word, through passage (channel) transmission and in the received reception signal that becomes of a receiving terminal, n represents the length of this circulation code word, k represents the length of this original message, and d represents the smallest hamming distance (Hamming distance) of this circulation code word, and the maximum error correction capacity (errorcorrecting capacity) of this circulation code word is And, also be n to the length of this reception signal that should the cyclic code word.

This reception signal because in the process that passage transmits, might being subject to noise (noise), this circulation code word disturbs, so may not equal this circulation code word.If should the circulation code word with a codeword polynome

Expression, to the error messages that should noise disturbs with an error polynomial

Expression, then this reception signal can represent suc as formula the receiverd polynomial r (x) shown in (1).

$r\left(x\right)=\underset{j=0}{\overset{n-1}{\mathrm{\Σ}}}{r}_j{x}^j=c\left(x\right)+e\left(x\right)...\left(1\right)$

Consult Fig. 1, the preferred embodiment of the decoder 1 of error correcting code of the present invention, be applicable to more positive system of an error detection, this error detection more positive system and is carried out error detection and corrigendum to obtain this corresponding circulation code word to this reception signal in order to receiving this reception signal.This error detection more positive system comprises the decoder 1 of this error correcting code and an error correcting unit 2.The decoder 1 of this error correcting code comprises a syndrome calculation element 11, and an error correction value calculation apparatus 12.And the execution mode of the decoder 1 of this error correcting code and this error correcting unit 2 and running pass further describe as rear.

At first, this syndrome calculation element 11 receives this and receives signal, and produces a plurality of syndromes, the i syndrome S of this error polynomial e (x) _iBe defined as e (β ⁱ), i is the manipulative indexing of syndrome, β is the primitive root of this generator polynomial G (x).This syndrome calculation element 11 comprises known syndrome (knownsyndrome) computing module 111, and a unknown syndrome (unknown syndrome) computing module 112; This known syndrome computing module 111 is tried to achieve at least one known syndrome according to primitive root β (primitive root) and this receiverd polynomial r (x) of this generator polynomial G (x), then, this unknown syndrome computing module 112 is tried to achieve at least one unknown syndrome according to this known syndrome again; Described syndrome comprises this known syndrome and this unknown syndrome.Because the method for asking of described syndrome has been exposed in some existing documents, for example, " " Algebraic Decoding of (71,36,11), (79,40,15), and (97,49,15) Quadratic Residue Codes, " SEPTEMBER 2003 for IEEE TRANSACTIONSON COMMUNICATIONS, VOL.51; N0.9; PP.1463-1473 " and " " Algebraic Decoding of (103,52,19) and (113,57,15) QuadraticResidue Codes, " MAY 2005 for IEEE TRANSACTIONS ON COMMUNICATIONS; VOL.53; NO.5, PP.749-754 ", and non-emphasis of the present invention, so the implementation detail of this known syndrome computing module 111 and this unknown syndrome computing module 112 is not given unnecessary details at this.

Then, this error correction value calculation apparatus 12 receives described syndrome, and producing an error correction information, this error correction information comprises respectively a plurality of error correction values of corresponding a plurality of errors presents, can be with described error correction value and described errors present with this error polynomial Expression, e _jRepresent this error correction value of j errors present.This error correction value calculation apparatus 12 comprises one first computing module 121 and one second computing module 122, can following three kinds of enforcement aspects realize.It is worth mentioning that the needs of corresponding different enforcement aspects, the described syndrome of these syndrome calculation element 11 required calculating are slightly different, but there is no difference for account form and the definition of each syndrome.

First implements aspect

Cooperate this first enforcement aspect, this syndrome calculation element 11 needs to calculate all syndrome S of this error polynomial e (x) _i, i=0,1 ... ,-1 (being that i is 0 to n-1 integer).

This error correction value e for the j errors present _j, this first computing module 121 is the primitive root β according to this generator polynomial G (x), obtains in all syndromes limited body (finitefield) the result of division S of each _i/ β ^Ji, i=0,1 ... ,-1; Then, this second computing module 122 adds up described limited body result of division S _i/ β ^Ji, in the hope of a limited body addition results, and this limited body addition results is this error correction value e of j errors present _j, the arrangement as with following formula (2).

$e_j=\underset{i=0}{\overset{n-1}{\mathrm{\Σ}}}(S_i/{\mathrm{\β}}^{j\·i})...\left(2\right)$

Consult Fig. 1, Fig. 2 A and Fig. 2 B, because the primitive root β of this generator polynomial G (x) is a known constant, in this first enforcement aspect, this first computing module 121 comprises a plurality of limited body constant multipliers 123, and this second computing module 122 comprises a limited body adder 124.This first computing module 121 utilizes and i syndrome S _iCorresponding limited body constant multiplier 123 calculates it and presets constant 1/ β with one ^JiProduct, to obtain S _i/ β ^JiThen, this second computing module 122 utilizes this limited body adder 124 to add up described limited body result of division S _i/ β ^Ji _,This error correction value e in the hope of the j errors present _j

Second implements aspect

Cooperate this second enforcement aspect, this syndrome calculation element 11 only need calculate in the described syndrome of this error polynomial e (x), belongs to the syndrome S that a generation characterizes the shape value set _i, i ∈ R, R are the set of the representative element (representative) of all n time cyclotomy coset (cyclotomic coset of i modulo n).The definition of n cyclotomy coset is as with shown in the following formula (3).

C _i＝{i·2 ^k|k＝0，1，...，d-1}.............................(3)

D is so that i2 ^dThe minimum positive integer of ≡ i (modn).

In order to make follow-up description more explicit, carry out first following formula (4)～(7) definition.

F＝GF(2).........................................(4)

E＝GF(2 ^m)........................................(5)

GF represents Jia Luowa body (Galois Field), and E is m rank (degree m) ennations (extension field) of F.

If d is the approximate number (divisor) of m, then a daughter (subfield) K of E is defined as follows.

K＝GF(2 ^d)........................................(6)

Then, definition is as follows to mark mapping (trace mapping) value of F (K onto F) by K.

${\mathrm{Tr}}_{K/F}\left(\mathrm{\γ}\right)=\mathrm{\γ}+{\mathrm{\γ}}^2+...+{\mathrm{\γ}}^{2^{d-1}},\mathrm{\γ}\∈K...\left(7\right)$

Based on above-mentioned definition and hypothesis, this error correction value e of j errors present _jCalculating can be reduced to: this first computing module 121 is obtained in the set of this representative syndrome this limited body result of division S of each _i/ β ^Ji, i ∈ R; Then, this second computing module 122 calculates each limited body result of division S _i/ β ^JiA mark mapping value Tr _K/F(S _i/ β ^Ji), add up again described mark mapping value Tr _K/F(S _i/ β ^Ji), in the hope of this error correction value e of this limited body addition results as the j errors present _j, the arrangement as with following formula (8).

$e_j=\underset{i\∈R}{\mathrm{\Σ}}{\mathrm{Tr}}_{K/F}(S_i/{\mathrm{\β}}^{j\·i})...\left(8\right)$

Consult Fig. 1, Fig. 2 A and Fig. 3, in this second enforcement aspect, the implementation of class of this first computing module 121 is similar to this first enforcement aspect, is to utilize and i syndrome S _iCorresponding limited body constant multiplier 123 is obtained its limited body result of division S _i/ β ^JiThis second computing module 22 comprises a plurality of mark mappers 125 and a limited body adder 126; This second computing module 22 is to utilize and S _i/ β ^JiCorresponding mark mapper 125 is obtained first its mark mapping value Tr _K/F(S _i/ β ^Ji), recycle this limited body adder 126 and add up described mark mapping value Tr _K/F(S _i/ β ^Ji), in the hope of this error correction value e of j errors present _j, the implementation of class of each mark mapper 125 is similar to limited body adder.

The 3rd implements aspect

Cooperate this 3rd enforcement aspect, this syndrome calculation element 11 only need calculate with second and implement the identical described syndrome S of aspect _i, namely belong to the syndrome S that this representative syndrome is gathered _i, i ∈ R.

In this 3rd enforcement aspect, the enforcement of this second computing module 122 can further be simplified based on following definition and hypothesis.

Suppose α ⁰..., α ^M-1Be E=GF (2 ^m) a basis set (basis), arbitrary coefficient c of a mark coefficient sets then _lDefinition is suc as formula (9).

c _l＝Tr _E/F(α ^l)......................................(9)

Because α ⁰..., α ^M-1Be one group of known constant, so this mark coefficient sets can be set up and c in advance _l∈ F.

Suppose the primitive root β ∈ E of this generator polynomial G (x), and each limited body result of division S _i/ β ^JiCoefficient sequence in can formula (10)

Expression.

$S_i/{\mathrm{\β}}^{j\·i}=\underset{l=0}{\overset{m-1}{\mathrm{\Σ}}}{a}_{\mathrm{jl}}^i{\mathrm{\α}}^l,a_{\mathrm{jl}}^i\∈F...\left(10\right)$

Based on above-mentioned definition and hypothesis, this error correction value e of j errors present _jCalculating can streamline any further this limited body result of division S that obtains in this representative syndrome set each for: this first computing module 121 _i/ β ^Ji, i ∈ R, and store its coefficient sequence

Then, this second computing module 122 is according to described coefficient sequence

And this mark coefficient sets of setting up in advance, try to achieve this limited body addition results as this error correction value e of j errors present _j, the arrangement as with following formula (11).

$e_j=S_0+\underset{l=0}{\overset{m-1}{\mathrm{\Σ}}}\underset{i=1}{\overset{\left|R\right|}{\mathrm{\Σ}}}{a}_{\mathrm{jl}}^i{c}_l...\left(11\right)$

Consult Fig. 1, Fig. 2 A and Fig. 4, in this 3rd enforcement aspect, the enforcement of this first computing module 121 is identical with this second enforcement aspect.This second computing module 122 comprises a plurality of and (AND) arithmetic unit 127 and a plurality of mutual exclusion or (XOR) arithmetic unit 128; This second computing module 122 is to utilize described and arithmetic unit 127 to carry out multiplying in the formula (11), utilizes described mutual exclusion exclusive disjunction device 128 to carry out add operation in the formula (11).

At last, this error correcting unit 2 is according to this error correction information, that is, the described errors present that described error correction value and philosophy thereof are corresponding carries out error detection and corrigendum to this reception signal, to obtain this corresponding circulation code word.When the error correction value that arbitrary errors present is arranged was not 0 (that is, e (x) ≠ 0), expression detected this reception signal and is subject to the noise pollution, must carry out suc as formula the error correction shown in (12).

c(x)＝r(x)-e(x)....................................(12)

In sum, this first computing module 121 and this second computing module 122 by this error correction value calculation apparatus 12 of the present invention, after trying to achieve required syndrome, do not need " utilizing Bai Liken-Mei Xi algorithm to obtain error location polynomial; to cooperate again Qian Shi to look for one's roots and obtain errors present with iterating ", but directly try to achieve error correction value and errors present with computing and the circuit of low complex degree, so really can reach purpose of the present invention.

The above, it only is preferred embodiment of the present invention, be not that the present invention is done any pro forma restriction, although the present invention discloses as above with preferred embodiment, yet be not to limit the present invention, any those skilled in the art, within not breaking away from the technical solution of the present invention scope, when the technology contents that can utilize above-mentioned announcement is made a little change or is modified to the equivalent embodiment of equivalent variations, in every case be not break away from the technical solution of the present invention content, any simple modification that foundation technical spirit of the present invention is done above embodiment, equivalent variations and modification all still belong in the scope of technical solution of the present invention.

Claims (19)

1. the decoder of an error correcting code, produce an error correction information in order to receive signal according to one, for this reception signal is carried out error detection and corrigendum, this reception signal is after an original message is encoded into a circulation code word in a transmission end by a generation multinomial, to be received in a receiving terminal through a channel transfer; The decoder that it is characterized in that this error correcting code comprises:

One syndrome calculation element is in order to receive this reception signal and to produce according to this a plurality of syndromes with manipulative indexing; And

One error correction value calculation apparatus, in order to receive described syndrome and to produce according to this this error correction information, this error correction information comprises respectively a plurality of error correction values of corresponding a plurality of errors presents, this error correction value calculation apparatus comprises one first computing module and one second computing module, this first computing module and this second computing module are to carry out following calculating, to produce this error correction value of corresponding each errors present:

This first computing module is tried to achieve the limited body result of division of a syndrome of each syndrome according to a specific power of a primitive root of this generator polynomial, and this specific power is relevant with the manipulative indexing of this errors present and this syndrome; And

This second computing module is tried to achieve a limited body addition results as this error correction value according to the limited body result of division of described syndrome.

2. the decoder of error correcting code as claimed in claim 1, it is characterized in that: this syndrome calculation element is according to receiving the signal multinomial to receiving one of signal, try to achieve at least one known syndrome, try to achieve at least one unknown syndrome according to this known syndrome again, described syndrome comprises this known syndrome and this unknown syndrome.

3. the decoder of error correcting code as claimed in claim 1, it is characterized in that: for each syndrome, this first computing module is take this syndrome as dividend, and take this specific power of this primitive root as divisor, tries to achieve the limited body result of division of this syndrome.

4. the decoder of error correcting code as claimed in claim 3 is characterized in that: be this circulation code word of n for length, with described error correction value and respectively corresponding described errors present with an error polynomial

Expression, e _jRepresent this error correction value of j errors present, for each error correction value e _j, the limited body result of division of this syndrome of each syndrome that this first computing module of this error correction value calculation apparatus is obtained is S _i/ β ^Ji, S _iRepresent the i syndrome of this error polynomial, its manipulative indexing is i, and β is the primitive root of this generator polynomial.

5. the decoder of error correcting code as claimed in claim 4, it is characterized in that: this first computing module of this error correction value calculation apparatus comprises a limited body constant multiplier, and this first computing module is to utilize this limited body constant multiplier to calculate i syndrome S _iWith default constant 1/ β ^JiProduct, to obtain S _i/ β ^Ji

6. the decoder of error correcting code as claimed in claim 4 is characterized in that: this syndrome calculation element is all syndromes that produce this error polynomial, for each error correction value e _j, this second computing module of this error correction value calculation apparatus is to add up the limited body result of division of described syndrome, to obtain this error correction value

7. the decoder of error correcting code as claimed in claim 4 is characterized in that: each syndrome S that this syndrome calculation element produces _iBelong to a generation and characterize the shape value set, i ∈ R, R are the set of the representative element of all n time cyclotomy coset.

8. the decoder of error correcting code as claimed in claim 7 is characterized in that: for each error correction value e _j, this second computing module of this error correction value calculation apparatus is a mark mapping value Tr who calculates the limited body result of division of this syndrome of each syndrome _K/F(S _i/ β ^Ji), add up again described mark mapping value to obtain this error correction value

F=GF (2), K=GF (2 ^d).

9. the decoder of error correcting code as claimed in claim 7 is characterized in that: the primitive root β ∈ E=GF (2 of this generator polynomial ^m), for each error correction value e _jThe limited body result of division of this syndrome of each syndrome that this first computing module of this error correction value calculation apparatus is tried to achieve is to represent with a coefficient sequence, this second computing module of this error correction value calculation apparatus is to reach a mark coefficient sets of setting up in advance according to described coefficient sequence, obtains this error correction value

Be arbitrary coefficient of this coefficient sequence, c _lBe arbitrary coefficient of this mark coefficient sets, c _l∈ F=GF (2), and this mark coefficient sets is to set up in advance according to the basis set of E.

10. the decoder of error correcting code as claimed in claim 9, it is characterized in that: this second computing module of this error correction value calculation apparatus comprises that a plurality of and arithmetic unit and a plurality of mutual exclusion exclusive disjunction device, this second computing module are to utilize describedly to calculate this error correction value with arithmetic unit and described mutual exclusion exclusive disjunction device $e_j=S_0+\underset{l=0}{\overset{m-1}{\mathrm{\Σ}}}\underset{i=1}{\overset{\left|R\right|}{\mathrm{\Σ}}}{a}_{\mathrm{jl}}^i{c}_l.$

11. error correction value calculation apparatus, be applicable to the decoder of an error correcting code, one syndrome calculation element of the decoder of this error correcting code produces a plurality of syndromes with manipulative indexing according to a reception signal that has received, this reception signal is after an original message is encoded into a circulation code word in a transmission end by a generation multinomial, through a channel transfer and in the received person of a receiving terminal; It is characterized in that: this error correction value calculation apparatus is in order to receive described syndrome and to produce according to this respectively a plurality of error correction values of corresponding a plurality of errors presents, this error correction value calculation apparatus comprises one first computing module and one second computing module, this first computing module and this second computing module are to carry out following calculating, to produce this error correction value of corresponding each errors present:

This first computing module is tried to achieve the limited body result of division of a syndrome of each syndrome according to a specific power of a primitive root of this generator polynomial, and this specific power is relevant with the manipulative indexing of this errors present and this syndrome; And

This second computing module is tried to achieve a limited body addition results as this error correction value according to the limited body result of division of described syndrome.

12. error correction value calculation apparatus as claimed in claim 11 is characterized in that: for each syndrome, this first computing module is take this syndrome as dividend, and take this specific power of this primitive root as divisor, tries to achieve the limited body result of division of this syndrome.

13. error correction value calculation apparatus as claimed in claim 12 is characterized in that: be this circulation code word of n for length, with described error correction value and respectively corresponding described errors present with an error polynomial

Expression, e _jRepresent this error correction value of j errors present, for each error correction value e _j, the limited body result of division of this syndrome of each syndrome that this first computing module is obtained is S _i/ β ^Ji, S _iRepresent the i syndrome of this error polynomial, its manipulative indexing is i, and β is the primitive root of this generator polynomial.

14. error correction value calculation apparatus as claimed in claim 13 is characterized in that: this first computing module comprises a limited body constant multiplier, and this first computing module is to utilize this limited body constant multiplier to calculate i syndrome S _iWith default constant 1/ β ^JiProduct, to obtain S _i/ β ^Ji

15. error correction value calculation apparatus as claimed in claim 13 is characterized in that: for each error correction value e _j, this first computing module is to obtain in all syndromes of this error polynomial each syndrome S _iThe limited body result of division of this syndrome, i=0,1 ... n-1, this second computing module add up the limited body result of division of described syndrome, to obtain this error correction value

16. error correction value calculation apparatus as claimed in claim 13 is characterized in that: this first computing module is to obtain to belong to each syndrome S that a generation characterizes the shape value set _iThe limited body result of division of this syndrome, i ∈ R, R are the set of the representative element of all n time cyclotomy coset.

17. error correction value calculation apparatus as claimed in claim 16 is characterized in that: for each error correction value e _j, this second computing module of this error correction value calculation apparatus is a mark mapping value Tr who calculates the limited body result of division of this syndrome of each syndrome _K/F(S _i/ β ^Ji), add up again described mark mapping value to obtain this error correction value

F=GF (2), K=GF (2 ^d).

18. error correction value calculation apparatus as claimed in claim 16 is characterized in that: the primitive root β ∈ E=GF (2 of this generator polynomial ^m), for each error correction value e _jThe limited body result of division of this syndrome of each syndrome that this first computing module of this error correction value calculation apparatus is tried to achieve is to represent with a coefficient sequence, this second computing module of this error correction value calculation apparatus is to reach a mark coefficient sets of setting up in advance according to described coefficient sequence, obtains this error correction value

Be arbitrary coefficient of this coefficient sequence, c _lBe arbitrary coefficient of this mark coefficient sets,

c _l∈ F=GF (2), and this mark coefficient sets is to set up in advance according to the basis set of E.

19. error correction value calculation apparatus as claimed in claim 18, it is characterized in that: this second computing module of this error correction value calculation apparatus comprises that a plurality of and arithmetic unit and a plurality of mutual exclusion exclusive disjunction device, this second computing module are to utilize describedly to calculate this error correction value with arithmetic unit and described mutual exclusion exclusive disjunction device $e_j=S_0+\underset{l=0}{\overset{m-1}{\mathrm{\Σ}}}\underset{i=1}{\overset{\left|R\right|}{\mathrm{\Σ}}}{a}_{\mathrm{jl}}^i{c}_l.$

Images