Tail-biting trellises are defined on a circular time axis and can have a smaller number of states than equivalent conventional trellises. Existing circular Viterbi algorithms (CVAs) on the tail-biting trellis are non-convergent and sub-optimal. In this study, we show that the net path metric of each tail-biting path is lower-bounded during the decoding process of the CVA. This property can be applied to remove unnecessary iterations of the CVA and results in a convergent maximum likelihood (ML) decoder. Simulation results show that the proposed algorithm exhibits higher decoding efficiency compared with other existing ML decoders.

For linear block codes, conventional trellis and tail-biting trellis representations have gained a great deal of attention in the past decades[1–3]. Trellis representations not only reveal the code structure, but also lead to efficient trellis-based decoding algorithms[4–8]. For the same linear block codes, the number of states in its tail-biting trellis can be as low as the square root of the number of states in its minimal conventional trellis[1,8], e.g., for the (24, 12) extended Golay code, the maximum number of states in its conventional trellis is 512[8], while the maximum number of states in its time-varying tail-biting trellis is only 16[1].

In addition, the tail-biting technique has been widely used in convolutional encoders to eliminate the rate loss caused by the known tail bits. For example, the Worldwide Interoperability for Microwave Access (WiMAX)[9] and Long Term Evolution[10] standards both adopted tail-biting convolutional codes in the control channel or broadcasting channel. Consequently, a maximum likelihood (ML) decoder with high decoding efficiency on tail-biting trellises is important and desirable for studying tail-biting codes.

Both the Viterbi algorithm and bidirectional efficient algorithm for searching code trees (BEAST) can achieve ML decoding on conventional trellises[8]. In the case of a tail-biting trellis, due to the lack ofa priori knowledge about the starting state, the Viterbi and BEAST decoder have to perform an exhaustive search on tail-biting trellises to find the ML codeword. BEAST can be more efficient if applied to the conventional trellis obtained by reducing the tail-biting code generator matrix to the minimum span form[8].

Another kind of decoder, the two-phase ML decoder, has been proposed to reduce the decoding complexity for tail-biting trellises[5,6]. This kind of algorithm performs Viterbi searches on tail-biting trellises in the first phase and records the accumulated path metric of each path at every section for the second phase. In the second phase, heuristic searches are performing based on the result obtained from the first phase. Since the two-phase decoder is based on two distinct algorithms, this makes it difficult for practical application.

The circular Viterbi algorithm (CVA)-based decoder greatly reduces the implementation complexity of a decoder for tail-biting trellises and provides near-optimal block error rate performance. However, the decoding process of the CVA is non-convergent and sub-optimal[4,7]. In this paper, we introduce a CVA-based ML decoder for tail-biting trellises. In this algorithm, the lower bound of the net path metric of each tail-biting path can be obtained to exclude impossible starting state candidates, which leads to convergence of the CVA. In addition, the net path metric of survivor paths can be used to terminate redundant searches without performing a full Viterbi iteration.

The following parts of this article are organized as follows: In Section 2, a detailed description of the algorithm is presented. The performance of the proposed algorithm is demonstrated by simulations in Section 3. Section 4 concludes this paper.

2.1 Variable definition

An example of a tail-biting trellis is shown in Figure1, which has eight sections with four states at each section. For a tail-biting trellis withL sections, denote byS_l the set of states at locationl, where 0≤l≤L. From the definition of tail-biting trellises, we haveS₀≡S_L. Any path that starts from and terminates at the same state forms a tail-biting path. All tail-biting paths that start from the same state construct a sub-tail-biting trellis of this state. In Figure1, the branches of thick solid lines form a tail-biting path of state ‘01,’ and all solid lines compose the sub-tail-biting trellis of state ‘01’.

The tail-biting trellis of the (8, 4) convolutional code with octal generator polynomials of {7, 5}.

Full size image

