Patent ID: 12199634

DETAILED DESCRIPTION

Hereinafter, various example embodiments will be described in detail with reference to the accompanying drawings.

FIG.1is a block diagram illustrating a communication system according to at least one example embodiment.

Referring toFIG.1, a communication system1according to at least one example embodiment may include a first electronic apparatus10and a second electronic apparatus20, but the example embodiments are not limited thereto, and for example, the communication system1may include a greater number of electronic apparatuses and/or other devices. The first electronic apparatus10and the second electronic apparatus20may be apparatuses that communicate with each other via at least one wireless channel included in the communication system1, but are not limited thereto, and for example may communicate using at least one wired channel and/or a combination of wireless and wired channels, etc. For example, each of the first electronic apparatus10and/or the second electronic apparatus20may be a base station and/or a terminal in a cellular-based communication system, such as a 5th generation (5G) system, a 4G system, a WiFi system, a Bluetooth system, etc., but the example embodiments are not limited thereto.

The first electronic apparatus10may include an encoding apparatus100and/or a transmission apparatus200, etc., but is not limited thereto, and for example, may include a greater or lesser number of constituent elements.

The encoding apparatus100may generate at least one codeword by encoding data to be transmitted to the second electronic apparatus20using, for example, a low density parity check (LDPC) code, but is not limited thereto. In this case, the encoding apparatus100may perform encoding by using a parity check matrix. For example, assuming the parity check matrix is H, and the codeword generated by the encoding apparatus100is x, the parity check matrix and the codeword may satisfy a relationship of Hx=0.

The transmission apparatus200may generate at least one transmission signal Tx by modulating the codeword, etc. In addition, the transmission apparatus200may transmit the transmission signal Tx to the second electronic apparatus20.

The second electronic apparatus20may include a decoding apparatus300and/or a reception apparatus400, etc., but is not limited thereto, and for example, may include a greater or lesser number of constituent elements.

The reception apparatus400may receive the transmission signal Tx from the first electronic apparatus10, etc., but is not limited thereto. In addition, the reception apparatus400may generate the LDPC code by modulating the transmission signal Tx.

The decoding apparatus300may generate, decode, and/or reconstruct, etc., the data transmitted by the first electronic apparatus10by performing decoding using the LDPC code, but the example embodiments are not limited thereto. For example, the decoding apparatus300may perform decoding by using the same parity check matrix as the parity check matrix used by the encoding apparatus100, etc.

According to some example embodiments, the decoding apparatus300may decode the LDPC code by using a layered scheduling method of decoding the parity check matrix into a plurality of layers, and sequentially decoding each layer, but is not limited thereto. In this case, one row of the parity check matrix may be referred to as a layer.

As described below with reference toFIGS.11A and11B, after variable node processing on a specific column included in a row of the parity check matrix to be processed first is completed, a stall may occur when check node processing is performed on a specific column included in a row of the parity check matrix to be processed next.

According to at least one example embodiment, the decoding apparatus300may decode the LDPC code by performing processing on a column included in a second row of the parity check matrix before processing all of the columns included in a first row of the parity check matrix is completed. That is, the decoding apparatus300may perform processing on one layer before processing on another layer is completed. As described above, the decoding apparatus300according to at least one example embodiment may reduce a stall that may occur (and/or reduce the probability that a stall occurs) during a decoding process, and accordingly, the LDPC code may be decoded faster.

A detailed structure and operation of the decoding apparatus300according to at least one example embodiment of the inventive concepts is described below in more detail.

FIG.2is a diagram illustrating an example of a parity check matrix of an LDPC code and a Tanner graph corresponding to the parity check matrix according to at least one example embodiment.

Referring toFIG.2,FIG.2illustrates a parity check matrix H having a size of 2*3 and a Tanner graph corresponding to the parity check matrix are on the left side of the figure.

The LDPC code may be decoded through a process of exchanging messages on the Tanner graph corresponding to the parity check matrix H. Each element of the parity check matrix H may indicate a connection between a check node and a variable node on the Tanner graph. In this case, each row of the parity check matrix H may correspond to a check node of the Tanner graph, and each column of the parity check matrix H may correspond to a variable node of the Tanner graph, etc.

For example, an element in a first row and a first column of the parity check matrix H may indicate whether a message is exchanged between a first check node Ci and a first variable node Vi of the Tanner graph. In this case, in the parity check matrix H, an element having a value of 1 may indicate that the message is exchanged between the check node and the variable node, and an element having a value of 0 may indicate that a message is not exchanged between the check node and the variable node.

On the right side ofFIG.2, a parity check matrix H′ in which each element of the parity check matrix H on the left side is extended to a size of Z*Z may be identified (e.g., Z=4, etc.). In this case, the extended parity check matrix H′ may be used in a quasi-cyclic (QC)-LDPC code used in communication systems, such as Wi-Fi, WiMax, and/or 5G systems, etc., but the example embodiment are not limited thereto.

Each element of the extended parity check matrix H′ may be represented by a small square submatrix having a size Z*Z, and each submatrix may be, e.g., a cyclic-permutation matrix in which a Z*Z unit matrix is cyclically shifted, but is not limited thereto. For example, in the extended parity check matrix H′, an element having a value of 0 may indicate a Z*Z unit matrix. In addition, in the extended parity check matrix H′, an element having a value of 3 may indicate a cyclic-permutation matrix generated by cyclically shifting the Z*Z unit matrix to the right three times. Also, in the extended parity check matrix H′, an element having a value of −1 may indicate a Z*Z zero matrix.

Hereinafter, for the sake of convenience of description and brevity, a parity check matrix having the same shape as the parity check matrix H shown on the left side ofFIG.2is mainly described, and it is assumed that a calculation desired and/or required for the extended parity check matrix H′ on the right side ofFIG.2is implicitly performed, but the example embodiment are not limited thereto.

FIG.3is a diagram illustrating a decoding apparatus according to at least one example embodiment.

Referring toFIG.3, the decoding apparatus300according to at least one example embodiment may include a memory310and/or a processing circuit320(e.g., processing circuitry, at least one processor, etc.), but the example embodiments are not limited thereto, and for example, the decoding apparatus300may include a greater or lesser number of constituent elements.

The memory310may store a scheduling table311, etc., but is not limited thereto. The scheduling table311may be a table indicating a processing order of rows included in a parity check matrix and/or columns included in each row of the parity check matrix, etc. The scheduling table311may be referenced by the processing circuit320, etc.

The processing order may include a row processing order, a column check node processing order, and/or a column variable node processing order, etc.

The row processing order may indicate an order in which processing on each row of the parity check matrix is performed and/or completed. The row processing order may be configured in consideration of and/or based on a weight assigned to each row included in the parity check matrix. In this case, the weight may be proportional to the number of columns that desire and/or require check node processing and/or variable node processing among columns included in a row included in the parity check matrix, but the example embodiments are not limited thereto. For example, the weight may indicate the number of elements having a value of 1 among elements included in each row of the parity check matrix, etc.

The row processing order according to at least one example embodiment may be configured such that a row having a relatively high weight (relative to the other rows of the matrix, e.g., the half of the rows of the matrix that have the highest weight, etc.) and a row having a relatively low weight (relative to the other rows of the matrix, e.g., the half of the rows of the matrix that have the lowest weight, etc.) are alternately processed, but is not limited thereto. At least one example embodiment in which the row processing order is configured based on the weight may be identified with reference toFIGS.13and15to be described below.

