text:
Feedback Communication Systems with Limitations on Incremental Redundancy

This paper explores feedback systems using incremental redundancy (IR) with noiseless transmitter confirmation (NTC). For IR-NTC systems based on {\em finite-length} codes (with blocklength $N$) and decoding attempts only at {\em certain specified decoding times}, this paper presents the asymptotic expansion achieved by random coding, provides rate-compatible sphere-packing (RCSP) performance approximations, and presents simulation results of tail-biting convolutional codes. The information-theoretic analysis shows that values of $N$ relatively close to the expected latency yield the same random-coding achievability expansion as with $N = \infty$. However, the penalty introduced in the expansion by limiting decoding times is linear in the interval between decoding times. For binary symmetric channels, the RCSP approximation provides an efficiently-computed approximation of performance that shows excellent agreement with a family of rate-compatible, tail-biting convolutional codes in the short-latency regime. For the additive white Gaussian noise channel, bounded-distance decoding simplifies the computation of the marginal RCSP approximation and produces similar results as analysis based on maximum-likelihood decoding for latencies greater than 200. The efficiency of the marginal RCSP approximation facilitates optimization of the lengths of incremental transmissions when the number of incremental transmissions is constrained to be small or the length of the incremental transmissions is constrained to be uniform after the first transmission. Finally, an RCSP-based decoding error trajectory is introduced that provides target error rates for the design of rate-compatible code families for use in feedback communication systems.

feedback of the received symbol) the capacity for a single-user memoryless channel remains the same as without feedback [1].
That same year Elias and Chang each showed that while feedback does not change the capacity, it can make approaching the capacity much easier. Elias [2] showed that feedback makes it possible to achieve the best possible distortion using a simple strategy without any coding when transmitting a Gaussian source over a Gaussian channel if the channel bandwidth is an integer multiple of the source bandwidth. Chang [3] showed that feedback can be used to reduce the equivocation H(X|Y ) in a coded system to bring its rate closer to capacity for finite blocklengths.
The next phase in the information-theoretic analysis of feedback showed that it can greatly improve the error exponent. Numerous papers including [4]- [9] explicitly showed this improvement. A key result in this area is the seminal work of Burnashev [10] which provides an elegant expression of the optimal error-exponent for DMC with noiseless feedback. Burnashev employed a technique that can be considered as a form of active hypothesis testing [11], which uses feedback to adapt future transmitted symbols based on the current state of the receiver.
Although active hypothesis testing provides a performance benefit, practical systems using feedback have thus far primarily used feedback to explicitly decide when to stop transmitting additional information about the intended message. This can happen in two ways: Receiver confirmation (RC) occurs when the receiver decides whether it has decoded with sufficient reliability (e.g. passing a checksum) to terminate communication and feeds this decision back to the transmitter. The alternative to RC is transmitter confirmation (TC), in which the transmitter decides (based on feedback from the receiver) whether the receiver has decoded with sufficient reliability (or even if it has decoded correctly, since the transmitter knows the true message).
TC schemes often use distinct transmissions for a message phase and a confirmation phase. Practical TC and RC systems can usually be assigned to one of two categories based on when confirmation is possible. Single-codeword repetition (SCR) only allows confirmation at the end of a complete codeword and repeats the same codeword until confirmation. In contrast, incremental redundancy (IR) systems [12] transmit a sequence of distinct coded symbols with numerous opportunities for confirmation within the sequence before the codeword is repeated. In some cases of IR, the sequence of distinct coded symbols is infinite and is therefore never repeated. If the sequence of symbols is finite and thus repeated, we call this a repeated IR system.
Forney's analysis [13] provided an early connection between these practical system designs and theoretical analysis by deriving error-exponent bounds for a DMC using an SCR-RC scheme. Following Forney's work, Yamamoto and Itoh [14] replaced Forney's SCR-RC scheme with a SCR-TC scheme in which the receiver feeds back its decoding result (based only on the codeword sent during the current message phase). The transmitter confirms or rejects the decoded message during a confirmation phase, continuing with additional message and confirmation phases if needed. This relatively simple SCR-TC scheme allows block codes to achieve the optimal errorexponent of Burnashev for DMCs.
Error-exponent results are asymptotic and do not always provide the correct guidance in the low-latency regime. Polyanskiy et al. [15] analyzed the benefit of feedback in the non-asymptotic regime. They studied random-coding IR schemes under both RC and TC, and showed that capacity can be closely approached in hundreds of symbols using feedback [15] rather than the thousands of symbols required without feedback [16].
In [15] the IR schemes provide information to the receiver one symbol at a time. For the RC approach, the receiver provides confirmation when the belief for a prospective codeword exceeds a threshold. For the TC approach, the transmitter provides confirmation using a special noiseless transmitter confirmation (NTC) allowed once per message when the transmitter observes that the currently decoded message is correct. This setup, referred to as variable-length feedback codes with termination (VLFT) in [15], supports zero-error communication. VLFT codes are defined broadly enough to include active hypothesis testing in [15], but the achievability results of interest use feedback only for confirmation.
When expected latency (average blocklength) is constrained to be short, there is a considerable performance gap shown in [15] between the SCR-TC scheme of Yamamoto and Itoh [14] and the superior IR-TC scheme of [15]. This is notable because the SCR-TC scheme of Yamamoto and Itoh achieves the best possible error-exponent, demonstrating that errorexponent results do not always provide the correct guidance in the non-asymptotic regime.
Using [15] as our theoretical starting point, this paper explores the information-theoretic analysis of IR-NTC systems at low latencies (i.e., with short average blocklengths) under practical constraints and with practical codes.

B. Feedback in Practical Systems
The use of feedback in practical communication systems predates Shannon's 1948 paper. By 1940 a patent had been filed for an RC feedback communication system using "repeat request" in printing telegraph systems [17]. The first analysis of a retransmission system using feedback in the practical literature appears to be [18] in 1964, which analyzed automatic repeat request (ARQ) for uncoded systems that employ error detection (ED) to determine when to request a repeat transmission.
In the 1960s, forward-error correction (FEC) and EDbased ARQ were considered as two separate approaches to enhance transmission reliability. Davida proposed the idea of combining ARQ and FEC [19] using punctured, linear, block codes. The possible combinations of FEC and ARQ came to be known as type-I and type-II hybrid ARQ (HARQ), which first appeared in [20] (also see [21]). Type-I HARQ is an SCR-RC feedback system that repeats the same set of coded symbols with both ED and FEC until the decoded message passes the ED test. Recent literature and the present paper refer to type-I HARQ as simply ARQ because today's systems rarely send uncoded messages. Type-II HARQ originally referred to systems that alternated between uncoded data with error detection and a separate transmission of parity symbols. Today, type-II HARQ has taken on a wider meaning including essentially all IR-RC feedback systems.
Utilizing the soft information of the received coded symbols, Chase proposed a decoding scheme for SCR-RC [22] that applies maximal ratio combining to the repeated blocks of coded symbols. Hagenauer [23] introduced rate-compatible punctured convolutional (RCPC) codes, which allow a wide range of rate flexibility for IR schemes. Rowitch et al. [24] and Liu et al. [25] used rate-compatible punctured turbo (RCPT) codes in an IR-RC system to match the expected throughput to the binary-input AWGN channel capacity.
When implementing an IR system using a family of ratecompatible codes, the IR transmissions will often repeat once all of the symbols corresponding to the longest codeword have been transmitted and the confirmation is not yet received. Chen et al. demonstrated in [26] that a repeated IR system using RCPC codes could deliver bit error rate performance similar to long-blocklength turbo and LDPC codes, but with much lower latency. The demonstration of [26] qualitatively agrees with the error-exponent analysis and the random-coding analysis in [15]. Using [26] as our practical starting point, this paper explores the practical design of IR-NTC systems at low latencies (i.e., with short average blocklengths) under practical constraints and with practical codes.
Practical design for an IR scheme is primarily concerned with optimizing the incremental transmissions, which includes design of a rate-compatible code family and optimization of the lengths of the incremental transmissions. Practical constraints include limitations on the blocklength N of the lowest-rate codeword in the rate-compatible code family, the number m of incremental transmissions, and the lengths of the incremental transmissions.
Several papers have provided inspiration in practical deign of feedback systems. Uhlemann et al. [27] studied a similar optimization problem assuming that the error probabilities of each transmission are given. Finding code-independent estimates of appropriate target values for these error probabilities is one goal of this paper.
In related work, [28] provides expressions relating throughput and latency to facilitate optimization of the lengths of incremental transmissions in real-time for an IR-RC system. In contrast with the current paper, the receivers in [28] must send the optimized transmission lengths in addition to the confirmation message in order to adapt the transmission lengths in real time. Moreover, [28] used relatively large transmission lengths in order to accurately approximate mappings from codeword reliability to block error rate, while our focus is on short blocklengths.
Chande et al. [29] and Visotsky et al. [30] discussed how to choose the optimal blocklengths for incremental redundancy using a dynamic programming framework. Their approach uses the error probabilities of a given code with specified puncturing to determine the optimal transmission lengths for that code. That work focused on fading channels and on longer blocklengths than the current paper.
Freudenberger's work [31] differs from the present work in that the receiver requests specific incremental retransmissions by determining which segments of the received word are unreliable. This represents a step in the direction of a practical active hypothesis testing system.
In [32] the authors used a reliability-based retransmission criteria in a HARQ setting to show the throughput gains compared to using cyclic redundancy checks for error detection. While [32] shows simulation results for several values of the message size k, the results are not discussed in terms of proximity to capacity at short blocklengths.

C. Main Contributions
This paper is concerned with IR-NTC feedback systems that use a rate-compatible code family to send m incremental transmissions. The jth incremental transmission has length I j so that after i incremental transmissions the cumulative blocklength is n i = i j=1 I j and the decoder uses all n i symbols to decode. We are also concerned with the blocklength of the lowest-rate codeword in the rate-compatible code family, which is N = m j=1 I j . Among its numerous other results, [15] provides achievability result for an IR-NTC system with zero-error probability in the non-asymptotic regime. The achievability uses randomcoding analysis for the case where N = ∞ (and thus m = ∞) and I j = 1, ∀j.
The main contributions of this paper are as follows: 1) This paper extends the IR-NTC random-coding result of [15] to include the constraint of finite N and of I > 1 where I j = I ∀j. Though N is finite, our setup still supports zero-error probability through an ARQ-style retransmission if decoding fails even after the N symbols of the lowest-rate codeword have been transmitted. We refer this type of system as repeated IR-NTC. Our analysis yields two primary conclusions: • Constraining the difference between N and the expected latency to grow logarithmically with the expected latency negligibly reduces expected throughput as compared with N = ∞. • An uniform incremental transmission length I causes expected latency to increase linearly with I as compared to the I = 1 case. 2) This paper uses rate-compatible sphere-packing (RCSP) approximation as a tool for analysis and optimization of IR feedback systems as follows: • Exact joint error probability computations based on RCSP and bounded-distance (BD) decoding are used to optimize the incremental lengths I 1 , . is also similar, but with a gap possibly due to the constraint of the convolutional codes to a binaryinput alphabet. • Simulations were also performed on the AWGN channel using m = 5 incremental transmissions with transmission increments I j optimized using RCSP under the assumption of BD decoding. These simulations exceeded the random-coding lower bound of [15] at low latencies for the same values of m and I j . Also at sufficiently low latencies, the simulations closely match the throughputlatency performance predicted by RCSP with ML decoding.

