Abstract
In this work, we investigate a coding strategy devised to increase the throughput in hybrid ARQ (HARQ) transmission over block fading channel. In our approach, the transmitter jointly encodes a variable number of bits for each round of HARQ. The parameters (rates) of this joint coding can vary and may be based on the negative acknowledgment (NACK) provided by the receiver or, on the past (outdated) information about the channel states. These new degrees of freedom allow us to improve the match between the codebook and the channel states experienced by the receiver. The results indicate that significant gains can be obtained using the proposed coding strategy, particularly notable when the conventional HARQ fails to offer throughput improvement even if the number of transmission rounds is increased. The new cross-packet HARQ is also implemented using turbo codes where we show that the theoretically predicted throughput gains materialize in practice, and we discuss the implementation challenges.
I. INTRODUCTION
In this work, in order to improve the throughput of the HARQ transmission over block-fading channel, we propose to use joint coding of multiple information packets into the same channel block and we develop methods to optimize the coding rates.
I. INTRODUCTION
HARQ is used in modern communications systems to deal with unpredictable changes in the channel (due to fading), and with the distortion of the transmitted signals (due to noise). HARQ M. Jabi, A. Benyouss, and L. Szczecinski are with INRS-EMT, University of Quebec, Montreal, Canada. e-mail: {benyouss,jabi,gtapia@example.net, E. Pierre-Doray is with Polytechnique de Montréal, Canada; he was also with INRS-EMT when this work was carried out. e-mail: {gtapia@example.net} relies on the feedback/acknowledgement channel, which is used by the receiver to inform the transmitter about the decoding errors (via NACK) and about the decoding success, via positive acknowledgment (ACK). After NACK, the transmitter makes another transmission round which conveys additional information necessary to decode the packet. This continues till ACK is receiver and then a new HARQ cycle starts again for another information packet. In so-called truncated HARQ, the cycle stops also if the maximum number of rounds is attained.
I. INTRODUCTION
As in many previous works, e.g., [1] , [2] , we will consider throughput as a performance measure assuming that residual errors are taken care of by the upper layers [3] . We consider here the "canonical" problem defined in [1] , where the channel state information (CSI) is available at the receiver but not at the transmitter, which knows only its statistical description. The essential part of HARQ is channel coding, which is done over many channel blocks as long as NACKs are obtained over the feedback channel.
I. INTRODUCTION
It was shown in [1] that HARQ's throughput may approach the ergodic capacity of the channel with sufficiently high "nominal" coding rate per round. However, such an approach is based on large number of HARQ rounds, and thus has a limited practical value: long buffers are required which becomes a limiting factor for implementation of HARQ [4] .
I. INTRODUCTION
On the other hand, using finite nominal coding rate and truncated HARQ, the difference between the throughput achievable using HARQ and the theoretical limits may be large, especially, when we target throughput close to the nominal rate [2] , [5] .
I. INTRODUCTION
To address this problem, various adaptive versions of HARQ were proposed in the literature.
I. INTRODUCTION
For example, [6] - [12] suggested to vary the length of the codewords so as to strike the balance between the number of channel uses and the chances of successful decoding. Their obvious drawback is that the resources assigned to the various HARQ rounds are not constant which may leave an "empty" space within the block.
I. INTRODUCTION
To deal with this issue, it was proposed to share the block resources (power, time or bandwidth) between various packets in e.g., [3] , [13] - [16] , to encode many packets into predefined size blocks as done in [17] , [18] , or to group variable-length codewords to fill the channel block [11] , [19] . A simplified approach was also proposed in [20] to transmit the redundancy using two-step encoding.
I. INTRODUCTION
These approaches implicitly implement a joint coding of many packets into a single channel block. Here, we want to address the issue of cross-packet coding explicitly. The idea of this Cross-packet HARQ (XP-HARQ) is to get rid of the restricting assumptions proper to various heuristics developed before and to use a generic joint HARQ encoder accepting many information packets and encoding them into a common codeword which fills the channel block.
I. INTRODUCTION
The contributions of this work are the following:
I. INTRODUCTION
• We propose a general framework to analyze joint encoding of multiple packets which allow us to derive the relationship between the coding rates and the throughput. Our approach to cross-packet coding is similar to the one shown in [21] - [24] , which, however, did not optimize the coding parameters. The optimization was proposed in [25] , however, due to complex decoding rules, it was very tedious and thus limited to the case of a simple channel model. In our work we simplify the problem assuming asymptotically long codewords are used, which leads to a compact description of the decoding criteria and allows us to solve the rate-optimization problem.
I. INTRODUCTION
• We consider the so-called multi-bit feedback to adapt the coding rates to the channel state experienced by the receiver in the past transmission rounds of HARQ. The same idea was exploited already e.g., in [3] , [6] , [9] , [11] , [12] , [26] - [31] . The assumption of multi-bit feedback not only simplifies the optimization but also yields the results which may be treated as the ultimate performance limits of any adaptation schemes when the instantaneous CSI is not available at the transmitter.
I. INTRODUCTION
• We optimize the coding rates using the Markov decision process (MDP) formulation [32, Chap. 4] , and compare the proposed, XP-HARQ to the conventional incremental redundancy HARQ (IR-HARQ) from the perspective of attainable throughput. For the particular case of two transmission round, we obtain the optimal solution in closed-form.
I. INTRODUCTION
• We also present an analytical formula for attainable throughput using heuristic rate-adaptation inspired by the numerical results and which presents a notable gain over the conventional IR-HARQ.
I. INTRODUCTION
• To obtain an insight into the practical constraints on the system design, we also show the results obtained when a turbo coding is adopted.
I. INTRODUCTION
The remainder of the paper is organized as follows. We define the transmission model as well as the basic performance metrics in Sec. II. The idea of cross-packet coding is explained in Sec. III. The optimization of the rates in the proposed coding strategy is presented in Sec. IV. October 14, 2018 DRAFT
I. INTRODUCTION
We discuss the effects of using a practical encoding/decoding schemes in Sec. V. The numerical results are presented in form of short examples throughout the work to illustrate the main ideas.
I. INTRODUCTION
Conclusions are presented in Sec. VI. The optimization methods used to obtain the numerical results and the proof of decoding conditions are presented in appendices.
II. CHANNEL MODEL AND HARQ
We consider a point-to-point IR-HARQ transmission of a packet m over a block fading channel. After each transmission, using a feedback/acknowledgement channel, the receiver tells the transmitter whether the decoding of m succeeded (ACK) or failed (NACK). We thus assume that error detection is possible (e.g., via cyclic redundancy check (CRC) mechanisms) and that the feedback channel is error-free. For simplicity, we ignore any loss of resources due to the CRC and the acknowledgement feedback.
II. CHANNEL MODEL AND HARQ
The transmission of a single packet may thus require many transmission rounds which continue till the Kth round is reached or till ACK is received. When K is finite, we say that HARQ is truncated, otherwise we say it is persistent. We define a HARQ cycle as the sequence of transmission rounds of the same packet m.
II. CHANNEL MODEL AND HARQ
The received signal in the kth round is given by
II. CHANNEL MODEL AND HARQ
where z k and x k modelling, respectively, the noise and the transmitted codeword are N sdimensional vectors, each containing independent, identically distributed (i.i.d.) zero mean, unitvariance random variables; snr k is thus the signal-to-noise ratio (SNR) at the receiver. The elements of z k are drawn from complex Gaussian distribution, and elements of x k -from the uniform distribution over the set (constellation) X .
II. CHANNEL MODEL AND HARQ
During the kth round, snr k is assumed to be perfectly known/estimated at the receiver and unknown at the transmitter; it varies from one round to another and we model snr k , k = 1, . . . , K as the i.i.d. random variables SNR with distribution p SNR (snr).
A. Conventional HARQ
In the conventional IR-HARQ, a packet m ∈ {0, 1} RNs is firstly encoded into a codeword 
A. Conventional HARQ
Following [1] , [27] , we assume N s large enough to make the random coding limits valid.
A. Conventional HARQ
Then, knowing the mutual information (MI) I k = I(X k ; Y k |snr k ) between the random variables X k and Y k modeling respectively, the channel input and output in the kth block, allows us to determine when the decoding is successful or not: the decoding failure occurs in the kth round if the accumulated MI at the receiver is smaller than the coding rate
A. Conventional HARQ
where I Σ k k l=1 I l is the MI accumulated in k rounds. Of course, the MI depends on the SNR, i.e., I k ≡ I k (snr k ).
A. Conventional HARQ
IR-HARQ can be modelled as a Markov chain where the transmission rounds correspond to the states, and the HARQ cycle corresponds to a renewal cycle in the chain. Thus, the long-term average throughput, defined as the average number of correctly received bits per transmitted symbol, may be calculated from the renewal-reward theorem: it is a ratio between the average reward (number of bits successfully decoded per cycle) and the average renewal time (the expected number of transmissions needed to deliver the packet with up to K transmission rounds) [1] .
A. Conventional HARQ
Let f k Pr {NACK k } , k ≥ 1 be the probability of k successive errors so the probability of successful decoding in the kth round is given by
A. Conventional HARQ
The throughput is then calculated as follows [1] 
A. Conventional HARQ
Because the instantaneous CSI is not available at the transmitter, the highest achievable throughput is given by the ergodic capacity 2 of the channel [1] , [33] C E SNR [I(SNR]).
A. Conventional HARQ
However, achieving C is not obvious: as shown in [1] , it can be done growing simultaneously R and K to infinity but this approach is impractical due to large memory requirements. 
A. Conventional HARQ
and
A. Conventional HARQ
The optimum throughput-rate pairs are then (η 
A. Conventional HARQ
where snr is the average SNR.
A. Conventional HARQ
We calculate I(snr) and the average C using the numerical methods outlined in [34, Ch. 4.5] and compare it in Fig. 1 with the throughput η ir K when K ∈ {2, ∞}. 4 The
results indicate that i) there is a significant loss with respect to the ergodic capacity when using truncated HARQ, and ii) increasing the number of transmission rounds (K = ∞) helps recovering the loss for a
small-medium range of throughput (e.g., for η ir = 1 we gain ∼ 3dB and the gap to C is less than 1dB), but it is less useful in the region of high η ir K , i.e., in the vicinity of the maximum attainable throughput (e.g., for η ir = 3, we gain 1dB but the gap to C is still ∼ 5dB). We highlight this well-known effect [2] to emphasize later the gains of the new coding strategy.
III. CROSS-PACKET HARQ
The examples shown previously indicate that the conventional coding cannot bring the throughput of HARQ close to the capacity unless the nominal coding rate R and the number of rounds K increase. We would like now to exploit a new coding possibility consisting in joint coding of packets during the HARQ cycle. 4 η ir ∞ can be computed by taking K large enough in (5) as suggested in [2] or by evaluating the throughput using the method outlined in the Appendix B and considering the policy π(s) = R if s = (0, 0) and π(s) = 0 otherwise. We opt for the later method. Let us start with the case of two transmission rounds. In the first round, we use the nominal rate R 1 is used, i.e., the packet m 1 ∈ {0, 1} R 1 Ns is encoded
III. CROSS-PACKET HARQ
and transmitted over the channel (1) producing
III. CROSS-PACKET HARQ
is the encoding at the kth round.
III. CROSS-PACKET HARQ
If the packet m 1 is decoded correctly (which occurs if I 1 ≥ R 1 ), a new cycle HARQ starts by the transmission of a new packet. However, if the decoding fails, the packet
III. CROSS-PACKET HARQ
Ns is encoded using a conventional code designed independently of the codebook corresponding to the first transmission
III. CROSS-PACKET HARQ
which yields the channel outcome y 2 = √ snr 2 x 2 + z 2 as depicted in Fig. 2 . outcomes y [2] are given by
III. CROSS-PACKET HARQ
where (13) is a constraint over the sum-rate that guarantees the joint decoding of the packets pair (m 1 , m 2 ) while (14) ensures the correct decoding of the packet m 2 . This means, the MI must be accumulated to decode each of the packets even though the decoding is done jointly.
III. CROSS-PACKET HARQ
The formal proof of (13) and (14) is presented in the Appendix A. Similar decoding conditions were presented in the context of physical layer (PHY) security in [35] .
III. CROSS-PACKET HARQ
While the event NACK 1 remains unchanged with respect to the conventional coding, the event NACK 2 means that NACK 1 occurred, as well as, that (13) and (14) are not satisfied
III. CROSS-PACKET HARQ
where R Σ k k l=1 R l and the event E is the complement of E. To pass from (15) to (16) we used the decoding failure implication
III. CROSS-PACKET HARQ
which means that NACK 1 combined with (13) implies (14) .
III. CROSS-PACKET HARQ
The above conditions generalize straightforwardly for any k > 1 with R k being the rate of the packet m k added in the kth round
III. CROSS-PACKET HARQ
To calculate the throughput of such an XP-HARQ, we adopt a similar approach as in (5) but we must account for the reward in the k transmission round given by R Σ k , which yields
III. CROSS-PACKET HARQ
Here, again f k = Pr {NACK k } , k ≥ 1 with NACK k defined by (17) .
III. CROSS-PACKET HARQ
As a sanity check we can set R k = 0, k = 2, . . . , K, and recover the conventional single-packet HARQ, i.e., (18) will be equivalent to (6).
III. CROSS-PACKET HARQ
The fundamental difference of the proposed XP-HARQ with respect to the conventional HARQ appears now clearly in the numerator of (18) which expresses the idea of variable rate transmission due to encoding of multiple packets. Nevertheless, not only the numerator changed with respect to (6) but also the denominator is different due to the new definition of NACK k in (17) .
Example 3 (Two-state channel and XP-HARQ). We consider now the proposed XP-HARQ in
PSfrag replacements
Example 3 (Two-state channel and XP-HARQ). We consider now the proposed XP-HARQ in
. . .
Example 3 (Two-state channel and XP-HARQ). We consider now the proposed XP-HARQ in
Fig . 3 . Illustration of the codebook defined through the coding function Φ1 in (11) and the joint coding function Φ2 in (12) . Each codeword composed of 2Ns symbols is indexed by the packet m [2] . The first Ns symbols are created without indexing by m2 so we artificially repeat them 2 R 2 Ns times to match the number of codewords in the codebook Φ2. For the case when K = 2 and using R 2 = 0.5, we obtain f 1 = 0.25 and f 2 = 0. The throughput is then given by Similarly, for K = 3, we can use the larger value of R 2 (that guarantees our objective of decodability, f 2 < 1), i.e., R 2 = 1. In this case, f 1 = 0.25, and f 2 = Pr I 1 < 1.5 ∧ I Σ 2 < 2.5 = 0.0625. In the third transmission we observe I Σ 3 ∈ (3, 3.5) so, using R 3 = 0.5, we obtain f 3 = 0 and thus the throughput is calculated as
Example 3 (Two-state channel and XP-HARQ). We consider now the proposed XP-HARQ in
which is already quite close to C = 1.375.
Example 3 (Two-state channel and XP-HARQ). We consider now the proposed XP-HARQ in
The improvement of the throughput in XP-HARQ is due to the way the codebook is constructed. While the conventional IR-HARQ, see Sec. II-A, makes a rigid separation of the codewords into the fixed-content subcodewords -an approach which is blind to the channel realizations, in XP-HARQ we match the information content of the codebook following the outcome of the transmissions.
IV. OPTIMIZATION OF THE CODING RATES
Our goal now is to evaluate how well the XP-HARQ can perform. To this end, we will have to find the optimal coding rates R 1 , R 2 , . . . , R K which maximize throughput (18) .
IV. OPTIMIZATION OF THE CODING RATES
Since the objective function is highly non linear, we will use the exhaustive search: for a truncated HARQ this can be done with a manageable complexity.
Example 4 (16QAM, Rayleigh fading -continued).
In Fig. 4 In terms of SNR required to attain η = 3, the gain of XP-HARQ over IR-HARQ varies from
A. Rate adaptation
The possibility of varying the rates during the HARQ cycle opens new optimization space and we want to explore it fully following the idea of adapting the transmission parameters in HARQ on the basis of obsolete CSI considered before, e.g., in [6] , [8] - [11] , [29] , [36] .
A. Rate adaptation
The idea is to adapt the coding rates using obsolete CSIs, I 1 , I 2 , . . . , I k−1 ; this concept remains compatible with the assumption of transmitter operating without CSI knowledge because the obsolete CSIs I 1 , I 2 , . . . , I k−1 cannot be used in the kth round to infer anything about I k (due to i.i.d. model of the SNRs).
A. Rate adaptation
Using this approach, the rate R k will not only depend on the MIs I 1 , . . . , I k−1 but alsoon the past rates R 1 , . . . , R k . 6 This recursive dependence may be dealt with using the MDP framework, where the states of the Markov chain not only indicate the transmission number but also gather all information necessary to decide on the rate, which in the language of the MDP is called an action. The state has to be defined so that i) knowing the action (chosen rate), the state-transition probability can be determined after each transmission, and ii) the reward may be calculated knowing the state and the action. The state defined as a pair
A. Rate adaptation
, which determine the probability of the decoding success, see (17) .
A. Rate adaptation
these two requirements, where we only need to consider the pairs which satisfy R Σ k > I Σ k , otherwise the decoding is successful and the HARQ cycle terminates.
A. Rate adaptation
Thus, the rate adaptation consists in finding the functions (called policies), R l (s l−1 ) maximizing the throughput, which is found generalizing the expression (18)
A. Rate adaptation
where
A. Rate adaptation
indicates the successful decoding in the kth round, and
A. Rate adaptation
is the accumulated rate depending in a recursive fashion on the states of the Markov chain. The probability of k successive errors, f k , may be expressed as (17) considering the dependence of the rates on the states given by (23) . All the expectations are taken with respect to the statesor equivalently -with respect to I 1 , . . . , I K .
A. Rate adaptation
The expression (21) will be useful in Sec. IV-B, however, its maximization with respect to the policies R l (s l−1 ), l = 1, . . . , K will be done using efficient specialized algorithms as explained in Appendix B. In the particular case of two HARQ rounds (K = 2), the optimal rate adaptation policy can be derived in closed form as shown in Appendix C.
A. Rate adaptation
To run the optimization algorithms outlined in Appendix B, we need to discretize the variables involved (states and actions). As for the rates (actions), we use a relatively course discretization step equal to 0.25 and define the action space as the set R = {0.25, 0.5, . . . , R max }. While the results are notably affected by R max , using a finer discretization step did not change the results
significantly.
Here, it is natural to ask a question about the signaling overhead due to proposed adaptation scheme. We thus note that while we assume the outdated MI, I
significantly.
Σ k is discretized with a high resolution when optimizing the throughput (cf. Appendix B), the feedback load is affected by the cardinality of the action space, R: the receiver knows the accumulated MI but only transmits the index of the chosen rate. 
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
To exploit this very regular form, which was also observed solving the related problems in [11] , [29] , we propose to use the following heuristic function inspired by Fig. 7 R
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
where only the rate R 1 needs to be optimized (from Fig. 7 we find R 1 ≈ 3.5). Furthermore, applying (24) recursively we obtain R 2 = I 1 , R 3 = I 2 , . . . , R k = I k−1 ; the identical rateadaptation strategy may be derived from [20, Sec. III].
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
The simplicity of the adaptation function allows us now to evaluate analytically the throughput of XP-HARQ. To this end we need to calculate f l in the denominator of (21) and the expectation in its numerator.
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
We first note that, from (24) we obtain
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
which means that the probability of decoding failure does not change with the index of the transmission round. Thus
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
and (22) may be formulated as
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
From (24) we also obtain R
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
l=1 I l , which allows us to calculate the expectation in the numerator of (21) as
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
whereC = E I 1 I 1 · I I 1 < R 1 is a "truncated" expected MI.
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
Using (29) and (26) in (21), the throughput is calculated as
The improvements due to adaptive XP-HARQ are most notable for high values of the throughput. In particular we observe that • The persistent XP-HARQ halves the gap between the ergodic capacity and the conventional IR-HARQ. For example, the SNR gap betweenη
In the limit, K → ∞, (30) becomes which is the same as [20, Eq. (12)]. Fig. 8 the throughput of optimal XP-HARQ with the heuristic policy (24), which is optimized over R 1 . As expected, the optimal solution outperforms the heuristic policy but the gap is very small (less than 0.5dB). The results are quite intriguing and suggesting that the strategy of [20] based on a doublelayer encoding 7 and a transmission-by-transmission decoding (as opposed to the joint decoding required in XP-HARQ), asymptotically yield the same throughput as the heuristic cross-packet HARQ, whose throughput is also very close to the optimal XP-HARQ.
Example 6 (16QAM, Rayleigh fading -continued). We compare in

