# US 2021/0242886 A1 · Electronic device with bit pattern generation, integrated circuit and method for polar coding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0242886 A1
- Document ID: US20210242886A1
- Status: Published application
- Kind: A1
- Application number: 17/240,080
- Filed: 2021-04-26
- Published: 2021-08-05
- Earliest claimed: 2017-09-11
- Assignees: Accelercomm Limited
- Applicants: AccelerComm Limited
- Inventors: Robert Maunder; Matthew Brejza; Shida Zhong; Isaac Perez-Andrade; Taihai Chen
- Web page: https://patentgrep.com/patent/US20210242886A1

## CPC

- H03M 13/13: Linear codes
- G06F 7/76: Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
- H03M 13/00: Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes (error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C)
- H03M 13/618: {Shortening and extension of codes}
- H03M 13/6356: {by repetition or insertion of dummy data, i.e. rate reduction}
- H03M 13/6362: {by puncturing}
- H03M 13/6508: {Flexibility, adaptability, parametrability and configurability of the implementation}
- H03M 13/6575: {Implementations based on combinatorial logic, e.g. Boolean circuits}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An electronic device configured to perform polar coding is described. The electronic device includes a bit pattern generator (3403) configured to successively perform a bit pattern generation process over a series (t=┌n/w┐) of clock cycles; and a counter (c, 4203), operably coupled to the bit pattern generator (3403) and configured to count a number of successive bit pattern generation sub-processes over the series (t=┌n/w┐) of clock cycles. The bit pattern generator (3403) is configured to: provide a successive sub-set of (w) bits from a bit pattern vector (bk,n) in each successive t=┌n/w┐ clock cycle; where the bit pattern vector comprises n bits, of which ‘k’ bits adopt a first binary value and n−k bits adopt a complementary binary value.

## Claims

### Claim 1

An electronic device configured to perform polar coding, the electronic device comprising:
a bit pattern generator configured to successively perform a bit pattern generation process over a series of clock cycles;
wherein the bit pattern generator is configured to:
provide a successive sub-set of, w, bits from a bit pattern vector, bk,n, in each successive clock cycle; where the bit pattern vector comprises n bits, of which ‘k’ bits adopt a first binary value and n−k bits adopt a complementary binary value, and wherein the bit pattern generator comprises a bank of (w) comparators, and wherein the successive sub-set of, w, bits cause each of w bit pattern bits {b0, b1, b2, . . . bw−1} to be obtained from a corresponding comparator in the bank of w comparators, and wherein a rank vector, Rn, for a length of the bit pattern, ‘n’, comprises integers in a range of ‘0’ to ‘n−1’, permuted in an order that corresponds to a rank of each bit position, and wherein the bit pattern vector, bk, n, is generated for a respective combination of the number, k, of bits in a bit pattern adopting the first binary value and the length of the bit pattern ‘n’ using the bank of w comparators that compares each element of the rank vector, Rn with ‘k’.

### Claim 2 (depends on 1)

The electronic device of claim 1, wherein the bit pattern generator comprises a rank read only memory, ROM, configured to store information sufficient to obtain the rank vector, Rn, for each supported length of the bit pattern, ‘n’.

### Claim 3 (depends on 1)

The electronic device of claim 1, wherein the rank of each bit position indicates a maximum value for the number ‘k’ out of ‘n’ bits in the bit pattern adopting the first binary value, for which a corresponding bit in the bit pattern vector, bk,n, has a complementary binary value, and wherein each comparison determines whether the element of the rank vector, Rn, is less than ‘k’.

### Claim 4 (depends on 2)

The electronic device of claim 2, wherein at least one of the following is adopted:
a length of the bit pattern n is used to index a second look-up table, in order to identify a start address of each particular rank vector, Rn;
the rank ROM comprises multiple multiplexed rank ROMs, wherein one multiplexed rank ROM is configured to store the rank vector, Rn, corresponding to each supported value of the length of the bit pattern ‘n’.

### Claim 5 (depends on 2)

The electronic device of claim 2, wherein at least one of the following is adopted:
all entries in the rank ROM are stored using fixed point numbers having a width of log2(nmax) bits, where nmax is a maximum of the supported bit pattern lengths;
all entries in the rank ROM for values of n are stored using fixed point numbers having a width of log2(n) bits.

