APPARATUS AND METHOD FOR LOW DENSITY PARITY CHECK (LDPC) ENCODING

Provided is a low density parity check (LDPC) encoding apparatus and method that may store M registers each including N bits, obtain N×M parity bits by performing a partial parallel operation an N×M number of times with respect to the M registers, and mutually invert subsequent N parity bits periodically, based on previous parity bits for each Nth parity bit of the N×M parity bits, respectively.

DETAILED DESCRIPTION

When it is determined that a detailed description is related to a related known function or configuration which may make the purpose of the present invention unnecessarily ambiguous in the description of the present invention, such a detailed description will be omitted. Also, terminologies used herein are defined to appropriately describe the exemplary embodiments of the present invention and thus may be changed depending on a user, the intent of an operator, or a custom. Accordingly, the terminologies must be defined based on the following overall description of this specification.

FIG. 1is a block diagram illustrating a configuration of a low density parity check (LDPC) encoding apparatus according to an embodiment of the present invention.

Referring toFIG. 1, the LDPC encoding apparatus may include a storage unit110, an operation unit120, and an inversion unit130. The storage unit may store M registers each including N bits. The operation unit120may obtain N×M parity bits, by performing a partial parallel operation an N×M number of times with respect to the M registers. The inversion unit130may mutually invert subsequent N parity bits periodically, based on previous parity bits for each Nth parity bit of the N×M parity bits, respectively.

FIG. 2is a diagram illustrating an H matrix structure for LDPC encoding according to an embodiment of the present invention.

Referring toFIG. 2, XX may include an H matrix of Digital Video Broadcasting-Satellite-Second Generation (DVB-S2) LDPC codes. The H matrix may include an information bit210corresponding to information bits, and a parity part220corresponding to parity bits. In the information bit210, a position of “1” may be distributed variously depending on a code rate. In the parity bit220, the position of “1” may be fixed in a stepped form, as shown inFIG. 1.

Although the DVB-S2 LDPC may be designed to perform a partial parallel operation 360 times, an operation for accumulating a previous value and a current value may be required in an encoding process and thus, performing the partial processing may be difficult.

According to an embodiment of the present invention, an LDPC encoding apparatus may perform a partial parallel operation for a predetermined number of bits with respect to a process prior to an accumulator operation, and mutually invert parity bits based on a result of performing the operation, thereby operating codes at a high speed.

FIG. 3is a diagram illustrating an LDPC encoding algorithm structure according to an embodiment of the present invention.

Referring toFIG. 3, an LDPC encoding apparatus may store M registers310, each including N bits, and obtain N×M parity bits by performing a partial parallel operation an N×M number of times with respect to the M registers310.

For ease of understanding and description, N may correspond to a value of “360” and M may correspond to a value of “90”.

For example, all information bits may be stored in groups of 360 bits sequentially in registers. When a code rate corresponds to 1/2, a number of registers each including 360 information bits may correspond to “90”. When all of the information bits are stored in the 90 registers, the LDPC encoding apparatus may perform a parity operation with respect each information bit, based on a first index list and a second index list.

FIG. 4is a block diagram illustrating a configuration of an operation unit400according to an embodiment of the present invention.

Referring toFIG. 4, the operation unit440may include an extraction unit410to extract at least one of M registers based on a first index list, and a permutation unit420to permute N bits included in the extracted register, using a second index list.

The extraction unit410may extract a respective register corresponding to at least one first index value included in the first index list. The permutation unit420may place a bit of a sequence corresponding to at least one second index value included in the second index list as a first bit, and arrange at least one subsequent bit sequentially.

FIG. 5is a diagram illustrating a first index list according to an embodiment of the present invention, andFIG. 6is a diagram illustrating a second index list according to an embodiment of the present invention.

Referring toFIGS. 5 and 6, at least one first index value with respect to a register may be stored in the first index list, and the second index list may indicate N bits included in a resister selected by a selected first index value. In particular, the second index list may indicate permutation values of 360 data included in the register selected by the first index value.