A conventional CVA-based decoder performs Viterbi iterations around the tail-biting trellis to find the optimal tail-biting path. This algorithm takes advantage of the circular property of tail-biting trellises and employs the path metrics accumulated in the ending states of the trellis to initialize the path metrics in the starting states for a new iteration until a predefined termination condition is fulfilled. In the following parts, we elaborate the decoding process of CVA on tail-biting convolutional codes. The decoding process for general tail-biting trellises can be similarly obtained.

For tail-biting convolutional codes of rateb/c, the length of information bits isbL and the length of the corresponding codeword iscL. Binary code bits$v_l^{\left(j\right)}\in \{0,1\}$ are mapped to$x_l^{\left(j\right)}=\left(1-2v_l^{\left(j\right)}\right)\sqrt{E_s}$ with binary phase-shift keying (BPSK) modulation, where 0≤j≤c−1 and 0≤l≤L−1. Without loss of generality, signal energyE_s is normalized to 1. After passing through an additive white Gaussian noise (AWGN) channel with a double-sided noise power spectrum density ofN₀/2, the corresponding received symbols are$r_l^{\left(j\right)}$. The log-likelihood ratio of$r_l^{\left(j\right)}$ is given by$\Lambda \left(r_l^{\left(j\right)}\right)=4r_l^{\left(j\right)}/N_0$, where forl≥L,$x_l^{\left(j\right)}=x_{{\left(l\right)}_L}^{\left(j\right)}$,$\Lambda \left(r_l^{\left(j\right)}\right)=\Lambda \left(r_{{\left(l\right)}_L}^{\left(j\right)}\right)$, and (l)_L =l modL.

During the decoding process of the CVA, the accumulated path metric of the survivor path entering states at locationl in thei th iteration is

The weighted Hamming distance between$\Lambda \left(r_l^{\left(j\right)}\right)$ and$x_l^{\left(j\right)}$ can be defined as in[8]:

where$\text{sgn}\left(\Lambda \left(r_l^{\left(j\right)}\right)\right)$ denotes the sign of$\Lambda \left(r_l^{\left(j\right)}\right)$. Based on (1) and (2), the ML decoding on the tail-biting trellis is equivalent to solving the following equation:

The term$\left|\Lambda \left(r_k^{\left(j\right)}\right)\right|$ can be ignored in the third line of (3) since it is independent of specific codewordsx and consequently is a constant for all paths on the tail-biting trellis.

Denote byPⁱ(βⁱ(s),s) the survivor path that connects stateβⁱ(s) ofS₀ with states ofS_l in thei th iteration. The corresponding net path metric ofPⁱ(βⁱ(s),s) can be derived from (1) and (3):

Since the initial path metrics$M_0^{i+1}\left(s^{\prime }\right)$ are different from$M_0^i\left(s^{\prime }\right)$ for each states^′∈S₀, different survivor paths can be obtained in each iteration. Denote by${\overline{P}}^i$ the ML path obtained in thei th iteration, where the ML path obtained from the first iteration has the least net path metric among all possible survivor paths[4]. Similarly, the ML tail-biting path obtained in thei th iteration is denoted by${\tilde{P}}^i$, which has the net path metric of${\tilde{M}}^i$. Among the set of tail-biting paths$\left\{\right({\tilde{P}}^i(s,s)$,${\tilde{M}}^i(s,s))$∣∀s∈S₀,i≥1}, the optimal tail-biting path and its net path metric are denoted by${\tilde{P}}^{\mathrm{O}}$ and${\tilde{M}}^{\mathrm{O}}$, respectively.

2.2 Lower bounds of the net path metrics

A conventional CVA-based decoder is non-convergent, and consequently, it cannot guarantee that the tail-biting path obtained is optimal when the decoding process is terminated[4,7]. In order to design a convergent ML decoder on tail-biting trellises, further information needs to be obtained from the decoding process of CVA. Based on the characteristics of CVA, we can derive a lower bound of the net path metric of each tail-biting path. This observation is summarized in Lemma 1

Lemma 1.

Let$\tilde{P}(s,s)$ denote the ML tail-biting path on the sub-tail-biting trellis of states, and the corresponding net path metric is$\tilde{M}(s,s)$, wheres∈S₀. DefineB(s) as

