# Patent

## Title
Encoding method, decoding method, encoding device, and decoding device

## Abstract

The embodiments of the present invention provide an encoding and decoding method and device. The encoding method includes: equally dividing input K-bit information into n blocks, where k1, k2, . . . , and kn are used to represent each block of information; combining a kith block of information with n−1 encoded code words Vi−1, Vi−2, . . . , and Vi−n+1 of ki−1th, ki−2th, . . . , and ki−n+1th blocks, to obtain a code word to be encoded, where when a sequence number of an encoded code word is smaller than or equal to 0, the encoded code word is history information; performing, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and the kith block of information form an encoded code word Vi; and outputting encoded code words V1, V2, . . . , and Vn. The embodiments of the present invention are applied in encoding and decoding.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is a continuation of International Application No. PCT/CN2011/082362, filed on Nov. 17, 2011, which is hereby incorporated by reference in its entirety.


TECHNICAL FIELD
The present invention relates to the field of communications, and in particular, to an encoding method, a decoding method, an encoding device, and a decoding device.
BACKGROUND
In a high-speed information transmission system generally adopted at present, usually, it is required to perform FEC (Forward Error Correction, forward error correction) encoding on information to be sent at a transmitting end, and correct an error in a transmission link and output required information through a corresponding FEC decoder at a receiving end. FEC is such a technology that information is processed in a certain format in advance before the information is sent, and decoding is performed according to a specified algorithm at a receiving end, so as to find and correct an error code.
With development of the high-speed information transmission system, a higher requirement is also imposed on a FEC technology. An FEC encoder/decoder with high performance, a high throughput, and a low implementation difficulty is critical to system design. Using an LDPC (Low Density Parity Code, low density parity code) code with higher transmission performance to transmit information gradually becomes a mainstream encoding manner of the FEC technology.
The LDPC code is a type of FEC code word that may approach the Shannon limit and has a gain characteristic. LDPC encoding and decoding are both performed for a single block of information, and LDPC decoding is implemented through a check matrix (H matrix). The H matrix is an M×N matrix, where N is the length of a block code, K is the length of information, and M=N−K, which represents that M check equations exist. Each row of the H matrix represents one check equation. Generally, an LDPC block decoder divides M check equations into m layers, and each layer includes M/m check equations. A decoding process is that the LDPC block decoder checks one code word by using check equations of a 1st layer to an mth layer respectively, and output information is fed back to an input end of the LDPC block decoder for multiple iterations until the decoding is completed.
Since performance of information transmission is restricted by an LDPC code length, in order to implement high-performance and high-throughput FEC encoding and decoding, a code length of the LDPC code is usually required to be quite long. However, the LDPC is a linear block code, and therefore, when a code length of information processed at a single time is longer, an implementation difficulty of a circuit is increased, and meanwhile, consumption of a logical resource is greatly increased, thereby seriously affecting performance of encoding and decoding.
SUMMARY
Embodiments of the present invention provide an encoding method, a decoding method, an encoding device, and a decoding device, so that a code length of information processed at a single time is shortened, thereby reducing an implementation difficulty of a circuit and improving performance of encoding and decoding.
In order to achieve the foregoing objective, the embodiments of the present invention adopt the following technical solutions.
In one aspect, an encoding method is provided and includes:
equally dividing input K-bit information into n blocks, where k1, k2, . . . , and kn are used to represent each block of information;
combining a kith block of information with n−1 encoded code words Vi−1, Vi−2, . . . , and Vi−n+1 of ki−1th, ki−2th, . . . , and ki−n+1th blocks, to obtain a code word to be encoded, where when a sequence number of an encoded code word is smaller than or equal to 0, the encoded code word is history information;
performing, by using a low density parity code LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and the kith block of information form an encoded code word Vi; and
outputting encoded code words V1, V2, . . . , and Vn,
where the LDPC check matrix includes m layers, each layer includes N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block includes N/n sub-matrixes, where iε[1, n], and N, m, n, and i are all positive integers.
In another aspect, a decoding method is provided and includes:
forming input encoded code words Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and performing decoding by using an LDPC check matrix, to obtain a kith block of information, where when a sequence number of the encoded code word is smaller than or equal to 0, the encoded code word is history information;
after obtaining k1th, k2th, . . . , and knth blocks of information after the decoding, combining them to obtain K-bit information; and
outputting the K-bit information,
where the LDPC check matrix includes m layers, each layer includes N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block includes N/n sub-matrixes, where iε[1, n], and N, m, n, and i are all positive integers.
In one aspect, an encoding device is provided and includes:
an encoding inputting unit, configured to input K-bit information;
an encoding processing unit, configured to equally divide the input K-bit information into n blocks, where k1, k2, . . . , and kn are used to represent each block of information; combine a kith block of information with n−1 encoded code words Vi−1, Vi−2, . . . , and Vi−n+1 of ki−1th, ki−2th, . . . , and ki−n+1th blocks, to obtain a code word to be encoded, where when a sequence number of the encoded code word is smaller than or equal to 0, the encoded code word is history information; and perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and the kith block of information form an encoded code word Vi; and
an encoding outputting unit, configured to output encoded code words V1, V2, . . . , and Vn,
where the LDPC check matrix includes m layers, each layer includes N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block includes N/n sub-matrixes, where iε[1, n], and N, m, n, and i are all positive integers.
In another aspect, a decoding device is provided and includes:
a decoding inputting unit, configured to input encoded code words Vi, Vi−1, Vi−2, . . . , and Vi−n+1;
at least one decoding processing unit, configured to form the input encoded code words Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and perform decoding by using an LDPC check matrix, to obtain a kith block of information, where when a sequence number of the encoded code word is smaller than or equal to 0, the encoded code word is history information; and after obtaining k1th, k2th, . . . , and knth blocks of information after the decoding, combine them to obtain the K-bit information; and
a decoding outputting unit, configured to output the K-bit information,
where the LDPC check matrix includes m layers, each layer includes N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block includes N/n sub-matrixes, where iε[1, n], and N, m, n, and i are all positive integers.
With the encoding method, decoding method, encoding device, and decoding device provided in the embodiments of the present invention, the input K-bit information is equally divided into n blocks, so that a code length of information processed at a single time changes from a code length N of information processed at a single time in an existing LDPC encoding and decoding process to N/n (n is a positive integer). In this way, the code length of the information processed at a single time may be greatly shortened by reasonably selecting the number of blocks n. In another aspect, data input at each time is combined with multiple previously obtained encoded code words for check in an encoding and decoding process. By adopting such a convolutional encoding and decoding check method, a total code length of processing is greatly increased in logic, thereby effectively improving performance of encoding and decoding.