D. Organization
To conclude this section, we briefly summarize the organization of this paper. Sec. II investigates the rate penalty incurred by imposing the constraints of finite blocklength and limited decoding times on VLFT codes. A numerical example for the binary symmetric channel (BSC) is presented in Sec. II-F. Sec. III describes the examples (used throughout the rest of the paper) of IR-NTC systems using families of practical rate-compatible codes based on convolutional and turbo codes. Sec. IV presents the RCSP approximations and applies the approximations to provide numerical examples for the BSC and the additive white Gaussian noise (AWGN) channel. Sec. IV also explores ARQ, Chase code combining, and IR-NTC systems for the AWGN channels using RCSP approximation. Sec. V continues the RCSP-based exploration of the use of IR-NTC on the AWGN channels studying the optimization of the increments {I j } m j=1 based on RCSP approximation. Finally Sec. VI concludes the paper.

II. PRACTICAL CONSTRAINTS ON VLFT
This section studies IR-NTC systems using the VLFT framework in [15] with the practical constraints of finite N and uniform increments I > 1.

A. Review of VLFT Achievability
We will consider discrete memoryless channels (DMC) in this section and use the following notation: x n = (x 1 , x 2 , . . . , x n ) denotes an n-dimensional vector, x j the jth element of x n , and x j i the ith to jth elements of x n . We denote a random variable (r.v.) by capitalized letter, e.g., X n , unless otherwise stated. The input and output alphabets are denoted as X and Y respectively. Let the input and output product spaces be X = X n , Y = Y n respectively. A channel used without feedback is characterized by a conditional distribution P Y|X = n i=1 P Yi|Xi where the equality holds because the channel is memoryless. For codes that use a noiseless feedback link, we consider causal channels and additionally focus on causal, memoryless channels {P Yi|Xi } ∞ i=1 . Let the finite dimensional distribution of (X n ,X n , Y n ) be: i.e., the distribution ofX n is identical to X n but independent of Y n . The information density i(x n ; y n ) is defined as In this paper we only consider channels with essentially bounded information density i(X; Y ). This section extends the results in [15] for VLFT codes. In order to be self-contained, we state the definition of VLFT codes in [15]: Definition 1: An (ℓ, M, ǫ) variable-length feedback code with termination (VLFT code) is defined as: 1) A common r.v. U ∈ U with a probability distribution P U revealed to both transmitter and receiver before the start of transmission. 2) A sequence of encoders f n : 5) The final decisionŴ = g τ (U, Y τ ) must satisfy: VLFT represents a TC feedback system because the stopping time defined in item 4) above has access to the message W , which is only available at the transmitter. As observed in [15], the setup of VLFT is equivalent to augmenting each channel with a special use-once input symbol, referred to as the termination symbol, that has infinite reliability. We will refer this concept as noiseless transmitter confirmation (NTC) for the rest of the paper.
NTC simplifies analysis by separating the confirmation/termination operation from regular physical channel communication. The assumption of NTC captures the fact that many practical systems communicate control signals in upper protocol layers.
The assumption of NTC increases the non-asymptotic, achievable rate to be larger than the original feedback channel capacity because it noiselessly provides the information of the stopping position. This increases the capacity by the conditional entropy of the stopping position given the received symbols normalized by the average blocklength.
The following is the zero-error VLFT achievability in [15]: where ξ n is the following expectation: The expression in (7) is referred to as the random-coding union (RCU) bound. We take the information density before any symbols are received, i(X 0 ; Y 0 ), to be 0 and hence ξ 0 = 1. Additionally, from the proof of [15,Thm. 11], we have: The proof of Thm. 1 is based on a special class of VLFT codes called fixed-to-variable (FV) codes [33]. FV codes satisfy the following conditions: The condition in (9) precludes active hypothesis testing since the feedback is not used by the encoder to determine transmitted symbols. The condition in (10) enforces zero-error operation since the stopping criterion is correct decoding.
In the proof of Thm. 1 each codeword is randomly drawn according to the capacity-achieving input distribution ∞ j=1 P X on the infinite product space X ∞ . Given a codebook realization, the encoder maps a message to an infinite-length vector and the transmitter sends the vector over the channel symbol-by-symbol. Upon receiving each symbol, the decoder computes M different information densities between the M different codewords and the received vector. The transmitter sends the noiseless confirmation when the largest information density corresponds to the true message. Averaging over all possible codebooks gives the achievability result.

B. Introducing Practical Constraints to VLFT
Define a VLFT code with the constraints of finite blocklength N and uniform increment I as follows: Definition 2: An (ℓ, M, N, I, ǫ) VLFT code modifies 2) and 4) in Definition 1 as follows: 2') A sequence of encoders ≤ ℓ and n 1 is a given constant such that n 1 + kI|N for some k ∈ N. Define the fundamental limit of message cardinality M for an (ℓ, M, N, I, ǫ) VLFT code as follows: Definition 3: Let M * t (ℓ, N, I, ǫ) be the maximum integer M such that there exists an (ℓ, M, N, I, ǫ) VLFT code. For zero-error codes where ǫ = 0, we denote the maximum M as M * t (ℓ, N, I) and for zero-error codes with I = 1 (i.e., decoding attempts after every received symbol) we denote the maximum M as M * t (ℓ, N ). For a feedback system that conveys M messages with expected latency ℓ, the expected throughput R t is given as R t = log M/ℓ. All of the results that follow assume an arbitrary but fixed channel {P Yj |Xj } N j=1 and a channel-input process {X j } N j=1 taking values in X where N could be infinity.

C. The Finite-Blocklength Limitation
This subsection investigates (ℓ, M, N, I, ǫ) VLFT codes with finite N but retains decoding at every symbol (I = 1). The achievability results are examples of IR-NTC systems (or FV codes as described in Sec. II-A), so that encoding does not depend on the feedback except that feedback indicates when the transmission should be terminated.
In an IR-NTC system, the expected latency E[τ ] is given as: where and ζ j is the marginal error event at the decoder immediately after the jth symbol is transmitted. Equation (14) follows since Consider a code C N with finite blocklength N and symbols from X . Achievability results for an (ℓ, M, N, 1, ǫ) "truncated" VLFT code follow from a random-coding argument. In particular we have the following: Theorem 2: For any M > 0 there exists an (ℓ, M, N, 1, ǫ) truncated VLFT code with where ξ n is the same as (7). The proof is provided in Appendix A. Achievability results for ǫ = 0 can be obtained using an (ℓ, M, N, 1, 0) "repeated" VLFT code, which repeats the transmission if the blocklength-N codeword is exhausted without successful decoding. The transmission process starts from scratch in this case, discarding the previous received symbols. Using the original N symbols through, for example, Chase code combining would be beneficial but is not necessary for our achievability result. Specifically, for an (ℓ, M, N, I, 0) repeated VLFT code we have the following result: Theorem 3: For every M > 0 there exists an (ℓ, M, N, 1, 0) repeated VLFT code such that where ξ n is the same as (7). The proof is provided in Appendix A. The rate penalty of using a finite-length (length-N ) codebook is quantified in the following theorem and its corollary: Theorem 4: For an (ℓ, M, N, 1, 0) repeated VLFT code with N = Ω(log M ), we have the following upper bound on ℓ for a stationary DMC with capacity C: Let C ∆ = C − ∆ for some ∆ > 0 and N = log M/C ∆ . The O(1) term c due to the finite value of N is upper bounded by the following expression: where a depends on the mean and uniform bound of i(X; Y ), and b j 's are constants related to ∆ and M . The proof is provided in Appendix A. This choice of N may have residual terms decaying with M very slowly. However, our non-asymptotic numerical results in Sec. II-F for a BSC indicate that this decay is fast enough for excellent performance in the short-blocklength regime.
An asymptotic expansion of log M * t (ℓ, N ) needs to be independent of M and requires N growing with ℓ. However, the components of the correction term c in Thm. 4 depend on both N (as log M/C ∆ ) and M . Indeed for a fixed ℓ, the smallest M satisfying (19) and (20) is achievable. The argument we make below is that for any fixed constant c = c 0 > 0, there is an ℓ 0 that depends logarithmically on c −1 0 such that the expansion log M * t (ℓ, N ) ≥ Cℓ − c 0 is true for all ℓ ≥ ℓ 0 . We first invoke the converse for an (ℓ, M, ∞, 1, 0) VLFT code: Theorem 5 ( [15], Thm. 11): Given an arbitrary DMC with capacity C we have the following for an (ℓ, M, ∞, 1, 0) VLFT code: log M * t ≤ ℓC + log(ℓ + 1) + log e .
To conclude this discussion of the penalty associated with finite blocklength, we comment that N only needs to be scaled properly, i.e., N = ℓ + Ω(log ℓ), to obtain the infiniteblocklength expansion of M * t (ℓ, ∞) provided in [15]. Therefore the restriction to a finite blocklength N does not restrict the asymptotic performance if N is selected properly with respect to ℓ. The constant penalty terms in the expansion are different for infinite and finite N , which might not be negligible in the short-blocklength regime. Still, our numerical results in Sec. II-F indicate that relatively small values of N can yield good results for short blocklengths.

D. Limited, Regularly-Spaced, Decoding Attempts
This subsection investigates (ℓ, M, N, I, ǫ) VLFT codes with N = ∞ but decoding attempted only at specified, regularly-spaced symbols (I > 1). The first decoding time occurs after n 1 symbols (which could be larger than I) so that the decoding attempts are made at the times n j = n 1 +(j−1)I. The relevant information density process i(X nj ; Y nj ) is on the subsequence n j = n 1 + (j − 1)I. The main result here is that the constant penalty now scales linearly with I: Theorem 6: For an (ℓ, M, N, I, 0) VLFT code with uniform increments I and N = ∞ we have the following expansion for a stationary DMC with capacity C: The proof is provided in Appendix A.
In view of Thm. 6, the penalty is linear in the increment I. The increment I can grow slowly, e.g., I = O(log ℓ) and still permit an expected rate that approaches C without the dispersion penalty incurred when feedback is absence [16]. In the non-asymptotic regime, however, the increment I must be carefully controlled to keep the penalty small. Our numerical results in Sec. II-F indicate that choosing I = ⌈log 2 log 2 M ⌉ yields good results for short blocklengths. Also, varying I j to decrease with j can avoid a substantial penally while keeping the penalty small.