then we have$B\left(s\right)\le \tilde{M}(s,s)$, i.e.,B(s) is the lower bound of the metrics of all paths on the sub-tail-biting trellis of states.

Proof

The tail-biting trellis defined on a circular time axis can be split at sectionl=0 and duplicated on the time axis head-tail. Conventional CVA then becomes a general Viterbi decoder composed of several lengthL decoding sections, where the Viterbi algorithm searches on the duplicated trellis by recording and repeating the received symbols. Consequently, combining (1) and (3), we find that the survivor pathPⁱ(βⁱ(s),s) has the minimum accumulated path metric$M_l^i\left(s\right)$ among all possible pathsPⁱ(s^∗,s), wheres^∗,βⁱ(s)∈S₀,s∈S_l, and 0≤l≤L−1. Consequently, we have

Since (6) holds for 0≤l≤L−1, we know that for anys∈S_L, (6) also holds. Then for the ML tail-biting path,$\tilde{P}(s,s)$, on the sub-tail-biting trellis of states, from (6), we have

Since$B\left(s\right)=\underset{i\ge 1}{\text{max}}\left\{M_L^i\right(s)-M_0^i(s\left)\right\}$, then combining (7), we have

Since$\tilde{P}(s,s)$ is the ML tail-biting path on the sub-tail-biting trellis of states, from (3) and (8), we come to the conclusion thatB(s) is a lower bound of the metrics of all paths on the sub-tail-biting trellis of states. □

The lower boundB(s) defined in Lemma 1 is updated as iterations continue, and a more precise estimation ofB(s) can be obtained if more iterations are performed on the tail-biting trellis. According to (8), the maximal value ofB(s) is$\tilde{M}(s,s)$.

Based on Lemma 1, we can reduce the decoding complexity of CVA on the tail-biting trellis by removing redundant computations and iterations during the decoding process and control the convergence of CVA. The improvements of the proposed decoder can be summarized into the following two aspects.

Firstly, during the decoding process, if the net path metricM neti(βⁱ(s),s) of survivor pathPⁱ(βⁱ(s),s) is not less than${\tilde{M}}^{\mathrm{O}}$, where${\tilde{M}}^{\mathrm{O}}$ is the optimal tail-biting path obtained in the firsti−1 iterations ands∈S_l, all searches that follow states can be terminated (refer to Figure2). In this case, the net path metric of any survivor path that starts from stateβⁱ(s) and passes through states is not less than${\tilde{M}}^{\mathrm{O}}$.

Decoding process of the B-CVA ML decoder. For the first iteration, four survivor paths corresponding to each of the terminal states are shown on the tail-biting trellis in (a), where the tail-biting trellis has been split at locationl=0. For the second iteration, the decoding process is illustrated from (b) to (e). Searches following the circles with left incident branch are terminated according to step 2.1. The decoding process is terminated atl=4 since there are no survivor paths with net path metric less than${\tilde{M}}^{\mathrm{O}}$.

Full size image

Secondly, denote by${\mathbf{S}}_{\mathrm{C}}^i$ the set of survivor starting state candidates in thei th iteration of the CVA, i.e.,

where${\mathbf{S}}_{\mathrm{C}}^1={\mathbf{S}}_0$.

After thei th iteration, (${\tilde{P}}^{\mathrm{O}}$,${\tilde{M}}^{\mathrm{O}}$) andB(s) will be updated with (${\tilde{P}}^i$,${\tilde{M}}^i$) andBⁱ(s), where (${\tilde{P}}^i$,${\tilde{M}}^i$) is the best tail-biting path and its metric obtained in thei th iteration, andBⁱ(s) is the lower bound of the metrics of all paths on the sub-tail-biting trellis of states obtained in thei th iteration. For$\forall s\in {\mathbf{S}}_{\mathrm{C}}^i$, if$B\left(s\right)\ge {\tilde{M}}^{\mathrm{O}}$, then from Lemma 1, we have$\tilde{M}(s,s)\ge {\tilde{M}}^{\mathrm{O}}$. This indicates that the ML tail-biting path on the sub-tail-biting trellis of states is not better than${\tilde{P}}^{\mathrm{O}}$. States can be excluded from the set${\mathbf{S}}_{\mathrm{C}}^{i+1}$. As iterations continue, the search space on the tail-biting trellis shrinks and the decoder will converge to the global optimal solution eventually.