BRIEF DESCRIPTION OF THE DRAWINGS
To describe the technical solutions in the embodiments of the present invention or in the prior art more clearly, the accompanying drawings required for describing the embodiments or the prior art are introduced briefly in the following. Apparently, the accompanying drawings in the following descriptions are only some embodiments of the present invention, and persons of ordinary skill in the art may still obtain other drawings according to these accompanying drawings without creative efforts.
FIG. 1 is a schematic flow chart of an encoding method according to an embodiment of the present invention;
FIG. 2 is a schematic flow chart of a decoding method according to an embodiment of the present invention;
FIG. 3a is a schematic diagram of an original check matrix;
FIG. 3b is a schematic diagram of a check matrix obtained through extension and transformation according to an embodiment of the present invention;
FIG. 4a is a schematic diagram of another original check matrix;
FIG. 4b is a schematic diagram of another check matrix obtained through extension and transformation according to an embodiment of the present invention;
FIG. 5 is a schematic structural diagram of an encoding device according to an embodiment of the present invention;
FIG. 6 is a schematic structural diagram of another encoding device according to an embodiment of the present invention;
FIG. 7 is a schematic structural diagram of a decoding device according to an embodiment of the present invention;
FIG. 8 is a schematic connection diagram of a decoding device according to an embodiment of the present invention; and
FIG. 9 is a schematic connection diagram of another decoding device according to an embodiment of the present invention.



