Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
METHODS AND APPARATUS FOR ERROR CORRECTION CODING WITH TRIANGULAR FACTORIZATION OF GENERATOR MATRIX
Document Type and Number:
WIPO Patent Application WO/2020/261038
Kind Code:
A4
Abstract:
An encoder apparatus 110, 210 for reliable transfer of source data block d in communication system 100 includes an outer transform 212 configured to receive a data container block v and compute an outer transform block u, whereby u = vG out for an outer transform matrix G out. The encoder apparatus also includes an inner transform 213 configured to receive the outer transform block u and compute a transmitted code block x, whereby x = uG in for an inner transform matrix G in. The data container block v is obtained from the source data block d and a frozen data block a which is a predetermined block of symbols. The outer transform matrix G out and the inner transform matrix form a triangular factorization of a transform matrix G, while the outer transform matrix G out and the inner transform matrix G in are strictly upper- and lower-triangular matrices, respectively.

Inventors:
ARIKAN ERDAL (TR)
Application Number:
PCT/IB2020/055588
Publication Date:
February 25, 2021
Filing Date:
June 15, 2020
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
POLARAN HABERLESME TEKNOLOJILERI ANONIM SIRKETI (TR)
International Classes:
H04L1/00; H03M13/13; H03M13/29
Download PDF:
Claims:
1

AMENDED CLAIMS received by the International Bureau on 11 January 2021 (11.01.2021)

1. (Replaces Claim 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, Gout, Gin, A, a), wherein N is a length of the transmitted code block x, K is a length of the source data block d, wherein Gout is an outer transform matrix and Gn is an inner transform matrix, wherein A is a data index set, wherein a is a fixed 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 \A\ = K, wherein the fixed data block a has a length N — K, wherein the outer transform matrix Gout is an N X N upper triangular matrix with an element (gout)i,j at an ith row and a j th column of Gout for each i = 1,2, ··· , N and j = 1,2, ··· , N, wherein (gout)i,j = 0 for each pair of integers (i,j) satisfying 1 £ j < i £ N, wherein (gout)i,i ¹ 0 for each i = 1,2, ···, N, wherein (gout)i,j ¹ 0 for at least one pair of integers (i,j) satisfying 1 £ i < j £ N, wherein the inner transform matrix Gn is an N X N lower triangular polar transform matrix given by a Kronecker power wherein the data inserter is configured to receive the source data block d and generate a data container block v by setting vA = d and vAc = a, wherein vA denotes the data part of v corresponding to the coordinates of v whose indices are in A, and wherein vAc denotes the part of v corresponding to coordinates of v whose indices are not in A, wherein the transform encoder is configured to receive the data container block v and generate a transmitted code block x by computing x = vGout Gn, wherein the encoder apparatus is further configured to send the transmitted code block x to a channel in the communication system.

2. (Replaces Claim 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 = vGout, and 2 an inner transform encoder configured to receive the outer transform block u and compute the transmitted code block x = uGn.

3. (Replaces Claim 3) The encoder apparatus of claim 2, wherein the outer transform matrix Gout is a Toeplitz matrix defined by a causal impulse response c = (c0, c1, ···, cm), wherein m > 0, cQ ¹ 0, and cm ¹ 0.

4. (Replaces Claim 7) The encoder apparatus of claim 1, wherein the data index set A is chosen in accordance with a pointwise score function, wherein the pointwise score function is one of a Hamming score function, a mutual information score function, or a Gallager score function.

5. (Replaces Claim 8) A decoder apparatus for use in a communication system for receiving a received code block y from a channel and decoding the 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 according a set of parameters (N, K, Gout, Gn, A, a), wherein N is a length of the transmitted code block x, K is a length of the source data block d, wherein Gout is an outer transform matrix and Gn is an inner transform matrix, wherein A is a data index set, wherein a is a fixed 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 \A\ = K, wherein the fixed data block a has a length N — K, wherein the outer transform matrix Gout is an N X N upper triangular matrix with an element (gout)i,j at an ith row and a j th column of Gout for each i = 1,2, ··· , N and j = 1,2, ··· , N wherein (gout)i,j = 0 for each pair of integers (i,j) satisfying 1 £ j < i £ N, wherein(gout)i,i ¹ 0 for each i = 1,2, ··· , N, and wherein (gout)i,j ¹ 0 for at least one pair of integers (i,j) satisfying 1 £ i < j £ N, wherein the inner transform matrix Gin is a N X N lower-triangular polar transform matrix given by a Kronecker power Gin = 3 wherein the transmitted code block x is related to the source data block d by a relation x = vGoutGin, wherein v is a data container block such that vA = d and vAc = a, wherein vA denotes the part of v corresponding to the coordinates of v whose indices are in A, and wherein vAc denotes the part of v corresponding to the coordinates of v whose indices are not in A, 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 Gn, 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 v in accordance with the outer transform matrix Gout, the data index set A, and the fixed data block a, and wherein the decoder apparatus further configured to extract the decoded source data block d from the decoded data container block v by setting d = vA wherein vA denotes the part of v corresponding to the coordinates of v whose indices are in A, and send the decoded source data block d to a destination in the communication system.

6. (Replaces Claim 9) The decoder apparatus of claim 5, wherein the outer transform matrix Gout is a Toeplitz matrix defined by a causal impulse response c = (c0, c1, ..., cN-1), wherein c0 ¹ 0 and and cm ¹ 0 for at least one integer m satisfying 1 £ m £ N — 1.

7. (Replaces Claim 10) The decoder apparatus of claim 5, wherein the data index set A is chosen in accordance with a pointwise score function, wherein the pointwise score function is one of a Hamming score function, a mutual information score function, or a Gallager score function.

8. (Replaces Claim 11) The decoder apparatus of claim 5, wherein the outer decoder calculates the decoded data container block by using a depth-first tree search algorithm.

9. (Replaces Claim 13) An encoding method for use in a communication system for 4 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, Gout, Gn, A, a), wherein N is a length of the transmitted code block x, K is a length of the source data block d, wherein Gout is an outer transform matrix and Gin is an inner transform matrix, wherein A is a data index set, wherein a is a fixed 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 IAI = K , wherein the fixed data block a has a length N — K, wherein the outer transform matrix Gout is an N x N upper triangular matrix with an element (gout)i,j at an ith row and a j th column of Gout for each i = 1,2, ··· , N and j = 1,2, ··· , N, wherein (gout)i,j = 0 for each pair of integers (i,j) satisfying 1 £ j < i £ N, wherein (gout)i,i ¹ 0 for each i = 1,2, ··· , N, wherein (gout)i,j ¹ 0 for at least one pair of integers (i,j) satisfying 1 £ i < j £ N, wherein the inner transform matrix Gn is an N X N lower triangular polar transform matrix given by a Kronecker power wherein n = log2 N, 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 VA = d and vAc = a, wherein VA denotes the part of v corresponding to the coordinates of v whose indices are in A, and wherein vAc denotes the part of v corresponding to the coordinates of v whose indices are not in Jl; 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 = and sending the transmitted code block x to a channel in the communication system.

