Polar code generating method, and electronic device and non-transitory computer-readable storage medium therefor

The disclosure relates to a polar code generating method, and an electronic device and a non-transitory computer-readable storage medium using the same.

Polar code is an advanced error correcting code. The coding scheme of polar code mainly uses a polar matrix to polarize input bit channels into relatively reliable bit channels and relatively unreliable bit channels. The reliable bit channels are used to transfer information bits, while the unreliable bit channels are used to transfer frozen bits. If a polar code has a sufficiently long code length (chunk size), information bits are guaranteed to be transmitted perfectly. In other words, the error rate tends to 0 as code length increases.

Currently, the code length of polar code is often restricted to the power of 2, resulting in an increase in system complexity. In addition, the reliability of input bit channels is highly influenced by the states of output channels of the polar transformation. Once the output channel changes, even with the same polarization matrix, the ranking of the reliability of the input bit channels will change. Once the unreliable bit channel is misused to transmit information bits, the performance of error correction is reduced.

The disclosure relates to a polar code generating method, and an electronic device and a non-transitory computer-readable storage medium using the same. According to the embodiments of the present disclosure, the processor may establish a plurality of polarization matrices and perform repolarization on specific input bit channel(s) of the polarization matrices to improve the channel reliability. Further, the code length of the present disclosure is not restricted to the power of 2 due to the re-polarization processing, thereby reducing the complexity of system design.

According to an embodiment, a polar code generating method is provided. The polar code generating method can be executed by an electronic device including a processor, and includes the following steps. A plurality of polarization matrices that receive a plurality of first input bits via a plurality of first input channels are established. The polarization matrices perform a first polar coding scheme on the first input bits and provide a plurality of first output bits on a plurality of first output channels. At least one to-be-enhanced input channel is selected from the first input channels of the polarization matrices. A re-polarization matrix that receives a plurality of second input bits via a plurality of second input channels is provided. The re-polarization matrix performs a second polar coding scheme on the second input bits and provides a plurality of second output bits on a plurality of second output channels, wherein a part of the second output bits is used as the first output bit(s) on the at least one to-be-enhanced input channel. A polar code that includes the first output bits and a remaining part of the second output bits is provided.

According to an embodiment, a non-transitory computer-readable storage medium is provided. The non-transitory computer-readable storage medium stores one or more instructions executable by a processor to cause an electronic device including the processor perform the following steps. A plurality of polarization matrices that receive a plurality of first input bits via a plurality of first input channels are established. The polarization matrices perform a first polar coding scheme on the first input bits and provide a plurality of first output bits on a plurality of first output channels. At least one to-be-enhanced input channel is selected from the first input channels of the polarization matrices. A re-polarization matrix that receives a plurality of second input bits via a plurality of second input channels is provided. The re-polarization matrix performs a second polar coding scheme on the second input bits and provides a plurality of second output bits on a plurality of second output channels, wherein a part of the second output bits is used as the first output bit(s) on the at least one to-be-enhanced input channel. A polar code that includes the first output bits and a remaining part of the second output bits is provided.

According to an embodiment, an electronic device including a memory and a processor is provided. The memory stores at least one instruction. The processor is coupled to the memory and executes the at least one instruction to implement the following steps. A plurality of polarization matrices that receive a plurality of first input bits via a plurality of first input channels are established. The polarization matrices perform a first polar coding scheme on the first input bits and provide a plurality of first output bits on a plurality of first output channels. At least one to-be-enhanced input channel is selected from the first input channels of the polarization matrices. A re-polarization matrix that receives a plurality of second input bits via a plurality of second input channels is provided. The re-polarization matrix performs a second polar coding scheme on the second input bits and provides a plurality of second output bits on a plurality of second output channels, wherein a part of the second output bits is used as the first output bit(s) on the at least one to-be-enhanced input channel. A polar code that includes the first output bits and a remaining part of the second output bits is provided.

For a better understanding of the above and other aspects of the present disclosure, embodiments are described below in detail with reference to the accompanying drawings:

FIG. 1A is a schematic diagram of polarization transformation.

FIG. 1B is a schematic diagram of an arithmetic unit in the polarization matrix.

FIG. 2 is a flow chart of a polar code generating method according to an embodiment of the present disclosure.

