Methods and apparatus for error correction coding with triangular factorization of generator matrix

1. An encoder apparatus for use in a communication system for encoding of a source data block d into a transmitted code block x, the encoder apparatus comprising:

a data inserter; and

a transform encoder,

wherein the encoder apparatus is configured according to a set of parameters (N, K, G out , G in , , a), wherein N is a length of the transmitted code block x, K is a length of the source data block d, wherein G out is an outer transform matrix and G in is an inner transform matrix, wherein is a data index set, wherein a is a frozen data block, wherein N and K are integers that satisfy 1≤K<N, wherein the data index set is a subset of {1, 2, . . . , N} with a size | |=K, wherein the frozen data block a has a length N−K, wherein the outer transform matrix G out is an N×N upper-triangular Toeplitz matrix defined by a causal impulse response c=(c 0 , c 1 , . . . , c N-1 ), wherein c 0 ≠0 and c m ≠0 for at least one integer m satisfying 1≤m≤N−1, wherein the inner transform matrix G in is an N×N lower-triangular polar transform matrix given by a Kronecker power

G

in

=

[

1

0

1

1

]

⊗

n

,

wherein n=log 2 N, wherein the outer transform matrix G out is further constrained so that G out G in cannot be obtained from G in by any row or column permutation,

wherein the data inserter is configured to receive the source data block d and generate a data container block v by setting v =d and v c =a, wherein v denotes the part of v corresponding to the coordinates of v whose indices are in , and wherein v c denotes the part of v corresponding to the coordinates of v whose indices are not in ,

wherein the transform encoder is configured to receive the data container block v and generate the transmitted code block x by computing x=vG out G in ,

wherein the encoder apparatus is further configured to transmit the transmitted code block x to a decoder apparatus via a channel in the communication system.

2. The encoder apparatus of claim 1 , wherein the transform encoder comprises:

an outer transform encoder configured to receive the data container block v and generate an outer transform block u by computing u=vG out , and

an inner transform encoder configured to receive the outer transform block u and generate the transmitted code block x by computing x=uG in .

3. The encoder apparatus of claim 1 , wherein the encoder apparatus is further configured to determine the data index set by means of a score function, wherein the score function depends on the product G out G in of the inner and outer transform matrices G in and G out .

4. A decoder apparatus for use in a communication system for a received code block y to generate a decoded source data block d as an estimate of a source data block d, wherein the received code block y comprises a noisy version of a transmitted code block x, the decoder apparatus comprising:

an inner decoder; and

an outer decoder,

wherein the decoder apparatus is configured to receive the received code block y from an encoder apparatus via a channel in the communication system, the decoder apparatus configured according a set of parameters (N, K, G out , G in , , a), wherein N is a length of the transmitted code block x, K is a length of the source data block d, wherein G out is an outer transform matrix and G in is an inner transform matrix, wherein is a data index set, wherein a is frozen data block, wherein N and K are integers that satisfy 1≤K<N, wherein the data index set A is a subset of {1, 2, . . . , N} with a size | |=K, wherein the frozen data block a has a length N−K, wherein the outer transform matrix G out is an N×N upper-triangular Toeplitz matrix defined by a causal impulse response c=(c 0 , c 1 , . . . , c N-1 ), wherein c 0 ≠0 and c m ≠0 for at least one integer m satisfying 1≤m≤N−1, wherein the inner transform matrix G in is an N×N lower-triangular polar transform matrix given by a Kronecker power

G

in

=

[

1

0

1

1

]

⊗

n

,

wherein n=log 2 N,

wherein the transmitted code block x is related to the source data block d by a relation x=vG out G in , wherein v is a data container block such that v =d and v c =a, wherein v denotes the part of v corresponding to the coordinates of v whose indices are in , and wherein v c denotes the part of v corresponding to the coordinates of v whose indices are not in ,

wherein the inner decoder is configured to receive the received code block y, receive node metric requests from the outer decoder, calculate node metrics in accordance with the inner transform matrix G in , and send calculated node metrics to the outer decoder,

wherein the outer decoder is configured to send node metric requests to the inner decoder, receive calculated node metrics from the inner decoder, and calculate a decoded data container block P in accordance with the outer transform matrix G out , the data index set , and the frozen data block a, and

wherein the decoder apparatus is further configured to extract the decoded source data block {circumflex over (d)} from the decoded data container block {circumflex over (v)} by setting {circumflex over (d)}={circumflex over (v)} A , wherein {circumflex over (v)} denotes the part of {circumflex over (v)} corresponding to the coordinates of {circumflex over (v)} whose indices are in , and send the decoded source data block {circumflex over (d)} to a destination in the communication system.

5. The decoder apparatus of claim 4 , wherein the inner decoder calculates the node metrics in accordance with a successive cancellation decoder for polar codes.

6. The decoder apparatus of claim 4 , wherein the outer decoder calculates the decoded data container block P by using a tree search algorithm.