2.3 CVA-based ML decoder on tail-biting trellis

We summarize the above decoding process as follows: In the algorithm description, the operator ‘ ←’ denotes value assignment from the right-hand side to the left-hand side, and the operator ‘=’ denotes logic comparison between two operands.

From the description above, we find that the decoding process can only be terminated when${\mathbf{S}}_{\mathrm{C}}^{i+1}=\varnothing$ in step 2.4. The number of entries in${\mathbf{S}}_{\mathrm{C}}^1$ is finite, and as iterations continue, the size of${\mathbf{S}}_{\mathrm{C}}^i$ will reduce to zero.

Firstly, states with bound$B\left(s\right)>{\tilde{M}}^{\mathrm{O}}$ is deleted from${\mathbf{S}}_{\mathrm{C}}^i$ in step 2.3 since the ML tail-biting path on the sub-tail biting trellis of states is not better than${\tilde{P}}^{\mathrm{O}}$.

Secondly, after the (i+1)th iteration, if no state has been deleted from${\mathbf{S}}_{\mathrm{C}}^{i+1}$, i.e.,$\forall s\in {\mathbf{S}}_{\mathrm{C}}^{i+1}$,$B\left(s\right)<{\tilde{M}}^{\mathrm{O}}$, then equation${\mathbf{S}}_{\mathrm{C}}^{i+1}={\mathbf{S}}_{\mathrm{C}}^{i+2}$ holds and the Viterbi algorithm will be performed on the sub-tail-biting trellis of states^‡ in step 2.4, where$s^{‡}\in {\mathbf{S}}_{\mathrm{C}}^{i+1}$. If$\tilde{M}(s^{‡},s^{‡})<{\tilde{M}}^{\mathrm{O}}$,${\tilde{P}}^{\mathrm{O}}$ will be updated with$\tilde{P}(s^{‡},s^{‡})$; else, if$\tilde{M}(s^{‡},s^{‡})\ge {\tilde{M}}^{\mathrm{O}}$, this indicates that$\tilde{P}(s^{‡},s^{‡})$ is not better than${\tilde{P}}^{\mathrm{O}}$. Then states^‡ can be deleted from${\mathbf{S}}_{\mathrm{C}}^{i+1}$ since the ML tail-biting path on its sub-tail-biting trellis has been found.

Thirdly, after thei th iteration, if$\tilde{M}(s^{\prime },s^{\prime })<{\tilde{M}}^{\mathrm{O}}$,${\tilde{P}}^{\mathrm{O}}$ will be updated with$\tilde{P}(s^{\prime },s^{\prime })$, where$s^{\prime }\in {\mathbf{S}}_{\mathrm{C}}^i$. Since$B\left(s^{\prime }\right)=\underset{i\ge 1}{\text{max}}\left\{M_L^i\right(s^{\prime })-M_0^i(s^{\prime }\left)\right\}\le \tilde{M}(s^{\prime },s^{\prime })$,B(s^′) will be updated with$\tilde{M}(s^{\prime },s^{\prime })$ in step 2.3, and then states^′ will be deleted from${\mathbf{S}}_{\mathrm{C}}^i$ since the equality in$B\left(s\right)\ge {\tilde{M}}^{\mathrm{O}}$ holds.

All survivor starting state candidates in${\mathbf{S}}_{\mathrm{C}}^1$ will be deleted eventually, and${\mathbf{S}}_{\mathrm{C}}^i$ will be empty in a finite number of iterations. When${\mathbf{S}}_{\mathrm{C}}^i$ is empty, the decoder converges to the global optimal solution that has been recorded in${\tilde{P}}^{\mathrm{O}}$. In summary, the algorithm presented above is a convergent ML decoder on tail-biting trellises. We call this a bounded CVA (B-CVA) ML decoder.

