Polar code successive cancellation list decoding

Abstract

A method is performed by an information decoder. The method comprises obtaining (S102) an encoded sequence having been encoded using a polar code. The method comprises successively decoding (S104) the encoded sequence into the successive bits of the decoded sequence. Successively decoding the encoded sequence comprises performing a threshold check (S106) for evaluating a bit uncertainty criterion. Successively decoding the encoded sequence comprises branching (S108) the decoded sequence into two candidate decoded sequences whenever the threshold check fails.

Claims

1. A method for decoding an encoded sequence into a decoded sequence, the method comprising an information decoder: obtaining the encoded sequence, the encoded sequence having been encoded using a polar code; and successively decoding the encoded sequence into the decoded sequence, by: performing a threshold check of at least some successive binary digits in a sequence of the encoded sequence that is being decoded, the threshold check evaluating a bit uncertainty criterion of the at least some successive binary digits; and branching the decoded sequence into two candidate decoded sequences whenever the threshold check fails.

2. The method of claim 1, wherein performing the threshold check comprises determining one probability value for each one of the at least some successive binary digits.

3. The method of claim 2, wherein the bit uncertainty criterion for a given binary digit of the at least some successive binary digits is evaluated using the one probability value for the given binary digit.

4. The method of claim 3: wherein evaluating the bit uncertainty criterion for the given binary digit comprises determining at least one of a log-likelihood ratio, entropy, self-information, or probability measure using the probability value of the given binary digit; and wherein the threshold check fails whenever the log-likelihood ratio, entropy, self-information, or probability measure is lower than a threshold.

5. The method of claim 2: further comprising repeating the successively decoding until all binary digits of the encoded sequence have been decoded, resulting in at least two candidate decoded sequences; further comprising discarding all but one of the at least two candidate decoded sequences, resulting in one single decoded sequence; wherein the discarding comprises selecting as the one single decoded sequence a candidate decoded sequence of the at least two candidate decoded sequences having highest accumulated probability values.

6. The method of claim 2: further comprising repeating the successively decoding until all binary digits of the encoded sequence have been decoded, resulting in at least two candidate decoded sequences; further comprising discarding all but one of the at least two candidate decoded sequences, resulting in one single decoded sequence; wherein the discarding comprises: performing a respective cyclic redundancy check for each of the at least two candidate decoded sequences; and selecting as the one single decoded sequence a candidate decoded sequence of the at least two candidate decoded sequences that passes its cyclic redundancy check.

7. The method of claim 1, further comprising: repeating the successively decoding until all binary digits of the encoded sequence have been decoded, resulting in at least two candidate decoded sequences; and discarding all but one of the at least two candidate decoded sequences, resulting in one single decoded sequence.

8. The method of claim 1, wherein the branching is caused by a binary digit of the at least some successive binary digits for which the threshold check fails having an equal probability of being decoded into a zero and a one during the successive decoding of the encoded sequence.

9. The method of claim 1, wherein the branching causes a binary digit of the at least some successive binary digits for which the threshold check fails to be set to binary 0 in a first of the two candidate decoded sequences and set to binary 1 in a second of the two candidate decoded sequences.

10. The method of claim 1, wherein the threshold check is performed for each successive binary digit in the sequence of the encoded sequence that is being decoded.

11. An information decoder for decoding an encoded sequence into a decoded sequence, the information decoder comprising: processing circuitry; memory containing instructions executable by the processing circuitry whereby the information decoder is operative to: obtain the encoded sequence, the encoded sequence having been encoded using a polar code; and successively decode the encoded sequence into the decoded sequence by: performing a threshold check of at least some successive binary digits in a sequence of the encoded sequence that is being decoded, the threshold check evaluating a bit uncertainty criterion of the at least some successive binary digits; and branching the decoded sequence into two candidate decoded sequences whenever the threshold check fails.

12. The information decoder of claim 11, wherein performing the threshold check comprises determining one probability value for each one of the at least some successive binary digits.