E. Finite Blocklength and Limited Decoding Attempts
This subsection investigates (ℓ, M, N, I, 0) repeated VLFT codes with both finite N and I > 1. When these two limitations are combined, a key parameter is m, the number of decoding attempts before the transmission process must start from scratch if successful decoding has not yet been achieved. The parameters m, n 1 , N and I are related by the following equation: Combining the results of Sec. II-C and Sec. II-D yields the following expansion for (ℓ, M, N, I, 0) repeated VLFT codes on a stationary DMC with capacity C: Theorem 7: For an (ℓ, M, N, I, 0) repeated VLFT with N = ℓ + Ω(log ℓ) on a stationary DMC with capacity C and ℓ sufficiently large Specifically, if we choose N > ℓ + log(ℓ+1)+log e C and have decoding attempts separated by an increment I, then the expansion is the same as the case with I > 0 and N = ∞ so that the penalty term is linear in I.
Proof: The proof is based on the following lemma that provides an upper bound on ℓ for an (ℓ, M, N, I, 0) repeated VLFT codes : Lemma 1: For an (ℓ, M, N, I, 0) repeated VLFT code with N = Ω(log M ), we have the following upper bound on ℓ for a stationary DMC with capacity C: where τ 0 is the stopping time in terms of the number of decoding attempts up to and including the first success. The proof of the lemma is similar to Thm. 4 and the details are in Appendix A.
The proof of Thm. 7 now follows. For an (ℓ, M, N, I, 0) repeated VLFT code, pick N as follows: The result follows by a similar argument as for Cor. 1 and by observing that for the condition of δ, (1 + δ)ℓ = ℓ + Ω(log ℓ).
The restriction on the initial blocklength n 1 only makes a constant difference. Our earlier work [34] used an intuitive choice of the finite blocklength: N = (1 + δ)ℓ for a fixed δ > 0, i.e., a blocklength that is larger than the target expected latency by the fraction δ. Theorem 7 validates such choice in terms of the optimality of the asymptotic expansion (since δℓ ∈ Ω(log ℓ)), and indicates that the required overhead δ is decreasing as the target expected latency grows.

F. Numerical Results
For practical applications that apply feedback to obtain reduced latency, non-asymptotic behavior is critical. This section gives numerical examples of non-asymptotic results for a BSC. For a BSC with transition probability p we use the RCU bound in [15], [16] 2 , which gives the following expression: scales as: so that N = ℓ+Ω(log ℓ). The constants a, b > 0 were selected experimentally to be a = 10, b = 30.
For the other two repeated VLFT codes, N = log M/C ∆ where C ∆ = C − ∆. We chose ∆ = 0.3C and 0.4C, which are 43% and 67% longer, respectively, than the blocklength N = log M/C that corresponds to capacity. In other words, N = 1.43 log M/C and N = 1.67 log M/C respectively.
Expected throughput for the finite-N repeated VLFT codes converges to that of VLFT with N = ∞ before expected latency has reached 200 symbols. For expected latency above 75 symbols, the only repeated VLFT code with visibly different throughput than the N = ∞ VLFT code is the ∆ = 0.3C code.
As mentioned in Sec. II-A, VLFT codes can have expected throughput higher than the original BSC capacity of 0.6017 because of the NTC. This effect vanishes as expected latency increases. Fig. 2 shows the R t vs. ℓ performance of a VLFT code with N = ∞ and I = 1 and repeated VLFT codes with various decoding-time increments I. As in (25), when I grows linearly with log M (i.e., ⌈0.15 log 2 M ⌉) then there is a constant gap from the I = 1 case. However, if I grows as ⌈log 2 log 2 M ⌉ then the gap from the I = 1 case decreases as expected latency increases. ARQ performance (in which I = N * , where N * is the optimal blocklength for M ) is also shown in the figure, which reveals a considerable performance gap from even the most constrained repeated VLFT implementation in Fig. 2.

III. IR-NTC WITH CONVOLUTIONAL AND TURBO CODES
The achievability proofs in [15] and II are based on an IR-NTC scheme using random codebooks. This section provides examples of IR-NTC based on practical codebooks: ratecompatible families of turbo codes and tail-biting convolutional codes. The constraints of finite N and I > 1 studied analytically in the previous section appear naturally in the context of these codes.

A. Implementation of a repeated IR-NTC with Practical Codes
A practical way to implement repeated IR-NTC is by using a family of rate-compatible codes with incremental blocklengths Defining an (n, M ) code to be a collection of M length-n vectors taking values in X , we define a family of rate-compatible codes as follows: Definition 4: Let n 1 < n 2 < · · · < n m be integers. A collection of codes {C j } m j=1 is said to be a family of ratecompatible codes if each C j is an (n j , M ) code that is the result of puncturing a common mother code, and all the symbols in the higher-rate code {C j } are also in the lower rate code {C j+1 }.
A family of rate-compatible codes can be constructed by finding a collection of compatible puncturing patterns [23] satisfying Def. 4 for an (N, M ) mother code. Note that the puncturing becomes straightforward if we reorder the symbols of the mother code so that the symbols of C 1 are first, followed by the symbols of C 2 and so on. From this perspective, the symbols transmitted by VLFT in [15] can be seen as an infinite family of rate-compatible codes resulting from such an ordered puncturing.
When implemented using a family of rate-compatible codes {C j } m j=1 , repeated IR-NTC works as follows. A codeword of C 1 with blocklength n 1 = I 1 is transmitted to convey one of the M messages. The decoding result is fed back to the transmitter and an NTC is sent if the decoding is successful. Otherwise the transmitter will send I 2 coded symbols such that the n 2 = I 1 +I 2 symbols form the codeword in C 2 representing the same message. The decoder attempts to decode with code C 2 and feeds back the decoding result. If decoding is not successful after the mth transmission where n m = N , the decoder discards all of the previously received symbols and the process begins again with the transmitter resending the I 1 initial coded symbols. This repetition process continues until the decoding is successful. Fig. 3. Pseudo-random puncturing (or circular buffer rate matching) of a convolutional code. At the bit selection block, a proper amount of coded bits are selected to match the desired code rate. In the special case where m = 1 the repeated IR-NTC reduces to SCR-NTC, which we refer to as ARQ.

B. Randomly Punctured Convolutional and Turbo Codes
The practical examples of repeated IR-NTC provided in this paper use tail-biting RCPC codes and RCPT codes. The details of the rate-compatible codes used in this paper are given as follows: The two convolutional codes we used in this paper are a 64state code and a 1024-state code with generator polynomials (g 1 , g 2 , g 3 ) = (133, 171, 165) and (2325, 2731, 3747) in octal, respectively. The 64-state code is from the 3GPP-LTE [35] standard and the 1024-state code is the optimal free distance code from [21, Table 12.1b]. Both of the codes are implemented as tail-biting codes [36] to avoid rate loss at short blocklengths.
The turbo code used in this paper is from the 3GPP-LTE standard [35], i.e., the turbo code with generator polynomials (g 1 , g 2 ) = (13,15) in octal, with a quadratic permutation polynomial interleaver.
Pseudo-random puncturing, also referred to as circular buffer rate matching in [35], provides the rate-compatible families for both the convolutional and the turbo codes. The process is shown in Fig. 3: the encoder first generates a rate-1/3 codeword. Then the output of each of the encoder's three bit streams passes through a "sub-block" interleaver with a blocklength K. The interleaved bits of each subblock are concatenated in a buffer, and bits are transmitted sequentially from the buffer to produce the increments I j as shown in Fig. 4. The sub-block interleavers re-order the bits of the mother code so that sequential transmission of the bits produces an effective family of rate-compatible codes as discussed in Sec. III-A.
We will use simulation results of repeated IR-NTC systems based on these RCPC and RCPT codes to compare with our analysis in the following sections.

IV. RATE-COMPATIBLE SPHERE-PACKING (RCSP)
The random-coding approach gives a tight achievable bound on expected latency when M is sufficiently large. In the short-latency regime, however, practical codes can outperform random codes, as noted in [37]. To find a code-independent analysis that gives a better prediction of practical code performance, we introduce the rate-compatible sphere-packing (RCSP) approximation. As we will see in Sec. V, RCSP can also facilitate the optimization of the increment lengths I j and provide a trajectory of target error rates for use in the design of a rate-compatible code family.
Shannon et al. [38] derived lower bounds of channel codes for DMC by packing typical sets into the output space. The typical sets are related to the divergence of the channel and an auxiliary distribution on the output alphabet. For the AWGN channel, Shannon [39] showed both the lower bounds on the error probability by considering optimal codes on a sphere (the surface of the relevant ball). The bound turns out to be tight even in the finite-blocklength regime as indicated in [16]. One drawback for considering codes on a sphere is the computational difficulty involved, even for a single fixedlength code.
RCSP is an approximation of the performance of repeated IR-NTC using a family of rate-compatible codes. The idea of RCSP is an extension of the sphere-packing lower bound from a single fixed-length code to a family of rate-compatible codes. For the ideal family of rate-compatible codes, each code in the family would achieve perfect packing. Our analysis will involve two types of packing: 1) perfect packing throughout the volume of the ball whose radius is determined from the signal and noise powers or 2) perfect packing on the surface of the ball whose radius is determined by the signal power constraint. We will also consider both maximum-likelihood (ML) decoding and bounded-distance (BD) decoding.
Let {C j } m j=1 be a family of rate-compatible codes. Let the marginal error event of the code C j at blocklength n j be ζ nj and let the joint error probabilities P[E nj ] be defined similar to (15): The expected latency for a repeated IR-NTC can be computed as follows: Applying the ideal of RCSP throughout the volume of the ball to (31) leads to the joint RCSP approximation of the repeated IR-NTC performance. Since produces a upper bound on expected latency as follows: Since P[ζ nj ] is often a tight upper bound on P[E nj ] (examples will be shown in Sec. V-C), applying the ideal of RCSP throughout the volume of the ball to (32) produces the marginal RCSP approximation of the expected latency in a repeated IR-NTC, which is very similar to the joint RCSP approximation and more easily computed. Performing ML decoding gives a lower bound on the expected latency for the repeated IR-NTC, but makes the error probabilities difficult to evaluate. We initially analyze using BD decoding to decode the ideal code family {C j } m j=1 . Subsequently we refine the analysis by bounding ML decoding performance. Thus we will be considering both the joint and marginal RCSP approximations and also considering both BD and ML decoding.