The following example is used to explain the decoding process of the B-CVA.

Example 1

The tail-biting convolutional code that is represented by the tail-biting trellis in Figure1 is selected in this example. The information sequence is {01011100}, and the corresponding codeword is {(00), (11), (10), (00), (01), (10), (01), (11)}. After passing through the AWGN channel where the signal-to-noise ratio (SNR) isE_b/N₀=0 dB, the received sequence (for one realization) is {(1.144, 0.458), (−0.986, −1.234), (0.291, 1.364), (0.472, 0.350), (1.578, −1.594), (0.050, −0.399), (2.260, 0.359), (−1.501, 0.234)}. For convenience, states {00, 01, 10, 11} are represented by {0, 1, 2, 3}. For the first iteration, set${\mathbf{S}}_{\mathrm{C}}^1=\{0,1,2,3\}$ and the four survivor paths are shown on Figure2a. We find that there is a tail-biting pathP¹(0,0) with net path metric$M_{\text{net}}^1(0,0)=1.333$. Then (${\tilde{P}}^{\mathrm{O}}$,${\tilde{M}}^{\mathrm{O}}$) are updated with (P¹(0,0),$M_{\text{net}}^1(0,0)$). The bounds of each terminal state are updated toB(0)=1.333,B(1)=0.291,B(2)=1.868, andB(3)=2.026. Since only$B\left(1\right)<{\tilde{M}}^{\mathrm{O}}$, according to step 2.3 of the B-CVA,${\mathbf{S}}_{\mathrm{C}}^2=\left\{1\right\}$. The decoding process of the second iteration is illustrated in Figure2b, c, d, e. We find that with the control on the decoding process of the CVA, the second iteration terminates at sectionl=4; and at each section, searches after states^′ that has$M_{\text{net}}^2(1,s^{\prime })\ge {\tilde{M}}^{\mathrm{O}}$ are terminated. The states^′ corresponds to the circle with left incident branch on the trellis in Figure2b, c, d, e. The decoding result is the codeword associated with the tail-biting path${\tilde{P}}^{\mathrm{O}}$. In the first iteration, there are 64 real additions and 32 logical comparisons; and in the second iteration, the numbers of real additions and logical comparisons corresponding to each step are {(4, 2), (4, 2), (8, 4), (6, 4)}. In summary, the decoding complexity of B-CVA is denoted by 86 real additions and 44 logical comparisons. As is shown in Appendix 1: decoding process of the two-phase ML decoder, the decoding complexity of the two-phase decoder is denoted by 100 real additions and 101 logical comparisons.

In order to show the decoding efficiency, we compare the proposed B-CVA ML decoder with other widely cited tail-biting ML decoders in three aspects: the number of real additions, the number of logical comparisons, and average memory space consumption during the decoding process. The codewords are modulated to BPSK symbols and then passed through an AWGN channel. The results shown in the tables and figures are obtained by observing at least 100 block error events.

The conventional BEAST ML decoder should perform decoding on each sub-tail-biting trellis independently and consecutively to find the ML tail-biting path[8]. To improve its efficiency, we use the upper-bounding technique on the thresholds used by BEAST. During the consecutive decoding process, the metric of the optimal tail-biting path obtained on the firsti sub-tail-biting trellises are used to upper-bound the thresholds that will be used for decoding the remaining |S₀|−i sub-tail-biting trellises, where |S₀| denotes the size of setS₀. With this upper-bounding technique, redundant searches can be terminated timely or reduced through the whole decoding process. For convenience, we call the BEAST decoder with this upper-bounding technique an advanced-BEAST ML decoder, which should be more efficient than the original BEAST decoder in[8]. Results presented in Appendix 4 are used to demonstrate this point.

In the first example, different decoders were applied for decoding the tail-biting convolutional codes (64, 32) with octal generator polynomials {345, 237}, which can be represented by a 128-state tail-biting trellis[7]. For the demonstration of the block error rate (BLER) performance of the B-CVA, we choose the most cited sub-optimal decoder proposed in[7] for comparison. This decoder is called the wrap-around Viterbi algorithm (WAVA). Because the WAVA is non-convergent, the maximal allowed number of iterations is set as 20 during the decoding process. Table1 shows the BLER performance of different decoders. We find that of the sub-optimal decoders, WAVA has performance that is close to the optimal results.

