Apparatus and method for decoding polar codes

Abstract

The present disclosure relates to a method and an apparatus for decoding polar codes and the polar code decoding method according to an exemplary embodiment of the present disclosure is a polar code decoding method performed by a polar code decoding apparatus which includes receiving a code word vector generated by polar encoding; and decoding the code word vector based on a soft cancellation (SCAN) decoding method and a round-trip belief propagation (BP) decoding method, in the decoding, an inner code of the code word vector may be decoded by the round-trip belief propagation method and an outer code may be decoded by the SCAN decoding method.

Claims

1. A polar code decoding method by a polar code decoding apparatus, the polar code decoding method comprising: receiving a code word vector generated by polar encoding; and decoding the encoding vector based on a soft cancellation (SCAN) decoding method and a round-trip belief propagation (BP) decoding method, in the decoding, an inner code of the code word vector is decoded by the round-trip BP decoding method and an outer code is decoded by the SCAN decoding method, wherein the decoding includes: updating an input L message of the outer code with a channel LLR as an input value in accordance with a schedule of the round-trip BP, wherein the input L message is a LLR message propagated to leftmost mode of the outer code; updating an L message and a B message of the inner code in accordance with a schedule of the SCAN, wherein the L message is a LLR message propagated from left node to right node and the B message is a LLR message propagated from right node to left node; and updating an input B message of the outer code with an output LLR updated in accordance with the schedule of the SCAN as an input value in accordance with a schedule of the round-trip BP, wherein the input B message is a LLR message propagated to rightmost node of the inner code.

2. The polar code decoding method according to claim 1, wherein the polar code having a length N is defined as a concatenated code of a plurality of outer codes having a length N/S and one inner code having the length N, where S is 2.sup.a and a is a level of parallelism, which determines a number of the plurality of outer codes.

3. The polar code decoding method according to claim 1, further comprising: measuring a convergence rate of polar code decoding based on mutual information of each of the L message and the B message.

4. The polar code decoding method according to claim 3, wherein the measuring of a convergence rate includes: updating mutual information of the L message and the B message propagated to nodes connected to each node; determining that the decoding is converged when APP mutual information which is the mutual information between prior LLRs calculated in a code associated with a code word node is 1 in all nodes; and calculating a clock cycle taken to converge the decoding as the convergence rate.

5. The polar code decoding method according to claim 4, wherein the mutual information is updated in accordance with a decoding schedule of the polar code.

6. The polar code decoding method according to claim 4, wherein the convergence rate is calculated by multiplying the number of iterative decoding at the moment of convergence and the clock cycle for one decoding.

7. A polar code decoding apparatus, comprising: a receiving unit which receives a code word vector generated by polar encoding; and a decoding unit which decodes the code word vector based on a soft cancellation (SCAN) decoding method and a round-trip belief propagation (BP) decoding method to output a decoding data bit string, wherein the decoding unit decodes an inner code of the code word vector by the round-trip BP decoding method and decodes an outer code by the SCAN decoding method, wherein the decoding unit updates an input L message of the outer code with a channel LLR as an input value in accordance with a schedule of the round-trip BP, wherein the input L message is a LLR message propagated to leftmost node of the outer code, wherein the decoding unit updates an L message and a B message of the inner code in accordance with a schedule of the SCAN, wherein the L message is a LLR message propagated from left node to right node and the B message is a LLR message propagated from right node to left node, and wherein the decoding unit updates an input B message of the outer code with an output LLR updated in accordance with the schedule of the SCAN as an input value in accordance with the schedule of the round-trip BP, wherein the input B message is a LLR message propagated to rightmost node of the inner code.

8. The polar code decoding apparatus according to claim 7, further comprising: a latency measuring unit which measures a convergence rate of polar code decoding based on mutual information of the L message and the B message.

9. The polar code decoding apparatus according to claim 8, wherein the latency measuring unit updates the mutual information of each of the L message and the B message which are propagated to nodes connected to each node, determines that the decoding is converged when APP mutual information which is the mutual information between prior LLRs calculated in a code correlated with a code word node is 1 in all the nodes, and calculates a clock cycle taken to converge the decoding as the convergence rate.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The above and other aspects, features and other advantages of the present disclosure will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings, in which:

(2) FIG. 1 is a view for explaining an encoding/decoding system of polar codes according to an exemplary embodiment of the present disclosure;

(3) FIG. 2 is a block diagram for explaining a decoding apparatus of polar codes according to an exemplary embodiment of the present disclosure;

(4) FIG. 3 is a view illustrating a factor graph for explaining soft-output decoding according to an exemplary embodiment of the present disclosure;

(5) FIG. 4 is a view illustrating a protograph of the factor graph illustrated in FIG. 3;

(6) FIG. 5 is a view illustrating two different connection codes for a polar code whose length N is 8, according to an exemplary embodiment of the present disclosure;

(7) FIG. 6 is a view for explaining a decoding procedure of FIG. 5;

(8) FIG. 7 is a flowchart illustrating a decoding method of polar codes according to an exemplary embodiment of the present disclosure;

(9) FIG. 8 is a flowchart illustrating a decoding method of an encoding vector according to an exemplary embodiment of the present disclosure;

(10) FIG. 9 is a view illustrating a decoding algorithm of polar codes according to an exemplary embodiment of the present disclosure;

(11) FIG. 10 is a flowchart illustrating a method of measuring a convergence rate of decoding polar codes according to an exemplary embodiment of the present disclosure;

(12) FIG. 11 is a view illustrating an algorithm of measuring a convergence rate of decoding polar codes according to an exemplary embodiment of the present disclosure;

(13) FIG. 12 is a graph illustrating a result when a latency of decoding polar codes is measured by mutual information according to an exemplary embodiment of the present disclosure; and

(14) FIG. 13 is a graph illustrating how a latency, a storage complexity, and a computational complexity change when a level of parallelism is changed, according to an exemplary embodiment of the present disclosure.

DETAILED DESCRIPTION OF THE EMBODIMENT

(15) Hereinafter, exemplary embodiments of the present disclosure will be described more fully with reference to the accompanying drawings for those skilled in the art to easily implement the present disclosure. As those skilled in the art would realize, the described embodiments may be modified in various different ways, all without departing from the spirit or scope of the present disclosure.

(16) In order to clearly illustrate the present disclosure, parts not related to the description are omitted. Accordingly, the drawings and description are to be regarded as illustrative in nature and not restrictive. Like reference numerals designate like elements throughout the specification. Therefore, reference numerals which are used in previous drawings may be used for another drawing.

(17) The size and thickness of the components shown the drawings are optionally determined for better understanding and ease of description, and the present disclosure is not limited to the examples shown in the drawings. In the drawings, thicknesses of several layers and regions are enlarged for clear expressions.

(18) Hereinafter, a method and an apparatus for decoding polar codes according to an exemplary embodiment of the present disclosure will be described in more detail with reference to accompanying drawings.

(19) FIG. 1 is a view for explaining an encoding/decoding system of polar codes according to an exemplary embodiment of the present disclosure.

(20) Referring to FIG. 1, an encoding/decoding system of polar codes according to an exemplary embodiment of the present disclosure includes a polar code encoding apparatus 100, a polar code decoding apparatus 200, and a channel 300. In the polar code encoding/decoding system, some components among various components which are exemplarily illustrated in FIG. 1 may be omitted or other components may be added.

(21) The polar code encoding apparatus 100 encodes data using polar codes and converts a code word, and then transmits the code word through a channel. The polar code is a code which achieves a channel capacity using a channel polarization phenomenon generated when a plurality of channels is coupled and then appropriately separated.

(22) The polar code decoding apparatus 200 receives and demodulates a signal through the channel 300. The polar code decoding apparatus 200 decodes the received code word using the polar code.

(23) FIG. 2 is a block diagram for explaining a polar code decoding apparatus according to an exemplary embodiment of the present disclosure.

(24) Referring to FIG. 2, a polar code decoding apparatus 200 according to an exemplary embodiment of the present disclosure includes a receiving unit 210 and a decoding unit 220.

(25) The receiving unit 210 receives a communication signal including polar codes through a channel. The communication channel may correspond to a binary input discrete memoryless channel.