A. Marginal RCSP Approximation for BSC
For the BSC the optimal decoding regions are simply Hamming spheres. RCSP upper bounds IR-NTC performance on the BSC by assuming that each code in the family of ratecompatible codes achieves the relevant Hamming bound.
For a BSC with transition probability p the marginal error probability P[ζ nj ] is lower bounded as follows: 3 where r j is chosen such that and We use (33) to compute the marginal RCSP approximation for the BSC. Note that for the BSC and an (n, M ) code with M uniform decoding regions that perfectly fill the space, ML decoding is also BD decoding with an uniform radius. For the BSC with p = 0.0789, Fig. 5 shows the marginal RCSP approximation with m = ∞, the VLFT converse of [15], the random-coding achievability of [15], and simulations of repeated IR-NTC using the 64-state convolutional code from Sec. III-B. All simulation points have increment I = 1, finite codeword lengths N = 3k, and initial blocklength n 1 = k for k = 16, 20, 32, 64, respectively. To compare the choice of N = 3k with the results in Sec. II, take k = 32 as an example. For k = 32 the expected latency is ℓ = 49.62 in Fig. 5 and N = 96 corresponds to choosing a δ = 0.93. As we saw in Fig. 1, δ = 0.67 gives RCU performance indistinguishable from N = ∞ so that N = 96 should be more than sufficient for this example.
The convolutional code simulations give throughput-latency points that are very close to the marginal RCSP approximation for expected latency less than 50. The simulation points for k = 16, 20, 32 are significantly higher than the randomcoding achievability result of [15]. The simulation point for k = 64 falls below the random-coding achievability because the expected latency is larger than the analytic trace-back depth of 60 bits (or 20 trellis state transitions) for the 64-state convolutional code.
Note that in Fig. 5, the convolutional code simulation points, the marginal RCSP approximation curve, the VLFT achievability, and the VLFT converse curves are all above the BSC capacity because the NTC assumption provides 3 Formally, the sphere-packing lower bound for BSC follows from the fact that the tail of a binomial r.v. is convex. In the short-latency regime, the marginal RCSP approximation can be more accurate for characterizing the performance of good codes (such as the convolutional code in this figure) than random-coding analysis. The additional information provided by the error-free termination symbol of NTC leads to a converse and an operational rate for the convolutional code that are above the original BSC capacity.
additional information to the receiver as discussed in Sec. II-A.

B. RCSP Approximation for AWGN Channel
This subsection derives joint and marginal RCSP approximations for the AWGN channel under both BD and ML decoding. Consider an AWGN channel Y = X + Z with an average power constraint P . 4 Let the signal-to-noise ratio (SNR) be η = P/σ 2 where P is the signal power and σ 2 is the noise power. Assume without loss of generality (w.l.o.g.) that each noise sample has a unit variance. The average power of a length-n received word is E[ Y n 2 ] ≤ n(P + σ 2 ) = n(1 + η). Sphere packing seeks a codebook that has M equally separated codewords within the n-dimensional norm ball with radius r outer = n(1 + η).
One can visualize a large outer sphere that contains M = 2 nR decoding regions, D i , i = 1, . . . , M , each with the same volume. Considering the spherical symmetry of i.i.d. Gaussian noise Z, our bounded-distance decoding region is an n-dimensional Euclidean ball centered around the message point. By conservation of volume, the largest radius of the decoding region has a volume satisfying Vol(D i ) = K n r n ≤ 2 −nR × Vol(Outer sphere) = 2 −nR K n n(1 + η) n 4 We use the expectation average power constraint E n j=1 X 2 j ≤ nP , which is not as strict as the summation average power constraint n j=1 X 2 j ≤ nP since it allows the codeword power be larger than P with low probability. As shown in the Appendix C, the sphere-packing property combined with the expectation average power constraint will satisfy the summation average power constraint if the rate is less than capacity.
where K n is the volume of the n-dimensional unit sphere. Solving for the radius of the decoding region yields

1) RCSP Approximation for AWGN under BD decoding:
Using bounded-distance decoding on the AWGN channel gives the following decoding rule: the decoder selects message j if the received word Y n ∈ D i for a unique i ∈ {1, . . . , M } and declares an error otherwise. Regardless of the transmitted codeword, the marginal error event for BD decoding is ζ n = {Z n : Z n 2 > r 2 } where r is the decoding radius. The error probability for decoding region with radius r is then simply given by the tail of a chi-square r.v. with n degrees of freedom: where F χ 2 n is the CDF of a chi-square distribution with n degrees of freedom.
Let M = 2 k for an integer k. Assuming perfect spherepacking (i.e., achieving (36) with equality) at each incremental code rate, the radius at incremental code rate k/n j is given as: Note that the probability of a decoding error in the jth transmission depends on previous error events. Conditioning on previous decoding errors ζ nj , j = 1 . . . , m − 1 makes the error event ζ nm more likely than the marginal distribution would suggest. Recall that E nm denotes ∩ j≤m ζ nj ; the joint probability P[E nj ], 1 ≤ j ≤ m is given as: where the increments I j are as defined in Sec. III-A and G χ 2 I j is defined in (38). Using P[E nj ] or P[ζ nj ] as derived above, we can compute the expected latency ℓ of the repeated IR-NTC by using the joint BD RCSP approximation as in (31) or the marginal BD RCSP approximation as in (32). The expected throughput R t is given by k/ℓ.

2) Marginal RCSP Approximation under ML decoding:
To compute the marginal RCSP approximation with MLdecoding, we apply Shannon's sphere-packing lower bound 5 [38]. We use the asymptotic approximation in [38] to estimate the lower bounds of the marginal error probabilities. The approximation formula in [38] does not work well for rates above capacity, providing negative values that are trivial lower bounds. To obtain a good estimate in these cases we replace those trivial probabilities with the ones suggested by the marginal RCSP approximation using BD decoding. 5 We bound the error probability using Shannon's argument: the optimal error probability for codewords inside an n-dimensional ball with radius √ nP is lower bounded by the optimal error probability for codewords on an n + 1dimensional sphere surface with radius (n + 1)P . For the 2dB AWGN channel, Fig. 6 shows the VLFT converse of [15], the random-coding lower bound of [15], the marginal RCSP with BD decoding, and marginal RCSP with ML decoding, all with m = ∞ and I = 1. To approximate the behavior of m = ∞ we found numerically that m = 10k is sufficient in this example. Also shown in Fig. 6 is the simulation of the repeated IR-NTC with step size I = 1 and k = 16, 32, and 64 using the 64-state convolutional code from Sec. III-B. Similar to the BSC example, Fig. 6 shows that the VLFT converse based on Fano's inequality [15] and the marginal RCSP approximation with ML decoding are both above the asymptotic capacity due to the information provided by NTC. The marginal RCSP approximation with BD decoding is not as accurate as the curve with ML decoding in the short-latency regime. The difference between the two curves, however, becomes small beyond the expected latency of 200.
For k = 16 and 32, the convolutional code simulations of repeated IR-NTC (even with a finite N of 3k) with binary modulation outperform the corresponding points on the curve for VLFT random-coding achievability with N = ∞ and unconstrained input to the channel. The two simulation points generally follow the curve of the marginal RCSP approximation with ML decoding, but with a gap. We suspect that this gap is due to the use of binary modulation rather than an unconstrained input in the simulation. As with the BSC example, for k = 64 the performance of the simulation falls short as the expected latency goes beyond the analytic traceback depth of the 64-state convolutional code.

C. Marginal BD RCSP for ARQ and IR-NTC in AWGN
This subsection provides examples of applying the marginal RCSP approximation using BD decoding for the AWGN  channel. Note that all examples use BD decoding and we will simply use the term "marginal RCSP approximation". 1) ARQ: Consider ARQ (SCR-NTC) on an AWGN channel. Based on the marginal RCSP approximation the expected latency ℓ is given as and expected throughput R t = k/ℓ is given as where R c = k/n 1 is the initial code rate and r 1 is the decoding radius of the codeword with length n 1 . Note that in the case of ARQ (SCR-NTC), the joint RCSP and marginal RCSP approximations are identical since there is only a single transmission before repetition. Fig. 7 shows the R t vs. R c (expected throughput vs. initial code rate) curve for the RCSP with ARQ. The SNR is 2 dB and the initial blocklengths are n 1 = 64, n 1 = 704 and n 1 = 10, 000. For each curve in Fig. 7, the initial blocklength n 1 is fixed as we vary the number of messages M = 2 k and the initial code rate R c = k/n 1 changes accordingly. Note that for ARQ, the initial blocklength is also the length of the possible subsequent transmissions.
For blocklengths n 1 = 704 and n 1 = 10000, Fig. 7 compares RCSP with the 3GPP-LTE turbo codes. Each point of the dash-dot turbo-code curves represents a different turbo code with the same blocklength but different code rate (different k). Interestingly, after the initial negligible-codeword-error region where expected throughput equals code rate, the RCSP curve and the turbo code curve are very similar for both n 1 = 704 and n 1 = 10, 000. Furthermore, in this region the difference between the code rate R c associated with a given throughput for RCSP and for the turbo code is about 0.1 bits for both  n 1 = 704 and n 1 = 10, 000 despite the large difference between these two blocklengths.
For blocklength n 1 = 64, Fig. 7 compares the marginal RCSP approximation to the performance of 64-state and 1024-state tail-biting convolutional codes. The marginal RCSP approximation closely predicts the performance of these good tail-biting convolutional codes. Thus, while the turbo codes achieve higher throughputs than the convolutional codes, the convolutional codes perform closer to the RCSP approximation for their (short) blocklengths than do the turbo codes relative to the RCSP approximation for their (longer) blocklengths.
RCSP with its optimistic decoding radius r 1 and suboptimal bounded-distance decoding is a mixture of optimistic and pessimistic assumptions. These plots, however, show that RCSP can provide accurate guidance for good short-blocklength codes such as tail-biting convolutional codes.
2) Chase Combining and IR-NTC: In the ARQ scheme, the same complete codeword is transmitted at each retransmission. One way to utilize these repetitions is to apply the combining scheme proposed by Chase [22]. The Chase scheme uses maximal ratio combining of L repeated codewords at the receiver. If the L codewords are transmitted directly through the AWGN channel with the same SNR, the combining process increases the effective SNR at the receiver by a factor of L.
The side information that the previous block was decoded unsuccessfully (available from the absence of the NTC) implies that the instantaneous noise power in the previous packet is larger than the expected noise power. The error probability is lower bounded (and the throughput is upper bounded) by ignoring this side information.
As shown in Fig. 8, Chase combining of all received packets for a message does not significantly increase the highest possible throughput. Note that the RCSP curve for Chase combining uses the throughput upper bound that ignores the side information of previous decoding failures. Chase combining does provide a substantial throughput improvement for higher-than-optimal initial code rates, but these improved throughputs could have also been achieved by using a lower initial code rate and no Chase combining.
We now present an RCSP approximation and code simulations of repeated IR-NTC as described in Sec. III-A. The exact computation of the joint RCSP approximation is challenging when m is large. We use the marginal RCSP approximation here to compute the R t vs. R c curve for the repeated IR-NTC. Fig. 8 shows an R t vs. R c curve computed based on the approximation of RCSP for the repeated IR-NTC scheme with n 1 = 64, m = 10 and a uniform increment I = 10. We use a uniform increment to avoid the need to optimize each increment although the computation also admits nonuniform increments. We choose m = 10 because experimental results show that for m > 10 the throughput improvement is diminishing. Note that we include AWGN channel capacity in Fig. 8 only as a point of reference since finite-latency capacity with NTC is higher than the asymptotic capacity as shown in Sec. IV-B. Fig. 8 also shows repeated IR-NTC simulations of two tail-biting convolutional codes and a turbo code, where the relevant codes are described in Sec. III-B. The simulated turbo code saturates at a lower throughput than the 64-state and 1024-state tail-biting convolutional codes, which are both ML decoded. We expect that turbo codes with better performance at short latencies can be found. Still, the convolutional code performance is outstanding in this short-latency regime. Fig. 8 shows that ARQ achieves a throughput of less than 0.5 bits and Chase combining provides little improvement over ARQ, with less than 0.01 bits increase in expected throughput. In contrast, the 1024-state convolutional code simulation of repeated IR-NTC achieves a throughput of 0.638 bits. This coincides with the observation in [15] that IR is essential in achieving high throughput with feedback in the finiteblocklength regime, even though the SCR scheme proposed by Yamamoto and Itoh [14] achieves the optimal error-exponent shown by Burnashev [10].
We conclude this section by comparing Fig. 7 and Fig. 8. As shown in Fig. 7, the expected throughput of an ARQ using the blocklength-10, 000 turbo code is 0.56 bits with an expected latency of 10, 016 bits. Fig. 8 shows that the repeated IR-NTC using the 1024-state convolutional code achieves a higher expected throughput of 0.64 bits with an expected latency of only 100 bits!