FIG. 3 is a schematic diagram of polarization transformation according to an embodiment of the present disclosure.

FIG. 4 is a schematic diagram of polarization transformation according to an embodiment of the present disclosure.

FIG. 5 illustrates channel error rate simulations according to an embodiment of the present disclosure.

FIG. 6 is a schematic diagram of polarization transformation according to an embodiment of the present disclosure.

FIG. 7 is a schematic diagram of polarization transformation according to another embodiment of the present disclosure.

FIG. 8A illustrates a polar code structure according to an embodiment of the present disclosure.

FIG. 8B illustrates the polarization transformation according to the embodiment of FIG. 8A .

In the following detailed description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the disclosed embodiments. It will be apparent, however, that one or more embodiments may be practiced without these specific details. In other instances, well-known structures and devices are schematically shown in order to simplify the drawing.

The disclosure provides a polar code generating method, and an electronic device and a non-transitory computer-readable storage medium using the same. The polar code generating method of the present disclosure is executable by an electronic device. For example, the electronic device includes a memory and a processor. The memory stores at least one instruction. The processor is coupled to the memory and may execute the at least one instruction to implement the polar code generating method of the present disclosure. The processor may be, for example, implemented as a microcontroller, a microprocessor, a digital signal processor, an application specific integrated circuit (ASIC), a digital logic circuit, a field programmable gate array (FPGA), or any other hardware element having processing functions. The polar code generating method of the present disclosure may also be implemented as a software program including one or more instructions. The software program may be stored in a non-transitory computer-readable storage medium, such as a hard disk, a compact disc, a flash drive, and a memory. When the processor loads the software program from the non-transitory computer-readable storage medium, the disclosed polar code generating method may be executed.

FIG. 1A is a schematic diagram of polarization transformation. As shown in FIG. 1A , a set of input bits U 1 to U 8 passes through the polarization matrix GM from the left to the right to form a set of output bits X 1 to X 8 . The input bits X 1 to X 8 may be written into a set of output channels W 1 to W 8 as a polar code. In an application of storage devices, each output channel W 1 to W 8 may be regarded as a memory cell. The output values of the output channels W 1 to W 8 are Y 1 to Y 8 .

The polarization matrix GM includes a plurality of arithmetic units 102 . In the example of FIG. 1A , the polarization matrix GM is formed by three stages of arithmetic units 102 connected in series. With the polarization matrix GM, the input bit channels that receive the input bits U 1 to U 8 are polarized into reliable input bit channel(s) and unreliable input bit channel(s). With the polarization matrix GM of FIG. 1A , if the output channels W 1 to W 8 are identical independent distributed (i.i.d.), the input channels that receive the input bits U 4 , U 6 , U 7 and U 8 will be polarized into more reliable channels than the input bit channels that receive the input bits U 1 , U 2 , U 3 , and U 5 .

FIG. 1B is a schematic diagram of an arithmetic unit 102 in the polarization matrix GM. The arithmetic unit 102 may be, for example, an XOR logic gate. With the XOR logic gate, the reliability of the input channel that transmits the input bit U i+1 will be enhanced, while the reliability of the input channel that transmits the input bit U i will be weakened. In other words, the input channel that carries the input bit U i+1 will be polarized into a relatively reliable channel compared to the input channel that carries the input bit U i . In the above manner, a polarization matrix that provides arbitrary reliability ranking can be implemented.

FIG. 2 is a flow chart of a polar code generating method according to an embodiment of the present disclosure. In step S 202 , the processor establishes a plurality of polarization matrices. The polarization matrices receive a plurality of first input bits via a plurality of first input channels and perform a first polarization scheme on the first input bits to provide a plurality of first output bits on a plurality of first output channels.

The first polarization scheme may refer to, for example, polarization transformations performed on the first input bits through the respective polarization matrices. The design of each polarization matrix may be arbitrary, and can be implemented with any known polar code construction technique.

In step S 204 , the processor selects at least one to-be-enhanced input channel from the first input channels of the polarization matrixes. The selected to-be-enhanced input channel(s) will be further re-polarized to improve the channel reliability.

