Patent Description:
A CRC construction mechanism has been proposed with J' bits for the purpose of assisting the polar decoding, where <NUM><=J'<=Jmax, aiming for Jmax, e.g. in the region of <NUM> (other values are not precluded). This mechanism does not preclude the use of the J bits for assisting decoding and any PC-frozen bits are considered to be among the J' bits.

In the proposals mentioned above there are J CRC bits for error detection and J' (additional) bits which may be CRC, Parity, or Hash bits used for error correction purposes. The J' error correcting bits can be placed in the non-frozen or frozen bit positions such a way that tree pruning happens whenever an info bit and associated CRC/parity/or Hash bit is available. In<NPL>, a distributed method is proposed for tree pruning by distributing info and CRC bits in such a way that it allows CRC checks to occur much earlier than usually happens. This allows early termination of the decoding. In <NPL>, two types of longer-CRC polar codes are discussed.

In general, early termination is useful as it reduces the energy consumption of blind decodes and reduces the latency of recovery. However, relying on a single CRC or parity bit to terminate the decoding process can lead to higher miss detection, where the receiver discards the transmission when the CRC or parity bit is failed (for the decoded part of info bits).

Examples of techniques according to embodiments of the invention are described hereunder in detail, by way of example only, with reference to the accompanying drawings, in which:.

Techniques according to embodiments of the present invention are described in detail below, by way of example only.

The concepts as discussed in further detail propose new methods for enabling early termination utilizing CRC bits purposed for both error correction and detection.

The distribution as disclosed herein can also in some examples not falling under the scope of the claimed invention be used with respect to parity or hash bits, where parity or hash bits are distributed such a way that they can decode together with the information bits and be used to enable the early termination.

<FIG> schematically shows an example of four user equipments (UEs) (for example, high complexity devices such as smartphones etc., low complexity devices such as Machine Type Communications (MTC) devices or any other type of wireless communication device) <NUM> located within the coverage area of a cell operated by a wireless network infrastructure node, which is generally referred to below as a base station (BS). <FIG> only shows a small number of base stations, but a radio access network typically comprises a large number of base stations each operating one or more cells.

Each BS <NUM> of a radio access network is typically connected to one or more core network entities and/or a mobile management entity etc., but these other entities are omitted from <FIG> for conciseness.

<FIG> shows a schematic view of an example of apparatus for each UE <NUM>. The UE <NUM> may be used for various tasks such as making and receiving phone calls, receiving and sending data from and to a data network, and experiencing, for example, multimedia or other content. The UE <NUM> may be any device at least capable of both recovering data/information from radio transmissions made by the BS <NUM>, and making radio transmissions from which data/information is recoverable by the BS <NUM>. Non-limiting examples of user equipment (UE) <NUM> include smartphones, tablets, personal computers, and devices without any user interface, such as devices that are designed for machine type communications (MTC).

With reference to <FIG>, a baseband processor <NUM>, operating in accordance with program code stored at memory <NUM>, controls the generation and transmission of radio signals via radio-frequency (RF) front end <NUM> and antenna <NUM>. The RF front end <NUM> may include an analogue transceiver, filters, a duplexer, and antenna switch. Also, the combination of antenna <NUM>, RF front end <NUM> and baseband processor <NUM> recovers data/information from radio signals reaching UE <NUM> from e.g. BS <NUM>. The UE <NUM> may also comprise an application processor (not shown) that generates user data for transmission via radio signals, and processes user data recovered from radio signals by baseband processor <NUM> and stored at memory <NUM>.

The application processor and the baseband processor <NUM> may be implemented as separate chips or combined into a single chip. The memory <NUM> may be implemented as one or more chips. The memory <NUM> may include both read-only memory and random-access memory. The above elements may be provided on one or more circuit boards.

The UE may include additional other elements not shown in <FIG>. For example, the UE <NUM> may include a user interface such as a key pad, voice command recognition device, touch sensitive screen or pad, combinations thereof or the like, via which a user may control operation of the UE <NUM>. The UE <NUM> may also include a display, a speaker and a microphone. Furthermore, the UE <NUM> may comprise appropriate connectors (either wired or wireless) to other devices and/or for connecting external accessories (e.g. hands-free equipment) thereto.

<FIG> shows an example of apparatus for use at the BS <NUM> of <FIG>. A baseband processor <NUM>, operating in accordance with program code stored at memory <NUM>, (a) controls the generation and transmission of radio signals via the combination of RF front end <NUM> and antenna <NUM>; and (b) recovers control information/data from radio transmissions reaching the BS from e.g. UEs <NUM>. The RF front end may include an analogue transceiver, filters, a duplexer, and antenna switch. Both the processor <NUM> and the memory <NUM> may be implemented as one or more chips. The memory <NUM> may include both read-only memory and random-access memory. The above elements may be provided on one or more circuit boards. The apparatus also comprises an interface <NUM> for transferring data to and from one or more other entities such as e.g. core network entities, mobile management entities, and other base stations in the same access network.

