Patent Description:
In a communication system, information is transmitted from a transmitter, over a channel, to a receiver. For example, in a wireless communication system, a transmitter in a mobile device may transmit information over a wireless channel to a receiver in a base station.

The channel may introduce errors into the information transmitted over the channel. Error control coding may be used to detect and/or correct the errors. For example, k bits of information to be transmitted from a transmitter to a receiver may first be encoded by an encoder in the transmitter to obtain a codeword having a length of Nb bits, where Nb > k. The codeword may then be transmitted over the channel. The received codeword is then decoded by a decoder in the receiver to obtain a decision as to which k bits were transmitted. The redundancy added by transmitting a codeword of bit length Nb > k increases the probability that the k bits are correctly decoded at the receiver, even if some errors were introduced into the codeword by the noise in the channel.

There are different types of error detecting and correcting codes. One type of error correcting code, referred to as an Arikan polar code, is disclosed in the paper "<NPL>). The Arikan polar code is a binary polar code, which means that the Arikan polar code only performs error control coding on a binary symbol alphabet. The k bits that are encoded using the Arkian polar code represent k information symbols. Each one of the k information symbols can only take on one of two values.

Also, the bit length Nb of each codeword in the Arikan polar code must be a power of two, i.e. Nb = <NUM>n, where n is a natural number. However, due to the coding rate requirement, the codeword length that can be actually transmitted into the channel may not be exactly the bit length Nb = <NUM>n.

The subject matter of the present invention is defined by the appended claims.

General polar codes are disclosed that encode symbols of a q-ary alphabet, where q ≥ <NUM>. Systems and methods are disclosed for performing code rate matching when using general polar codes.

Embodiments and examples will be described with reference to the accompanying figures wherein:.

For illustrative purposes, specific example embodiments will now be explained in greater detail below in conjunction with the figures.

<FIG> is a block diagram of a communication system <NUM> according to one embodiment. The communication system <NUM> includes a transmitter <NUM> and a receiver <NUM> that communicate over a channel <NUM>. The transmitter <NUM> includes a polar encoder <NUM> and the receiver <NUM> includes a polar decoder <NUM>.

The polar encoder <NUM>, as well as other data/signal processing functions of the transmitter <NUM>, e.g. the puncturer described later, may be implemented by a processor that executes instructions to cause the processor to perform some or all of the operations of the polar encoder <NUM> and transmitter <NUM>. Alternatively, the polar encoder <NUM>, as well as the other data/signal processing functions of the transmitter <NUM>, may be implemented in hardware or circuitry (e.g. in one or more chipsets, microprocessors, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), dedicated circuitry, or combinations thereof) and configured to implement the operations of the polar encoder <NUM> and transmitter <NUM>. Although not shown, the transmitter <NUM> could include a modulator, an amplifier, antenna and/or other modules or components of a transmit chain or alternatively could be configured to interface with a separate (Radio-Frequency - RF) transmission module so that codewords may be produced as described herein and transmitted directly or by a separate transmission unit or module. The transmitter <NUM> may also include a non-transitory computer readable medium (not shown), that includes instructions for execution (e.g. by a processor or some other circuitry as described above) to implement and/or control operation of the polar encoder <NUM> and transmitter <NUM>, and/or to otherwise control the execution of functionality and/or embodiments described herein. 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 or memory, which could be, for example, a compact disc read-only memory (CD-ROM), universal serial bus (USB) flash disk, or a removable hard disk.

Similarly, the polar decoder <NUM>, as well as other data/signal processing functions of the receiver <NUM>, may be implemented by a processor that that executes instructions to cause the processor to perform some or all of the operations of the polar decoder <NUM> and receiver <NUM>. Alternatively, the polar decoder <NUM>, as well as the other data/signal processing functions of the receiver <NUM>, may be implemented in hardware or circuitry (e.g. in one or more chipsets, microprocessors, ASICs, FPGAs, dedicated circuitry, or combinations thereof) and configured to implement some or all of the operations of the polar decoder <NUM> and receiver <NUM>. Although not shown, the receiver <NUM> could include an antenna, demodulator, amplifier, and/or other modules or components of a receive chain or alternatively could be configured to interface with a separate (Radio-Frequency - RF) receiving module to process and/or decode words based on codewords of a polar code received by the receiver <NUM> directly or indirectly from a separate receiving unit or module. The receiver <NUM> may also include a non-transitory computer readable medium (not shown), that includes instructions for execution (e.g. by a processor or some other circuitry as described above) to implement and/or control operation of the polar decoder <NUM> and receiver <NUM>, and/or to otherwise control the execution of functionality and/or embodiments described herein. 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 or memory, which could be, for example, a CD-ROM, USB flash disk, or a removable hard disk.

In operation, the polar encoder <NUM> encodes a group of m bits to obtain a corresponding codeword x that has a codeword length equal to Nb bits, where Nb > m. Although the polar encoder <NUM> receives bits, in the polar encoder <NUM> the bits represent symbols of a q-ary alphabet. The use of the word "symbols" is not meant to refer to symbols in a modulation constellation, but is meant to refer to elements of a q-ary alphabet. For example, a <NUM>-ary alphabet may have four symbols denoted using the notation "<NUM>", "<NUM>", "<NUM>", and "<NUM>", and respectively represented by bits <NUM>, <NUM>, <NUM>, and <NUM>.

The codeword x output by the polar encoder <NUM> is transmitted over the channel <NUM> and received at the polar decoder <NUM> of the receiver <NUM>. The polar decoder <NUM> performs decoding to make a decision as to which group of m bits was transmitted. The decoding is considered successful if the m bits decoded by the polar decoder <NUM> match the m bits originally transmitted. If the channel <NUM> is noisy and introduces too many errors into the codeword x, then the polar decoding may not be able to correct all of the errors.

A polar code may be generated using a Kronecker product matrix G that is produced from a seed matrix Gs. For a binary polar code, each information symbol is a bit, and a seed matrix Gs = G<NUM> may be used, where <MAT>.

<FIG> shows how a Kronecker product matrix can be produced from the seed matrix G<NUM>. Shown in <FIG> is a <NUM>-fold Kronecker product matrix G<NUM> ⊗<NUM> <NUM> and a <NUM>-fold Kronecker product matrix G<NUM> ⊗<NUM> <NUM>. The Kronecker product approach can be iterated to produce an n-fold Kronecker product matrix G<NUM> ⊗n. For a binary polar code having codewords of length N = <NUM>n, the Kronecker product matrix G is the generator matrix for the polar code, and is equal to G = G<NUM> ⊗n.

