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

Abstract

An encoder apparatus for reliable transfer of a source data block d in a communication system includes an outer transform configured to receive a data container block v and compute an outer transform block u, whereby u=vG.sub.out for an outer transform matrix G.sub.out. The encoder apparatus also includes an inner transform configured to receive the outer transform block u and compute a transmitted code block x, whereby x=uG.sub.in for an inner transform matrix G.sub.in. The data container block v is obtained from the source data block d and a frozen data block a. The frozen data block a is a predetermined block of symbols. The outer transform matrix G.sub.out and the inner transform matrix form a triangular factorization of a transform matrix G, which optionally is a non-triangular matrix, while the outer transform matrix G.sub.out and the inner transform matrix G.sub.in are strictly upper- and lower-triangular matrices, respectively.

Claims

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.sub.out, G.sub.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.sub.out is an outer transform matrix and G.sub.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.sub.out is an N×N upper-triangular Toeplitz matrix defined by a causal impulse response c=(c.sub.0, c.sub.1, . . . , c.sub.N-1), wherein c.sub.0≠0 and c.sub.m≠0 for at least one integer m satisfying 1≤m≤N−1, wherein the inner transform matrix G.sub.in is an N×N lower-triangular polar transform matrix given by a Kronecker power $G_{\mathrm{in}}={\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]}^{.Math.n},$ wherein n=log.sub.2 N, wherein the outer transform matrix G.sub.out is further constrained so that G.sub.outG.sub.in cannot be obtained from G.sub.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.sub.c=a, wherein v.sub. denotes the part of v corresponding to the coordinates of v whose indices are in , and wherein v.sub.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.sub.outG.sub.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.sub.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.sub.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.sub.outG.sub.in of the inner and outer transform matrices G.sub.in and G.sub.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.sub.out, G.sub.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.sub.out is an outer transform matrix and G.sub.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.sub.out is an N×N upper-triangular Toeplitz matrix defined by a causal impulse response c=(c.sub.0, c.sub.1, . . . , c.sub.N-1), wherein c.sub.0≠0 and c.sub.m≠0 for at least one integer m satisfying 1≤m≤N−1, wherein the inner transform matrix G.sub.in is an N×N lower-triangular polar transform matrix given by a Kronecker power $G_{\mathrm{in}}={\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]}^{.Math.n},$ wherein n=log.sub.2 N, wherein the transmitted code block x is related to the source data block d by a relation x=vG.sub.outG.sub.in, wherein v is a data container block such that v=d and v.sub.c=a, wherein v denotes the part of v corresponding to the coordinates of v whose indices are in , and wherein v.sub.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.sub.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.sub.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)}.sub.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.sub.out, G.sub.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.sub.out is an outer transform matrix and G.sub.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.sub.out is an N×N upper-triangular Toeplitz matrix defined by a causal impulse response c=(c.sub.0, c.sub.1, . . . , c.sub.N-1), wherein c.sub.0≠0 and c.sub.m≠0 for at least one integer m satisfying 1≤m≤N−1, wherein the inner transform matrix G.sub.in is an N×N lower-triangular polar transform matrix given by a Kronecker power $G_{\mathrm{in}}={\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]}^{.Math.n},$ wherein n=log.sub.2 N, wherein the outer transform matrix G.sub.out is further constrained so that G.sub.outG.sub.in cannot be obtained from G.sub.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.sub.c=a, wherein v.sub. denotes the part of v corresponding to the coordinates of v whose indices are in , and wherein V.sub.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.sub.outG.sub.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.sub.out; and an inner transform encoder receiving the outer transform block u and generating the transmitted code block x by computing x=uG.sub.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.sub.outG.sub.in of the inner and outer transform matrices G.sub.in and G.sub.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.sub.out, G.sub.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.sub.out is an outer transform matrix and G.sub.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.sub.out is an N×N upper-triangular Toeplitz matrix defined by a causal impulse response c=(c.sub.0, c.sub.1, . . . , c.sub.N-1), wherein c.sub.0≠0 and c.sub.m≠0 for at least one integer m satisfying 1≤m≤N−1, wherein the inner transform matrix G.sub.in is a N×N lower-triangular polar transform matrix given by a Kronecker power $G_{\mathrm{in}}={\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]}^{.Math.n},$ wherein n=log.sub.2 N, wherein the transmitted code block x is related to the source data block d by a relation x=vG.sub.outG.sub.in, wherein v is a data container block such that v=d and v.sub.c=a, wherein v.sub. denotes the part of v corresponding to the coordinates of v whose indices are in , and wherein v.sub.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.sub.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.sub.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)}.sub. 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.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a functional block diagram of a communication system employing error correction coding in accordance with embodiments of the present disclosure;

(2) FIG. 2 is a functional block diagram of a communication system employing triangular factorization coding in accordance with embodiments of the present disclosure;

(3) FIG. 3 is a circuit for implementing an exemplary hardware data inserter for use with the system of FIG. 2;

(4) FIG. 4 is a pseudo code for implementing an exemplary data inserter in software for use with the system of FIG. 2;

(5) FIG. 5 is an exemplary outer transform for use in a communication system employing error correction coding in accordance with embodiments of the present disclosure;

(6) FIG. 6 is an exemplary polar transform circuit for use in a communication system employing error correction coding in accordance with embodiments of the present disclosure;

(7) FIG. 7 is a flowchart for a stack decoder for use in a communication system employing error correction coding in accordance with embodiments of the present disclosure;

(8) FIG. 8A is a graph showing simulation results that demonstrate a performance advantage of the present principles relative to prior art in polar coding;

(9) FIG. 8B is a graph comparing information and rate allocation profiles for the present principles and the prior art;

(10) FIG. 9 illustrates an example wireless network within which error correction coding may be implemented according to this disclosure;

(11) FIG. 10A illustrates an example user equipment network within which error correction coding may be implemented according to this disclosure; and

(12) FIG. 10B illustrates an example enhanced NodeB (eNB) network within which error correction coding may be implemented according to this disclosure.

DETAILED DESCRIPTION

(13) FIGS. 1 through 10B, discussed below, and the various embodiments used to describe the principles of the present disclosure in this patent document are by way of illustration only and should not be construed in any way to limit the scope of the disclosure. Those skilled in the art will understand that the principles of the present disclosure may be implemented in any suitably arranged communication system.

(14) Notation. For any set and integer m≥1, .sup.m denotes the set of m-tuples over . If a=(a.sub.1, a.sub.2, . . . , a.sub.m)∈.sup.m and i,j are integers satisfying 1≤i≤j≤m, we will use the notation a.sub.i.sup.j as a short-hand for the portion (a.sub.i, a.sub.i+1, . . . , a.sub.j) of a consisting of coordinates from i to j. We will interpret a.sub.i.sup.j as null if j<i. Given a=(a.sub.1, a.sub.2, . . . , a.sub.m)∈.sup.m and any set ⊂{1, 2, . . . , m} of indices (coordinates) of a, we use the notation a.sub. to denote the tuple a=(a.sub.i:i∈) that consists of the elements of a with indices in ; the notation a.sub.c=(a.sub.i:i∈.sup.c) denotes the vector that consists of the elements of a with indices in .sup.c wherein .sup.c denotes the set of indices of a that is complimentary to the set . For example, let m=8 and ={1,2,3,5,8}. Then, a=(a.sub.1, a.sub.2, a.sub.3, a.sub.5, a.sub.8) and a.sub.c=(a.sub.4, a.sub.6, a.sub.7). (We define a.sub. so that a.sub. does not depend on the order in which the elements of are listed; e.g., a=(a.sub.1, a.sub.2, a.sub.3, a.sub.5, a.sub.8) for ={2,3,1,5,8}.)

(15) We will consider matrices over arbitrary finite fields .sub.q={0, 1, . . . , q−1} with q a prime power. The notation .sub.q.sup.m×n denotes the set of all m-by-n matrices with elements from .sub.q. Thus, A∈.sub.q.sup.m×n indicates that A is a matrix with m rows and n columns. When we need to refer to the elements of A∈.sub.q.sup.m×n, we use the notation a.sub.i,j to denote the element in the ith row and jth column of A, for 1≤i≤m, 1≤j≤n. A matrix P∈.sub.q.sup.n×n is called a permutation matrix if P is a 0-1 matrix that has exactly one 1 in each row and in each column. A matrix A∈.sub.q.sup.n×n is called lower-triangular if a.sub.i,j=0 for all 1≤i<j≤n. A matrix A∈.sub.q.sup.n×n is called upper-triangular if a.sub.i,j=0 for all 1≤j<i≤n. A matrix A∈.sub.q.sup.n×n is called strictly lower triangular if a.sub.i,j=0 for all 1≤i<j≤n and a.sub.i,j≠0 for at least one a.sub.i,j with indices 1≤j<i≤n. A matrix A∈.sub.q.sup.n×n is called strictly upper triangular if a.sub.i,j=0 for all 1≤j<i≤n and a.sub.i,j≠0 for at least one a.sub.i,j with indices 1≤i<j≤n. A matrix A is called diagonal if a.sub.i,j=0 for all i≠j. The diagonal matrix with is on the diagonal is called the identity matrix and denoted I. A matrix A∈.sub.q.sup.n×n is called non-singular or invertible if there exists a matrix B∈.sub.q.sup.n×n (called the inverse of A) such that AB=BA=I. If it exists, the inverse of A is denoted A.sup.−1. A matrix A∈.sub.q.sup.n×n is called upper-triangular Toeplitz with impulse response c=(c.sub.0, c.sub.1, . . . , c.sub.n-1)∈.sub.q.sup.n if A is an upper-triangular matrix and a.sub.i,j=c.sub.j-i for j≥i, i.e., if A has the form

(16) $A=\left[\begin{array}{ccccc}{c}_0& c_1& c_2& \mathrm{.Math.}& c_{n-1}\\ 0& c_0& c_1& \mathrm{.Math.}& c_{n-2}\\ 0& 0& c_0& \mathrm{.Math.}& c_{n-3}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ 0& 0& 0& \mathrm{.Math.}& c_0\end{array}\right].$
The Kronecker product of two matrices A∈.sub.q.sup.m×n and B∈.sub.q.sup.k×l is defined as the matrix

(17) $A.Math.B=\left[\begin{array}{ccccc}{a}_{1,1}B& a_{1,2}B& a_{1,3}B& \mathrm{.Math.}& a_{1,n}B\\ a_{2,1}B& a_{2,2}B& a_{2,3}B& \mathrm{.Math.}& a_{2,n}B\\ a_{3,1}B& a_{3,2}B& a_{3,3}B& \mathrm{.Math.}& a_{3,n}B\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ a_{m,1}B& a_{m,2}B& a_{m,3}B& \mathrm{.Math.}& a_{m,n}B\end{array}\right]\in {𝔽}_q^{\mathrm{mk}\times \mathrm{nl}}.$
The nth Kronecker power A.sup..Math.n of a matrix A is defined inductively as A.sup..Math.1=A and A.sup..Math.n=A.Math.A.sup..Math.(n-1) for n≥2.