10. (Replaces Claim 14) The encoding method of claim 9, wherein the transform encoder comprises: an outer transform encoder receiving the data container block v and generating an outer transform block u = vGout; and an inner transform encoder receiving the outer transform block u and computing the transmitted code block x = uGin. 5

11. (Replaces Claim 15) The encoding method of claim 10, wherein the outer transform matrix Gout is a Toeplitz matrix defined by a causal impulse response c = (c0, c1, ..., cm) , herein m > 0, cQ ¹ 0, and cm ¹ 0.

12. (Replaces Claim 18) The encoding method of claim 9, wherein the data index set A is chosen in accordance with a pointwise score function, wherein the pointwise score function is one of a Hamming score function, a mutual information score function, or a Gallager score function.

13. (Replaces Claim 19) A decoding method for use in a communication system for receiving a received code block y from a channel and decoding the received code block y using a decode apparatus including an inner decoder and an outer decoder to generate a decoded source 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 decoding method comprising: configuring the decoder apparatus according to a set of parameters ( N , K, Gout, Gn, A, a), wherein N is a length of the transmitted code block x, K is a length of the source data block d, wherein Gout is an outer transform matrix and Gin is an inner transform matrix, wherein A is a data index set, wherein a is a fixed 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 \A\ = K , wherein the fixed data block a has a length N — K, wherein the outer transform matrix Gout is an N x N upper triangular matrix with an element (gout)i,j at an ith row and a ;th column of Gout for each i = 1,2, ··· , N and j = 1,2, ··· , N, wherein (gout);,; = 0 for each pair of integers (i,j) satisfying 1 £ j < i £ N, wherein (gout)i,i ¹ 0 for each i = 1,2, ··· , N, and wherein (gout)i,j ¹ 0 for at least one pair of integers (i, j) satisfying 1 £ i < j £ N, wherein the inner transform matrix Gin is a N X N lower-triangular polar transform matrix given by a Kronecker power wherein n = log2 N, wherein the transmitted code block x is related to the source data block d by a relation x = vGoutGin, wherein v is a data container block such that vA = d and vAc = a, wherein vA denotes the part of v corresponding to the coordinates of v whose indices are in A, and wherein vAc denotes the part of v corresponding to the coordinates of v whose indices are not in A; 6 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 Gin; 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 v in accordance with the outer transform matrix , the data index set A, and the fixed data block a; extracting the decoded source data block d from a part vA of the decoded data container block v, wherein vA denotes the part of v corresponding to the coordinates of v whose indices are in A; and sending the decoded source data block d to a destination in the communication system.

14. (Replaces Claim 20) The decoding method of claim 13, wherein the outer transform matrix Gout is a Toeplitz matrix defined by a causal impulse response c = (c0, c1, ..., cN-1) , wherein c0 ¹ 0 and and cm ¹ 0 for at least one integer m satisfying 1 £ m £ N — 1.

15. (Replaces Claim 21) The decoding method of claim 13, wherein the data index set A is chosen in accordance with a pointwise score function, wherein the pointwise score function is one of a Hamming score function, a mutual information score function, or a Gallager score function.

16. (Replaces Claim 22) The decoding method of claim 13, wherein the outer decoder calculates the decoded data container block v by using a depth-first tree search algorithm.