13. The information decoder of claim 12, wherein the bit uncertainty criterion for a given binary digit of the at least some successive binary digits is evaluated using the one probability value for the given binary digit.

14. The information decoder of claim 13: wherein evaluating the bit uncertainty criterion for the given binary digit comprises determining at least one of a log-likelihood ratio, entropy, self-information, or probability measure using the probability value of the given binary digit; and wherein the threshold check fails whenever the log-likelihood ratio, entropy, self-information, or probability measure is lower than a threshold.

15. The information decoder of claim 12: wherein the instructions are such that the information decoder is operative to: repeat the successively decoding until all binary digits of the encoded sequence have been decoded, resulting in at least two candidate decoded sequences; discard all but one of the at least two candidate decoded sequences, resulting in one single decoded sequence; and wherein the discarding comprises selecting as the one single decoded sequence a candidate decoded sequence of the at least two candidate decoded sequences having highest accumulated probability values.

16. The information decoder of claim 12: wherein the instructions are such that the information decoder is operative to: repeat the successively decoding until all binary digits of the encoded sequence have been decoded, resulting in at least two candidate decoded sequences; discard all but one of the at least two candidate decoded sequences, resulting in one single decoded sequence; and wherein the discarding comprises: performing a respective cyclic redundancy check for each of the at least two candidate decoded sequences; and selecting as the one single decoded sequence a candidate decoded sequence of the at least two candidate decoded sequences that passes its cyclic redundancy check.

17. The information decoder of claim 11, wherein the instructions are such that the information decoder is operative to: repeat the successively decoding until all binary digits of the encoded sequence have been decoded, resulting in at least two candidate decoded sequences; and discard all but one of the at least two candidate decoded sequences, resulting in one single decoded sequence.

18. The information decoder of claim 11, wherein the branching is caused by a binary digit of the at least some successive binary digits for which the threshold check fails having an equal probability of being decoded into a zero and a one during the successive decoding of the encoded sequence.

19. The information decoder of claim 11, wherein the branching causes a binary digit of the at least some successive binary digits for which the threshold check fails to be set to binary 0 in a first of the two candidate decoded sequences and set to binary 1 in a second of the two candidate decoded sequences.

20. A non-transitory computer readable recording medium storing a computer program product for decoding an encoded sequence into a decoded sequence, the computer program product comprising software instructions which, when run on processing circuitry of an information decoder, causes the information decoder to: obtain the encoded sequence, the encoded sequence having been encoded using a polar code; and successively decode the encoded sequence into the decoded sequence by: performing a threshold check of at least some successive binary digits in a sequence of the encoded sequence that is being decoded, the threshold check evaluating a bit uncertainty criterion of the at least some successive binary digits; and branching the decoded sequence into two candidate decoded sequences whenever the threshold check fails.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The inventive concept is now described, by way of example, with reference to the accompanying drawings, in which:

(2) FIG. 1 is a schematic diagram illustrating a communication network according to an embodiment;

(3) FIG. 2 is a schematic diagram illustrating mutual information according to an embodiment;

(4) FIG. 3 is a schematic diagram illustrating a polar code;

(5) FIGS. 4, 5, and 6 are flowcharts of methods according to embodiments;

(6) FIGS. 7 and 8 are schematic diagrams illustrating list decoding according to embodiments;

(7) FIG. 9 is a schematic diagram showing functional units of an information decoder according to an embodiment;

(8) FIG. 10 is a schematic diagram showing functional modules of an information decoder according to an embodiment; and

(9) FIG. 11 shows one example of a computer program product comprising computer readable means according to an embodiment.

DETAILED DESCRIPTION

(10) The inventive concept will now be described more fully hereinafter with reference to the accompanying drawings, in which certain embodiments of the inventive concept are shown. This inventive concept may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided by way of example so that this disclosure will be thorough and complete, and will fully convey the scope of the inventive concept to those skilled in the art. Like numbers refer to like elements throughout the description. Any step or feature illustrated by dashed lines should be regarded as optional.