It should be appreciated that the apparatus shown in each of <FIG> described above may comprise further elements which are not directly involved with the embodiments of the invention described hereafter.

With respect to <FIG> an example of a two stage J and J' CRC attachment apparatus is shown.

The information bits of the control information or control payload, K bits, are passed to an error detector <NUM> which is configured to encode the control information with CRC J bits which are used for the error detection purpose. The encoded bits, K + J bits, are then passed to an error corrector <NUM> configured to encode the K+J bits with CRC J' bits for error correction purposes. The encoded bits, K + J + J' bits, are then passed to a polar encoder <NUM>. The polar encoder <NUM> may be configured to receive the known frozen bits and further configured to map the encoded bits to the most reliable locations of the polar code word prior encoding. The output of the polar encoder <NUM> is then passed to the rate matcher <NUM> configured to rate match the output of the polar encoder <NUM> with a suitable output binary channel.

The CRC distribution performed in the error detector <NUM> and the error corrector <NUM> is mainly obtained by observing a generator matrix of the CRC polynomial. A specific CRC bit is related only to a subset of the information bits, and not all of them. In the successive decoding of the polar code in the decoder, if all the related information bits are decoded at some decoding stage, the error check of the CRC bit is possible.

For the typical successive cancellation list (SCL) based decoding, at each decoding stage, there are at most L branches kept. So if all these L branches fail for the CRC check of the available CRC bits, there must be some errors in the codeword, either in the information bits or in the CRC bits. In a normal CRC distribution, it is not possible to correct this and decoding should be terminated.

This is referred to as early termination and may be helpful to reduce the decoding power and reduce the decoding calculations. However, it is possible that information bits are correct and it is the CRC bit that is in error. In such a case the early termination may lead to a missed detection and require the transmitter to transmit the same control message and thus increase the overall latency.

An example of CRC distribution for <NUM> information bits with <NUM> CRC bits (with the CRC polynomial [<NUM><NUM><NUM><NUM><NUM><NUM><NUM>]) is shown herein. The corresponding generator matrix G is shown below (where the right <NUM> bits in each row are the CRC bits associated with the <NUM> information bits preceding them).

By column and row swapping, the CRC check part of G1 can be converted into the following format where relevant bit indexes are indicated.

This matrix shows that the first CRC bit is calculated from information bits with index values of [<NUM><NUM><NUM><NUM>], the second with index values of [<NUM><NUM><NUM><NUM>] and so on.

Within the decoder the CRC bit will be available for CRC checking when these corresponding information bits are decoded as well as the CRC bit itself. Therefore the distribution of the CRC bits within the information bits can be selected to be in an order wherein the CRC bit follows the defined combination of information bits which are used to generate the CRC bit.

In this case information and CRC bits can be distributed as follows. [<NUM><NUM><NUM><NUM> CRC<NUM> <NUM><NUM> CRC<NUM> <NUM><NUM> CRC<NUM> <NUM> CRC<NUM> <NUM> CRC<NUM> <NUM> CRC<NUM> CRC<NUM> CRC<NUM>].

Where CRCx where x=<NUM> to <NUM> is the CRC bit index and X is the information bit index.

As shown in <FIG> the two CRC polynomials where J' is used for error correction (tree pruning) and J bits CRC is used for error detection can be similarly distributed. Thus even though error detection is required after decoding the full information block, these error detecting CRC bits can be used to improve the reliability of early termination. The following procedure is useful to attain higher reliability and improved error correction of the CRC aided SCL decoding.

With respect to <FIG> an example CRC generation and distribution and mapping procedure is described with respect to the apparatus shown in <FIG>.

The error detector <NUM> in some embodiments generates the J CRC bits from the information bits B = [b<NUM> b<NUM> b<NUM> b<NUM> b<NUM> b<NUM>. bK-<NUM> bK] using the J bits polynomial as shown in <FIG> by step <NUM>.

The error detector <NUM> furthermore identifies a distribution pattern to map B and to an output E= [ e<NUM> e<NUM>. eK-<NUM> eK. eK+J-<NUM> eK+J], where Row/swapping is used with J CRC generator matrix to make sure that has an upper triangular structure in the check part as shown in <FIG> by step <NUM>. The purpose of row/swapping is to rank the bit indexes and to arrange CRC bits in such a way that it enables the ability to perform early termination. The CRC generation can be implemented in some embodiments with or without the upper triangular structure. The row/swapping thus does not change the values of the CRC bits, but reorders the CRC bits (this is the most possible case in practices as we normally use traditional CRC generation methods).