V. OPTIMIZATION OF INCREMENTS
Sec. IV-C studied throughput by fixing the initial blocklength n 1 and varying the number of information symbols k, which correspondingly varied the initial code rate R c . This produces curves of expected throughput R t vs. initial code rate R c . In contrast, this section fixes k and studies throughput by optimizing the set of increments {I j } m j=1 for the repeated IR-NTC scheme as presented in Sec. III-A. This produces curves of expected throughput R t vs. expected latency ℓ. The optimization uses BD decoding to compute the expected throughput for both joint and marginal RCSP approximation. For the rest of the paper we will assume BD decoding unless We first consider exact computations of the joint RCSP approximation for relatively small values of m. We begin with the special case of m = 1, which is ARQ. We then provide results for cases where m > 1 and study how increasing m improves performance. We introduce Chernoff bounds on the joint RCSP approximation and compare these bounds with the marginal RCSP approximation. We then use the marginal RCSP approximation to optimize the performance of repeated IR-NTC for large m but constrained to have uniform increments after the initial transmission. Then we optimize increments for non-repeating IR-NTC constraining both the maximum number of incremental transmissions and the probability of outage. Finally, we introduce the concept of the decoding error trajectory, which provides the RCSP approximation of error probability at each incremental transmission. It is a useful guide for rate-compatible code design for feedback systems.

A. Choosing I 1 for the m = 1 Case (ARQ)
Recall that for repeated IR-NTC the special case of m = 1 is ARQ. In this case, when the message is fixed to be k bits, the RCSP approximation 6 of expected throughput is a quasiconcave function of the code rate R c in (43). Thus a unique optimal code rate R * c for the repeated codewords can be found numerically [40] to maximize the RCSP approximation of R t for a given k. Table I presents the optimal code rates R * c = k/I * 1 and transmission lengths n 1 = I * 1 for ARQ. Fig. 9 plots the maximum RCSP approximation of throughput vs. expected latency ℓ for ARQ as the red curve with diamond markers. Both Table I and Fig. 9 apply the constraint that the lengths I * 1 must be integers. These results for ARQ are discussed together with the results of m > 1 in the next subsection.

B. Choosing Increments {I j } to Maximize Throughput
In Sec. IV-C2 we demonstrated one repeated IR-NTC scheme with m = 10 transmissions that could approach capacity with low latency based on RCSP. Specifically, the transmission lengths were fixed to I 1 = 64 and I 2 , . . . , I 10 = 10, while k was varied to maximize throughput.
This subsection presents optimization results based on exact numerical integrations computing the joint RCSP approximation. Both k and the number of transmissions m are fixed, and a search identifies the set of transmission lengths {I j } m j=1 6 Note that for the m = 1 case there is no distinction between the joint RCSP approximation and the marginal RCSP approximation.  that maximizes the joint RCSP approximation of expected throughput using BD decoding. Based on the optimized increments, this subsection also provides the marginal RCSP approximation of the expected throughput using ML decoding.
For m > 1, identifying the transmission lengths I j which minimize the latency ℓ is not straightforward due to the joint decoding error probabilities in (40). Restricting to a small m allows exact computation of (40) in Mathematica, avoiding the marginal approximation. We study the cases when m ≤ 6 based on numerical integration.
The computational complexity of numerical integration for (40) increases with the transmission index j. Because of this increasing complexity we limited attention to a well-chosen subset of possible transmission lengths. Thus our results based on numerical integration may be considered as lower bounds to what is possible with a fully exhaustive optimization. Table II shows the results of the m = 5 optimization (i.e., the set of lengths I j found to achieve the highest throughput) and the corresponding throughput for the joint RCSP approximation. Table II also shows that for every value of k the initial code rate k/I 1 is above the channel capacity of 0.6851. These high initial code rates indicate that feedback is allowing the decoder to capitalize on favorable noise realizations by attempting to decode and terminate early. Fig. 9 shows the optimized joint RCSP approximation of R t vs. ℓ for m = 1, 2, 5, 6 on an AWGN channel with SNR 2 dB. As m increases, each additional retransmission increases the expected throughput but the amount of that increase diminishes. The points on each curve in Fig. 9 represent values of k ranging from 16 to 256 information bits. Fig. 9 shows, for example, that by allowing up to four retransmissions (m = 5) with k = 64, the joint RCSP approximation has a throughput R t = 0.636 bits or 93% of the original AWGN capacity 7 with an expected latency of 101 symbols. Similar results are obtained for other SNRs. Fig. 9 also shows the R t vs. ℓ curves for marginal RCSP approximation using ML decoding. The increments in Table II are used in the computation. The curves for ML decoding shows that the effect of NTC starts to manifest at low latencies as m increases. Moreover, the differences between the BD decoding curves and ML decoding curves are negligible for m > 1 and expected latencies larger than 200. This observation motivates us to focus on the expected throughput optimization using BD decoding, which simplifies the computation.

C. Chernoff Bounds for RCSP over AWGN Channel
Even using the less complex BD decoding, the computation of the joint RCSP approximation based on numerical integration becomes unwieldy for m > 6. In this subsection we study upper and lower bounds based on the Chernoff inequality and compare these bounds with the marginal RCSP approximation of throughput, which is itself a lower bound on the joint RCSP approximation. Similar to previous subsection we assume BD decoding unless otherwise stated.
Assume w.l.o.g. that the noise has unit variance. Let r j and n j be the decoding radius and blocklength for the jth decoding attempt. As in earlier sections let ζ nj be the marginal error event and E ni = ∩ i j=1 ζ nj is the joint error event. The main result of applying the Chernoff inequality to bound the joint RCSP approximation is the following theorem.
Theorem 8: Using the joint RCSP approximation with BD decoding for AWGN channel we have for all 1 < i ≤ m that where P 1 = P[ζ ni ] and P 2 = P[ζ ni ∩ ζ ni−1 ]. The pairs of joint events ζ nm ∩ζ nj , j = 1, . . . , m−1 can be bounded as follows: The bounds on pairs of joint events (46) and (47) can be extended to joints of more than two events which leads to We observed numerically that the marginal probability P[ζ nm ] in (45), which can be evaluated directly via the tail of a single chi-square random variable, is surprisingly tight for short blocklengths. The tightness of the marginal was used in [15] for (6), where the upper bound on the error probability of each time instance is the marginal.
Using the marginal P[ζ ni ] as an upper bound on P[E ni ], the lower bound (44) shows that the gap between the joint and marginal probability is upper bounded by applying (47) to i−1 j=1 P ζ ni ∩ ζ c nj . We found numerically that setting u = 1/2 − n m /(2r 2 m + 2k) in (47) where k = log 2 M , gives a tight upper bound on the gap, although this convenient choice of u is not the optimal value. Fig. 10 shows the R t vs. ℓ curves for m = 5 using the optimized step sizes provided in Table II of Sec. V and the values of k are shown in the figure. The channel SNR is 2 dB and the asymptotic capacity is 0.6851 bits. The m = 5 curves shown include exact numerical integration of the joint RCSP approximation, the marginal RCSP approximation using both ML decoding and BD decoding, the upper bound on the joint RCSP approximation using (44) and (47), and the randomcoding lower bound using (8). Evaluating (6) would give a slightly better bound than (8) for random coding but is very time-consuming to compute.
The throughput upper bound using (44) and (47) becomes tight for latencies larger than 100. The lower bound on the joint RCSP approximation using (45) and (46) is not shown separately because it turns out to be identical to the marginal RCSP approximation. This is because the Chernoff bound of the pairwise joint probabilities are often larger than the marginal probabilities. Fig. 10  and 64-state convolutional codes presented in Sec. III-B.
The simulation results demonstrate that both codes achieve throughputs higher than the random-coding lower bound for k = 16 and k = 32. The more complex 1024-state code gives expected throughput higher than random coding even for k = 64. For k = 16 and k = 32 the simulation points of the 1024-state code closely approach the marginal RCSP approximation of the expected throughput using ML decoding.
Note that the lower bound of the expected throughput using random coding is significantly below the RCSP approximations (joint RCSP approximation using BD decoding and marginal RCSP using ML or BD decoding) for low expected latencies. However, for expected latencies above 350 symbols the RCSP approximations and the lower bound based on random coding produce very similar expected throughputs.
For random coding, an i.i.d. codebook is drawn using a Gaussian distribution with a zero mean and a variance equal to the power constraint η. This type of random codebook generation will sometimes produce a codeword that violates the power constraint. To address this, the average power should be slightly reduced or codewords violating the power constraint should be purged, either of which will lead to a slight performance degradation.
To conclude this subsection, we summarize two relevant observations to motivate the next subsection: (1) When using BD decoding, the difference in expected throughput between the joint RCSP approximation and the marginal RCSP approximation is negligible. (2) The difference between the joint RCSP approximation using BD decoding and marginal RCSP approximation using ML decoding is small for reasonably large expected latencies, e.g., 200 for m > 1. These two observations allow us to focus on efficient optimizations based on marginal RCSP approximation using BD decoding.

