Patent Description:
Polar codes are based on Kronecker product matrices. G= F ⊗m = F ⊗ · · · ⊗ F is the m-fold Kronecker product of a seed matrix F.

If A is an m × n matrix and B is a p × q matrix, then the Kronecker product A ⊗ B is the mp × nq block matrix: <MAT>
more explicitly:
<MAT>.

<FIG> shows how a Kronecker product matrix can be produced from a seed matrix G<NUM> <NUM>. Shown in <FIG> are the <NUM>-fold Kronecker product matrix G<NUM> ⊗<NUM> <NUM> and the <NUM>-fold Kronecker product matrix G<NUM> ⊗<NUM> <NUM>, where <MAT>. This approach can be extended to produce m-fold Kronecker product matrix G<NUM> ⊗m.

A polar code can be formed from a Kronecker product matrix based on matrix G<NUM>. For a polar code having codewords of length N = <NUM>m, the generator matrix is G<NUM> ⊗m. An example of using Kronecker product matrix G<NUM> ⊗<NUM> to produce codewords of length <NUM> is depicted in <FIG>. A codeword x is formed by the product of an input vector u and the Kronecker product matrix G<NUM> ⊗<NUM> <NUM> as indicated at <NUM>. The input vector u is composed of frozen bits and information bits. In the specific example, N=<NUM>, so the input vector u is an <NUM> bit vector, and the codeword x is an <NUM>-bit vector. The input vector has frozen bits in positions <NUM>,<NUM>,<NUM> and <NUM>, and has information bits at positions <NUM>,<NUM>,<NUM> and <NUM>. An example implementation of a coder that generates codewords is indicated at <NUM>, where the frozen bits are all set to <NUM>, where a circle around a plus symbol indicates modulo <NUM> addition. For the example of <FIG>, an N=<NUM> bit input vector is formed from K=<NUM> information bits and N-K=<NUM> frozen bits. Codes of this form are referred to as Polar codes and the encoder is referred to as a Polar encoder.

More generally, in "<NPL>, a "channel polarization" theory was proved in chapter IV. Channel polarization is an operation which produces N channels from N independent copies of a binary-input discrete memoryless channel (B-DMC) W such that the new parallel channels are polarized in the sense that their mutual information is either close to <NUM> (low mutual SNR channels) or close to <NUM> (high mutual SNRchannels). In other words, some encoder bit positions will experience a channel with high mutual SNR, and will have a relatively low reliability/low possibility to be correctly decoded, and for some encoder bit positions, they will experience a channel with a high mutual SNR, and will have high reliability /high possibility to be correctly decoded. In code construction, information bits are put in the reliable positions and frozen bits (bits known to both encoder and decoder) are put in unreliable positions. In theory, the frozen bits can be set to any value so long as the frozen bit sequence is known to both encoder and decoder. In conventional applications, the frozen bits are all set to "<NUM>".

<NPL>, discloses bidirectional relay networks, in which a relay node establishes bidirectional communication between two other nodes using a decode-and-forward protocol. In the broadcast phase, the relay transmits additional common and confidential messages, which then requires the study of the bidirectional broadcast channel (BBC) with common and confidential messages. This channel generalizes the broadcast channel with receiver side information considered by Kramer and Shamai. Low complexity polar codes are constructed that achieve the capacity region of both the degraded symmetric BBC, and the BBC with common and confidential messages.

<NPL>, discloses a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arikan. In the proposed list decoder, L decoding paths are considered concurrently at each decoding stage, where L is an integer parameter. At the end of the decoding process, the most likely among the L paths is selected as the single codeword at the decoder output.

In a communication scenario in which a transmitter may want to send the data only for one or several specific receivers, an encoded block transmitted over the air can be received by any other non-targeted receivers. Various approaches can be employed to prevent these non-targeted receivers from decoding the information. Some systems use a well-known security/encrypting protocol on higher layers to provide privacy. However, these approaches involve some higher-layer scheduling resources, and result in a long processing delay. Moreover, higher-layer scheduling algorithms may not provide sufficient security in a relatively low SNR condition.

It would be advantageous to have a relatively simple approach to providing security for polar codes.