(18) Initially turning to FIG. 1, a communication system 100 is shown in which embodiments of the present principles may be used. The communication system 100 receives a source data block (SDB) d from a source and delivers it as a decoded source data block (DSDB) {circumflex over (d)} to a destination. (The source and destination are not shown in the figure and fall outside the scope of the present principles.) A frame error is said to occur when the DSDB {circumflex over (d)} does not match the SDB d exactly, i.e., when {circumflex over (d)}≠d. A performance criterion for the communication system 100 is the frame error rate (FER), defined as the probability of decision error, Pr({circumflex over (d)}≠d). It is in general preferable to have a communication system 100 with as small a FER as feasible within constraints on channel bandwidth, equipment cost, system latency, data throughput, etc. The communication system 100 comprises an encoder 110 located at a transmitter side, a channel 120 connecting the transmitter side to a receiver side, and a decoder 130 at the receiver side. The encoder 110 in the communication system 100 receives the SDB d and encodes it into a transmitted code block (TCB) x. The channel 120 comprises a channel input and a channel output. The encoder 110 applies the TCB x to the channel input. The channel receives the TCB x applied to the channel input and produces in response a received code block (RCB) y at the channel output. The decoder 130 receives the RCB y from the channel output and processes the RCB y to produce the DSDB d.

(19) It will be apparent to those skilled in the art that the channel 120 incorporates many functional blocks (such as modulator, digital-to-analog converter, power amplifier, transmit and receive antennas, signal acquisition and synchronization circuitry, analog-to-digital converter, demodulator) that are essential for the operation of a communication system. The present principles are primarily about the design of the encoder 110 and the decoder 130.

(20) We will represent the SDB as a vector d=(d.sub.1, d.sub.2, . . . , d.sub.K), where K is a source block length. Likewise, we will denote the DSDB as a vector {circumflex over (d)}=({circumflex over (d)}.sub.1, {circumflex over (d)}.sub.2, . . . , {circumflex over (d)}.sub.K). Typically, both the SDB d and the DSDB {circumflex over (d)} will be vectors over a common alphabet. We will represent the TCB as a vector x=(x.sub.1, x.sub.2, . . . , x.sub.N), where N is a code block length. After the encoder 110 encodes the SDB d into the TCB x, the TCB x is transmitted over the channel 120 by N successive uses of the channel 120 and the channel produces the RCB y=(y.sub.1, y.sub.2, . . . , y.sub.N) with a certain probability.

(21) For purposes of analyzing the communication system 100, we will use a probabilistic set-up and model the various signals in the system as samples of random signals. In particular, we will regard the SDB d, TCB x, RCB y, and DSDB {circumflex over (d)} as samples of D, X, Y, and {circumflex over (D)}, respectively, and use the standard notation to denote their joint and conditional probabilities. For example, P.sub.D,Y(d, y) will denote the probability that D=d and Y=y, and P.sub.Y|D(y|d) will denote the conditional probability that Y=y given D=d. Unless otherwise specified, we will assume that P.sub.D(d) is the uniform distribution over the range of possible values of the SDB d.

(22) Using the probabilistic set-up, the FER Pr ({circumflex over (d)}≠d) for the communication system 100 is computed using the formula Σ.sub.(d,{circumflex over (d)}):{circumflex over (d)}≠dP.sub.D,{circumflex over (D)}(d,{circumflex over (d)}). If the encoder 110 and the channel 120 are given, the FER depends on the decoder 130. An important type of decoder is the maximum-likelihood (ML) decoder, which sets the DSDB a to the value d′ that maximizes P.sub.Y|D(y|d′). Under the assumption that P.sub.D(d) is the uniform, the ML decoder minimizes the FER. In general, ML decoders are too complex to implement; they mainly serve as benchmarks for assessing the best achievable performance by other more practical decoders.

(23) An important channel model is the discrete memoryless channel (DMC) model. A DMC is characterized by its input alphabet X, output alphabet Y, and transition probabilities W(y|x) for x∈X, y∈Y. The transition probability W(y|x) is the conditional probability that y∈Y is received at the channel output given that x∈X is sent at the channel input. A DMC is memoryless in the sense that the conditional probability of receiving an output block y=y.sub.2, . . . , y.sub.N)∈Y.sup.N given that an input block x=(x.sub.1, x.sub.2, . . . , x.sub.N)∈X.sup.N is sent is given by a product-form expression W.sup.N(y|x)=Π.sub.i=1.sup.NW(y.sub.i|x.sub.i). In the following, we will restrict attention to DMC models with X=F.sub.q, with q=2 being the most important case. Note that the DMC channel model for the channel 120 defines part of the probabilistic model for the communication system 100 by the equation P.sub.Y|X(y|x)=W.sup.N(y|x).

(24) We will use the term code to refer to the mapping d.fwdarw.x from the SBD d to the TCB x. The encoder 110 and the decoder 130 are designed to encode and decode a specific code. There are many types of codes in the prior art, such as convolutional codes and polar codes. The present disclosure introduces a new family of codes called triangular factorization (TF) codes. TF codes will be introduced as a subclass of a broader family of codes that we now define.

(25) Transform codes. A transform code over a finite field .sub.q is a code characterized by a transform matrix G∈.sub.q.sup.N×N a data index set , and a frozen data block (FDB) a∈.sub.q.sup.N-K, wherein N is the code block length, K is the source block length, the data index set is a subset of {1, 2, . . . , N} with cardinality ||=K, and the FDB a is a fixed but arbitrary vector. Throughout the following .sup.c will denote the complement of the data index set in {1, 2, . . . , N}. An encoder for the transform code with parameters (G, , a) maps the SDB d∈.sub.q.sup.K to the TCB x∈.sub.q.sup.N whereby x=vG, wherein v∈.sub.q.sup.N is a data container block (DCB) comprising of a data part v=d and a frozen part v.sub.c=a. The decoding task for transform codes is to estimate the SDB d based on knowledge of the RCB y and the FDB a.

(26) The decoding of a transform code can be thought of as consisting of two steps. The first step is to produce the DDCB {circumflex over (v)} by processing the RCB y; the second step is to obtain the DSDB {circumflex over (d)} by setting {circumflex over (d)}={circumflex over (v)}. (These two steps may be carried out simultaneously in implementing a decoder to save time and reduce equipment complexity.) An ML decoder for a transform code may carry out the first step of the above procedure by calculating the DDCB {circumflex over (v)} by maximizing P.sub.Y|V(y|v) over v∈.sub.q.sup.N subject to the constraint v.sub.c=a.

(27) Relation to polar codes. It will be clear to the person skilled in the art of polar coding that polar codes are a subclass of transform codes. In particular, the standard polar code over .sub.2 is a transform code with parameters (G, , a) wherein G=F.sup..Math.n with

(28) $F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right],$
is chosen with respect to an information-theoretic criterion such as mutual information, and a is typically set to the all-zero vector 0.

(29) Relation to linear codes. A transform code with parameters (G, , a) for which the FDB a is an all-zero vector, a=0, reduces to a linear code, which is a very broad and well-known class of codes in the prior art. For a linear code, the SDB d and the TCB x are related by x=dG′ for a generator matrix G′∈.sub.q.sup.K×N. The generator matrix G′ of the linear code corresponding to a transform code (G, , a=0) is given by G′=G where G∈.sub.q.sup.K×N is defined as the matrix obtained from G by deleting the ith row of G for each i∈.sup.c. In general, the encoder mapping defined by a transform code (G, , a) has the form x=dG′+b wherein G′=G and b=aG.sub.c. Conversely, given a linear code with a generator matrix G′, one may construct an equivalent transform code (G, , a=0) by selecting G as any matrix such that G=G′.

(30) Complexity considerations. We note that using an encoder for a transform code to implement the encoding of an equivalent linear code may reduce encoding complexity significantly. A direct implementation of the mapping x=dG′ (as a vector-matrix product) for a given linear code may be more complex than computing an equivalent transform x=vG with v=d, v.sub.c, =0, and G=G′. While G′ may lack any structure that can be exploited in computing x=dG′, it may be possible to build a computationally useful structure into the transform matrix G by using the additional degrees of freedom available in the choice of the parameters and G.sub.c. For example, in the case of standard polar codes with G=F.sup..Math.n,

(31) 0$F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right],$
the complexity of computing the transform x=vG is O(N log N), while computation of x=dG.sub. without exploiting the structure in G takes O(NK) steps, which may be significantly higher than O(N log N). The present principles aim to find transform codes (G, , a) that can be encoded and decoded at low-complexity by exploiting specially designed structures in the transform matrix G while providing a performance advantage over codes of comparable dimensions in the prior art. The present principles exploit triangular factorizations of matrices to achieve these goals.

(32) Triangular factorizations. Triangular factorizations of matrices is a well-known topic in linear algebra over any field. We are concerned here with the triangular factorizations of the generator matrices G of transform codes. We will state a number of facts about such factorizations without proof. (For proofs, we refer to Section 3.5 of the book “Matrix Analysis, Cambridge University Press, 1985” by R. A. Horn and C. R. Johnson.)

(33) Given a transform code with a generator matrix G∈.sub.q.sup.N×N (singular or non-singular), there exist an upper-triangular matrix U∈.sub.q.sup.N×N a lower-triangular matrix L∈.sub.q.sup.N×N, and permutation matrices P∈.sub.q.sup.N×N and Q∈.sub.q.sup.N×N such that G=PULQ. If G is nonsingular, then there exists a unique factorization of the form G=UDL such that U∈.sub.q.sup.N×N is an upper triangular matrix with 1s on the diagonal, L∈.sub.q.sup.N×N is a lower-triangular matrix with 1s on the diagonal, and D∈.sub.q.sup.N×N is a diagonal matrix with non-zero diagonal entries. In particular, if G belongs to .sub.2.sup.N×N (the binary case) and is non-singular, then there exists a unique factorization G=UL where U∈.sub.2.sup.N×N is an upper-triangular matrix (with is on the diagonal) and L∈.sub.2.sup.N×N is a lower-triangular matrix (with 1s on the diagonal).

(34) Triangular factorizations are used in linear algebra as efficient methods for solving systems of linear equations. The present principles carry triangular factorization methods to the domain of error correction coding. In the following, we will use the term triangular factorization (TF) code with parameters (G.sub.out, G.sub.in, , a) as a more specific way to refer to a transform code (G, , a) when G.sub.out, G.sub.in, and G are related by a triangular factorization of the form G=G.sub.out G.sub.in. Each triangular factorization G=G.sub.outG.sub.in of the transform matrix of a transform code (G, , a) will define a corresponding triangular factorization code. Triangular factorizations are of interest mainly as templates for implementing the encoding or decoding functions in a communication system. The present principles have the goal of designing transform matrices G with triangular factorizations G=G.sub.outG.sub.in so that the resulting transform code provides sufficiently reliable data transmission while at the same time having low-complexity encoding and decoding procedures that exploit special structures designed into G.sub.out and G.sub.in. The present principles in their preferred embodiments will illustrate how this can be done.