(26) The decoding unit 220 decodes an encoding vector based on a soft cancellation (SCAN) decoding method and a round-trip belief propagation (BP) decoding method to output a decoded data bit string. In this case, the decoding unit 220 decodes an inner code of the code word vector by the round-trip BP decoding method and decodes an outer code by the SCAN decoding method.

(27) As described above, the polar code decoding apparatus 200 performs the decoding based on the SCAN and the round-trip BP which are soft-output decoding of the polar codes and the soft-output decoding is performed based on a factor graph expression of the polar code.

(28) In the meantime, the polar code decoding apparatus 200 configured as described above may further include a latency measuring unit (not illustrated).

(29) The latency measuring unit updates mutual information of each of an L message and a B message which are propagated to nodes connected to each node and determines that the decoding is converged when APP mutual information I.sub.APP(j) which is mutual information between prior LLRs calculated in a code associated with a code word node is 1 in all the nodes and calculates a clock cycle required to completely converge the decoding as a latency.

(30) That is, the latency measuring unit updates mutual information of a message I.sub..sup.L(,) which is propagated from the left to the right and mutual information I.sub..sup.B(,) of a message which is propagated from the right to the left. In this case, the mutual information may be updated in accordance with the schedule of the decoding algorithm of the polar codes.

(31) Thereafter, the latency measuring unit may calculate APP mutual information which is mutual information between prior LLRs calculated in a code associated with a code word node. Thereafter, the latency measuring unit considers that the decoding is converged when the calculated APP mutual information is 1 in all the nodes. The latency measuring unit may calculate a clock cycle taken for the decoding to be completely converged by multiplying the number of iterative decoding at the moment that the iterative decoding is converged while performing the iterative decoding and a clock cycle for one decoding.

(32) In the meantime, according to the present disclosure, the polar code decoding apparatus 200 configured as described above may satisfy the requirements of various systems by adjusting a level of parallelism to be flexibly changed from the most sequential level to the most parallel level, and thus to adjust the latency, the storage complexity, and the computational complexity. That is, the polar code decoding apparatus 200 may flexibly adjust the latency and the complexity with a trade-off relationship.

(33) FIG. 3 is a view illustrating a factor graph for explaining soft-output decoding according to an exemplary embodiment of the present disclosure. FIG. 4 is a view illustrating a protograph of the factor graph illustrated in FIG. 3.

(34) The polar code is defined as a code length N (N is a natural number), the number K (K is a natural number) of information bits, and a bit index set [N] for an information bit. Further, the information data is expressed as u.sub.0.sup.N-1=(u.sub.0, . . . , u.sub.N-1), the code word is expressed as x.sub.0.sup.N-1=(x.sub.0, . . . , x.sub.N-1), and the received sequence is expressed as y.sub.0.sup.N-1=(y.sub.0, . . . , y.sub.N-1).

(35) During an encoding process to a polar code, K bits are selected from the data bit string U at a ratio corresponding to a channel capacity in accordance with the channel polarization phenomenon to input information and a fixed value is input to the remaining (N-K) frozen bits to be encoded. A code word, that is, the code bit string X is expressed by X=u.Math.G.sub.N. Here, G.sub.N is G.sub.N=B.sub.N.Math.F.sub.2.sup..Math.n, B.sub.N represents a bit reversal permutation matrix, and F.sub.2.sup.n represents a n-order Kronecker power of

(36) $F_2=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right].$
When i, a bit u.sub.i is an information bit, when i.Math., the bit u.sub.i is a frozen bit, and the frozen bit is set as 0.

(37) FIG. 3 illustrates a factor graph of a polar code having a code length N (=8) and a code rate of . A vector x and a vector u refer to a code word and an information message, respectively. Each node is defined by three variables of a layer , a group , and an order of nodes in the group. The layer is a vertical axis on a factor graph and the group is expressed by a dotted-line rectangle in the layer.

(38) In the factor graph, each node (, , ) has two associated logarithmic likelihood ratio (LLR) messages L.sub.(,) and B.sub.(,) which are propagated to the right and the left.