Figure3 shows the average memory space consumption of the different ML decoders during the decoding process. We find that the advanced BEAST decoder and the B-CVA decoder require almost constant memory space from the low- to high-SNR regions. However, we find that the WAVA decoder requires less memory space than the B-CVA. This is due to the fact that WAVA has no need of space for storingB(s) of every state inS₀. The memory space required by the two-phase decoder is about 2∼12 times more than that required by the B-CVA or BEAST decoders. This is due to the fact that the two-phase decoder has to store path metrics of all survivor paths obtained in the first phase and has to maintain the open stack and close table during the second phase.

Average memory space required for decoding the (64, 32) tail-biting convolutional codes. Average memory space consumption by the WAVA and different ML decoders: advanced BEAST ML decoder, two-phase ML decoder and B-CVA ML decoder, for decoding the (64, 32) tail-biting convolutional codes over the AWGN channel.

Full size image

Figure4 shows that the two-phase ML decoder which is based on depth-first searches is a little better than the B-CVA ML decoder in the number of real additions. The BEAST ML decoder which performs exhaustive searches on the tail-biting trellis shows the highest decoding complexity. Figure5 shows that a larger number of logical comparisons should be performed by the two-phase decoder than that performed by the B-CVA decoder. This is due to the fact that many logical comparisons need to be performed to sort the open stack and to retrieve the close table in the low-SNR region. In fact, the length of the close table grows linearly as the searches continue. Figures4 and5 also show that the advanced BEAST decoder, which has to be performed on each sub-tail-biting trellis, exhibits high decoding complexity from the low- to high-SNR regions. Meanwhile, we find that the WAVA exhibits high decoding complexity from the low- to medium-SNR regions; this is caused by circular traps existing in the CVA decoding process[4].

Average number of real additions required for decoding the (64, 32) tail-biting convolutional codes. Average number of real additions that were performed during the decoding process of the WAVA and different ML decoders: advanced BEAST ML decoder, two-phase ML decoder and B-CVA ML decoder, for decoding the (64, 32) tail-biting convolutional codes over the AWGN channel.

Full size image

Average number of logical comparisons required for decoding the (64, 32) tail-biting convolutional codes. Average number of logical comparisons that were performed during the decoding process of the WAVA and different ML decoders: advanced BEAST ML decoder, two-phase ML decoder, and B-CVA ML decoder, for decoding the (64, 32) tail-biting convolutional codes over the AWGN channel.

Full size image

The second example adopts the tail-biting convolutional codes that have been used in WiMAX. The corresponding generator polynomials are {133, 171} in octal form[9]. The length of the information sequence is 40 bits, and the corresponding code is a long tail-biting convolutional code[7], which is denoted as an (80, 40) tail-biting convolutional code. The BLER of the WAVA and ML decoders are presented in Table2, where the ML decoder in Table1 refers to any kind of ML decoders mentioned in this paper: the advanced BEAST ML decoder, two-phase ML decoder, or BCVA decoder, since all of them exhibit exactly the same block error rate performance. We find that in the case of long tail-biting codes, the BLER performance of WAVA is close to that of ML decoders.

From Figures6,7 and8, we come to almost the same conclusions as that in the first example. In Figure6, the memory space required by the advanced BEAST decoder decreases slowly as system SNR grows. Figure8 shows that, in the low-SNR region, many comparisons were performed to maintain the open stack and close table in the second phase of the two-phase ML decoder. In summary, the B-CVA decoder is an efficient ML decoder on tail-biting trellises both in memory space saving and decoding complexity reduction.

Average memory space required for decoding the (80, 40) tail-biting convolutional code. Average memory space consumption by the WAVA and different ML decoders: advanced BEAST ML decoder, two-phase ML decoder, and B-CVA ML decoder, for decoding the (80, 40) tail-biting convolutional codes over the AWGN channel.