(35) Turning to FIG. 2, we see a block diagram showing a TF coding system 200, wherein the TF coding system 200 is an adaptation of the communication system 100 to encoding and decoding of a TF code (G.sub.out, G.sub.in, , a), wherein G.sub.out is an outer transform matrix, G.sub.in is an inner transform matrix, A is a data selector set, and a is a frozen data block (FDB). The TF coding system 200 comprises a TF encoder 210, the channel 120 (which is the same as in FIG. 1), and a TF decoder 230. The TF encoder 210 comprises a data inserter 211, an outer transform 212, and an inner transform 213, wherein the data inserter 211 receives the SDB d and generates a data container block (DCB) v so that v=d and v.sub.c=a. The outer transform 212 receives the DCB v and generates an outer transform block (OTB) u whereby u G=v G.sub.out. The inner transform 213 receives the OTB u and generates the TCB x whereby x=u G.sub.in. The TF encoder 210 sends the TCB x to the channel 120. The channel 120 receives the TCB x and, in response, produces the received code block (RCB) y at the channel output. The TF decoder 230 comprises an inner decoder 231, an outer decoder 232, and a data extractor 233. The TF decoder 230 receives the RCB y from the channel output and passes it to the inner decoder 231. The inner decoder 231 and the outer decoder 232 exchange messages with each other over a message interface. In response to each node metric request sent by the outer decoder 232 over the message interface, the inner decoder 231 computes a node metric and sends the node metric to the outer decoder 232 over the message interface. Each node metric is a function of a plurality of variables, the plurality of variables comprising a node identifier and the RCB y. The outer decoder 232 receives the node metrics generated by the inner decoder 231, computes a decoded data container block (DDCB) V, and passes the DDCB {circumflex over (v)} to the data extractor 233. The data extractor 233 receives the DDCB and extracts the DSDB {circumflex over (d)} by setting {circumflex over (d)}={circumflex over (v)}. In a well-designed TF coding system, the DSDB d is an exact replica of the SDB d with high probability.

(36) An important aspect of the TF coding system 200 is its modular structure in the sense that it is possible to implement the inner decoder 231 and outer decoder 232 independently of each other. More precisely, the inner decoder 231 may be implemented independently of the outer transform G.sub.out and the outer decoder 232 may be implemented independently of the inner transform G.sub.in. Having such modularity in the implementation of the TF decoder 230 is advantageous because one can change the inner transform or the outer transform without having to redesign all parts of the TF decoder 230. In the following, we will discuss in greater detail each part of the TF coding system 200 and present exemplary embodiments for each part.

(37) FIG. 3 shows an exemplary data inserter 300, wherein the exemplary data inserter 300 is a digital logic circuit implementing the data inserter 211 for the specific case N=8, ={4,6,7,8}, and a=(a.sub.1 a.sub.2, a.sub.3, a.sub.4). Accordingly, the exemplary data inserter 300 generates the DCB v=(v.sub.1, v.sub.2, . . . , v.sub.8) from the SDB d=(d.sub.1, d.sub.2, d.sub.3, d.sub.4) so that v.sub.1=a.sub.1, v.sub.2=a.sub.2, v.sub.3=a.sub.3, v.sub.4=d.sub.1, v.sub.5=a.sub.4, v.sub.6=d.sub.2, v.sub.7=d.sub.3, and v.sub.8=d.sub.4. The exemplary data inserter 300 comprises an SDB register 301 for receiving and storing the SDB d, an FDB register 302 for storing the FDB a, and a DCB register 303 for forming and storing the DCB v. The operation of the exemplary data inserter 300 comprises three steps. In the first step, the SDB d is loaded serially into the SDB register 301 under control of a clock (not shown in the figure). In the second step, the SDB d and the FDB a are loaded from their respective registers 301 and 302 in parallel into the DCB register 303. In the third step, the DCB i is shifted serially out of the DCB register 303. It will be clear to the person skilled in the art that there are many other alternative implementations of a data inserter function corresponding to a given pair of parameters (N, , a) using digital circuits or stored program computers. For example, parallel logic operations may be used instead of serial operations where latency is important.

(38) The data inserter 211 can be implemented also on general purpose processors, which may be a better option when it is desired that the data inserter 211 be reconfigurable to different settings of the parameters (N, , a). Turning to FIG. 4, we see an exemplary data inserter algorithm 400 for implementing the data inserter 211 using a general purpose stored program computer, wherein the algorithm 400 is a sequence of instructions written in pseudo-code and is reconfigurable to operate with any given set of parameters (N, , a), wherein N is the code block length, A is the data index set, and a is the FDB. The algorithm 400 receives as input the SDB d and produces as output the DCB v whereby that v=d and v.sub.c=a. The person skilled in the art will have no difficulty in implementing the data inserter 211 on a stored program computer following the logic of the exemplary data inserter algorithm 400.

(39) The data index set . The performance of a TF code depends critically on the choice of the data index set . Since the choice of the data index set is a one-time design problem, the complexity of finding an optimal or near-optimal is not a major concern. Still, an exhaustive search for the best data index set is not feasible given the exponential size of the search space. The present principles can be used with any method for choosing the data index set ; however, a preferred method of constructing the data index set is the score function approach.

(40) Score functions. Let be a set that is admissible as a data index set, i.e., let be such that ⊂{1, 2, . . . , N} and ||=K. A score function associated with is any function s: {1, 2, . . . , N}.fwdarw. (real numbers) that assigns a real number (a score) to each index i∈{1, 2, . . . , N}. In the score function approach, the data index set is chosen as an admissible such that the minimum of s(i) over all i∈ is as large as possible. In other words, in the score function approach, we seek to solve the optimization problem

(41) $\underset{𝒜}{\max }\underset{i\in 𝒜}{\min }{s}_{𝒜}\left(i\right)$
where the maximum is over all admissible . Score functions defined below assume that the coordinates of the DCB v will be decoded in the natural order from 1 to N at the TF decoder 230. The person skilled in the art will have no difficulty in making appropriate changes to the score functions below if some other order of decoding is employed at the TF decoder 230.

(42) We will consider two types of score functions: pointwise and windowed. Pointwise score functions have been used in the prior art for constructing polar codes and Reed-Muller codes. Windowed score functions are a novel approach. Both types of score functions can be used in conjunction with the present principles to improve the prior art. We first give three examples of pointwise score functions.

(43) The Hamming score function is defined as s(i)=w.sub.H(i−1)−χ(i) where W.sub.H is the Hamming weight of an integer (defined below) and χ.sub. is the indicator function of the set (i.e., χ(i)=1 if i∈ and χ(i)=0 if i.Math.). The Hamming weight of an integer k≥0 is defined as w.sub.H(k)=Σ.sub.j=0.sup.n-1b.sub.j, where b.sub.0, b.sub.1, . . . , b.sub.n-1∈.sub.2 are the coefficients in the binary representation k=Σ.sub.j=0.sup.n-1b.sub.j2.sup.j. For example, w.sub.H(13)=3 since 13=1+2.sup.2+2.sup.3. The Hamming score function has the property of being independent of the parameters of the channel 120. The person skilled in the art will recognize that the Hamming score function produces Reed-Muller codes for the special case of a transform code with G=F.sup..Math.n,

(44) $F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right].$
Reed-Muller codes have the largest possible minimum Hamming distance over all codes of a given rate when G=F.sup..Math.n. Minimum Hamming distance is an important parameter in determining the FER performance of codes at high signal-to-noise-ratios. In a simulation study reported below, we will see that the Hamming score function, when it is used as part of the present principles, produces a FER performance that improves the prior art in polar coding and Reed-Muller coding.

(45) The mutual-information score function is defined as s(i)=I(Y; V.sub.i|V.sup.i−1)−χ(i), where

(46) $I\left(Y;V_i|V^{i-1}\right)=\underset{y,v^i}{.Math.}{P}_{Y,V^i}\left(y,v^i\right)\log \frac{P_{Y|V^i}\left(y|v^i\right)}{P_{Y|V^{i-1}}\left(y|v^{i-1}\right)}$
is the conditional mutual information between V.sub.i and Y given V.sup.i−1. Here, V.sub.i is the random variable corresponding to the ith coordinate of the DCB v, V.sup.i−1 is the random vector associated with the initial segment v.sup.i−1 of the DCB v, V.sup.i=(V.sup.i−1,V.sub.i), and Y is the random vector corresponding to the RCB y. The skilled person in the art will recognize that the mutual-information score function produces the standard polar codes for the special case of a transform code with G=F.sup..Math.n,

(47) $F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right].$

(48) The Gallager score function is defined as s(i)=E.sub.p(Y; V.sub.i|V.sup.i−1)−χ(i), where

(49) $E_{\rho }\left(Y;V_i|V^{i-1}\right)=-\frac{1}{\rho }{\log }_2\underset{y,v^{i-1}}{.Math.}{P}_{V^{i-1}}\left(v^{i-1}\right){\left\{\underset{v_i}{.Math.}{P}_{V_i|V^{i-1}}\left(v_i|v^{i-1}\right){P_{Y|V^i}\left(y|v^i\right)}^{1/1+\rho }\right\}}^{1+\rho }$
where ρ>0 is a free parameter (for each value of ρ, we have a different score function). For a discussion of the significance of the Gallager function and its properties, we refer to R. Gallager, “A simple derivation of the coding theorem and some applications,” IEEE Transactions on Information Theory, vol. 11, no. 1, pp. 3-18, January 1965”. The function E.sub.ρ(Y; V.sub.i|V.sup.i−1) is a generalized conditional information. As ρ.fwdarw.0, we have E.sub.ρ(Y; V.sub.i|V.sup.i−1).fwdarw.I(Y; V.sub.i|V.sup.i−1), so the Gallager score function contains the mutual-information score function as a special case. Another important special case of the Gallager score function occurs with ρ=1. We have E.sub.1(Y; V.sub.i|V.sup.i−1)=R.sub.0(Y; V.sub.i|V.sup.i−1), where R.sub.0(Y; V.sub.i|V.sup.i−1) is a conditional cutoff rate. The Gallager score function places more emphasis on the code minimum distance as ρ increases.

(50) The computation of the above score functions is facilitated when the outer transform G.sub.out is an upper-triangular non-singular matrix. In that case, the inverse of G.sub.out is also non-singular and upper-triangular and the initial segments v.sup.i of the DCB v and u.sup.i of the OTB u are related to each other in a one-to-one manner. Hence, E.sub.ρ(Y; V.sub.i|V.sup.i−1)=E.sub.ρ(Y; U.sub.i|U.sup.i−1). Density-evolution techniques can be used to compute E.sub.ρ(Y; U.sub.i|U.sup.i−1) efficiently when the inner transform has sufficient structure, e.g., when G.sub.in=F.sup..Math.n with

(51) $F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right].$