D. RCSP with Uniform Increments
For a specified k and for a fixed finite number of transmissions m, there are m variables {I j } m j=1 that can be varied to optimize the throughput. The number of possible combinations of I j 's increases rapidly as m increases. Sec. V-B addressed the optimization problem for m ≤ 6 by using the joint RCSP approximation. Motivated by the pattern seen in Table II, this subsection considers the large m case by restricting the transmissions to use uniform increments I j = I for j > 1. This yields a two parameter optimization: the initial blocklength n 1 and the increment I. To reflect practical constraints, we restrict the increment I to be an integer.
We also reduce computational burden by replacing the joint RCSP approximation with the marginal RCSP approximation, and we only use BD decoding. Note that in Sec. V-C we saw that the marginal RCSP approximation is operationally identical to lower bound on the joint RCSP approximation using (45) and (46) and is a tight lower bound to the joint RCSP approximation. It is also relatively simple to compute using BD decoding since the relevant probability of error is simply the tail of a chi-square. Fig. 11 presents the optimized performance with uniform increments for various m ranging from 2 to ∞. In the optimization that produced this figure, the longest possible blocklength was constrained to be less than ⌈6k/C⌉ where C is the capacity of the AWGN channel.
For the m = 5 case, it is instructive to compare optimized uniform increments with the unconstrained optimal increments of Table II. Table III shows the numerical results of the uniform-increment optimization for m = 5 on the 2 dB AWGN channel. Comparing the m = 5 curves in Fig. 11 and the parameters n 1 , n m , I, and R t in Tables II and III shows that the constraint of constant increments I j = I for j > 1 negligibly reduces expected throughput in this case.
Looking at the uniform-increment curves in Fig. 11, we observe diminishing returns even for m increasing exponentially. This implies that for a practical system it suffices to consider an m smaller than 16.

E. Performance across a range of SNRs
To allow easy comparison across the various plots above, we have focused attention on the specific case of the 2 dB AWGN channel. The uniform-increment approach of the previous subsection allows us to efficiently explore performance across a range of SNRs. For expected latencies constrained to be close to (but not greater than) 200 symbols, Fig. 12 plots the marginal RCSP approximation of R t vs. η for m = 1, 4, 8 and η ranging from 0 to 5 dB. The expected throughput R t is obtained by finding the largest integer k such that the optimized initial blocklength n 1 and the uniform increment I yield expected latency ℓ ≤ 200. The actual expected latencies ranged only between 197 and 200. We chose the constraint to be 200 since the difference between ML decoding and BD decoding for the marginal RCSP approximation is small.
This plot shows the significant benefit of even limited IR as compared to ARQ over a range of SNRs. For example, at 4 dB the curve for m = 1 (ARQ) is 0.155 bits from the original AWGN capacity, but this gap reduces to 0.046 bits for m = 4 and 0.025 bits for m = 8. To see these gaps from an SNR perspective, the horizontal line at expected throughput 8.7 bits shows that m = 1 (ARQ) performs within 1.3 dB of the original AWGN capacity while m = 4 is within 0.4 dB and m = 8 is within 0.2 dB.
Recall that the marginal RCSP curves in Fig. 12 are for repeated IR-NTC, which generally can have throughputs above capacity because of the extra information communicated by the NTC. We saw this in Figs. 5 and 6. However, this extra information is quite limited for small values of m. A simple upper bound on the extra information per transmitted symbol to communicate τ for repeated IR-NTC with initial blocklength n 1 is log 2 (m + 1)/n 1 . We examine this upper bound for the case of Thus, the small values of m along with practically reasonable expected latencies of around 200 symbols considered in Fig. 12 cause the extra information provided by NTC to be negligible. Note that for larger expected latencies, the persymbol extra information of NTC will become even smaller.

F. Optimizing Increments for Non-Repeating IR-NTC
Repeated IR-NTC has an outage probability of zero because it never stops trying until a message is decoded correctly. However, this leads to an unbounded maximum latency. Using a non-repeating IR-NTC scheme, optimization of transmission lengths using the joint RCSP approximation can incorporate a strict constraint on the number of incremental transmissions so that the transmitter gives up after m transmissions. This optimization can also include a constraint on the outage probability, which is nonzero for non-repeating IR-NTC.
To handle these two new constraints, we fix m and restrict P[E nm ] to be less than a specified p outage . Without modifying the computations of P[E nj ], the optimization is adapted to pick the set of lengths that yields the maximum throughput s.t. P[E nm ] ≤ p outage . When there is a decoding error after the mth transmission, the transmitter declares an outage event and proceeds to encode the next k information bits. This scheme is suitable for delay-sensitive communications, in which data packets are not useful to the receiver after a fixed number of transmission attempts. The expected number of channel uses ℓ is given by The expected throughput R t is again given by k/ℓ and the outage probability is P[E nm ].

G. Decoding Error Trajectory with BD Decoding
The optimization of increments in Sec. V-B uses the joint RCSP approximation 8 to find the highest expected throughput R t . The joint RCSP approximation provides a set of joint decoding error probabilities P[E nj ], j = 1, . . . , m, which we call the "decoding error trajectory". If we can find a family of rate-compatible codes that achieves this decoding error trajectory, then we can match the throughput performance suggested by the joint RCSP approximation. For the shortlatency regime, e.g. k = 16 and k = 32, one should use the marginal RCSP approximation with ML decoding to study the decoding error trajectory for a better approximation. To demonstrate an example of the decoding error trajectory we focus our attention on the case of k = 64 and use BD decoding throughout this subsection. Fig. 14 presents the decoding error trajectories for k = 64 and m = 1, 2, 5, 6 using the joint RCSP approximation. Each trajectory corresponds to a k = 64 point on the R t vs. ℓ curve in Fig. 9. For example, the decoding error trajectory for k = 64 and m = 2 consists of the two blue square markers in Fig. 14 and corresponds to the point on the blue solid curve in Fig. 9 with k = 64, m = 2.
Fig. 14 also shows the decoding error trajectories for the random-coding lower bound using (8) with m = 5, as well as the simulations of the two tail-biting convolutional codes presented in Sec. III-B with m = 5. The dashed line is the decoding error trajectory using the marginal RCSP approximation. The marginal RCSP approximation provides a good estimate that can serve as a performance goal for practical rate-compatible code design across a wide range of blocklengths.
While the 64-state code is not powerful enough to match the trajectory suggested by the joint RCSP approximation, the 1024-state code closely follows the trajectory for m = 5 and therefore has a performance very close to the joint RCSP (c.f. Fig. 10). Thus there exist practical codes, at least in some cases, that achieve the idealized performance of RCSP. Fig. 15 shows how the outage probability constraints affect the decoding error trajectory for k = 128 and m = 4 using the joint RCSP approximation. Curves are shown with no constraint on the outage probability p 4 and for p 4 constrained to be less than 10 −4 , 10 −5 and 10 −10 . For ease of comparison, the x-axis is labeled with the transmission index rather than blocklength as in Fig. 14.
At each index, the blocklengths corresponding to the curves with different constraints are different. For example, at transmission index two, the curve with p 4 = 10 −4 has blocklength 191 whereas the curve with p 4 = 10 −10 has blocklength 211. An important observation is that even for relatively low outage probability constraints such as p 4 = 10 −10 , the initial transmission should still have a relatively high decoding error rate in order to take advantage of instantaneous information densities that may be significantly higher than capacity.

VI. CONCLUDING REMARKS
Inspired by the achievability and converse results in [15] and practical simulation results in [26], this paper studies feedback communication systems that use incremental redundancy. We focus on the convenient model of IR-NTC, in which a stream of incremental redundancy concludes when a noiseless confirmation symbol is sent by the transmitter once the receiver has successfully decoded.
VLFT achievability in [15] uses a non-repeating IR-NTC system with an infinite-length mother code and decoding attempted after each received symbol. The first part of this paper shows that a finite-length mother code (implying repeated IR-NTC to achieve zero-error communication) with decoding attempted only at certain specified times can still approach the VLFT achievability curve. The finite-length constraint introduces only a slight penalty in expected latency as long as the additional length of the mother code beyond the blocklength corresponding to capacity grows logarithmically with the expected latency. This is a requirement that is easily met by practical systems. In contrast, the expected latency penalty associated with decoding time limitations is linear in the interval between decoding times. This forces the intervals to grow sub-linearly in the expected latency for systems to approach capacity.
The second part of this paper introduces rate-compatible sphere-packing (RCSP) and uses this tool to analyze and optimize IR-NTC systems for the AWGN channel. The joint RCSP approximation with BD decoding optimizes the incremental lengths I 1 , . . . , I m for small values of m in a repeated IR-NTC system. We found that under BD decoding, the marginal RCSP approximation is a tight lower bound of the joint RCSP approximation of expected throughput and simplifies the computation. This simplification allows optimization of the uniform incremental length I for repeated IR-NTC with larger values of m. The marginal RCSP approximation can also be computed for ML decoding, and the difference between ML decoding and BD decoding is significant for short expected latencies. For expected latencies larger than 200 symbols, however, we observed that the difference between ML and BD decoding becomes small.
For relatively small values of m and N , a repeated IR-NTC system can approach the capacity of the original AWGN channel with expected latencies around 200 symbols. We applied the marginal RCSP approximation assuming BD decoding across a range of SNRs to an IR-NTC system with m = 8 and expected latencies at or below 200 symbols. The results showed throughputs consistently within about 0.2 dB of the performance corresponding to the original AWGN capacity. The NTC introduces additional information that can generally cause IR-NTC achievable rates to be above capacity. When m is less than 8 and the expected latency is above 200 symbols, however, this increase in throughput is limited to negligible values (less than 0.02 bits) so that comparisons with the original AWGN channel capacity are reasonable.
For non-repeating IR-NTC, we can use the joint RCSP approximation with BD decoding to optimize the incremental lengths I 1 , . . . , I m under an outage constraint. Numerical result shows that for an expected latency above 200 symbols, strict outage probability constraints can be met with minimal loss in throughput.
From a practical code design perspective, this paper demonstrates an IR-NTC system for m = 5 incremental transmissions based on a 1024-state, randomly punctured, tail-biting convolutional code with optimized transmission increments. At short expected latencies, the resulting IR-NTC system exceeds the random-coding lower bound of [15] and closely matches the throughput-latency performance predicted by RCSP for the AWGN channel at low latency.
Rate-compatible codes for IR-NTC systems that match the performance predicted by RCSP remain to be identified for expected latencies between 200 and 600 symbols. This paper demonstrates that the decoding error trajectory based on the marginal RCSP approximation can provide the target error probabilities for designing such rate-compatible codes. Approximations based on both ML decoding and BD decoding can be used. BD decoding is easier to compute and we showed that the difference between ML and BD decoding becomes small for m > 1 and expected latencies larger than 200. The design of rate-compatible codes matching the marginal-RCSP decoding error trajectory for expected latencies between 200 and 600 symbols is a challenging open problem in channel code design.