The column check node processing order may indicate an order of processing check nodes of columns included in one row of the parity check matrix. In addition, the column variable node processing order may indicate an order of processing variable nodes of columns included in at least one row of the parity check matrix.

The column check node processing order and the column variable node processing order may be configured such that, after the completion of variable node processing on a specific and/or desired column included in a first row of the parity check matrix to be processed first according to the row processing order, check node processing is performed on a specific and/or desired column included in a second row of the parity check matrix to be processed next (e.g., second, etc.) to the first row according to the row processing order. For example, the column check node processing order and the column variable node processing order may be configured such that, after variable node processing on a fifth column included in the first row of the parity check matrix is completed, check node processing is performed on a fifth column included in the second row, etc.

The processing circuit320may decode an LDPC code based on the scheduling table311. The processing circuit320may decode the LDPC code by performing check node processing including a plurality of check node processing operations and/or variable node processing including a plurality of variable node processing operations, etc. In this case, the processing circuit320may perform check node processing and variable node processing based on the scheduling table311stored in the memory310, but is not limited thereto. The processing circuit320may be implemented as hardware or a combination of hardware and software, etc. According to some example embodiments, the processing circuit320may be implemented as processing circuitry which may include hardware including logic circuits; a hardware/software combination such as a processor executing software and/or firmware; or a combination thereof. For example, the processing circuitry more specifically may include, but is not limited to, a central processing unit (CPU), an arithmetic logic unit (ALU), a digital signal processor, a microcomputer, a field programmable gate array (FPGA), a System-on-Chip (SoC), a programmable logic unit, a microprocessor, application-specific integrated circuit (ASIC), etc., but is not limited thereto. Further, according to some example embodiments, the processing circuitry may further include memory, such as the memory310and/or the posterior probability value memory323, check-variable memory324, and/or variable-check memory327, etc.

Some example embodiments of the processing circuit320will be described in more detail with reference toFIGS.4to6, and some example embodiments of the plurality of check node processing operations and the plurality of variable node processing operations will be described in more detail with reference toFIGS.7and8.

FIG.4is a diagram illustrating a detailed structure of a processing circuit, according to at least one example embodiment.

Referring toFIG.4, the processing circuit320according to at least one example embodiment may include a check node processing scheduler321, a variable node processing scheduler322, a posterior probability value memory323, a check-variable memory324, an extrinsic value calculator325, a minimum value calculator326, a variable-check memory327, an update calculator328, and/or a posterior probability value calculator329, etc., but is not limited thereto, and for example, may include a greater or lesser number of constituent elements. Also, the processing circuit320according to at least one example embodiment may further include a shifter330, etc.

The check node processing scheduler321may control a plurality of check node processing operations to be sequentially performed based on a processing order (e.g., a desired processing order). The check node processing scheduler321may read the scheduling table311stored in the memory310and control a check node processing operation performed by other components of the processing circuit320and/or performed by the processing circuit320based on the scheduling table311.

The variable node processing scheduler322may control the plurality of variable node processing operations to be sequentially performed based on the processing order. The variable node processing scheduler322may read the scheduling table311stored in the memory310and control a variable node processing operation performed by other components of the processing circuit320and/or performed by the processing circuit320based on the scheduling table311.

The posterior probability value memory323may store a plurality of posterior probability values respectively corresponding to a plurality of variable nodes.

The posterior probability value memory323may store, for example, a log-likelihood ratio (LLR) value of an LDPC code generated by the reception apparatus400, etc., as an initial posterior probability value, but is not limited thereto. In this case, the processing circuit320may determine that decoding is successful when a posterior probability value obtained by repeatedly performing check node processing and/or variable node processing by using the LLR value of the LDPC code satisfies a desired and/or preset condition. The posterior probability value memory323may store a posterior probability value changed during check node processing and/or variable node processing. In this case, a posterior probability value of a j-th variable node may be represented as Γj(where j is an integer greater than or equal to 0).

The check-variable memory324may store a plurality of check-variable values transmitted from a plurality of check nodes to a plurality of variable nodes. In this case, a check-variable value transmitted from an i-th check node to the j-th variable node may be represented as αij(where i is an integer greater than or equal to 0).

In order to reduce memory capacity requirements and/or the amount of memory used, the check-variable memory324may store a check-variable value when an element of a parity check matrix is non-zero. That is, when a check node is not connected to a variable node, the check-variable memory324may not store a corresponding check-variable value.

According to another example embodiment, in order to reduce memory capacity requirements and/or the amount of memory used, instead of storing the check-variable value αij, the check-variable memory324may store a sign of the check-variable value αij, a first minimum value (e.g., a first desired value) that is the smallest value among the check-variable values (αijhaving the same value of i) transmitted from the same check node, and a second minimum value (e.g., a second desired value) that is the second smallest value among the check-variable values (αijhaving the same value of i) transmitted from the same check node, and a column index j of the first minimum value, but the example embodiments are not limited thereto. In this case, an output of the check-variable memory324may be transmitted to the extrinsic value calculator325through an operation, for example, to be performed by the update calculator328, but the example embodiments are not limited thereto.

The extrinsic value calculator325may calculate a plurality of extrinsic values by subtracting the plurality of check-variable values from the plurality of posterior probability values, or in other words the extrinsic value calculator325may calculate the plurality of extrinsic values based on the plurality of check-variable values and the plurality of posterior probability values, etc.

The extrinsic value calculator325may read a posterior probability value from the posterior probability value memory323. Also, the extrinsic value calculator325may read a check-variable value from the check-variable memory324. In addition, the extrinsic value calculator325may calculate an extrinsic value by subtracting the check-variable value from the posterior probability value, or in other words, the extrinsic value calculator325may calculate an extrinsic value based on the check-variable value and the posterior probability value, etc.

According to at least one example embodiment, the extrinsic value calculator325may read a posterior probability value Γjof the j-th variable node from the posterior probability value memory323, read the check-variable value αijtransmitted from the i-th check node to the j-th variable node from the check-variable memory324, and/or calculate an extrinsic value Qijcorresponding to the i-th check node and the j-th variable node by subtracting the check-variable value αijfrom the posterior probability value Γj, etc., or in other words, the extrinsic value calculator325may calculate the extrinsic value Qijcorresponding to the i-th check node and the j-th variable node based on the check-variable value αijand the posterior probability value Γj. That is, the extrinsic value may be calculated by Equation 1 below.
Qij=Γj−αij[Equation 1]

The minimum value calculator326may receive a calculation result from the extrinsic value calculator325. In addition, the minimum value calculator326may calculate and/or determine a first minimum value and/or a second minimum value among the plurality of extrinsic values. For example, the minimum value calculator326may determine a first minimum value (e.g., a first desired value) by determining the smallest value among the plurality of extrinsic values, and the minimum value calculator326may determine a second minimum value (e.g., a second desired value) by determining the second smallest value among the plurality of extrinsic values, etc., but the example embodiments are not limited thereto, and for example, the minimum value calculator326may determine a single minimum value or three or more minimum values, etc.