### Claim 6 (depends on 2)

The electronic device of claim 2, wherein each address of the rank ROM is configured to store w fixed-point numbers and wherein the rank ROM, in cases where n<w, is configured to append the rank vector, Rn, with w-n dummy elements, such that the rank vector, Rn, occupies a width of a single address in the rank ROM.

### Claim 7 (depends on 1)

The electronic device of claim 1, wherein a bit pattern bit of the bit pattern vector bk,n is obtained by representing both a rank value and k using a two's complement fixed-point number representation, and the bit pattern generator circuit performs a two's complement subtraction of ‘k’ from the rank value and then uses a most significant bit, MSB, as a value of the bit pattern bit.

### Claim 8 (depends on 1)

The electronic device of claim 1, wherein frozen bit insertion or frozen bit removal within the polar coding is performed by the electronic device and the frozen bit insertion or frozen bit removal comprises at least two sub-processes and the bit pattern generator is configured to provide the successive sub-set of (w) bits from the bit pattern vector (bk,n) in each successive clock cycle that spans a duration of a second sub-process that is preceded by a first sub-process that spans a series of zero or more clock cycles and wherein a first logic circuit is arranged to provide during the first sub-process a reliability threshold, k, to an input of the bit pattern generator for use in the second sub-process.

### Claim 9 (depends on 8)

The electronic device of claim 8, wherein the electronic device is configured to support at least two modes of operation, where a respective mode of operation is employed in response to whether a number, M, of encoded bits is less than a kernal block size, N and wherein the at least two modes of operation comprise at least two from: a repetition mode of operation when M is not less than N, a shortening mode of operation when M<N, a puncturing mode of operation when M<N.

### Claim 10 (depends on 9)

The electronic device of claim 9, wherein the first sub-process has zero clock cycles, and the second sub-process is performed when M is not less than N, and the threshold reliability number, k, is set to a number of K bits that adopt the first binary value in a final output bit sequence.

### Claim 11 (depends on 8)

The electronic device of claim 8, further comprising a controller operably coupled to a counter arranged to count a number of clock cycles under control of the controller in the first sub-process when M is less than N, and the first sub-process determines the rank threshold, k, that indicates a number of bits having the first binary value contained in an intermediate value for the bit pattern vector, bk,n, output by the bit pattern generator.

### Claim 12 (depends on 11)

The electronic device of claim 11, further comprising a second logic circuit configured to successively perform a binary flag generation process over the series of clock cycles that comprise the second sub-process and configured to provide a successive sub-set of w binary flags in each successive clock cycle and wherein a binary flag is set in the binary flag generation process if a corresponding bit in the bit pattern vector, bk,n, is not frozen by rate matching.

### Claim 13 (depends on 12)

The electronic device of claim 12, further comprising a third logic circuit configured to receive at least a first input from the second logic circuit and a second input from the bit pattern generator wherein the third logic circuit is configured to provide an output of a first binary value when a bit in the subset of w bits of the intermediate bit pattern vector, bk,n, from the bit pattern generator adopts the first binary value and a corresponding flag from a plurality of binary flags from the second logic circuit is set, thereby adjusting a bit pattern vector, bk,n, of the intermediate bit pattern based on the at least first and second inputs.

### Claim 14 (depends on 8)

The electronic device of claim 8, wherein the first logic circuit is arranged to identify the reliability threshold, k, for use in the second sub-process by determining whether each uncoded bit is frozen by rate matching and the first logic circuit comprises a non-frozen bit counter arranged to count a number of uncoded bits that are not frozen by rate matching in order of decreasing reliability during the first sub-process, and once the count reaches the number of final value bits in a final output bit sequence, K, whereupon the rank of the Kth most reliable unfrozen bit is determined as the rank threshold, k, and the first logic circuit provides the rank threshold k as an input to the bit pattern generator.

### Claim 15 (depends on 8)