<FIG> is a flowchart illustrating how a codeword is generated using a binary polar code. One specific example is shown in stippled bubbles for a binary polar code having codewords of bit length Nb = <NUM>, i.e., a binary polar code having the generator matrix G = G<NUM> ⊗<NUM>. In step <NUM>, k information bits that are to be transmitted to the receiver <NUM> are obtained. In the example, k = <NUM> bits labelled b<NUM>b<NUM>b<NUM>b<NUM>. Optionally, in step <NUM>, assistant or error-detecting code (EDC) bits, such as cyclic redundancy check (CRC) bits, are added to the k bits (to result in m information bits) to assist in decoding. It is understood that more than one EDC could be used within one codeword. It should also be understood that other types of EDCs may be used instead or in addition, such as checksum codes, Fletcher codes, hash codes or other parity check codes. Some EDCs may also be used as Error-Correction Codes (ECCs) and may be used in path selection for List decoding, for example, to improve polar code performance.

CRC bits, for example, are generated based on the k information bits and generally placed in more reliable positions in the input vector. However, depending on their intended purpose (e.g. used for error detection or error correction or both), the CRC bits may also or instead be distributed or otherwise placed in other positions in the input vector. In this example, starting with the k information bits, a CRC is calculated and appended to the k information bits to produce the m information bits that includes the k information bits and the CRC bits.

In the example of <FIG>, no EDC bits are added in step <NUM>, and therefore k = m. The m bits are input into the polar encoder <NUM>. In step <NUM>, the polar encoder <NUM> forms an input vector u = [u<NUM> u<NUM> u<NUM>. uNb] that is Nb bits long by mapping each one of the m bits to a respective one of the Nb positions in the input vector u, and then by placing "frozen" bits in the remaining positions of the input vector u. The value and position of the frozen bits are known to both the polar encoder <NUM> and the polar decoder <NUM>. According to the channel polarization theory behind polar code construction, some positions of the input vector u will have a higher reliability of being correctly decoded than other positions of the input vector u. In polar code construction, an attempt is made to put the m bits in the more reliable positions of the input vector u, and to put frozen bits in the more unreliable positions of the input vector u. In the example in <FIG>, Nb = <NUM>, and positions u<NUM>, u<NUM>, u<NUM>, and u<NUM> are the more reliable positions of the input vector u. Therefore, the m bits are placed in positions u<NUM>, u<NUM>, u<NUM>, and u<NUM>. The frozen bits each have the value zero, although more generally the frozen bits can be set to another value known to both the polar encoder <NUM> and the polar decoder <NUM>.

