METHOD AND APPARATUS FOR GENERATING A DECODING POSITION CONTROL SIGNAL FOR DECODING USING POLAR CODES

Abstract

Disclosed are a method and apparatus for generating a decoding position control signal for decoding using polar codes. The method and apparatus for generating a decoding position control signal for decoding using polar codes according to an embodiment of the present disclosure include generating a decoding tree obtained by forming a plurality of nodes in a hierarchical structure for a polar-encoded codeword, decoding the codeword using a successive cancellation (SC) decoding technique, and generating control signal through a preset operation relationship based on a position of a bit returned during re-decoding among the decoded codeword.

Claims

1. A method for generating a decoding position control signal for decoding using polar codes, the method comprising: generating a decoding tree obtained by forming a plurality of nodes in a hierarchical structure for a polar-encoded codeword; decoding the codeword using a successive cancellation (SC) decoding technique; and generating control signal through a preset operation relationship based on a position of a bit returned during re-decoding among the decoded codeword.

2. The method of claim 1, wherein in the decoding of the codeword, nodes of the lowest stage are sequentially decoded one by one by searching the nodes of the lowest stage from a node of the highest stage in the decoding tree in a depth-first search (DFS) method.

3. The method of claim 1, wherein in the generating of the control signal, the control signal is generated based on a first bit string indicating the position of the bit returned during the re-decoding, and a second bit string calculated through the preset operation relationship with the first bit string.

4. The method of claim 3, wherein the first bit string and the second bit string are expressed in a binary system having a log.sub.2N number of bit places (where N is a codeword length of the codeword).

5. The method of claim 4, wherein in the preset operation relationship, the second bit string is output by adding the first bit string and 2's complement of 1 using an adder, and performing an exclusive-OR operation of the first bit string and a result of the addition using an exclusive-OR (XOR) operator.

6. The method of claim 5, wherein the generating of the control signal further includes: generating clock cycle information required to decode the bit returned during the re-decoding through the number of is in all bit places in the second bit string; generating stage information in which an operation to be performed through a bit place value of the second bit string; and generating operation information performed through the stage information through a bit place value of the first bit string.

7. The method of claim 6, wherein in the generating of the stage information, it is checked whether or not the operation is to be performed in a j-th stage of the decoding tree through a j-th bit place of the second bit string, and when a j-th bit place value of the second bit string is 1, it is determined that the operation is to be performed in the j-th stage of the decoding tree (where j is from (log.sub.2N−1) to 0 in descending order from left).

8. The method of claim 7, wherein in the generating of the operation information, the operation to be performed in the j-th stage in which the operation is determined to be performed is checked through a j-th bit place of the first bit string, and if a bit place value of the first bit string is 0, the operation to be performed in the j-th stage is determined as an f operation, and if the j-th bit place value of the first bit string is 1, the operation to be performed in the j-th stage is determined as a g operation.

9. An apparatus for generating a decoding position control signal for decoding using polar codes, the apparatus comprising: a decoding tree generator configured to generate a decoding tree obtained by forming a plurality of nodes in a hierarchical structure for a polar-encoded codeword; a decoder configured to decode the codeword using a successive cancellation (SC) decoding technique; and a control signal generator configured to generate a control signal through a preset relationship based on a position of a bit returned during re-decoding among the decoded codeword.

10. The apparatus of claim 9, wherein the decoder is configured to sequentially decode nodes of the lowest stage one by one by searching the nodes of the lowest stage from a node of the highest stage in the decoding tree in a depth-first search (DFS) method.

11. The apparatus of claim 9, wherein the control signal generator is configured to generate the control signal based on a first bit string indicating the position of the bit returned during the re-decoding, and a second bit string calculated through the preset operation relationship with the first bit string.

12. The apparatus of claim 11, wherein the first bit string and the second bit string are expressed in a binary system having a log.sub.2N number of bit places (where N is a codeword length of the codeword).

13. The apparatus of claim 12, wherein in the preset operation relationship, the second bit string is output by adding the first bit string and 2's complement of 1 using an adder, and performing an exclusive-OR operation of the first bit string and a result of the addition using an exclusive-OR (XOR) operator.