(11) FIG. 1 is a schematic diagram illustrating a communications network 100 where embodiments presented herein can be applied. The communications network 100 comprises an information encoder 110 and an information decoder 200. The information encoder 110 is configured to encode an information sequence z=z.sub.1, z.sub.2, z.sub.3, . . . , z.sub.N into an encoded sequence y. The information decoder 200 is configured to decode an encoded sequence into a decoded sequence {circumflex over (z)}.

(12) The information encoder 110 and the information decoder 200 are separated by a symbolic communications channel 120. The communications channel 120 models how the encoded sequence y is affected between the information encoder 110 and the information decoder 200. For example, the transmission of the encoded sequence y may cause errors to be inserted in the encoded sequence y. Here, and error is to be interpreted as a bit-value in the encoded sequence y being flipped from a binary zero to a binary one, or vice versa, during transmission over the communications channel 120. Therefore the encoded sequence y as obtained by the information decoder 200 is denoted , where =y if the channel is error-free and y elsewhere. Further, if =y then also {circumflex over (z)}=z, but if y there is a non-zero probability that {circumflex over (z)}z. In order to minimize the probability that {circumflex over (z)}z the information encoder 110 during the encoding procedure adds redundancy to the information sequence z in a controlled manner, resulting in the encoded sequence y. The redundancy is added in the controlled manner by using a polar code. Conversely, at the information decoder 200 the added redundancy is removed from the received encoded sequence in a controlled manner, resulting in the decoded sequence {circumflex over (z)}. Further, the communications network 100 comprises a (optional) data storage 130. The data storage 130 is assumed to store data losslessly, i.e., without introducing losses in the stored data. Any losses in the data are modeled by the communications channel 120.

(13) The information encoder 110 and the information decoder 200 use a polar code to protect the information sequence z against channel distortions. The information encoder 110 will encode the information sequence z using a predetermined polar code into the encoded sequence y which will then be used in a transmission over the communications channel 120. The received encoded sequence , which, as disclosed above, can be distorted when passing through the communications channel 120, will be decoded by the information decoder 200 using a polar code successive decoder.

(14) FIG. 3 is a schematic diagram illustrating a polar code 300, where w represents the communications channel 120. In the example of FIG. 3, some of z.sub.1, z.sub.2, z.sub.3, . . . , z.sub.N represents information bits and the rest of z.sub.1, z.sub.2, z.sub.3, . . . , z.sub.N represents added redundancy bits (having fixed, and thus known, values). Using the polar code example in FIG. 3, the information decoder 200, based on the received encoded sequence , estimates the probabilities of the encoded sequence y and then propagates these backwards throughout the polar code structure to calculate the probabilities of the information sequence z. The decision made on z.sub.1 based on the calculated probability is propagated downwards when the probabilities of z.sub.2, z.sub.3, . . . , z.sub.N are evaluated. The same is repeated for z.sub.2 and so on, which defines the underlying successive decoding procedure. The better the information decoder 200 is, i.e., the more errors in the received encoded sequence it can correct, the more information can be conveyed over the communication channel w.

(15) The embodiments disclosed herein relate to decoding an encoded sequence into a decoded sequence {circumflex over (z)}, where the encoded sequence has been encoded using a polar code. In order to obtain such mechanism there is provided a information decoder 200, a method performed by the information decoder 200, a computer program product comprising code, for example in the form of a computer program, that when run on a information decoder 200, causes the information decoder 200 to perform the method.

(16) FIGS. 4, 5, and 6 are flow charts illustrating embodiments of methods for decoding an encoded sequence into a decoded sequence {circumflex over (z)}. The methods are performed by the information decoder 200. The methods are advantageously provided as computer programs.