DETAILED DESCRIPTION
The technical solutions in the embodiments of the present invention are clearly and fully described in the following with reference to the accompanying drawings in the embodiments of the present invention. Apparently, the embodiments to be described are only a part rather than all of the embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.
An encoding method provided in an embodiment of the present invention. as shown in FIG. 1, includes:
S101: An encoding device equally divides input K-bit information into n blocks, where k1, k2, . . . , and kn are used to represent each block of information.
S102: The encoding device combines a kith block of information with n−1 encoded code words Vi−1, Vi−2, . . . , and Vi−n+1 of ki−1th, ki−2th, . . . , and ki−n+1th blocks, to obtain a code word to be encoded, where when a sequence number of an encoded code word is smaller than or equal to 0, the encoded code word is history information.
S103: The encoding device performs, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and the kith block of information form an encoded code word Vi.
S104: The encoding device outputs encoded code words V1, V2, . . . , and Vn.
The LDPC check matrix includes m layers, each layer includes N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block includes N/n sub-matrixes, where iε[1, n], and N, m, n, and i are all positive integers.
It should be noted that in the foregoing encoding method, the history information refers to an encoded code word of each block of information before the k1th block of information is input. Because the k1th block of information is a first block of input information in an encoding process, the history information may be a preset value, and the history information may also be equal to 0.
With the encoding method provided in this embodiment of the present invention, the input K-bit information is equally divided into n blocks, so that a code length of information processed at a single time changes from a code length N of information processed at a single time in an existing LDPC encoding and decoding process to N/n (n is a positive integer). In this way, the code length of the information processed at a single time may be greatly shortened by reasonably selecting the number of blocks n. In another aspect, data input at each time is combined with multiple previously obtained encoded code words for check in an encoding and decoding process. By adopting such a convolutional encoding and decoding check method, a total code length of processing is greatly increased in logic, thereby effectively improving performance of encoding and decoding.
A decoding method provided in an embodiment of the present invention, as shown in FIG. 2, includes:
S201: A decoding device forms input encoded code words Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and performs decoding by using an LDPC check matrix, to obtain a kith block of information, where when a sequence number of an encoded code word is smaller than or equal to 0, the encoded code word is history information.
S202: After obtaining k1th, k2th, . . . , and knth blocks of information after the decoding, the decoding device combines them to obtain K-bit information.
S203: The decoding device outputs the K-bit information.
The LDPC check matrix includes m layers, each layer includes N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block includes N/n sub-matrixes, where iε[1, n], and N, m, n, and i are all positive integers.
It should be noted that, in the foregoing decoding method, the history information refers to an encoded code word of each block before an encoded code word of a V1th block is input. Because the encoded code word of the V1th block is a first block of input information in a decoding process, the history information may be a preset value, and the history information may also be equal to 0.
With the decoding method provided in this embodiment of the present invention, the input K-bit information is equally divided into n blocks, so that a code length of information processed at a single time changes from a code length N of information processed at a single time in an existing LDPC encoding and decoding process to N/n (n is a positive integer). In this way, the code length of the information processed at a single time may be greatly shortened by reasonably selecting the number of blocks n. In another aspect, data input at each time is combined with multiple previously obtained encoded code words for check in an encoding and decoding process. By adopting such a convolutional encoding and decoding check method, a total code length of processing is greatly increased in logic, thereby effectively improving performance of encoding and decoding.
An embodiment of the present invention provides an encoding method, and based on a continuously extended check matrix, the method adopts a concatenated pipelined convolutional manner for encoding. An original check matrix is shown in FIG. 3a. A size of of the check matrix is m×N and the check matrix includes m layers, each layer represents one check equation, each layer includes N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block includes N/n sub-matrixes, where m=4, n=4, and N=24. That is, the check matrix includes 4 layers, each layer has 4 columns, and each column includes 6 sub-columns (not shown in the figure). The check matrix is extended and transformed to obtain a check matrix H shown in FIG. 3b. The check matrix H is formed by an infinite number of original check matrixes that are connected end to end from left to right or from right to left, shifted down column by column from left to right, and extended to infinite, and each column still has 4 layers. Therefore, H1L, H2L, H3L, and H4L may be used respectively to represent a check equation of each layer cyclically. Exemplarily, H1L is a layer shown by a dashed line in FIG. 3b. A specific encoding process may be described as follows.
Equally divide input K-bit information into 4 blocks, where k1, k2, k3, and k4 are used to represent each block of information.
Combine a kith block of information with 3 encoded code words Vi−1, Vi−2, and Vi−3 of ki−1th, ki−2th, and ki−3th blocks, to obtain a code word to be encoded.
Perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and the kith block of information form an encoded code word Vi, and iε[1, 4].
For example, when i is 3, a k3th block of information is combined with 3 encoded code words V2, V1, and V0 of k2th, k1th, and k0th blocks, to obtain a code word to be encoded; and then, encoding is performed, by using an LDPC check matrix, on the code word to be encoded, where a generated check bit and the k3th block of information form an encoded code word V3. It should be noted that V2 is an encoded code word that is obtained after the k2th block of information is encoded by adopting the same encoding method, that is, the k2th block of information is combined with 3 encoded code words V1, V0, and V−1 of k1th, k0th, and k−1th blocks, to obtain a code word to be encoded, and then encoding is performed, by using an LDPC check matrix, on the code word to be encoded, where a generated check bit and the k2th block of information form an encoded code word V2. Similarly, V1 that exists in a process of encoding the k3th block of information and the k2th block of information is an encoded code word that is obtained after the k1th block of information is encoded by adopting the same encoding method, that is, the k1th block of information is combined with 3 encoded code words V0, V−1, and V−2 of k0th, k−1th, and k−2th blocks, to obtain a code word to be encoded, and then encoding is performed, by using an LDPC check matrix, on the code word to be encoded, where a generated check bit and the k1th block of information form the encoded code word V1. Specifically, the encoded code words V0, V−1, and V−2 are history information, and V0, V−1, and V−2 may be set to 0. It can be seen that in a process of encoding the kith block of information, a value of i is assigned in ascending order from 1 to 4, that is, the k1th block of information to a k4th block of information are input in turn for encoding. A specific process may be described as follows.
Input a k1th block of data, with reference to a check relation of an H1Lth layer in the check matrix H, combine the k1th block of data with encoded code words V0, V−1, and V−2 of k0th, k−1th, and k−2th blocks after encoding, to obtain a code word to be encoded, where the code word to be encoded is a combination of 4 blocks of data, and perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and k1 form an encoded code word V1. k0th, k−1th, and k−2th blocks of data represent data blocks that are encoded before the k1th block of data, and the encoded code words V0, V−1, and V−2 of the k0th, k−1th, and k−2th blocks of data after encoding are history information. In this embodiment, because the k1th block is used as a first block of data for encoding, the k0th, k−1th, and k−2th blocks of data are assigned a preset value 0, and the encoded code words V0, V−1, and V−2 of the k0th, k−1th, and k−2th blocks after encoding are also 0.
Input a k2th block of data, with reference to a check relation of an H2Lth layer in the check matrix H, combine the k2th block of data with encoded code words V1, V0, and V−1 of k1th, k0th, and k−1th blocks after encoding, to obtain a code word to be encoded, where the code word to be encoded is a combination of 4 blocks of data, and perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and k2 form an encoded code word V2. V1 is an encoded code word of a previous k1th block of data.
Input a k3th block of data, with reference to a check relation of an H3Lth layer in the check matrix H, combine the k3th block of data with encoded code words V2, V1, and V0 of k2th, k1th, and k0th blocks after encoding, to obtain a code word to be encoded, where the code word to be encoded is a combination of 4 blocks of data, and perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and k3 form an encoded code word V3.
Input a k4th block of data, with reference to a check relation of an H4Lth layer in the check matrix H, combine the k4th block of data with encoded code words V3, V2, and V1 of k3th, k2th, and k1th blocks after encoding, to obtain a code word to be encoded, where the code word to be encoded is a combination of 4 blocks of data, and perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and k4 form an encoded code word V4.
The finally obtained V1, V2, V3, and V4 are encoded code words of input data k1, k2, k3, and k4, and the encoded code words V1, V2, V3, and V4 are output from an encoding device in order, and an encoding process is completed.
It should be noted that such values as m=4, n=4, and N=24 in this embodiment of the present invention are just exemplary values, and m may be any positive integer, n is smaller than N, and a value of N/n is a positive integer.
With the encoding method provided in this embodiment of the present invention, the input K-bit information is equally divided into n blocks, so that a code length of information processed at a single time changes from a code length N of information processed at a single time in an existing LDPC encoding and decoding process to N/n (n is a positive integer). In this way, the code length of the information processed at a single time may be greatly shortened by reasonably selecting the number of blocks n. In another aspect, data input at each time is combined with multiple previously obtained encoded code words for check in an encoding and decoding process. By adopting such a convolutional encoding and decoding check method, a total code length of processing is greatly increased in logic, thereby effectively improving performance of encoding and decoding.
An embodiment of the present invention provides a decoding method corresponding to the foregoing encoding method. With reference to a check matrix H shown in FIG. 3b, in the same way, assume m=4, n=4, and N=24, and assume the specified number of times I=6. The specified number of times refers to the number of extension times of the check matrix H. The larger the number of extension times of the check matrix H is, the larger the number of decoding check times performed in a decoding process is, and the better performance of the decoding is. The specified number of times is the number of decoding processing units. The specified number of times may be set manually. In theory, the larger the specified number of times is, the better. However, with the increase of the specified number of times, more decoding processing units are required, so that a cost is also higher. Here, the specified number of times I=6 may be preferably selected, that is, a six-stage decoding processing process needs to be performed. A specific decoding process may be described as follows.
Form input encoded code words V1, Vi−1, Vi−2, and Vi−3 into one code word, and perform decoding by using an LDPC check matrix, to obtain a kith block of information, where iε[1, 4].
Being corresponding to an encoding process, in a process of decoding Vi, a value of i is assigned in ascending order from 1 to 4, that is, a decoding device performs decoding on encoded code words V1, V2, V3, and V4 that are input in turn.
Input an encoded code word V1 into the decoding device, with reference to a check relation of an H1Lth layer in the check matrix H, form V1 and V0, V−1, and V−2 into one code word, in a first-stage decoding processing process, perform decoding on the code word by using an LDPC check matrix, and output V′1, V′0, V′−1, and V′−2 and cached data C1, C0, C−1, and C−2; in a second-stage decoding processing process, perform decoding on code words V′1, V′0, V′−1, and V′−2 and the cached data C1, C0, C−1, and C−2 by using the LDPC check matrix, where the code words V′1, V′0, V′−1, and V′−2 and the cached data C1, C0, C−1, and C−2 are output in the first stage, and output V21, V20, V2−1, and V2−2 and updated cached data C′1, C0, C′−1, and C′−2; and the rest may be deduced by analogy, and in a sixth-stage decoding processing process, perform decoding on code words V51, V50, V5−1, and V5−2 and cached data C41, C40, C4−1, and C4−2 by using the LDPC check matrix, where the code words V51, V50, V5−1, and V5−2 and the cached data C41, C40, C4−1, and C4−2 are output in a fifth stage, and output k1, k0, k−1, and k−2. V0th, V−1th, and V−2th blocks of data represent encoded code words before a V1th block of data. In this embodiment, because the V1th block is used as a first block of data for decoding, the V0th, V−1th, and V−2th, blocks of data are assigned a preset value 0, and k0, k−1, and k−2 obtained after decoding of the V0th, V−1th, and V−2th blocks are also 0.
Input an encoded code word V2 into the decoding device, with reference to a check relation of an H2Lth layer in the check matrix H, form V2 and V1, V0, and V−1 into one code word, in a first-stage decoding processing process, perform decoding on the code word by using an LDPC check matrix, and output V′2, V′1, V′0, and V′−1 and cached data C2, C1, C0, and C−1; in a second-stage decoding processing process, perform decoding on code words V′2, V′1, V′0, and V′−1 and the cached data C2, C1, C0, and C−1 by using the LDPC check matrix, where the code words V′2, V′1, V′0, and V′−1 and the cached data C2, C1, C0, and C−1 are output in the first stage, and output V22, V21, V20, and V2−1 and updated cached data C′2, C′1, C′0, and C′−1; and the rest may be deduced by analogy, and in a sixth-stage decoding processing process, perform decoding on code words V52, V51, V50, and V5−1 and cached data C42, C41, C40, and C4−1 by using the LDPC check matrix, where the code words V52, V51, V50, and V5−1 and the cached data C42, C41, C40, and C4−1 are output in a fifth stage, and output k2, k1, k0, and k−1. V1 used for forming the code word of decoding is the encoded code word V1 that has been input into the decoding device previously.
Input an encoded code word V3 into the decoding device, with reference to a check relation of an H3Lth layer in the check matrix H, form V3 and V2, V1, and V0 into one code word, in a first-stage decoding processing process, perform decoding on the code word by using an LDPC check matrix, and output V′3, V′2, V′1, and V′0 and cached data C3, C2, C1, and C0; in a second-stage decoding processing process, perform decoding on code words V′3, V′2, V′1, and V′0 and the cached data C3, C2, C1, and C0 by using the LDPC check matrix, where the code words V′3, V′2, V′1, and V′0 and the cached data C3, C2, C1, and C0 are output in the first stage, and output V23, V22, V21, and V20 and updated cached data C′3, C′2, C′1, C′0; and the rest may be deduced by analogy, and in a sixth-stage decoding processing process, perform decoding on code words V53, V52, V51, and V50 and cached data C43, C42, C41, and C40 by using the LDPC check matrix, where the code words V53, V52, V51, and V50 and the cached data C43, C42, C41, and C40 are output in a fifth stage, and output k3, k2, k1, and k0.
Input an encoded code word V4 into the decoding device, with reference to a check relation of an H4Lth layer in the check matrix H, form V4 and V3, V2, and V1 into one code word, in a first-stage decoding processing process, perform decoding on the code word by using an LDPC check matrix, and output V′4, V′3, V′2, and V′1 and cached data C4, C3, C2, and C1; in a second-stage decoding processing process, perform decoding on code words V′4, V′3, V′2, and V′1 and the cached data C4, C3, C2, and C1 by using the LDPC check matrix, where the code words V′4, V′3, V′2, and V′1 and the cached data C4, C3, C2, and C1 are output in the first stage, and output V24, V23, V22, and V21 and updated cached data C′4, C′3, C′2, and C′1; and the rest may be deduced by analogy, and in a sixth-stage decoding processing process, perform decoding on code words V54, V53, V52, and V51 and cached data C44, C43, C42, and C41 by using the LDPC check matrix, where the code words V54, V53, V52, and V51 and the cached data C44, C43, C42, and C41 are output in a fifth stage, and output k4, k3, k2, and k1.
After the decoding of the encoded code word V4 of a last block is completed, a decoding process ends, the finally output k4, k3, k2, and k1 are decoding results of V4, V3, V2, and V1, the decoding device performs recombination in an order of k1, k2, k3, and k4 to obtain K-bit information, the decoding device outputs the K-bit information, and the decoding is completed.
It should be noted that such values as m=4, n=4, N=24, and the specified number of times I=6 in this embodiment of the present invention are just exemplary values, and m and I may be any positive integer, n is smaller than N, and a value of N/n is a positive integer.
With the decoding method provided in this embodiment of the present invention, input K-bit information is equally divided into n blocks, so that a code length of information processed at a single time changes from a code length N of information processed at a single time in an existing LDPC encoding and decoding process to N/n (n is a positive integer). In this way, the code length of the information processed at a single time may be greatly shortened by reasonably selecting the number of blocks n. In another aspect, data input at each time is combined with multiple previously obtained encoded code words for check in an encoding and decoding process. By adopting such a convolutional encoding and decoding check method, a total code length of processing is greatly increased in logic, thereby effectively improving performance of encoding and decoding.
An embodiment of the present invention further provides an encoding and decoding method by adopting a concatenated pipelined convolution and based on an interleaved check matrix. An original check matrix in FIG. 4a is an interleaved check matrix. Compared with the original check matrix shown in FIG. 3a, the interleaved check matrix has an empty layer, and the number of non-empty layers is m. Because interleaving methods are numerous, positions and the number of empty layers may be random, and the original check matrix shown in FIG. 4a is just one example. A check matrix obtained through extension and transformation according to a method of shifting down column by column is shown in FIG. 4b, where assume m=4, n=4, and N=24, and H1L, H2L, H3L, and H4L are used respectively to represent a check equation of each layer cyclically. A specific encoding process may be described as follows.
Equally divide input K-bit information into 4 blocks, where k1, k2, k3, and k4 are used to represent each block of information.
Combine a kith block of information with 3 encoded code words Vi−1, Vi−2, and Vi−3 of ki−1th ki−2th, and ki−3th blocks, to obtain a code word to be encoded.
Perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and the kith block of information form an encoded code word Vi, where iε[1, 4].
For example, when i is 3, a k3th block of information is combined with 3 encoded code words V2, V1, and V0 of k2th, k1th, and k0th blocks, to obtain a code word to be encoded. Then, encoding is performed, by using an LDPC check matrix, on the code word to be encoded, where a generated check bit and the k3th block of information form an encoded code word V3. It should be noted that V2 is an encoded code word that is obtained after the k2th block of information is encoded by adopting the same encoding method, that is, the k2th block of information is combined with 3 encoded code words V1, V0, and V−1 of k1th, k0th, and k−1th blocks, to obtain a code word to be encoded, and then encoding is performed, by using an LDPC check matrix, on the code word to be encoded, where a generated check bit and the k2th block of information form an encoded code word V2. Similarly, V1 that exists in a process of encoding the k3th block of information and the k2th block of information is an encoded code word that is obtained after the k1th block of information is encoded by adopting the same encoding method, that is, the k1th block of information is combined with 3 encoded code words V0, V−1, and V−2 of k0th, k−1th, and k−2th blocks, to obtain a code word to be encoded, and then encoding is performed, by using an LDPC check matrix, on the code word to be encoded, where a generated check bit and the k1th block of information form the encoded code word V1. Specifically, the encoded code words V0, V−1, and V−2 are history information, and V0, V−1, and V−2 may be set to 0. It can be seen that in a process of encoding the kith block of information, a value of i is assigned in ascending order from 1 to 4, that is, the k1th block of information to a k4th block of information are input in turn for encoding. A specific process may be described as follows.
Input a k1th block of data, with reference to a check relation of an H1Lth layer in a check matrix H, combine the k1th block of data with encoded code words V0, V−1, and V−2 of k0th, k−1th, and k−2th blocks after encoding, to obtain a code word to be encoded, where the code word to be encoded is a combination of 4 blocks of data, and perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and k1 form an encoded code word V1. k0th, k−1th, and k−2th blocks of data are assigned with a preset value 0, and the encoded code words V0, V−1, and V−2 of the k0th, k−1th, and k−2th blocks after encoding are also 0.
It should be noted that the input data of the k1th, k0th, k−1th, and k−2th blocks and the encoded code words V1, V0, V−1, and V−2 all refer to logical blocks, that is, a block of input data or encoded code words with contiguous sequence numbers are logically contiguous. In the previous embodiment, the check matrix is non-interleaved, so that a logical block number is an actual data block number; and in this embodiment of the present invention, reference may be made to the check matrix shown in FIG. 4b, the input data of the k1th, k0th, k−1th, and k−2th blocks respectively corresponds to actual data of k1th, k0th, k−2th, and k−5th blocks, and the encoded code words V1, V0, V−1, and V−2 respectively correspond to encoded code words V1, V0, V−2, V−5.
Reference may be made in the following to an encoding method in which a check matrix is non-interleaved, until a k4th block of data is input, with reference to a check relation of an H4Lth layer in the check matrix H, the k4th block of data is combined with encoded code words V3, V2, and V1 of k3th, k2th, and k1th blocks after encoding, to obtain a code word to be encoded, where the code word to be encoded is a combination of 4 blocks of data, and encoding is performed, by using an LDPC check matrix, on the code word to be encoded, where a generated check bit and k4 form an encoded code word V4. Input data of the k4th, k3th, k2th, and k1th blocks respectively corresponds to actual data of the k4th, k3th, k1th, and k−2th blocks, and encoded code words V4, V3, V2, V1 respectively correspond to encoded code words V4, V3, V1, and V−2.
The finally obtained V1, V2, V3, and V4 are encoded code words of input data k1, k2, k3, and k4, and the encoded code words V1, V2, V3, and V4 are output from an encoding device in order, and an encoding process is completed.
Referring to the check matrix shown in FIG. 4b, in the same way, assume m=4, n=4, and N=24, and assume the specified number of times I=6, and a corresponding decoding method may be described as follows.
Form input encoded code words Vi, Vi−1, Vi−2, and Vi−3 into one code word, and perform decoding by using an LDPC check matrix, to obtain a kith block of information, where iε[1, 4].
Being corresponding to an encoding process, in a process of decoding Vi, a value of i is assigned in ascending order from 1 to 4, that is, a decoding device performs decoding on encoded code words V1, V2, V3, and V4 that are input in turn.
Input an encoded code word V1 into the decoding device, with reference to a check relation of an H1Lth layer in the check matrix H, form V1 and V0, V−1, and V−2 into one code word, in a first-stage decoding processing process, perform decoding on the code word by using an LDPC check matrix, and output V′1, V′0, V′−1, and V′−2 and cached data C1, C0, C−1, and C−2; in a second-stage decoding processing process, perform decoding on code words V′1, V′0, V′−1, and V′−2 and the cached data C1, C0, C−1, and C−2 by using the LDPC check matrix, where the code words V′1, V′0, V′−1, and V′−2 and the cached data C1, C0, C−1, and C−2 are output in the first stage, and output V21, V20, V2−1, and V2−2 and updated cached data C′1, C′0, C′−1, and C′−2; and the rest may be deduced by analogy, and in a sixth-stage decoding processing process, perform decoding on code words V51, V50, V5−1, and V5−2 and cached data C41, C40, C4−1, and C4−2 by using the LDPC check matrix, where the code words V51, V50, V5−1, and V5−2 and the cached data C41, C40, C4−1, and C4−2 are output in a fifth stage, and output k1, k0, k−1, and k−2. V0th, V−1th, and V−2th blocks of data are assigned a preset value 0, and k0, k−1, and k−2 obtained after decoding of the V0th, V−1th, and V−2th blocks are also 0.
Being similar to the encoding process, the encoded code words V1, V0, V−1, and V−2 and the input data of the k1th, k0th, k−1th, and k−2th blocks all refer to logical blocks. In this embodiment of the present invention, reference may be made to the check matrix shown in FIG. 4b, the encoded code words V1, V0, V−1, and V−2 respectively correspond to encoded code words V1, V0, V−2, and V−5, and the input data of the k1th, k0th, k−1th, and k−2th blocks respectively corresponds to actual data of k1th, k0th, k−2th, and k−5th blocks.
Reference may be made in the following to a decoding method in which a check matrix is non-interleaved, until an encoded code word V4 is input into the decoding device, with reference to a check relation of an H4Lth layer in the check matrix H, form V4 and V3, V2, and V1 into one code word, in a first-stage decoding processing process, perform decoding on the code word by using an LDPC check matrix, and output V′4, V′3, V′2, and V′1, and cached data C4, C3, C2, and C1; in a second-stage decoding processing process, perform decoding on code words V′4, V′3, V′2, and V′1 and the cached data C4, C3, C2, and C1 by using the LDPC check matrix, where the code words V′4, V′3, V′2, and V′1 and the cached data C4, C3, C2, and C1 are output in the first stage, and output V24, V23, V22, and V21 and updated cached data C′4, C′3, C′2, C′1; and the rest may be deduced by analogy, and in a sixth-stage decoding processing process, perform decoding on code words V54, V53, V52, V51 and cached data C44, C43, C42, C41 by using the LDPC check matrix, where the code words V54, V53, V52, V51 and the cached data C44, C43, C42, C41 are output in a fifth stage, and output k4, k3, k2, and k1. Encoded code words V4, V3, V2, and V1 respectively correspond to encoded code words V4, V3, V1, and V−2, and input data of k4th, k3th, k2th, and k1th blocks respectively corresponds to actual data of k4th, k3th, k1th, and k−2th blocks.
After the decoding of the encoded code word V4 of a last block is completed, a decoding process ends, the finally output k4, k3, k2, and k1 are decoding results of V4, V3, V2, and V1, the decoding device performs recombination in an order of k1, k2, k3, and k4 to obtain K-bit information, the decoding device outputs the K-bit information, and the decoding is completed.
It should be noted that such values as m=4, n=4, N=24, and the specified number of times I=6 in this embodiment of the present invention are just exemplary values, and m and I may be any positive integer, n is smaller than N, and a value of N/n is a positive integer. After a check matrix is interleaved, a corresponding relation between logical block numbers of input data and an encoded code word and actual data block numbers is not unique, a corresponding relation between logical block numbers of input data and an encoded code word and actual data block numbers in the encoding and decoding method provided in this embodiment of the present invention is only exemplary. Any other corresponding relation that is between logical block numbers and actual data block numbers and generated by interleaving the check matrix is applicable to the method provided in this embodiment of the present invention, and shall all fall within the protection scope of the present invention.
With the encoding method and decoding method provided in this embodiment of the present invention, the input K-bit information is equally divided into n blocks, so that a code length of information processed at a single time changes from a code length N of information processed at a single time in an existing LDPC encoding and decoding process to N/n (n is a positive integer). In this way, the code length of the information processed at a single time may be greatly shortened by reasonably selecting the number of blocks n. In another aspect, data input at each time is combined with multiple previously obtained encoded code words for check in an encoding and decoding process. By adopting such a convolutional encoding and decoding check method, a total code length of processing is greatly increased in logic, thereby effectively improving performance of encoding and decoding.
An encoding device 50 provided in an embodiment of the present invention as shown in FIG. 5, includes:
an encoding inputting unit 501, configured to input K-bit information;
an encoding processing unit 502, configured to equally divide the input K-bit information into n blocks, where k1, k2, . . . , and kn are used to represent each block of information; combine a kith block of information with n−1 encoded code words Vi−1, Vi−2, . . . , and Vi−n+1 of ki−1th, ki−2th, . . . , and ki−n+1th blocks, to obtain a code word to be encoded, where when a sequence number of an encoded code word is smaller than or equal to 0, the encoded code word is history information; and perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and the kith block of information form an encoded code word Vi; and
an encoding outputting unit 503, configured to output encoded code words V1, V2, . . . , and Vn.
The LDPC check matrix includes m layers, each layer includes N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block includes N/n sub-matrixes, where iε[1, n], and N, m, n, and i are all positive integers.
With the encoding device provided in this embodiment of the present invention, the input K-bit information is equally divided into n blocks, so that a code length of information processed at a single time changes from a code length N of information processed at a single time in an existing LDPC encoding and decoding process to N/n (n is a positive integer). In this way, the code length of the information processed at a single time may be greatly shortened by reasonably selecting the number of blocks n. In another aspect, data input at each time is combined with multiple previously obtained encoded code words for check in an encoding and decoding process. By adopting such a convolutional encoding and decoding check method, a total code length of processing is greatly increased in logic, thereby effectively improving performance of encoding and decoding.
Further, as shown in FIG. 6, an encoding processing unit 502 includes:
a blocking module 5021, configured to equally divide input K-bit information into n blocks, where k1, k2, . . . , and kn are used to represent each block of information;
a data combining module 5022, configured to combine a kith block of information with n−1 encoded code words Vi−1, Vi−2, . . . , and Vi−n+1 of ki−1th, k−2th, . . . , and ki−n+1th blocks, to obtain a code word to be encoded, where when a sequence number of an encoded code word is smaller than or equal to 0, the encoded code word is history information; and
a processing module 5023, configured to perform, by using an LDPC check matrix, encoding on the code word to be encoded, where a generated check bit and the kith block of information form an encoded code word Vi.
A decoding device 70 provided in an embodiment of the present invention as shown in FIG. 7, includes:
a decoding inputting unit 701, configured to input encoded code words Vi, Vi−1, Vi−2, . . . , and Vi−n+1;
at least one decoding processing unit 702, configured to form the input encoded code words Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and perform decoding by using an LDPC check matrix, to obtain a kith block of information, where when a sequence number of an encoded code word is smaller than or equal to 0, the encoded code word is history information; and after obtaining k1th, k2th, . . . , and knth blocks of information after the decoding, combine them to obtain K-bit information; and
a decoding outputting unit 703, configured to output the K-bit information.
The LDPC check matrix includes m layers, each layer includes N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block includes N/n sub-matrixes, where iε[1, n], and N, m, n, and i are all positive integers.
With the decoding device provided in this embodiment of the present invention, input K-bit information is equally divided into n blocks, so that a code length of information processed at a single time changes from a code length N of information processed at a single time in an existing LDPC encoding and decoding process to N/n (n is a positive integer). In this way, the code length of the information processed at a single time may be greatly shortened by reasonably selecting the number of blocks n. In another aspect, data input at each time is combined with multiple previously obtained encoded code words for check in an encoding and decoding process. By adopting such a convolutional encoding and decoding check method, a total code length of processing is greatly increased in logic, thereby effectively improving performance of encoding and decoding.
Further, the at least one decoding processing unit 702 is further configured to form the input Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and perform decoding by using the LDPC check matrix, to obtain V′i, V′i−1, V′i−2, . . . , and V′i−n+1 and cached data Ci, Ci−1, Ci−2, and Ci−3; form the V′i, V′i−1, V′i−2, . . . , and V′i−n+1 and the cached data Ci, Ci−1, Ci−2, and Ci−3 into a code word and then perform decoding by using the LDPC check matrix again, and perform the foregoing decoding operation for the specified number of times in this manner, to obtain a kith block of information.
As shown in FIG. 8, a decoding device 70 further includes:
at least one caching unit 704, configured to store cached data, where the number of caching units 704 is one less than that of decoding processing units 702; and
a controlling unit 705, connected to at least one decoding processing unit 702 and the at least one caching unit 704 respectively, and configured to control enabling of the at least one decoding processing unit 702 and the at least one caching unit 704, so as to control a whole decoding procedure.
Further, when decoding is performed in a decoding method that adopts a concatenated pipelined convolutional manner and is based on an interleaved check matrix, as shown in FIG. 9, the number of caching units 704 is equal to that of the decoding processing units 702.
The caching unit 704 is further configured to perform interleaving processing on input data, so that data input into the caching unit 704 is combined with a block of random-interval data, to generate one block of code words that satisfy a check relation of the interleaved check matrix. The data input into the caching unit 704 includes an encoded code word and cached data.
Persons of ordinary skill in the art may understand that all or a part of steps in the foregoing method embodiments may be implemented by a program instructing relevant hardware. The program may be stored in a computer readable storage medium. When the program runs, the steps in the foregoing method embodiments are performed. The storage medium may be any medium that is capable of storing program codes, such as a ROM, a RAM, a magnetic disk, or an optical disk.
The foregoing descriptions are merely specific embodiments of the present invention, but are not intended to limit the protection scope of the present invention. Changes or replacements easily figured out by persons skilled in the art within the technical scope disclosed in the present invention shall all fall within the protection scope of the present invention. Therefore, the protection scope of the present invention shall be subject to that of the appended claims.