For example, an LDPC encoding apparatus may retrieve first index values of “26, 27, 30, 36, 74” from the first index list, and retrieve second index values of “60, 101, 293, 0, 179” from the second index list. The LDPC encoding apparatus may extract a 26th register, a 27th register, a 30th register, a 36th register, and a 74th register, among the registers ofFIG. 3, based on the retrieved index values, and perform a permutation task with respect to the extracted registers, respectively. In particular, the LDPC encoding apparatus may perform the permutation for a 60th bit of the 26th register to be placed first, and for a 59th bit of the 26th register to be placed last. Similarly, the LDPC encoding apparatus may perform the permutation for a 101st bit of the 27th register, a 293rd bit of the 30th register, a 0th bit of the 36th register, and a 179th bit of the 74th register, respectively, to be placed first.

The LDPC encoding apparatus may perform a parallel operation with respect to all 360 bits for each register. When an operation for a first row is completed, a parity bit Pa0may be obtained, and sequentially, parity bits Pa90, Pa180, Pa270, . . . , Pa32040may be obtained, as shown inFIG. 3.

In order to obtain subsequent parity bits based on previous parity bits, the LDPC encoding apparatus may store the 360 parity bits at a first address of a storage unit, and store the 360 parity bits in a register capable of storing 360 bits. In particular, the storage unit may store N×M parity bits in groups of N parity bits, at respective addresses.

The LDPC encoding apparatus may iterate the foregoing process 90 times, complete the parity operation for the information bits, and obtain the parity bits Pa0through Pa89shown inFIG. 3.

When the LDPC encoding apparatus extracts 360 parity bits at a last address of the storage unit, a parity bit Pa89, among the extracted parity bits, may correspond to data for which all operations are performed. However, although Pan=Pan⊕Pan-1is to be performed, the operation may be performed improperly with respect to a parity bit Pa90and subsequent parity bits. Accordingly, values of parity bits other than the parity bit Pa89may be imperfect.

The LDPC encoding apparatus may extract, using the inversion unit, N parity bits at a last address, among the respective addresses, and mutually invert subsequent N parity bits based on a last parity bit of the extracted N parity bits, respectively. In this instance, an initial parity bit of the previous parity bits may correspond to an Nth parity bit.

When the previous parity bits have predetermined values, the LDPC encoding apparatus may mutually invert, using the inversion unit, the subsequent N parity bits, respectively. In this instance, the predetermined values may correspond to a value of “1”.

The parity bit operation may be performed through an exclusive OR operation of a bit operation. For example, when the parity bit Pa89corresponds to a value of “1,” the LDPC encoding apparatus may invert all parity bits from Pa90to Pa179. In addition, when the parity bit Pa179corresponds to a value of “1,” the LDPC encoding apparatus may invert all parity bits from Pa180to Pa269.

In such a logic operation, the LDPC encoding apparatus may iterate the sequential process a total of 359 times, with respect to the 360 parity bits extracted at the last address of the storage unit, thereby operating a very last parity bit. Here, the sequential process may refer to the process of inverting the parity bit Pa179when the parity bit Pa89corresponds to a value of “1,” inverting the parity bit Pa269when the parity bit Pa179corresponds to a value of “1,” and the like.

When the operation for the very last parity bit is completed, the LDPC encoding apparatus may extract parity bits at the first address of the storage unit again, and invert or not invert the 360 parity bits, respectively.

q clocks may be used for an operation with respect to initial information bits, and 359 clocks may be used for an operation with respect to last parity bits. Here, q may correspond to 90 when a code rate corresponds to 1/2. In addition, the LDPC encoding process may be performed using a total of 2q+358+α clocks when q−1 clocks are used through the process of retrieving addresses of the storage unit. In this instance, a denotes a number of clocks used for varied operations, and reading/writing of the storage unit.

FIG. 7is a flowchart illustrating an LDPC encoding method according to an embodiment of the present invention.

Referring toFIG. 7, in operation710, an LDPC encoding apparatus may store M registers each including N bits. In operation720, the LDPC encoding apparatus may obtain N×M parity bits by performing a partial parallel operation an N×M number of times with respect to the M registers. In operation730, the LDPC may mutually invert subsequent N parity bits periodically, based on previous parity bits for each Nth parity bit of the N×M parity bits, respectively.

According to an embodiment of the present invention, there is provided an LDPC encoding apparatus and method capable of partial parallel processing.

According to an embodiment of the present invention, a giga-class high speed encoder may be implemented by performing a clock operation at a high speed.