(39) The polar code decoding apparatus iteratively updates a plurality of messages in the factor graph. In this case, the plurality of messages is divided into an L message which is propagated from leftmost nodes to rightmost nodes and a B message which is propagated from the rightmost nodes to the leftmost nodes by switching the direction. The plurality of messages uses a logarithmic likelihood ratio (LLR) which is expressed by a specific probability of a transmission value of a node associated with the plurality of messages.

(40) FIG. 4 illustrates a relationship of an L message propagated to the right and a B message propagated to the left which are two LLR messages associated with nodes on a protograph. The LLR messages may be calculated as represented in the following Equation 1.
L.sub.(,)=L.sub.1(,2)[L.sub.1(,2+1)+B.sub.(,+1)]
L.sub.(+1,)=L.sub.1(,2+1)+[L.sub.1(,2)B.sub.(,)]
B.sub.(,2)=B.sub.(,)[B.sub.(+1 )+L.sub.1(,2+1)]
B.sub.(+1,2+1)=B.sub.(+1,)+[B.sub.(,)L.sub.1(,2)][Equation 1]

(41) Here, an operator is defined as represented in the following Equation 2.

(42) $\begin{array}{cc}\stackrel{}{=}2{\tanh }^{-1}\left[\tanh \left(\frac{}{2}\right)\tanh \left(\frac{}{2}\right)\right]& \left[\mathrm{Equation}2\right]\end{array}$

(43) In the meantime, since the polar code is recursively configured, the code may be considered as a concatenated code. Therefore, in the present disclosure, the polar code having a length N may be defined as a concatenated code of a plurality of outer codes having a length N/S and one inner code having a length N. Here, N=2.sup.n and S=2.sup.s and s may be a level of parallelism which determines the number of outer codes.

(44) FIG. 5 is a view illustrating two different connection codes for a polar code whose length N is 8, according to an exemplary embodiment of the present disclosure. FIG. 5A illustrates an inner code C.sub.0, a first outer code C1 and a second outer code C2 each having a length of 4 and FIG. 5B illustrates an inner code C.sub.0, a first outer code C.sub.1, a second outer code C.sub.2, a third outer code C.sub.3, and a fourth outer code C.sub.4 each having a length of 2. In the case of the polar code having a length of 8, two connection relationships are illustrated. Therefore, in the case of various polar codes whose length is 16 or 32, 2.sup.(n1) connection relationships may be illustrated.

(45) One inner code according to the present disclosure is subjected to round-trip BP decoding and the outer codes are subjected to SCAN decoding in parallel.

(46) Specifically, the polar code decoding apparatus performs the decoding through three steps. In a first step, the L message of the outer code is updated with the channel LLR as an input value in accordance with the schedule of the round-trip BP. In this case, the L message is updated in parallel in the unit of layer. In a second step, the L message and the B message are updated with the L message updated in the first step as an input value in accordance with the SCAN schedule. In a third step which is the final step, when the B message is updated in accordance with the schedule of the round-trip BP like the first step, the decoding is completed. In this case, the L message and the B message may be updated using Equation 1.

(47) Such a polar code decoding method will be described with reference to FIG. 6.

(48) FIG. 6 is a view for explaining a decoding procedure of FIG. 5. The number represented with a red color in FIG. 6 refers to a decoding order.

(49) First, FIG. 6A will be described.

(50) First, the polar code decoding apparatus updates the input L message of the outer code with the channel LLR as an input value in accordance with the schedule of the round-trip BP in an inner code C.sub.0 and simultaneously inputs the updated L message to the first outer code C.sub.1 and the second outer code C.sub.2.

(51) By doing this, the polar code decoding apparatus updates the L message and the B message with the updated L message as an input value in the first outer code C.sub.1 and the second outer code C.sub.2 in accordance with the SCAN schedule. In this case, the message in the first outer code C.sub.1 and the second outer code C.sub.2 may be updated in parallel. Therefore, the output messages of the first outer code C.sub.1 and the second outer code C.sub.2 are simultaneously input as an input message of the inner code C.sub.0.

(52) Therefore, the polar code decoding apparatus updates the B message in the inner code C.sub.0 in accordance with the schedule of the round-trip BP.

(53) FIG. 6B will be described.