7. An encoding method for use in a communication system for encoding of a source data block d into a transmitted code block x using an encoder apparatus including a data inserter and a transform encoder, the method comprising:

configuring the encoder apparatus according to a set of parameters (N, K, G out , G in , , a), wherein N is a length of the transmitted code block x, K is a length of the source data block d, wherein G out is an outer transform matrix and G in is an inner transform matrix, wherein is a data index set, wherein a is a frozen data block, wherein N and K are integers that satisfy 1≤K<N, wherein the data index set is a subset of {1, 2, . . . , N} with a size | |=K, wherein the frozen data block a has a length N−K, wherein the outer transform matrix G out is an N×N upper-triangular Toeplitz matrix defined by a causal impulse response c=(c 0 , c 1 , . . . , c N-1 ), wherein c 0 ≠0 and c m ≠0 for at least one integer m satisfying 1≤m≤N−1, wherein the inner transform matrix G in is an N×N lower-triangular polar transform matrix given by a Kronecker power

G

in

=

[

1

0

1

1

]

⊗

n

,

wherein n=log 2 N, wherein the outer transform matrix G out is further constrained so that G out G in cannot be obtained from G in by any row or column permutation, the encoding method comprising:

receiving, at the data inserter, the source data block d;

generating, within the data inserter, a data container block v by setting v =d and v c =a, wherein v denotes the part of v corresponding to the coordinates of v whose indices are in , and wherein V c denotes the part of v corresponding to the coordinates of v whose indices are not in ;

receiving the data container block v at the transform encoder from the data inserter;

generating, in the transform encoder, the transmitted code block x by computing x=vG out G in ; and

transmitting the transmitted code block x to a decoder via a channel in the communication system.

8. The encoding method of claim 7 , wherein the transform encoder comprises:

an outer transform encoder receiving the data container block v and generating an outer transform block u by computing u=vG out ; and

an inner transform encoder receiving the outer transform block u and generating the transmitted code block x by computing x=uG in .

9. The encoding method of claim 7 , wherein the encoding method further comprises determining the data index set by means of a score function, wherein the score function depends on the product G out G in of the inner and outer transform matrices G in and G out .

10. A decoding method for use in a communication system for decoding a received code block y using a decoder apparatus including an inner decoder and an outer decoder to generate a decoded source block {circumflex over (d)} as an estimate of a source data block d, wherein the received code block y comprises a noisy version of a transmitted code block x, the decoding method comprising:

receiving the received code block y from an encoder via a channel in the communication system;

configuring the decoder apparatus according to a set of parameters (N, K, G out , G in , , a), wherein N is a length of the transmitted code block x, K is a length of the source data block d, wherein G out is an outer transform matrix and G in is an inner transform matrix, wherein is a data index set, wherein a is a frozen data block, wherein N and K are integers that satisfy 1≤K<N, wherein the data index set is a subset of {1, 2, . . . , N} with a size | |=K, wherein the frozen data block a has a length N−K, wherein the outer transform matrix G out is an N×N upper-triangular Toeplitz matrix defined by a causal impulse response c=(c 0 , c 1 , . . . , c N-1 ), wherein c 0 ≠0 and c m ≠0 for at least one integer m satisfying 1≤m≤N−1, wherein the inner transform matrix G in is a N×N lower-triangular polar transform matrix given by a Kronecker power

G

in

=

[

1

0

1

1

]

⊗

n

,

wherein n=log 2 N, wherein the transmitted code block x is related to the source data block d by a relation x=vG out G in , wherein v is a data container block such that v =d and v c =a, wherein v denotes the part of v corresponding to the coordinates of v whose indices are in , and wherein v c denotes the part of v corresponding to the coordinates of v whose indices are not in ;

receiving, at the inner decoder, the received code block y;

sending node metric requests from the outer decoder to the inner decoder;

receiving, at the inner decoder, the node metric requests from the outer decoder;

calculating, in the inner decoder, node metrics in accordance with the inner transform matrix G in ;

sending calculated node metrics from the inner decoder to the outer decoder;

receiving, at the outer decoder, the calculated node metrics from the inner decoder;

calculating, in the outer decoder, a decoded data container block 19 in accordance with the outer transform matrix G out , the data index set , and the frozen data block a;

extracting the decoded source data block {circumflex over (d)} from a part {circumflex over (v)} of the decoded data container block {circumflex over (v)}, wherein {circumflex over (v)} denotes the part of {circumflex over (v)} corresponding to the coordinates of {circumflex over (v)} whose indices are in ; and

sending the decoded source data block {circumflex over (d)} to a destination in the communication system.

11. The decoding method of claim 10 , further comprising:

calculating, within the inner decoder, the node metrics in accordance with a successive cancellation decoder for polar codes.

12. The decoding method of claim 10 , further comprising:

calculating, within the outer decoder, the decoded data container block P by using a tree search algorithm.