# US 2019/0173496 A1 · Coding and Decoding of Polar Codes Extended to Lengths which are not Powers of Two

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

- Number: US 2019/0173496 A1
- Document ID: US20190173496A1
- Status: Published application
- Kind: A1
- Application number: 16/272,173
- Filed: 2019-02-11
- Published: 2019-06-06
- Earliest claimed: 2016-08-12
- Assignees: Huawei Technologies Co., Ltd.
- Applicants: Huawei Technologies Co., Ltd.
- Inventors: Oleg Feat'evich Kurmaev; Petr Vladimirovich Trifonov; Alexey Mikhailovich Razinkin; Aleksei Eduardovich Maevskii
- Web page: https://patentgrep.com/patent/US20190173496A1

## CPC

- H03M 13/2927: {Decoding strategies}
- H03M 13/033: {Theoretical methods to calculate these checking codes}
- H03M 13/13: Linear codes
- H03M 13/152: {Bose-Chaudhuri-Hocquenghem [BCH] codes}
- H03M 13/2909: {Product codes}
- H03M 13/618: {Shortening and extension of codes}
- 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)

## Abstract

An encoding apparatus includes a processor a non-transitory computer-readable storage medium storing a program for encoding data x of dimension k into a codeword c of length n. The program includes instructions to encode the data x using a C(n, k, d) code. The code C(n,k,d) has a length n and a minimum distance d, n=2m1+ . . . +2ms, mh, h=1, . . . , s, is an integer, on the basis of c=uA, where ui=xji, 0≤ji<k−1, if i∉F, F is a set of n−k frozen bit indices of the code C(n,k,d), and ui=Σs=0i−1ϕi,sus, if i∈F, is a constraint matrix given by a solution of T=0, ϕi is an index of a row of the matrix , having a last non-zero element in column i, and is a precoding matrix and A is a matrix defined by A m h = ( 1 0 1 1 ) ⊗ m h , and Q⊗m denotes the m-times Kronecker product of a matrix Q with itself.

## Claims

### Claim 1

An encoding apparatus, comprising:
a processor; and
a non-transitory computer-readable storage medium storing a program for encoding data x of dimension k into a codeword c of length n, the program to be executed by the processor, the program including instructions to:
encode the data x using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2m1++2ms, wherein mh, h=1, . . . , s, is an integer number, on the basis of the equation:
wherein ui=xji, 0≤ji<k−1, if i∉F, wherein F is a set of n−k frozen bit indices of the code C(n, k, d), and ui=Σs=0i−1ϕi,sus, if i∈F, wherein is a constraint matrix given by a solution of the equation:
T=0,
wherein ϕi is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as:
A
=
(
A
m
1
0
…
0
0
A
m
2
…
0
⋮
⋮
⋱
⋮
0
0
…
A
m
s
)
,
and
wherein
A
m
h
=
(
1
0
1
1
)
⊗
m
h
,
and wherein Q⊗n denotes the m-times Kronecker product of a matrix Q with itself.

### Claim 2 (depends on 1)

The encoding apparatus of claim 1, wherein the program further includes instructions to:
construct the code C(n, k, d) according to a plurality of nested linear block codes Cij(2mi, Ki,j, dij),Ki,j+1>Ki,j,0≤j<τi, wherein τi is a positive integer, wherein a generator matrix of Cij(2mi, Ki,j,Ki,j, dij) is given by the equation:
G
~
(
i
,
j
)
=
(
G
(
i
,
0
)
G
(
i
,
1
)
⋮
G
(
i
,
j
)
)
,
wherein G(i,j) is a ki,j×2mi matrix, Ki,j=Σs=0jki,s, wherein a precoding matrix of G(i,j) is defined by
W
(
i
,
j
)
=
G
(
i
,
j
)

(
1
0
1
1
)
⊗
i
,
wherein a precoding matrix of {tilde over (G)}(i,j) is defined by
W
~
(
i
,
j
)
=
G
~
(
i
,
j
)

(
1
0
1
1
)
⊗
i
,
and wherein an index li,p of a column, where a p-th row of the matrix {tilde over (W)}(i,τi−1) starts, is defined by the equation
l
i
,
p
=
min


0
≤
t
<
2
i
W
~
p
,
t
(
i
,
τ
i
-
1
)
=
1


t
,
0≤p<2mi; and
construct the precoding matrix as a block matrix, wherein the blocks of the precoding matrix consist of selected rows of the matrices {tilde over (W)}(i,j).

### Claim 3 (depends on 2)

The encoding apparatus of claim 2, wherein the plurality of nested linear block codes Cij(2mi,Ki,j,dij) are extended Bose-Chaudhuri-Hocquenghem (e-BCH) codes.

### Claim 4 (depends on 2)

The encoding apparatus of claim 2, wherein the program further includes instructions to construct a precoding matrix of the code C(n, k, d) according to:

~
=
(
W
~
(
1
,
r
1
)
0
0
…
0
0
W
~
(
2
,
r
2
)
0
…
0
0
0
W
~
(
3
,
r
3
)
…
0
⋮
⋮
⋮
⋱
⋮
0
0
0
…
W
~
(
s
,
r
s
)
W
(
1
,
r
1
+
1
)
W
^
(
2
,
1
)
W
^
(
3
,
1
)
…
W
^
(
s
,
1
)
0
W
(
2
,
r
2
+
1
)
W
^
(
3
,
2
)
…
W
^
(
s
,
2
)
⋮
⋮
⋮
⋱
⋮
)
,
wherein ri=maxj:dj≥d j is an index of a largest e-BCH code of length 2mi having a minimum distance of at least d, and wherein Ŵ(i,j) is a matrix defined on the basis of the matrix {tilde over (W)}.

### Claim 5 (depends on 2)

The encoding apparatus of claim 2, wherein the program further includes instructions to construct the matrix Ŵ(i,j) using rows of the matrix {tilde over (W)}(i,τj) having the smallest value of Pmi,Ii,p, wherein Pm,i is an error probability in a bit subchannel Wm(i)(y02m−1,u0i−1|ui), and wherein y02m−1=y0 . . . y2m−1 denotes 2m−1 noisy symbols of the codeword c after a transmission over a communication channel.

### Claim 6 (depends on 2)

The encoding apparatus of claim 2, wherein the program further includes instructions to arrange the rows of the matrix W(i,ri+1) or Ŵ(j,i) in an ascending order of the values li,p and lj,p, respectively.

### Claim 7 (depends on 2)

The encoding apparatus of claim 2, wherein the program further includes instructions to construct the matrix based on k rows of the matrix with the smallest values of li,p.

### Claim 8 (depends on 1)

The encoding apparatus of claim 1, wherein the program further includes instructions to:
construct a first plurality of t rows of the matrix such that the last non-zero elements in the first plurality of t rows are located in distinct positions j, j≥j0 for some integer j0;
construct elements of the first plurality of t rows located in columns having an index z<j using a pseudorandom number generator; and
construct a second plurality of n−k−t rows of matrix as distinct weight-one rows.

### Claim 9 (depends on 8)

The encoding apparatus of claim 8, wherein the pseudorandom number generator is a linear feedback shift register.

### Claim 10

A method, comprising:
encoding data x of dimension k into a codeword c of length n using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2m1+ . . . +2ms, wherein mh, h=1, . . . , s, is an integer number, on the basis of the equation:
c=uA,
wherein ui=xji, 0≤ji<k−1, if i∉F, wherein F is a set of n−k frozen bit indices of the code C(n, k, d), and ut=Σs=0i−1ϕi,sus, if i∈F, wherein is a constraint matrix given by a solution of the equation:
T=0,
wherein ϕi is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as:
A
=
(
A
m
1
0
…
0
0
A
m
2
…
0
⋮
⋮
⋱
⋮
0
0
…
A
m
s
)
,
and
wherein
A
m
h
=
(
1
0
1
1
)
⊗
m
h
,
and wherein Q⊗m denotes the m-times Kronecker product of a matrix Q with itself.

### Claim 11 (depends on 10)

The method of claim 10, further comprising:
constructing the code C(n, k, d) on the basis of a plurality of nested linear block codes Cij(2mi,Ki,j,dij),Ki,j+1>Ki,j,0≤j<τi, wherein τi is a positive integer, wherein a generator matrix of Cij(2mi,Ki,j, dij) is given by the equation:
G
~
(
i
,
j
)
=
(
G
(
i
,
0
)
G
(
i
,
1
)
⋮
G
(
i
,
j
)
)
,
wherein G(i,j) is a ki,j×2mi matrix, Ki,j=Σs=0jki,s, wherein a precoding matrix of G(i,j) is defined by
W
(
i
,
j
)
=
G
(
i
,
j
)

(
1
0
1
1
)
⊗
i
,
wherein a precoding matrix of {tilde over (G)}(i,j) is defined by
W
~
(
i
,
j
)
=
G
~
(
i
,
j
)

(
1
0
1
1
)
⊗
i
,
wherein an index li,p of a column, where a p-th row of the matrix {tilde over (W)}(i,τi−1) starts, is defined by the equation
l
i
,
p
=
min


0
≤
t
<
2
i
W
~
p
,
t
(
i
,
τ
i
-
1
)
=
1


t
,
0
≤
p
<
2
m
i
;
and
construct the precoding matrix as a block matrix, wherein the blocks of the precoding matrix consist of selected rows of the matrices {tilde over (W)}(i,j).

### Claim 12 (depends on 11)

The method of claim 11, wherein the plurality of nested linear block codes Cij (2mi, Ki,j, dij) are extended Bose-Chaudhuri-Hocquenghem (e-BCH) codes.

### Claim 13 (depends on 11)

The method of claim 11, further comprising:
constructing a precoding matrix of the code C(n, k, d) according to:

~
=
(
W
~
(
1
,
r
1
)
0
0
…
0
0
W
~
(
2
,
r
2
)
0
…
0
0
0
W
~
(
3
,
r
3
)
…
0
⋮
⋮
⋮
⋱
⋮
0
0
0
…
W
~
(
s
,
r
s
)
W
(
1
,
r
1
+
1
)
W
^
(
2
,
1
)
W
^
(
3
,
1
)
…
W
^
(
s
,
1
)
0
W
(
2
,
r
2
+
1
)
W
^
(
3
,
2
)
…
W
^
(
s
,
2
)
⋮
⋮
⋮
⋱
⋮
)
,
wherein ri=maxj:dij≥d kj is an index of a largest e-BCH code of length 2mi having a minimum distance of at least d, and wherein {tilde over (W)}(i,j) is a matrix defined on the basis of the matrix {tilde over (W)}.

### Claim 14 (depends on 11)

The method of claim 11, further comprising:
constructing the matrix {tilde over (W)}(i,j) using rows of the matrix {tilde over (W)}(i,τj) having the smallest value of Pmi,li,p, wherein Pm, is an error probability in a bit subchannel Wm(i)(y02m−1,u0i−1|ui), and wherein y02m−1=y0 . . . y2m-1 denotes 2m−1 noisy symbols of the codeword c after a transmission over a communication channel.

### Claim 15 (depends on 10)

The method of claim 10, further comprising:
constructing a first plurality of t rows of the matrix such that the last non-zero elements in the first plurality of t rows are located in distinct positions j, j≥j0 for some integer j0;
constructing elements of the first plurality oft rows located in columns having an index z<j using a pseudorandom number generator; and
constructing a second plurality of n−k−t rows of matrix as distinct weight-one rows.

### Claim 16

A decoding apparatus
a processor; and
a non-transitory computer-readable storage medium storing a program for decoding a codeword c of length n, the program to be executed by the processor, the program including instructions to:
decode the codeword c using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2m1+ . . . +2ms, wherein mh, h=1, . . . , s, is an integer number, wherein:
c=uA,
wherein ui=xji, 0≤ji<k−1, wherein x is data of dimension k, if i∉F, wherein F is a set of n−k frozen bit indices of the code C(n, k, d) and ui=Σs=0i−1ϕi,sus, if i∈F, wherein V is a constraint matrix given by a solution of the equation:
T=0,
wherein ϕi is an index of a row of the matrix V, which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as:
A
=
(
A
m
1
0
…
0
0
A
m
2
…
0
⋮
⋮
⋱
⋮
0
0
…
A
m
s
)
,
wherein
A
m
h
=
(
1
0
1
1
)
⊗
m
h
,
and wherein Q⊗m denotes the m-times Kronecker product of a matrix Q with itself.

### Claim 17 (depends on 16)

The decoding apparatus of claim 16, wherein the instructions to decode the codeword include instructions to decode the codeword c by generalization of a successive cancellation algorithm.

### Claim 18 (depends on 17)

The decoding apparatus of claim 17, wherein the program further includes instructions to compute u according to:
ûi=Σs=0i−1ϕi,sû2, if i∈F
and
ûi=arg maxuiWμi(imod2μi)(yti2μi+ti−1,ûtii−1|ui), if i∈F,
wherein ϕi is an index of a row of the matrix V, which has a last non-zero element in column i, and wherein y0n-1=y0 . . . yn-1 denotes n noisy symbols of the codeword c after a transmission over a communication channel 110 to the decoding apparatus, μi=└log2 (2┌log2 n┐−i)┘, and ti=2┌log2 n┐−2μi+1.

### Claim 19 (depends on 18)

The decoding apparatus of claim 18, wherein the program further includes instructions to compute ûi1 before ûi2, if μi1=μi2 and i1<i2, and to compute ûs:ϕi,s≠0, s<i, before ûi, if i∈F.

### Claim 20

A method, comprising:
decoding for decoding a codeword c of length n using a C(n, k, d) code, wherein the code C(n, k, d) has a length n and a minimum distance d, wherein n=2m1+ . . . +2ms, wherein mh, h=1, . . . , s, is an integer number, wherein:
c=uA,
wherein ui=xji, 0≤ji<k−1, wherein x is data of dimension k, if i∉F, wherein F is a set of n−k frozen bit indices of the code C(n, k, d) and ui=Σs=0i−1ϕi,sus, if i∈F, wherein V is a constraint matrix given by a solution of the equation:
T=0,
wherein ϕi is an index of a row of the matrix , which has a last non-zero element in column i, wherein is a precoding matrix, and wherein A is defined as:
A
=
(
A
m
1
0
…
0
0
A
m
2
…
0
⋮
⋮
⋱
⋮
0
0
…
A
m
s
)
,
wherein
A
m
h
=
(
1
0
1
1
)
⊗
m
h
,
and wherein Q⊗m denotes the m-times Kronecker product of a matrix Q with itself.