In step S 206 , the processor provides a re-polarization matrix. The re-polarization matrix may receive a plurality of second input bits via a plurality of second input channels and performs a second polarization scheme on the second input bits to provide a plurality of second output bits on a plurality of second output channels. A part of the second output bits may be used as the first output bit(s) provided on the to-be-enhanced input channel(s).

The second polarization scheme refers to a polarization transformation performed on the second input bits through the re-polarization matrix. The design of the re-polarization matrix may be arbitrary and can be implemented with any known polar code construction technique. A part of the second input channels of the re-polarization matrix may be configured to receive raw data bits corresponding to the to-be-enhanced input channels. The re-polarization matrix may be designed to enhance the reliability of the second input channels receiving the raw data bits. On the other hand, the remaining second input channels which are weakened by the re-polarization matrix may be used to transfer frozen bits.

In step S 208 , the processor provides a polar code, wherein the polar code includes the first output bits and the remaining part of the second output bits that is not used as the first input bit(s). Because the number of bits of the remaining part of the second output bits may be arbitrary, the code length of the polar code is not limited to the power of 2.

FIG. 3 is a schematic diagram of polarization transformation according to an embodiment of the present disclosure. In FIG. 3 , the polarization transformation is implemented by k polarization matrices GM 1 to GM k and a re-polarization matrix RGM, where k is a positive integer. The polarization matrices GM 1 , GM 2 , . . . , GM k respectively have N 1 , N 2 , . . . , N k first input channels (shown on the left side of the polarization matrices GM 1 to GM k ) and N 1 , N 2 , . . . , N k first output channels (shown on the right side of the polarization matrices GM 1 to GM k ), where N 1 to N k are positive integers. Among N 1 first input channel(s) of the polarization matrix GM 1 , q, first output channels are selected as the to-be-enhanced input channels and are provided to the re-polarization matrix RGM for re-polarization, while the remaining N 1 −q 1 first input channels directly receive the raw data bits as the first input bits. Likewise, among the N 2 first input channel(s) of the polarization matrix GM 2 , q 2 first output channels are selected as the to-be-enhanced input channels and are provided to the re-polarization matrix RGM for re-polarization, while the remaining N 2 -q 2 first input channels directly receive the corresponding raw data bits as the first input bits; similarly, among the N k first input channel(s) of the polarization matrix GM k , the q k first output channels are selected as the to-be-enhanced input channels and are provided to the re-polarization matrix RGM for re-polarization, while the remaining N k -q k first input channels directly receive the raw data bits as the first input bits, where q 1 to q k are non-negative integers.

The re-polarization matrix RGM has q r second input channels (shown on the left side of the re-polarization matrix RGM) and q r second output channels (shown on the right side of the re-polarization matrix RGM), where q r =q+(q 1 +q 2 + . . . +q k ). Among the second output bits provided by the re-polarization matrix RGM, a part of the second output bits is provided to the q 1 to-be-enhanced channels of the polarization matrix GM 1 , a part of the second output bits is provided to the q 2 to-be-enhanced channels of the polarization matrix GM 2 , . . . , and a part of the second output bits is provided to the q k to-be-enhanced channels of the polarization matrix GM k . The number of bits of the remaining part of the second output bits is q=q r −(q 1 +q 2 + . . . +q k ). In an embodiment, the number of bits of the remaining part of the second output bits (q) is the same as the number of channels of the to-be-enhanced input channels (q 1 +q 2 + . . . +q k ). At this time, q r =2q, but it is noted that the present disclosure is not limited thereto.

In FIG. 3 , the polar code generated from the polarization transformation consists of N 1 +N 2 + . . . +N k first output bits and q second output bits. The q second output bits can be deemed as extra bits generated due to the re-polarization processing.

For better comprehension, the relevant details are described in conjunction with FIG. 4 and FIG. 5 .

FIG. 4 is a schematic diagram of polarization transformation according to an embodiment of the present disclosure. In FIG. 4 , the polarization transformation is realized by two polarization matrices GM 1 and GM 2 and one re-polarization matrix RGM. The polarization matrix GM, may convert the first input bits U 3 ′ to U 6 ′ into the corresponding first output bits X 3 to X 6 . The polarization matrix GM 2 may convert the first input bits U 7 ′ to U 10 ′ into the corresponding first output bits X 7 to X 10 .