(17) Reference is now made to FIG. 4 illustrating a method for decoding an encoded sequence into a decoded sequence {circumflex over (z)} as performed by the information decoder 200 according to an embodiment.

(18) S102: The information decoder 200 obtains the encoded sequence . The encoded sequence has been encoded using a polar code.

(19) S104: The information decoder 200 successively decodes the encoded sequence into the decoded sequence {circumflex over (z)}.

(20) The successive decoding is based on using a criterion that depends on the instantaneous channel realizations, to expand a list of candidate decoded sequences with a new candidate candidate decoded sequence. Successively decoding the encoded sequence into the decoded sequence {circumflex over (z)} therefore involves the information decoder 200 to be configured to perform steps S106 and S108:

(21) S106: The information decoder 200 performs a threshold check of at least some successive binary digits in a sequence of the encoded sequence that is being decoded. The threshold check evaluates a bit uncertainty criterion of these at least some successive binary digits. Exemplary embodiments of such bit uncertainty criterions will be disclosed below.

(22) S108: The information decoder 200 branches the decoded sequence into two candidate decoded sequences whenever the threshold check fails.

(23) The branching is thus based on a threshold check using an uncertainty mapping that depends on the instantaneous channel realization

(24) This method differs from aforementioned US2015/0026543 A1 in the way the decision is made whether to branch the decoded sequence. In US2015/0026543 A1, the decoded sequence is branched based on a predetermined set of bit indices. This list is designed when the polar code is designed and does not change for different channel realizations. From a channel perspective the list thus appears as deterministic. A typical list is based on the most reliable bit indices in terms of mutual information (or entropy). Mutual information is an averaged measure over a distribution of channel realizations. According to the herein disclosed method, the decoded sequence is branched based on a threshold check using an uncertainty mapping that depends on the instantaneous channel realization.

(25) This method differs also from the aforementioned paper List decoding of polar codes in the way the decision is made whether to branch the decoded sequence. In List decoding of polar codes, all possible decoded sequence are expanded fully (i.e., all binary digits are branched) until a limited list-size has been reached. This branching is then followed by a pruning criterion in order to remove the least likely decoded sequence in the remaining decoding steps in order to keep the list-size feasible. According to the herein disclosed method, the decoding procedure involves the opposite, namely not all decoded binary digits are branched and no decoded sequences are pruned.

(26) Instead, only specific decoded sequences are chosen (by means of only selected binary digits being branched).

(27) As mentioned above, the information decoder 200 in step S108 branches the decoded sequence into two candidate decoded sequences whenever the threshold check fails. In this respect, no branching is performed when the whenever the threshold check is successful. When the threshold check is successful the binary digits in the sequence of the encoded sequence that is being decoded are decoded into one decoded sequence {circumflex over (z)}, without any branching thereof.

(28) The herein disclosed methods for decoding the encoded sequence into the decoded sequence {circumflex over (z)} can thus use a dynamic list expansion procedure when decoding a polar code with the possibility to have several instances (each defined by a candidate decoded sequence) of the polar code decoding problem. The candidate decoded sequences are found by successive decoding of the encoded sequence. Following the polar code bit-order, the successive decoding will decode the first bit, which means that it will set the most likely value of that bit (binary 0 or 1) as the true decoded value. This information will then be propagated throughout the structure of the polar code (updating the probabilities in the remaining binary digits), before the next bit in the order, i.e., the second bit is decoded. This decoding procedure be repeated until all the remaining binary digits are decoded. According to the herein disclosed methods, a bit, that does not have a distinct probability of being either 0 or 1, will be set to both values and thus two separate candidate decoded sequences will be created from the encoded sequence that is being decoded, one with that binary digit being set to 0 and another with the same binary digit set to 1.

(29) Embodiments relating to further details of decoding an encoded sequence into a decoded sequence {circumflex over (z)} as performed by the information decoder 200 will now be disclosed.