(52) The above score functions are pointwise in the sense that s(i) is defined as the difference of two functions, a pointwise resource function q(i) and a pointwise rate function χ(i). The pointwise resource value q(i) depends on the particular triangular factorization G=G.sub.nutG.sub.in used in the code construction, but is independent of . The pointwise rate χ(i) depends only on . The value s(i) may be interpreted as the difference between an available resource (information available at time i) and a demand (transmission of a source data bit at time i). We choose so as to minimize the shortage of resources. Pointwise score functions are meaningful when decisions are made sequentially one and for all for each bit in the sequence, with no backtracking or look-ahead into the future. Since the present principles are based on using a powerful tree search algorithm as part of an outer code, pointwise score functions are sub-optimal for the present principles. There is need for score functions that can match the score to the characteristics of the search algorithm. The windowed score functions that are introduced next serve this purpose.

(53) For every score function s(i)=q(i)−χ(i) we define a windowed version of s(i) as S(i; k, m)=Σ.sub.j=−k.sup.mw.sub.js(i+j) where k≥0 (a fixed integer) is a lag parameter, m≥0 (a fixed integer) is a lead parameter, and w.sub.j>0 (fixed real numbers) are weight parameters. We extend the definition of s(i) to all integers by setting s(i)=0 for i≤0 or i>N. The window length for a windowed score function S(i; k, m) with lag k and lead m is defined as k+m+1. When we speak of a windowed score function, we implicitly assume that the window length is greater than one. We do not put an upper bound on how large the window length can be. If TF coding with an upper-triangular Toeplitz G.sub.out is used, the window length may be on the same order as the span of the non-zero portion of the first row of G.sub.out.

(54) The index set design problem with a windowed score function is the problem of finding an admissible data index set so that the minimum of S(i; k, m) over all i∈ is maximized.

(55) Clearly, the windowed score functions contain the pointwise score functions as a special case with k=0, m=0, and w.sub.j=1. The motivation for having a non-zero lag and lead is the idea that a search method equipped with a backtracking mechanism will carry out a search within a window of possible choices in a present search neighborhood. Thus, an algorithm for selecting a data index set should pay attention to keeping the ambiguity (source uncertainty minus the channel information) small over a search window rather than at particular decision points.

(56) The above score functions are given for illustrating the general idea that the choice of a data index set is a significantly different optimization problem than that in polar coding. The skilled person in the art will be able to design other score functions to serve the same purposes. All such extensions of the exemplary score function methods presented above fall within the scope of the present disclosure.

(57) The outer transform G.sub.out. The complexity of computing the outer transform u=vG.sub.out is O(N.sup.2) for a general matrix G.sub.out∈.sub.q.sup.N×N, which is prohibitively complex in many applications even for moderate values of N. The present principles recognize that it is important to reduce the complexity of the outer transform by imposing a structure on G.sub.out. To that end, in preferred embodiments of the present principles, we will restrict G.sub.out to be an upper-triangular Toeplitz matrix, characterized by an impulse response c=(c.sub.0, c.sub.1, . . . , c.sub.m)∈.sub.q.sup.m with c.sub.0≠0, and c.sub.m≠0, wherein m is an integer satisfying 1≤m≤N−1. The assumption c.sub.0≠0 ensures that the outer transform matrix G.sub.out has non-zero diagonal entries, which in turn ensures that G.sub.out is nonsingular. The assumption c.sub.m≠0 for some m≥1 ensures that G.sub.out is a strictly upper-triangular matrix. By using a strictly upper-triangular outer transform matrix G.sub.out, we guarantee that the outer transform 212 is a non-trivial operation, which in turn ensures that TF codes in their preferred embodiments do not coincide with certain other codes, such as polar codes, in the prior art. An exemplary outer transform matrix under the above condition is

(58) $G_{\mathrm{out}}=\left[\begin{array}{cccccccc}1& 1& 0& 1& 0& 0& 0& 0\\ 0& 1& 1& 0& 1& 0& 0& 0\\ 0& 0& 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right],$
which corresponds to the impulse response c=(c.sub.0, c.sub.1, c.sub.2, c.sub.3)=(1,1,0,1). When G.sub.out is defined as an upper-triangular Toeplitz matrix with an impulse response c, the outer transform operation u=vG.sub.out can be expressed as a convolution so that u.sub.i=c.sub.0v.sub.i+c.sub.1v.sub.i−1+ . . . c.sub.jv.sub.i−j+ . . . +c.sub.mv.sub.i−m for all i=1, 2, . . . , N, where we interpret v.sub.i−j as 0 if i−j≤0. Thus, the outer transform 212 may be seen as a discrete-time linear time-invariant filter; and the vector c can be interpreted as the impulse response of the linear time-invariant filter (response to the input v=(1, 0, . . . , 0)). It will be known to the person skilled in the art that there are many practical methods of implementing a convolution operation corresponding to an upper-triangular Toeplitz matrix G.sub.out.

(59) FIG. 5 displays an exemplary outer transform circuit 500 that implements the transform u=vG.sub.out for the special case where G.sub.out is an upper-triangular Toeplitz matrix defined by the impulse response c=(1,1,0,1). The exemplary outer transform circuit 500 comprises a serial input port 501, a shift-register 502, a modulo-2 adder 503, a reset circuit 504, and a serial output port 505. The exemplary outer transform circuit 500 uses sequential logic, which requires additional signals such as clock and control logic. These additional signals are not shown in FIG. 5 in order not to clutter the diagram with unnecessary detail. The person skilled in the art will have no difficulty in providing the missing details. The shift-register 502 comprises three registers connected in tandem, a first register 502a, a second register 502b, and a third register 502c. Each shift register 502a, 502b, 502c can hold one bit, which is either 0 or 1. The modulo-two adder 503 computes the modulo-2 sum (equivalently the exclusive-or (XOR)) of the logic signals at the input port 501, the output of the first register 502a, and the output of the third register 502c. The logic signal at the output of register 502b is excluded from the modulo-2 sum because c.sub.2=0. Initially, with the rising edge of the first clock tick, the contents of the shift register 502 are initialized to 0 by the reset circuit 504 and the first bit v.sub.1 of the DCB v appears as a valid logic signal at the serial input port 501. With the rising edge of the second clock tick, the modulo-2 adder 503 computes the first bit u.sub.1 of the OTB u and sends it out at the serial output port 505, the first bit v.sub.1 is shifted into the first register 502a, the content of the first register 502a moves into the second register 502b, the content of the second register 502b moves into the third register 502c, and the second bit v.sub.2 of the DCB v appears as a valid logic signal at the serial input port 501. Thus, before the rising edge of the third clock tick, the contents of the shift register 502 read (v.sub.1, 0,0) and the second bit v.sub.2 of the DCB v is available at the serial input port 501 for the next round of modulo-2 addition. The operation of the exemplary outer transform circuit 500 continues in this manner, producing u.sub.1=v.sub.1, u.sub.2=v.sub.1+v.sub.2, u.sub.3=v.sub.2+v.sub.3, u.sub.q=v.sub.1+v.sub.3+v.sub.4, u.sub.5=v.sub.2+v.sub.4+v.sub.5, u.sub.6=v.sub.3+v.sub.5+v.sub.6, u.sub.7=v.sub.4+v.sub.6+v.sub.7, and u.sub.8=v.sub.5+v.sub.7+v.sub.8. For example, if v=(1,1,0,0,1,0,1,1), then u=(1,0,1,1,0,1,1,1). As the eighth bit u.sub.8 of the OTB u is sent out at the serial output port 505, the reset circuit 504 is activated and the circuit becomes ready for accepting the next DCB. It takes exactly 8 clock ticks to complete one round of the outer transform operation. The exemplary outer transform circuit 500 can operate without time gaps between outer transform operations on successive DCBs.

(60) Following the model of the exemplary outer transform circuit 500, one can readily implement a general convolution operation corresponding to any upper triangular Toeplitz matrix. If the DCB v is N-dimensional and the impulse response is of the form c=(c.sub.0, c.sub.1, . . . , c.sub.m), then a shift register with m stages is required and it takes N clock cycles to complete one round of the outer transform operation.

(61) The person skilled in the art will know that the method of computing a convolution as presented in FIG. 5 is well known and that there are many alternative circuits for computing a convolution, such as circuits using parallel processing and/or pipelining in order to improve data throughout or decrease latency.

(62) The inner transform G.sub.in. The inner transform operation x=uG.sub.in has complexity O(N.sup.2) for a general matrix G.sub.in∈.sub.q.sup.N×N, which may be prohibitive for practical implementations. The present principles aim to reduce the complexity of the inner transform operation by imposing a structure on G.sub.in. In preferred embodiments of the present principles, G.sub.in is restricted to have a Kronecker product form: G.sub.in=L.sub.1.Math. . . . .Math.L.sub.n, where L.sub.i∈.sub.q.sup.N.sup.i.sup.×N.sup.i is a lower-triangular matrix with N.sub.i≥2 for each i=1, 2, . . . , n. The resulting G.sub.in is a N-by-N lower-triangular matrix with N=Π.sub.i=1.sup.nN.sub.i. If the Kronecker factors L.sub.1, . . . , L.sub.n of G.sub.in are chosen suitably, the complexity of computing the inner transform x=uG.sub.in can be reduced from O(N.sup.2) to O(N log N). For example, if

(63) $L_i=F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$
for each i=1, 2, . . . , n, then G.sub.in=F.sup..Math.n becomes the polar transform matrix in polar coding and the complexity of the inner transform reduces to O(N log.sub.2 N). For completeness, we present below a circuit for implementing x=uG.sub.in for this important special case with G.sub.in=F.sup..Math.n.

(64) FIG. 6 shows an exemplary polar transform circuit 600 that can be used to implement the inner transform 213 in the special case where

(65) $G_{\mathrm{in}}=F^{.Math.3}=\left[\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 1& 1& 0& 0\\ 1& 0& 1& 0& 1& 0& 1& 0\\ 1& 1& 1& 1& 1& 1& 1& 1\end{array}\right].$
The exemplary polar transform circuit 600 comprises a parallel input port 601, a parallel output port 602, and an internal logic circuit. The internal logic is combinational. The circuit is driven by input signals (u.sub.1, . . . , u.sub.8) applied at the parallel input port 601 and produces (after some signal propagation delay) output signals (x.sub.1, . . . , x.sub.8) at the parallel output port 602. By tracing the input logic signals through the circuit, it can be verified that the output signals are related to the input signals by x.sub.1=u.sub.2 ⊕u.sub.3 ⊕u.sub.4 ⊕u.sub.5 ⊕u.sub.6 ⊕u.sub.7 ⊕u.sub.8, x.sub.2=u.sub.2 ⊕u.sub.4 ⊕u.sub.6 ⊕u.sub.8, x.sub.3=u.sub.3 ⊕u.sub.4 ⊕u.sub.7 ⊕u.sub.8, x.sub.4=u.sub.4 ⊕u.sub.8, x.sub.5=u.sub.5⊕u.sub.6 ⊕u.sub.7 ⊕u.sub.8, x.sub.6=u.sub.6 ⊕u.sub.8, x.sub.7=u.sub.7 ⊕u.sub.8, and x.sub.8=u.sub.8, wherein ⊕ denotes the logic exclusive or (XOR) operation. These relations between the logic signals are the same as the algebraic relations one obtains between the vectors u=(u.sub.1, . . . , u.sub.8)∈.sub.2.sup.8 and x=(x.sub.1, . . . , x.sub.8)∈.sub.2.sup.8 by carrying out the matrix multiplication x=uF.sup..Math.3 Thus, it is verified that the circuit 600 implements correctly the inner transform operation for the exemplary case G.sub.in=F.sup..Math.3. For generalization of the circuit 600 to the case G.sub.in=F.sup..Math.n with arbitrary n, we refer to the prior art on polar coding. The prior art on polar coding contains many options for implementing a polar transform using either hardware or software. All such implementation options can be used in physical realizations of the present principles.