## Claims

1. An encoding method, comprising:
equally dividing input K-bit information into n blocks, wherein k1, k2, . . . , and kn are used to represent each block of information;
combining a kith block of information with n−1 encoded code words Vi−1, Vi−2, . . . , and Vi−n+1 of ki−1th, ki−2th, . . . , and ki−n+1th blocks, to obtain a code word to be encoded, wherein when a sequence number of an encoded code word is smaller than or equal to 0, the encoded code word is history information;
performing, by using a low density parity code LDPC check matrix, encoding on the code word to be encoded, wherein a generated check bit and the kith block of information form an encoded code word Vi; and
outputting encoded code words V1, V2, . . . , and Vn,
wherein the LDPC check matrix comprises m layers, each layer comprises N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block comprises N/n sub-matrixes, wherein iε[1, n], and N, m, n, and i are all positive integers.

2. A decoding method, comprising:
forming input encoded code words Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and performing decoding by using an LDPC check matrix, to obtain a kith block of information, wherein when a sequence number of the encoded code word is smaller than or equal to 0, the encoded code word is history information;
after obtaining k1th, k2th, . . . , and knth blocks of information after the decoding, combining them to obtain K-bit information; and
outputting the K-bit information,
wherein the LDPC check matrix comprises m layers, each layer comprises N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block comprises N/n sub-matrixes, wherein iε[1, n], and N, m, n, and i are all positive integers.