The minimum value calculator326may calculate a first minimum value and/or a second minimum value for each row of the parity check matrix, but is not limited thereto. That is, the minimum value calculator326may calculate a first minimum value and a second minimum value among the plurality of extrinsic values for variable nodes connected to the same check node, etc.

The minimum value calculator326may include a plurality of buffers. In this case, each of the plurality of buffers may store the first minimum value and the second minimum value calculated for each row of the parity check matrix, but the example embodiments are not limited thereto. According to at least one example embodiment, the decoding apparatus300may decode the LDPC code by performing processing on a column included in a second row of the parity check matrix before processing on all columns included in a first row of the parity check matrix has been completed, or in other words, the decoding apparatus300may process the column in two or more rows of the parity check matrix concurrently and/or in parallel, etc. In this case, the minimum value calculator326may process the columns included in the second desired row while processing on the columns included in the first desired row is performed, but is not limited thereto, and for example, more than two rows may be concurrently processed and/or parallelly processed. In addition, the minimum value calculator326may temporarily store, in a first buffer of the plurality of buffers, a first minimum value and a second minimum value being calculated for a first row of the parity check matrix, and may store, in a second buffer of the plurality of buffers, a first minimum value and a second minimum value being calculated for a second row of the parity check matrix, etc. As described above, because the minimum value calculator326includes the plurality of buffers, the decoding apparatus300may decode the LDPC code by performing processing on the column included in the second row of the parity check matrix before processing on all columns included in the first row of the parity check matrix has been completed.

The first minimum value and the second minimum value calculated by the minimum value calculator326may be represented as Equations 2 and 3 below.

M⁢1i=minj∈V⁡(i)❘"\[LeftBracketingBar]"Qij❘"\[RightBracketingBar]"[Equation⁢2]M⁢2i=2⁢ndminj∈V⁡(i)❘"\[LeftBracketingBar]"Qij❘"\[RightBracketingBar]"[Equation⁢3]

In addition, an index of a variable node having the first minimum value calculated by the minimum value calculator326may be represented as Equation 4 below.

M⁢1index=argminj∈V⁡(i)❘"\[LeftBracketingBar]"Qij❘"\[RightBracketingBar]"[Equation⁢4]

According to at least one example embodiment, the minimum value calculator326may calculate the first minimum value and the second minimum value by applying an offset min sum (OMS) method, but the example embodiments are not limited thereto. In this case, when c is applied as an offset value, the minimum value calculator326may calculate the first minimum value by using Equation 5 below and calculate the second minimum value by using Equation 6 below.

M⁢1i=max(minj∈V⁡(i)❘"\[LeftBracketingBar]"Qij❘"\[RightBracketingBar]"-ε,0)[Equation⁢5]M⁢2i=max(2⁢ndminj∈V⁡(i)❘"\[LeftBracketingBar]"Qij❘"\[RightBracketingBar]"-ε,0)[Equation⁢6]

According to another example embodiment, the minimum value calculator326may calculate the first minimum value and the second minimum value by applying a scaled min sum (SMS) method, but the example embodiments are not limited thereto. In this case, when s is used as a scale value, the minimum value calculator326may calculate the first minimum value by using Equation 7 below and calculate the second minimum value by using Equation 8 below.

M⁢1i=s·minj∈V⁡(i)⁢❘"\[LeftBracketingBar]"Qij❘"\[RightBracketingBar]"[Equation⁢7]M⁢2i=s·2⁢ndminj∈V⁡(i)❘"\[LeftBracketingBar]"Qij❘"\[RightBracketingBar]"[Equation⁢8]

According to another example embodiment, the minimum value calculator326may calculate the first minimum value and the second minimum value by applying both the OMS method and the SMS method, but the example embodiments are not limited thereto. In this case, when c is applied as an offset value and s is applied as a scale value, the minimum value calculator326may calculate the first minimum value by using Equation 9 below and calculate the second minimum value by using Equation 10 below.

M⁢1i=max(s·minj∈V⁡(i)⁢❘"\[LeftBracketingBar]"Qij❘"\[RightBracketingBar]"-ε,0)[Equation⁢9]M⁢2i=max(s·2⁢ndminj∈V⁡(i)❘"\[LeftBracketingBar]"Qij❘"\[RightBracketingBar]"-ε,0)[Equation⁢10]

The variable-check memory327may store the plurality of extrinsic values. The variable-check memory327may receive and store the plurality of extrinsic values calculated by the extrinsic value calculator325.

The update calculator328may receive the first minimum value and/or the second minimum value, e.g., a plurality of minimum values, from the minimum value calculator326, etc. The update calculator328may recalculate a plurality of check-variable values based on the first minimum value and the second minimum value (e.g., recalculate the plurality of check-variable values based on the plurality of minimum values), etc. In this case, a check-variable value may be recalculated using Equations 11 to 14 below.