APPENDIX A PROOFS FOR VLFT WITH PRACTICAL CONSTRAINTS
Proof of Thm. 2: Consider a random codebook C N = {C 1 , . . . , C M } with M codewords of length-N and codeword symbols independent and identically distributed according to P X . To construct a VLFT code consider the following (U, f n , g n , τ ): The common random variable is distributed as: A realization of U corresponds to a deterministic codebook {c 1 , . . . , c M }. Let C W (n) denote the nth symbol of the codeword C W , and let [C j ] n denote the first n symbols of the codeword C j . The sequence (f n , g n ) is defined as and the stopping time τ is defined as: The nth marginal error event ζ n is given as: Following (11)- (14) we have As in [15, (151)-(153)], the union bound P(ζ n ) ≤ ξ n provides an upper bound on (14) as follows: where ξ n is given in (7).
With a similar bounding technique, the error probability can be upper bounded as: In other words, the error probability is upper bounded by the error probability of the underlying finite-length code C N .

Proof of Thm. 3:
The proof follows from random coding and the following modification of the triplet (f n , g n , τ ) of Thm. 2: For k = 1, 2, . . . let (f ′ n , g ′ n ) be defined as: ) if kN < n ≤ (k + 1)N Let the new stopping time τ ′ be defined as: The error probability is zero because the definition of the stopping time τ ′ ensures that decoding stops only when the decision is correct. As mentioned above, the new encoder/decoder sequence (f ′ n , g ′ n ) is simply an extension of the VLFT code in Thm. 2 by performing an ARQ-like repetition. The expectation of τ ′ is thus given as: which implies that: Applying the RCU bound to replace each P[ζ n ] with ξ n completes the proof.

Proof of Thm. 4:
We define a pair of random walks to simplify the proofs: Referring to (2), note that for any measurable function f we have the property: Letting P X to be a capacity-achieving input distribution, observe that S n andS n are sums of i.i.d. r.v.s with positive and negative means: where C is the channel capacity and L is the lautum information [41]. The sequence {S n − nC} n is a bounded martingale based on our assumption that the information density of each symbol is essentially bounded. Hence, by Doob's optional stopping theorem we have for a stopping time τ : Properties (68)-(71) are used in the rest of this appendix.
Using the definitions of (66) and (67) in (7) produces (72). Weakening the RCU bound using (8) and replacing M − 1 with M in (8) for simplicity produces (73): Applying (73) to Thm. 3 yields the following: Consider an auxiliary stopping timeτ w.r.t. the filtration F n = σ{X n ,X n , Y n }: For a specified set E, use E[X; E] to denote E[X1 E ] where 1 E is the indicator function of the set E. We now turn our attention to computing the summation in (74). Letting E be the set {τ < N }, we have the following: On E we have i(Xτ ; Yτ ) ≥ log M and hence: where the last equality is equality in distribution and is true almost surely by the strong Markov property of random walks. Applying (77)-(79) to (76) yields: Using (68) we have the following: S k andS k are sums of i.i.d. r.v.s with positive and negative means, respectively. Thus by the Chernoff inequality, both terms decay exponentially in k, yielding for some positive constants a 1 and a 2 . Thus there is a constant a 3 > 0 such that: We assume that S n has bounded jumps, and hence on the set E there is a constant a 4 such that Therefore from (71) we have that on the set E: We are now ready to provide a bound on (74). Letting a 5 = a 3 + a 4 and applying (83)-(86) and (88) to (76) we have: For a fixed M with random coding, there is a constant ∆ > 0 such that with C ∆ = C − ∆ and N = log M/C ∆ we have the following bound on error probability: for some constants b 2 > 0 and b 3 > 0.
Recalling that S n is a sum of i.i.d. r.v.'s with mean C, let N = log M/C ∆ we have by the Chernoff inequality that: Combining (89) and (93) we have the following for ℓ: for some a 6 > 0. Hence for M large enough we have (19).

Proof of Cor. 1:
We first choose N to scale with ℓ with a factor δ to be chosen later: Then by the converse (Thm. 5) we have: The term δ ′ on the right is positive by setting: Again by the Chernoff inequality we have: Since δ is chosen such that log M/N is less than capacity, we also have (90). By reordering (89) we have for some which implies log M * t (ℓ, N ) ≥ ℓC − O(1) for N = (1 + δ)ℓ and large enough ℓ.
Proof of Thm. 6: Consider the same random-coding scheme as in Thm. 3 with encoders f ′ n (U, W ) and decoders g ′ n (U, Y n ). The auxiliary stopping timeτ of Thm. 4 is altered to reflect the limitation on decoding times as follows: wherej is also a stopping time given as: The rest is similar to the proof of Thm. 4, but without the complication of a finite N : for some a 3 > 0 and some a 4 > 0, where (110) follows by applying the Chernoff inequality and (111) is a consequence of the jumps S n k being bounded by Ia 4 C for some a 4 > 0.
Reordering the equations gives the result.
Proof of Lem. 1: Consider the same random-coding scheme as in Thm. 6 with encoders f ′ n (U, W ) and decoders g ′ n (U, Y n ), an initial blocklength n 1 , and a uniform increment I. However, the number of increments is now limited to a finite integer m. The finite block-length is then given by N = n m where n j = n 1 + (j − 1)I. Similar to Thm. 4, define the auxiliary stopping time as: which yields a similar choice of N as in the proof of Thm. 4: 21 The rest of the proof follows as in the proof of Thm. 4.

APPENDIX B CHERNOFF BOUNDS FOR RCSP
This appendix gives the proofs of the upper and lower bounds provided in Sec. V-C. Let f χ 2 n = dF χ 2 n be the density function of a chi-square distribution with n degrees of freedom. The following lemma gives upper and lower bounds on the joint of a pair or error events.
Lemma 2: For an AWGN channel, let {ζ nj } m j=1 be the error events of RCSP with bounded-distance decoding. We have the following upper and lower bounds on the probability of a pair of joint error events ζ nj and ζ ni where j < i ≤ m: where w 1 and w 2 are given as: Proof: It suffices to show the bounds for ζ n1 ∩ ζ n2 . Let the set A j i (r 2 k ) be defined as: Applying the Chernoff inequality to (40) for m = 2, we have P[ζ n1 ∩ ζ n2 ] ≤ where (129) follows from a change of variable z ′ i = (1 + 2u) 1/2 z i . Taking the infimum over u < 1/2 gives the result.
The following theorem extends the upper bound of the above lemma for the m-transmission joint error probability given in (40), which depends on the initial blocklength n 1 = I 1 and the m − 1 step sizes I 2 , . . . , I m : Theorem 9: Let u i < 1/2, i = 1, 2, . . . , m be the parameters for each use of Chernoff bound in the integral. Define h i , g i (u m 1 ) by the following recursion: Note the property that 1 − 2h i = j≤i (1 − 2u j ). We have Proof: The proof follows from changing the variables iteratively similar to the proof of Lem. 2.
Several versions of lower bounds of the joint error probability with m transmissions can be obtained by different expansions of the joint events, and the recursion formulas follow closely to those in Thm. 9 and Lem 2. The following corollary gives an example of one specific expansion that yields a lower bound in a recursive fashion and the other formulas are omitted.

Corollary 2:
With the same recursion as in Thm. 9, the lower bound is given as: where p is given as Proof: Expand E m as and the proof follows from applying Thm. 9 except for the last event ζ n1 , which gives P χ 2 I1 ≤ (1 − 2h m−1 )r 2 1 instead of P χ 2 I1 ≥ (1 − 2h m−1 )r 2 1 . Applying Thm. 9 for the case of m = 2 gives a proof of Thm. 8 as shown in the following.
Proof of Thm. 8: We first show that both (44) and (45) follow immediately from properties of probability. For any two sets A, B we can write a disjoint union of A as Letting A = ζ nm and B = E nm \ ζ nm = E nm−1 , we can rewrite the expression of P[E nm ] as We therefore have the following: where the last inequality can be seen as the union bound on the second term of the first equality.
To show the upper bound, a straightforward probability upper bound of E nm gives which can be computed with the tail of the chi-square CDF directly. Since P E nj ≤ P[ζ nj−1 ∩ ζ nj ], applying Lem. 2 for upper bounds on P[ζ nj−1 ∩ ζ c nj ] finishes the proof. Note that alternatively, we can rewrite the joint error probability to obtain different upper bounds. For example, write P[E nj ], j ≤ m as Applying Thm. 9 to the first two terms and Cor. 2 to the last term gives another version of the upper bound. Also note that for rates above capacity, only (139) is active since the Chernoff bounds give trivial results.

APPENDIX C THE AWGN POWER CONSTRAINT FOR RCSP
Recall that for an n-dimensional input X n for the AWGN channel with unit noise variance and SNR η, the power constraint is given as n j=1 X 2 j ≤ nη. Assuming perfect packing of M = 2 k identical Euclidean balls D i with radii r into the outer sphere with radius r outer = n(1 + η), the radii for D i is r = √ n(1+η) 2 k/n . The codeword point, which is located at the center of the decoding region D i , is at least distance r from the outer sphere surface assuming perfect packing and within the outer sphere.
Let S n (r) = {y n : n i=1 y 2 i = r 2 } be the sphere surface with radius r. The set of x ∈ R n that is at least distance r away from the sphere surface with radius r outer = n(1 + η) is given as H(r) = x n : n i=1 (x i − y i ) 2 ≥ r 2 , ∀y ∈ S n (r outer ) .
Let B n (r) denote a ball with radius r. With an additional constraint that x n must also be in the ball with radius n(1 + η), we conclude that the codeword points must be in the ball B n √ nη . The maximum energy of a codeword is therefore within the power constraint n j=1 X 2 j ≤ nη if k/n ≤ 1 2 log 2 (1 + η), the capacity of the AWGN channel.


Ensemble Learning of Colorectal Cancer Survival Rates