(66) We have presented exemplary implementation options for each individual part of the TF encoder 210. Next, we will present an embodiment of the TF encoder 210 that brings those parts together.

(67) A preferred embodiment of TF encoder 210. In the preferred embodiment of the TF encoder 210, the TF code (G.sub.out, G.sub.in, , a) is a code over a finite field .sub.q, wherein the outer transform matrix G.sub.out is a nonsingular strictly upper-triangular Toeplitz matrix defined by an impulse response c; the inner transform matrix G.sub.in is a strictly lower-triangular matrix that has a Kronecker-product form G.sub.in=L.sub.1 .Math. . . . .Math.L.sub.n, wherein n≥1 and L.sub.i ∈.sub.q.sup.N.sup.i.sup.×N.sup.i is a lower-triangular matrix, having N.sub.i≥2 rows (equivalently columns) for each i=1, 2, . . . , n; the data index set and the FDB a are left arbitrary. The preferred embodiment of the TF encoder 210 takes can be implemented using the exemplary implementations in FIGS. 3, 4, 5, and 6.

(68) We turn now to developing a suitable decoder for an arbitrary but fixed TF code (G.sub.out, G.sub.in, , a) constructed in accordance with the preferred embodiment of the TF encoder 210. We observe that, since G.sub.out is an upper-triangular matrix, the mapping u=VG.sub.out from v∈.sub.q.sup.N to u∈.sub.q.sup.N is causal in the sense that u.sup.i=(u.sub.1, . . . , u.sub.i) is determined by v=(v.sub.1, . . . , v.sub.i), for all i∈{1, 2, . . . , N}. The causal nature of the outer transform G.sub.out makes it possible to represent the mapping v.fwdarw.u=vG.sub.out in the form of a tree, which we call the outer transform (OT) tree. The OT tree has N+1 levels indexed by integers 0 to N. At level 0 of the OT tree, there is only a root node. At level i∈{1, 2, . . . , N} of the OT tree, there are q.sup.i nodes, with one node for each v.sup.i∈.sub.q.sup.i. The nodes at the final level (level N) of the OT tree are called leaf nodes. There are q.sup.N leaf nodes in the OT tree, one for each v∈.sub.q.sup.N.

(69) Next we show that the TF code is a tree code. Let us call a leaf node v in the OT tree admissible if v.sub.c=a. There are q.sup.K admissible leaf nodes for a TF code ||=K. The code tree for the TF code (G.sub.out, G.sub.in, , a) is defined as the subtree of the OT that one obtains after deleting all branches in the OT tree that do not lie on the path from the root to at least one admissible leaf node. The path in the code tree corresponding to the DCB v is called the correct path. Using the tree representation, the decoding task for a TF code may be seen as a search for the correct path through the TF code tree using the information provided by the RCB y. This viewpoint shows that various tree search algorithms can be adapted to the decoding task. For example, Viterbi decoding is derived from breadth-first search, sequential decoding from depth-first search with backtracking, successive-cancellation decoding from depth-first search without backtracking, and successive cancellation list decoding from beam search.

(70) Having reformulated the task of the TF decoder 230 as a tree-search problem, we now turn our attention to the implementation of generic tree-search algorithms within the modular architecture of the TF decoder 230 shown in FIG. 2. Specifically, we discuss how the various tasks involved in a generic tree-search algorithm can be partitioned between the inner decoder 231 and the outer decoder 232. We will see that thanks to the upper-triangular form of the outer transform G.sub.out such a partition is possible. We begin by recalling from linear algebra that the inverse of a non-singular upper-triangular matrix is also upper-triangular. Hence, the inverse mapping v=u(G.sub.out).sup.−1 is causal in the same sense that the forward mapping u=vG.sub.out is causal. In other words, the prefixes v.sup.i=(v.sub.1, . . . , v.sub.i) and u.sup.i=(u.sub.1, . . . , u.sub.i) uniquely determine each other for each i∈{1, 2, . . . , N} and either prefix can be used to identify the nodes in the OT tree uniquely. Thanks to this property, the metric traffic across the interface between the inner decoder 231 and the outer decoder 232 can be carried out using the OTB prefixes u.sup.i as node identifiers. We will see below that passing metric request and metric value messages with OTB prefixes u.sup.i as node identifiers makes it possible to partition the tree-search tasks into modules as shown in FIG. 2.

(71) A preferred embodiment of the TF decoder 230. In the preferred embodiment of the TF decoder 230, the constraints on the TF code parameters (G.sub.out, G.sub.in, , a) are the same as in the preferred embodiment of the TF encoder and need not be specified separately. Thus, if the preferred embodiments of the TF encoder 210 and the TF decoder 230 are compatible with each other. In the preferred embodiment of the TF decoder 230, the outer decoder 232 uses a tree-search algorithm to search for the correct path through the OT tree, wherein the tree-search algorithm assesses the likelihood of a node u.sup.i being on the correct path by means of a node metric Γ(u.sup.i, y), wherein the node metric Γ(u.sup.i, y) is designed to drift up on the correct path and drift down on incorrect paths. The outer decoder 232 requests the calculation of a node metric Γ(u.sup.i, y) from the inner decoder 231 by presenting the node identifier u.sup.i to the inner decoder 232. Upon receiving such a request, the inner decoder 231 is responsible for computing the node metric Γ(u.sup.i, y). The metric Γ(u.sup.i, y) is designed to be such that it requires no knowledge of the outer code parameters (G.sub.out, , a) so that the inner decoder 231 can be configured independently of the outer code. The outer decoder 232 uses the metric values received from the inner decoder 231 to carry out a tree search. At the end of the tree search, the inner decoder produces the DDCB {circumflex over (v)} and passes the DDCB {circumflex over (v)} to the data extractor 233. The data extractor 233 computes the DSDB {circumflex over (d)} by setting {circumflex over (d)}={circumflex over (v)}.

(72) The scope of the preferred embodiment of the TF decoder 230 covers any tree-search algorithm and any node metric with the properties specified above. More specific choices for the search algorithm and the node metric are discussed below in preparation for the description of the most preferred embodiment of the TF decoder 230. We begin with the node metric.

(73) The Fano metric. An exemplary node metric that can be used to implement the preferred embodiment of the TF decoder 230 is the Fano metric [FAN1963], defined as

(74) 0$\Gamma \left(u^i,y\right)={\log }_2\frac{P_{Y|U^i}\left(y|u^i\right)}{P_Y\left(y\right)}-B_i$
where B.sub.i is a bias term. In regular convolutional coding and sequential decoding, the bias term is constant; here, we allow the bias term to be time-varying. The reason for using a time-varying Fano metric is to ensure that the Fano metric maintains a positive drift E[Γ(u.sup.i, y)] on the correct path in the TF code tree despite the fact that the amount of information

(75) $E\left[{\log }_2\frac{P_{Y|U^i}\left(y|u^i\right)}{P_Y\left(y\right)}\right]$
coming from the channel by way of the Fano metric is time-varying. The use of a Fano metric with a time-varying bias term is a feature that sets the present principles apart from the prior art.

(76) In calculating the Fano metric, the inner decoder 231 makes an approximation by assuming that all paths in the OT code tree are admissible (ignoring that the TF code tree is a subtree of the OT tree), which amounts to assuming that the prefixes U.sup.i are equally likely over their 2.sup.i possible values in the OT code tree. This approximation simplifies the calculation of the Fano metric and makes it independent of the details of the TF code. We leave it to the outer decoder 232 to apply a correction to the metric values received from the inner decoder 231 so that the tree-search does not deviate to paths that are not in the TF code tree.

(77) The Fano metric can be computed incrementally by writing Γ(u.sup.i,y)=Σ.sub.j=1.sup.iγ(u.sub.j,y|u.sup.j-1) where

(78) $\gamma \left(u_j,y|u^{j-1}\right)={\log }_2\frac{P_{Y|U^j}\left(y|u^j\right)}{P_{Y|U^{j-1}}\left(y|u^{j-1}\right)}-b_j$
with b.sub.j=B.sub.j−B.sub.j-1. For computational purposes, it may be more advantageous to use the Bayes' rule and the assumption that

(79) $P_{U_j|U^{j-1}}\left(u_j|u^{j-1}\right)=1\text{/}2,$
and rewrite the branch metrics as

(80) $\gamma \left(u_j,y|u^{j-1}\right)={\log }_2{P}_{U_j|Y,U^{j-1}}\left(u_j|y,u^{j-1}\right)-b_j+1.$

(81) A preferred method of choosing the bias terms is to set B.sub.i=αI(U.sup.i; Y) for some constant 0<α<1. Then, the drift of the Fano metric at the ith node on the correct path equals E[Γ(U.sup.i,Y)]=(1−α)I(U.sup.i; Y), which is positive, as desired. When B.sub.i=αI(U.sup.i; Y), the branch metric bias terms become b.sub.j=αI(U.sub.j; Y|.sup.j-1) and the expected values of the branch metrics along the correct path become E[γ(u.sub.j,y|u.sup.j-1)]=(1−α)I(U.sub.j; Y|U.sup.j-1), which are also positive. This discussion shows the need for having a time-varying bias term in applying the Fano metric in connection with a tree-search algorithm for decoding a TF code.

(82) The skilled person in the art will recognize that, in the important special case where the inner transform G.sub.in is a polar transform G.sub.in=F.sup..Math.n, the probability

(83) $P_{U_j|Y,U^{j-1}}\left(u_j|y,u^{j-1}\right)$
can be computed at low-complexity using the method of successive cancellation decoding of polar codes. In fact, in this case, one has the formula

(84) $P_{U_j|Y,U^{j-1}}\left(u_j|y,u^{j-1}\right)=\frac{W_N^{\left(j\right)}\left(y,u^{j-1}|u_j\right)}{W_N^{\left(j\right)}\left(y,u^{j-1}|0\right)+W_N^{\left(j\right)}\left(y,u^{j-1}|1\right)}$
where W.sub.N.sup.(j) denotes the jth bit channel created by the polar transform. Furthermore, in this case, the mutual information terms I(U.sup.i; Y) and I(U.sub.j; Y|U.sup.j-1) that appear in the recommended forms of the bias terms can be computed in complexity O(N log N) using the density-evolution technique for the design of polar codes.