In step <NUM>, the input vector u is then multiplied by the generator matrix G to obtain the codeword x = [x<NUM> x<NUM> x<NUM>. In the example in <FIG>, x = uG<NUM> ⊗<NUM>.

The polar encoder <NUM> may use kernels to implement the multiplication of the input vector u with the generator G, e.g. to implement step <NUM> of <FIG> is a schematic of a kernel <NUM> for implementing a multiplication of inputs [u v] by seed matrix <MAT>. The seed matrix for a kernel is sometimes instead referred to as a kernel generator matrix. The kernel <NUM> is a binary kernel, and specifically the Arikan binary kernel. Other types of binary kernels are possible. The Arikan binary kernel <NUM> receives the two inputs u and v, and outputs u + v and v , which represent the output of the multiplication <MAT>. The circle plus symbol represents modulo <NUM> addition.

<FIG> is a schematic of an example structure for implementing the example in step <NUM> of <FIG>, i.e. the matrix multiplication x = [x<NUM> x<NUM> x<NUM>. xNb] = uG<NUM> ⊗<NUM>. Each kernel <NUM> in <FIG> is the same as that illustrated in <FIG>, and is therefore designated using the same reference number <NUM>. Each kernel is also indicated by the letter "A" in <FIG> since it is the Arikan binary kernel. Three encoding layers are used, labelled L<NUM>, L<NUM>, and L<NUM>, with each encoding layer having four binary kernels. An encoding layer may also be called an encoding stage.

Polar coding may be performed with or without bit reversal. The example structure of <FIG> does not have bit reversal. Another example structure for implementing step <NUM> is shown in <FIG>. The example in <FIG> implements bit reversal. Generally, the output of a polar encoder can be expressed as <MAT>, where, without bit reversal, GN = F⊗n is an N-by-N generator matrix, N = <NUM>n, n ≥ <NUM>. For example, for n = <NUM>, G<NUM> = F. For bit reversal, GN = BNF⊗n, where BN is an N-by-N bit-reversal permutation matrix.

The binary polar codes described above based on seed matrix <MAT> are limited to a binary symbol alphabet. A general polar code may be constructed that encodes symbols of an q-ary alphabet, where q ≥ <NUM>. An input vector u is encoded using a generator matrix G to result in a codeword x. The input vector u has m information symbols, with each information symbol being represented using log<NUM>q information bits. The remaining positions of the input vector u are frozen, i.e. known to both the polar encoder <NUM> and polar decoder <NUM>. Multiplication of the input vector u with the generator matrix G may be implemented using kernel layers, where each kernel performs finite field operations in a Galois field GF(q) in order to implement multiplication with the seed matrix Gs of the generator matrix G. An example general kernel <NUM> is illustrated in <FIG>. The kernel <NUM> implements the operation x = uGs, where u = [u<NUM> u<NUM>. uq-<NUM> uq] and x = [x<NUM> x<NUM>. xq-<NUM> xq]. Both u and x are vectors of symbols, each symbol represented by log<NUM>q bits. A binary kernel is a special case of the general kernel <NUM> for q = <NUM>.

For example, a general polar code may be defined that encodes <NUM>-ary symbols, i.e. q = <NUM>. Each input symbol is one of four possible values, which are respectively represented using the notation <NUM>, <NUM>, ∝, and ∝<NUM>. Two bits are used in implementation to represent each possible symbol value: <NUM>, <NUM>, <NUM>, and <NUM>. The following is one example of a seed matrix Gs that may be used: <MAT> where the following finite field operations are defined: <NUM> + ∝=∝<NUM>, <NUM> + ∝<NUM>=∝, <NUM> + <NUM> = <NUM>, ∝ +<NUM> =∝, ∝<NUM> + <NUM> =∝<NUM>, ∝ +∝<NUM> = <NUM>, <NUM> + <NUM> = <NUM>, oc +∝= <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> =∝, and <NUM> × <NUM> = <NUM>. The corresponding kernel will be referred to as a Reed-Solomon (RS) based kernel and is illustrated in <FIG> using reference number <NUM>. The notation "RS(<NUM>)" is used to indicate that the kernel <NUM> is an RS based kernel for encoding <NUM>-ary symbols. More generally an "RS(q)" kernel is an RS based kernel for encoding q-ary symbols. An RS based kernel may have performance advantages, some of which will be described below in further detail. Non-binary RS kernels are only one example. Other non-binary kernels may be used, e.g. a Hermitian kernel.

The codeword length for <NUM>-ary symbols is restricted to Nb = <NUM> × <NUM>n bits, where n is a natural number.

<FIG> is a schematic of an RS(<NUM>) polar encoder structures for n = <NUM>, i.e. <NUM> symbols. The codeword length is Nb =<NUM> × <NUM> = <NUM> bits because each <NUM>-ary symbol is represented by <NUM> bits. Two encoding layers L<NUM> and L<NUM> are used, with each encoding layer having four RS(<NUM>) kernels. Each RS(<NUM>) kernel accepts four <NUM>-ary symbols, i.e. <NUM> bits, as an input and produces an output of four <NUM>-ary symbols, i.e. <NUM> bits. Similar to the polar encoder structure with binary kernel, an RS(<NUM>) polar encoder structure can either have symbol index permutation or not. <FIG> illustrates the structure with symbol index permutation. <FIG> illustrates the structure without symbol index permutation. For the structure with symbol index permutation (<FIG>), the generator matrix is a permutation matrix times the generator matrix of the encoding structure without symbol index permutation. Embodiments disclosed herein could be implemented with or without symbol index permutation.

For an <NUM>-ary alphabet, a kernel would implement the matrix multiplication x = uGs, where u is an input vector of eight symbols and Gs is an <NUM> × <NUM> seed matrix. Finite field operations in a Galois field GF(<NUM>) would be performed. Therefore, the input of the kernel would be eight <NUM>-ary symbols, i.e. <NUM> bits because three bits are used to represent each input symbol. The output of the kernel would be eight <NUM>-ary symbols, i.e. again <NUM> bits.

In general, the polar encoder <NUM> may be constructed to generate a codeword x of length Nb bits by implementing x = uG, where x and u both represent a respective vector of q-ary symbols. Each vector x and u has symbol length Ns = qn, which corresponds to a bit length Nb = log<NUM>q × qn. Each of n encoding layers has qn-<NUM> kernels, and each kernel has q inputs and q outputs.

The following are possible benefits of using a non-binary general polar code, such as an RS based code. With the same codeword length, a lower frame error rate (FER) for a given list size in the decoder may be achieved, or a smaller list size in the decoder for a given FER may be achieved. Using a smaller list size may reduce implementation complexity and increase the decoding throughput, e.g. by having less list-related memory for copying, moving, and sorting.

A coding rate R is defined as R = kb/Nb, where kb is the number of information bits, and Nb is the bit length of the generated codeword corresponding to the kb information bits. When the transmitter <NUM> is to transmit kb bits to the receiver <NUM>, the transmitter <NUM> may be required to use a particular coding rate R / code length, which may change over time, e.g. based on the available network resources, such as bandwidth.

A polar code places a restriction on the values of Nb. For example, when performing polar encoding using only binary kernels, the codeword length in bits, Nb, is restricted to a power of two: Nb = <NUM>n bits. The following table summarizes the codeword length Nb, and the corresponding number of encoding layers, n, for different values of n, up to n = <NUM>:.

As another example, when performing polar encoding using only RS(<NUM>) kernels, the codeword length Nb is restricted to Nb = <NUM> × <NUM>n bits. The following table summarizes the codeword length Nb, and the corresponding number of encoding layers, n, for different values of n, up to n = <NUM>:.

If the transmitter <NUM> is to transmit at a coding rate R, and the transmitter <NUM> has kb bits to transmit, then the codeword length, in bits, used by the polar encoder <NUM> should ideally be Nb = kb/R. However, the restriction on Nb due to using a polar code may not allow for a value of Nb that is exactly equal to Nb = kb/R. For example, when performing polar encoding using only binary kernels, then Nb is limited to a power of two. If the transmitter <NUM> has kb = <NUM> bits to transmit and the coding rate R the transmitter <NUM> must use is R = <NUM>/<NUM>, then ideally <MAT> bits. However, a codeword length of exactly Nb =<NUM> bits cannot be generated using binary kernels. Therefore, the transmitter <NUM> performs rate matching by padding (lengthening) or puncturing (shortening) the codeword to have exactly M = <NUM> bits. Rate matching is therefore performed by length matching, that is, modifying the length of the codeword so that the coding rate is satisfied.

<FIG> illustrates the communication system <NUM> of <FIG> according to another aspect. The transmitter <NUM> further includes a puncturer <NUM>. The polar encoder <NUM> specifically includes an input vector former <NUM>, an information sequence generator <NUM>, and one or more kernel layers <NUM>. The transmitter <NUM> may also include a non-transitory computer readable medium (not shown), that includes instructions for execution (e.g. by a processor or some other circuitry as described above) to implement and/or control operation of the polar encoder <NUM>, and/or the puncturer <NUM>, and/or the transmitter <NUM>, and/or to otherwise control the execution of functionality and/or embodiments described herein. 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 or memory, which could be, for example, a CD-ROM, USB flash disk, or a removable hard disk.

The polar decoder <NUM> in the receiver <NUM> specifically includes a bit log-likelihood ratio (LLR) computer <NUM>, a bit LLR to symbol LLR converter <NUM>, and a decoder <NUM>. The receiver <NUM> may also include a non-transitory computer readable medium (not shown), that includes instructions for execution (e.g. by a processor or some other circuitry as described above) to implement and/or control operation of the polar decoder <NUM> and receiver <NUM>, and/or to otherwise control the execution of functionality and/or embodiments described herein. 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 or memory, which could be, for example, a CD-ROM, USB flash disk, or a removable hard disk.

<FIG> would or may include other components not illustrated, such as a modulator in the transmitter <NUM> and a demodulator in the receiver <NUM>. Modulation and corresponding demodulation may be used to enable computing LLRs. Additional components in the transmitter <NUM> may also include an amplifier, antenna and/or other modules or components of a transmit chain or alternatively the transmitter <NUM> could be configured to interface with a separate (RF) transmission module so that codewords may be produced as described herein and transmitted directly or by a separate transmission unit or module. Additional components in the receiver <NUM> may include an antenna, amplifier, and/or other modules or components of a receive chain or alternatively could be configured to interface with a separate (RF) receiving module to process and/or decode words based on codewords of a polar code received by the receiver <NUM> directly or indirectly from a separate receiving unit or module.

In operation, kb bits are received at the polar encoder <NUM>. The input vector former <NUM> maps the kb bits to certain positions of an input vector u. The remaining positions of the input vector u are set as frozen positions. An information sequence <NUM> indicates which positions of the input vector u are to receive each of the kb bits and which positions of the input vector u are to receive frozen values. The information sequence <NUM> is generated by the information sequence generator <NUM> (either generated on-line or read from memory) based on factors such as the coding rate R the transmitter <NUM> is to use to transmit the kb bits, and the noise of the channel <NUM> or a predefined working SNR that is based on the coding rate and coding length. The information sequence generator <NUM> generates the information sequence <NUM> such that an attempt is made to put the kb bits in the more reliable positions of the input vector u and the frozen values in the less reliable positions of the input vector u.

As is known, an ordered sequence such as the information sequence <NUM> is representative of the relative "reliability" of the sub-channels, where a sub-channel refers to a synthesized channel after the polarization process. In other words, some sub-channels have high capacity, and some sub-channels have low capacity. Put another way, some sub-channels have high Signal-to-Noise Ratio (SNR) and others have low SNR. These metrics are examples of characteristics that could be used to quantify or classify sub-channel "reliability". Other metrics indicative of sub-channel reliability can also be used. Sub-channel selection is based on reliabilities of the sub-channels, and typically the highest reliability sub-channels are selected as information sub-channels for carrying information bits.

For general polar codes, the information sequence <NUM> could be either a sequence of symbol positions or a sequence of bit positions. For a codeword of Nb bits using q-ary kernels, the full length of a sequence of symbol positions is Nb/log<NUM>(q); while that of a sequence of bit positions is Nb. Take RS(<NUM>) polar codes as an example. For a sequence of symbol positions, the positions for putting the information bits are selected in terms of symbols, that is, the neighboring <NUM> bits representing one symbol to be encoded should be either both information bits or both frozen bits; while for a sequence of bit positions, the neighboring two bits representing one symbol can accommodate zero, one, or two information bits. In some embodiments, using a sequence of symbol positions may have a better error correction performance than using a sequence of bit positions, at least under Genie-aided sequence generation methods. This is attributed to that using a sequence of symbol positions may better exploit the polarization gains when symbol-based kernels are used. A sequence of symbol positions is actually a special case of a sequence of bit positions, in the sense that a sequence of symbol positions is equivalent to a sequence of bit positions with a constraint that the neighboring two bit positions <NUM>*i and <NUM>*i+<NUM> (<NUM>≤i<Nb/<NUM>) should be either both information bit positions or frozen bit positions. Therefore, for the sake of generality, the information sequence in the following texts refers all to the sequence of bit positions.

A single, nested, SNR-independent ordered sequence <NUM> of sub-channels could be computed for a code length Nmax, with ordered sequences for shorter code lengths N being selected from the longer Nmax sequence. Multiple ordered sequences in terms of different mother code lengths N; could instead be computed, and one of the mother code length sequences could be selected for a particular code based on preferred code length. Another possible option involves computing multiple ordered sequences in terms of SNR values, for example, and selecting an ordered sequence based on the measured SNR.

The information sequence generator <NUM> can perform ordered sequence computations in a number of different ways. For example, the computations could be performed online, producing an ordered sequence that can be dynamically adjusted or recomputed based on, for example, observed channel conditions. The computations may alternatively be performed offline (e.g. in advance) to produce pre-computed (and static) ordered sequences that can be stored and retrieved or read from memory during subsequent coding operations. In yet another alternative, the computations may be performed partially online and partially offline.

The input vector u that is output from the input vector former <NUM> is encoded by the one or more kernel layers <NUM>, each kernel layer having at least one kernel, to result in a corresponding codeword x of length Nb bits. The input vector u should be transformed into a vector of q-ary symbols (denoted as us) before being operated with the kernel layers, and the codeword x of Nb bits should be transformed from an output vector of q-ary symbols (denoted as xs). The one or more kernel layers <NUM> implement the operation xs = usG. Although xs and us are symbols, they are still represented by bits in the hardware.

The polar encoder <NUM> implements a polar code in which Nb exceeds the number of bits M = kb/R that can actually be transmitted based on the coding rate R. The codeword x of length Nb bits is therefore punctured by the puncturer <NUM> to remove bits, according to a puncturing pattern <NUM>, in order to result in M bits. The M bits are then transmitted over the channel <NUM>. "Puncturing" as used herein refers to removing bits from the codeword. When puncturing is performed, the codeword has its length reduced. The word "shortening" is sometimes used to refer to the specific situation in which each bit removed from the codeword has a value that is known by the decoder, e.g. which may be the case if the bits removed from the codeword are a linear combination of frozen bits. "Puncturing", as used herein, encompasses both "shortening", as well as other implementations in which one, some, or all bits removed from the codeword each have a value that is not known by the decoder. Any pattern that indicates which bit(s) to remove from a codeword is referred to as a puncturing pattern. A puncturing pattern encompasses shortening patterns which shorten a subset of positions of a codeword to a reduced length. Puncturing pattern also encompasses other types of patterns that puncture bits but that are not shortening patterns.

The received signal carrying the M bits is processed at the polar decoder <NUM>. The bit LLR computer <NUM> first computes the bit LLR for each one of the M bits. Depuncturing is then performed by setting the bit LLR for each one of the punctured bits to zero, as shown at <NUM>. The bit LLR to symbol LLR converter <NUM> then converts the bit LLRs to corresponding symbol LLRs for the symbols represented by the Nb bits. If the polar encoding <NUM> only uses binary kernels, then each bit represents a symbol and therefore the each bit LLR is a symbol LLR, and bit LLR to symbol LLR conversion is not required. The symbol LLR values are then processed by the decoder <NUM> to generate a decision as to which kb bits were transmitted. An example decoding algorithm implemented by the decoder <NUM> is symbol-based successive cancellation (SC) or successive cancellation list (SCL) decoding. <FIG> illustrates one example of the decoder <NUM> for a <NUM> bit codeword generated using <NUM> layers of RS(<NUM>) kernels with symbol index permutation, and where the first <NUM> bits of the codeword have been punctured. Depuncturing is performed by setting the bit LLR values to zero for each of <NUM> punctured bits, as shown at <NUM>. <FIG> illustrates another example of decoder <NUM>, where the same puncturing pattern (i.e., puncturing the first <NUM> bits of the codeword) also applies to the decoder using RS(<NUM>) kernel layers, but without symbol index permutation.

Returning to <FIG>, the puncturing pattern <NUM> is used to puncture the bits of the codeword x so that the Nb bits of the codeword x are reduced to M < Nb bits. The puncturing pattern <NUM> indicates which bits should be punctured, i.e. specifically which bits of the codeword x should be removed. When a general polar code is used that encodes symbols of a q-ary alphabet, where q > <NUM>, then the puncturing must take into account that fact that groups of bits represent different symbols.

The decision as to which puncturing pattern <NUM> and information sequence <NUM> to use is mutually dependent. One approach is to obtain the optimal puncturing pattern <NUM> given a fixed information sequence <NUM>. For example, first determine the information sequence <NUM>, and then given the frozen positions indicated in the information sequence <NUM> (i.e. the "frozen set"), generate an optimal puncturing pattern <NUM>. As an example, the information sequence <NUM> may indicate to place the kb bits in the last kb bit positions in the input vector u because the information sequence generator <NUM> has determined that the last kb bit positions in the input vector u are the most reliable positions given the noise in the channel and the coding rate R. The puncturing pattern <NUM> may then be computed based on this specific information sequence <NUM> in order to try to puncture bits in the codeword x that best correspond to the frozen values.

An alternative method is to first choose the puncturing pattern <NUM> and then, based on the puncturing pattern <NUM>, generate an optimal information sequence <NUM>. For example, for a given puncturing pattern <NUM>, the frozen set, i.e., the frozen positions in the information sequence <NUM>, may be optimized. The optimal frozen set may be determined using a density evolution method via Gaussian Approximation or Gene-aided methods using simulations. When the optimal frozen set is determined based on the chosen puncturing pattern, then the information sequence generator <NUM> is modified to not only generate the information sequence <NUM> based on, for example, the channel noise (or working SNR) and coding rate R, but also generate the information sequence <NUM> based on the selected puncturing pattern <NUM>. According to the invention as defined in the appended claims, the puncturing pattern <NUM> is selected to simply puncture the first P = Nb - M bits of the codeword x. An optimal information sequence <NUM> is then generated by the information sequence generator <NUM> in order to determine the frozen positions in the input vector u as the positions that best correspond to the punctured bits in the codeword x.

Alternatively, a joint optimization method may be performed in which the information sequence <NUM> and the puncturing pattern <NUM> are generated together in order to jointly optimize the information sequence <NUM> and the puncturing pattern <NUM>. An exhaustive search or smart reduction of the search space may be performed when doing the joint optimization.

<FIG> illustrates FER curves for CRC-aided SCL polar decoding in which Nb = <NUM> bits, kb = <NUM> bits, and R = <NUM>/<NUM>. Therefore, M = <NUM> bits, and so <NUM> bits are punctured. The frozen positions of the information sequence are optimized based on the puncturing pattern. For SC decoding with list size L = <NUM>, the performance gain of using RS(<NUM>) kernels over Arikan kernels is <NUM>. 45dB at FER = <NUM>, and <NUM>. 5dB at FER = <NUM>. For SCL decoding with list size L = <NUM>, the performance gain is <NUM>. 15dB at FER = <NUM>, and <NUM>. 17dB at FER = <NUM>.

<FIG> is a flow chart of an embodiment of a method performed by the transmitter <NUM>, in which the puncturing pattern <NUM> is first selected and then the information sequence <NUM> is generated. In step <NUM>, the transmitter <NUM> determines the bit length M that is to be transmitted over the channel <NUM>. For example, the bit length M may be computed as M = kb/R. In step <NUM>, the transmitter <NUM> generates or determines the puncturing pattern <NUM> by constructing a puncturing pattern that punctures the first P = Nb - M bits of the codeword x.

In step <NUM>, puncturing the first P = Nb - M bits is performed according to the invention as defined in the appended claims. Another set of P = Nb - M bits may be punctured (e.g. shortened) instead according to another puncturing pattern not falling within the scope of the appended claims. The puncturing pattern in step <NUM> may include the shortening patterns that determine which subset of codeword bits to be shortened to a reduced length. In some examples, the puncturing pattern may be generated or determined considering other parameters in addition to M, e. g, the information block length K and/or coding rate R. For instance, for better error correction performance, puncturing the first Nb - M may be adopted for low and medium coding rates R, while block-based shortening or Bit Reversal (BIV) shortening may be used for high coding rates R. In other examples, the puncturing pattern <NUM> may be determined by selecting a puncturing pattern (e.g. based on one or more of the above-noted parameters) from a plurality of available puncturing patterns. In step <NUM>, the transmitter <NUM> then sends or otherwise makes available the puncturing pattern determined to the information sequence generator <NUM>. Alternatively, the information sequence generator <NUM> may independently obtain the puncturing pattern <NUM> determined. In step <NUM>, the information sequence generator <NUM> generates the information sequence <NUM> based in part on the puncturing pattern <NUM>.

In some embodiments, step <NUM> involves computing the information sequence <NUM> for each codeword x using the puncturing pattern <NUM> for that codeword x and some or all of the following additional parameters: (i) the length of the input vector u, which is equal to Nb bits; (ii) the number of information bits kb, (iii) the signal-to-noise ratio (SNR) of the channel <NUM> (or a working SNR), and (iv) the bit length M to be transmitted. For example, a Gaussian approximation for density evolution may be performed to find the optimal frozen positions in the input vector u and thereby generate the information sequence <NUM>. However, performing the computation in step <NUM> may result in increased computational complexity and increased latency. In particular, when a general polar code is used that encodes symbols of an q-ary alphabet, where q > <NUM>, then performing step <NUM> in an online manner during operation of the transmitter <NUM> may not be practical. An alternative option is to pre-compute offline and store in the transmitter <NUM> all information sequences for all possible values of M. However, this may require a large portion of memory to store all of the pre-computed information sequences. Memory constraints on the transmitter <NUM>, such as memory space and/or memory access time, may not allow for storage of all of the pre-computed information sequences.

Therefore, in one embodiment, as shown in <FIG>, a look up table (LUT) <NUM> is stored in memory <NUM> in the transmitter <NUM>. The LUT <NUM> may correspond to a particular puncturing pattern. The LUT <NUM> indicates which information sequence to use for various ranges of M. For each range, a single information sequence is computed offline for a representative value of M inside the range, and then that information sequence is used for any value of M inside the range. For example, for a range MA ≤ M < MB, a representative block length MRep is chosen, where MA ≤ MRep < MB. The information sequence is computed offline for MRep and stored in the LUT <NUM>. Then, during operation, whenever the value of M is inside the range MA ≤ M < MB, the information sequence stored in the LUT <NUM> that corresponds to the range MA ≤ M < MB is used. Specifically, for any value M that is inside the range MA ≤ M < MB, K most reliable bit positions are selected to accommodate the K information bits as indicated by the corresponding information sequence of the range (i.e., the information sequence generated for MRep). When M is larger than MRep, the selection may skip one or some bit positions that are forced to be frozen positions due to additional puncturing compared to MRep. The LUT may be significantly abbreviated due to partitioning M into ranges and storing only one information sequence per range, rather than storing an information sequence for every possible value of M.

<FIG> illustrates three codewords <NUM>, <NUM>, and <NUM>. The coding rate R at which codeword <NUM> is transmitted is such that M is slightly smaller than MB. The coding rate R at which codeword <NUM> is transmitted is such that M equals MRep. The coding rate R at which codeword <NUM> is transmitted is such that M equals MA. For each codeword, the number of bits to puncture (P = Nb - M) is different, but the same information sequence, corresponding to MRep, is used. In the example in <FIG>, values MU and ML are illustrated, where MU = MB - MRep and ML = MRep - MA. MU is the portion of the range between MRep and MB, and ML is the portion of the range between MA and MRep. MU is larger than ML. Although it is not necessary for MU to be larger than ML, in implementation MU may be considerably larger than ML. Using a value of M that is less than MRep requires more puncturing than MRep, which results in a higher coding rate with less information available for error detection and/or correction, which may result in decoding failure and further degrade the performance. Therefore, it may be desirable for MA to be closer to MRep, i.e. ML smaller than MU, as illustrated in <FIG>. However, using a value of M that is larger than MRep does not result in additional puncturing compared to MRep, and so important coding information may be mostly kept with little loss. Therefore, MB may not need to be kept as close to MRep, i.e. MU may be larger than ML, as illustrated in <FIG>.

<FIG> is a flow chart of a method performed by the transmitter <NUM> according to one embodiment. In step <NUM>, the transmitter <NUM> determines the bit length M that is to be transmitted over the channel <NUM>. For example, the bit length M may be computed as M = kb/R. In step <NUM>, the transmitter <NUM> generates or determines the puncturing pattern <NUM> by constructing a puncturing pattern that punctures the first P = Nb - M bits of the codeword x. In step <NUM>, the transmitter <NUM> then sends or otherwise makes available the value M to the information sequence generator <NUM>. Alternatively, the information sequence generator <NUM> may independently compute the value of M. In step <NUM>, the information sequence generator <NUM> generates the information sequence <NUM> by reading from the LUT <NUM> the information sequence <NUM> corresponding to the range containing the value of M. The method of <FIG> may be referred to as a piece-wise offline rate/length matching scheme because an information sequence used for a representative MRep is also used for adjacent values of M contained in the designated range.

In step <NUM>, puncturing the first P = Nb - M bits is performed according to the invention as defined in the appended claims. Another set of P = Nb - M bits may be punctured (e.g. shortened) instead according to another puncturing pattern in examples not falling within the scope of the appended claims. The puncturing pattern in step <NUM> may include the shortening patterns that determine which subset of codeword bits to be shortened. In some examples, the puncturing pattern may be generated or determined considering other parameters in addition to M, e. g, the information block length K and/or coding rate R. For instance, for better error correction performance, puncturing the first Nb - M may be adopted for low and medium coding rates R, while block-based shortening or Bit Reversal (BIV) shortening may be used for high coding rates R. In other embodiments, the puncturing pattern may be determined by selecting a puncturing pattern (e.g. based on one or more of the above-noted parameters) from a plurality of available puncturing patterns. In some embodiments, determining a puncturing pattern includes determining the puncturing set, including the number and indices of the sub-channels to be punctured. Also, the piece-wise method described in relation to <FIG> applies to both puncturing patterns that puncture consecutive bits in the codeword and puncturing patterns that do not puncture consecutive bits in the codeword.

In step <NUM>, different LUTs may be used if different puncturing patterns are considered, e.g. each puncturing pattern corresponding to a respective LUT. Different LUTs may contain different numbers of ranges of M and the associated representative sequences. For example, in <FIG>, if block-based shortening or BIV shortening are considered rather than puncturing the first few bits, the number of ranges of M may change with possibly different range boundaries (e.g., <MAT>, etc.). Moreover, for the same value of M, the LUT may contain a different representative sequence (e.g., for M that satisfies M<NUM> ≤ M < M<NUM> and <MAT>, Sequence #<NUM> may be used in one LUT and Sequence #<NUM>' which is different from Sequence #<NUM> may be used in another LUT). Furthermore, although in some embodiments the length of each of the stored sequences is Nb, in other embodiments the length of one, some, or all of the sequences may not be the mother code block length, i.e., power of <NUM>. Instead, a sequence of length smaller than Nb, but no smaller than M<NUM> may be stored for the corresponding range of M, where M<NUM> is the upper boundary of the corresponding range of M.

In some embodiments, the different information sequences for the different ranges of M (e.g. Sequence #<NUM>, Sequence #<NUM>,. etc. in <FIG>) may each correspond to the same mother code length Nb. In other embodiments, different information sequences for different ranges of M may correspond to different mother code lengths (e.g. each information sequence / range of M in <FIG> may correspond to a respective different mother code length).

The flow chart in <FIG> indicates that the selection of sequence, or the sequence generation, is dependent on the specific puncturing patterns as well as the transmitted code block length M.

Possible benefits associated with the method of <FIG> are as follows. By properly dividing the coding bit length space and choosing a representative block length MRep, one for each range, the performance of polar encoding/decoding may be comparable to that of a polar encoder that computes a different information sequence for each value of M. Offline generation is also possible, which may reduce implementation complexity because LUT <NUM> is being accessed during operation, rather than computing the information sequence during operation. The memory requirements may be reduced because an information sequence is being stored for each range of block length values, rather than for every possible block length value M. The method of <FIG> is applicable to encoders that use only binary polar codes, e.g. the Arikan polar code, as well as to encoders that use non-binary general polar codes, e.g. RS based polar codes.

Embodiments above describe generating or choosing the information sequence <NUM> based on which range the value M falls within, e.g. via LUT <NUM>. Alternatively, the range may be based on the coding rate R instead. That is, different ranges of values for the coding rate R may each have a representative coding rate RRep. The information sequence corresponding to RRep may be used whenever the coding rate falls within the range represented by RRep. Also, in alternative embodiments, an information sequence of the mother code block length may be pre-fixed, according to which a common puncturing set is generated or determined for a range of code block lengths M or the coding rates R.

<FIG> illustrate different FER curves. Nb = <NUM> bits and kb = <NUM> bits. The representative coding rate RRep = <NUM>/<NUM>, and therefore <MAT> bits. SCL decoding was performed using a list size L. RS(<NUM>) polar codes were used in the simulations corresponding to <FIG> and <FIG>, and binary polar codes were used in the simulations corresponding to <FIG> and <FIG>. The FER for different list sizes L and values of M are plotted. As may be seen from <FIG>, the FER changes more, relative to MRep = <NUM> bits, when using a value of M that is <NUM> bits less than MRep compared to using a value of M that is <NUM> bits more than MRep.

<FIG> is a flow chart of a method performed by a transmitter, e.g. transmitter <NUM>, according to one embodiment. In step <NUM>, a plurality of bits are received at a polar encoder of the transmitter. The plurality of bits represent a plurality of q-ary symbols, where q > <NUM>.

In step <NUM>, the plurality of bits are encoded using the polar encoder to generate a codeword of q-ary symbols represented by bits.

In some embodiments, encoding the plurality of bits includes encoding the plurality of bits using at least one polar encoder kernel to generate the codeword. The encoding may include: receiving, at the polar encoder kernel, a set of input q-ary symbols represented by bits; and transforming the set of input q-ary symbols, according to a seed matrix of the polar encoder kernel, to produce a set of output q-ary symbols represented by bits.

According to the invention as defined in the appended claims, encoding the plurality of bits includes: (<NUM>) mapping the plurality of q-ary symbols to a subset of positions of an input vector according to an information sequence; (<NUM>) setting remaining positions of the input vector as frozen values that are known by a decoder; and then (<NUM>) encoding the input vector in the polar encoder.

In step <NUM>, the codeword is punctured according to a puncturing pattern to obtain a punctured codeword having a reduced bit length.

In some examples not falling within the scope of the appended claims, the puncturing pattern may be generated based on the information sequence. In embodiments, the information sequence may be generated based on the puncturing pattern. In other examples not falling within the scope of the appended claims, both the information sequence and the puncturing pattern may be jointly generated.

According to the invention as defined in the appended claims, the information sequence is obtained by: (<NUM>) obtaining a value corresponding to at least one of: a coding rate R to be used to transmit the plurality of bits, and a length M of the punctured codeword; (<NUM>) determining which range of values the value falls within; and then (<NUM>) obtaining an information sequence corresponding to the range the value falls within. In some embodiments, obtaining the information sequence corresponding to the range the value falls within includes: retrieving from memory a stored information sequence corresponding to the range. In some embodiments, the information sequence corresponding to the range is an information sequence determined based on a representative value in the range.

According to the invention as defined in the appended claims, the codeword has bit length Nb, the punctured codeword has bit length M, and the puncturing pattern is to puncture the first (Nb - M) bits of the codeword.

<FIG> illustrates an example communication system <NUM> in which embodiments of the present disclosure could be implemented. In general, the system <NUM> enables multiple wireless or wired elements to communicate data and other content. The purpose of the system <NUM> may be to provide content (voice, data, video, text) via broadcast, narrowcast, user device to user device, etc. The system <NUM> may operate efficiently by sharing resources such as bandwidth.

In this example, the communication system <NUM> includes electronic devices (ED) 1310a-1310c, radio access networks (RANs) 1320a-1320b, a core network <NUM>, a public switched telephone network (PSTN) <NUM>, the Internet <NUM>, and other networks <NUM>. While certain numbers of these components or elements are shown in <FIG>, any reasonable number of these components or elements may be included in the system <NUM>.

The EDs 1310a-1310c and base stations 1370a-1370b are examples of communication equipment that can be configured to implement some or all of the functionality and/or embodiments described herein. For example, any one of the EDs 1310a-1310c and base stations 1370a-1370b could be configured to implement the encoding or decoding functionality (or both) described above. In another example, any one of the EDs 1310a-1310c and base stations 1370a-1370b could include the transmitter <NUM>, the receiver <NUM>, or both described above.

The EDs 1310a-1310c are configured to operate, communicate, or both, in the system <NUM>. For example, the EDs 1310a-1310c are configured to transmit, receive, or both via wireless or wired communication channels. Each ED 1310a-1310c represents any suitable end user device for wireless operation and may include such devices (or may be referred to) as a user equipment/device (UE), wireless transmit/receive unit (WTRU), mobile station, fixed or mobile subscriber unit, cellular telephone, station (STA), machine type communication device (MTC), personal digital assistant (PDA), smartphone, laptop, computer, touchpad, wireless sensor, or consumer electronics device.

In <FIG>, the RANs 1320a-1320b include base stations 1370a-1370b, respectively. Each base station 1370a-1370b is configured to wirelessly interface with one or more of the EDs 1310a-1310c to enable access to any other base station 1370a-1370b, the core network <NUM>, the PSTN <NUM>, the Internet <NUM>, and/or the other networks <NUM>. For example, the base stations 1370a-1370b may include (or be) one or more of several well-known devices, such as a base transceiver station (BTS), a Node-B (NodeB), an evolved NodeB (eNodeB), a Home eNodeB, a gNodeB (sometimes called a "gigabit" NodeB), a transmission point (TP), a site controller, an access point (AP), or a wireless router. Any ED 1310a-1310c may be alternatively or jointly configured to interface, access, or communicate with any other base station 1370a-1370b, the internet <NUM>, the core network <NUM>, the PSTN <NUM>, the other networks <NUM>, or any combination of the preceding. Optionally, the system may include RANs, such as RAN 1320b, wherein the corresponding base station 1370b accesses the core network <NUM> via the internet <NUM>, as shown.

In the embodiment shown in <FIG>, the base station 1370a forms part of the RAN 1320a, which may include other base stations, base station controller(s) (BSC), radio network controller(s) (RNC), relay nodes, elements, and/or devices. Any base station 1370a, 1370b may be a single element, as shown, or multiple elements, distributed in the corresponding RAN, or otherwise. Also, the base station 1370b forms part of the RAN 1320b, which may include other base stations, elements, and/or devices. Each base station 1370a-1370b may be configured to operate to transmit and/or receive wireless signals within a particular geographic region or area, sometimes referred to as a "cell. " A cell may be further divided into cell sectors, and a base station 1370a-1370b may, for example, employ multiple transceivers to provide service to multiple sectors. In some embodiments a base station 1370a-1370b may establish pico or femto cells where the radio access technology supports such. In some embodiments, multiple-input multiple-output (MIMO) technology may be employed having multiple transceivers for each cell. The number of RAN 1320a-1320b shown is exemplary only. Any number of RAN may be contemplated when devising the system <NUM>.

The base stations 1370a-1370b communicate with one or more of the EDs 1310a-1310c over one or more air interfaces <NUM> using wireless communication links e.g. RF, µ Wave, IR, etc. The air interfaces <NUM> may utilize any suitable radio access technology. For example, the system <NUM> may implement one or more channel access methods, such as code division multiple access (CDMA), time division multiple access (TDMA), frequency division multiple access (FDMA), orthogonal FDMA (OFDMA), or single-carrier FDMA (SC-FDMA) in the air interfaces <NUM>.

A base station 1370a-1370b may implement Universal Mobile Telecommunication System (UMTS) Terrestrial Radio Access (UTRA) to establish an air interface <NUM> using wideband CDMA (WCDMA). In doing so, the base station 1370a-1370b may implement protocols such as HSPA, HSPA+ optionally including HSDPA, HSUPA or both. Alternatively, a base station 1370a-1370b may establish an air interface <NUM> with Evolved UTMS Terrestrial Radio Access (E-UTRA) using LTE, LTE-A, and/or LTE-B. It is contemplated that the system <NUM> may use multiple channel access functionality, including such schemes as described above. Other radio technologies for implementing air interfaces include IEEE <NUM>, <NUM>, <NUM>, CDMA2000, CDMA2000 1X, CDMA2000 EV-DO, IS-<NUM>, IS-<NUM>, IS-<NUM>, GSM, EDGE, and GERAN. Of course, other multiple access schemes and wireless protocols may be utilized.

The RANs 1320a-1320b are in communication with the core network <NUM> to provide the EDs 1310a-1310c with various services such as voice, data, and other services. Understandably, the RANs 1320a-1320b and/or the core network <NUM> may be in direct or indirect communication with one or more other RANs (not shown), which may or may not be directly served by core network <NUM>, and may or may not employ the same radio access technology as RAN 1320a, RAN 1320b or both. The core network <NUM> may also serve as a gateway access between (i) the RANs 1320a-1320b or EDs 1310a-1310c or both, and (ii) other networks (such as the PSTN <NUM>, the Internet <NUM>, and the other networks <NUM>). In addition, some or all of the EDs 1310a-1310c may include functionality for communicating with different wireless networks over different wireless links using different wireless technologies and/or protocols. Instead of wireless communication (or in addition thereto), the EDs 1310a-1310c may communicate via wired communication channels to a service provider or switch (not shown), and to the internet <NUM>. PSTN <NUM> may include circuit switched telephone networks for providing plain old telephone service (POTS). Internet <NUM> may include a network of computers and subnets (intranets) or both, and incorporate protocols, such as IP, TCP, UDP. EDs 1310a-1310c may be multimode devices capable of operation according to multiple radio access technologies, and incorporate multiple transceivers necessary to support such.

<FIG> illustrate example devices that may implement the functionality and/or embodiments described above.

The processing unit <NUM> may also be configured to implement some or all of the functionality and/or embodiments described above.

The ED <NUM> also includes at least one transceiver <NUM>. The transceiver <NUM> is configured to modulate data or other content for transmission by at least one antenna or NIC (Network Interface Controller) <NUM>. The transceiver <NUM> is also configured to demodulate data or other content received by the at least one antenna <NUM>. Each transceiver <NUM> includes any suitable structure for generating signals for wireless or wired transmission and/or processing signals received wirelessly or by wire. Each antenna <NUM> includes any suitable structure for transmitting and/or receiving wireless or wired signals. One or multiple transceivers <NUM> could be used in the ED <NUM>, and one or multiple antennas <NUM> could be used in the ED <NUM>. Although shown as a single functional unit, a transceiver <NUM> could also be implemented using at least one transmitter and at least one separate receiver. In some embodiments, the transceiver <NUM> may implement transmitter <NUM> and/or receiver <NUM> described earlier.

The ED <NUM> further includes one or more input/output devices <NUM> or interfaces (such as a wired interface to the internet <NUM>). The input/output devices <NUM> facilitate interaction with a user or other devices (network communications) in the network. Each input/output device <NUM> includes any suitable structure for providing information to or receiving/providing information from a user, such as a speaker, microphone, keypad, keyboard, display, or touch screen, including network interface communications.

In addition, the ED <NUM> includes at least one memory <NUM>. The memory <NUM> stores instructions and data used, generated, or collected by the ED <NUM>. For example, the memory <NUM> could store software instructions or modules configured to implement some or all of the functionality and/or embodiments described above and that are executed by the processing unit(s) <NUM>. Each memory <NUM> includes any suitable volatile and/or non-volatile storage and retrieval device(s). Any suitable type of memory may be used, such as random access memory (RAM), read only memory (ROM), hard disk, optical disc, subscriber identity module (SIM) card, memory stick, secure digital (SD) memory card, and the like.

As shown in <FIG>, the base station <NUM> includes at least one processing unit <NUM>, at least one transmitter <NUM> (which may or may not be the same as transmitter <NUM> described earlier), at least one receiver <NUM> (which may or may not be the same as receiver <NUM> described earlier), one or more antennas <NUM>, at least one memory <NUM>, and one or more input/output devices or interfaces <NUM>. A transceiver, not shown, may be used instead of the transmitter <NUM> and receiver <NUM>. A scheduler <NUM> may be coupled to the processing unit <NUM>. The scheduler <NUM> may be included within or operated separately from the base station <NUM>. The processing unit <NUM> can also be configured to implement some or all of the functionality and/or embodiments described in more detail above.

Each transmitter <NUM> includes any suitable structure for generating signals for wireless or wired transmission to one or more EDs or other devices. Each receiver <NUM> includes any suitable structure for processing signals received wirelessly or by wire from one or more EDs or other devices. Although shown as separate components, at least one transmitter <NUM> and at least one receiver <NUM> could be combined into a transceiver. Each antenna <NUM> includes any suitable structure for transmitting and/or receiving wireless or wired signals. While a common antenna <NUM> is shown here as being coupled to both the transmitter <NUM> and the receiver <NUM>, one or more antennas <NUM> could be coupled to the transmitter(s) <NUM>, and one or more separate antennas <NUM> could be coupled to the receiver(s) <NUM>. Each memory <NUM> includes any suitable volatile and/or non-volatile storage and retrieval device(s) such as those described above in connection to the ED <NUM>. The memory <NUM> stores instructions and data used, generated, or collected by the base station <NUM>. For example, the memory <NUM> could store software instructions or modules configured to implement some or all of the functionality and/or embodiments described above and that are executed by the processing unit(s) <NUM>.

Each input/output device <NUM> facilitates interaction with a user or other devices (network communications) in the network. Each input/output device <NUM> includes any suitable structure for providing information to or receiving/providing information from a user, including network interface communications.

Although the present invention has been described with reference to specific features and embodiments thereof, various modifications and combinations can be made thereto without departing from the invention. The description and drawings are, accordingly, to be regarded simply as an illustration of some embodiments of the invention as defined by the appended claims, and are contemplated to cover any and all modifications, variations, combinations or equivalents that fall within the scope of the present invention. Therefore, although the present invention and its advantages have been described in detail, various changes, substitutions and alterations can be made herein without departing from the invention as defined by the appended claims. Moreover, the scope of the present application is not intended to be limited to the particular embodiments of the process, machine, manufacture, composition of matter, means, methods and steps described in the specification. As one of ordinary skill in the art will readily appreciate from the disclosure of the present invention, processes, machines, manufacture, compositions of matter, means, methods, or steps, presently existing or later to be developed, that perform substantially the same function or achieve substantially the same result as the corresponding embodiments described herein may be utilized according to the present invention. Accordingly, the appended claims are intended to include within their scope such processes, machines, manufacture, compositions of matter, means, methods, or steps.

Claim 1:
A method performed at a transmitter comprising:
receiving (<NUM>) a plurality of bits at a polar encoder, the plurality of bits representing a plurality of q-ary symbols, where q > <NUM>;
encoding (<NUM>) the plurality of bits using the polar encoder to generate a codeword x of q-ary symbols represented by bits, wherein the output of the polar encoder can be expressed as x = uG, where G is a generator matrix and u is an input vector;
puncturing (<NUM>) the codeword according to a puncturing pattern to obtain a punctured codeword having a reduced bit length;
characterized in that the codeword has bit length Nb, wherein the punctured codeword has bit length M, and wherein the puncturing pattern is to puncture the first (Nb - M) bits of the codeword;
wherein encoding the plurality of bits comprises:
mapping the plurality of q-ary symbols to a subset of positions of an input vector according to an information sequence;
setting remaining positions of the input vector as frozen values that are known by a decoder; and
encoding the input vector in the polar encoder;
the method further comprising obtaining the information sequence by:
obtaining a value corresponding to at least one of: a coding rate R to be used to transmit the plurality of bits, and a length M of the punctured codeword;
determining which range of values the value falls within;
obtaining an information sequence corresponding to the range the value falls within.