(54) First, the polar code decoding apparatus updates the input L message of the outer code with the channel LLR as an input value in accordance with the schedule of the round-trip BP in an inner code C.sub.0 and simultaneously inputs the updated L message to the first outer code C.sub.1, the second outer code C.sub.2, the third outer code C.sub.3, and the fourth outer code C.sub.4.

(55) By doing this, the polar code decoding apparatus updates the L message and the B message with the updated L message as an input value in the first outer code C.sub.1, the second outer code C.sub.2, the third outer code C.sub.3, and the fourth outer code C.sub.4 in accordance with the SCAN schedule. In this case, the message of the first outer code C.sub.1, the second outer code C.sub.2, the third outer code C.sub.3, and the fourth outer code C.sub.4 may be updated in parallel. Therefore, the output messages of the first outer code C.sub.1, the second outer code C.sub.2, the third outer code C.sub.3, and the fourth outer code C.sub.4 may be simultaneously input to the inner code C.sub.0.

(56) Therefore, the polar code decoding apparatus updates the B message in accordance with the schedule of the round-trip BP based on the message input to the inner code C.sub.0.

(57) In the meantime, according to the present disclosure, the SCAN algorithm is a scheme in which s=0, which is serialized extreme and the round-trip BP algorithm is a scheme in which s=(n1), which is parallelized extreme. Therefore, the polar code decoding apparatus provides explicit scheduling of soft-output polar decoding including two extremes. Further, the polar code decoding apparatus may gradually change the update schedule from the most serial way to the most parallel way. In this case, s is controlled to determine a degree of parallelism of the decoding. Therefore, s may be referred to as a level of parallelism.

(58) The polar code decoding apparatus according to the present disclosure may be flexibly changed from the most serial way to the most parallel way by adjusting the level of parallelism to satisfy the requirements of various systems.

(59) FIG. 7 is a flowchart illustrating a decoding method of polar codes according to an exemplary embodiment of the present disclosure.

(60) Referring to FIG. 7, the polar code decoding apparatus receives a code word vector generated by the polar encoding in step S610. The code word vector may be generated by binary multiplication of a source vector of a length of 1N to be transmitted and a polar code generating matrix having a size of NN. The code word vector transmitted from a transmission side is received at a reception side to initialize the decoding of the polar code.

(61) When step S610 is performed, the polar code decoding apparatus decodes the encoding vector based on the SCAN decoding method and the round-trip BP decoding method in step S620. In this case, the polar code decoding apparatus decodes an inner code of the code word vector by the round-trip belief propagation method and decodes an outer code by the SCAN decoding method.

(62) By doing this, the polar code decoding apparatus outputs a polar decoding data bit string.

(63) A decoding method of the polar code decoding apparatus will be described in detail with reference to FIG. 8.

(64) FIG. 8 is a flowchart illustrating a decoding method of an encoding vector according to an exemplary embodiment of the present disclosure and FIG. 9 is a view illustrating a decoding algorithm of polar codes according to an exemplary embodiment of the present disclosure.

(65) Referring to FIG. 8, the polar code decoding apparatus updates an input L message of an outer code with a channel LLR as an input value in accordance with a schedule of a round-trip BP in step S710. Here, the channel LLR may refer to channel information that each variable node receives from a channel based on a signal received from the channel. The decoding apparatus may update the input L message of the outer code using Equation 1.

(66) When step S710 is performed, the polar code decoding apparatus updates the L message and the B message of the inner code in accordance with the schedule of SCAN in step S720. In this case, the polar code decoding apparatus simultaneously updates the messages of the outer codes.

(67) When step S720 is performed, the polar code decoding apparatus updates an input B message of an outer code with an output LLR of step S720 as an input value in accordance with a schedule of a round-trip BP in step S730.

(68) The polar code decoding algorithm described above is as illustrated in FIG. 9.

(69) In the meantime, in order to measure a convergence rate of the decoding algorithm according to the present disclosure, an extrinsic information transfer (EXIT) chart scheme is introduced. A protograph-based EXIT (PEXIT) analysis scheme among EXIT charts has been utilized for the LDPC code analysis. The present disclosure modifies the analysis scheme to apply the scheme to polar code.