14. The apparatus of claim 13, wherein is the control signal generator is configured to generate clock cycle information required to decode the bit returned during the re-decoding through the number of 1 s in bit places in the second bit string, generate stage information (=information of a stage) in which an operation to be performed through a bit place value of the second bit string, and generate operation information to be performed through the stage information through a bit place value of the first bit string.

15. The apparatus of claim 14, wherein the control signal generator is configured to check whether or not the operation is to be performed in a j-th stage of the decoding tree through a j-th bit place of the second bit string, and generate the stage information by determining that the operation is to be performed in the j-th stage of the decoding tree when a j-th bit place value of the second bit string is 1 (where j is from (log.sub.2N−1) to 0 in descending order from left).

16. The apparatus of claim 15, wherein the control signal generator is configured to check the operation to be performed in the j-th stage in which the operation is determined to be performed through a j-th bit place of the first bit string, and generate the stage information by determining that the operation to be performed in the j-th stage as an f operation if a bit place value of the first bit string is 0, and by determining that the operation to be performed in the j-th stage as a g operation if the j-th bit place value of the first bit string is 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0027] FIG. 1 is a block diagram illustrating an apparatus for generating a decoding position control signal according to an embodiment of the present disclosure.

[0028] FIG. 2 is a diagram illustrating a decoding tree generated by the apparatus for generating the decoding position control signal according to an embodiment of the present disclosure.

[0029] FIG. 3 is a diagram illustrating a process of generating a decoding position control signal based on a position of a bit in the apparatus for generating the decoding position control signal according to an embodiment of the present disclosure.

[0030] FIG. 4 is a flowchart illustrating a method of generating a decoding position control signal for decoding using polar codes according to an embodiment of the present disclosure.

[0031] FIG. 5 is a block diagram illustratively describing a computing environment including a computing device according to an embodiment.

DETAILED DESCRIPTION

[0032] Hereinafter, a specific embodiment of the present disclosure will be described with reference to the drawings. The following detailed description is provided to aid in a comprehensive understanding of the methods, apparatus and/or systems described herein. However, this is illustrative only, and the present disclosure is not limited thereto.

[0033] In describing the embodiments of the present disclosure, when it is determined that a detailed description of related known technologies may unnecessarily obscure the subject matter of the present disclosure, a detailed description thereof will be omitted. In addition, terms to be described later are terms defined in consideration of functions in the present disclosure, which may vary according to the intention or custom of users or operators. Therefore, the definition should be made based on the contents throughout this specification. The terms used in the detailed description are only for describing embodiments of the present disclosure, and should not be limiting. Unless explicitly used otherwise, expressions in the singular form include the meaning of the plural form. In this description, expressions such as “comprising” or “including” are intended to refer to certain features, numbers, steps, actions, elements, some or combination thereof, and it is not to be construed to exclude the presence or possibility of one or more other features, numbers, steps, actions, elements, some or combinations thereof, other than those described.

[0034] FIG. 1 is a block diagram illustrating an apparatus 100 for generating a decoding position control signal according to an embodiment of the present disclosure.

[0035] Meanwhile, in the present disclosure, a polar code encoding and decoding device used in a communication system can be described as an example. The polar code encoding device may encode data (information bits) to be transmitted using the polar code, and transmit the encoded data (codeword) to the polar code decoding device through a channel. Here, the polar code is a code that achieves channel capacity by using a channel polarization phenomenon that occurs when several channels are combined and then properly separated. In addition, the polar code decoding device may decode the codeword received from the polar code encoding device through the channel based on a successive cancellation (SC) decoding technique, and estimate and output the data encoded by the polar code encoding device. In this case, according to the SC decoding technique, the encoded data is sequentially decoded bit by bit, and in decoding a certain bit, the decoded bit result before decoding is performed on the bit can be used. SCL (SClist) decoding, SCS (SC-stack) decoding, and SCF (SC-flip) decoding used to improve performance also basically use a sequential decoding method.

[0036] Referring to FIG. 1, the apparatus 100 for generating the decoding position control signal according to an embodiment may include a decoding tree generator 110, a decoder 120, and a control signal generator 130.

[0037] In the illustrated embodiment, configurations may respectively have different functions and capabilities other than those described below, and additional configurations may be included in addition to those described below.