(30) There may be different causes of the branching. For example, according to an embodiment the branching is caused by a binary digit of the at least some successive binary digits for which the threshold check fails has an equal probability of being decoded into a zero and a one during the successive decoding of the encoded sequence. In this respect the term equal probability can be defined as a probability value of decoding a binary digit to a one being in the interval 0.35-0.65, preferably in the interval 0.4-0.6, more preferably in the interval 0.45-0.55.

(31) There may be different ways to form the candidate decoded sequences when performing the branching. For example, according to an embodiment the branching causes a binary digit of the at least some successive binary digits for which the threshold check fails to be set to binary 0 in a first of the two candidate decoded sequences and set to binary 1 in a second of the two candidate decoded sequences.

(32) That is, some binary digits that the information decoder 200 decides to be uncertain (for instance if the probability of a given binary digit being binary 1 is close to 0.5, then the information decoder 200 cannot be certain that the value of this given binary digit is binary 0 or binary 1) can be branched into two decoding instances: one candidate decoded sequence where this given binary digit is set to binary 0 and one candidate decoded sequence where this given binary digit is set to binary 1.

(33) Reference is now made to FIG. 5 illustrating methods for decoding an encoded sequence into a decoded sequence {circumflex over (z)} as performed by the information decoder 200 according to further embodiments. It is assumed that steps S102, S104, S106, and S108 are performed as disclosed above and a thus repeated description thereof is therefore omitted.

(34) There may be different ways to perform the threshold check in step S106. Different embodiments relating thereto will now be described in turn. For example, estimated probabilities can be acquired during the successive decoding of the polar code. Hence, according to an embodiment the information decoder 200 is configured to perform step S106a as part of performing the threshold check in step S106:

(35) S106a: The information decoder 200 determines one probability value for each of the at least some successive binary digits.

(36) The bit uncertainty criterion for a given binary digit of said at least some successive binary digits can then be evaluated using this one probability value for this given binary digit.

(37) The branching can be based on various uncertainty metrics of the binary digits that are being decoded. There can thus be different ways to evaluate the bit uncertainty criterion for this given binary digit. For example, the uncertainty criterion can be evaluated using a log-likelihood ratio, entropy, sell-information, or probability measure. Hence, according to an embodiment the information decoder 200 is configured to perform step S106b as part of performing the threshold check in step S106 in order to evaluate the bit uncertainty criterion for this given binary digit:

(38) S106b: The information decoder 200 determines at least one of a log-likelihood ratio, entropy, sell-information, or probability measure using the probability value of this given binary digit. The threshold check then fails whenever the absolute value of the log-likelihood ratio, the entropy, the self-information, or the probability measure is lower than a threshold. Examples of such thresholds will be disclosed next.

(39) For instance, the log-likelihood ratio value LLR.sub.i of a given binary digit at index i represents the certainty of that given binary digit being a binary 0 or a binary 1. If the log-likelihood ratio value is close to zero, which is an indication that the threshold check fails, branching is performed at this given binary digit. Further examples of threshold checks are:

(40) |LLR.sub.i|, where LLR.sub.i is the log-likelihood ratio value of the binary digit at index i, where the log-likelihood ratio value are determined

(41) H.sub.i, where H.sub.i is the entropy value of the binary digit at index i,

(42) I.sub.i, where I.sub.i is the sell-information value of the binary digit at index i.

(43) Here, the notation means that a decision is taken based on a comparison with a threshold. Denote by p.sub.i the probability of the binary digit at index i being decoded into binary 1. The log-likelihood ratio values could then be determined from the estimated probabilities that are acquired in the successive decoding of the polar code, i.e.,

(44) ${\mathrm{LLR}}_i=\log \left(\frac{p_i}{1-\mathrm{pi}}\right).$
The entropy value can be determined assuming a binary symmetric channel, i.e., H.sub.i=p.sub.i log.sub.2 p.sub.i(1p.sub.i) log.sub.2(1p.sub.i). The sell-information can be determined as I.sub.i=1H.sub.i.

