{'fraction_non_alphanumeric': 0.04557725186718258, 'fraction_numerical': 0.009718347880860253, 'mean_word_length': 4.136815345504969, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Low Complexity Maximum Likelihood Decoding of Convolutional Codes

This paper considers the average complexity of maximum likelihood (ML) decoding of convolutional codes. ML decoding can be modeled as finding the most probable path taken through a Markov graph. Integrated with the Viterbi algorithm (VA), complexity reduction methods such as the sphere decoder often use the sum log likelihood (SLL) of a Markov path as a bound to disprove the optimality of other Markov path sets and to consequently avoid exhaustive path search. In this paper, it is shown that SLL-based optimality tests are inefficient if one fixes the coding memory and takes the codeword length to infinity. Alternatively, optimality of a source symbol at a given time index can be testified using bounds derived from log likelihoods of the neighboring symbols. It is demonstrated that such neighboring log likelihood (NLL)-based optimality tests, whose efficiency does not depend on the codeword length, can bring significant complexity reduction to ML decoding of convolutional codes. The results are generalized to ML sequence detection in a class of discrete-time hidden Markov systems.


I. Introduction
We study the algorithms that reduce the average complexity of maximum likelihood (ML) decoding of convolutional codes. By ML decoding, we mean the decoder uses code-search to find, and to guarantee the output of, the most likely codeword.
Forney showed that ML decoding of convolutional codes is equivalent to finding the most probable path taken through a Markov graph [1]. Denote the codeword length by N and the coding memory by ν. For each time index, the number of Markov states in the Markov graph is exponential in ν. The total number of Markov states is therefore exponential in ν but linear in N. Define the complexity of a decoder as the number of visited Markov states normalized by the codeword length N. Practical ML decoding is often achieved using the Viterbi algorithm (VA) [2] [1], whose complexity does not scale in N but scales exponentially in ν. Well known decoders such as the list decoders [3], the sequential decoders [4], and the iterative decoders [5] are able to achieve near optimal error performance with low average complexity. However, these decoders do not guarantee the output of the ML codeword [6].
If obtaining the ML codeword is strictly enforced (see Section VII for justification), to avoid exhaustive path search, the decoder must develop certain criterion or bound that can be used to disprove the optimality of a Markov path set. This is equivalent to developing an optimality test criterion (OTC) [7] to test whether the ML path (or codeword) belongs to the complementary path set (or codeword set) 1 .
Two major OTCs have been used in the ML decoding of convolutional codes. The first one is the "path covering criterion" (PCC) (explained in [8] and in Appendix A) used in the VA [2] [1]. VA visits all Markov states in chronological order [1]. For each time index, the decoder maintains a set of "cover" (defined in Appendix A) Markov paths each passing one of the Markov states [1]. According to the PCC, the "cover" Markov path passing a Markov state disproves the optimality of all other Markov paths passing the same state. The second OTC is the sum log likelihood (SLL)-based OTCs used extensively in the sphere decoder [10] [9]. Sphere decoder models ML decoding as finding the lattice point closest to the channel output in the signal space [9]. Hence the distance between the channel output and an arbitrary lattice point upper bounds the distance from the channel output to the ML codeword. Such distance bound is based on the SLL of the corresponding codeword, and is used in the sphere decoder [10] [9] as well as other ML decoders [7] as the key means to avoid exhaustive codeword search. In [11] [12], Vikalo and Hassibi showed that PCC-based and SLL-based optimality tests can be combined to find the ML codeword without visiting all Markov states.
Assume PCC-based optimality test is always implemented. In this paper, we first show that additional complexity reduction brought by the SLL-based optimality test diminishes as one fixes the coding memory ν and takes the codeword length N to infinity. Such inefficiency is due to the fact that SLL-based OTC does not exploit the structure of the convolutional code. Searching the ML codeword is equivalent to finding the ML source message, which contains a sequence of source symbols. We show whether the ML message contains a particular symbol at a given time index can be tested using an OTC that depends only on the log likelihood of channel output symbols in a fixed- 1 In the literature such as [7], OTC refers to a criterion designed to test whether a single codeword is optimum. In this paper, we extend the definition of OTC to a general criterion that can either verify or disprove the optimality of a codeword set. sized time neighborhood. We call such test the neighboring log likelihood (NLL)-based optimality test, and show its efficiency does not depend on the codeword length. We theoretically demonstrate that NLL-based optimality test can bring significant complexity reduction to ML decoding when the communication system has a high signal to noise ratio (SNR). Complexity of the decoder using SLL-base optimality test, on the other hand, remains the same as the VA for all SNR if the codeword length is taken to infinity. The results are also generalized to ML sequence detection in a class of discrete-time hidden Markov systems [13].

II. Problem Formulation
Let C be an (n, k) convolutional code over GF(q) defined by a polynomial generater matrix G(D) [14], where D is the delay operator; ν is the coding memory; G[l], l = 0, . . . , ν − 1, are k × n matrices over GF(q). Assume G(D) is a minimal encoder [14].
Denote the source message by a sequence of vector symbols, where d is the time index, possibly negative; x[d], ∀d, are row vectors of dimension k over GF(q).
The encoded message, or the corresponding codeword, is given by To simplify the presentation, we assume time index d takes all integer values. We assume x[d] = 0 for d < 0 and d ≥ N. We term N the codeword length.
Define a function g q (y) that maps y from GF(q) to R (the set of real numbers) in one-to-one sense. If y(D) is a vector sequence, g q (y(D)) applies the mapping to each of the elements of y(D), respectively 2 . Assume the codeword is transmitted over a memoryless Gaussian channel. The channel output symbol sequence is given by where i.i.d. Gaussian. Without loss of generality, we define the scaled signal to noise ratio of the system as SNR = 1 σ 2 . In Section VI, we show that the results are generalizable not only to other channel models, but also to a class of hidden Markov systems.
Given the channel output, for any source message x(D) and its corresponding codeword y(D) = x(D)G(D), we define the "negative SLL" as The objective of ML decoding is to find the ML message x M L (D) that minimizes the negative SLL, Throughout this paper, we assume PCC-based optimality test is always implemented. For the sake of completeness, a description of PCC-based optimality test is given in Appendix A.

III. Inefficiency of Sum Log Likelihood-based Optimality Test
For ML decoders using SLL-based optimality test, the decoder first obtains a quick guess of the source message without solving the ML decoding problem. SLL of the obtained message is then used to help disproving the optimality of certain Markov path sets and consequently to avoid exhaustive path search. We make an ideal assumption that the "guessed" message equals the transmitted message 3 .
We show in this section that, even under this ideal assumption, complexity reduction brought by the SLL-based optimality tests still diminishes as we take N to infinity.
Let x(D) be the actual source message, which is also the message "guessed" by the decoder. Let y(D) = x(D)G(D) be the transmitted codeword. The corresponding negative SLL is given by Suppose the decoder wants to test whether it can disprove the optimality of {x(D x d )}, i.e., whether [12] is to find a lower bound, denoted by S L x (x(D x d )), of the negative SLLs of the messages in {x(D x d )}.
If the lower bound S L x (x(D x d )) is larger than S x (x(D)) obtained in (7), then we have In Appendix B, we show that the SLL lower bounds appeared in the literature satisfy the following assumption.
Assumption 1: Given {x(D x d )}, let D y d ⊆ [0, N + ν) be the maximum time index set, over which we can find a partial codewordỹ(D y d ) such that for all We assume the existence of a positive constant ǫ ∈ (0, 1], whose value does not depend on N, such that As demonstrated in [11][7], if we fix N, using S L x (x(D x d )) > S x (x(D)) as the OTC to disprove the optimality of message set {x(D x d )} can bring significant complexity reduction to ML decoding, especially under high SNR. However, if we define D e ⊆ D y d as the subset of time indices corresponding to the erroneous codeword symbols, i.e., the following proposition shows that SLL-based optimality tests become inefficient if N − |D x d | is taken to infinity while |D e | is kept finite.
Lemma 1: Assume the generater matrix G(D) is fixed, and therefore the constraint length ν is fixed. Consider message sets characterized by {x(D x d )} for arbitrary D x d but under the constraint of a fixed D e , where D e ⊆ D y d is defined in (11) and the derivation of D y d is specified in Assumption 1. If we fix SNR and take N − |D x d | to infinity, we have If we first take N − |D x d | to infinity and then take SNR to infinity, we have Proof: Since |D y d | ≤ |D x d | + ν, taking N − |D x d | to infinity implies taking N − |D y d | to infinity. According to Assumption 1, we have Since n[d] are i.i.d. Gaussian with covariance matrix σ 2 I, n[d] 2 are i.i.d. χ 2 with mean nσ 2 and variance 2nσ 4 . Therefore Consequently, denote the right hand side of (14) by U 0 , we have with probability one, This yields Since (16) holds for all SNR, the conclusion remains true if we take SNR to infinity after N − |D x d | is taken to infinity 4 .
With the help of Lemma 1, inefficiency of SLL-based optimality tests is characterized by the following lemma.
Lemma 2: Let C sll be the complexity of an ML decoder that only uses PCC-and SLL-based optimality tests for complexity reduction. Let C va be the complexity of the Viterbi decoder, in which, only PCC-based optimality test is used. For any δ > 0, we have, The proof of Lemma 2 is given in Appendix C.

IV. Neighboring Log Likelihood-based Optimality Test
We propose in Theorem 1 a class of NLL-based optimality tests, whose efficiency does not depend on the codeword length N. We show in Section V that these NLL-based optimality tests can significantly reduce the average complexity of ML decoding under high SNR. This is in contrast to the inefficiency of SLL-based optimality tests which are not able to bring meaningful complexity reduction if N is taken to infinity first. 4 Note that the order in which limits are taken in (13) is important. If we fix N and take SNR to infinity first, we can get where y 1 , y 2 are n-dimensional row vectors over GF (q). Let ξ be an arbitrary constant, M be an arbitrary integer, satisfying Let x 0 (D) be a source message whose corresponding codeword is y 0 (D). For any time index m, if the following inequality is satisfied for all d ∈ [m − 2Mν, m + 2Mν), and the following inequalities hold, We skip the proof of Theorem 1 since the result is implied by Theorem 3 presented in Section VI.
Note that the values of d min and d max only depend on the g q () function. Hence, as long as g q () and ν are given, the values of ξ and M can be fixed, e.g., ξ = Efficiency of the OTC proposed in Theorem 1 is characterized by the following lemma. Fix all other parameters and take SNR to infinity, we have The same conclusion holds if we first take N to infinity, then take SNR to infinity.
Consequently, (22) and (23) hold because n[d] 2 are i.i.d. χ 2 , whose mean, n SNR , and variance, 2n SNR 2 , converge to 0 as SNR goes to infinity. Lemma 3 implies, if there is a suboptimal decoder whose probability of symbol detection error (as opposed to sequence detection error) is low under high SNR, then NLL-based optimality tests can help transforming the suboptimal detector to an ML detector with only marginal increase in average decoding complexity. An example of such transformation is presented in the following section.

V. A Three-step ML Decoding Framework
The communication system given in Section II follows a discrete-time hidden Markov model [13], Following this idea, the three-step ML decoding framework is given as follows.
• Step 1: The decoder uses a suboptimal algorithm (denoted by Φ sub ) to obtain a quick guess of the codewordỹ(D) and its corresponding source messagex(D). Implementing the modified VA is quite straightforward. Hence its further description is skipped.
Comparing to the three-step decoding algorithm studied in [7], the key advantage of using an NLLbased optimality test is that the test can be applied to an individual source symbol rather than the whole source message.
Since the worst case complexity of the modified VA is bounded, (28) implies, for any δ > 0, Since all derivations hold if we first take N to infinity, we also have lim SNR→∞ lim N →∞ P {C mva ≤ 1 + δ} = 1.
By sharing computations among optimality tests, it is easy to see that the complexity of the second step of the ML decoder is equivalent, in order, to visiting one Markov state per time unit. Therefore, if Φ sub satisfies (25), as SNR → ∞, the complexity of the three-step ML decoder converges to the complexity of Φ sub , which can be significantly lower than the complexity of the VA. Moreover, the three steps of the ML decoder can be implemented in a parallelized manner in the sense that each step can process some of the source symbols without waiting for the previous step to completely finish its work. An example of such parallelized implementation can be found in [15, The Simple MLSD Algorithm].

VI. Maximum Likelihood Sequence Detection in A Class of Hidden Markov Systems
In this section, we generalize the results of Section IV to ML sequence detection (MLSD) in a class of first order discrete-time hidden Markov systems [13]. We demonstrate in Appendix D that the communication system presented in Section II satisfies the model and the key assumptions given in this section.
is a n-dimensional row vector with real-valued elements.
Denote the state transition probability of the hidden Markov system by Define the transition probability ratio bound p tr by We assume the Markov chain is ergodic and homogeneous. Therefore, there exists a positive integer ν, such that Denote the observation distribution function by Let the corresponding probability density function (or probability mass function) be f o (r|y 1 ).
We also make the following two key assumptions. Note that we used the same constant ν in (31) and in Assumption 2. This is valid because if (31) is satisfied for ν = ν 0 , then it is also satisfied for all ν ≥ ν 0 ; similar property applies to Assumption 2. Consequently, if Assumption 2 holds, a common integer ν satisfying both (31) and Assumption 2 can always be found.
Assumption 3: Assume the existence of two functions: L l (r, y 1 ) and L u (r, y 1 ), both are functions of the channel output symbol r and the processed state y 1 . Assume L l (r, y 1 ) and L u (r, y 1 ) have the following two properties.
First, the following inequalities hold for all r and y 1 .
L l (r, y 1 ) ≤ min y 2 ,y 2 =y 1 [− log(f o (r|y 2 )) + log(f o (r|y 1 ))] L u (r, y 1 ) ≥ max Second, the complexity of evaluating L l (r, y 1 ) and L u (r, y 1 ) is low in the sense that they do not require the search of any processed state other than y 1 .
Note that validity of the results presented in this section does not depend on the second property imposed in Assumption 3. However, we still include the property in the assumption since the key motivation of posing Assumption 3 is to use the two functions L l (r, y 1 ) and L u (r, y 1 ) as tools to avoid exhaustive Markov state search and hence to reduce the complexity of ML decoding. Also note that the right hand side of the second inequality in (33) is not a function of y 1 . However, the upper bound on the left hand side is a function of a processed state y 1 since one often needs a "reference state" in order to upper bound the right hand side of (33). Further explanation is given in Appendix D.
Given the observation sequence r(D), the negative SLL of a state sequence u(D) is obtained by The objective of MLSD is to find the ML sequence that minimizes the negative SLL, S u (u(D)).
The following theorem gives a class of NLL-based optimality tests. and We assume The following lemma characterizes the efficiency of the OTC proposed in Theorem 3.
If we fix all other parameters except the SNR and the sequence length N, we have We skip the proof of Lemma 4 since it is quite straightforward.
Note that in Lemma 4, when we take N and SNR to infinity, M can be fixed at a constant. This indicates that, when testing the optimality of a Markov state at a given time index, the NLL-based optimality test only uses observation symbols in a fixed-sized time neighborhood. Based on Theorem 3 and Lemma 3, a three-step ML sequence detector similar to the one presented in Section V can be developed to transform a suboptimal sequence detector to a low complexity ML sequence detector.
The detailed discussion is skipped since it does not essentially differ from the one presented in Section V.

VII. Further Discussions
In a practical system, suboptimal decoders such as the belief-propagation-based iterative decoders More importantly, such conclusion holds irrespective of the codeword length.
Although the efficiency of SLL-based optimality tests does not depend on the codeword length, NLL-based optimality tests are inefficient only when the codeword length is large. Lemma 1 and Theorem 2 suggest that complexity reduction brought by NLL-based optimality tests can be superior to SLL-based optimality tests even for moderate SNR if the codeword length is large enough.

A. The Path Covering Criterion
Assume the discrete-time hidden Markov model given in Section VI 5 . Given the observation sequence r(D). Letũ(D) and u(D) be two Markov state sequences whose corresponding processed state sequences areỹ(D) and y(D), respectively. If we can find two time indices d 1 < d 2 , such that we say u(D) "covers"ũ(D).
Path Covering Criterion: Markov state sequenceũ(D) cannot be the ML sequence if we can find another state sequence u(D) that coversũ(D).
The proof of the PCC is skipped since it is quite well known [8].
We say u(D) is a "cover" path with respect to Markov states In other words, D d = [0, m]. The negative SLL lower bound is given by which satisfies Assumption 1 with ǫ = 1.
In [7], several SLL-based OTCs were presented for decoding block codes. The decoder obtains a first guess y(D) of the codeword. A negative SLL lower bound S L y ≤ S y (ỹ(D) = y(D)) is then developed for the codeword set {ỹ(D) = y(D)}, which corresponds to the case of D d being an empty set in the context of Section III. y(D) is optimal if the optimality test S L y > S y (y(D)) gives a positive answer [7].
The lower bounds S L y presented in [7, Section III] satisfy the following inequality, Since the coding constraint is ν, we can always find a codewordỹ(D) = y(D) withỹ(D) differing from y(D) at no more than ν codeword symbols. This implies that the right hand side of (46) can be upper bounded by a constant, denoted by U 1 , which is not a function of N.
Consequently, given SNR > 0 and 0 < ǫ < 1, there exists a constant N 0 such that Assumption 1 is satisfied for N > N 0 .

C. Proof of Lemma
The definition of D x d also implies that the decoder needs to obtain a lower bound S L x (x(D x 0 ∪ D x d )) of the negative SLLs of the messages in {x(D should only be a function of the partial messagex(D x 0 ∪ D x d ), but should not depend on any source message symbol whose time index is outside D x 0 ∪D x d . However, since the corresponding D e (defined in (11)) of {x 0 (D x 0 ∪D x d )} satisfies |D e | ≤ 2ν, according to Lemma 1, the probability of disproving the optimality To make the argument explicit, the fact that the decoder visits all Markov states According to Lemma 1, for any positive constant δ > 0, if we fix all other parameters and take N to Combining (48) and (49), we get Since (50) holds for any fixed SNR, it still holds if we take SNR to infinity after taking N to infinity, i.e.,

D. The Hidden Markov Model and Its Key Assumptions
In this section, we show the communication system presented in Section II satisfies the discrete-time hidden Markov model and the key assumptions given in Section VI.
Note that evaluating L l (r, y 1 ) and L u (r, y 1 ) does not involve visiting any processed state other than y 1 .
Theorem 3 holds if we can prove that anyũ(D) satisfying (60) cannot be the ML state sequence.
Let k denote a positive integer. Define two integers K l and K r as follows.
We consider respectively the following four cases based on the values of K l and K r . In all the four cases, we showũ(D) cannot be the ML sequence.
Sinceũ[m+ν −1+kν] = u[m+ν −1+kν] for all −K 1 < k < K r , according to Assumption 2,ỹ(D) and y(D) differ at no less than K l +Kr 2 time indices in the time interval [m + ν − K l ν, m + ν + K r ν), where ⌊x⌋ denotes the maximum integer no larger than x. According to (33) Consequently, we get According to the PCC presented in Appendix A, (63) implies that u(D) "covers" 7ũ (D). Hencẽ u(D) cannot be the ML sequence.
In this case, we will construct a Markov sequence u c (D) and show that u c (D) coversũ(D). 7 See definition in Appendix A. (67) implies that u c (D) coversũ(D). Hence according to the PCC,ũ(D) cannot be the ML sequence.
Similar to Case 2, we will construct a Markov sequence u c (D) and show that u c (D) coversũ(D).
u c (D) is constructed as follows.  According to (33)  Overall, we showed thatũ(D) cannot be the ML sequence irrespective of the values of K l and K r .