The invention relates to a soft input decoding method and a decoder for generalized concatenated (GC) codes. The GC codes are constructed from inner nested block codes, such as binary Bose-Chaudhuri-Hocquenghem, BCH, codes and outer codes, such as Reed-Solomon, RS, codes. In order to enable soft inp
The invention relates to a soft input decoding method and a decoder for generalized concatenated (GC) codes. The GC codes are constructed from inner nested block codes, such as binary Bose-Chaudhuri-Hocquenghem, BCH, codes and outer codes, such as Reed-Solomon, RS, codes. In order to enable soft input decoding for the inner block codes, a sequential stack decoding algorithm is used. Ordinary stack decoding of binary block codes requires the complete trellis of the code. In one aspect, the present invention applies instead a representation of the block codes based on the trellises of supercodes in order to reduce the memory requirements for the representation of the inner codes. This enables an efficient hardware implementation. In another aspect, the present invention provides a soft input decoding method and device employing a sequential stack decoding algorithm in combination with list-of-two decoding which is particularly well suited for applications that require very low residual error rates.
대표청구항▼
1. A soft input decoding method for a generalized concatenated code, GCC, wherein the GCC is constructed from L inner block codes B( . . . ) and L outer codes, wherein L≥2 denotes the number of levels of the GCC and the inner code of a higher level is a sub-code of the inner code of a respectively p
1. A soft input decoding method for a generalized concatenated code, GCC, wherein the GCC is constructed from L inner block codes B( . . . ) and L outer codes, wherein L≥2 denotes the number of levels of the GCC and the inner code of a higher level is a sub-code of the inner code of a respectively preceding lower level, if any, the method comprising: using one or more decoding devices to iteratively decode level by level original data received from a data channel, wherein such iterative decoding includes performing in each level:a first decoding process for decoding input data of at least one current level l based on the inner block of codes of the current level l and providing respective decoded data, the input data of the lowest level including the original data and the input data of each subsequent level being based on the decoding result of a previous level; anda subsequent second decoding process for decoding the outer code of the current level l based on the output data of the first decoding process to estimate a decoding result of the current level l, wherein the decoding result of a highest level is output as decoded data;wherein: the first decoding process of at least one current level l other than the lowest level comprises trellis-based sequential stack decoding of the input data of the current level l using as a soft input information characterizing the reliability of the data channel;the sequential stack decoding is based on a first trellis representing a first supercode B1(l) of the inner block code B(l) of the current level l and on a second trellis representing a second supercode B2(l) of B(l), with B(l)=B1(l)∩B2(l), wherein a supercode of B(l) is a code containing all codewords of B(l) and the redundancy of each of the first supercode B1(l) and the second supercode B2(l) is lower than that of B(l);the corresponding inner code B(l−1) of the immediately preceding level l−1 is reused as one of the supercodes B1(l) and B2(l); andthe sequential stack decoding is configured to deliver only codewords comprised in the output data of the first decoding process that are represented by both the first trellis and the second trellis. 2. The soft input decoding method of claim 1, wherein the block code of the lowest level of each of the inner block codes is a single error correction code. 3. The soft input decoding method of claim 1, wherein: the inner codes are each nested Bose-Chaudhuri-Hocquenghem (BCH) codes;the extended BCH code in the lowest level of the inner nested BCH codes is a single parity-check (SPC) code; andthe extended BCH code in at least one higher level of the inner nested BCH codes has an error correction capability and is a sub-code of the BCH code of the lowest nesting level. 4. The soft input decoding method of claim 1, the method further comprising: arranging the original data received from a data channel in a two dimensional original data matrix having a first dimension na equal to the length of the outer codes and a second dimension nb equal to the length of the inner block codes, wherein a line of the first dimension of a matrix is a row of the matrix and a line of its second dimension is a column of the matrix, or vice versa, and the outer codes are defined over a Galois-Field GF(2m), with m elements of each line of the second dimension representing one symbol of the Galois-Field GF(2m); anda) a first iteration corresponding to the lowest level of the inner block codes of the original data matrix, wherein the first decoding process includes: applying a decoding scheme of the inner block code of the lowest level to the lines of the second dimension of the original data matrix with respect to the lowest level of the inner nested block codes in which the lines of a second dimension of the original data matrix are encoded in order to obtain an intermediate decoding data matrix of the first iteration and to determine erasure information characterizing lines of the second dimension of the original data matrix in which an erasure has been detected based on the decoding of the inner block code of the lowest level;inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the first iteration in order to retrieve code symbols (ai,j) of the outer codes in which the lines of a first dimension of the original data matrix are encoded;the second decoding process includes: applying outer decoding corresponding to the respective outer codes to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the first iteration in order to obtain a partial decoding result matrix of the first iteration, wherein the erasure information is used during outer decoding to identify erroneous symbols of the outer code in the intermediate decoding data matrix of the first iteration;re-encoding said partial decoding result matrix of the first iteration by applying an encoding scheme of the inner block code of the lowest level to the second dimension of this matrix to obtain a re-encoded matrix of the first iteration; andsubtracting there-encoded matrix of the first iteration from the original data matrix in order to obtain a start matrix for a subsequent further iteration; and(b) for each of the further levels of the inner block codes, a respective further iteration wherein the first decoding step of the respective level includes:applying a decoding scheme of the inner block code of the current level to the lines of the second dimension of the start matrix of the current iteration with respect to the current level of the inner block codes in which the lines of a second dimension of the start matrix of the current iteration are encoded in order to obtain an intermediate decoding data matrix of the current iteration;inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the current iteration in order to retrieve code symbols of the outer codes in which the lines of a first dimension of the original data matrix are encoded;applying outer decoding corresponding to the respective outer codes used for obtaining the original data matrix during encoding, to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the current iteration in order to obtain a partial decoding result matrix of the current iteration;if the current iteration corresponds to the highest nesting level of the inner block codes in the original data matrix, outputting the partial decoding result matrix of the current iteration as the decoded data, andotherwise, re-encoding said partial decoding result matrix of the current iteration by applying an encoding scheme of the inner block code of the current level to the second dimension of this matrix to obtain a re-encoded matrix of the current iteration, and subtracting there-encoded matrix of the current iteration from the start matrix of the current iteration in order to obtain a start matrix for a subsequent further iteration. 5. The soft input decoding method of claim 1, the method further including, in at least one first decoding process using sequential stack decoding, terminating the decoding of a data word in the input data of the inner code of the current level, when: a maximum possible path length is reached, wherein the trellis path having the best metric value among the paths accrued so far in the stack is selected as the decoded codeword corresponding to the data word; ora predetermined maximum number of iterations have occurred. 6. The soft input decoding method of claim 5, the method further including: if the termination is caused because a predetermined maximum number of iterations have occurred, marking the output data of the current first decoding step as an erasure symbol for the corresponding outer code used in the second decoding step of the current level. 7. The soft input decoding method of claim 1, wherein the one or more decoding devices comprise: a plurality of distinct memories or memory areas which can be simultaneously accessed and each of which is configured to store a data representation of a trellis used in a decoding method. 8. A soft input data decoder system for a generalized concatenated code, GCC, wherein the GCC is constructed from L inner block codes B( . . . ) and L outer codes, wherein L≥2 denotes the number of levels of the GCC and the inner code of a higher level is a sub-code of the inner code of a respectively preceding lower level, if any, the method comprising: at least one decoding device configured to iteratively decode level by level original data received from a data channel, wherein such iterative decoding includes performing in each level: a first decoding process of at least one current level l based on the inner block of codes of the current level l and providing respective decoded data, the input data of the lowest level including the original data and the input data of each subsequent level being based on the decoding result of a previous level; anda subsequent second decoding process for decoding the outer code of the current level l based on the output data of the first decoding process to estimate a decoding result of the current level l, wherein the decoding result of a highest level is output as decoded data;wherein: the first decoding process of at least one current level l other than the lowest level comprises trellis-based sequential stack decoding of the input data of the current level l using as a soft input information characterizing the reliability of the data channel;the sequential stack decoding is based on a first trellis representing a first supercode B1(l) of the inner block code B(l) of the current level l and on a second trellis representing a second supercode B2(l) of B(l), with B(l)=B1(l)∩B2(l), wherein a supercode of B(l) is a code containing all codewords of B(l) and the redundancy of each of the first supercode B1(l) and the second supercode B2(l) is lower than that of B(l);the corresponding inner code B(l−1) of the immediately preceding level l−1 is reused as one of the supercodes B1(l) and B2(l); andthe sequential stack decoding is configured to deliver only codewords comprised in the output data of the first decoding process that are represented by both the first trellis and the second trellis. 9. The soft input data decoder system of claim 8, wherein the block code of the lowest level of each of the inner block codes is a single error correction code. 10. The soft input data decoder system of claim 8, wherein: the inner codes are each nested Bose-Chaudhuri-Hocquenghem (BCH) codes;the extended BCH code in the lowest level of the inner nested BCH codes is a single parity-check (SPC) code; andthe extended BCH code in at least one higher level of the inner nested BCH codes has an error correction capability and is a sub-code of the BCH code of the lowest nesting level. 11. The soft input data decoder system of claim 8, the at least one decoding device further configured to: arranging the original data received from a data channel in a two dimensional original data matrix having a first dimension na equal to the length of the outer codes and a second dimension nb equal to the length of the inner block codes, wherein a line of the first dimension of a matrix is a row of the matrix and a line of its second dimension is a column of the matrix, or vice versa, and the outer codes are defined over a Galois-Field GF(2m), with m elements of each lineof the second dimension representing one symbol of the Galois-Field GF(2m); anda) a first iteration corresponding to the lowest level of the inner block codes of the original data matrix, wherein the first decoding process includes: applying a decoding scheme of the inner block code of the lowest level to the lines of the second dimension of the original data matrix with respect to the lowest level of the inner nested block codes in which the lines of a second dimension of the original data matrix are encoded in order to obtain an intermediate decoding data matrix of the first iteration and to determine erasure information characterizing lines of the second dimension of the original data matrix in which an erasure has been detected based on the decoding of the inner block code of the lowest level;inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the first iteration in order to retrieve code symbols (ai,j) of the outer codes in which the lines of a first dimension of the original data matrix are encoded;the second decoding process includes: applying outer decoding corresponding to the respective outer codes to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the first iteration in order to obtain a partial decoding result matrix of the first iteration, wherein the erasure information is used during outer decoding to identify erroneous symbols of the outer code in the intermediate decoding data matrix of the first iteration;re-encoding said partial decoding result matrix of the first iteration by applying an encoding scheme of the inner block code of the lowest level to the second dimension of this matrix to obtain a re-encoded matrix of the first iteration; andsubtracting there-encoded matrix of the first iteration from the original data matrix in order to obtain a start matrix for a subsequent further iteration; and(b) for each of the further levels of the inner block codes, a respective further iteration wherein the first decoding step of the respective level includes:applying a decoding scheme of the inner block code of the current level to the lines of the second dimension of the start matrix of the current iteration with respect to the current level of the inner block codes in which the lines of a second dimension of the start matrix of the current iteration are encoded in order to obtain an intermediate decoding data matrix of the current iteration;inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the current iteration in order to retrieve code symbols of the outer codes in which the lines of a first dimension of the original data matrix are encoded;applying outer decoding corresponding to the respective outer codes used for obtaining the original data matrix during encoding, to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the current iteration in order to obtain a partial decoding result matrix of the current iteration;if the current iteration corresponds to the highest nesting level of the inner block codes in the original data matrix, outputting the partial decoding result matrix of the current iteration as the decoded data, andotherwise, re-encoding said partial decoding result matrix of the current iteration by applying an encoding scheme of the inner block code of the current level to the second dimension of this matrix to obtain a re-encoded matrix of the current iteration, and subtracting there-encoded matrix of the current iteration from the start matrix of the current iteration in order to obtain a start matrix for a subsequent further iteration. 12. The soft input data decoder system of claim 8, the at least one data decoding device further configured to, in at least one first decoding process using sequential stack decoding, terminate the decoding of a data word in the input data of the inner code of the current level, when: a maximum possible path length is reached, wherein the trellis path having the best metric value among the paths accrued so far in the stack is selected as the decoded codeword corresponding to the data word; ora predetermined maximum number of iterations have occurred. 13. The soft input data decoder system of claim 12, wherein the at least one data decoding device is further configured to marking the output data of the current first decoding step as an erasure symbol for the corresponding outer code used in the second decoding step of the current level if the termination is caused because a predetermined maximum number of iterations have occurred. 14. A soft input decoding system for a generalized concatenated code, GCC, wherein the GCC is constructed from L inner block codes B( . . . ) and L outer codes, wherein L≥2 denotes the number of levels of the GCC and the inner code of a higher level is a sub-code of the inner code of a respectively preceding lower level, if any, the decoding system comprising: a processor and a computer readable medium, wherein the computer readable medium includes instructions executable by the processor to:iteratively decode level by level original data received from a data channel, wherein such iterative decoding includes performing in each level: a first decoding process of at least one current level l based on the inner block of codes of the current level l and providing respective decoded data, the input data of the lowest level including the original data and the input data of each subsequent level being based on the decoding result of a previous level; anda subsequent second decoding process for decoding the outer code of the current level l based on the output data of the first decoding process to estimate a decoding result of the current level l, wherein the decoding result of a highest level is output as decoded data;wherein: the first decoding process of at least one current level l other than the lowest level comprises trellis-based sequential stack decoding of the input data of the current level l using as a soft input information characterizing the reliability of the data channel;the sequential stack decoding is based on a first trellis representing a first supercode B1(l) of the inner block code B(l) of the current level l and on a second trellis representing a second supercode B2(l) of B(l), with B(l)=B1(l)∩B2(l), wherein a supercode of B(l) is a code containing all codewords of B(l) and the redundancy of each of the first supercode B1(l) and the second supercode B2(l) is lower than that of B(l);the corresponding inner code B(l−1) of the immediately preceding level l−1 is reused as one of the supercodes B1(l) and B2(l); andthe sequential stack decoding is configured to deliver only codewords comprised in the output data of the first decoding process that are represented by both the first trellis and the second trellis. 15. The soft input decoding system of claim 14, wherein the block code of the lowest level of each of the inner block codes is a single error correction code. 16. The soft input decoding system of claim 14, wherein: the inner codes are each nested Bose-Chaudhuri-Hocquenghem (BCH) codes;the extended BCH code in the lowest level of the inner nested BCH codes is a single parity-check (SPC) code; andthe extended BCH code in at least one higher level of the inner nested BCH codes has an error correction capability and is a sub-code of the BCH code of the lowest nesting level. 17. The soft input decoding system of claim 14, wherein the instructions executable by the processor are further executable to: arrange the original data received from a data channel in a two dimensional original data matrix having a first dimension na equal to the length of the outer codes and a second dimension nb equal to the length of the inner block codes, wherein a line of the first dimension of a matrix is a row of the matrix and a line of its second dimension is a column of the matrix, or vice versa, and the outer codes are defined over a Galois-Field GF(2m), with m elements of each line of the second dimension representing one symbol of the Galois-Field GF(2m); anda) a first iteration corresponding to the lowest level of the inner block codes of the original data matrix, wherein the first decoding process includes: applying a decoding scheme of the inner block code of the lowest level to the lines of the second dimension of the original data matrix with respect to the lowest level of the inner nested block codes in which the lines of a second dimension of the original data matrix are encoded in order to obtain an intermediate decoding data matrix of the first iteration and to determine erasure information characterizing lines of the second dimension of the original data matrix in which an erasure has been detected based on the decoding of the inner block code of the lowest level;inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the first iteration in order to retrieve code symbols (ai,j) of the outer codes in which the lines of a first dimension of the original data matrix are encoded;the second decoding process includes: applying outer decoding corresponding to the respective outer codes to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the first iteration in order to obtain a partial decoding result matrix of the first iteration, wherein the erasure information is used during outer decoding to identify erroneous symbols of the outer code in the intermediate decoding data matrix of the first iteration;re-encoding said partial decoding result matrix of the first iteration by applying an encoding scheme of the inner block code of the lowest level to the second dimension of this matrix to obtain a re-encoded matrix of the first iteration; andsubtracting there-encoded matrix of the first iteration from the original data matrix in order to obtain a start matrix for a subsequent further iteration; and(b) for each of the further levels of the inner block codes, a respective further iteration wherein the first decoding step of the respective level includes:applying a decoding scheme of the inner block code of the current level to the lines of the second dimension of the start matrix of the current iteration with respect to the current level of the inner block codes in which the lines of a second dimension of the start matrix of the current iteration are encoded in order to obtain an intermediate decoding data matrix of the current iteration;inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the current iteration in order to retrieve code symbols of the outer codes in which the lines of a first dimension of the original data matrix are encoded;applying outer decoding corresponding to the respective outer codes used for obtaining the original data matrix during encoding, to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the current iteration in order to obtain a partial decoding result matrix of the current iteration;if the current iteration corresponds to the highest nesting level of the inner block codes in the original data matrix, outputting the partial decoding result matrix of the current iteration as the decoded data, andotherwise, re-encoding said partial decoding result matrix of the current iteration by applying an encoding scheme of the inner block code of the current level to the second dimension of this matrix to obtain a re-encoded matrix of the current iteration, and subtracting there-encoded matrix of the current iteration from the start matrix of the current iteration in order to obtain a start matrix for a subsequent further iteration. 18. The soft input decoding system of claim 14, wherein the instructions executable by the processor are further executable to, in at least one first decoding process using sequential stack decoding, terminating the decoding of a data word in the input data of the inner code of the current level, when: a maximum possible path length is reached, wherein the trellis path having the best metric value among the paths accrued so far in the stack is selected as the decoded codeword corresponding to the data word; ora predetermined maximum number of iterations have occurred. 19. The soft input decoding system of claim 18, wherein the instructions executable by the processor are further executable to mark the output data of the current first decoding step as an erasure symbol for the corresponding outer code used in the second decoding step of the current level if the termination is caused because a predetermined maximum number of iterations have occurred. 20. The soft input decoding system of claim 14, wherein the instructions executable by the processor are further executable to mark the output data of the current first decoding step as an erasure symbol for the corresponding outer code used in the second decoding step of the current level if the termination is caused because a predetermined maximum number of iterations have occurred. 21. The soft input decoding method of claim 14, wherein the one or more decoding devices comprise: a plurality of distinct memories or memory areas which can be simultaneously accessed and each of which is configured to store a data representation of a trellis used in a decoding method.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.