In this paper, we describe a dataset relating to cellular and physical conditions of patients who are operated upon to remove colorectal tumours. This data provides a unique insight into immunological status at the point of tumour removal, tumour classification and post-operative survival. We build on existing research on clustering and machine learning facets of this data to demonstrate a role for an ensemble approach to highlighting patients with clearer prognosis parameters. Results for survival prediction using 3 different approaches are shown for a subset of the data which is most difficult to model. The performance of each model individually is compared with subsets of the data where some agreement is reached for multiple models. Significant improvements in model accuracy on an unseen test set can be achieved for patients where agreement between models is achieved.

INTRODUCTION
Colorectal cancer is the third most commonly diagnosed cancer in the world. Colorectal cancers start in the lining of the bowel and grow into the muscle layers underneath then through the bowel wall [1]. TNM staging involves the Classification of Malignant Tumours • Tumour (T). Size of the tumor and whether it has invaded nearby tissue • Nodes (N). The extent to which regional lymph nodes involved • Metastasis (M). This is the spread of a disease from one organ or part to another non-adjacent organ. 4 TNM stages (I,II,III,IV) are generated by combining these three indicator levels and are allied with increasing severity and decreasing survival rates.
Treatment options include minor/major surgery, chemotherapy, radiotherapy but the correct treatment is heavily dependent on the unique features of the tumour which are summarised by the TNM staging. Choosing the correct treatment at this stage is crucial to both the patient's survival and quality of life. A major goal of this research is to automatically optimize the treatment plan based on the existing data.
The data for this research was gathered by scientists and clinicians at City Hospital, Nottingham. The dataset we use here is made up of over 200 possible attributes for 462 patients. The attributes are generated by recording metrics at the time of tumour removal, these include:

•
Physical data (age, sex etc) • Immunological data (levels of various T Cell subsets) • Biochemical data (levels of certain proteins) • Retrospective data (post-operative survival statistics) • Clinical data (Tumour location, size etc).
In the research into the relationship between immune response and tumour staging there has been some support of the hypothesis that the adaptive immune response influences the behavior of human tumors. In situ analysis of tumorinfiltrating immune cells may therefore be a valuable prognostic tool in the treatment of colorectal cancer [2]. The immune and inflammation responses appear to have a role to play in the responses of patients to cancer [3] but the precise nature of this is still unclear.
This research brings together earlier findings on the nature of the tumour biomarker dataset and builds an ensemble learning solution that offers improved predictive performance for a subset of patients.

II. BACKGROUND
The dataset supplied is a biological dataset and as such has a rich complement of pre-processing issues. For instance, over 10% of the values are missing, with some attributes having over 40% missing values and some patients having over 30% missing values. Missing data poses a problem for most modelling techniques. One approach would be to remove every patient or every attribute with any missing data. This would remove a large number of entries, some of which only have a few missing values that are possibly insignificant. Another approach is to average the existing values for each attribute and to insert an average into the missing value space. The appropriate average may be the mean, median or mode depending on the profile of the data, because of this the handling of missing values attributes with a non-linear effect is particularly difficult.
Much of the data takes the form of human analysis of biopsy samples stained for various markers. Rather than raw cell counts or measurements of protein levels we are presented with thresholded values. For instance, CD16 [4] is found on the surface of different types of cells such as natural killer, neutrophils, monocytes and macrophages. The data contains a simple 0 or 1 representing the existence or otherwise of a significant number of these cells rather than a count of the number of cells. This kind of manual inspection and simplification is true for most of the data and any modeling solution must work with this limitation.
By using a combination of correlation coefficients and expert knowledge the data was reduced down to a set of ~50 attributes. This included removing several measurements that were hindsight dependent (ie. chemo or radio treatment) and correlated with TNM stage. (ie. Dukes stage).
The survival of patients with TNM class 2 and 3 tumours, the middle grade categories, is the most difficult to predict, Single attribute relationships exist within the dataset but are not strong. Analysis of single attributes in relation to survival can yield predictions with accuracy of only 59%.

III. PREPROCESSING
A range of preprocessing methods were applied to the data beyond interpolating. Some patients had extensive missing values, while some attributes were very poorly sampled. There were also some patients who's operation was too recent or who had died of an unrelated cause before the success of the operation could be evaluated. An initial pass followed the following protocol:

Removed patients with data for fewer than 50% attributes
Removed attributes with data for fewer than 50% patients

Removed compound attributes
Next an effort was made to convert non-linear, single attribute relationships into linear ones. In an effort to better represent attributes with non-linear effect we also converted attributes with non-linear effects into linear effects. FLIPL is a good example (figure 2), values of 0 and 3 have poorer prognosis for survival than 1 and 2, thereby giving a non-linear relationship between grade and survival. Merging the values for FLIPL of 0 and 3 into a new group '0' and 1 and 2 into another group '1' means that using the mean value for missing values now has a meaningful representation for the resulting modeling approach.

Figure 2. Relationship between survival and FLIPL category
A range of supervised [10] and unsupervised [11] method have been applied to this dataset both in predicting TNM classes from immune-histochemical data and predicting survival. The fact that an anti-learning method [10] appears to perform as well as any learning methods for most tasks suggests that there are complex behaviours at work within this dataset, coupled with its high dimensionality, leading to relatively poor prediction results.

IV. SUPERVISED ENSEMBLE LEARNING OF SURVIVAL RATES
The data used in this paper has detailed information about post-operative survival, so we can model how attribute values effect survival rates. For the purposes of this work a patient is deemed to have "survived" if they are still alive 5 years after their tumour removal. We initially looked at how linear transformation and attribute selection affected the ability to predict 5 year survival. Details of the neural network modeling approach are given later in this section but at this stage if we just look at the impact of this reduction in non-linearity. We see a much improved performance with survival prediction levels better than the 65% achieved by TNM alone ( figure 3). We can also see that using the top 8 attributes selected by SVM attribute selection [18] provides the best performance.  Figure 4 shows survival curves for patients up to 6 months. The strong difference between survival rates in TNM stage 1 and 4 patients is apparent (ie. at 30 month the survival rate is approximately 95% and 5% for these 2 groups). The difference between patients with TNM stage 2 and 3 cancers is less apparent. After 30 months deaths from colorectal cancer for TNM stage 1 patients increase quite quickly, in percentage terms steeper than any other TNM class. Again focusing on just TNM stage 2 and 3 patients we attempted to predict survival using both AI techniques and the TNM stage itself. The term "survival" is somewhat subjective but for the purposes of this work we used 5 years as the threshold for survival. Using the TNM stage alone to predict survival gives an accuracy of 64.6% (155 correct from 240). This is achieved by stating that all type 2 tumour patients will survive and all type 3 will not. If we use the cell marker statistics with patient physical details (such as age and sex) we can achieve a slightly higher predictive performance of 65.4% on the unseen test by using the top 8 attributes (table 1) selected by SVM attribute selection [12] followed by a trained Neural network [4]. As well as the physical characteristic of age, these 8 also included T Cell levels for CD24 and Tstroma and chemicals such as Interleukin 17 (IL17) signalling the expression of certain genes such as P27. The SVM based attribute selection method uses recursive feature elimination where the SVM is trained multiple times and the attributes subsequently evaluated post-training. We have already shown that this dataset shows anti-learning properties [8], whereby predicting TNM stage from immunohistochemical markers is best tackled using an anti-learning approach. An anti-learning approach [9,10], using the bottom 6 attributes from the SVM attribute selection approach (table 1) achieves a 61.3% prediction rate. This included indicators such as the patients sex and levels of antibodies like clxcl10 and cxcr4.
These three approaches use different attributes to perform their prediction and there are many inconsistencies between the predictions. This can be used to our advantage by measuring performance, in an ensemble manner, on patients where 2 or all 3 of the models agree. This agreement will be with a subset of patients so will not apply to every patient, but the ability to give SOME patients a BETTER prediction of survival is extremely valuable. Conversely, where there isn't agreement the possibility of being less confident about a prediction could also be useful. Table 2 shows the individual performance of each model and also the performance when models agree. For example, when the simple TNM model and the neural network model for the top 8 attributes agree, we achieve a 79.2% prediction for survival. This can be viewed logically as:

If Learned Neural model predicts a patient will survive 5 years AND Patient is TNM type 2 OR If Learned Neural model predicts a patient will not survive five years AND Patient is TNM type 3 THEN We can be ~80% confident that our prediction is correct ELSE Patient survival cannot be predicted with any reliable accuracy
The trained neural network used for this predictive task is shown in figure 5. While the non-linearity of a neural network decision making is notoriously difficult to glean information from, the relative simplicity of this neural approach means equation synthesis [13] yields formulas with some qualitative value, achieving predictive values of ~60% where models agree One interesting observation about this is that survival of TNM 3 patients with a positive prognosis from the model have a better survival rate that TNM 2 patients with a negative prognosis. This is shown more clearly by plotting the 4 corresponding survival curves ( fig. 6) We have presented results for a unique dataset based on the biochemical and factors associated with colorectal tumour patients. This dataset is limited in many ways, but extremely important nonetheless and modeling any relationships or features based on the dataset to hand is an urgent priority. Generally, whether attempting to predict TNM stages or survival, patients at TNM stage 1 and 4 have more clear indicators in the attribute set. TNM stage 2 and 3 provides a much more challenging prediction task, so much so that the TNM stage appears much less important when predicting survival for these 2 stages than other indicators.
The dataset used here has several drawbacks when it comes to building robust cause-effect models. The 2 main issues are the missing values and the high dimensionality. By preprocessing the dataset to convert attributes that may have a non-linear effect into linear attributes missing values can be represented as means of all values with a more stable meaning. This pre-processing step also makes resulting machine learning approach more capable of reaching global minima. The second issue of high dimensionality is tackled by using an attribute selection approach first demonstrated on another cancer dataset. We not only use the most highly ranked attributes here but by using anti-learning on the lowest ranked attributes we can produce a another, distinct model of the data.
When looking specifically at survival, using 3 unique predictive approaches allows us to compare predictions from all three approaches. The amount of differences between the 3 approaches could be inferred from the lack of relationships between TNM staging and the immunohistochemistry [8] and the lack of a relationship between unsupervised clusters and TNM stages [11]. So for the 240 patients, there was only agreement between 2 of the approaches for between 103 and 140 patients but when agreement occurred, predictive performance increased up to a maximum of 82.5%. This level of accuracy for predicting survival of patients with TNM stage 2 and 3 tumours is unprecedented, albeit on a small subset of patients. This approach offer an important opportunity for clinicians to improve prognosis for patients but also, any information gained by analysing the agreeing models can be fed back to researcher in their endeavours to improve treatment options at a cellular level.