[0038] In addition, in the following embodiments, the decoding tree generator 110, the decoder 120, and the control signal generator 130 may be implemented using one or more physically separated devices, or implemented by one or more processors or a combination of one or more processors and software, and may not be clearly distinguished in a specific operation unlike the illustrated example.

[0039] The decoding tree generator 110 may receive a polar encoded codeword and a codeword length to generate a decoding tree that satisfies the received codeword and codeword length. That is, the decoding tree generator 110 may form a plurality of nodes in a hierarchical structure for the polar encoded codeword.

[0040] FIG. 2 is a diagram illustrating a decoding tree generated by the apparatus 100 for generating the decoding position control signal according to an embodiment of the present disclosure.

[0041] Referring to FIG. 2, a binary tree structure of the polar encoded codeword when the total code length of the codeword is 8 bits and the information bits are 4 bits may be identified. Here, the left branch may represent an f operation, the right branch may represent a g operation, S.sub.i may represent a stage of the decoding tree, .Math..sub.i may represent a decoded bit position, and the number indicated on a branch line may represent a clock cycle (CC) of a decoding schedule.

[0042] The decoding tree generator 110 may receive a codeword with a total codeword length N of 8 bits, of which 4 bits are information bits (.Math..sub.3, .Math..sub.5, .Math..sub.6, .Math..sub.7) and the remaining 4 bits are frozen bits) (.Math..sub.0, .Math..sub.1, .Math..sub.2, .Math..sub.4). In addition, the decoding tree generator 110 may generate a decoding tree that satisfies the received codeword as illustrated in FIG. 2.

[0043] The decoder 120 may decode the codeword using the SC decoding technique. That is, the decoder 120 may sequentially decode the entire received codeword bit by bit based on the SC decoding method.

[0044] Specifically, the decoder 120 may sequentially decode leaf nodes bit by bit by visiting or searching each leaf node (node of the lowest stage) from the root node (node of the highest stage) in the decoding tree in a depth-first search (DFS) method. Here, the highest stage may be log.sub.2N, and the decoding schedule (clock cycle) may be (2N−2). For example, in the process of visiting each leaf node in the DFS method, the decoder 120 may calculate a log-likelihood ratio (LLR) value when visiting the left node (left branch) of the tree by the f operation, and calculate the LLR value when visiting the right node (right branch) of the tree by the g operation. Here, the f operation and the g operation are equations defined for calculating the LLR value in the SC decoding technique, and may be expressed as in Equation 1 below. Meanwhile, since the f operation and the g operation in the polar code decoding algorithm are well-known techniques, a detailed description thereof will be omitted.

f=sign(LLR.sub.1)sign(LLR.sub.2)min(|LLR.sub.1|,|LLR.sub.2|)

g−LLR.sub.2+(−1).sup.uLLR  [Equation 1]

[0045] As described above, by using the LLR values of the nodes indicated by the parent node by the DFS method visit in the decoding tree, the LLR values of the nodes indicated by the child nodes may be calculated by the f operation or the g operation depending on the position of the node.

[0046] The control signal generator 130 may generate control signal through a preset operation relationship based on the position of the bit returned during re-decoding. Specifically, the control signal generator 130 may generate a decoding position control signal by using a first bit string and a second bit string. Here, the first bit string may indicate a position of a bit returned during re-decoding. In addition, the second bit string may be obtained by performing an operation using the first bit string, an adder, and an exclusive-OR (XOR) operator. In addition, the control signal may be information on a type of operation for each stage performed for decoding a corresponding bit and clock cycle used in the corresponding bit.

[0047] FIG. 3 is a diagram illustrating a process of generating a decoding position control signal based on a position of a bit in the apparatus 100 for generating the decoding position control signal according to an embodiment of the present disclosure.

[0048] Referring to FIG. 3, a first bit string X.sub.i indicating positions of bits based on a position of a bit returned during re-decoding, and a second bit string obtained by performing an operation using the first bit string X.sub.i, an adder, and an XOR operator may be identified. Here, the length of the bit string may be determined according to the codeword length N of the codeword. For example, when the codeword length of the codeword is 8, the bit string may be a bit string having a bit string length of 3 as in the example illustrated in FIG. 3.