The error detector <NUM> furthermore applies a permutation to the K information and J CRC bits to generate F = [ f<NUM> f<NUM>. fK+J-<NUM> fK+J] as shown in <FIG> by step <NUM>.

The error corrector <NUM> may then apply the J' bits CRC polynomial to all of the bits to generate the J' error correction CRC bits as shown in <FIG> by step <NUM>. In some embodiments the polynomial is applied to the information bits only. In some embodiments the polynomial is applied to part of the full block comprising both information and CRC bits.

The error corrector <NUM> furthermore is configured to identify a distribution pattern to map F and J' to an output H = [ h<NUM> h<NUM> h<NUM> h<NUM> h<NUM> h<NUM>. hK+J+J'-<NUM> hK+J+J'], where Row/swapping is used with the J' CRC generator matrix to make sure that has an upper triangular structure in the check part as shown in <FIG> by step <NUM>.

The error corrector <NUM> is further configured to determine a permutation pattern to get F= [ f<NUM> f<NUM> f<NUM>. fK+J-<NUM> fK+J] from the distributed bits of E= [ e<NUM> e<NUM> e<NUM>. eK+J-<NUM> eK+J] in such a way that H = [ h<NUM> h<NUM> h<NUM> h<NUM> h<NUM> h<NUM>. hK+J+J'-<NUM> hK+J+J' ] contains an additional CRC check from the J CRC polynomial before the first CRC bit check of the J' CRC polynomial and may contain additional CRC checks before or after the first CRC bit check of the J' CRC polynomial as shown in <FIG> by step <NUM>.

With respect to <FIG> an example decoder, not falling under the scope of the claimed invention, is shown. The decoder comprises a successive cancellation list (SCL) decoder <NUM> which is configured to output bits based on decoding the channel output by applying an inverse to the polar encoding. However in some embodiments the decoder may be any suitable polar decoder variant which uses CRC or parity bits for tree pruning.

The decoder further comprises a CRC bit checker <NUM> which is configured to apply the CRC check to determine errors in the decoded data and control the successive cancellation decoder <NUM> based on the checks.

<FIG> shows an example flow diagram showing the operation of the decoder as shown in <FIG>.

The J' CRC bits may be used for tree pruning, and may be performed whenever information bits and associated CRC bits are available.

The decoder and the successive cancellation decoder may be configured to continue the decoding process. The decoded bits may be passed to the CRC bit checker <NUM> wherein as soon as J' CRC bits and the information bits are available a first J' CRC bit check is performed (the decoder in other words uses the J CRC bits at the end to detect errors of the decoded information block) as shown in <FIG> by step <NUM>.

If the first CRC check is passed then the decoding continues as shown in <FIG> by step <NUM>.

If the first CRC is failed, the decoder halts checking CRC from the J' CRC polynomial as shown in <FIG> by step <NUM>.

The decoder furthermore is then configured to check CRC bits from the J CRC polynomial. In most cases, some of these CRC bits are decoded prior to the first J' CRC bit. Those CRC bits will be checked to see CRC pass/fail as shown in <FIG> by step <NUM>.

If the CRC check fails in the J CRC polynomial the decoding can be terminated as shown in <FIG> by step <NUM>.

If CRC check passes in the J CRC polynomial, successive cancellation (SCL) decoding is continued with path metric (but discarding J' CRC tests) until the next CRC bit (from J or J') is decoded and then a further check is performed on the this bit as shown in <FIG> by step <NUM>.

If the 'further' CRC check is failed, then decoding can be terminated such as shown in <FIG> by step <NUM>.

