METHOD EMPLOYED IN LDPC DECODER AND THE DECODER

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
0
Assignments
First Claim
1. An LDPC decoder, comprising:
 a barrel shifter, configured for shifting and rotating a first codeword by a specified number of bits;
a syndrome calculator, coupled to the barrel shifter, configured for receiving an output of the barrel shifter to calculate a syndrome of a specific data portion of the first codeword based on checking equations of a parity check matrix;
an inverse barrel shifter, coupled to the syndrome calculator, configured for performing an inverse operation of the barrel shifter upon an output of the syndrome calculator to generate a checking value of the specific data portion for a checking equation at a particular row of the parity check matrix;
a flipping function value calculator, coupled to the inverse barrel shifter, configured for calculating a flipping function value of the specific data portion according to the specific data portion by using checking values which are generated from checking equations of the parity check matrix; and
a determining block, coupled to the flipping function value calculator, configured for determining whether to flip the specific data portion of the first codeword by comparing the flipping function value with a flipping threshold which has been calculated based on a plurality of flipping function values of a plurality of previous data portions earlier than the specific data portion;
wherein a data length formed by the specific data portion and the plurality of previous data portions is equal to a data length of a complete codeword.
0 Assignments
0 Petitions
Accused Products
Abstract
A method employed in a lowdensity paritycheck code decoder includes: receiving a specific data portion of a first codeword; calculating a flipping function value of the specific data portion of the first codeword according to the specific data portion by using checking equations of a parity check matrix to calculate checking values of the specific data portion; and determining whether to flip the specific data portion of the first codeword by comparing the flipping function value with a flipping threshold which has been calculated based on a plurality of flipping function values of a plurality of previous data portions earlier than the specific data portion.
0 Citations
No References
No References
9 Claims
 1. An LDPC decoder, comprising:
a barrel shifter, configured for shifting and rotating a first codeword by a specified number of bits; a syndrome calculator, coupled to the barrel shifter, configured for receiving an output of the barrel shifter to calculate a syndrome of a specific data portion of the first codeword based on checking equations of a parity check matrix; an inverse barrel shifter, coupled to the syndrome calculator, configured for performing an inverse operation of the barrel shifter upon an output of the syndrome calculator to generate a checking value of the specific data portion for a checking equation at a particular row of the parity check matrix; a flipping function value calculator, coupled to the inverse barrel shifter, configured for calculating a flipping function value of the specific data portion according to the specific data portion by using checking values which are generated from checking equations of the parity check matrix; and a determining block, coupled to the flipping function value calculator, configured for determining whether to flip the specific data portion of the first codeword by comparing the flipping function value with a flipping threshold which has been calculated based on a plurality of flipping function values of a plurality of previous data portions earlier than the specific data portion; wherein a data length formed by the specific data portion and the plurality of previous data portions is equal to a data length of a complete codeword.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
1 Specification
This continuation application claims the benefits of U.S. application Ser. No. 15/820,391 filed on 2017 Nov. 21, which is entirely incorporated herein by reference.
The invention relates to a decoding mechanism, and more particularly to a method employed in a lowdensity paritycheck code (LDPC) decoder and the LDPC decoder.
Generally speaking, an LDPC decoder with a conventional bit flipping scheme is arranged to calculate all preliminary/initial syndromes of all data bits of a complete codeword, then determine a flipping threshold based on all the preliminary/initial syndromes, then respectively deciding whether to flip/toggle each bit of the complete codeword by comparing the calculated syndrome of the each bit with the flipping threshold, and calculating or updating the syndrome of each bit of the complete codeword if such bit has been flipped or toggled. This conventional bit flipping scheme inevitably needs complexity computation and leads to a slow convergence problem since it is necessary for the conventional scheme to calculate all preliminary/initial syndromes of all data bits of a complete codeword, then determining the flipping threshold based on all the preliminary/initial syndromes which have been calculated, and finally deciding whether to flip/toggle each bit of the complete codeword according to such flipping threshold and the calculated syndromes of all bits.
Therefore one of the objectives of the invention is to provide a method employed in a lowdensity paritycheck code (LDPC) decoder and the LDPC decoder, to solve the abovementioned problems.
According to embodiments of the invention, a method employed in a lowdensity paritycheck code (LDPC) decoder is disclosed. The method comprises: receiving a specific data portion of a first codeword; calculating a flipping function value of the specific data portion of the first codeword according to the specific data portion by using checking equations of a parity check matrix to calculate checking values of the specific data portion; and determining whether to flip the specific data portion of the first codeword by comparing the flipping function value with a flipping threshold which has been calculated based on a plurality of flipping function values of a plurality of previous data portions earlier than the specific data portion.
According to the embodiments, an LDPC decoder is disclosed. The LDPC decoder comprises a barrel shifter, a syndrome calculator, an inverse barrel shifter, a flipping function value calculator, and a determining block. The barrel shifter is configured for shifting and rotating a first codeword by a specified number of bits. The syndrome calculator is coupled to the barrel shifter and configured for receiving an output of the barrel shifter to calculate a syndrome of a specific data portion of the first codeword based on checking equations of a parity check matrix. The inverse barrel shifter is coupled to the syndrome calculator and configured for performing an inverse operation of the barrel shifter upon an output of the syndrome calculator to generate a checking value of the specific data portion for a checking equation at a particular row of the parity check matrix. The flipping function value calculator is coupled to the inverse barrel shifter and configured for calculating a flipping function value of the specific data portion according to the specific data portion by using checking values which are generated from checking equations of the parity check matrix. The determining block is coupled to the flipping function value calculator and configured for determining whether to flip the specific data portion of the first codeword by comparing the flipping function value with a flipping threshold which has been calculated based on a plurality of flipping function values of a plurality of previous data portions earlier than the specific data portion.
According to the embodiments mentioned above, the method and decoder can significantly improve the performance of the decoder, reduce the complexity of computation, and speed up the convergence.
These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings.
For a complete codeword, a conventional scheme is arranged for calculating all preliminary/initial syndromes of all data bits of such complete codeword, determining a flipping threshold based on all the preliminary/initial syndromes, deciding whether to flip a bit of the complete codeword by comparing a preliminary/initial syndrome of such bit with the flipping threshold for the bit, and finally calculating resultant/updated syndromes again after flipping operation. This, however, needs complexity computation.
To solve the problems of conventional scheme, in the first embodiment, the operation of determining whether to flip a bit in the embodiment is based on a flipping threshold which is determined according to the resultant/updated syndromes of previous data bits such as bits of a previous codeword after flipping operation. Thus, for determining whether to flip a bit of a current codeword, the decoding method does not require to wait until all preliminary syndromes of all data bits of such current codeword have been calculated. The decoding method can immediately determine whether to flip a bit once the preliminary syndrome of the bit has been calculated.
The decoding method more particularly relates to a columnlayer bit flipping scheme which is capable of flipping a codeword bit without waiting until all preliminary syndromes of a completed codeword have been derived. That is, the decoding method can flip such codeword bit if necessary under a condition that other remaining codeword bit(s) of the same codeword has/have not been received/processed by the decoder. This can significantly improve the performance of the decoder, reduce the complexity of computation, and speed up the convergence.
That is, the decoding method is based on information of the codeword bit such as an incoming data bit and information of other data bits earlier than the incoming data bit. More specifically, the decoding method is arranged to estimate and update a flipping threshold for each data bit based on previous data bits when each data bit is being processed and then compare the estimated flipping threshold with a flipping function value of this currently incoming data bit to decide whether to flip this incoming data bit and calculate its updated syndrome. For example, the flipping function value can be configured as the preliminary syndrome of the data bit, i.e. invalid checksum.
In other embodiments of a weighted bit flipping decoder, the decoding method can be further arranged to determine weighted values based on information of the previous data bits to determine flipping function values and flipping threshold.
Provided that substantially the same result is achieved, the steps of the flowchart shown in
Step 105: Start;
Step 110: Receive a specific data bit of a codeword having N bits wherein N is a positive integer; for example, the specific data bit is an incoming bit, e.g. the nth bit of the codeword;
Step 115: Calculate the flipping function value En of the nth data bit, for example, the flipping function value En can be the invalid checksum (i.e. the syndrome, the sum of preliminary checking values associated with all checking equations of parity check matrix H) of the specific data bit;
Step 120: Compare the flipping function value En of the nth data bit with the flipping threshold θ of nth data bit to decide whether to flip the nth data bit wherein the flipping threshold θ of nth data bit has calculated or determined according to the flipping function values of (N−1) previous data bits;
Step 125A: Flip the nth data bit;
Step 125B: Not flip the nth data bit;
Step 130A: Calculate the syndrome/checking values of all checking equations for the nth data bit which has been flipped;
Step 130A: Calculate the syndrome/checking values of all checking equations for the nth data bit which is not flipped;
Step 135: Update the flipping threshold θ for next data bit (s) according to the flipping function value En of the nth data bit and flipping function values of the (N−1) previous data bits;
Step 140: Repeat the above steps for next data bit(s) until the sum of calculated syndrome/checking values is equal to zero or a maximum iteration number is reached; and
Step 145: End.
Particularly, the decoding method is based on a parity check matrix H to calculate syndrome/checking values of received data bits. For any (row) vector X, S=X^{T}·H is called the syndrome of X. The vector X indicates a received codeword which is a correct codeword if and only if S=0. The matrix H has M rows and N columns wherein M and N are positive integers. In the embodiments, N means that a codeword is defined to have N data bits, and M means M checking equations or checking nodes. In the embodiments, the parity check matrix H is associated with a quasicyclic (QC) code and formed by multiple blocks of circulant matrices. The LDPC decoder is a QCLDPC decoder. Each element of codeword vector X is either 0 or 1. Smn denotes the syndrome/checking value of the nth data bit at the nth column for a particular checking equation at mth row, and Σ_{m}Smn denotes the summation of syndrome/checking values of the nth data bit at the nth column for all M checking equations, i.e. the invalid checksum of the nth data bit. For example, if one checking equation is not satisfied, the invalid checksum is equal to one; similarly, if two checking equations are not satisfied, the invalid checksum is equal to two.
In Step 115, the decoding method configures the flipping function value En of the nth data bit as the invalid checksum of the nth data bit, i.e. the preliminary syndrome before flipping operation. Identically, the decoding method can perform similar steps for (N−1) previous data bits to respectively calculate the flipping function values of (N−1) previous data bits before processing the nth data bit.
Thus, in Step 120, the decoding method is arranged to compare the flipping function value En with the flipping threshold θ wherein the flipping threshold θ has been determined or updated based on the flipping function values of (N−1) previous data bits in which some data bits may belong to another different codeword. For example, the decoding method can sort the flipping function values of (N−1) previous data bits, select and record the maximum one among the flipping function values of (N−1) previous data bits as the flipping threshold θ, and can also record the second maximum value among the above flipping function values as a candidate flipping threshold for the nth data bit. If the flipping function value En is not smaller than the flipping threshold θ, the decoding method is arranged to flip or toggle the nth data bit in Step 125A, and in Step 130A the decoding method is arranged to calculate Σ_{m }Smn=En, i.e. the sum of syndrome/checking values of all checking equations for the nth data bit which has been flipped. If the flipping function value En is smaller than the flipping threshold θ, the decoding method is arranged to not to flip or toggle the nth data bit in Step 125B, and in Step 130B the decoding method is arranged to calculate Σ_{m}Smn=En, i.e. the sum of syndrome/checking values of all checking equations for the nth data bit which is not flipped.
In Step 135, the decoding method then is arranged to update the flipping threshold θ for one or more next data bit (s) according to the flipping function value En and flipping function values of the (N−1) previous data bits. Similarly, the decoding method can sort the flipping function value En and the flipping function values of (N−2) previous data bits, select and update/record the maximum one among the flipping function value En and flipping function values of (N−2) previous data bits as the flipping threshold θ, and can also update/record the second maximum value among the above flipping function values as a candidate flipping threshold for the next data bit (s).
Accordingly, the flipping threshold θ for each data portion such as each data bit is determined based on the invalid checksums of (N−1) previous data bits. It should be noted that the decoding method can also record the corresponding index of the flipping threshold θ corresponding to the maximum flipping function value and the corresponding index of candidate threshold corresponding the second maximum flipping function value, so as to update the thresholds. However, this is not meant to be a limitation.
For implementation, please refer to
The determining block 230 is coupled to the output of flipping function value calculator 225 and is arranged to compare the flipping function value En of the nth data bit with the flipping threshold θ to decide whether to flip the nth data bit. The threshold recording block 235 is coupled to the determining block 230 and arranged for recoding the abovementioned flipping threshold θ and the candidate flipping threshold (i.e. the second maximum of the invalid checksums of (N−1) previous data bits). The determining block 230 is arranged to update the flipping threshold θ. The determining block 230 then outputs the feedback bit (if flipped or not flipped) to the XOR circuit 205. ΔA(1), ΔB(1), ΔC(1), ΔD(1), ΔE(1), ΔA(2), ΔB(2), and so on respectively mean different feedback bits of different codewords. The barrel shifter 210, syndrome calculator 215, inverse barrel shifter 220, flipping function value calculator 225, determining block 230, and threshold recording block 235 are respectively arranged to perform corresponding operations upon the next data bit such as (n+1)th data bit.
Further, the decoding method mentioned above can be also applied to a weighted bit flipping (WBF) decoder circuit. Please refer to
Provided that substantially the same result is achieved, the steps of the flowchart shown in
Step 305: Start;
Step 307: Calculate initial weighting;
Step 310: Receive a specific data bit of a codeword having N bits wherein N is a positive integer; for example, the specific data bit is an incoming bit, e.g. the nth bit of the codeword;
Step 315: Calculate the flipping function value En of the nth data bit;
Step 317: Update the weighting;
Step 320: Compare the flipping function value En of the nth data bit with the flipping threshold θ of nth data bit to decide whether to flip the nth data bit wherein the flipping threshold θ of nth data bit has calculated or determined according to the flipping function values of (N−1) previous data bits;
Step 325A: Flip the nth data bit;
Step 325B: Not flip the nth data bit;
Step 330A: Calculate the syndrome/checking values of all checking equations for the nth data bit which has been flipped;
Step 330B: Calculate the syndrome/checking values of all checking equations for the nth data bit which is not flipped;
Step 335: Update the flipping threshold θ for next data bit(s) according to the flipping function value En of the nth data bit and flipping function values of the (N−1) previous data bits;
Step 340: Repeat the above steps for next data bit(s) iteratively until the sum of calculated syndrome/checking values is equal to zero or a maximum iteration number is reached; and
Step 345: End.
In Step 307, the initial weighting such as an initial weighted value can be configured as zero if the WBF LDPC decoder 400 is with a dynamic weighted bit flipping algorithm or calculated according to the channel value if the WBF LDPC decoder 400 is with other weighted bit flipping algorithms.
In Step 315, for example, the decoding method is arranged to calculate the flipping function value En of the nth data bit based on the following equation:
wherein ω_{mn }denotes a weighted value for the nth data bit corresponding to the checking equation at the mth row of parity check matrix H. That is, there are M×N weighted values in which some are identical while others are different. ω_{mn }can be represented by the following equation:
In other embodiment, the flipping function value En of the nth data bit can be also designed as the following equation (but not limited):
In Step 317, the decoding method is arranged to calculate the weighted values ω_{mn }for each of (N−1) previous data bits, and sort the weighted values to select and record the minimum weighted value, the second minimum weighted value, and the third weighted value each time when calculating the flipping function value such as En of the nth data bit. If a new weighted value has been calculated based on the flipping function value according to the above equation, the decoding method is arranged to sort and record the minimum weighted value, the second minimum weighted value, and the third weighted value. Also, the decoding method can be arranged to record corresponding indexes associated with the minimum weighted value, the second minimum weighted value, and the third weighted value.
Also, the decoding method is arranged to configure the maximum one among the flipping function values of (N−1) previous data bits as the flipping threshold θ.
The operations of Step 320 to Step 340 are similar to corresponding Steps mentioned in
For implementation, the decoder circuit 400 comprises the XOR circuit 205, barrel shifter 210, syndrome calculator 215, inverse barrel shifter 220, a flipping function value calculator 425, a weighting updating block 427, the determining block 230, and the threshold recording block 235. The XOR circuit 205 is arranged to receive codewords such as codewords 201A, 201B, 201C, 201D, and 201E at its first input and receive feedback bits at its second input to perform XOR operation to generate an output for the barrel shifter 210. The barrel shifter 210 is a digital circuit which is couple to the output of XOR circuit 205 and arranged to shift and rotate a codeword by a specified number of bits. The syndrome calculator 215 is coupled to the barrel shifter 210 and arranged to receive the output of barrel shifter 210 to calculate the syndrome (s) of a data portion such a data bit (e.g. the nth data bit of the codeword) based on checking equations. The inverse barrel shifter 220 is coupled to the syndrome calculator 215 and arranged to receive the output of syndrome calculator 215 to perform the inverse operation of barrel shifter 210 to generate the syndrome/checking value Smn of the nth data bit at its output for a checking equation at the mth row of parity check matrix H. The inverse barrel shifter 220 is arranged to output the syndrome/checking values S1n, S2n, . . . , and SMn of the nth data bit at its output one by one for all checking equations of parity check matrix H.
The flipping function value calculator 425 is coupled to the inverse barrel shifter 220 and arranged to calculate or derive the flipping function value En of the nth data bit based on the values S1n, S2n, . . . , and SMn of the nth data bit corresponding to all checking equations of parity check matrix H. For example, the flipping function value calculator 225 calculates the flipping function value En=Σ_{m}ω_{mn}×(1−2×Sm). This is not meant to be a limitation; in other embodiments, the flipping function value En can be configured or calculated by other different formulas.
The weighting updating block 427 is coupled to the flipping function value calculator 425 and arranged to calculate the weighted values ω_{mn }for each of (N−1) previous data bits before processing the nth data bit, and sort the weighted values to select and recode the minimum weighted value, the second minimum weighted value, and the third weighted value each time when calculating the flipping function value such as En of the nth data bit. If a new weighted value has been calculated based on the flipping function value according to the above equation, the weighting updating block 427 is arranged to sort and record the minimum weighted value, the second minimum weighted value, and the third weighted value. Also, the weighting updating block 427 can be arranged to record corresponding indexes associated with the minimum weighted value, the second minimum weighted value, and the third weighted value.
The determining block 230 is coupled to the output of flipping function value calculator 425 and is arranged to compare the flipping function value En of the nth data bit with the flipping threshold θ to decide whether to flip the nth data bit. The threshold recording block 235 is coupled to the determining block 230 and arranged for recoding the abovementioned flipping threshold θ and the candidate flipping threshold (i.e. the second maximum of flipping function values of (N−1) previous data bits). The determining block 230 is arranged to update the flipping threshold θ. The determining block 230 then outputs the feedback bit (if flipped or not flipped) to the XOR circuit 205. ΔA(1), ΔB(1), ΔC(1), ΔD(1), ΔE(1), ΔA(2), ΔB(2), and so on respectively mean different feedback bits of different codewords. The barrel shifter 210, syndrome calculator 215, inverse barrel shifter 220, flipping function value calculator 425, weighting updating block 427, determining block 230, and threshold recording block 235 are respectively arranged to perform corresponding operations upon the next data bit such as (n+1)th data bit.
In addition, it should be noted that the abovementioned elements and/or blocks included within a decoder circuit can be implemented by hardware circuits such as processors, software modules/application/programs, and/or any combinations of hardware circuits and software modules/application/programs.
Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.