A signature-enabled Polar code encoder and decoder are provided. Signature bits are inserted in some unreliable bit positions. Different signature bits are inserted for different receivers. For a given codeword, only the receiver with knowledge of the signature can decode the codeword. Cyclic redundancy check (CRC) bits may be included in the input vector to assist in decoding.

Embodiments of the invention will now be described with reference to the attached drawings in which:.

When Polar codes are used, cyclic redundancy check (CRC) bits can be included in the input vector to assist in decoding. CRC bits are generated based on the information bits being transmitted. CRC bits are included in reliable positions (i.e. the positions with a reliable channel). CRC bits may be added to improve polar code performance for short to moderate block length. For a very long block length polar encoder, CRC is not needed. In a case where CRC bits are included, an N-bit input vector is formed from K information bits, a u-bit CRC, and N-K-u frozen bits. An example is depicted in <FIG>. Starting with a k-bit information block <NUM>, a u-bit CRC is appended at <NUM> to produce a vector with the K-bit information block, and the u-bit CRC at <NUM>. At <NUM>, the N-K-u frozen bits are inserted to produce the N-bit input vector with the K-bit information block, and the u-bit CRC and the N-K-u frozen bits, where N is a power of <NUM>. The vector <NUM> is then multiplied by the Kronecker product matrix at <NUM> to produce an N-bit codeword <NUM>.

In an example implementation (not shown) where N=<NUM>, K=<NUM>, u=<NUM>, there are six frozen bits for a code rate of <NUM> The frozen bits are inserted as positions <NUM>,<NUM>,<NUM>,<NUM>,<NUM> and <NUM>. In the decoder, CRC bits are treated like information bits until such time as they are used to check the other information bits.

A characteristic of a Polar decoder is that once an information bit is decoded, the bit never has the chance to be corrected. A bit that was set at step i cannot be changed at step j > i. In addition, knowledge of the value of future frozen bits or future signature bits is not taken into account i.e. these future bits, even known for the decoder, will not help decode the current information bit.

In a communication scenario in which a transmitter may want to send the data only for one or several specific receivers, an encoded block on the air can be received by any other non-targeted receivers. To prevent these non-targeted receivers from decoding the information, a signature that is known by a transmitter and targeted receiver(s) only is used to protect the encoded data. That is to say, the signature is "embedded" into the encoded data by a given means that only targeted receiver(s) can use it to decode the data. The length of a signature can, for example, be tens of bits up to hundreds of bits. The longer a signature is, the more privacy it can provide, and the larger the resulting signature space. For example with a long enough signature, the signature space may contain thousands or even millions of signatures. In addition, ideally, this signature-enabled feature would be able to work at relatively low signal-to-noise ratio environment.

Some systems use a well-known security/encrypting protocol on higher layers to support the privacy. However, it involves some higher-layer scheduling resources, and results into a long processing delay. Moreover, higher-layer scheduling algorithm may not provide enough anti-jamming function in a relative low SNR condition.

To overcome the shortcomings of methods involving higher-layer scheduling resources , another approach employs signature-based FEC parameters at the physical layer. For example, a Turbo Code's interleaving or puncturing is made a function of the signature. In another example, an LDPC matrix is somehow a function of the signature. These approaches tend to not only have a negative impact on FEC performance but also to increase the complexity of the decoder and the processing latency. Furthermore, their signature space usually contains a very limited number of signatures and can be decoded by brute force.

Another approach involves the use of signature-based Pseudo-Scrambling at the physical layer. This approach requires extra resources (computation and buffer) for de-scrambling and can cause increased processing delay.

In some scenarios, a signature can be the combination of multiple signatures that include a group signature and an individual signature. In this scenario, a part of a data block associated to the group signature can be decoded by all the receivers of the group. A part of a data block associated to the individual signature can be ONLY decoded by this receiver of this group.

Approaches to achieve multiple signatures involve higher layer scheduling, and therefore consume more resources for high-layer scheduling and may result in a long processing time. In addition, this method would divide a long data block into several smaller ones. However, separating a block into several smaller blocks can cause FEC performance (BLER vs. SNR) to degrade due to the smaller blocks (Turbo and LDPC).