3. The method according to claim 2, wherein the forming input Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and performing decoding by using the LDPC check matrix, to obtain the kith block of information comprises:
forming the input Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and performing decoding by using the LDPC check matrix, to obtain V′i, V′i−1, V′i−2, . . . , and V′i−n+1 and cached data Ci, Ci−1, Ci−2, and Ci−3; and
forming V′i, V′i−1, V′i−2, . . . , and V′i−n+1 and the cached data Ci, Ci−1, Ci−2, and Ci−3 into a code word and then performing decoding by using the LDPC check matrix again, and performing the foregoing decoding operation for the specified number of times in this manner, to obtain the kith block of information.

4. The method according to claim 2, wherein n is smaller than N, and a value of N/n is a positive integer.

5. The method according to claim 3, wherein n is smaller than N, and a value of N/n is a positive integer.

6. An encoding device, comprising:
an encoding inputting unit, configured to input K-bit information;
an encoding processing unit, configured to equally divide the input K-bit information into n blocks, wherein k1, k2, . . . , and kn are used to represent each block of information; combine a kith block of information with n−1 encoded code words Vi−1, Vi−2, . . . , and Vi−n+1 of ki−1th, ki−2th, . . . , ki−n+1th blocks, to obtain a code word to be encoded, wherein when a sequence number of the encoded code word is smaller than or equal to 0, the encoded code word is history information; and perform, by using an LDPC check matrix, encoding on the code word to be encoded, wherein a generated check bit and the kith block of information form an encoded code word Vi; and
an encoding outputting unit, configured to output encoded code words V1, V2, . . . , and Vn,
wherein the LDPC check matrix comprises m layers, each layer comprises N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block comprises N/n sub-matrixes, wherein iε[1, n], and N, m, n, and i are all positive integers.