(70) FIG. 10 is a flowchart illustrating a convergence rate of decoding polar codes according to an exemplary embodiment of the present disclosure and FIG. 11 is a view illustrating an algorithm of measuring a convergence rate of decoding polar codes according to an exemplary embodiment of the present disclosure.

(71) Referring to FIG. 10, the polar code decoding apparatus calculates channel mutual information which is mutual information for a channel based on a signal received through a channel in step S1010. That is, the polar code decoding apparatus calculates mutual information I.sub.ch for a reception signal received from the channel using the following Equation 3 as an initialization process.
I.sub.ch=J({square root over (8RE.sub.b/N.sub.0))}[Equation 3]

(72) Here, R is a code rate of a polar code and E.sub.b/N.sub.c is a signal to noise ratio (SNR) of the used channel. J(.sup.2.sub.ch) is a function for mutual information between a binary random variable with the same probability of 0 and 1 and a Gaussian random variable having a variance of .sup.2.sub.ch.

(73) J() may be defined as represented in the following Equation 4.

(74) $\begin{array}{cc}J\left(\right)=1-{}_{-}^{+}\frac{1}{\sqrt{2{}^2}}{e}^{-\frac{{\left(y-{}^2/2\right)}^2}{2{}^2}}{\log }_2\left(1+e^{-y}\right)dy& \left[\mathrm{Equation}4\right]\end{array}$

(75) When step S1010 is performed, the polar code decoding apparatus updates the mutual information of a message propagated to a node connected to each node based on the channel mutual information in step S1020. That is, the polar code decoding apparatus updates mutual information I.sub.+1.sup.L(,) of a message which is propagated from the left to the right and mutual information I.sub.+1.sup.B(,) of a message which is propagated from the right to the left. In this case, the mutual information may be updated in accordance with the schedule of a decoding algorithm of the polar codes.

(76) For example, as represented in the protograph of FIG. 4, each mutual information which forms a pair with each LLR message represented by (, , ) may be updated using the following Equation 5.