An embodiment of the invention provides a single signature-enabled Polar code. In some embodiments, cyclic redundancy check (CRC) bits are included in the input vector to assist in decoding. CRC bits are generated based on the information bits being transmitted. CRC bits are included in reliable positions (i.e. the positions with a reliable channel). CRC bits may be added to improve polar code performance for short to moderate block length. For a very long block length polar encoder, CRC may not be needed. A signature-enabled Polar code with CRC bits is referred to herein as a CRC-checked signature-enabled Polar code. Although an embodiment with CRC is disclosed herein, more generally, in other embodiments, some parity check bits for error detection and/or detection can be included in the relatively reliable bit positions.

Referring to <FIG>, shown is a flowchart of a method of implementing a CRC-checked signature-enabled Polar code for execution by an encoder. At block <NUM>, a K-bit information block for encoding is received or otherwise obtained. In block <NUM>, a u-bit CRC is computed and inserted to produce a vector with the K-bit information block, and the u-bit CRC at <NUM>. At <NUM>, M signature bits are inserted, and N-K-u-M frozen bits are inserted to produce an N-bit input vector <NUM> with the K-bit information block, and the u-bit CRC, the M signature bits and the N-K-u-M frozen bits, where N is a power of <NUM>. The vector <NUM> is then multiplied by the Kronecker product matrix at <NUM> to produce an N-bit codeword output (or stored) at block <NUM>. The Kronecker product matrix is G<NUM> ⊗m, where N =<NUM>m.

The information bits and the CRC bits are inserted in to the codeword in positions corresponding to reliable bit positions for the polar code. The CRC bits do not need to all be together or at the end, so long as the transmitter and receiver know the positions of the CRC bits and the information bits. Similarly, the frozen bits and the signature bits are inserted into the unreliable bit positions for the polar code. In some embodiments, all of the frozen bit positions are used for signature bits.

Various signature lengths can be employed. The length of the signature can be tens of bits up to hundreds of bits. The longer a signature is, the more security it can provide. The signature may be long enough such that there are thousands or even millions of unique signatures.