(45) After the successive decoding in steps S104, S106, S108 has been completed, the information decoder 200 can be configured to run through a number of parallel decoding instances and select the candidate decoded sequence which has the highest probability of being correct (by for instance accumulating the probabilities over the binary digits in that candidate decoded sequence). Hence, according to an embodiment the information decoder 200 is configured to perform steps S110 and S112 after having performed step S108:

(46) S110: The information decoder 200 repeats the successively decoding (in steps S104, S106, S108) until all binary digits of the encoded sequence have been decoded. This results in at least two candidate decoded sequences.

(47) S112: The information decoder 200 discards all but one of the at least two candidate decoded sequences, resulting in one single decoded sequence.

(48) After the list decoding is performed, the information decoder 200 can thereby select the candidate sequence which has the highest probability of being correct. Two embodiments relating to how the information decoder 200 can discard all but one of the at least two candidate decoded sequences will now be disclosed.

(49) According to a first embodiment the information decoder accumulates the probabilities over the binary digits in the candidate decoded sequences. According to this embodiment the information decoder 200 is configured to discard all but one of the at least two candidate decoded sequences in step S112 by performing step S112a:

(50) S112a: The information decoder 200 selects as the one single decoded sequence that candidate decoded sequences of the at least two candidate decoded sequences that has highest accumulated probability values.

(51) Step S112a represents a stand-alone technique that only uses the information in the information decoder 200. Another way is to perform a cyclic redundancy check at the end. This can be an even more confident way of picking a single candidate decoded sequence amongst a plurality of candidate decoded sequences. Hence, according to a second embodiment the information decoder 200 is configured to discard all but one of the at least two candidate decoded sequences in step S112 by performing step S112b and step S112c:

(52) S112b: The information decoder 200 performs a respective cyclic redundancy check for each of the at least two candidate decoded sequences.

(53) S112c: The information decoder 200 selects as the one single decoded sequence that candidate decoded sequences of the at least two candidate decoded sequences that passes its cyclic redundancy check.

(54) Although it has above been disclosed that the threshold check is performed for at least some of the successive binary digits in the sequence of the encoded sequence that is being decoded, the threshold check can be performed for all these successive binary digits. Hence, according to an embodiment the threshold check in step S106 is performed for each successive binary digit in the sequence of the encoded sequence that is being decoded.

(55) Reference is now made to FIG. 6 illustrating methods for decoding an encoded sequence into a decoded sequence {circumflex over (z)} as performed by the information decoder 200 according to one particular embodiment based on at least some of the above disclosed embodiments.

(56) S201: The information decoder 300 obtains a value for a current binary digit in the encoded sequence being decoded. One way to implement step S201 is to perform step S102.

(57) S202: The information decoder 300 determines a probability value p.sub.i for the binary digit at index i being decoded into binary 1 (or the probability 1p.sub.i for the binary digit at index i being decoded into binary 0). One way to implement step S202 is to perform step S106a as part of step S106.

(58) S203: The information decoder 300 evaluates a bit uncertainty criterion for the binary digit at index i being decoded into binary 1 (or binary 0). One way to implement step S203 is to perform step S106b as part of step S106.

(59) S204: The information decoder 300, if the evaluation of the bit uncertainty criterion is successful, fixes the binary digit at index i being decoded into its most probable value (i.e., binary 0 or binary 1, depending on the value of p.sub.i).

(60) S205: The information decoder 300, if the evaluation of the bit uncertainty criterion fails, branches the decoded sequence into two candidate decoded sequence at the binary digit at index i. Further, the information decoder 300 fixes the binary digit at index i to have binary value 0 in one of the two candidate decoded sequences and binary value 1 in the other of the two decoded candidate decoded sequences. One way to implement step S205 is to perform step S108.