In the example of FIG. 4 , the first input channels that transmit the first input bits U 5 and U 8 are selected as the to-be-enhanced input channels, while the other first output channels transmit the raw data bits. Therefore, except for the first input bits U 5 and U 8 , the other first input bits U 3 , U 4 , U 6 , U 7 , U 9 and U 10 are raw data bits V 3 , V 4 , V 6 , V 7 and V 9 and V 10 that has not been processed by the re-polarization matrix RGM.

The two raw date bits V 5 and V 8 corresponding to the first input bits U 5 and U 8 and other two raw data bits V 1 and V 2 are taken as the second input bits provided to the second input channels of the re-polarization matrix RGM. In this embodiment, the re-polarization matrix RGM is implemented by two stages of XOR logic gates, but it should be noted that the disclosure is not limited thereto. The number of stages of the logic gates of the re-polarization matrix RGM may be arbitrary.

The re-polarization matrix RGM has four second output channels, two of which are responsible for providing the first input bits U 5 and U 8 to the polarization matrices GM 1 and GM 2 , respectively, while the remaining two second output channels are responsible for providing the second output bits X 1 and X 2 which are used a part of the outputted polar code.

Through the re-polarization matrix RGM, the second input channels that transmit the raw data bits V 5 and V 8 are re-polarized into relatively reliable channels, so that the reliability of the first input channels of the polarization matrices GM 1 and GM 2 that transmit the first input bits U 5 and U 8 may be enhanced, and the code length of the polar code may only be increased by two bits (i.e., the two second output bits X 1 ′ and X 2 ′ in this example).

FIG. 5 illustrates channel error rate simulations according to an embodiment of the present disclosure. In the first stage 502 , the polarization transformation has not been performed, so the simulated error rates for the eight first input channels with channel indexes 1 to 8 are the same. In the second stage 504 , the simulated error rates for the eight first input channels are polarized into different values through a plurality of polarization matrices. Compared with the first channels with channel indexes 1 to 3, the first input channels with channel indexes 4 to 8 are relatively reliable, because they have a lower error rate. In the third stage 506 , the first input channels with channel indexes 4 and 5 are selected as the to-be-enhanced input channels for re-polarization, so their error rates are significantly reduced.

According to the disclosed embodiments, different polarization matrices may be configured for different storage units as output channels to provide adaptive polarization transformations. For better comprehension, the relevant details are described in conjunction with FIGS. 6, 7, 8A and 8B .

FIG. 6 is a schematic diagram of polarization transformation according to an embodiment of the present disclosure. Generally, the channel characteristic of a storage unit for storing MLC high bit information may be different from that for storing MLC low bit information. Applying a single polarization matrix to all the storage units with different channel characteristics may reduce the overall error correcting performance. Therefore, according to the embodiment of FIG. 6 , different polarization matrices are set for different MLC logical pages (e.g., high bit data and low bit data). The high bit may refer to, for example, one of the two bits stored in the MLC, and the low bit may refer to the other one of the two bits stored in the MLC. For example, for the 2-bit data “10” stored in the MLC, the high bit may refer to bit “1” (or bit “0” in another example), and the low bit may refer to bit “0” (or bit “1” in another example).

As shown in FIG. 6 , the polarization transformation is realized by two polarization matrices GM H and GM L and one re-polarization matrix RGM A . The polarization matrix GM H provides a first group of output bits including N H first output bits representing the MLC high bit data. The polarization matrix GM L provides a second group of output bits including N L first output bits representing the MLC low bit data. The re-polarization matrix RGM A is implemented by two stages of XOR logic gates. In another embodiment, the number of stages of the logic gates of the re-polarization matrix RGM A may be arbitrary.

The polarization matrix GM H and the polarization matrix GM L respectively have q H and q L first input channels selected as the to-be-enhanced input channels. The reliability of the to-be-enhanced input channels may be improved through the re-polarization matrix RGM A , wherein the re-polarization matrix RGM A includes q rA second input channels, and the number of extra bits in the polar code generated due to the re-polarization matrix RGM A is q A =q rA −(q H +q L ). In an embodiment, q rA =2q A .

