CN101409565B - Method and apparatus for decoding, and encoding/decoding system - Google Patents
Method and apparatus for decoding, and encoding/decoding system Download PDFInfo
- Publication number
- CN101409565B CN101409565B CN2008100426174A CN200810042617A CN101409565B CN 101409565 B CN101409565 B CN 101409565B CN 2008100426174 A CN2008100426174 A CN 2008100426174A CN 200810042617 A CN200810042617 A CN 200810042617A CN 101409565 B CN101409565 B CN 101409565B
- Authority
- CN
- China
- Prior art keywords
- mrow
- polynomial
- msup
- pattern
- circleplus
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Error Detection And Correction (AREA)
Abstract
The embodiment of the invention discloses a decoding method, a decoding device and a coding and decoding system. The method comprises code polynomial is received, mod of the preset generator polynomial is calculated by using the code polynomial, and pattern of original syndrome is acquired; the pattern of original syndrome is led into reciprocal polynomial circuit running based on the generator polynomial, the wrong polynomial corresponding to the pattern of original syndrome circularly shifts towards the low-order direction of the received code polynomial, and the wrong pattern is determined; modular two addition is carried out on the reverse order of the received code polynomial and the wrong pattern. The decoding device comprises an original syndrome generation unit, a circuit unit of the reciprocal polynomial based on the generator polynomial, a buffer and an error check unit. The decoding method, the decoding device and the coding and decoding system which are provided by the embodiment of the invention can flexibly adapt to the change of the contraction length of shorten cyclic codes, and are easy to realize and calculate.
Description
Technical Field
The embodiment of the invention relates to the technical field of decoding, in particular to a decoding method, a decoding device and a coding and decoding system.
Background
The cyclic code is an important subset of linear block codes, and the most important characteristic of the cyclic code is the cyclic characteristic of a code word, wherein the cyclic characteristic means that after any allowed code block in the cyclic code is circularly shifted to the left or the right, the obtained code block is still the allowed code block. A shortened cyclic code is a common cyclic code that shortens the upper s bits of the code polynomial. If decoding is performed by a conventional Mergitt decoder, the corresponding syndrome patterns will be different with the change of the shortened length s.
Fig. 1 is a schematic diagram of a conventional megger decoder. The syndrome calculating circuit of the Mergitt decoder can adopt a division circuit, and the syndrome of a certain code group circularly shifted for i times is equal to the result obtained by operating the syndrome of the original code group in the division circuit for i times. Simultaneously inputting the received code group into a syndrome calculation circuit and a buffer; and when the code group is input and the syndrome calculation is finished, the input is disconnected, and division circuit operation and error pattern recognition are carried out. When the division circuit operates to a certain moment, the pattern of the register of the division circuit is identified by the circuit, namely the cache received data corresponding to the moment is modulo-two added with the corresponding error pattern, so that error correction is realized.
Referring to fig. 2 together with the schematic diagram of the conventional megger decoder shown in fig. 1, fig. 2 is a schematic diagram of an implementation of the megger decoder of the cyclic CRC-CCITT code. The error pattern recognition circuit of the Mergite decoder of the CRC-CCITT code is an AND gate, and the recognized pattern is a corresponding syndrome pattern when the highest bit of the corresponding code polynomial is in error. When the circuit starts to work, the register of the syndrome generating circuit is 0, the gate 1 is opened, and the switch K is disconnected; when a packet is input, calculating to obtain a syndrome pattern s (x), closing the gate 1 and stopping the buffer from moving; and (3) closing the switch K, sending a syndrome pattern s (x) of the syndrome generating circuit to a division circuit below, immediately opening the switch K, and emptying a register in the syndrome generating circuit to be 0. At this time, the gate 1 is opened again, and the buffer sends out the data of the current packet while receiving the data of the next packet. Meanwhile, the syndrome generating circuit calculates the syndrome of the next packet of received data, and the lower division circuit corrects the data of the current packet. And if and only if the pattern in the register of the following division circuit is the syndrome pattern, the output of the AND gate is 1, and the output of the AND gate is 0 in other cases. And performing modulo two addition on the output of the AND gate and the received data output in the buffer in sequence to correct the error at the corresponding position.
In the process of implementing the invention, the inventor finds that shortening the cyclic code is performed by shortening the high-order bits of the code polynomial, and the corresponding syndrome patterns to be identified are different along with the change of the shortening length. Therefore, when the shortened cyclic code with variable shortened length is decoded, the check sub-pattern recognition circuit of the existing Mergite decoder cannot be flexibly applied; and because the syndrome division circuit needs syndrome pattern recognition every time when rotating, parallel calculation is difficult to realize.
Disclosure of Invention
In view of this, an embodiment of the present invention provides a decoding method, an apparatus and a coding/decoding system, which can flexibly adapt to the change of shortening the length of a shortened cyclic code and are easy to perform parallel computation.
In order to achieve the above object, the technical solutions provided by the embodiments of the present invention are as follows:
the embodiment of the invention provides a decoding method, which comprises the following steps:
receiving a code polynomial, and performing modulo operation on a preset generator polynomial by using the code polynomial to obtain an original syndrome pattern; the code polynomial is formed by modulo addition of a code polynomial sent by a coding end and an error polynomial generated in the transmission process;
inputting the original syndrome pattern into a circuit operation based on an inverse polynomial of a generator polynomial, circularly shifting an error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial, and determining an error pattern;
and performing modulo two addition on the received reverse sequence of the code polynomial and the error pattern to obtain an error-corrected code sequence.
An embodiment of the present invention further provides a decoder, including:
the original syndrome generating unit is used for receiving a code polynomial, performing modulo operation on a preset generator polynomial by using the code polynomial and acquiring an original syndrome pattern; the code polynomial is formed by modulo addition of a code polynomial sent by a coding end and an error polynomial generated in the transmission process;
the circuit unit is used for receiving the original syndrome pattern and operating, and an error polynomial corresponding to the original syndrome pattern is circularly shifted to the low-order direction of the received code polynomial; determining an error pattern and outputting;
the buffer is used for receiving and outputting the code polynomial;
and the error correction unit is used for performing modulo-two addition on the reverse order of the code polynomial output by the buffer and the error pattern output by the circuit unit based on the inverse polynomial of the generator polynomial to obtain an error-corrected code sequence.
The embodiment of the invention also provides a coding and decoding system which comprises the decoder, wherein the decoder is connected with the encoder in a communication mode.
The embodiment of the invention is based on the application of the inverse polynomial circuit of the generator polynomial, because the high-order bits of the code polynomial do not influence the low-order bits when the cyclic code is shortened, and the inverse polynomial circuit based on the generator polynomial is applied to operate the original check sub-pattern, which is equivalent to the cyclic shift of the error polynomial corresponding to the original check sub-pattern to the low-order direction of the received code polynomial, and the syndrome pattern corresponding to the low-order bit error of the code polynomial does not change along with the change of the shortened length, so that the embodiment of the invention can flexibly adapt to the change of the shortened length of the shortened cyclic code and is easy to calculate in parallel.
FIG. 1 is a schematic diagram of a conventional Mergite decoder;
FIG. 2 is a diagram illustrating an implementation of a CRC-CCITT code error correction method in the prior art;
FIG. 3 is a flowchart illustrating a decoding method according to an embodiment of the present invention;
drawings
Fig. 4 is a schematic diagram illustrating an implementation of a decoding method according to an embodiment of the present invention;
FIG. 5 is a schematic diagram illustrating an implementation of another decoding method according to an embodiment of the present invention;
fig. 6 is a schematic logic structure diagram of a decoder according to an embodiment of the present invention.
The embodiment of the invention provides a decoding method, a decoding device and a coding and decoding system, which can enable an error polynomial corresponding to an original check sub-pattern to circularly shift to the low-order direction of a received code polynomial, flexibly adapt to the change of shortening the length of a shortened cyclic code and are easy to calculate in parallel.
For the purpose of facilitating a further understanding of the embodiments of the present invention, reference will now be made in detail to the embodiments of the present invention, which are illustrated in the accompanying drawings.
Referring to fig. 3, fig. 3 is a schematic flowchart of a decoding method according to an embodiment of the present invention, where the method specifically includes:
Detailed Description
Step 301: and receiving a code polynomial, and performing modulo operation on a preset generator polynomial by using the code polynomial to obtain an original syndrome pattern.
The received code polynomial is formed by modulo-two addition of a code polynomial sent by an encoder and an error polynomial generated in the transmission process;
dividing the received code polynomial by a generator polynomial and taking a remainder to obtain an original syndrome pattern; the generating polynomial is preset during encoding, and the generating polynomial which is completely the same as the generating polynomial during encoding is adopted during decoding to carry out decoding error correction and detection.
Let the code polynomial transmitted during encoding be c (x), the code polynomial received during decoding be r (x), the error polynomial be e (x), and r (x) ═ c (x) + e (x).
For cyclic codes, the original syndrome pattern s (x) is often defined as the remainder of r (x) divided by the generator polynomial g (x), i.e.
s(x)＝r(x)modg(x) (1)
The formula (1) is decomposed, and the property that the transmitted code polynomial C (x) must be divided by g (x) is utilized to obtain
s(x)＝r(x)mod g(x)＝(C(x)+e(x))modg(x)
＝C(x)modg(x)+e(x)modg(x) (2)
＝0+e(x)modg(x)
＝e(x)modg(x)
It can be seen that the original syndrome pattern s (x) is only related to the error polynomial e (x), and is not related to the code polynomial c (x) transmitted during encoding. When the error polynomial e (x) is 0, the original syndrome pattern s (x) is 0, and the received codeword r (x) is considered to be correct; when the error polynomial e (x) ≠ 0, the original syndrome pattern s (x) ≠ 0, then the received codeword r (x) is considered incorrect.
Step 302: and operating the original syndrome pattern by using an inverse polynomial circuit based on the generator polynomial, and circularly shifting the error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial to determine the error pattern.
Substituting the original syndrome pattern into a circuit of an inverse polynomial based on a generator polynomial; the inverse polynomial is obtained by inverting the coefficient of the preset generator polynomial;
the original syndrome pattern operates in a circuit based on an inverse polynomial of a generator polynomial; the pattern in the corresponding circuit register is a syndrome pattern obtained after cyclic shift of an error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial;
register patterns in a circuit based on an inverse polynomial of the generator polynomial are identified to obtain corresponding error patterns.
The identifying a register pattern in a circuit based on an inverse polynomial of a generator polynomial to obtain a corresponding error pattern may specifically be:
and judging whether the sum of the numerical values of the registers in the circuit which forms the inverse polynomial based on the generator polynomial is less than or equal to the correctable error number of the received code polynomial, and if so, outputting an error pattern corresponding to the register pattern.
The inverse polynomial is obtained by inverting coefficients of the preset generator polynomial, and specifically may be:
the base number of the generating polynomial is unchanged, and the exponent is inverted to obtain the generating polynomial with the exponent being a negative value;
and multiplying the generator polynomial with the exponential being negative by the generator polynomial with the exponential being the highest term of the generator polynomial to obtain the inverse polynomial of the generator polynomial.
Wherein, the determining whether the sum of the numerical values of the registers in the circuit that constitutes the inverse polynomial based on the generator polynomial is less than or equal to the correctable error number of the received code polynomial, and if so, the error pattern corresponding to the output register pattern may specifically be:
the numerical value of the register of the inverse polynomial circuit based on the generator polynomial changes correspondingly along with the operation of the circuit, and the numerical value of the register of the inverse polynomial circuit based on the generator polynomial forms a corresponding syndrome pattern after the cyclic shift of the original syndrome; and judging whether the sum of the numerical values of the registers is less than or equal to t (t is the number of errors which can be corrected by the code polynomial), and if so, outputting an error pattern corresponding to the check sub-pattern.
Suppose s-m(x) Is the original syndrome pattern s (x) after reverse cyclic shift m times, has
s-m(x)＝[x-m·s(x)]modg(x) (3)
Let y be x-1Is provided with
s-m(y-1)＝[ym·s(y-1)]mod g(y-1) (4)
Both sides of the equation are multiplied by y simultaneouslyn-kTo obtain
s-m(y-1)·yn-k＝[ym·s(y-1)·yn-k]mod[g(y-1)·yn-k] (5)
Wherein, <math><mrow> <msubsup> <mi>s</mi> <mrow> <mo>-</mo> <mi>m</mi> </mrow> <mo>′</mo> </msubsup> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mo>=</mo> <msub> <mi>s</mi> <mrow> <mo>-</mo> <mi>m</mi> </mrow> </msub> <mrow> <mo>(</mo> <msup> <mi>x</mi> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mo>)</mo> </mrow> <mo>*</mo> <msup> <mi>x</mi> <mrow> <mi>n</mi> <mo>-</mo> <mi>k</mi> </mrow> </msup> <mo>,</mo> </mrow></math> s＇(x)＝s(x-1)*xn-k、g＇(x)＝g(x-1)*xn-kare respectively s-m(x) The inverse polynomial of(s), (x), g (x), n is the length of the code word after encoding, and k is the length of the information bit before encoding. The operation of the circuit based on the inverse polynomial g' (x) of g (x) may result in a cyclic shift of the corresponding error polynomial in the lower order direction by the corresponding syndrome pattern.
Step 303: and performing modulo two addition on the reverse order of the received code polynomial and the error pattern.
The error pattern corresponds to a received check sub-pattern when the lower-order bits of the code polynomial are in error, if and only if the error pattern corresponds to the received check sub-pattern when the lower-order bits of the code polynomial are in error, the sum of the numerical values of the registers of the inverse polynomial circuit based on the generator polynomial is less than or equal to t (t is the number of errors which can be corrected by the code polynomial), the circuit outputs the numerical value of the register, and the reverse order of the code sequence received in the buffer and the numerical value of the register are subjected to modulo-two addition, so that the errors at the corresponding positions can be corrected.
Step 304: if no recognizable error pattern occurs during decoding, an uncorrectable indication is output.
The decoding method provided by the embodiment of the invention is based on the application of an inverse polynomial circuit for generating a polynomial, takes an error pattern corresponding to a syndrome pattern when low-order bits of the received code polynomial are in error as a pattern of an identification circuit, and circularly shifts the error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial, so that the conversion for shortening the length of the cyclic code can be flexibly adapted, and the parallel calculation is easy.
The first embodiment is as follows:
in this embodiment, the error detection and correction method provided in this embodiment of the present invention is described by taking CRC-CCITT codes as an example of application of error detection and correction, calculating 16 bits in parallel, and dividing the number of bits N of an input packet by 16. Referring to fig. 4, fig. 4 is a schematic diagram illustrating an implementation of a decoding method according to an embodiment of the present invention. As shown in fig. 4, the CRC-CCITT code generator polynomial in the syndrome generator circuit is g (x) x16+x12+x5+ 1; the inverse polynomial in the inverse polynomial circuit is g' (x) ═ g (x)-1)×x16＝x16+x11+x4＋1。
As shown in fig. 4, when the operation is started, the register in the syndrome generating circuit is cleared to 0, the gate 1 is opened, and the switch K is turned off. When a packet is input, calculating to obtain a syndrome pattern s (x), closing the gate 1 and stopping the buffer; and opening the switch K, sending the original syndrome pattern s (x) of the syndrome generating circuit to the following inverse generating polynomial circuit, closing the switch K immediately, and clearing the register in the syndrome generating circuit to be 0. At this time, the gate 1 is opened again, and the buffer receives the data of the next packet while transmitting the data of the current packet. At the same time, the syndrome generating circuit calculates the syndrome of the next packet of received data, the following inverse polynomial circuit based on the generator polynomial starts to operate, the gates output the values of the circuit registers simultaneously, and when the sum of the values of the registers in the inverse polynomial circuit based on the generator polynomial is equal to 1 (1 is the number of correctable errors of the CRC-CCITT code), the gates output the values of the circuit registers; otherwise, the output sequence of the digital gate is all zeros. The reverse order of the received code sequence in the buffer and the value of the register of the digital output circuit are modulo-two added.
Assuming that the parallel calculation equation of the syndrome generating circuit at the decoding time of the nth beat is as follows:
wherein, the beat number N is 0, 1, N/16-1(N is the bit number of the input packet), and the processing of each beat is equivalent to the syndrome generating circuit shown in fig. 4 to operate 16 times; dn-1[i]The value in the register in the syndrome generating circuit representing the decoding time of the previous beat (i.e. beat n-1), i.e. has Dn-1[i]＝Di(i＝0，1，...，15)。M[i](i, ═ 0, 1.., 15) is the intermediate processing result of the parallel computation; at the decoding time of the nth beat, the new value in the register of the syndrome generating circuit is calculated as <math><mrow> <msup> <mi>D</mi> <mi>n</mi> </msup> <mrow> <mo>[</mo> <mi>i</mi> <mo>]</mo> </mrow> <mo>=</mo> <mi>r</mi> <mrow> <mo>[</mo> <mi>n</mi> <mo>*</mo> <mn>16</mn> <mo>+</mo> <mrow> <mo>(</mo> <mn>15</mn> <mo>-</mo> <mi>i</mi> <mo>)</mo> </mrow> <mo>]</mo> </mrow> <mo>⊕</mo> <mi>M</mi> <mrow> <mo>[</mo> <mi>i</mi> <mo>]</mo> </mrow> <mo>,</mo> </mrow></math> (i ═ 0, 1.., 15), where r [ j ] is](j ═ 0, 1,. N-1) is the value of the received codeword sequence.
It should be noted that the parallel computation of the syndrome generating circuit to obtain the original syndrome pattern is prior art and is familiar to those skilled in the art, and the embodiments of the present invention are not further derived herein.
When the syndrome generating circuit has rotated N/16 beats, the generated syndrome pattern will be input into an inverse polynomial circuit based on a generator polynomial, and the equation is:
suppose that:
when the m-th beat of the inverse polynomial circuit based on the generator polynomial is finished, the register thereof
Di(i ═ 0, 1.., 15) with an initial value of C-1[i](i ═ 0, 1.., 15). The estimated equation for the error pattern output by the gate is
The digital gate judges whether the sum of numerical values in a register of the inverse polynomial circuit based on the generator polynomial at the m-1 th beat time is equal to 1, and if so, an error pattern corresponding to a syndrome pattern in the register is output; if not, outputting an all-zero sequence. The equation of obtaining the code sequence after error correction by performing modulo-two addition on the reverse order of the received code sequence in the buffer and the error pattern is as follows:
where r [ j ] (j 0, 1.. cndot.n-1) is the value of the received codeword sequence, and r' j ] (j 0, 1.. cndot.n-1) is the value of the codeword sequence after error correction. Assuming that N is 16 and i is 0, equation (9) is:
that is, the code sequence after error correction is obtained by performing modulo two addition on the reverse sequence of the received code sequence and the error pattern in the buffer. When the inverse polynomial circuit based on the generator polynomial runs circularly for the mth beat, the register D is obtainediA value C of (i ═ 0, 1.., 15)m[i]The parallel computing equation of (1) is:
it should be noted that, the circuit first performs digital gate judgment to obtain a digital gate output pattern. And performing modulo-two addition on the reverse sequence of the received code sequence and the output pattern of the digital gate to finish the error correction of the current beat. Meanwhile, an inverse polynomial circuit based on the generator polynomial calculates one beat in parallel to obtain a syndrome pattern, so as to prepare for error correction of the next beat. And outputting an uncorrectable indication when no recognizable error pattern appears after the sequence decoding of the whole packet is finished. And after the decoding of the current packet is finished, the register receives the original syndrome pattern of the next packet input by the syndrome generating circuit again.
The embodiment of the invention is based on the application of an inverse polynomial circuit for generating a polynomial, is equivalent to the cyclic shift of an error polynomial corresponding to an original syndrome pattern to the low-order direction of a received code polynomial, and takes the error pattern corresponding to the syndrome pattern when the low order of the received code polynomial goes wrong as the pattern of an identification circuit, thereby being capable of flexibly adapting to the transformation for shortening the shortening length of the cyclic code and being easy for parallel calculation.
Example two:
this embodiment also describes the error detection and correction method provided by the embodiment of the present invention, taking CRC-CCITT codes as an example of error detection and correction application, calculating 16 bits in parallel, and dividing the number of bits N of an input packet by 16. Referring to fig. 5, fig. 5 is a schematic diagram illustrating an implementation of another decoding method according to an embodiment of the present invention. The difference between the schematic implementation of the decoding method provided by the second embodiment of the present invention shown in fig. 5 and the schematic implementation of the decoding method provided by the first embodiment of the present invention shown in fig. 4 is that: FIG. 4 is a low order input of the received code polynomial from the syndrome generation circuit; figure 5 inputs the received code polynomial from the upper bits of the syndrome generation circuit. As shown in fig. 5, the CRC-CCITT code generator polynomial in the syndrome generator circuit is g (x) x16+x12+x5+ 1; the inverse polynomial in the inverse polynomial circuit is g' (x) ═ x16+x11+x4+1。
First, assume that <math><mrow> <mfenced open='' close='-' separators=''> <mtable> <mtr> <mtd> <mrow> <mi>M</mi> <mrow> <mo>[</mo> <mi>i</mi> <mo>]</mo> </mrow> <mo>=</mo> <mi>r</mi> <mrow> <mo>[</mo> <mi>n</mi> <mo>*</mo> <mn>16</mn> <mo>+</mo> <mrow> <mo>(</mo> <mn>15</mn> <mo>-</mo> <mi>i</mi> <mo>)</mo> </mrow> <mo>]</mo> </mrow> <mo>⊕</mo> <msup> <mi>D</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> <mrow> <mo>[</mo> <mi>i</mi> <mo>]</mo> </mrow> </mrow> </mtd> <mtd> <mrow> <mo>(</mo> <mi>i</mi> <mo>=</mo> <mn>0,1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mn>15</mn> <mo>)</mo> </mrow> <mo>-</mo> <mo>-</mo> <mo>-</mo> <mrow> <mo>(</mo> <mn>11</mn> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> </mrow></math>
Where the number of beats N is 0, 1,., N/16-1(N is the number of bits of the input packet), the processing of each beat is equivalent to the syndrome generating circuit shown in fig. 5 to cycle 16 times. Dn-1[i]The value in the register of the syndrome generating circuit representing the decoding time of the previous beat (beat n-1), i.e. Dn-1[i]＝Di(i ═ 0, 1,. 15); and M [ i ]](i ═ 0, 1., 15) is the intermediate processing result of the parallel computation, r [ j [, j [ ])](j ═ 0, 1,. N-1) is the value of the received codeword sequence.
At the decoding time of the nth beat, the new value in the register in the syndrome generating circuit is calculated as:
it should be noted that the parallel computation of the syndrome generating circuit to obtain the original syndrome pattern is prior art and is familiar to those skilled in the art, and the embodiments of the present invention are not further derived herein.
When the syndrome generating circuit rotates N/16 beats, the generated original syndrome pattern is input into an inverse polynomial circuit based on a generating polynomial, and the equation is as follows:
suppose that:
when the m-th beat of the inverse polynomial circuit based on the generator polynomial is finished, the register DiA value of (i ═ 0, 1.., 15). Initial value of C-1[i](i＝0，1，...，15)。
When the inverse polynomial circuit based on the generator polynomial runs for the mth beat, the register D of the inverse polynomial circuit is calculated in paralleliThe equation for the value of (i ═ 0, 1.., 15) is:
the estimated equation for the error pattern output by the gate is
The digital gate judges whether the sum of the numerical values of the registers of the inverse polynomial circuit based on the generator polynomial at the mth beat moment is equal to 1, if so, an error pattern corresponding to the syndrome pattern in the register is output; if not, outputting an all-zero sequence. The equation of the code sequence after error correction obtained by performing modulo two addition on the reverse order of the receiving code polynomial and the error pattern in the buffer is as follows:
where r [ j ] (j 0, 1.. N-1) is the value of the received codeword sequence, and r' j ] (j 0, 1.. N-1) is the value of the codeword sequence after error correction. Assuming that N is 16 and i is 0, equation (14) is:
namely, the code sequence after error correction is obtained by performing modulo two addition on the reverse order of the receiving code polynomial and the error pattern in the buffer.
It should be noted that, during the operation of each beat, an inverse polynomial circuit based on a generator polynomial calculates one beat in parallel to obtain a corresponding syndrome pattern after the cyclic shift of the original syndrome; then the circuit carries out the digital gate judgment to obtain the digital gate output pattern. And performing modulo-two addition on the reverse order of the received code sequence and the output pattern of the digital gate to finish the error correction of the current beat. And outputting an uncorrectable indication when no recognizable error pattern appears after the sequence decoding of the whole packet is finished. And after the decoding of the current packet is finished, the register receives the original syndrome pattern of the next packet input by the syndrome generating circuit again.
The embodiment of the invention is based on the application of an inverse polynomial circuit for generating a polynomial, takes an error pattern corresponding to a syndrome pattern when low-order bits of a received code polynomial are in error as a pattern of an identification circuit, and circularly shifts the error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial, so that the embodiment of the invention can flexibly adapt to the transformation for shortening the shortening length of a cyclic code and is easy for parallel calculation.
The decoding method provided by the embodiment of the invention is described in detail with reference to the specific embodiment. The inverse polynomial circuit based on the generator polynomial is also suitable for cyclic codes and Mergite decoding, error trapping decoding and correction algorithms of shortened cyclic codes. Moreover, an inverse polynomial circuit based on a generator polynomial and error trapping decoding are applied, and parallel calculation of the circuit can be easily realized. If the error correction capability t of the cyclic code (n, k) is 1, setting the criterion of the error pattern recognition circuit as whether the syndrome pattern weight is equal to 1, wherein the syndrome pattern weight is the sum of the values of the registers in the circuit; the parallel computation of less than or equal to n-k bits can be supported, thereby solving the problem that the parallel computation of the existing Mergite decoder is difficult to realize.
Example three:
referring to fig. 6, fig. 6 is a schematic structural diagram of a decoder according to an embodiment of the present invention. The decoder shown in fig. 6 may specifically include:
the original syndrome generating unit 601 is configured to receive a code polynomial, modulo a preset generator polynomial by the code polynomial, and obtain an original syndrome pattern.
A circuit unit 602 based on an inverse polynomial of the generator polynomial, configured to receive the original syndrome pattern and operate, where an error polynomial corresponding to the original syndrome pattern is cyclically shifted to a lower-order direction of the received code polynomial; and determining and outputting an error pattern.
And a buffer 603 for receiving and outputting the code polynomial.
And an error correcting unit 604 for performing modulo-two addition of the reverse order of the code polynomial output by the buffer and the error pattern output by the circuit unit 602 based on the inverse polynomial of the generator polynomial.
Wherein the circuit unit 602 based on the inverse polynomial of the generator polynomial may include:
an inverse polynomial unit 605, configured to receive the original syndrome pattern input by the original syndrome generating unit and operate; and circularly shifting an error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial to obtain a syndrome pattern after circular shifting.
A gate decision unit 606, configured to determine whether a sum of numerical values of registers in the circuit based on the inverse polynomial of the generator polynomial is less than or equal to the correctable error number of the received code polynomial, and if so, output an error pattern corresponding to the circularly shifted check sub-pattern.
The error correction unit 604 is further configured to determine an error pattern according to a pattern of a register of a circuit based on an inverse polynomial of the generator polynomial, determine whether a recognizable error pattern occurs, and if not, output an uncorrectable indication.
The circuit unit 602 based on the inverse polynomial of the generator polynomial can also be applied to the cyclic code and the merget decoding, error trapping decoding and correction algorithm of the shortened cyclic code, and parallel computation is easy to realize.
According to the decoding method provided by the embodiment of the present invention, the original syndrome generating unit 601 and the buffer 603 receive the code polynomial r (x) at the same time, and the original syndrome generating unit 601 calculates the original syndrome pattern s (x) according to the generating polynomial g (x) and the code polynomial r (x) and substitutes the original syndrome pattern s (x) into the circuit unit 602 based on the inverse polynomial of the generating polynomial; the inverse polynomial unit 605 of the circuit unit 602 based on the inverse polynomial of the generator polynomial operates, and is equivalent to that the error polynomial corresponding to the original check sub-pattern circularly shifts to the lower order; obtaining a syndrome pattern corresponding to the error pattern after cyclic shift; the number gate decision unit 606 determines whether the sum of the numerical values in the register of the circuit unit 602 based on the inverse polynomial of the generator polynomial is equal to 1, and if so, outputs an error pattern corresponding to the syndrome pattern in the register; if not, outputting an all-zero sequence; the error correction unit 604 performs modulo-two addition on the reverse order of the code polynomial output from the buffer 603 and the error pattern output from the gate decision unit 606 to correct errors.
It should be noted that, in the embodiment of the present invention, the error pattern is identified by a method of gate counting, which is easy to perform parallel computation, but those skilled in the art may also use other methods instead, and the embodiment of the present invention is not limited herein.
The decoder according to the embodiment of the present invention is described above, based on the application of the inverse polynomial circuit for generating a polynomial, to circularly shift the error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial, and to use the error pattern corresponding to the syndrome pattern when the low bits of the received code polynomial are erroneous as the pattern of the identification circuit, so that the decoder can flexibly adapt to the transformation for shortening the length of the cyclic code, and is easy to perform parallel computation.
Example four:
the decoding method and the decoder provided by the embodiments of the present invention are described above, respectively, and a coding and decoding system provided by the embodiments of the present invention is described below. The system may include a decoder communicatively coupled to the encoder,
the decoder is used for receiving a code polynomial, performing modulo operation on a preset generator polynomial by using the code polynomial, and acquiring an original syndrome pattern;
substituting the original syndrome pattern into a circuit based on an inverse polynomial of a generator polynomial for operation, and circularly shifting an error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial; determining an error pattern from a register pattern of the circuit and outputting the error pattern;
and performing modulo two addition on the reverse order of the received code polynomial and the output error pattern sum.
Wherein an uncorrectable indication is output if an error pattern cannot be identified from the pattern of the register of the circuit based on the inverse polynomial of the generator polynomial.
The inverse polynomial circuit based on the generator polynomial can also be applied to cyclic codes and Mergite decoding, error trapping decoding and correction algorithms of shortened cyclic codes, and parallel calculation is easy to realize.
The coding and decoding system provided by the embodiment of the invention is based on the application of an inverse polynomial of a generator polynomial, takes an error pattern corresponding to a syndrome pattern when the low order of the received code polynomial is in error as a pattern of an identification circuit, and circularly shifts the error polynomial corresponding to the original syndrome pattern to the low order direction of the code polynomial, so that the conversion of shortening the length of a cyclic code can be flexibly adapted, and the parallel calculation is easy.
The decoding method, apparatus, and coding/decoding system provided by the embodiments of the present invention are described in detail above, and the specific embodiments are applied in this document to explain the principle and implementation manner of the embodiments of the present invention, and the description of the embodiments above is only used to help understanding the method and core ideas of the embodiments of the present invention; meanwhile, for a person skilled in the art, according to the idea of the embodiment of the present invention, there may be a change in the specific implementation and application scope, and in summary, the content of the present specification should not be construed as a limitation to the embodiment of the present invention.
Claims (10)
1. A decoding method, comprising:
receiving a code polynomial, and performing modulo operation on a preset generator polynomial by using the code polynomial to obtain an original syndrome pattern; the code polynomial is formed by modulo addition of a code polynomial sent by a coding end and an error polynomial generated in the transmission process;
inputting the original syndrome pattern into a circuit operation based on an inverse polynomial of a generator polynomial, circularly shifting an error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial, and determining an error pattern; the error pattern corresponds to a check sub-pattern when the low-order bits of the received code polynomial are in error;
performing modulo two addition on the received reverse sequence of the code polynomial and the error pattern to obtain an error-corrected code sequence; the modulo-two addition of the reverse order of the received code polynomial and the error pattern is performed when the sum of the values of the registers of the inverse polynomial circuit based on the generator polynomial is less than or equal to the correctable number of errors of the received code polynomial.
2. The method of claim 1, wherein the modulo the predetermined generator polynomial by the code polynomial to obtain the original check sub-pattern comprises:
and dividing the code polynomial by the preset generating polynomial and taking a remainder to obtain an original syndrome pattern.
3. The method of claim 1, wherein the circuit that inputs the original syndrome pattern into an inverse polynomial based on a generator polynomial operates, wherein an error polynomial corresponding to the original syndrome pattern is cyclically shifted to a lower order of the received code polynomial, and wherein determining an error pattern comprises:
inputting the original syndrome pattern into a circuit based on an inverse polynomial of a generator polynomial; the inverse polynomial is obtained by inverting the coefficient of the preset generator polynomial;
the original syndrome pattern operates in a circuit based on an inverse polynomial of a generator polynomial; the register pattern of the circuit is a syndrome pattern obtained after cyclic shift of an error polynomial corresponding to an original syndrome pattern to the low-order direction of a received code polynomial;
a register pattern of a circuit based on an inverse polynomial of the generator polynomial is identified to obtain a corresponding error pattern.
4. The method of claim 3, wherein identifying a register pattern of a circuit based on an inverse polynomial of a generator polynomial to obtain a corresponding error pattern comprises:
and judging whether the sum of the numerical values of the registers of the circuit which forms the inverse polynomial based on the generator polynomial is less than or equal to the correctable error number of the received code polynomial, and if so, outputting an error pattern corresponding to the check sub-pattern after cyclic shift.
5. The method of claim 3, wherein the method comprises:
the base number of the generating polynomial is unchanged, and the exponent is inverted to obtain the generating polynomial with the exponent being a negative value;
and multiplying the generator polynomial with the exponential being negative by the generator polynomial with the exponential being the highest term of the generator polynomial to obtain the inverse polynomial of the generator polynomial.
6. The method of claim 1, further comprising:
and judging whether recognizable error images appear in the decoding process, and if yes, performing modulo two addition on the reverse order of the received code polynomial and the error pattern.
7. A decoder, comprising:
the original syndrome generating unit is used for receiving a code polynomial, performing modulo operation on a preset generator polynomial by using the code polynomial and acquiring an original syndrome pattern; the code polynomial is formed by modulo addition of a code polynomial sent by a coding end and an error polynomial generated in the transmission process;
the circuit unit is used for receiving the original syndrome pattern and operating, and an error polynomial corresponding to the original syndrome pattern is circularly shifted to the low-order direction of the received code polynomial; determining an error pattern and outputting; the error pattern corresponds to a check sub-pattern when the low-order bits of the received code polynomial are in error;
the buffer is used for receiving and outputting the code polynomial;
the error correction unit is used for performing modulo-two addition on the reverse order of the code polynomial output by the buffer and an error pattern output by the circuit unit based on the inverse polynomial of the generator polynomial to obtain an error-corrected code sequence; the modulo-two addition of the reverse order of the code polynomial output by the buffer and the error pattern output by the circuit unit based on the inverse polynomial of the generator polynomial is performed when the sum of the values of the registers of the circuit based on the inverse polynomial of the generator polynomial is less than or equal to the correctable error number of the received code polynomial.
8. The decoder of claim 7, wherein the error correction unit is further configured to determine whether a recognizable error pattern occurs based on a pattern of a register of a circuit based on an inverse polynomial of the generator polynomial, and if not, to output an uncorrectable indication.
9. The decoder of claim 7, wherein the circuit unit based on an inverse polynomial of a generator polynomial comprises:
the inverse polynomial unit is used for receiving the original syndrome pattern input by the original syndrome generating unit and operating; circularly shifting an error polynomial corresponding to the original syndrome pattern to the low-order direction of the received code polynomial to obtain a syndrome pattern after circular shifting;
and the number gate judgment unit is used for judging whether the sum of the numerical values of the registers in the circuit based on the inverse polynomial of the generator polynomial is less than or equal to the correctable error number of the received code polynomial, and if so, outputting an error pattern corresponding to the check sub-pattern after cyclic shift.
10. A coding system comprising a decoder according to any of claims 7 to 9, the decoder being communicatively coupled to the encoder.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2008100426174A CN101409565B (en) | 2008-09-04 | 2008-09-04 | Method and apparatus for decoding, and encoding/decoding system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2008100426174A CN101409565B (en) | 2008-09-04 | 2008-09-04 | Method and apparatus for decoding, and encoding/decoding system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101409565A CN101409565A (en) | 2009-04-15 |
| CN101409565B true CN101409565B (en) | 2012-02-01 |
Family
ID=40572390
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2008100426174A Expired - Fee Related CN101409565B (en) | 2008-09-04 | 2008-09-04 | Method and apparatus for decoding, and encoding/decoding system |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101409565B (en) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103166649B (en) * | 2011-12-19 | 2016-06-15 | 国际商业机器公司 | For method, device and the decoder of decode cycle code |
| CN104052502B (en) * | 2013-03-14 | 2018-04-27 | 华为技术有限公司 | The method and decoder of decoding |
| CN103716058B (en) * | 2014-01-20 | 2016-08-10 | 谢东福 | A kind of cyclic code interpretation method based on complement code |
| CN103973318A (en) * | 2014-04-29 | 2014-08-06 | 重庆邮电大学 | Linear programming coding method of 73 square residue code |
| US9236890B1 (en) | 2014-12-14 | 2016-01-12 | Apple Inc. | Decoding a super-code using joint decoding of underlying component codes |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6049903A (en) * | 1996-09-30 | 2000-04-11 | Kabushiki Kaisha Toshiba | Digital data error detection and correction system |
| CN1322063A (en) * | 2001-03-30 | 2001-11-14 | 清华大学 | Long burst error-correcting decoding method adopting Reed-solomon code |
-
2008
- 2008-09-04 CN CN2008100426174A patent/CN101409565B/en not_active Expired - Fee Related
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6049903A (en) * | 1996-09-30 | 2000-04-11 | Kabushiki Kaisha Toshiba | Digital data error detection and correction system |
| CN1322063A (en) * | 2001-03-30 | 2001-11-14 | 清华大学 | Long burst error-correcting decoding method adopting Reed-solomon code |
Also Published As
| Publication number | Publication date |
|---|---|
| CN101409565A (en) | 2009-04-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US20160156432A1 (en) | Signal segmentation method and crc attachment method for reducing undetected error | |
| EP0396403B1 (en) | Data stream frame synchronisation | |
| CN101867379B (en) | A Decoding Method of Convolutional Codes Aided by Cyclic Redundancy Check | |
| CN101409565B (en) | Method and apparatus for decoding, and encoding/decoding system | |
| CN113491080A (en) | Multi-mode channel coding with mode specific coloring sequences | |
| JP4125500B2 (en) | CRC code error detection apparatus with parity bits added in reverse order and method thereof | |
| WO2010087776A1 (en) | Encoding and decoding methods for expurgated convolutional codes and convolutional turbo codes | |
| JPH10107650A (en) | Error detection circuit and error correction circuit | |
| WO1996019054A1 (en) | Digital transmission system for encoding and decoding attribute data into error checking symbols of main data | |
| WO2008043282A1 (en) | A method and a system for ldpc erasure correcting decoding | |
| CN115037415A (en) | Error correction coding method, device and terminal based on CRC | |
| JPS63123232A (en) | Method of detecting single bit error and arithmetic decoder employing the same | |
| CA1213673A (en) | Burst error correction using cyclic block codes | |
| CN101567696B (en) | Encoder and decoder of Code BCH with changeable parameters | |
| WO2013189274A1 (en) | Circuit, encoder and method for parallel bch coding | |
| CN105812000A (en) | Improved BCH soft-decision decoding algorithm | |
| US20140013181A1 (en) | Error Correction Coding Using Large Fields | |
| JPH10327080A (en) | Syndrome calculation device | |
| JPH08265173A (en) | Encoder and decoder for error correction code | |
| JP2016051924A (en) | Decoding device and error detection method | |
| RU2693190C1 (en) | Method of diagnosing non-binary block codes | |
| TWI399042B (en) | To detect the wrong position of the detection device | |
| US9032277B1 (en) | Parallel low and asymmetric rate Reed Solomon coding | |
| RU2631142C2 (en) | Method of diagnosing cyclic codes | |
| CN115037414A (en) | Error correction decoding method, device and terminal based on CRC |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20120201 |