<FIG> shows an example scenario where the embodiment of <FIG> could be used, where a transmitter <NUM> (Alice's user equipment (UE)) has data targeted for reception by a targeted receiver <NUM> (Bob's UE) and does not want non-targeted receiver <NUM> (Carol's UE) to be able to decode the data. The data block <NUM> for Bob's UE <NUM> is transmitted over the air after CRC-checked signature-enabled polar encoding. By only informing the targeted receiver of the signature bits, the non-targeted receiver will not be able to decode the data.

An example implementation is depicted in <FIG>, where N=<NUM>, K=<NUM>, u=<NUM>, and M=<NUM>, and there are three frozen bits for a code rate of <NUM>. The signature bits are inserted at bit positions <NUM>,<NUM> and <NUM>. The frozen bits are inserted at positions <NUM>,<NUM> and <NUM>, the information bits are in positions <NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>,<NUM>, and the CRC bits are at positions <NUM> and <NUM>.

A CRC-checked signature-enabled Polar decoder does not require significant extra complexity compared with a conventional Polar decoder. The decoder uses the signature bits to decode the information bits in the same ways as frozen bits are used in conventional Polar decoders. Without knowledge of these signature bits, it is nearly impossible for the decoder to decode the information bits successfully. There is no BER/BLER performance degradation due to the presence of the signature bits, as verified by both theory and simulation. In addition, there may be strong anti-jamming and error correction capacity.

In a situation where a data block has a large number of bits (e.g. on the order of a thousand bits) with R=<NUM>/<NUM>~<NUM>/<NUM>, there is room to insert hundreds or even thousands of signature bits, resulting in strong privacy and obstruction capacity.

<FIG> shows a flowchart of a method for implementation in a decoder of successive-cancellation decoding for a CRC-checked signature-enabled Polar codeword having N bits in bit positions i = <NUM> to N-<NUM>. The method starts in block <NUM> with obtaining frozen bit information and signature bit information. This information indicates the M frozen bit positions (a set Frozen), and the K signature bit positions (a set Signature), and the values of the frozen bits (the frozen bits are typically not receiver specific, Frozenm, m =<NUM> to M-<NUM>, typically zero for all receivers), and the signature bits (signaturek, k= <NUM>, K-<NUM>, receiver specific). This information is obtained separately from the received codeword. For example, this information might be communicated by a transmitter to a receiver during an initial connection setup. In a specific example, N=<NUM>, M=<NUM> and K=<NUM>, and the frozen bits are in positions <NUM>,<NUM> and <NUM> and have values <NUM>,<NUM>,<NUM>, and the signature bits are in positions <NUM>, <NUM>,<NUM> and have values <NUM>,<NUM>,<NUM>, as indicated at <NUM>. Decoding starts at bit position <NUM>, by setting index i = <NUM> in block <NUM>. In block <NUM>, if the index i is the index of a signature bit position, then <MAT> is set to the corresponding known signature bit value. In block <NUM>, if the index i is the index of a frozen bit position, then <MAT> is set to the corresponding known frozen bit value. In block <NUM>, if the index I is not the index of a signature bit position or a frozen bit position, then the bit position is decoded to a value of <NUM> or <NUM>, for example using a path comparison operation. If the index i is equal to N-<NUM> in block <NUM>, then the method ends. Otherwise, the index i is incremented in block <NUM> and the method continues back at block <NUM>.

The CRC bits are treated like data bits in the decoder in blocks <NUM> to <NUM>. Then, when the bits are all decoded including data bits and CRC bits, the CRC check is performed in block <NUM>. If the CRC check is successful then the decoded data bits are correct with high probability.

It can be seen that the path comparison block <NUM> is performed only for bits that are neither frozen bits nor signature bits. The approach of <FIG> is not dependent on the specific signature and frozen bit positions.

Another embodiment of the invention provides a CRC-checked multiplesignature-enabled Polar encoder. With such an encoder, multiple signatures are inserted, and differing receivers can decode differing subsets of data depending on their knowledge of the signatures.

Referring to <FIG>, starting at block <NUM>, a K1-bit first information block and a K2-bit second information block are obtained. At <NUM> a u1-bit first CRC is calculated based on the K1-bit first information block, and a u2-bit second CRC is calculated based on the K2-bit second information block to produce a vector <NUM> with the K1-bit first information block, and the u1-bit first CRC, the k2-bit second information block, and the u2-bit second CRC. At <NUM>, a M1-bit first signature is inserted before the K1-bit first information block, and an M2-bit second signature is inserted after the K1-bit first information block and the u1-bit first CRC and before the K2-bit second information block. In addition, the N-K1-u1-M1-K2-u2-M2 frozen bits are inserted to produce the N-bit input vector <NUM> where N is a power of <NUM>. The vector <NUM> is then multiplied by the Kronecker product matrix at block <NUM> to produce an N-bit codeword which is output (or stored) at block <NUM>.

A receiver with knowledge of only the M1-bit first signature can only decode the bits of the K1-bit first information block. It cannot decode the bits of the K2-bit second information block. A receiver with knowledge of both the M1-bit first signature and the M2-bit second signature can decode all the information bits. The decoding approach is the same as the approach of <FIG>, but a receiver that does not have all the signature bits would stop decoding for bit positions following a position containing an unknown signature bit.

<FIG> shows an example scenario where the embodiment of <FIG> could be used, where a transmitter <NUM> (Alice's UE) has data <NUM> targeted for reception by a first receiver <NUM> (Bob's UE) and wants only some of the data <NUM> to be decoded by a second receiver <NUM> (Carol's UE) such that the rest of the data <NUM> can only be decoded by the first receiver <NUM>. By informing a targeted receiver (Bob's UE in the example of <FIG>) of the all the signature bits, the targeted receiver can decode all of the data <NUM>. By only informing a receiver (Carol's UE in the example of <FIG>) of only the first signature, the receiver can only decode the first part <NUM> of the data <NUM>.

The multiple signature approach can be readily extended to accommodate P>=<NUM> information blocks, by generating an input vector with P portions, each containing respective signature bits, one of the information blocks with at least one frozen bit inserted, and a CRC over the information block.

A specific example of an encoder that uses signatures is depicted in <FIG>, where N=<NUM>, K1=<NUM>, u1=<NUM>, M1=<NUM>, and K2=<NUM>, u2=<NUM> and M2=<NUM>. For the first information block, bits <NUM>,<NUM>,<NUM> contain the M1-bit first signature. Bits <NUM>,<NUM>,<NUM> contain the K1 information bits. Bits <NUM> and <NUM> contain the u1 CRC bits, and bit <NUM> is a frozen bit. For the second information block, bit <NUM> contains the M2-bit second signature. Bits <NUM>,<NUM>,<NUM> contain the K2 information bits. Bits <NUM> and <NUM> contain the u2 CRC bits, and bit <NUM> is a frozen bit.

Advantages of the CRC-checked signature-enabled Polar code that may be realized in some implementations include:.

A CRC-checked signature-enabled polar code can be completely specified by the eight-tuple (N, K, F, vF, S, vS, C, vC), where:.

In the above, the K + C bit positions correspond to reliable bit positions for the polar code, and the Nf + Nc bit positions correspond to unreliable bit positions for the polar code. An implementation without CRC is achieved by using all of the reliable bit positions as information bits. An implementation without frozen bits is achieved by using all of the unreliable bit positions as signature bits, although it should be noted that the signature bits function the same as frozen bits; the difference is that not all receivers are aware of the signature bits.

Given any subset of indices A from a vector x, the corresponding subvector is denoted as xA.

For a (N, K, F, vF, S, vS, C, vC ) polar code, the encoding operation for a vector of information bits u of length K will now be described. Let m = log2 (N) and G= F ⊗n = F ⊗ · · · ⊗ F be the m-fold Kronecker product of a seed matrix F, Where F is <MAT>.

In polar codes that are not signature enabled, the choice of the set F of frozen bit positions (i.e. the unreliable bit positions) is a step in polar coding often referred to as polar code construction. See, for example, Arikan's paper, referred to previously. More generally, any method of choosing a set of polar code noisy bit positions can be used instead to choose a set of positions that will be used for signature bits, or signature bits and frozen bits. As noted previously, in some cases, all frozen bit positions are used for signature bits. This application is not limited to specific frozen bit position/signature bit positions. However, within the set of positions thus chosen, a give signature bit needs to be included before information bits associated with the given signature bit. In addition, CRC bits, when included, are placed in polar code reliable bit positions. The Kronecker product matrix based on the specific seed matrix referred to above is a specific example of a Polar code generator matrix. More generally, any Polar code generator matrix can be employed that produces codewords with reliable and unreliable positions. In some embodiments, a Polar code generator matrix is based on a Kronecker product matrix of a different seed matrix. For example, the seed matrix may be a prime-number dimensions matrix, such as 3x3 or 5x5. The seed matrix may be binary or non-binary.

More generally, any method of encoding that is mathematically equivalent with the described methods can be employed. For example, once a set of codewords is determined as described herein, many different encoder structures known in the art can be used to encode input data to produce codewords. Typically the encoder described herein is included as part of an apparatus that includes other components. These might, for example, include a modulator that modulates bits output by the encoder to produce symbols, and a transmitter that transmits the symbols over a channel such as a wireless channel. Similar reverse functionality would be in the receiver together with the decoder.

<FIG> is a block diagram of an apparatus for receiving and decoding codewords. The apparatus <NUM> includes a receiver <NUM> coupled to an antenna <NUM> for receiving signals from a wireless channel, and a decoder <NUM>. Memory <NUM> is coupled to the decoder <NUM>. In some embodiments, the receiver <NUM> includes a demodulator, an amplifier, and/or other components of an RF receive chain. The receiver <NUM> receives, via the antenna <NUM>, a word that is based on a codeword of a polar code. Decoded bits are output at <NUM> for further receive processing.

The decoder <NUM> is implemented in circuitry, such as a processor, that is configured to estimate bits in the received word as disclosed herein. The memory <NUM> could include one or more solid-state memory devices and/or memory devices with movable and possibly removable storage media. In a processor-based implementation of the decoder <NUM>, processor-executable instructions to configure a processor to perform decoding operations are stored in a non-transitory processor-readable medium. The non-transitory medium could include the same memory device(s) used for the memory <NUM>, or one or more separate memory devices. The decoding method of <FIG> represents one possible implementation of the decoder <NUM> and the memory <NUM>.

The memory <NUM> could be used to store results of processing by the processing elements of the decoder <NUM>. The decoder <NUM> could also include an address multiplexer coupled between the processing elements and the memory <NUM>. In an embodiment, the decoder <NUM> is configured to store the results of the processing by the processing elements to respective memory areas in the memory <NUM> that are each accessible to provide, in a single memory access operation, inputs to each of the processing elements for subsequent computations. Other embodiments may include further, fewer, or different components and/or variations in operation of receiving apparatus components.

In a specific example, the decoder <NUM> includes a polar code decoder <NUM> configured to perform to polar code decoding of the received codeword by treating at least one signature bit as a frozen bit having a known signature bit value. The apparatus may be configured to receive information on signature bits used in the signature-enabled polar code separately from receiving the codeword. Where CRC is employed, the decoder <NUM> includes a CRC checker <NUM> configured to verify a result of decoding using a CRC check.

<FIG> is a block diagram of an example apparatus for encoding and transmitting codewords. The apparatus <NUM> includes an encoder <NUM> coupled to a transmitter <NUM>. The encoder <NUM> is implemented in circuitry that is configured to encode an input bit stream <NUM> using a signature-enabled polar code, or a CRC-checked signature-enabled polar code. In the illustrated embodiment, the apparatus <NUM> also includes an antenna <NUM>, coupled to the transmitter <NUM>, for transmitting signals over a wireless channel. In some embodiments, the transmitter <NUM> includes a modulator, an amplifier, and/or other components of an RF transmit chain.

In some embodiments, the apparatus <NUM>, and similarly the apparatus <NUM> in FIG. <NUM>, include a non-transitory computer readable medium that includes instructions for execution by a processor to implement and/or control operation of the encoder <NUM> in FIG. <NUM>, to implement and/or control operation of the decoder <NUM> in FIG. <NUM>, and/or to otherwise control the execution of methods described herein. In some embodiments, the processor may be a component of a general-purpose computer hardware platform. In other embodiments, the processor may be a component of a special-purpose hardware platform. For example, the processor may be an embedded processor, and the instructions may be provided as firmware. Some embodiments may be implemented by using hardware only. In some embodiments, the instructions for execution by a processor may be embodied in the form of a software product. The software product may be stored in a non-volatile or non-transitory storage medium, which could be, for example, a compact disc read-only memory (CD-ROM), universal serial bus (USB) flash disk, or a removable hard disk.

Communication equipment could include the apparatus <NUM>, the apparatus <NUM>, or both a transmitter and a receiver and both an encoder and a decoder. Such communication equipment could be user equipment or communication network equipment. In a specific example, the encoder <NUM> includes an input vector generator <NUM> configured to produce an N-bit input vector for polar encoding, the input vector having polar code reliable bit positions and polar code unreliable bit positions by inserting each of at least one information bit in a respective polar code reliable bit position, and each of at least one signature bit in a respective polar code unreliable bit position, where N = <NUM>m where m>=<NUM>. The encoder <NUM> also includes a polar code encoder <NUM> configured to multiply the input vector by a polar code generator matrix to produce a signature-enabled polar codeword. The transmitter <NUM> transmits the signature-enabled polar codeword. In addition, or alternatively, there may be a memory (not shown) for storing the signature-enabled polar codeword.

In embodiments that include the CRC, the apparatus also includes a CRC processor <NUM> configured to process the K information bits to produce a u-bit CRC, where u >=<NUM>. In this case, the input vector generator <NUM> produces the N-bit input vector by inserting each of the u CRC bits in a respective polar code reliable bit position.

In some embodiments, the input vector producer uses the multiple signature approach described previously, with or without CRC.

Claim 1:
A method for a transmitter device for transmitting information bits, the method comprising:
producing (<NUM>) an input vector for polar encoding, the input vector having bit positions with respective reliabilities, and the input vector including information bits, frozen bits, and one or more signature bits, wherein each bit of the one or more signature bits is in a respective bit position in the input vector that has a lower reliability than a reliability of bit positions in the input vector for the information bits;
polar encoding (<NUM>) the input vector to produce a polar code codeword;
transmitting (<NUM>) the polar code codeword to at least one receiver device; and
transmitting the one or more signature bits to the at least one receiver device separately from transmitting the codeword, such that a respective value of the one or more signature bits is known to the at least one receiver device.