(85) We now specify in further detail how the metric messages are exchanged at the interface between the inner decoder 231 and the outer decoder 232. Suppose that the outer decoder is looking forward from a node u.sup.i−1 in the TF code tree at some point during the execution of a tree search algorithm. If i∈, then there are two possible extensions (u.sup.i−1,0) and (u.sup.i−1,1) in the TF code tree of the node u.sup.i−1, and the outer decoder 232 requests both node metrics, Γ((u.sup.i−10),y) and Γ((u.sup.i−11), y), from the inner decoder 231. If i.Math., then there is only one possible extension in the TF code tree of the node u.sup.i−1, either (u.sup.i−1,0) or (u.sup.i−1,1), and the outer decoder 232 requests the node metric for the valid extension of the node u.sup.i−1 and sets the node metric of the invalid extension of the node u.sup.i−1 to −∞.

(86) As an option, the outer decoder may modify all received node metrics by applying an outer code specific and level specific bias to each received node metric. Such a procedure has been observed to yield improved results in simulations.

(87) Sequential decoding. As mentioned above, sequential decoding is a decoding algorithm for convolutional codes developed by Wozencraft [WOZ1961]. Fano [FAN1963] developed a practical method of implementing sequential decoding that is especially suitable for hardware implementation. Zigangirov [ZIG1966] and Jelinek [JEL1969] developed a version of sequential decoder known as the stack decoder, which is easier to understand than Fano's algorithm but consumes considerably more memory resources. Both versions of sequential decoding can be used as a tree-search heuristic in implementing the outer decoder 232. Here, we will describe the stack decoder since it is much easier to explain.

(88) FIG. 7 is a flowchart of a stack decoder 700, wherein the stack decoder is a decoding algorithm for tree codes and can be run on a general purpose computer with a random access memory and processor unit. The term stack in the flowchart 700 refers to a data structure, generally known as a priority queue. The stack resides in the random access memory and contains a plurality of nodes, wherein each node on the stack is a data record associated with a node in a tree code. The nodes on the stack are ordered in decreasing order of a node metric. The node on the stack with the highest metric value is referred to as the stack-top node. The stack decoder 700 comprises an initialization step 701, a look forward step 702, a termination check step 703, a time-out check step 704, a regular exit step 705, and a time-out step 706. In the initialization step 701, the stack is cleared, a root node of the tree is placed on the stack as the stack-top node with a metric value of zero, a cycle counter is set to zero, and control is passed to the look forward step 702. In the look forward step 702, the cycle counter is incremented by one, the stack-top node is removed from the stack, the metric values of all child nodes of the removed stack-top node are requested and received from a metric computer, the child nodes are inserted into the stack, all nodes on the stack are re-ordered with respect to their metric values in descending order, and control is passed to the termination check step 703. In the termination check step 703, it is checked if the present stack-top node is a leaf node in the tree; if the answer is YES, control is passed to the regular exit step 705; else (if the answer is NO), control is passed to the time-out check step 704. In the regular exit step 705, the stack decoder 700 outputs the stack-top node as the final decoder decision and the algorithm terminates. In the time-out check step 704, a check is made if the cycle counter exceeds a time-out limit; if the answer is YES, control is passed to the time-out exit step 706; else if the answer is NO, control is passed to the look forward step 702. In the time-out exit step 706, the stack decoder outputs the current stack-top node as the final decoder decision with an indication that there was a time-out.

(89) It will be clear to those skilled in the art that the stack decoder 700 described above can be used to implement the preferred embodiment of the TF decoder 230 by assigning the responsibility of maintaining the stack and generating node metric requests to the outer decoder 232 and the responsibility of computing the node metric values to the inner decoder 231. The splitting of the functions of node metric calculation and tree search can be seen as a method of forward (inner decoding) and backward (outer decoding) substitution akin to solving a system of linear equations using triangular factorization methods in linear algebra.

(90) A most preferred embodiment of the TF encoder 210. The most preferred embodiment of the TF encoder 210 is a special case of the preferred embodiment of the TF encoder 210 such that the field .sub.q is restricted to be the binary field .sub.2 (q=2), the data index set is constructed using a score function, the outer transform matrix G.sub.out is a non-singular strictly upper-triangular Toeplitz matrix defined by an impulse response c, and the inner transform matrix is chosen as G.sub.in=F.sup..Math.n where

(91) $F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right].$
It will be clear to the person skilled in the art that the preferred embodiment of the transform encoder can be implemented by combining the exemplary implementations presented in FIGS. 3, 4, 5, and 6.

(92) A most preferred embodiment of the TF decoder 230. In the most preferred embodiment of the TF decoder 230, the constraints on the TF code parameters (G.sub.out, G.sub.in, , a) are the same as in the most preferred embodiment of the TF encoder 210 and need not be specified separately. In the most preferred embodiment of the TF decoder 230, the inner decoder 231 computes the Fano metric and the outer decoder 232 implements the sequential decoding algorithm by adjusting the Fano metric received from the inner decoder 231 as described above. A matching pair of the most preferred embodiment of the TF encoder 210 and the most preferred embodiment of the TF decoder 230 constitute a most preferred embodiment of the TF coding system 200.

(93) Turning to FIG. 8A, we see simulation results 800 for comparing the present principles with the prior art. The simulation results 800 comprise five performance curves 801 through 805. The performance curve 805 belongs to an exemplary TF coding system constructed in accordance with the most preferred embodiment of the present principles (namely, the most preferred embodiment of the TF encoder 210 and the most preferred embodiment of the TF decoder 230). The simulation results show a clear advantage for the present principles. For a fair comparison, all five coding systems in FIG. 8A are codes over the binary field .sub.2, and have a common code block length N=128, and a common source block length K=64 for an overall coding rate of R=½. The channel used in the simulations is a binary-input memoryless channel with input alphabet X=.sub.2, output alphabet Y= (real numbers), and channel transition probability density function

(94) $W\left(y|x\right)=\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{-\frac{{\left(y-s\right)}^2}{2{\sigma }^2}}$
where x∈X, y∈Y, and s=1 if x=0 and s=−1 if x=1. Those skilled in the art will recognize that this channel as a model for binary signaling over an Additive White Gaussian Noise (AWGN) channel. We will refer to this channel as “the AWGN channel” in the rest of this discussion. The AWGN channel is characterized by its signal-to-noise ratio (SNR) which is defined as 1/σ.sup.2. In the simulation study, the SNR parameter is varied from 0 dB to 5 dB in steps of 0.5 dB and the FER values are measured at each SNR point by carrying out trials until the number of trials reaches hundred thousand or the number of frame errors reaches 100 (whichever occurs first). Details of the simulation study are as follows.

(95) The performance curve 805 belongs to a TF coding system constructed in accordance with the most preferred embodiment of the TF coding system so that the outer transform matrix G.sub.out is an upper-triangular Toeplitz matrix characterized by the impulse response c=(1,0,1,1,0,1,1), the inner transform is G.sub.in=F.sup..Math.7 with

(96) $F=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right],$
the data index set is constructed using the Hamming score function (={16, 24, 28, 30, 31, 32, 40, 44, 46, 47, 48, 52, 54, 55, 56, 58, 59, 60, 61, 62, 63, 64, 72, 76, 78, 79, 80, 84, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 100, 102, 103, 104, 106, 107, 108, 109, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128}, which coincides with the Reed-Muller code), the FDB a equals 0, the inner decoder 231 uses the Fano metric, and the outer decoder 232 uses the sequential decoding algorithm. It is instructive to analyze the code rates for this scheme. As stated before, the present principles aim to operate at rates R.sub.out=R and R.sub.in=1 for a given overall code rate R. Here, we have R=½. The outer and inner code rates are R.sub.out=64/112 and R.sub.in=112/128. We have R.sub.out=64/112 because the smallest element of the data index set is equal to 16, so the first 16 frozen bits of the DCB v propagate through the causal transform u=vG.sub.out and the first 16 bits of the OTB u remain frozen. Hence, effectively, the outer code has a code block length 128−16=112 instead of 128. This example shows that although the present principles aim for the rates R.sub.out=R and R.sub.in=1, this objective may not be fulfilled perfectly due to the artefact that the first element of the data index set may not be 1.

(97) The performance curve 801 belongs to a Reed-Muller code with successive cancellation (SC) decoding. The Reed-Muller code here is obtained as a special instance of transform coding (with G.sub.out=I (the identity matrix), G.sub.in=F.sup..Math.7, chosen using the Hamming score function, and a=0). So, the comparison of 801 with 805 shows the benefits of using an outer transform in accordance with the present principles. As a (degenerate) concatenated coding system, the Reed-Muller code here has rates R.sub.out=1, R.sub.in=½, and R=½.

(98) The performance curve 802 belongs to a polar code with successive cancellation decoding. This case may also be seen as a degenerate form of transform coding (with G.sub.out=I, G.sub.in=F.sup..Math.7, chosen using the mutual-information score function (optimized at 3 dB SNR), and a=0). The comparison of 802 with 805 shows the benefits of using an outer transform in accordance with the present principles. As a (degenerate) concatenated coding system, the polar code here has rates R.sub.out=1, R.sub.in=½, and R=½.

(99) The performance curve 803 belongs to a concatenated coding system (in the sense of Forney) for which the outer code is a 4-bit cyclic-redundancy-check (CRC) code, the inner code is a Reed-Muller code, and the decoder is a CRC-aided successive-cancellation-list (CA-SCL) decoder with list size 32 and CRC length 4 bits. (The 4-bit CRC yields the best performance among alternative lengths of 0, 4, 8, 16 bits.) The code rates are R.sub.out=64/68, R.sub.in=68/128, and R=½.

(100) The performance curve 804 belongs to a concatenated coding system for which the outer code is an 8-bit CRC code, the inner code is a polar code optimized for 3 dB SNR, and the decoder is a CA-SCL decoder with list size 32 and CRC length 8 bits. (The 8-bit CRC yields the best performance among alternative lengths of 0, 4, 8, 16 bits.) The code rates are R.sub.out=64/72, R.sub.in=72/128, and R=½.

(101) To summarize, FIG. 8A shows that the exemplary TF coding system provides significantly better performance than the prior art in Reed-Muller and polar codes even when the latter are decoded using a fairly complex CA-SCL decoder. It is worth noting that this significant improvement is obtained at a relatively small block length of N=128. Codes at such short block lengths are usually employed to protect sensitive control information in communication systems, such as telemetry information in space communications and resource allocation information in cellular systems. Thus, FIG. 8A demonstrates the practical utility and potential applications of the present principles. It is also worth noting that the rate pair (R.sub.out, R.sub.in) for the present principles is substantially different than those for the other codes that represent the prior art. The present principles set the rate R.sub.out near ½ and R.sub.in near 1 while the prior art techniques set R.sub.out near or equal to 1 and R.sub.in near or equal to ½. While the present principles rely mainly on a strong outer code for error correction, the prior art methods rely mainly on the strength of the inner code for error correction.