(61) Each branching during the successive decoding thus creates a list of candidate decoded sequences where each branched bit effectively results in a pair of candidate decoded sequences where the branched bit is fixed to binary 0 in one candidate decoded sequence and to binary 1 in the other candidate decoded sequence.

(62) S206: The information decoder 300 adds the two candidate sequences to a list of candidate decoded sequences.

(63) Steps S201-S206 are repeated until the entire encoded sequence has been decoded, as in step S110.

(64) Any of above disclosed steps S112, S112a, S112b, S112c can then be performed in order to select a single decoded sequence.

(65) FIG. 7 illustrates an example of list decoding of a polar code with a list that has reached a size of 4. In this example, the probabilities show the evaluated likelihoods of each bit being equal to 1. Any bit whose probability is between 0.50.2 is said to be uncertain in this example and hence is branched out. This has resulted in four different paths. In the example of FIG. 7 only the third path indicates a 0 at bit five (the probability of decoding bit 5 as a 1 is 0.18 and hence bit 5 is decoded as 0) and hence this path is selected as the correct decoded sequence.

(66) FIG. 8 shows a more general illustration of list decoding of a polar code wherein a sequence of uncertain binary digits may result in sub-trees of candidate decoded sequences. In more detail, FIG. 8 at 800 illustrates a sequence of the encoded sequence that is being decoded. For some of the binary digits the threshold check is successful and these binary digits are identified as fixed bits. A successive sequence of such fixed bits define one path 810. For some of the binary digits the threshold check fails and these binary digits are identified as uncertain bits. For each failure of the threshold check a branching of the decoded sequence into two candidate decoded sequences is performed, resulting in multiple paths 820a, 820b for the uncertain bits needed to be evaluated. At the end of the decoding, one path 830 of the multiple paths 820a, 820b is selected, based on having accumulated probability values as highly likely (in comparison to all other candidate decoded sequences), to represent the decoded sequence.

(67) FIG. 9 schematically illustrates, in terms of a number of functional units, the components of an information decoder 200 according to an embodiment.

(68) Processing circuitry 210 is provided using any combination of one or more of a suitable central processing unit (CPU), multiprocessor, microcontroller, digital signal processor (DSP), etc., capable of executing software instructions stored in a computer program product 1110 (as in FIG. 11), e.g. in the form of a storage medium 230. The processing circuitry 210 may further be provided as at least one application specific integrated circuit (ASIC), or field programmable gate array (FPGA).

(69) Particularly, the processing circuitry 210 is configured to cause the information decoder 200 to perform a set of operations, or steps, S102-S112, as disclosed above. For example, the storage medium 230 may store the set of operations, and the processing circuitry 210 may be configured to retrieve the set of operations from the storage medium 230 to cause the information decoder 200 to perform the set of operations. The set of operations may be provided as a set of executable instructions.

(70) Thus the processing circuitry 210 is thereby arranged to execute methods as herein disclosed. The storage medium 230 may also comprise persistent storage, which, for example, can be any single one or combination of magnetic memory, optical memory, solid state memory or even remotely mounted memory. The information decoder 200 may further comprise a communications interface 220 at least configured for communications with an information encoder 110. As such the communications interface 220 may comprise one or more transmitters and receivers, comprising analogue and digital components. The processing circuitry 210 controls the general operation of the information decoder 200 e.g. by sending data and control signals to the communications interface 220 and the storage medium 230, by receiving data and reports from the communications interface 220, and by retrieving data and instructions from the storage medium 230. Other components, as well as the related functionality, of the information decoder 200 are omitted in order not to obscure the concepts presented herein.

(71) FIG. 10 schematically illustrates, in terms of a number of functional modules, the components of an information decoder 200 according to an embodiment.

(72) The information decoder 200 of FIG. 10 comprises a number of functional modules; an obtain module 210a configured to perform step S102, a decode module 210b configured to perform step S104, a check module 210c configured to perform step S106, and a branch module 210f configured to perform step S108.