(77) $\begin{array}{cc}{I}_{}^L\left(,\right)=1-J(\sqrt{{J^{-1}\left(1-I_{-1}^L\left(,2\right)\right)}^2+{J^{-1}\left(1-J\left(\sqrt{J^{-1}(}\right)\right)}^2})I_{}^L\left(+1,\right)=J(\sqrt{{J^{-1}\left(I_{-1}^L\left(,2+1\right)\right)}^2+{J^{-1}\left(1-J\left(\sqrt{{J^{-1}\left(I_{-1}^L\left(,2\right)\right)}^2+{J^{-1}\left(\left(,\right)\right)}^2}\right)\right)}^2})I_{-1}^B\left(,2\right)=1-J(\sqrt{{J^{-1}\left(1-I_{}^B\left(,\right)\right)}^2+{J^{-1}\left(1-J\left(\sqrt{{J^{-1}\left(I_{-1}^B\left(,2+1\right)\right)}^2+{J^{-1}\left(I_{}^B\left(+1,\right)\right)}^2}\right)\right)}^2})I_{-1}^B\left(,2+1\right)=J(\sqrt{{J^{-1}\left(I_{}^B\left(+1,\right)\right)}^2+{J^{-1}\left(1-J\left(\sqrt{{J^{-1}\left(I_{}^B\left(,\right)\right)}^2+{J^{-1}\left(I_{-1}^L\left(,2\right)\right)}^2}\right)\right)}^2})& \left[\mathrm{Equation}5\right]\end{array}$

(78) The polar code decoding apparatus updates the mutual information in accordance with the same schedule, instead of the LLR message.

(79) When step S1020 is performed, the polar code decoding apparatus calculates APP mutual information which is mutual information between prior LLRs calculated in a code associated with a code word node in step S1030. Here, the APP mutual information is mutual information between posterior LLR which is evaluated by the variable node VN and an associated code word bit x.sub.j and the polar code decoding apparatus may calculate the APP mutual information I.sub.APP(j) using the following Equation 6.
I.sub.APP(j)=J({square root over (J.sup.1(I.sub.n.sup.L(0,k)).sup.2+J.sup.1(I.sub.n.sup.B(0,j)).sup.2))}[Equation 6]

(80) When step S1030 is performed, the polar code decoding apparatus determines whether the APP mutual information is 1 in all nodes in step S1040.

(81) As a determination result of step S1040, when all the mutual information is 1 in all nodes, the polar code decoding apparatus determines that the decoding is converged in step S1050 and calculates a latency (clock cycle) taken to converge the decoding in step S1060. That is, the polar code decoding apparatus may calculate a clock cycle taken to completely converge the decoding by multiplying the number of iterative decoding at the moment that the iterative decoding is converged while performing the iterative decoding and a clock cycle for one decoding.

(82) When it is assumed that a decoder for a polar code having a length of N has N processing units and each processing unit implements Equation 5 at a clock cycle , a SCAN decoder requires a clock cycle (2N3) to complete the message update.

(83) The clock cycle of the inner code may be twice the number of layers in the inner code and the clock cycle of the outer code may be the same as the SCAN decoding of the polar code having a length of N/S. Therefore, a clock cycle (latency) T.sub.s taken to completely converge the decoding may be calculated using Equation 7.

(84) $\begin{array}{cc}{T}_s=\left(2s+\frac{2N}{S}-3\right)l_s& \left[\mathrm{Equation}7\right]\end{array}$

(85) Here, I.sub.s is the number of iterations when the scheme with s is completed and may refer to a clock cycle to decode the polar code.

(86) An algorithm for measuring a convergence rate of the polar code decoding as described above may be as illustrated in FIG. 11.

(87) The polar code decoding apparatus measures the latency of the polar code decoding until the decoding is converged. Therefore, the latency is given as a multiplication of the number of iterations that the decoding is converged and a clock cycle required for one decoding. The channel environment may be an AWGN channel and a modulation method may be a BPSK method. A length of code is 32,768 (N=2.sup.15) bits, an SNR of the channel is 1.0 dB, and the code is built to be optimized at 2.0 dB.

(88) FIG. 12 is a graph illustrating a result when a latency of polar code decoding is measured by mutual information according to an exemplary embodiment of the present disclosure. It is assumed that process units as many as the code length are prepared and it takes t clocks for each unit to process the mutual information updating operation.

(89) Referring to FIG. 12, when the level of parallelism is 0, it is the SCAN which is the most sequential way and when the level of parallelism is 14, it is the BP which is the most parallel way. It is understood that when the decoding is performed in more parallel way, the latency is short. Further, it is confirmed that since all decoding is converged, there is no performance degradation.

(90) FIG. 13 is a graph illustrating how a latency, a storage complexity, and a computational complexity change when a level of parallelism is changed, according to an exemplary embodiment of the present disclosure.

(91) Referring to FIG. 13, it is understood that the higher the level of parallelism, the shorter the latency, but the higher the storage and computational complexities, which is inversely proportional thereto. Therefore, it is confirmed that the latency and the complexity form a trade-off relationship. Further, it is understood that a degree of lowering the latency is relatively smaller than a degree of increasing the complexity.

(92) However, the soft-output decoding is essential for a system such as a magnetic recording device in which a turbo-based receiver is utilized so that a method and an apparatus for decoding polar codes according to the present disclosure may be flexibly adaptable to system requirements.

(93) Further, in a desktop computer which utilizes a hard disk driver, a required latency and complexity vary depending on a working environment so that the method and the apparatus for decoding polar codes according to the present disclosure may also be applicable to such a system. For example, when a hard disk starts to read/write after an idle time, the system requires a low latency time even though the storage/computational complexities are increased. In contrast, when the system does not have free system resource due to other works, even though the latency is high, a low storage/computational complexity is required.

(94) Further, the method and the apparatus for decoding polar codes according to the present disclosure may be applied to a hard disk in the notebook computer when it is being charged or it is not charged.

(95) As described above, the method and the apparatus for decoding polar codes according to the present disclosure may be adaptable to various requirements of a system.

(96) The referenced drawings and described detailed description of the present disclosure are the exemplary embodiment of the present disclosure, which are used for the purpose of merely describing the present disclosure, not limiting the scope of the present disclosure which is included in the appended claims. Therefore, it will be appreciated to those skilled in the art that various modifications are made, and other equivalent embodiments are available. Accordingly, the actual scope of the present disclosure must be determined by the spirit of the appended claims.