7. The encoding device according to claim 6, wherein the encoding processing unit comprises:
a blocking module, configured to equally divide the input K-bit information into n blocks, wherein k1, k2, . . . , and kn are used to represent each block of information;
a data combining module, configured to combine the kith block of information with n−1 encoded code words Vi−1, Vi−2, . . . , and Vi−n+1 of the ki−1th, ki−2th, . . . , and ki−n+1th blocks, to obtain a code word to be encoded, wherein when the sequence number of the encoded code word is smaller than or equal to 0, the encoded code word is history information; and
a processing module, configured to perform, by using the LDPC check matrix, encoding on the code word to be encoded, wherein the generated check bit and the kith block of information form the encoded code word Vi.

8. A decoding device, comprising:
a decoding inputting unit, configured to input encoded code words Vi, Vi−1, Vi−2, . . . , and Vi−n+1;
at least one decoding processing unit, configured to form the input encoded code words Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and perform decoding by using an LDPC check matrix, to obtain a kith block of information, wherein when a sequence number of the encoded code word is smaller than or equal to 0, the encoded code word is history information; and after obtaining k1th, k2th, . . . , and knth blocks of information after the decoding, combine them to obtain the K-bit information; and
a decoding outputting unit, configured to output the K-bit information,
wherein the LDPC check matrix comprises m layers, each layer comprises N sub-matrixes, the N sub-matrixes are equally divided into n blocks according to columns, and each block comprises N/n sub-matrixes, wherein iε[1, n], and N, m, n, and i are all positive integers.

9. The decoding device according to claim 8, wherein
the at least one decoding processing unit is further configured to form input Vi, Vi−1, Vi−2, . . . , and Vi−n+1 into one code word, and perform decoding by using the LDPC check matrix, to obtain V′i, V′i−1, V′i−2, . . . , and V′i−n+1 and cached data Ci, Ci−1, Ci−2, and Ci−3; form V′i, V′i−1, V′i−2, . . . , and V′i−n+1 and the cached data Ci, Ci−1, Ci−2, and Ci−3 into a code word and then perform decoding by using the LDPC check matrix again, and perform the foregoing decoding operation for the specified number of times in this manner, to obtain the kith block of information.

10. The decoding device according to claim 8, wherein the decoding device further comprises:
at least one caching unit, configured to store the cached data; and
a controlling unit, connected to the at least one decoding processing unit and the at least one caching unit respectively, and configured to control enabling of the at least one decoding processing unit and the at least one caching unit.

11. The decoding device according to claim 9, wherein the decoding device further comprises:
at least one caching unit, configured to store the cached data; and
a controlling unit, connected to the at least one decoding processing unit and the at least one caching unit respectively, and configured to control enabling of the at least one decoding processing unit and the at least one caching unit.