If the 'further' CRC is passed, the decoder can continue with normal decoding process (and the J' CRC bit check performed again when available such as shown by the flow diagram loop back to step <NUM>). Thus when the early termination is scheduled happens with the second or later CRC checks, the same procedure can be used.

Although the examples above show a CRC check procedure, it can also be used with parity check polar codes, where CRC is used for error detection purposes. These CRC bits will thus provide additional reliability for error correction even though the main purpose of CRC used there is for error detection.

A detailed example with <NUM> information bits, <NUM> CRC bits with a CRC polynomial [<NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM>] for error detection, and <NUM> CRC bits with a polynomial [<NUM><NUM><NUM><NUM><NUM>] for error correction is considered below.

The corresponding generator matrices (only check part) for the <NUM> bit and <NUM> bit CRC are denoted as G1 and G2. To identify the distribution, only the row/column swapped version only check part) is presented below. <MAT>
<NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM>
G2= <NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM>
According to G2, [ f<NUM> f<NUM> f<NUM>. fK+J-<NUM> fK+J] is distributed to get [ h<NUM> h<NUM> h<NUM>. hK+J+J'-<NUM> hK+J+J' ]. The bit arrangement prior to polar encoding can be the following. Numbers represent bit indexes of [ f<NUM> f<NUM> f<NUM>. fK+J-<NUM> fK+J], [<NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM> C1 <NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM> C2 <NUM><NUM><NUM><NUM><NUM> C3 <NUM><NUM><NUM><NUM><NUM> C4], where Ci (i = <NUM>, <NUM>, <NUM>, <NUM>) are CRC bits used for error correction. According to G1, bit indexes from [b<NUM> b<NUM> b<NUM> b<NUM> b<NUM> b<NUM>. bK-<NUM> bK] are distributed to get [ e<NUM> e<NUM>. eK+J-<NUM> eK+J] as [<NUM><NUM><NUM><NUM> D1 <NUM><NUM><NUM> D2 <NUM><NUM><NUM> D3 <NUM><NUM><NUM> D4 <NUM> D5 D6 D7 <NUM> D8 D9 D10 D11 D12 D13 <NUM> D14 D15 D16],.

where Di (i = <NUM>, <NUM>,. ,<NUM>) are CRC bits used for error detection. Within the mapping stage, [ e<NUM> e<NUM>. eK+J-<NUM> eK+J ] to [ f<NUM> f<NUM> f<NUM>. fK+J-<NUM> fK+J ]is used to facilitate early termination with the help of both J' and J CRC polynomials, therefore, an example mapping can be the following, [<NUM> D3 <NUM><NUM> D10 <NUM><NUM> D5 D2 <NUM> D9 D16 <NUM><NUM><NUM><NUM> D12 D13 <NUM> D6 <NUM><NUM> D8 D15 D1 D7 <NUM> D4 D11 D14 <NUM><NUM>],.

Finally, the information and CRC bits will appear as follows (note that the bit indexes are referring to the actual bit indexes from [b<NUM> b<NUM> b<NUM> b<NUM> b<NUM> b<NUM>. bK-<NUM> bK]. ) [ <NUM><NUM><NUM><NUM> D1 <NUM><NUM><NUM> D2 <NUM><NUM> C1 <NUM> D3 <NUM><NUM><NUM> D4 <NUM> D5 D6 D7 <NUM> C2 D8 D9 D10 D11 D12 C3 D13 <NUM> D14 D15 D16 C4],.

It is evident that when the decoder is using the C1 bit for pruning the paths, D1, D2 bits are already decoded together with their relevant info bits. Thus in the case where C1 fails, D1 and D2 and then D3 will help to identify whether the decoded bits are in error or not. This will facilitate the early termination with lower miss detection probabilities.

Appropriately adapted computer program code product may be used for implementing the embodiments, when loaded to a computer. The program code product for providing the operation may be stored on and provided by means of a carrier medium such as a carrier disc, card or tape. A possibility is to download the program code product via a data network. Implementation may be provided with appropriate software in a server.

Embodiments of the invention may be practiced in various components such as integrated circuit modules.

Claim 1:
A method for encoding a sequence of control information bits comprising:
generating (<NUM>) a first sequence of J cyclic redundancy check, CRC, bits based on the sequence of control information bits using a first CRC polynomial;
generating (<NUM>) a second sequence of J' CRC bits based on the sequence of control information bits using a second CRC polynomial;
distributing the first sequence of J CRC bits and the second sequence of J' CRC bits between the sequence of control information bits to form a first combined sequence of bits, such that, in the bit order of the first combined sequence of bits following the distribution, each of the J+J' CRC bits of the first and the second sequences follows said control information bits, which are used to generate said each CRC bit, and a CRC bit from the first sequence of J CRC bits is located before the first CRC bit from the second sequence of J' CRC bits to enable an error detection check based on said CRC bit from the first sequence of J CRC bits to be performed before a first check based on said first CRC bit from the second sequence of J' CRC bits, wherein the distributing further comprises:
determining (<NUM>) a first distribution pattern to form a second combined sequence of bits comprising the first sequence of J CRC bits and the sequence of control information bits;
applying (<NUM>) the first distribution pattern to the first sequence of J CRC bits and the sequence of control information bits to generate the second combined sequence of bits;
determining (<NUM>) a second distribution pattern to form the first combined sequence of bits comprising the first sequence of J CRC bits, the second sequence of J' CRC bits and the sequence of control information bits; and
applying (<NUM>) the second distribution pattern to the second combined sequence of bits and the second sequence of J' CRC bits to generate the first combined sequence of bits; and
polar encoding the first combined sequence of bits.