Moreover, sinceη
We cannot follow that path here but this relationship should be studied in more details; in particular, the effect of removing the idealized assumption of using a continuous set of rates R, necessary to implement (24), should be analyzed.
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
Until now, we have adopted the perfect decoding assumption, i.e., the decoding error in the kth round is equivalent to the event
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
We will remove now this idealization to highlight also the practical aspect of XP-HARQ.
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
We thus implement the cross-packet encoders in Fig. 2 using turbo encoders. To this end, as shown in Fig. 9 we separate each encoder Φ k into i) a bit-level multiplexer, M, whose role is to interleave the input packets m 1 , . . . , m k and produce the packet, m [k] , ii) a conventional turboencoder (TC), iii) the rate-matching puncturer, P, which ensures that all binary codewords c k have the same length, N c , and iv) a modulator, which maps the codewords c k onto the codewords x k from the constellation X ; since we use 16ary QAM, N c = N s log 2 (M).
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
The multiplexers M k are implemented using pseudo-random interleaving. The encoders (TC) are constructed via parallel concatenation of two recursive convolutional encoders with polyno-
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
parity bits p k . 8 The bits c k are obtained concatenating "fresh" systematic bits m k (those which were not transmitted in the previous rounds) and the parity bits selected from p k via a periodic puncturing.
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
Such a construction of the encoders is of course not optimal and better interleavers and puncturers may be sought; however, their optimal design represents a challenge of its own and must be considered out of scope of the example we present here.
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
The encoding is rather straightforward and can be implemented using conventional elements.
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
The decoding in the kth round is slightly more involved because it is done using outcomes of all transmissions, y [k] . From this perspective, we may see the binary codewords c 1 , . . . , c k as an outcome of 2k concatenated convolutional encoders (two encoders per HARQ round), each producing the sequence with increasing lengths. The decoding of multiple encoding units was already addressed before [37] [38] and requires implementation of 2k Bahl-Cocke-Jelinek-Raviv (BCJR) decoders (one for each of the encoders) exchanging the extrinsic probabilities for the information bits. We implement the serial scheduling, that is, once a BCJR decoder is activated, it must wait till all other BCJR decoders are activated. One iteration is defined as 2k activations.
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
The results we present are obtained using algorithm from the library [39] ; we use N s = 1024 and four decoding iterations.
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
Since we do not have the closed-form formula which describes the probability of error under particular channel conditions, especially when multiples transmissions are involved, the rate-adaptation approach seems to be out of reach and we focus on finding the fixed coding rates R k , k = 1, . . . , K. We use the brute search over the space of available coding rates which verifies the following conditions
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
The results obtained are shown in Fig. 10 where the SNR gap (for the throughput η = 3) between XP-HARQ and the conventional IR-HARQ is ∼ 1.5dB for K = 2 and ∼ 2dB for K = 3dB. We attribute a small improvement of the throughput η xp 3 over η xp 2 to the suboptimal encoding scheme we consider in this example.
V. EXAMPLE OF A PRACTICAL IMPLEMENTATION
We also note that the improvement of η ir 3 with respect to η ir 2 does not materialize. This is because IR-HARQ is optimized for R 1 but, due to limitation of the turbo encoder which generates only 3N b bits, a full redundancy cannot be always obtained and, in such a case, we are forced to repeat the systematic and parity bits. This explains why η We show in Fig. 10 the ergodic capacity where the gap to the throughput of the TC-based transmission is increased by additional 3dB which should be expected when using relativelyshort codewords and practical decoders.
VI. CONCLUSIONS
In this work we proposed and analyzed a coding strategy tailored for HARQ protocol and aiming at the increase of the throughput for transmission over block fading channel. Unlike many heuristic coding schemes proposed previously, our goal was to address explicitly the issue of joint coding of many packets into the channel block of predefined length. With such a setup, the challenge is to optimize the coding rates for each packet which we do efficiently assuming existence of a multi-bits feedback channel which transmit the outdated CSI experienced by the receiver.
VI. CONCLUSIONS
The throughput of the resulting XP-HARQ is compared to the conventional IR-HARQ indicating that significant gains can be obtained using the proposed coding strategy. The gains are particularly notable in the range of high throughput, where the conventional HARQ fails to offer any improvement with increasing number of transmission rounds. The proposed encoding scheme may be seen as a method to increase the throughput, or as a mean to diminish the memory requirements at the receiver; the price for the improvements is paid by a more complex joint encoding/decoding.
VI. CONCLUSIONS
We also proposed an example of a practical implementation based on turbo codes. This example highlights the practical aspects of the proposed coding scheme, where the most important difficulties are i) the need of tailoring the encoder to provide the jointly coded symbols with the best decoding performance, and ii) the design of the simple decoder. Moreover, the real challenge is to leverage the possibility of adaptation to the outdated CSI. To do so, simple techniques for performance evaluation (e.g., the packet error rate (PER)) based on the expected CSI, must be used; such as, for example those studied in [40] .
APPENDIX A DECODING CONDITIONS OF XP-HARQ
We outline the proof of the decoding conditions (13) and (14), stated in the following Lemma 1.
APPENDIX A DECODING CONDITIONS OF XP-HARQ
The HARQ-code refers to the encoding functions stated in (11) and (12) 
APPENDIX A DECODING CONDITIONS OF XP-HARQ
the error probability is bounded by
APPENDIX A DECODING CONDITIONS OF XP-HARQ
Proof of Lemma 1: We consider the random HARQ-code:
APPENDIX A DECODING CONDITIONS OF XP-HARQ
• Random codebook: we generate 2 Ns·R 1 codewords x 1 and 2 Ns·(R 1 +R 2 ) codewords x 2 , drawn from the uniform distribution over the constellation X .
APPENDIX A DECODING CONDITIONS OF XP-HARQ
• Encoding function: as explained in Sec. III, the encoder starts by sending x 1 which corre- Otherwise a new transmission process starts.
APPENDIX A DECODING CONDITIONS OF XP-HARQ
• Decoding function: if the SNR realizations (snr 1 , snr 2 ) satisfy equations (33) 
APPENDIX A DECODING CONDITIONS OF XP-HARQ
• Error is declared when sequences are not jointly typical. Error events. We define the following error events:
APPENDIX A DECODING CONDITIONS OF XP-HARQ
The properties of the typical sequences imply that, for N s large enough, Pr {E 0 } ≤ ε, and the Packing Lemma [41, p. 46] implies that the probabilities of the events E 1 , E 2 , E 3 are bounded by ε if the following conditions are satisfied
APPENDIX A DECODING CONDITIONS OF XP-HARQ
Since ( To obtain the MDP formulation it is convenient to replace packet-wise notation of (1) with a time-wise model
APPENDIX A DECODING CONDITIONS OF XP-HARQ
where n is the index of the channel block.
APPENDIX A DECODING CONDITIONS OF XP-HARQ
At each time n, the HARQ controller observes the state s[n], and takes an action a[n] = π(a[n]), according to the policy π. The transition probability matrix, Q(a), has the elements
APPENDIX A DECODING CONDITIONS OF XP-HARQ
defining the probabilities of the system moving to the state s ′ ∈ S at time n + 1 conditioned on the system being in the state s ∈ S at time n and the controller taking the action a ∈ A(s), where A(s) is the set of actions allowed in a state s and s∈S A(s) = A. In our case, the actions are the coding rates, which we assume may take any positive value, and thus A(s) = R + .
APPENDIX A DECODING CONDITIONS OF XP-HARQ
A policy π is defined as a mapping π : S → A between the state space, S, and the action space, A. We aim at finding a policy π which maximizes the long-term average throughput
APPENDIX A DECODING CONDITIONS OF XP-HARQ
where R(s, a) is the average reward obtained when taking action a in the state s and the expectations are taken with respect to the random states s[n]. In our case the reward is the number of decoded bits normalized by the duration of the channel block, N s .
APPENDIX A DECODING CONDITIONS OF XP-HARQ
The optimal policy thus solves the following problem: problems, finding such a policy is indeed possible, proof of which we skip for sake of brevity.
APPENDIX A DECODING CONDITIONS OF XP-HARQ
In order to define the state space and the average reward, we deal separately with the truncated and persistent XP-HARQ but in both cases we must track the accumulated rate, R Σ [n] (it defines the reward, R(s, a)), and the accumulated MI, I Σ [n] (it defines the matrix Q). Thus these two variables must enter the definition of the state, s[n].
A. Persistent HARQ
For the persistent XP-HARQ, the state can be defined as a pair
A. Persistent HARQ
and the transition to the state at time n + 1 is defined as 
A. Persistent HARQ
where F c I (x) 1 − F I (x) and F I (x) is the cumulative density function (CDF) of I.
B. Truncated HARQ
In the truncated HARQ, a new HARQ cycle starts also if the maximum number of allowed rounds is attained (even if the message is not decoded correctly). Thus i) the index of the transmission round, k, must enter the defining of the state, ii) we need to make a distinction between the decoding success/failure of the last round. We thus define the state as
B. Truncated HARQ
where k[n] and M[n] ∈ {ACK, NACK} are respectively, the number of rounds and the decoding result after the transmission in block n. The system dynamic is described as follows: Knowing the rate of the first transmission, R 1 , the optimization problem (42) may be solved analytically for K = 2 using (21)
B. Truncated HARQ
Since f 1 is independent of R 2 (·), solving (48) is equivalent to finding, for each value of I 1 < R 1 , the optimal R 2 (·) as follows
B. Truncated HARQ
which is a one-dimension optimization problem, that can be solved analytically, provided
B. Truncated HARQ
is known.
B. Truncated HARQ
In the case of Gaussian codebook, i.e., when the MI is given by I k = log 2 (1 + snr k ), the optimal rate adaptation policy is given by the following closed-form R 2 (I 1 ) = max 0, W (2
B. Truncated HARQ
where W (.) is Lambert W function defined as the solution of x = W (x)e W (x) .

{'paper_id': '202669208', 'title': 'J un 2 01 6 Adaptive Cross-Packet HARQ', 's2_url': 'https://api.semanticscholar.org/CorpusID:202669208', 'source': 'S2ORC'}