[0049] The first bit string X.sub.i may represent the position of the bit returned during re-decoding among the bits of the codeword in a binary system. For example, when a codeword length N of a codeword expressed as a decimal number is N bits, the position of the bit returned during re-decoding may be expressed as a bit string having a length of log.sub.2N bits.

[0050] As a specific example, when the bit to be re-decoded is the first bit .Math..sub.0 decoded based on the SC decoding method, the position of the corresponding bit represented by the first bit string at this time may be expressed as 000.

[0051] As another example, when the bit to be re-decoded is the sixth decoded bit .Math..sub.5 based on the SC decoding method, the position of the corresponding bit represented by the first bit string at this time may be represented by 101.

[0052] The second bit string Y.sub.i may be obtained by performing an operation using the first bit string X.sub.i, an adder, and an XOR operator. That is, the second bit string Y.sub.i may be output by adding the first bit string and 2's complement of 1 by using the adder and performing an exclusive OR operation of the first bit string and the result obtained by performing addition of the first bit string and 2's complement of 1 using the XOR operator. For example, Y.sub.i may be obtained by calculating (X.sub.i−1) from X.sub.i using an adder and by performing an XOR operation of X.sub.i and (X.sub.i−1).

[0053] As a specific example, when the bit to be re-decoded is the first bit .Math..sub.0 decoded based on the SC decoding method, X.sub.i is 000 and (X.sub.i−1) is 111 using 2's complement of 1 (111, which is 2's complement 001, is added to X.sub.i), and the second bit string Y.sub.i obtained by performing an XOR operation of X.sub.i and (X.sub.i−1) may be expressed as 111.

[0054] As another example, when the bit to be re-decoded is the sixth bit .Math..sub.5 decoded based on the SC decoding method, X.sub.i is 100 and (X.sub.i−1) is 100 using 2's complement of 1 (111, which is 2's complement of 001, is added to X.sub.i), and the second bit string Yi obtained by performing an XOR operation of X.sub.i and (X.sub.i−1) may be expressed as 001.

[0055] The decoding position control signal may be generated using the first bit string and the second bit string. For example, clock cycle information required for decoding the bits to be re-decoded are generated through the number of 1s in all bit places in the second bit string, stage information S.sub.i on which an operation is to be performed may be generated through a bit place value of the second bit string, and operation information (f operation or g operation) to be performed may be generated from the corresponding stage information, through a bit place value of the first bit string. The apparatus 100 for generating the decoding position control signal may check whether an operation is to be performed in a j-th stage of the decoding tree through a j-the bit place of the second bit string through the stage information. When a j-th bit place value of the second bit string is 1, the apparatus 100 for generating the decoding position control signal may determine that the operation is to be performed in the j-th stage of the decoding tree. In addition, the apparatus 100 for generating the decoding position control signal may check the operation to be performed in the j-th stage, in which it is determined that the operation is to be performed through the j-th bit place of the first bit string, through the operation information. The decoding position control signal generating apparatus 100 may determine that the operation to be performed in the j-th stage is the f operation when a j-th bit place value of the first bit string is 0, and determine that the operation to be performed in the j-th stage is the g operation when the j-th bit place value of the first bit string is 1. Here, j may be expressed as (log.sub.2N−1) to 0 in descending order from the left.

[0056] As a specific example, when X.sub.i is 000 and Y.sub.i is 111, since the number of 1s in all bit places in Y.sub.i is 3, it may be determined that a total of 3 clock cycles is required. In addition, since all of the bit place values of Y.sub.i are 1, it may be determined that the operation is to be performed in the stages S.sub.2, S.sub.1, and S.sub.0 corresponding to respective bit place values. In addition, since the bit place values of X.sub.i corresponding to the stage S.sub.2, S.sub.1, and S.sub.0 where the operation is to be performed are 0, respectively, it may be determined that the operation f is to be performed in each of the the stages S.sub.2, S.sub.1, and S.sub.0.

[0057] As another example, when X.sub.i is 101 and Y.sub.i is 001, since the number of is in all bit places in Y.sub.i is 1, it may be determined that a total of 1 clock cycle is required. In addition, since the bit place value of Y.sub.i is 1 only in the 0-th bit place, it may be determined that the operation is to be performed only in the stage S.sub.0 corresponding to the corresponding bit place value. In addition, since the bit place value of X.sub.i corresponding to the stage S.sub.0 in which the operation is to be performed is 1, it may be determined that the g operation is to be performed in the stage S.sub.0.