The electronic device of claim 8, wherein the electronic device further comprises at least one of:
a set of reversed sequence read only memories, ROMs, located in the first logic circuit configured to store sets of reversed sequences where each successive element of the reversed sequence indicates a position of each successive uncoded bit arranged in order of decreasing reliability;
a set of deinterleaver ROMs located in the first logic circuit configured to store a set of deinterleaver patterns, where each element of the deinterleaver pattern indicates an interleaved position of a polar encoded bit during rate matching;
a set of interleaved sequence ROMs located in the first logic circuit configured to store a set of interleaved sequences;
a second counter, c1, incremented in successive clock cycles of the first sub-process, wherein successive addresses of a reversed sequence ROM and successive addresses of an interleaved sequence ROM, corresponding to a particular value of N are indexed;
a rank ROM located in the bit pattern generator configured to store information sufficient to obtain a rank vector, Rn, for each supported length of the bit pattern, ‘n’;
a first set of functional logic, f1, located in the first logic circuit and configured to obtain a set of binary flags based on received successive sets of elements read from the set of reversed sequence ROMs and the set of interleaved sequence ROMs in each successive clock cycle; and
an accumulator logic circuit located in the first logic circuit and configured to receive and count the set of binary flags up to a number, K, of uncoded bits that are not frozen by rate matching in a final output bit sequence, and the threshold reliability number, k, is set to complete the first sub-process.

### Claim 16 (depends on 8)

The electronic device of claim 8, wherein the first logic circuit is configured to identify a frozen bit as the complementary binary value in the bit pattern vector, bk,n, and identify using the first binary value in the bit pattern vector, bk,n, a bit that comprises one from a group of: an information bit, a cyclic redundancy check, CRC, bit, a parity-check frozen bit, a user equipment identifier, UE-ID, bit, a hash bit.

### Claim 17 (depends on 1)

The electronic device of claim 1, wherein the electronic device comprises at least one of: a transmitter comprising an encoder configured to perform the bit pattern generation process, a receiver comprising a decoder configured to perform the bit pattern generation process.

### Claim 18

An integrated circuit for an electronic device configured to perform polar coding, the integrated circuit comprising:
a bit pattern generator configured to successively perform a bit pattern generation process over a series of clock cycles;
wherein the bit pattern generator is configured to:
provide a successive sub-set of (w) bits from a bit pattern vector (bk,n) in each successive clock cycle; where the bit pattern vector comprises n bits, of which ‘k’ bits adopt a first binary value and n−k bits adopt a complementary binary value and wherein the bit pattern generator comprises a bank of (w) comparators, and wherein the successive sub-set of w bits cause each of w bit pattern bits {b0, b1, b2, . . . , bm−1} to be obtained from a corresponding comparator in the bank of ω comparators, and wherein a rank vector, Rn, for a length of the bit pattern, ‘n’, comprises integers in a range of ‘0’ to ‘n−1’, permuted in an order that corresponds to a rank of each bit position, and wherein the bit pattern vector, bk,n, is generated for a respective combination of the number, k, of bits in a bit pattern adopting the first binary value and the length of the bit pattern ‘n’ using the bank of w comparators that compares each element of the rank vector, Rn with ‘k’.

### Claim 19

A method of polar coding, wherein the method comprises:
successively performing a bit pattern generation process over a series of clock cycles by a bit pattern generator; and
providing a successive sub-set of w bits from a bit pattern vector, bk,n, in each successive clock cycle; where the bit pattern vector comprises ‘n’ bits, of which ‘k’ bits adopt a first binary value and n−k bits adopt a complementary binary value and wherein the bit pattern generator comprises a bank of w comparators, and wherein the successive sub-set of (w) bits cause each of w bit pattern bits {b0, b1, b2, . . . , bw−1} to be obtained from a corresponding comparator in the bank of w comparators, and wherein a rank vector, Rn, for a length of the bit pattern, ‘n’, comprises integers in a range of ‘0’ to ‘n−1’, permuted in an order that corresponds to a rank of each bit position, and wherein the bit pattern vector, bk,n, is generated for a respective combination of the number, k, of bits in a bit pattern adopting the first binary value and the length of the bit pattern ‘n’ using the bank of w comparators that compares each element of the rank vector, Rn with ‘k’

### Claim 20 (depends on 19)

The method of polar coding of claim 19, wherein the bit pattern generator comprises a rank read only memory, ROM, configured to store information sufficient to obtain the rank vector, Rn, for each supported length of the bit pattern, ‘n’.