(102) Next, we turn to FIG. 8B to discuss the design of the TF coding system whose performance is shown by the curve 805. FIG. 8B shows a graph 810 that compares information and rate allocation profiles for the present principles and the prior art. All curves in FIG. 8B are computed for the AWGN channel at 3 dB SNR. The capacity and the cutoff rate of the AWGN channel at 3 dB SNR are given by I(W)=0.72 bits and R.sub.o(W)=0.55 bits, respectively.

(103) The prior art is represented in FIG. 8B by the curves 811, 812, and 813, which are, respectively, the cumulative capacity i.Math.I(W), the cumulative cutoff rate i.Math.R.sub.0(W), and the cumulative rate i.Math.R versus the index variable i. The numerical values for the curves 811, 812, and 813 represent a convolutional code of rate R=½. (Actually, a more precise plot of the cumulative rate for a convolutional code of rate 1/2 would have a jump of 1 bit at odd time indices. So, the curve 813 is an approximation.) We see that the rate profile 813 for the convolutional code of rate 1/2 lies below the cutoff rate profile 812; so, we anticipate that a sequential decoder can be used to decode the convolutional code without excessive computational complexity. On the other hand, the gap between the cutoff rate profile 812 and the rate profile 813 is quite narrow; so, we also anticipate that occasionally there will be long searches that will result in decoder time-outs and/or buffer overflows.

(104) The present principles are represented in FIG. 8B by the curves 814, 815, and 816, which are, respectively, the cumulative capacity I(V.sup.i; Y)=Σ.sub.j=1.sup.iI(V.sub.j; Y|V.sup.j-1), the cumulative cutoff rate Σ.sub.j=1.sup.iR.sub.0(V.sub.j; Y|V.sup.j-1), and the cumulative rate Σ.sub.j=1.sup.iχ(j) as a function of the index variable i∈{1, 2, . . . , N}. The numerical values for the curves 814, 815, 816 belong to the TF code whose performance was discussed above in connection with the curve 805. The curves 814 and 815 exhibit, respectively, a polarization effect (as seen at the outer decoder 232) for the channel capacity and cutoff rate. For small values of the index i, the cumulative capacity 814 and the cumulative cutoff rate 815 rise very slowly, indicating a polarization of the respective quantities to 0; for large values of the index i, the slope of the curves 814 and 815 approach 1, indicating a polarization of the respective quantities to 1. It is noteworthy that the TF coding system boosts the cutoff rate in the sense that the final value of the curve 815 is significantly larger than the final value of the curve 812. The TF code boosts the cutoff rate thanks to the effect of the inner transform G.sub.in and a sequential decoder situated inside the outer decoder 232 can take advantage of the increased cutoff rate. We observe that the rate curve 816 has a widening gap with the cutoff rate curve 815, which translates to reduced complexity (in terms of the mean and higher order moments of the computation) in sequential decoding.

(105) FIG. 9 illustrates an example wireless network within which error correction coding may be implemented according to this disclosure. The embodiment of the wireless network 900 shown in FIG. 9 is for illustration only. Other embodiments of the wireless network 900 could be used without departing from the scope of this disclosure. The wireless network 900 includes an eNodeB (eNB) 901, an eNB 902, and an eNB 903. The eNB 901 communicates with the eNB 902 and the eNB 903. The eNB 901 also communicates with at least one Internet Protocol (IP) network 930, such as the Internet, a proprietary IP network, or other data network.

(106) Depending on the network type, other well-known terms may be used instead of “eNodeB” or “eNB,” such as “base station,” “BS,” or “access point.” For the sake of convenience, the terms “eNodeB” and “eNB” are used in this patent document to refer to network infrastructure components that provide wireless access to remote terminals. Also, depending on the network type, other well-known terms may be used instead of “user equipment” or “UE,” such as “mobile station” (or “MS”), “subscriber station” (or “SS”), “remote terminal,” “wireless terminal,” or “user device.” For the sake of convenience, the terms “user equipment” and “UE” are used in this patent document to refer to remote wireless equipment that wirelessly accesses an eNB, whether the UE is a mobile device (such as a mobile telephone or smartphone) or is normally considered a stationary device (such as a desktop computer or vending machine).

(107) The eNB 902 provides wireless broadband access to the network 930 for a first plurality of user equipments (UEs) within a coverage area 920 of the eNB 902. The first plurality of UEs includes a UE 911, which may be located in a small business (SB); a UE 912, which may be located in an enterprise (E); a UE 913, which may be located in a WiFi hotspot (HS); a UE 914, which may be located in a first residence (R1); a UE 915, which may be located in a second residence (R2); and a UE 916, which may be a mobile device (M) like a cell phone, a wireless laptop, a wireless personal digital assistant (PDA), tablet, or the like. The eNB 903 provides wireless broadband access to the network 930 for a second plurality of UEs within a coverage area 925 of the eNB 903. The second plurality of UEs includes the UE 915 and the UE 916. In some embodiments, one or more of the eNBs 901-903 may communicate with each other and with the UEs 911-916 using 3G, 4G or 5G, long-term evolution (LTE), LTE-A, WiMAX, or other advanced wireless communication techniques.

(108) Dotted lines show the approximate extents of the coverage areas 920 and 925, which are shown as approximately circular for the purposes of illustration and explanation only. It should be clearly understood that the coverage areas associated with eNBs, such as the coverage areas 920 and 925, may have other shapes, including irregular shapes, depending upon the configuration of the eNBs and variations in the radio environment associated with natural and man-made obstructions.

(109) As described in more detail below, one or more of BS 901, BS 902 and BS 903 include 2D antenna arrays as described in embodiments of the present disclosure. In some embodiments, one or more of BS 901, BS 902 and BS 903 support the codebook design and structure for systems having 2D antenna arrays.

(110) Although FIG. 9 illustrates one example of a wireless network 900, various changes may be made to FIG. 9. For example, the wireless network 900 could include any number of eNBs and any number of UEs in any suitable arrangement. Also, the eNB 901 could communicate directly with any number of UEs and provide those UEs with wireless broadband access to the network 930. Similarly, each eNB 902-903 could communicate directly with the network 930 and provide UEs with direct wireless broadband access to the network 930. Further, the eNB 901, 902, and/or 903 could provide access to other or additional external networks, such as external telephone networks or other types of data networks.

(111) The example channel decoding systems depicted in the figures and described above may be implemented in an eNB (such as eNB 902) and/or a UE (such as UE 916), as described in further detail below.

(112) FIG. 10A illustrates an example user equipment network within which error correction coding may be implemented according to this disclosure. The embodiment of the UE 916 illustrated in FIG. 10A is for illustration only, and the UEs 911-915 of FIG. 9 could have the same or similar configuration. However, UEs come in a wide variety of configurations, and FIG. 10A does not limit the scope of this disclosure to any particular implementation of a UE.

(113) The UE 916 includes an antenna 1005, a radio frequency (RF) transceiver 1010, transmit (TX) processing circuitry 1015 (which may include the encoder 110 in FIG. 1), a microphone 1020, and receive (RX) processing circuitry 1025 (which may include the decoder 130 in FIG. 1). The UE 916 also includes a speaker 1030, a main processor 1040, an input/output (I/O) interface (IF) 1045, a keypad 1050, a display 1055, and a memory 1060. The memory 1060 includes a basic operating system (OS) program 1061 and one or more applications 1062. Either the OS program 1061, one of the applications 1062, or some combination thereof may implement programming for employing error correction coding as described in the various embodiments of FIGS. 1 through 8.

(114) The RF transceiver 1010 receives, from the antenna 1005, an incoming RF signal transmitted by an eNB of the network 900. The RF transceiver 1010 may down-convert the incoming RF signal to generate an intermediate frequency (IF) or baseband signal which would be sent to the receiver (Rx) processing circuitry 1025. The Rx processing circuitry 1025 transmits the processed signal to the speaker 1030 (such as for voice data) or to the main processor 1040 for further processing (such as for web browsing data).

(115) The transmit (Tx) processing circuitry 1015 receives, as at least some input data for the source data block, analog or digital voice data from the microphone 1020 or other outgoing baseband data (such as web data, e-mail, or interactive video game data) from the main processor 1040. The Tx processing circuitry 1015 implements encoding. The RF transceiver 1010 receives the outgoing processed baseband or IF signal from the Tx processing circuitry 1015 and up-converts the baseband or IF signal to an RF signal that is transmitted via the antenna 1005.

(116) The main processor 1040 can include one or more processors or other processing devices and execute the basic OS program 1061 stored in the memory 1060 in order to control the overall operation of the UE 916. For example, the main processor 1040 could control the reception of forward channel signals and the transmission of reverse channel signals by the RF transceiver 1010, the Rx processing circuitry 1025, and the Tx processing circuitry 1015 in accordance with well-known principles. In some embodiments, the main processor 1040 includes at least one programmable microprocessor or microcontroller, while in other embodiments the main processor includes dedicated circuitry (e.g., for systemic and/or non-systematic encoding or decoding processes, puncturing processes, data mapping, etc.) as well as (optionally) programmable logic or processing circuits.

(117) The main processor 1040 is also capable of executing other processes and programs resident in the memory 1060, such as operations for channel quality measurement and reporting for systems having 2D antenna arrays. The main processor 1040 can move data and/or instructions into or out of the memory 1060 as required by an executing process. In some embodiments, the main processor 1040 is configured to execute the applications 1062 based on the OS program 1061 or in response to signals received from eNBs or an operator. The main processor 1040 is also coupled to the I/O interface 1045, which provides the UE 916 with the ability to connect to other devices such as laptop computers and handheld computers. The I/O interface 1045 is the communication path between these accessories and the main controller 1040.

(118) The main processor 1040 is also coupled to the keypad 1050 (which may simply be a single button or may be an array or other set of buttons) and the display unit 1055. The operator of the UE 916 can use the keypad 1050 to enter data into the UE 916. The display 1055 may be a touch screen display or other display capable of rendering text and/or at least limited graphics, such as from web sites, and receiving touch inputs by a user in accordance with known practices. The memory 1060 is coupled to the main processor 1040, and at least a part of the memory 1060 could include a random access memory (RAM), and another part of the memory 1060 could include a Flash memory or other read-only memory (ROM).

(119) Although FIG. 10A illustrates one example of UE 916, various changes may be made to FIG. 10A. For example, various components in FIG. 10A could be combined, further subdivided, or omitted and additional components could be added according to particular needs. As a particular example, the main processor 1040 could be divided into multiple processors, such as one or more central processing units (CPUs) and one or more graphics processing units (GPUs). Also, while FIG. 10A illustrates the UE 916 configured as a mobile telephone or smartphone, UEs could be configured to operate as other types of mobile or stationary devices.