FIG. 7 is a schematic diagram of polarization transformation according to another embodiment of the present disclosure. According to the embodiment of FIG. 7 , different polarization matrices are set for different triple-level cell (TLC) logical pages (e.g., high bit data, middle bit data and low bit data). The high bit, middle bit, and low bit may respectively represent the three bits in the 3-bit data stored by TLC.

As shown in FIG. 7 , the polarization transformation is realized by three polarization matrices GM H , GM M and GM L and one re-polarization matrix RGM B . The polarization matrix GM H provides a first group of output bits including N H first output bits representing the TLC high bit data. The polarization matrix GM M provides a second group of output bits including N M first output bits representing the TLC middle bit data. The polarization matrix GM L provides a third group of output bits including N L first output bits representing the TLC low bit data. The re-polarization matrix RGM B is implemented by three stages of XOR logic gates in this example. In another embodiment, the number of stages of the logic gates of the re-polarization matrix RGM B may be arbitrary.

The polarization matrices GM H , GM M and GM L respectively have q H , q M and q L first input channels selected as the to-be-enhanced input channels. The reliability of the to-be-enhanced input channels may be improved through the re-polarization matrix RGM B , wherein the re-polarization matrix RGM B includes q rB second input channels, and the number of extra bits in the polar code generated due to the re-polarization matrix RGM B is q B =q rB −(q H +q M +q L ). In an embodiment, q rB =2q B .

Next, please refer to FIG. 8A and FIG. 8B . FIG. 8A illustrates a polar code structure according to an embodiment of the present disclosure. FIG. 8B illustrates the polarization transformation according to the embodiment of FIG. 8A .

According to the embodiment, the high bit data and the low bit data in the polar code respectively include

N A + N B + q C 2

bits. The polarization matrices GM H1 and GM H2 respectively provide N B and N A first output bits for the high bit data of the polar code. The polarization matrices GM L1 and GM L2 respectively provide N B and N A first output bits for the low bit data of the polar code, where N A is not equal to N B . That is, the polarization matrices GM H1 and GM H2 (or GM L1 and GM L2 ) respectively provide two groups of output bits with different numbers of bits, wherein one group of output bits includes N B first output bits, and the other group of output bits includes N A first output bits.

In addition, the polarization matrices GM H1 , GM H2 , GM L1 , and GM L2 have respectively q H1 , q H2 , q L1 , and q L2 first output channels selected as to-be-enhanced input channels. The reliability of the to-be-enhanced input channels are enhanced through the re-polarization matrices RGM C , wherein the re-polarization matrix RGM C includes q rC second input channels, and the number of extra bits in the polar code generated due to the re-polarization matrix RGM C is q C =q rC −(q H1 +q H2 +q L1 +q L2 ). In an embodiment, q rC =2q C .

In the above manner, a

( 2 × ( N A + N B + q C 2 ) ,

K) polar code is realized, in which

2 × ( N A + N B + q C 2 )

represents the code length of the polar code and K represents the number of information bits in the polar code. For example, N A =4096, N B =512, q C =24, and K=8192.

It is noted that in the above various embodiments, the connection between the re-polarization matrix and the polarization matrices is not restricted to: the first half channels is responsible for transmitting the extra bits (e.g., the two sets of q C /2 channels in FIG. 8B ) and the second half channels consist of the to-be-enhanced input channels (e.g., the q H1 , q H2 , q L1 and q L2 channels of the polarization matrices in FIG. 8B ). In some embodiments, the arrangement of the connection between the re-polarization matrix and the polarization matrices may not be so regular when the length of re-polarization is large.

In summary, the disclosure provides a polar code generating method, and an electronic device and a non-transitory computer-readable storage medium using the same. According to the embodiments of the present disclosure, the processor may establish a plurality of polarization matrices and perform repolarization on specific input bit channel(s) of the polarization matrices to improve the channel reliability. Further, extra output bit(s) may be generated during the repolarization, so that the code length of the polar code is not restricted to the power of 2, thereby reducing the complexity of system design.

It will be apparent to those skilled in the art that various modifications and variations can be made to the disclosed embodiments. It is intended that the specification and examples be considered as exemplary only, with a true scope of the disclosure being indicated by the following claims and their equivalents.