Full size image

Average number of real additions required for decoding the (80, 40) tail-biting convolutional code. Average number of real additions that were performed during the decoding process of the WAVA and different ML decoders: advanced BEAST ML decoder, two-phase ML decoder and B-CVA ML decoder, for decoding the (80, 40) tail-biting convolutional codes over the AWGN channel.

Full size image

Average number of logical comparisons required for decoding the (80, 40) tail-biting convolutional code. Average number of logical comparisons that were performed during the decoding process of the WAVA and different ML decoders: advanced BEAST ML decoder, two-phase ML decoder and B-CVA ML decoder, for decoding the (80, 40) tail-biting convolutional codes over the AWGN channel.

Full size image

We propose a convergent CVA-based ML decoder for tail-biting trellises. The proposed algorithm takes advantage of the lower bound of the net path metric of the tail-biting path to control the decoding process of CVA. Simulation results show that, on tail-biting trellises, the B-CVA decoder exhibits high decoding efficiency while requiring relatively small memory space during the decoding process. These advantages make it attractive to practical applications.

Appendix 1: decoding process of the two-phase ML decoder

In Example 1, the decoding process of the two-phase ML decoder can be described as follows[6]: (1) During the first phase, the decoder stores the path metric$M_l^1\left(s\right)$ of∀s∈S_l and 0≤l≤L; the decoding complexity of the first phase is the same as that of the B-CVA, which contains 64 real additions and 32 logical comparisons; (2) in the second phase, heuristic searches are performed on the sub-tail-biting trellis of state 01; in each step, the heuristic search is performed following the top path in the open stack. There are 3 real additions and 4 logical comparisons for updating the values of theg-function,h-function, andf-function. The two successors will be saved in an open stack if the values of theirf-functions are less than${\tilde{M}}^1$. Meanwhile, the starting state, terminal state, and current sectionl of the top path will be saved in the close table. Then, the top path of the open stack will be compared with each entry of the close table in three aspects: starting state, terminal state, and current location. With six heuristic searching steps, the decoding process is stopped. The decoding complexity in summary is denoted by 100 real additions and 105 logical comparisons. We have ignored the complexity of sorting the open stack according to ascending order of theirf-function values. The open stack and the corresponding close table obtained in each step are shown in Table3, where Open stack = {(starting state, current state,l-section,f-function)}, Close table = {(starting state, current state,l-section)}, and Complexity = {(the number of real additions, the number of logical comparisons)}.

Appendix 2: improvements of the BEAST ML decoder with upper-bounding technique

To show the decoding efficiency improvement of the advanced BEAST decoder, we use it and the original BEAST decoder[8] to decode a tail-biting convolutional code used in WiMAX. The length of the information sequence is 40 bits. The average numbers of real additions and logical comparisons are presented in Table4. We find that the upper-bounding technique can cut the decoding complexity of the BEAST decoder by 1/2∼2/3.

This work was supported in part by the Hundred Talents Program of the Chinese Academy of Sciences, the Shanghai Pujiang Talent Program No. 11PJ1408700, the National Science and Technology Major Project No. 2011ZX03003-003-04, the International Science and Technology Cooperation Program of Shanghai Municipality No. 11220705400, and the Science and Technology Commission Foundation of Shanghai No. 12511503400.

Authors and Affiliations

1. Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai, 200050, China

   Xiaotao Wang, Hua Qian & Kai Kang

2. Graduate University of Chinese Academy of Sciences, Beijing, 100049, China

   Xiaotao Wang

3. Shanghai Research Center for Wireless Communications, Shanghai, 200335, China

   Hua Qian & Kai Kang

4. Shanghai Internet of Things Co., Ltd., Shanghai, 201899, China

   Hua Qian & Kai Kang

5. Electrical and Computer Engineering Department, University of Michigan-Dearborn, Dearborn, MI, 48128-2406, USA

   Weidong Xiang

Corresponding author

Correspondence toHua Qian.

Competing interests

The authors declare that they have no competing interests.

Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0 ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Reprints and permissions