(120) FIG. 10B illustrates an example enhanced NodeB (eNB) network within which error correction coding may be implemented according to this disclosure. The embodiment of the eNB 902 shown in FIG. 10B is for illustration only, and other eNBs of FIG. 9 could have the same or similar configuration. However, eNBs come in a wide variety of configurations, and FIG. 10B does not limit the scope of this disclosure to any particular implementation of an eNB. It is noted that eNB 901 and eNB 903 can include the same or similar structure as eNB 902.

(121) As shown in FIG. 10B, the eNB 902 includes multiple antennas 1070a-1070n, multiple RF transceivers 1072a-1072n, transmit (Tx) processing circuitry 1074, and receive (Rx) processing circuitry 1076. In certain embodiments, one or more of the multiple antennas 1070a-1070n include 2D antenna arrays. The eNB 902 also includes a controller/processor 1078, a memory 1080, and a backhaul or network interface 1082.

(122) The RF transceivers 1072a-1072n receive, from the antennas 1070a-1070n, incoming RF signals, such as signals transmitted by UEs or other eNBs. The RF transceivers 1072a-1072n down-convert the incoming RF signals to generate IF or baseband signals. The IF or baseband signals are sent to the Rx processing circuitry 1076, which generates processed signals by filtering, decoding, and/or digitizing the baseband or IF signals. The Rx processing circuitry 1076 transmits the processed signals to the controller/processor 1078 for further processing.

(123) The Tx processing circuitry 1074 receives, as at least some input data for source data blocks, analog or digital data (such as voice data, web data, e-mail, or interactive video game data) from the controller/processor 1078. The Tx processing circuitry 1074 implements circuits to encode, multiplex, and/or digitize the outgoing baseband data to generate processed signals. The RF transceivers 1072a-1072n receive the outgoing processed signals from the Tx processing circuitry 1074 and up-converts the baseband or IF signals to RF signals that are transmitted via the antennas 1070a-1070n.

(124) The controller/processor 1078 can include one or more processors or other processing devices that control the overall operation of the eNB 902. For example, the controller/processor 1078 could control the reception of forward channel signals and the transmission of reverse channel signals by the RF transceivers 1072a-1072n, the Rx processing circuitry 1076, and the Tx processing circuitry 1074 in accordance with well-known principles. The controller/processor 1078 could support additional functions as well, such as more advanced wireless communication functions. Any of a wide variety of other functions could be supported in the eNB 902 by the controller/processor 1078. In some embodiments, the controller/processor 1078 includes at least one microprocessor or microcontroller, while in other embodiments the main processor includes dedicated circuitry (e.g., for systemic and/or non-systematic encoding processes, puncturing processes, data mapping, etc.) as well as (optionally) programmable logic or processing circuits.

(125) The controller/processor 1078 is also capable of executing programs and other processes resident in the memory 1080, such as a basic OS. The controller/processor 1078 is also capable of supporting channel quality measurement and reporting for systems having 2D antenna arrays. In some embodiments, the controller/processor 1078 supports communications between entities. The controller/processor 1078 can move data and/or instructions into or out of the memory 1080 as required by an executing process.

(126) The controller/processor 1078 is also coupled to the backhaul or network interface 1082. The backhaul or network interface 1082 allows the eNB 902 to communicate with other devices or systems over a backhaul connection or over a network. The interface 1082 could support communications over any suitable wired or wireless connection(s). For example, when the eNB 902 is implemented as part of a cellular communication system (such as one supporting 3G, 4G, 5G, LTE, or LTE-A), the interface 1082 could allow the eNB 902 to communicate with other eNBs over a wired or wireless backhaul connection. When the eNB 902 is implemented as an access point, the interface 1082 could allow the eNB 902 to communicate over a wired or wireless local area network or over a wired or wireless connection to a larger network (such as the Internet). The interface 1082 includes any suitable structure supporting communications over a wired or wireless connection, such as an Ethernet or RF transceiver.

(127) The memory 1080 is coupled to the controller/processor 1078. Part of the memory 1080 could include a RAM, and another part of the memory 1080 could include a Flash memory or other ROM. In certain embodiments, a plurality of instructions is stored in memory. The instructions are configured to cause the controller/processor 1078 to perform the systemic and/or non-systematic encoding or decoding processes, puncturing processes, data mapping, etc.

(128) Although FIG. 10B illustrates one example of an eNB 902, various changes may be made to FIG. 10B. For example, the eNB 902 could include any number of each component shown. As a particular example, an access point could include a number of interfaces 1082, and the controller/processor 1078 could support routing functions to route data between different network addresses. As another particular example, while shown as including a single instance of Tx processing circuitry 1074 and a single instance of Rx processing circuitry 1076, the eNB 902 could include multiple instances of each (such as one per RF transceiver).

(129) Comparison with the prior art. In this part of the present disclosure, we compare the present principles with the prior art and point out some key differences.

(130) From a practical standpoint, the most important aspect of the present principles is that they provide a significant performance gain over the prior art, as shown by FIG. 8A. This improvement is obtained by combining several techniques. An inner transform is used as a means of creating channel polarization. An outer transform is used to create a tree code. A data index set selection method (based on a novel score function method) is used to regulate the intake of source data bits in accordance with the amount of polarized information available to a depth-first tree search algorithm at the decoder. The present principles use triangular factorization as an efficient and powerful method of solving a set of linear equations when the equations are corrupted by noise.

(131) The prior art in polar coding achieves the best known performance results by various concatenation schemes, notably by using a CRC as an outer code and a list-decoder for decoding the inner polar code. In such CRC-aided list-decoding methods, the outer code has a rate R.sub.out close to 1 and the inner code has a rate R.sub.in slightly above the target rate R for the overall code, subject to the constraint that R=R.sub.outR.sub.in; the complexity resides almost fully inside the inner decoder, while the outer decoder carries out a simple CRC check. The present principles differ from concatenation schemes in the prior art in certain important respects. First of all, the present principles in their preferred embodiments employ an inner code with rate R.sub.in close to 1 and an outer code with rate R.sub.out close to R. In other words, the inner code adds no significant redundancy (hence has no significant error-correction capability as a stand-alone code). The present principles rely mainly on a strong outer code for error correction, the prior art concatenation method rely mainly on the strength of an inner code for error correction.

(132) Polar transform is used in the prior art as a stand-alone coding scheme with some coordinates of the polar transform input frozen; the present principles employ polar transforms as a means of creating channel polarization. The present principles in their preferred embodiments take advantage of the polarized mutual information provided by the inner decoder to construct a tree code that can be decoded using a tree search algorithm.

(133) For low-complexity, the tree code is constructed using a convolution operation. Unlike convolutional codes in the prior art, the input to the convolutional operation is a mixture of data symbols and frozen symbols. The mixing of the data symbols and frozen symbols is done in accordance with an algorithm that matches the offered data rate to the polarized information coming from the channel by way of the inner transform. In their preferred embodiments, the TF codes enjoy the benefits of both a strong decoder (sequential decoder) for decoding an outer code and the beneficial effects of polarization for boosting the cutoff rate of sequential decoding provided by the inner transform.

(134) Convolutional coding in the prior art uses a time-invariant rate profile, which is suitable for a memoryless channel. The present principles employ a type of convolutional coding when a subset of coordinates of the input to the outer transform are frozen; however, the resulting convolutional code has a time-varying rate profile which is matched to the time-varying information profile of the effective channel seen by the outer transform. Convolutional codes in the prior art require a termination; the outer transform in accordance with the present principles does not use a termination.

(135) Sequential decoders in the prior art are mainly used with memoryless channels; the present principles employ sequential decoding to decode a code over a channel with memory (the channel created by the inner polar transform has memory). Sequential decoders in the prior art use time-invariant bias terms that do not depend on the depth of the nodes; the sequential decoders in accordance with the present principles use time-varying bias terms that depend on the depth of the node in the code tree.

(136) Extensions of the present principles. Here we point out some directions in which the present principles can be extended readily. All such extensions will be clear to the person skilled in the art and they are covered by the present disclosure.

(137) As pointed out above, the present principles can be applied with any tree-search algorithm as part of the outer decoder 232. One possibility is to use Viterbi decoding which is an ML procedure for decoding convolutional codes over memoryless channels. Viterbi decoding is sub-optimal for decoding TF codes since the outer coder 232 sees a channel with memory due to the presence of an inner decoder 231 between the channel 120 and the outer decoder 232. However, it is still possible to use a Viterbi decoder with or without a list to decode TF codes.

(138) For simplicity of exposition, we have defined TF codes so that the outer transform G.sub.out is a strictly upper-triangular matrix and the inner transform G.sub.in is a strictly lower-triangular matrix. It will be clear to the skilled person in the art that the benefits the present principles can be preserved even if one uses an outer transform of the form G.sub.out=PUQ or an inner transform of the form G.sub.in=P′LQ′ where P, Q, P′, Q′ are permutation matrices, and U and L are, respectively, strictly upper-triangular and strictly lower-triangular matrices. The present principles foresee that the introduction of such permutations may facilitate the implementation of the present principles in hardware or software. All such variations of the methods in the present disclosure are covered by the present principles.

(139) The outer transform matrix G.sub.out and the inner transform matrix G.sub.in are non-singular matrices in the preferred embodiments of the present principles. However, we foresee that in some embodiments of the present principles either G.sub.out or G.sub.in may be singular or even non-square. This situation may arise, for example, if some elements of the TCB are punctured, which is equivalent to dropping some columns of G.sub.in.

(140) It will be clear to the person skilled in the art that the essential ideas behind the present principles may be applied even when the outer transform G.sub.out and the inner transform G.sub.in do not have the same dimensions. For example, if the number of rows of G.sub.in is larger than the number of columns of G.sub.out, one may be able to insert a second source data block or a second frozen data block into the input of the inner transform G.sub.in.

(141) While particular embodiments of METHODS AND APPARATUS FOR ERROR CORRECTION CODING WITH TRIANGULAR FACTORIZATION OF GENERATOR MATRIX are herein described in detail and depicted in the drawings, it is to be understood that the subject matter which is encompassed by the present disclosure is limited only by the claims. Although the present disclosure has been described with exemplary embodiments, various changes and modifications may be suggested to one skilled in the art. It is intended that the present disclosure encompass such changes and modifications that fall within the scope of the appended claims. The description in the present application should not be read as implying that any particular element, step, or function is an essential or critical element which must be included in the claim scope: the scope of patented subject matter is defined only by the allowed claims. Moreover, none of these claims are intended to invoke 35 USC § 112(f) with respect to any of the appended claims or claim elements unless the exact words “means for” or “step for” are explicitly used in the particular claim, followed by a participle phrase identifying a function. Use of terms such as (but not limited to) “mechanism,” “module,” “device,” “unit,” “component,” “element,” “member,” “apparatus,” “machine,” “system,” “processor,” or “controller” within a claim is understood and intended to refer to structures known to those skilled in the relevant art, as further modified or enhanced by the features of the claims themselves, and is not intended to invoke 35 U.S.C. § 112(f).