{'fraction_non_alphanumeric': 0.03812503621299032, 'fraction_numerical': 0.007590242771887131, 'mean_word_length': 4.670170827858081, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reliability-based Error Detection for Feedback Communication with Low Latency

This paper presents a reliability-based decoding scheme for variable-length coding with feedback and demonstrates via simulation that it can achieve higher rates than Polyanskiy et al.'s random coding lower bound for variable-length feedback (VLF) coding on both the BSC and AWGN channel. The proposed scheme uses the reliability output Viterbi algorithm (ROVA) to compute the word error probability after each decoding attempt, which is compared against a target error threshold and used as a stopping criterion to terminate transmission. The only feedback required is a single bit for each decoding attempt, informing the transmitter whether the ROVA-computed word-error probability is sufficiently low. Furthermore, the ROVA determines whether transmission/decoding may be terminated without the need for a rate-reducing CRC.


I. INTRODUCTION
Polyanskiy et al. [1] tightly characterized the back-off from capacity at short blocklengths without feedback by providing achievability and converse bounds on the maximum rate, along with a normal approximation using the channel dispersion (i.e., the stochastic variation of the channel) that closely approximates both bounds. The results of [1] show that there is a severe penalty in the maximum achievable rate for small blocklengths (on the order of several hundred bits or less).
In [2], Polyanskiy et al. investigated how including feedback improves the maximum achievable rate at short blocklengths. Noiseless feedback does not increase the asymptotic (Shannon) capacity of memoryless channels [3], but it can significantly improve the achievable rate at short blocklengths. For (even the best) fixed-length block codes paired with an ARQ strategy, the maximum rate is slow to converge to the asymptotic capacity. However, when variable-length coding is used on channels with noiseless feedback, the maximum rate can improve dramatically [2] as compared to the no-feedback case for short average blocklength.
Polyanskiy et al. considered two main categories of coding with feedback in [2]: variable-length feedback (VLF) coding, in which the receiver decides when to terminate transmission based on a desired probability of error ǫ, and variablelength feedback coding with termination (VLFT), in which the receiver provides full, noiseless feedback to the transmitter, which uses an infinitely reliable feedforward channel to terminate the transmission when the receiver has decoded to the correct codeword. This research was supported by National Science Foundation Grant CIF CCF 1162501.
In [4], we presented a VLFT scheme based on a ratecompatible sphere-packing (RCSP) analysis and tail-biting convolutional codes. We showed that when constrained to limited decoding attempts, VLFT implemented with ratecompatible, punctured, tail-biting convolutional codes can provide higher throughput than the random coding lower bound of [2].
In this paper, we focus on VLF codes and demonstrate a scheme that achieves a higher rate than the random coding achievability bound of [2]. In particular, we show that trellisbased codes (e.g., convolutional codes) in which decoding is attempted after each received symbol using the reliability output Viterbi algorithm (ROVA) [5] can deliver rates surpassing the VLF random coding bound.
The remainder of the paper proceeds as follows: Sec. II reviews the VLF results of [2]. Sec. III presents the reliability output Viterbi algorithm (ROVA) and its use in the VLF setting. Sec. IV shows simulation results for VLF using convolutional codes and the ROVA, comparing these results with finite-blocklength bounds on the maximum rate for both the binary symmetric channel (BSC) and additive white Gaussian noise (AWGN) channel. Sec. V concludes the paper.

II. VARIABLE-LENGTH FEEDBACK (VLF) CODES
In the variable-length feedback (VLF) coding setting, the receiver attempts to decode the true message W * based on the sequence of n symbols that have been received so far, Y n . The receiver terminates the transmission when its estimate of the messageŴ is sufficiently reliable to satisfy the ǫ error requirement, i.e., P(Ŵ |Y n ) = P(X n |Y n ) ≥ 1 − ǫ, wherê X n is the transmitted sequence corresponding to messageŴ .
The transmitter is informed of the receiver's requests for additional coded symbols via noiseless ACK/NACKs, requiring only one bit of feedback per forward channel use (i.e., we are considering stop-feedback codes [2], or decision feedback [10]). We denote average blocklength by ℓ, the cardinality of the message alphabet W by M , and the required average probability of message error by ǫ.
where γ is used as a threshold for determining the hitting times τ andτ : This lower bound uses random coding to prove that some code exists with at least the given cardinality M , though it doesn't specify how to efficiently compute the information densities i(X n ; Y n ) for each of the M codewords, for n = 1, 2, . . .
where h b (ǫ) is the binary entropy function. When the maximal relative entropy C 1 is finite, we have the following converse result, which is tighter than Thm. 2: Theorem 3 ( [2, Theorem 6]): For a DMC with 0<C≤C 1 <∞ and 0 < ǫ ≤ 1 − 1 M , any (ℓ, M, ǫ) VLF code satisfies: where As shown in Fig. 1 for the binary symmetric channel with crossover probability p=0.05, there is a considerable gap between the lower (achievability) and upper (converse) bounds on the maximum rate at short blocklengths. In this paper we demonstrate that convolutional codes can deliver performance surpassing the lower bound, suggesting that other bounding techniques besides those based on random coding may be appropriate for especially short blocklengths.

III. THE RELIABILITY OUTPUT VITERBI ALGORITHM
In order to use VLF codes in practice, the receiver must compute the probability that the codewordX n of length n it has decoded is correct, P(X n |Y n ). This can be calculated as which can be further simplified if each of the codewords X n m ′ is a priori equally likely, i.e., P(X n m ) = P(X n m ′ ) ∀m = m ′ . This yields In general, the denominator in (14) may be computationally intractable when the message set cardinality M is large. However, in much the same way that the Viterbi algorithm takes advantage of the trellis structure of convolutional codes to compute P(Y n |X n ) for maximum-likelihood decoding, an augmented Viterbi decoder referred to as the reliability output Viterbi algorithm (ROVA) [5] can be used to compute P(X n |Y n ) exactly with relative efficiency. The complexity of the ROVA is linear in the blocklength and exponential in the constraint length of the code (i.e., it has complexity on the same order as that of the original Viterbi algorithm). This probability can also be computed approximately by the simplified (approximate) ROVA [7]. The ROVA can be used to compute the probability of word error for any finite-state Markov process observed via memoryless channels (e.g., in maximum-likelihood sequence estimation for signal processing applications).

A. Reliability-based Retransmissions
In [8], Fricke et al. proposed a reliability-based retransmission criteria for hybrid ARQ, using the word error probability calculated by the decoder. Similarly, in order to investigate the maximum rate at short blocklengths, we use the ROVA to compute P(X n |Y n ). If the computed word error probability is larger than the target error probability ǫ, our decoder signals that additional codeword symbols are required (e.g., sends a NACK), and the transmitter sends another coded symbol. When P(X n |Y n ) is computed exactly, this scheme guarantees that the overall undetected error rate will converge to a value less than the target ǫ.
As compared to setting aside some parity bits to be used only for error detection (e.g., in a CRC), a reliability-based feedback approach allows all coded symbols to be used for both error correction and detection, improving throughput.

B. Relationship to Generalized Decoding
Hof et al. [9] provides a modification to the Viterbi algorithm which permits erasure decoding according to Forney's generalized decoding rule [10], based upon a predetermined erasure threshold T . Using Forney's rule, a decoder picks codeword X n m if the following is satisfied: which is equivalent to the following condition: We note that setting the threshold T according to nT = log 1−ǫ ǫ coincides with the ROVA, in which a target undetected error probability ǫ is specified. Like that of the ROVA, the complexity of Hof's modified Viterbi algorithm [9] is linear in the blocklength and exponential in the constraint length. The algorithms are functionally equivalent, though the ROVA computes P(Y n ) in order to yield P(X n |Y n ), while Hof's algorithm computes m ′ =m P(Y n |X n m ′ ).

C. Throughput and Latency
Bounds on the maximum rate in [2] assume that an infinitelength codebook is available, i.e., that an infinite number of coded symbols may be transmitted until the receiver makes a reliable decoding decision. While such infinite-length code constructions exist (e.g., rateless fountain codes), we demonstrate that the combination of decoding after every symbol and ACK/NACK feedback controlling additional transmissions delivers high rates at short blocklengths even when the codewords have finite length. Similar behavior is seen in [11], which explores the effect of finite-length codewords on the achievable rates of VLFT coding.
We encode a message with k = log M message bits into a mother codeword of length N . The initial transmission is accomplished by pseudo-random rate-compatible puncturing of the mother code [12], such that one symbol is transmitted at a time and the receiver uses all received symbols to decode.
If the receiver requests additional redundancy after the N symbols have been exhausted, the transmitter begins resending the original sequence of symbols and decoding starts from scratch. While some benefit can be accrued by retaining the N already transmitted symbols (for example, by Chase code combining), we do not exploit this opportunity in our simulations for simplicity.
The latency ℓ (i.e., average number of channel uses, or average blocklength) and the throughput R t of the proposed scheme are given by where P NACK (i) is the probability of a NACK generated because the ROVA computed the probability of error to be larger than ǫ when i coded symbols have been received, and P UE is the overall probability of undetected error. Both P NACK (i) and P UE depend on the target ǫ. 1 We have included the factor (1 − P UE ) in the throughput expression to emphasize that we are only counting messages that are decoded successfully at the receiver (i.e., the goodput). Table I lists the rate 1/3 convolutional codes from [13, Table  12.1] that were used as mother codes for simulations. The codes selected have the optimum free distance d free , which is 1 We obtain P NACK (i) and P UE via simulation.  listed along with the analytic traceback depth L D [14]. Zerotail trellis termination is used to facilitate the ROVA, resulting in rate loss (compared to a tail-biting code with no termination bits) at short blocklengths. For a code with ν memory elements and rate R = k+ν N , the code's effective information rate is R eff = k N and the rate loss factor is ν k+ν . As part of the ROVA, the original Viterbi algorithm is used to compute the maximum-likelihood estimate of the transmitted sequence X n (representing the mother codeword X N ) after each new symbol is received. As soon as the estimate is sufficiently reliable, i.e., P(X n |Y n ) ≥ 1 − ǫ, transmission terminates and a new codeword is simulated. Though the upper and lower bounds for VLF codes coincide asymptotically, there is a considerable gap when latency is below 100 bits, a region in which convolutional codes can deliver high rates. At the shortest blocklengths, the 64-state code with the fewest memory elements performs best, due to the trellis-termination rate loss of the codes with larger constraint lengths. However, as the message size k increases (and the latency ℓ increases), the larger 1024-state code delivers superior throughput performance. As the latency continues to increase, the codes' throughputs fall below that of the VLF achievability bound. As the average latency grows, the power of random coding grows but the power of the convolutional codes does not improve significantly once the average latency is beyond twice the traceback depth L D of the convolutional code [14]. Fig. 1 also includes information-theoretic limits on the maximum rate attainable at short blocklengths without feedback. The "Max. rate for fixed-length block code, no feedback" curve uses the channel dispersion to compute the maximum rate, which tightly approximates both the achievability and converse bounds when there is no feedback [1]. The convolutional codes shown in Fig. 2 assume transmission over a binary-input AWGN (BI-AWGN) channel (i.e., using BPSK signaling) with soft-decision decoding, which has a maximum Shannon capacity of 1 bit per channel use even when the SNR P is unbounded. However, we have compared the throughput of the ROVA simulations with the capacity C AWGN and VLF bounds for the full AWGN channel (i.e., with real-valued inputs drawn i.i.d. ∼ N (0, P )). For SNR=2 dB and capacity 0.6851 this is a minor concern. However, simulations at higher SNRs would require a higher order modulation (e.g., QAM) to achieve rates above 1.

V. DISCUSSION AND CONCLUSION
For latencies (average blocklengths) on the order of 50 or 75 transmissions and less for the BSC and AWGN channel, respectively, VLF simulations with convolutional coding and ROVA outperform the random coding bound on VLF codes. Furthermore, every operation performed in the simulation is implementable and only one bit of feedback is required per decoding attempt. As discussed above, the ROVA for computing the probability of error associated with the most likely codeword has the same order of complexity as the Viterbi algorithm.

A. Grouped Transmissions for Practical Decoding
For comparison with the VLF random coding bounds, we focused attention to the case where decoding is attempted every symbol. Decoding less frequently is more practical due to the round-trip delay inherent in the feedback loop and because of the complexity of performing the ROVA after each received symbol. Decoding (with the ROVA) only after groups of symbols ("packet" transmissions) is a natural extension of this work. Limiting the frequency of decoding increases latency, but the additional latency can be minimal if the decoding interval is well-chosen, as shown for VLFT in [11]. Fricke et al. [8] used this approach in a reliability-based hybrid ARQ scheme, though that work was not focused on the shortblocklength regime.

B. On the Use of Convolutional Codes
Convolutional codes were chosen based on their errorcorrecting performance at short blocklengths (as compared to, for example, LDPC and turbo codes) and relatively low decoding complexity. In our simulations, throughput performance flattens after latency reaches about 75 symbols, consistent with the analytical traceback depths of L D ≤ 34. Unlike LDPC codes and turbo codes, the power of a convolutional code does not increase with blocklength; blocklengths greater than two or three times the analytical traceback depth won't significantly lower the error rate and hence won't improve throughput. The achievability of Thm. 1 is still valid; some code with the specified performance exists, but convolutional codes are not likely candidates for achievability at moderate blocklengths.
Recent work by Maiya et al. [15] compared fixedblocklength convolutional codes and LDPC codes without feedback to determine which codes yielded the best performance at low latencies (not in an incremental redundancy setting). They showed that for a fixed target error rate (e.g., BER = 10 −6 ) and code rate (e.g., R c = 1 2 ), Viterbi-decoded convolutional codes offered the best performance at low latency (e.g., less than 100 bits) and that LDPC codes decoded with iterative message passing offered the best performance for high latencies (e.g., greater than 220 bits). In an intermediate range of latencies (e.g., 100 to 220 bits), convolutional codes with stack sequential decoding were optimal. 2 This suggests that in order to deliver throughput above the VLF lower bound at moderate blocklengths, LDPC codes or stack sequential decoding of convolutional codes may be suitable.

B. Computation of VLF(ǫ) Achievability Curve
Consider the following bound on P[τ ≤ n]: where the last inequality follows because i(X τ ; Y τ ) ≥ γ by definition in (3). Accordingly, we can write the following which leads to a looser bound on the error probability: For a given error constraint ǫ ′ , we pick the smallest γ such that the right-hand side of (32) is smaller than ǫ ′ , and then compute the average blocklength ℓ as For each value of n, the term P[i(X n ; Y n ) < γ] can be evaluated numerically using the expression for i(X n ; Y n ) in (25). For the AWGN channel, this computation involves a 3dimensional integral over the random variables Z, χ 2 1 , and χ 2 2 .