[0058] The conventional control signal generator needs to consider three states for each stage of an initial state in which operations at all previous lower stages have been completed and the f operation is required, a state in which the f operation is completed and the g operation is required, and a state in which the g operation is completed and a lower stage operation is required, and requires a control signal state memory (2 bits per stage) for storing the three states for each stage and an initialization logic.

[0059] In contrast, the control signal generator 130 according to an embodiment may exhibits an effect of reducing an amount of additional memory required in the decoding process by using an adder and an exclusive-OR (XOR) operator based on the binary representation of the bit position.

[0060] FIG. 4 is a flowchart illustrating a method of generating a decoding position control signal for decoding using polar codes according to an embodiment of the present disclosure. The method illustrated in FIG. 4 may be performed by the apparatus 100 for generating the decoding position control signal illustrated in FIG. 1.

[0061] In the illustrated flowchart, although the method has been described by dividing the method into a plurality of steps, at least some steps may be performed in a different order, performed together in combination with other steps, omitted, performed by dividing the steps into sub-steps, or performed by being added with one or more steps (not illustrated).

[0062] Referring to FIG. 4, the apparatus 100 for generating the decoding position control signal receives a polar encoded codeword and a length of the codeword to generate a decoding tree that satisfies the received codeword and codeword length (S410).

[0063] After that, the apparatus 100 for generating the decoding position control signal decodes the codeword using the SC decoding technique (S420).

[0064] After that, the apparatus 100 for generating the decoding position control signal generates a control signal through a preset operation relationship based on the position of the bit returned during re-decoding (S430).

[0065] FIG. 5 is a block diagram illustratively describing a computing environment 10 including a computing device 12 according to an embodiment.

[0066] In the illustrated embodiment, respective components may have different functions and capabilities other than those described below, and may include additional components in addition to those described below.

[0067] The illustrated computing environment 10 includes the computing device 12. In an embodiment, the computing device 12 may be one or more components included in the apparatus 100 for generating the decoding position control signal.

[0068] The computing device 12 includes at least one processor 14, a computer-readable storage medium 16, and a communication bus 18. The processor 14 may cause the computing device 12 to operate according to the exemplary embodiment described above. For example, the processor 14 may execute one or more programs stored on the computer-readable storage medium 16. The one or more programs may include one or more computer-executable instructions, which, when executed by the processor 14, may be configured so that the computing device 12 performs operations according to the exemplary embodiment.

[0069] The computer-readable storage medium 16 is configured so that the computer-executable instruction or program code, program data, and/or other suitable forms of information are stored. A program 20 stored in the computer-readable storage medium 16 includes a set of instructions executable by the processor 14. In one embodiment, the computer-readable storage medium 16 may be a memory (volatile memory such as a random access memory, non-volatile memory, or any suitable combination thereof), one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, other types of storage media that are accessible by the computing device 12 and capable of storing desired information, or any suitable combination thereof.

[0070] The communication bus 18 interconnects various other components of the computing device 12, including the processor 14 and the computer-readable storage medium 16.

[0071] The computing device 12 may also include one or more input/output interfaces 22 that provide an interface for one or more input/output devices 24, and one or more network communication interfaces 26. The input/output interface 22 and the network communication interface 26 are connected to the communication bus 18. The input/output device 24 may be connected to other components of the computing device 12 through the input/output interface 22. The exemplary input/output device 24 may include a pointing device (such as a mouse or trackpad), a keyboard, a touch input device (such as a touch pad or touch screen), a speech or sound input device, input devices such as various types of sensor devices and/or photographing devices, and/or output devices such as a display device, a printer, a speaker, and/or a network card. The exemplary input/output device 24 may be included inside the computing device 12 as a component constituting the computing device 12, or may be connected to the computing device 12 as a separate device distinct from the computing device 12.

[0072] Although representative embodiments of the present disclosure have been described in detail, a person skilled in the art to which the present disclosure pertains will understand that various modifications may be made thereto within the limits that do not depart from the scope of the present disclosure. Therefore, the scope of rights of the present disclosure should not be limited to the described embodiments, but should be defined not only by claims set forth below but also by equivalents to the claims.