(73) The information decoder 200 of FIG. 10 may further comprises a number of optional functional modules, such as any of a determine module 210d configured to perform step S106a, an evaluate module 210e configured to perform step S106b, a repeat module 210g configured to perform step S110, a discard module 210h configured to perform step S112, a select module 210i configured to perform step S112a, a cyclic redundancy check (CRC) module 210j configured to perform step S112b, and a select module 210k configured to perform step S112c.

(74) In general terms, each functional module 210a-210k may in one embodiment be implemented only in hardware or and in another embodiment with the help of software, i.e., the latter embodiment having computer program instructions stored on the storage medium 230 which when run on the processing circuitry makes the information decoder 200 perform the corresponding steps mentioned above in conjunction with FIG. 10. It should also be mentioned that even though the modules correspond to parts of a computer program, they do not need to be separate modules therein, but the way in which they are implemented in software is dependent on the programming language used. Preferably, one or more or all functional modules 210a-210k may be implemented by the processing circuitry 210, possibly in cooperation with functional units 220 and/or 230. The processing circuitry 210 may thus be configured to from the storage medium 230 fetch instructions as provided by a functional module 210a-210k and to execute these instructions, thereby performing any steps as disclosed herein.

(75) The information decoder 200 may be provided as a standalone device or as a part of at least one further device. For example, the information decoder 200 may be provided in a radio access network node (such as in a radio base station, a base transceiver station, a node B, or an evolved node B) or in an end-user device (such as in a portable wireless device, a mobile station, a mobile phone, a handset, a wireless local loop phone, a user equipment (UE), a smartphone, a laptop computer, a tablet computer, a sensor device, an Internet of Things device, or a wireless modem).

(76) Thus, a first portion of the instructions performed by the information decoder 200 may be executed in a first device, and a second portion of the of the instructions performed by the information decoder 200 may be executed in a second device; the herein disclosed embodiments are not limited to any particular number of devices on which the instructions performed by the information decoder 200 may be executed. Hence, the methods according to the herein disclosed embodiments are suitable to be performed by a information decoder 200 residing in a cloud computational environment. Therefore, although a single processing circuitry 210 is illustrated in FIG. 9 the processing circuitry 210 may be distributed among a plurality of devices, or nodes. The same applies to the functional modules 210a-210k of FIG. 10 and the computer program 1120 of FIG. 11 (see below).

(77) FIG. 11 shows one example of a computer program product 1110 comprising computer readable storage medium 1130. On this computer readable storage medium 1130, a computer program 1120 can be stored, which computer program 1120 can cause the processing circuitry 210 and thereto operatively coupled entities and devices, such as the communications interface 220 and the storage medium 230, to execute methods according to embodiments described herein. The computer program 1120 and/or computer program product 1110 may thus provide means for performing any steps as herein disclosed.

(78) In the example of FIG. 11, the computer program product 1110 is illustrated as an optical disc, such as a CD (compact disc) or a DVD (digital versatile disc) or a Blu-Ray disc. The computer program product 1110 could also be embodied as a memory, such as a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM), or an electrically erasable programmable read-only memory (EEPROM) and more particularly as a non-volatile storage medium of a device in an external memory such as a USB (Universal Serial Bus) memory or a Flash memory, such as a compact Flash memory. Thus, while the computer program 1120 is here schematically shown as a track on the depicted optical disk, the computer program 1120 can be stored in any way which is suitable for the computer program product 1110.

(79) The inventive concept has mainly been described above with reference to a few embodiments. However, as is readily appreciated by a person skilled in the art, other embodiments than the ones disclosed above are equally possible within the scope of the inventive concept, as defined by the appended patent claims. Or example, although the above disclosed polar codes have been described as being binary valued, it is foreseen that the herein disclosed embodiments could be applied to decoding of non-binary valued polar codes, for example by determining multi-dimensional log-likelihoods (or other uncertainty criterions) for arbitrary non-binary alphabets.