αij′=δij·minj′∈V⁡(i)\j⁢❘"\[LeftBracketingBar]"Qij′❘"\[RightBracketingBar]"[Equation⁢11]δij=λisign⁡(Qij)[Equation⁢12]λi=∏j′∈V⁡(i)sign⁡(Qij′)[Equation⁢13]minj′∈V⁡(i)\j❘"\[LeftBracketingBar]"Qij′❘"\[RightBracketingBar]"={M⁢2i⁢if⁢j=M⁢1indexM⁢1i⁢otherwise[Equation⁢14]

In addition, the plurality of check-variable values recalculated by the update calculator328may be updated and stored in the check-variable memory324.

The posterior probability value calculator329may recalculate a plurality of posterior probability values by summing the plurality of extrinsic values and the plurality of recalculated check-variable values, or in other words, the posterior probability value calculator329may recalculate a plurality of posterior probability values based on the plurality of extrinsic values and the plurality of recalculated check-variable values, but the example embodiments are not limited thereto.

The posterior probability value calculator329may read an extrinsic value from the variable-check memory327. Also, the posterior probability value calculator329may read a recalculated check-variable value from the update calculator328. In addition, the posterior probability value calculator329may recalculate a posterior probability value by summing the extrinsic value and the recalculated check-variable value, or in other words, the posterior probability value calculator329may recalculate a posterior probability value based on the extrinsic value and the recalculated check-variable value, etc.

According to at least one example embodiment, the posterior probability value calculator329may read an extrinsic value Qijcorresponding to the i-th check node and the j-th variable node from the variable-check memory327, read a check-variable value α′ijcorresponding to the i-th check node and the j-th variable node from the update calculator328, and recalculate a posterior probability value Γ′jof the j-th variable node by summing the extrinsic value Qijand the recalculated check-variable value α′ij. In other words, the posterior probability value calculator329may recalculate a posterior probability value Γ′jof the j-th variable node based on the extrinsic value Qijand the recalculated check-variable value α′ij. That is, the recalculated posterior probability value Γ′jmay be as in Equation 15 below.
Γ′j=Qij+α′ij[Equation 15]

In addition, the plurality of posterior probability values recalculated by the posterior probability value calculator329may be updated and stored in the posterior probability value memory323.

The shifter330may shift the posterior probability value stored in the posterior probability value memory323and output the posterior probability value to the extrinsic value calculator325. The shifter330is a component desired and/or required for block-by-block decoding of the LDPC code, and may be omitted when block-by-block decoding is not desired and/or unnecessary, etc.

FIG.5is a diagram illustrating a detailed structure of a processing circuit, according to at least one example embodiment.

Referring toFIG.5, at least one example embodiment of the processing circuit320may be identified. In this case, unlikeFIG.4, although the check node processing scheduler321and the variable node processing scheduler322are not shown inFIG.5, at least one example embodiment ofFIG.5may also include the check node processing scheduler321and/or the variable node processing scheduler322, etc. Because the structure and operation of the processing circuit320ofFIG.5are similar to those shown inFIG.4, differences will be mainly described below.

A posterior probability value memory may include a first posterior probability value memory323_1and/or a second posterior probability value memory323_2, but the example embodiments are not limited thereto, and the posterior probability value memory may have a greater or lesser number of sub-memories and/or sub-memory regions, etc. The first posterior probability value memory323_1may store a plurality of first posterior probability values respectively corresponding to variable nodes that do not correspond to a puncturing area and/or a diagonal matrix area of a parity check matrix, but is not limited thereto. In addition, the second posterior probability value memory323_2may store a plurality of second posterior probability values respectively corresponding to variable nodes that correspond to the puncturing area and/or the diagonal matrix area of the parity check matrix, but is not limited thereto. The puncturing area of the parity check matrix refers to one or more columns of the parity check matrix which correspond to and/or include entries (e.g., parity bits) which have been removed from the parity check matrix. The diagonal matrix area of the parity check matrix corresponds to a diagonal area of the matrix in which the entries outside the diagonal are all zero. A detailed illustration of the puncturing area and the diagonal matrix area is given below with reference toFIG.9.

Among the plurality of second posterior probability values stored in the second posterior probability value memory323_2, a plurality of second posterior probability values corresponding to the diagonal matrix area may be stored in the same storage space. This is because the plurality of second posterior probability values corresponding to the diagonal matrix area do not change the extrinsic value and only need to maintain the posterior probability value before being hard-decided and output, etc.

The second posterior probability value memory323_2may include at least one flip-flop, etc., but is not limited thereto. Because the number of variable nodes corresponding to the puncturing area of the parity check matrix is a prime number, and a plurality of second posterior probability values respectively corresponding to variable nodes that correspond to the diagonal matrix area may be shared and stored, the second posterior probability value memory323_2may store a small number of values. Accordingly, the second posterior probability value memory323_2stores the plurality of second posterior probability values through the flip-flop, such that a delay occurring in reading and/or writing of a second posterior probability value may be significantly reduced.

In this case, only one of a first posterior probability value stored in the first posterior probability value memory323_1and a second posterior probability value stored in the second posterior probability value memory323_2may be output to the shifter330through a first multiplexer (MUX)332, but the example embodiments are not limited thereto. The first MUX332may output one of the first posterior probability value and the second posterior probability value based on a signal (e.g., control signal, etc.) received from the check node processing scheduler321. The check node processing scheduler321may output the second posterior probability value in response to check node processing and/or variable node processing corresponding to the puncturing area and/or the diagonal matrix area of the parity check matrix based on a scheduling table is desired and/or required, and may output the first posterior probability value in response to check node processing and/or variable node processing that does not correspond to the puncturing area and/or the diagonal matrix area of the parity check matrix is desired and/or required.

An update calculator may include, for example, a first update calculator328_1and a second update calculator328_2, etc., but is not limited thereto, and for example, may include a greater or lesser number of update calculators, etc. The first update calculator328_1may recalculate a plurality of first check-variable values respectively corresponding to the plurality of first posterior probability values. In addition, the second update calculator328_2may recalculate a plurality of second check-variable values respectively to the plurality of second posterior probability values.

A check-variable memory may include, for example, a first check-variable memory324_1and a second check-variable memory324_2, but is not limited thereto, and for example, may include a greater or lesser number of check-variable memories, etc. The first check-variable memory324_1may store a plurality of first check-variable values. The second check-variable memory324_2may store a plurality of second check-variable values.

In this case, only one of a first check-variable value stored in the first check-variable memory324_1and a second check-variable value stored in the second check-variable memory324_2may be output to the extrinsic value calculator325through a second MUX333, but the example embodiments are not limited thereto. The second MUX333may output one of the first check-variable value and the second check-variable value based on a signal received from the check node processing scheduler321. The check node processing scheduler321may output the second check-variable value when check node processing and/or variable node processing corresponding to the puncturing area and/or the diagonal matrix area of the parity check matrix based on a scheduling table is desired and/or required, and may output the first check-variable value when check node processing and/or variable node processing that does not correspond to the puncturing area and/or the diagonal matrix area of the parity check matrix is desired and/or required.

A variable-check memory may include a first variable-check memory327_1and a second variable-check memory327_2, but is not limited thereto, and for example, may include a greater or lesser number of variable-check memories, etc. The first variable-check memory327_1may store a plurality of first extrinsic values calculated based on the plurality of first posterior probability values, etc. In addition, the second variable-check memory327_2may store a plurality of second extrinsic values calculated based on the plurality of second posterior probability values, etc.

In this case, among a plurality of extrinsic values calculated by the extrinsic value calculator325, a first extrinsic value may be transmitted to the first variable-check memory327_1through a demultiplexer (DEMUX)334, and a second extrinsic value may be transmitted to the second variable-check memory327_2through the DEMUX334, etc. The DEMUX334may transmit the first extrinsic value or the second extrinsic value to the first variable-check memory327_1and/or the second variable-check memory327_2based on a signal (e.g., control signal, etc.) received from the check node processing scheduler321. The check node processing scheduler321may transmit, when a second extrinsic value corresponding to the puncturing area and/or the diagonal matrix area of the parity check matrix based on the scheduling table is calculated, the second extrinsic value to the second variable-check memory327_1, and may transmit, when a first extrinsic value that does not correspond to the puncturing area and/or the diagonal matrix area of the parity check matrix is calculated, the first extrinsic value to the first variable-check memory327_1.

A posterior probability value calculator may include for example, a first posterior probability value calculator329_1and a second posterior probability value calculator329_2, but is not limited thereto, and for example, may include a greater or lesser number of posterior probability value calculators, etc. The first posterior probability value calculator329_1may recalculate the plurality of first posterior probability values by summing the plurality of first extrinsic values and the plurality of first check-variable values, etc. In addition, the second posterior probability value calculator329_2may recalculate the plurality of second posterior probability values by summing the plurality of second extrinsic values and the plurality of second check-variable values, etc.

The processing circuit320may further include a diagonal matrix memory331. The diagonal matrix memory331may store a plurality of initial posterior probability values corresponding to the diagonal matrix area of the parity check matrix. The diagonal matrix area of the parity check matrix corresponds to a diagonal area of the matrix in which the entries outside the diagonal are all zero. Due to the characteristics of the parity check matrix, a variable node corresponding to the diagonal matrix area is connected to one check node. Accordingly, an extrinsic value corresponding to a variable node that corresponds to the diagonal matrix area of the parity check matrix has the same value as an initial posterior probability value. Therefore, by directly connecting the diagonal matrix memory331to the minimum value calculator326, the diagonal matrix memory331stores the plurality of initial posterior probability values corresponding to the diagonal matrix area of the parity check matrix, and a part of the variable node processing operation corresponding to a diagonal matrix may be omitted.

As described above, the processing circuit320according to at least one example embodiment may perform variable node processing on variable nodes that do not correspond to the puncturing area and/or the diagonal matrix area of the parity check matrix through the first posterior probability value memory323_1, the first check-variable memory324_1, the first variable-check memory327_1, the first update calculator328_1, and/or the first posterior probability value calculator329_1, etc., and may perform variable node processing on variable nodes corresponding to the puncturing area and/or the diagonal matrix area of the parity check matrix through the second posterior probability value memory323_2, the second check-variable memory324_2, the second variable-check memory327_2, the second update calculator328_2, and/or the second posterior probability value calculator329_2, etc. In addition, the initial posterior probability value may be directly transmitted to the minimum value calculator326through the diagonal matrix memory331. As described above, by performing variable node processing corresponding to the puncturing area and/or the diagonal matrix area of the parity check matrix through a separate memory and calculator and using the diagonal matrix memory331, the time required for decoding of the entire LDPC code may be reduced.

FIG.6is a diagram illustrating a detailed structure of the processing circuit, according to at least one example embodiment.

Referring toFIG.6, at least one example embodiment of the processing circuit320may be identified. In this case, unlikeFIG.4, although the check node processing scheduler321and the variable node processing scheduler322are not shown inFIG.6, at least one example embodiment ofFIG.6may also include the check node processing scheduler321and/or the variable node processing scheduler322, but is not limited thereto. Because the structure and operation of the processing circuit320ofFIG.6are similar to those shown inFIG.4, differences are mainly described.

Unlike the processing circuit320ofFIG.5, the processing circuit320ofFIG.6may include one variable-check memory327, and the variable-check memory327may store a plurality of first extrinsic values calculated based on a plurality of first posterior probability values. In addition, a plurality of second extrinsic values calculated by the extrinsic value calculator325may be transmitted to the second posterior probability value memory323_2. Accordingly, the reason that the second posterior probability value memory323_2may also be used as a memory storing the plurality of second extrinsic values is that, as described above, the second posterior probability value memory323_2is implemented as a flip-flop and thus may independently and/or simultaneously read from and write to each storage space corresponding to a variable node, and the flip-flop has less time delay in comparison to other memory devices.

The plurality of second extrinsic values received by the second posterior probability value memory323_2may be input to the second posterior probability value calculator329_2and may be used to calculate a second posterior probability value. That is, the second posterior probability value calculator329_2may recalculate a plurality of second posterior probability values by summing a plurality of initial posterior probability values and a plurality of second check-variable values, or in other words, the second posterior probability value calculator329_2may recalculate a plurality of second posterior probability values based on the plurality of initial posterior probability values and the plurality of second check-variable values, etc. In this case, an extrinsic value corresponding to a recalculated second posterior probability value stored in the second posterior probability value memory323_2may be updated with the recalculated second posterior probability value.

FIG.7is a flowchart illustrating a check node processing operation performed by the decoding apparatus, according to at least one example embodiment.

Referring toFIG.7, first, in operation S710, a processing circuit may read a posterior probability value from a posterior probability value memory. The posterior probability value read from the posterior probability value memory may be input to a shifter, but the example embodiments are not limited thereto.

In operation S720, the processing circuit may read a check-variable value from a check-variable memory. The check-variable value read from the check-variable memory may be input to an extrinsic value calculator. Also, in operation S720, the posterior probability value may be shifted and input to the extrinsic value calculator, but the example embodiments are not limited thereto.

In operation S730, the processing circuit may calculate an extrinsic value based on the check-variable value and the posterior probability value, etc. For example, the processing circuit may calculate the extrinsic value by subtracting the check-variable value from the posterior probability value using the extrinsic value calculator, etc.

In operation S740, the processing circuit may calculate and/or determine a plurality of minimum values, e.g., a first minimum value and a second minimum value, etc., among a plurality of extrinsic values for variable nodes connected to the same check node. In addition, the extrinsic value calculated in operation S730may be stored in the variable-check memory in operation S740.

In operation S750, the processing circuit may recalculate the check-variable value based on the determined plurality of minimum values, e.g., the first minimum value and the second minimum value, etc.

Operations S710to S750as described above may be controlled to be processed by other components of the processing circuit through a check node processing scheduler, but the example embodiments are not limited thereto. In this case, the check node processing scheduler may cause each of operations S710to S750to be processed by other components of the processing circuit by using a pipelined manner, but is not limited thereto. In addition, each of operations S710to S750may be processed in one clock cycle, but is not limited thereto.

FIG.8is a flowchart illustrating a variable node processing operation performed by the decoding apparatus, according to at least one example embodiment.

Referring toFIG.8, first, in operation S810, a processing circuit may read an extrinsic value from a variable-check memory. The extrinsic value read from the variable-check memory may be input to a posterior probability value calculator, but is not limited thereto.

In operation S820, the processing circuit may read the extrinsic value and a check-variable value recalculated by an update calculator. The recalculated check-variable value may be input to the posterior probability value calculator. Also, in operation S820, the posterior probability value calculator may recalculate the posterior probability value based on the input extrinsic value and the recalculated check-variable value, e.g., by summing the input extrinsic value and the recalculated check-variable value.

In operation S830, the processing circuit may update and store the recalculated posterior probability value in the posterior probability value memory, but the example embodiments are not limited thereto.

According to some example embodiments, the components of the processing circuit may be controlled by a variable node processing scheduler to perform operations S810to S830, but the example embodiments are not limited thereto. In this case, the variable node processing scheduler may cause each of operations S810to S830to be processed by other components of the processing circuit in a pipelined manner, but the example embodiments are not limited thereto. In addition, each of operations S810to S830may be processed in one clock cycle, but are not limited thereto.

FIG.9is a diagram illustrating an example of a parity check matrix used in a 5G communication system according to some example embodiments.

Referring toFIG.9, an example of the parity check matrix that may be used in the 5G communication system may be identified. In this case, the parity check matrix may include a total of 46 rows and 68 columns, but the example embodiments are not limited thereto. In this case, the sixty eight (68) columns may include twenty two (22) information columns91, four (4) core parity columns92, and forty two (42) extended parity columns93from the left. In addition, the forty six (46) rows may include four (4) core check rows94and forty two (42) extended check rows95from the top. The parity check matrix may be divided into a plurality of areas as shown inFIG.10, but is not limited thereto.

FIG.10is a diagram for describing a structure of the parity check matrix ofFIG.9according to some example embodiments.

Referring toFIG.10, the parity check matrix may be divided into a total of 5 areas, but the example embodiments are not limited thereto. First, an area A may be an area including twenty two (22) information columns91and four (4) core check rows94. In addition, an area B may be an area including four (4) core parity columns92and four (4) core check rows94. In this case, when only the areas A and B are used, the highest coding rate may be obtained, but the example embodiments are not limited thereto.

An area C may be an area including forty two (42) extended parity columns93and four (4) core check rows94. The area C may be a zero matrix in which all elements are 0, but the example embodiments are not limited thereto.

An area D may be an area including twenty two (22) information columns91, four (4) core parity columns92, and forty two (42) extended check rows95. In addition, an area E may be an area include forty two (42) extended parity columns93and forty two (42) extended check rows95. The area E may be a 42*42 unit matrix, but is not limited thereto. In this case, when only the areas D and E are used, a low coding rate may be obtained.

In this regard, two left columns of the areas A and D may be a puncturing area, but the example embodiments are not limited thereto. That is, the two left columns of the areas A and D may be columns corresponding to and/or including bits punctured (e.g., removed parity bits) and transmitted in a codeword encoded with an LDPC code. In other words, an original codeword may be “punctured” by removing parity bits corresponding to and/or included in the puncturing areas A and/or D of the parity check matrix to further increase the coding rate of the code word, etc.

InFIGS.11to16, some example embodiments of a processing order of the decoding apparatus for an LDPC code encoded based on the parity check matrix as shown inFIG.9and a scheduling table indicating the processing order may be identified. In the following description, rows of the parity check matrix may be represented by row indices 0 to 45 in order from the top row, and columns of the parity check matrix may be represented by column indices 0 to 67 in order from the leftmost column, however the example embodiments are not limited thereto, and there may be a greater or lesser number of rows and/or columns in the parity check matrix.

FIGS.11A and11Bare diagrams illustrating an example of an order of performing check node processing and variable node processing by the decoding apparatus, according to at least one comparative example embodiment.

Referring toFIG.11A, a processing order of check node processing operations for decoding of an LDPC code having a coding rate of, e.g., 22/28 by the decoding apparatus according to the comparative example may be identified, but the example embodiments are not limited thereto, and for example, a different coding rate for the LDPC code may be used. In this case, a row processing order of the check node processing operations is described as a row index in the leftmost column of the table. In the comparative example embodiment ofFIG.11A, the row processing order may be 0, 1, 2, 3, 4, and 5 as a row index.

In addition, a column check node processing order for columns corresponding to each row index is shown on the right side of the row index. In at least one example embodiment ofFIG.11A, the column check node processing order for columns included in a row having a row index of 0 may be 2, 5, 6, 9, 10, . . . as a column index, and the column check node processing order for columns included in a row having a row index of 4 may be 26, 0, and 1 as a column index, etc.

Referring toFIG.11B, a processing order of variable node processing operations for decoding of an LDPC code having a coding rate of, e.g., 22/28 by the decoding apparatus according to the comparative example may be identified, but the example embodiments are not limited thereto, and for example, a different coding rate for the LDPC code may be used. In this case, a row processing order of the variable node processing operations is described as a row index in the leftmost column of the table. In the comparative example embodiment ofFIG.11B, the row processing order may be 0, 1, 2, 3, 4, and 5 as a row index, and this may be the same as the row processing order of the check node processing operations shown inFIG.11A.

In addition, a column variable node processing order for columns corresponding to each row index is shown on the right side of the row index. In the comparative example embodiment ofFIG.11B, the column check node processing order for columns included in a row having a row index of 0 may be 0, 2, 3, 5, 9, . . . as a column index, and the column check node processing order for columns included in a row having a row index of 4 may be 0, 1, and 26 as a column index. In this case, as shown inFIGS.11A and11B, a column check node processing order and a column variable node processing order for the same row index may be different from each other, but the example embodiments are not limited thereto.

FIGS.12A to12Dare diagrams illustrating an example of a scheduling table used by the decoding apparatus according to at least one comparative example embodiment.

Referring toFIGS.12A to12D, a scheduling table generated according to the processing order as shown inFIGS.11A and11Bmay be identified, but the example embodiments are not limited thereto.

The top row in the scheduling table indicates a clock sequence number, but the example embodiments are not limited thereto. In addition, in the leftmost column, numbers of check node processing operations and variable node processing operations are shown. In this case, operations R1 to R5 may respectively correspond to operations S710to S750, which are check node processing operations shown inFIG.7, and operations W1 to W3 may respectively correspond to operations S810to S830, which are variable node processing operations shown inFIG.8, however, the example embodiments are not limited thereto.

In this case, operation R1, which is scheduled to be performed first among the check node processing operations, may start during a first clock cycle and may be performed according to and/or based on the processing order ofFIG.11A, but is not limited thereto. In addition, operation R2, which is scheduled to be performed second among the check node processing operations, may start during a second clock cycle, and operations R3 to R5, etc., may also sequentially start in a pipelined manner, but the example embodiments are not limited thereto.

Furthermore, operation W1, which is scheduled to be performed first among the variable node processing operations, may start during a clock cycle in which operation R5 for a row index on which variable node processing is scheduled to be performed and/or completed. For example, operation W1 for a row having a row index of 0 may start during a twenty-third clock cycle in which operation R5 for a row having a row index of 0 is performed last. In other words, the variable node processing operation W1 for row 0 starts during the same clock cycle that a check node processing for row 0 is completed.

In the aforementioned manner, inFIGS.12A and12B, a check node processing operation for rows having row indices of, e.g., 0 to 2 (e.g., 0, 1, 2, etc.) may be completed, and a variable node processing operation for columns having column indices of, e.g., 0 and 1, may be completed, etc. In addition, referring toFIG.12C, it may be identified that, after a check node processing operation for a row having a row index of 3 is completed, when a check node processing operation is performed on a row having a row index of 4, a stall occurs in the middle of the operations. In at least one example embodiment ofFIG.12C, in the case of operation R1, it may be identified that a stall occurs in a seventy-eighth clock cycle to an eighty-second clock cycle, etc. In addition, in the case of operation R2, it may be identified that a stall occurs in a seventy-ninth clock cycle to an eighty-third clock cycle. Also, due to the characteristics of a pipelined method, even in operations R3, R4, and R5, it may be identified that stalls having the same length propagate with a one-clock cycle delay, compared to a previous processing operation.

Such stalls may have occurred because, after variable node processing on specific columns included in a first row of the parity check matrix to be processed first according to the row processing order is completed, check node processing may be performed on specific columns included in a second row of the parity check matrix to be processed next to the first row according to the row processing order. In at least one example embodiment ofFIG.12C, this is because, after all of the variable node processing operations for a column having a column index of 0 in a row having a row index of 3, on which processing needs to be performed first, are finished, a check node processing operation for a column having a column index of 0 in a row having a row index of 4, on which processing needs to be performed next to the row having a row index of 3, may start. Accordingly, operation R1 for the column having a column index of 0 in the row having a row index of 4 may be performed during an eighty-third clock cycle, which follows an eighty-second clock cycle in which operation W3 for the column having a column index of 0 in the row having a row index of 3 is performed.

Similarly, inFIGS.12C and12D, it may be identified that a stall occurs when a check node processing operation and a variable node processing operation are performed on a row having a row index of 5.

As described above, in the decoding apparatus according to the comparative example, it may be identified that a stall occurs in the middle of the check node processing operation and the variable node processing operation, and thus, decoding of the LDPC code is delayed.

FIGS.13A and13Bare diagrams illustrating an example of an order of performing check node processing and variable node processing by the decoding apparatus, according to at least one example embodiment.

Referring toFIG.13A, a processing order of check node processing operations for decoding of an LDPC code having a coding rate of, e.g., 22/28 by the decoding apparatus according to at least one example embodiment may be identified, but the example embodiments are not limited thereto, and for example, a different coding rate for the LDPC code may be used. In this case, a row processing order of the check node processing operations is described as a row index in the leftmost column of the table. In at least one example embodiment ofFIG.13A, the row processing order may be 4, 1, 5, 0, 2, and 3 as a row index, but the example embodiments are not limited thereto.

As described above, the row processing order according to at least one example embodiment may be configured such that a row having a relatively high weight and a row having a relatively low weight are alternately processed (e.g., a first high weight row is processed first, a first low weight row is processed second, a second high weight row is processed third, a second low weight row is processed fourth, etc.). In at least one example embodiment ofFIG.13A, after check node processing operations are performed on a row having a relatively low weight of 3 and a row index of 4, check node processing operations may be performed on a row having a relatively high weight of 19 and a row index of 1, etc. In addition, after the check node processing operations are performed on the row having a row index of 1, check node processing operations may be performed on a row having a relatively low weight of 8 and a row index of 5, etc.

In addition, a column check node processing order for columns corresponding to each row index is described on the right side of the row index. In at least one example embodiment ofFIG.13A, the column check node processing order for columns included in a row having a row index of 4 may be 26, 0, and 1 as a column index, and the column check node processing order for columns included in a row having a row index of 1 may be 23, 2, 5, 9, 15, . . . as a column index, but the example embodiments are not limited thereto.

Referring toFIG.13B, a processing order of variable node processing operations for decoding of an LDPC code having a coding rate of, e.g., 22/28 by the decoding apparatus according to at least one example embodiment may be identified. In this case, a row processing order of the variable node processing operations is shown as a row index in the leftmost column of the table. In at least one example embodiment ofFIG.13B, the row processing order may be 4, 1, 5, 0, 2, and 3 as a row index, and this may be the same as the row processing order of the check node processing operations shown inFIG.13A, but the example embodiments are not limited thereto.

In addition, a column variable node processing order for columns corresponding to each row index is shown on the right side of the row index. In at least one example embodiment ofFIG.13B, the column check node processing order for columns included in a row having a row index of 4 may be 0, 1, and 26 as a column index, and the column check node processing order for columns included in a row having a row index of 1 may be 0, 3, 12, 16, 21, . . . as a column index, but the example embodiments are not limited thereto. In this case, as shown inFIGS.13A and13B, a column check node processing order and a column variable node processing order for the same row index may be different from each other, but are not limited thereto.

FIGS.14A to14Dare diagrams illustrating an example of a scheduling table used by the decoding apparatus, according to at least one example embodiment.

Referring toFIGS.14A to14D, a scheduling table generated according to and/or based on the processing order as shown inFIGS.13A and13Bmay be identified, but is not limited thereto. In this case, in the scheduling table ofFIGS.14A to14D, check node processing operations and variable node processing operations may sequentially start in a pipelined manner, similar to the scheduling table ofFIGS.12A to12D, but the example embodiments are not limited thereto.

However, inFIG.14A, although a check node processing operation for a row having a row index of 4, the row being positioned and/or scheduled first in a row processing order, starts later than a check node processing operation for a row having a row index of 1, the row being positioned and/or scheduled later in the row processing order, the check node processing operation for the row having a row index of 4 may start before the check node processing operation for all columns included in the row having a row index of 1 has been completed, and, therefore, the check node processing operation for the row having a row index of 4 may be completed earlier.

As described above, according to at least one example embodiment, the decoding apparatus may decode an LDPC code by performing processing on a column included in a second row of the parity check matrix before processing on all columns included in a first row of the parity check matrix is completed. Accordingly, unlike the comparative example embodiment shown inFIG.12C, a stall that may occur while the check node processing operation is performed on the row having a row index of 4 may be reduced, avoided, and/or prevented.

Also, inFIGS.14A and14B, a check node processing operation for a row having a row index of 5, the row being positioned and/or scheduled earlier in the row processing order, may start later than a check node processing operation for a row having a row index of 0, the row being positioned and/or scheduled later in the row processing order, but the example embodiments are not limited thereto. In addition, the check node processing operation for the row having a row index of 5 may start before the check node processing operation for all columns included in the row having a row index of 0 has completed, and the check node processing operation for the row having a row index of 5 may be completed earlier, but the example embodiments are not limited thereto.

Similarly, even inFIGS.14C and14D, in which repeated processing for rows having row indices of 1, 4, 0, and 5 are shown, it may be identified that processing is configured to be performed on a column included in a second row of the parity check matrix before processing on all columns included in a first row of the parity check matrix is completed.

In this case, when the decoding apparatus according to the comparative example ofFIGS.11A to12Dis compared with the decoding apparatus according to at least one example embodiment ofFIGS.13and14, it may be identified that the decoding apparatus according to the comparative example requires a total of 103 clocks to complete the check node processing operation once, whereas the decoding apparatus according to at least one example embodiment requires a total of 87 clocks to complete the check node processing operation once.

As described above, according to at least one example embodiment, the decoding apparatus may decode the LDPC code at a higher speed and/or within a reduced amount of time by removing a stall that may occur in the middle of decoding by using the processing order shown inFIGS.13A to14Dand the scheduling table indicating the processing order.

FIGS.15A to15Care diagrams illustrating an example of an order of performing check node processing and variable node processing by the decoding apparatus, according to at least one example embodiment.

Referring toFIG.15A, a processing order of check node processing operations for decoding of an LDPC code having a coding rate of, e.g., 22/36 by the decoding apparatus according to at least one example embodiment may be identified, but the example embodiments are not limited thereto, and for example, a different coding rate for the LDPC code may be used. In this case, a row processing order of the check node processing operations is described as a row index in the leftmost column of the table. In at least one example embodiment ofFIG.15A, the row processing order may be 4, 1, 5, 0, 6, 3, . . . as a row index, but is not limited thereto.

As described above, the row processing order according to at least one example embodiment may be configured such that a row having a relatively high weight and a row having a relatively low weight are alternately processed. In at least one example embodiment ofFIG.15A, after check node processing operations are performed on a row having a relatively low weight of 3 and a row index of 4, check node processing operations may be performed on a row having a relatively high weight of 19 and a row index of 1, etc., but the example embodiments are not limited thereto. In addition, after the check node processing operations are performed on the row having a row index of 1, check node processing operations may be performed on a row having a relatively low weight of 8 and a row index of 5, etc.

In addition, a column check node processing order for columns corresponding to each row index is described on the right side of the row index. In at least one example embodiment ofFIG.15A, the column check node processing order for columns included in a row having a row index of 4 may be 26, 1, and 0 as a column index, and the column check node processing order for columns included in a row having a row index of 1 may be 2, 4, 5, 8, 9, . . . as a column index, but the example embodiments are not limited thereto.

Referring toFIG.15B, a processing order of variable node processing operations for decoding of an LDPC code having a coding rate of, for example, 22/36 by the decoding apparatus according to at least one example embodiment may be identified, but the example embodiments are not limited thereto, and for example, a different coding rate for the LDPC code may be used. In this case,FIG.15Billustrates a column variable node processing order for columns respectively corresponding to variable nodes that do not correspond to a puncturing area and/or a diagonal matrix area of a parity check matrix.

In this case, a row processing order of the variable node processing operations is described as a row index in the leftmost column of the table. In at least one example embodiment ofFIG.15B, the row processing order may be 4, 1, 5, 0, 6, 3, . . . as a row index, and this may be the same as the row processing order of the check node processing operations shown inFIG.15A.

In addition, a column variable node processing order for columns corresponding to each row index is described on the right side of the row index. In at least one example embodiment ofFIG.15B, because all columns included in a row having a row index of 4 correspond to the puncturing area or the diagonal matrix area of the parity check matrix, a column check node processing order may not be described. In addition, a column check node processing order for columns included in a row having a row index of 1 may be 3, 12, 16, 21, 22, . . . as a column index.

Referring toFIG.15C, a processing order of variable node processing operations for decoding of an LDPC code having a coding rate of, e.g., 22/36 by the decoding apparatus according to at least one example embodiment may be identified, but the example embodiments are not limited thereto, and for example, a different coding rate for the LDPC code may be used. In this case,FIG.15Cillustrates a column variable node processing order for columns respectively corresponding to variable nodes that correspond to the puncturing area and/or the diagonal matrix area of the parity check matrix.

In this case, a row processing order of the variable node processing operations is shown as a row index in the leftmost column of the table. In at least one example embodiment ofFIG.15C, the row processing order may be 4, 1, 5, 0, 6, 3, . . . as a row index, and this may be the same as the row processing order of the check node processing operations shown inFIGS.15A and15B, but the example embodiments are not limited thereto.

In addition, a column variable node processing order for columns corresponding to each row index is shown on the right side of the row index. In at least one example embodiment ofFIG.15C, the column check node processing order for the columns included in the row having a row index of 4 may be 0, 1, and 26 as a column index, but is not limited thereto. In addition, a column check node processing order for columns included in a row having a row index of 1 may be 0 as a column index, but is not limited thereto.

FIGS.16A to16Fare diagrams illustrating an example of a scheduling table used by the decoding apparatus, according to at least one example embodiment.

Referring toFIGS.16A to16F, a scheduling table generated according to and/or based on the processing order as shown inFIGS.15A to15Cmay be identified, but the example embodiments are not limited thereto.

In the leftmost column of the scheduling table, numbers of and/or corresponding to check node processing operations and variable node processing operations are shown. In this case, in the case of the variable node processing operations, a variable node processing operation for columns that do not correspond to a puncturing area and/or a diagonal matrix area are represented by VNP0, and a variable node processing operation for columns corresponding to the puncturing area and/or the diagonal matrix area is represented by VNP1. In this case, in the scheduling table ofFIGS.16A to16F, the check node processing operations and the variable node processing operations may sequentially start in a pipelined manner, similar to the scheduling table ofFIGS.14A to14D.

In some example embodiments ofFIGS.16A to16F, operation W3 of the variable node processing operation for the columns corresponding to the puncturing area and/or the diagonal matrix area may be omitted. This is because operation S830corresponding to operation W3 is an operation of storing a posterior probability value in a posterior probability value memory, and a second posterior probability value memory storing a second posterior probability value corresponding to the puncturing area and/or the diagonal matrix area is implemented through a flip-flop, which enables processing without using a clock (e.g., a clock signal, and therefore do not have to occur during a desired clock cycle).

Also, in at least one example embodiments ofFIGS.16A to16F, operation R1 for a column corresponding to the diagonal matrix area as indicated by shades inFIG.15Amay be omitted. In this regard, because operation S710corresponding to operation R1 is an operation of reading a posterior probability value from a posterior probability value memory, and an initial posterior probability value corresponding to the diagonal matrix area is stored in a diagonal matrix memory, operation R1 may be omitted.

In addition, according to some example embodiments ofFIGS.16A to16F, similar to some example embodiments ofFIG.14A, inFIG.16A, although a check node processing operation for a row having a row index of 4, the row being positioned and/or scheduled first in a row processing order, starts later than and/or after a check node processing operation for a row having a row index of 1, the row being positioned and/or scheduled later in the row processing order, the check node processing operation for the row having a row index of 4 may start before the check node processing operation for all columns included in the row having a row index of 1 have completed, and the check node processing operation for the row having a row index of 4 may be completed earlier.

InFIG.14A, operation W1 for a row having a row index of 4 starts from a column having a column index of 0 and is performed in a twelfth clock cycle. This time point may be the same time point as an execution time of operation R5 for a column having a column index of 1 in the row having a row index of 4. However, inFIG.16A, operation W1 for a row having a row index of 4 may be performed in a tenth clock cycle, which is one clock cycle earlier than an eleventh clock cycle in which operation R5 for the row having a row index of 4 ends. As described above, when a column index at which operation R1 is performed last and a column index at which operation W1 is performed first are the same for rows having the same row index, operations R5 and W1 may be scheduled to overlap two clock cycles. This is because the minimum value used in operation W2 is calculated excluding a column index value being calculated, and thus, the calculated minimum value excluding the column index value may be used.

As described above, according to at least one example embodiment, the decoding apparatus may decode an LDPC code by performing processing on a column included in a second row of the parity check matrix before processing on all columns included in a first row of the parity check matrix has completed. Accordingly, unlike the comparative embodiment shown inFIG.12C, a stall that may occur while the check node processing operation is performed on the row having a row index of 4 may be reduced and/or prevented.

Also, inFIGS.16A and16B, a check node processing operation for a row having a row index of 5, the row being positioned and/or scheduled earlier in the row processing order, may start later than and/or after a check node processing operation for a row having a row index of 0, the row being positioned (and/or scheduled) later in the row processing order. In addition, the check node processing operation for the row having a row index of 5 may start before the check node processing operation for all columns included in the row having a row index of 0 has completed, and therefore the check node processing operation for the row having a row index of 5 may be completed earlier.

Also, inFIGS.16B and16C, a check node processing operation for a row having a row index of 6, the row being positioned and/or scheduled earlier in the row processing order, may start later than a check node processing operation for a row having a row index of 3, the row being positioned and/or scheduled later in the row processing order. In addition, the check node processing operation for the row having a row index of 6 may start before the check node processing operation for all columns included in the row having a row index of 3 has completed, and the check node processing operation for the row having a row index of 6 may be completed earlier.

Also, inFIGS.16C and16D, a check node processing operation for a row having a row index of 7, the row being positioned and/or scheduled earlier in the row processing order, may start later than a check node processing operation for a row having a row index of 2, the row being positioned and/or scheduled later in the row processing order. In addition, the check node processing operation for the row having a row index of 7 may start before the check node processing operation for all columns included in the row having a row index of 2 has completed, and the check node processing operation for the row having a row index of 7 may be completed earlier.

Similarly, even inFIG.16F, in which repeated processing on rows having row indices of 1, 4, 0, and 5 are shown, it may be identified that processing is configured to be performed on a column included in a second row of the parity check matrix before processing on all columns included in a first row of the parity check matrix has been completed.

As described above, according to at least one example embodiment, the decoding apparatus may decode the LDPC code at a higher speed by removing and/or reducing a stall that may occur during and/or in the middle of decoding by using the processing order shown inFIGS.15A to16Fand the scheduling table indicating the processing order. Also, according to at least one example embodiment, the decoding apparatus may decode the LDPC code at a higher speed by reducing unnecessary usage of clock cycles by separately performing processing on variable nodes corresponding to the puncturing area and/or the diagonal matrix area and variable nodes that do not correspond to the puncturing area and/or the diagonal matrix area.

While various example embodiments of the inventive concepts have been particularly shown and described herein, it will be understood that various changes in form and details may be made to the example embodiments without departing from the spirit and scope of the following claims.