Improved encoding structure and decoding algorithms for spinal codes

HUANG Wensha and WANG Lina,2,*

1.School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China;2.Shunde Graduate School,University of Science and Technology Beijing,Beijing 100083,China

Abstract: To improve the error correction performance,an innovative encoding structure with tail-biting for spinal codes is designed.Furthermore,an adaptive forward stack decoding(A-FSD) algorithm with lower complexity for spinal codes is proposed.In the A-FSD algorithm,a flexible threshold parameter is set by a variable channel state to narrow the scale of nodes accessed.On this basis,a new decoding method of AFSD with early termination (AFSD-ET) is further proposed.The AFSD-ET decoder not only has the ability of dynamically modifying the number of stored nodes,but also adopts the early termination criterion to curtail complexity.The complexity and related parameters are verified through a series of simulations.The simulation results show that the proposed spinal codes with tail-biting and the AFSD-ET decoding algorithms can reduce the complexity and improve the decoding rate without sacrificing correct decoding performance.

Keywords: spinal code,tail-biting encoding,lower decoding complexity,early termination strategy.

1.Introduction

Spinal codes,as a new kind of rateless codes,were proposed by Perry et al.in 2012 [1].Different from the traditional channel encoding algorithms,the key idea of spinal codes is that a similar structure of convolutional code[2,3] and an irreversible hash function to generate pseudorandom sequences are adopted.Compared with the fixedrate codes such as turbo codes [4,5] and low-density parity check (LDPC) codes [6,7],rateless codes can adapt to the dynamic channel and generate infinite modulation symbols to send continuously without feedback [6].As shown in [8,9],spinal codes have been proved that they can achieve the capacities of both additive white Gaussian noise (AWGN) channel and the binary symmetric channel (BSC) with short message length and pseudorandom like codewords.

Perry mentioned that the error bits of spinal codes are mainly concentrated in several symbols at the end of information [1].Yu et al.showed that spinal codes have the potential unequal error protection (UEP) property [10].To solve the high decoding error,a novel encoding structure was proposed by adding tail bits to the head of source message.The protection of tail bits was strengthened,thereby improving the bit-error-rate (BER).The effect of tail-biting on the original spinal codes is similar to adding tail symbols of original sequences,which can improve the overall error-control performance.The difference is that the former is added to the head,but the latter is added to the tail.The conclusion showed that the addition of extra tail symbols gains the higher reliability.

Based on the maximum likelihood (ML) decoding,the bubble decoding algorithm effectively reduces the decoding complexity [11,12].Yang et al.[13] proposed a lower complexity algorithm named forward stack decoding(FSD) algorithm by dividing the decoding tree into several layers.When the channel state fluctuates greatly,the FSD algorithm searches more invalid nodes,which is not ideal for reducing the complexity.Therefore,an adaptive FSD (A-FSD) algorithm is proposed in this paper.According to different channel states,a specific threshold which is inversely proportional to the signal to noise ratio (SNR) is designed to control the number of storage nodes.The A-FSD algorithm can dynamically adjust the number of node search through the real-time channel state,so as to adaptively optimize the decoding complexity.

According to different search criteria,tree search strategies can be divided into depth-first tree search and breadth-first tree search [14,15].Different from the breadth-first tree search,the depth-first tree search starts from a certain node and accesses its first subnode.If the subnode meets certain conditions,it goes to the next layer and searches the first node of this subnode,and then it searches down to the leaf node according to the search criteria.The depth-first search algorithm has the feature of implicit early termination (ET).The ET criterion[16,17] can be described in a decoding tree as searching for a node along a path,terminating the search for a node whose path metric is greater than a specified metric value,returning to the beginning and continuing the search along the next path.For spinal codes,there are many improved algorithms in encoding and decoding.Hu et al.designed a block dynamic decoding (BDD) algorithm to facilitate reliable data transmission [18].Xu et al.adapted a sliding feedback decoding (SFD) algorithm,which uses a sliding window to locate a layer for local decoding [19].Chen et al.proposed a multiplicative repetition-based scheme instead of the hash function and designed both frozen-aided and cyclic redundancy check-aided decoding algorithms to improve the spectral efficiency [20].However,the speed of reaching the end of the decoding tree is slow and the complexity is still high.It can be noted that most of the algorithms are carried out from the breadth-first tree search.Inspired by depth-first search and ET strategy,an AFSD-ET algorithm is designed to further optimize the decoding computation based on the A-FSD scheme.The new algorithm divides the tree into two groups.Meanwhile,in the process of node detection,the number of storage nodes is determined by setting a threshold level,and the ET criterion is adopted to stop the decoding process immediately.It can flexibly adjust the path of decoding search to reduce the number of nodes to be calculated.Through theoretical analysis and simulations,the AFSD-ET algorithm is capable of decreasing the complexity and accelerating the efficiency of searching the correct path.

The rest of this paper is organized as follows.Section 2 describes the tail-biting encoding structure.In Section 3,based on the FSD decoding method,the lower decoding complexity schemes including A-FSD and AFSD-ET are presented.And then the complexity of four decoding algorithms is discussed.The performance of the proposed algorithms is evaluated through a series of simulations in Section 4.And the conclusions are drawn in Section 5.

2.Tail-biting spinal codes

2.1 Tail-biting encoding structure

The encoding process is improved on the original structure as follows:

(i) Coding block segmentation

Divide then-bits messageMintod=n/ksegments which are consisted ofknon-overlapping bits,i.e.,M=m1,m2,m3,···,md.

(ii) Setting tail-biting parametersΔ

The last Δ segments of the blockMare added to the head of original sequences,and the order of the blocks added in the head is the same as tail blocks,so it is called tail-biting encoding structure.Suppose that two information block to the header are added,setting up Δ=2,and the new sequence isM′=md′-1,md′,m1,···,md-1,mdwith the same head and tail obtained,among whichmd′-1=md-1,md′=md.

(iii) Coded transmission

The initial state values0and the first information segment of the new sequenceM′are input into the hash functionh(·) to generate the next state value.Then the state value and the next segment are sent to the hash function,and the process is carried out successively until all information is processed byh(·).Eventually,a total ofd+Δstate values are generated.The hash function formula is given as follows:

The initial hash values0is known by both the encoder and the decoder,and it is assumed thats0is the zero set ofv-dimension.Then,these states are used as seeds for the random number generator (RNG) [21,22] and multibatch output generates a sequence ofc-bit pseudo-random numbers.The RNG formula is given as

whereLis the number of passes.

Finally,the sequence ofc-bit is mapped into the encoded symbolxi,jsuitable for channel transmission,whereiis theith state value andjis the batch sequence of symbols.

The tail-biting,also known as cyclic encoding,ensures that the initial and termination states of each component encoder are the same [23,24].In previous research,tailbiting convolutional codes could overcome the rate loss caused by initializing the coder with known bits [25],and the tail-biting encoding structure could solve the existing error-level phenomenon in turbo codes [26].

Fig.1 illustrates the encoding structure of tail-biting for spinal codes with Δ=2.The decoding process of tailbiting structure is roughly the same as the original process,only the optimal path is determined when decoding output is different.Assume that the decoder uses the bubble algorithm,and the original spinal codes selectBcandidate paths reserved in the decoding tree extending to the last level.After tail-biting treatment,when selecting the optimal decoding output fromBcandidate paths,the reliability of the paths is sorted first,and the path information corresponding to the paths with the same decoding results of the top Δ segments and the last Δ segments are selected as the decoding results.If theBpaths do not meet the condition requirement,the highest reliability is selected as the optimal path,and the top Δ segments replace the last Δ information segments as the final decoding result (Δ is a positive integer).

Fig.1 Encoding structure of tail-biting for spinal codes

2.2 Error probability analysis and comparison

The main purpose of tail-biting encoding structure is to improve the transmission reliability,so the performance is compared through calculating the symbol error rate of the proposed and the original structure.According to[10],the block error rate of the original spinal codes is calculated,where=Mrepresents the probability that the input information sequenceMis the same as the decoded output sequence.

At the transmitter,the mutual information between the blockmdand the transmission code symbolsx1,x2,···,xd-1is zero and independent of each other.The information ofmdis only carried by the coding symbolxd,therefore,the average error probability of the last information block can be taken as the lower bound of the average error probability of the whole spinal codes.

wherepdindicates that the decoding of the firstd-1 information segments is correct.While the decoding failure probability of thedth information block can be regarded as the error probability of a single information block,it can be regarded as the error probability of a single information block.

For the tail-biting spinal codes with parameter Δ,the total error probability is as follows:

It can be found that the segment leading to the error of the tail-biting spinal code ismd-1.That is,the lower bound of the overall BER is given as

It is obvious that the error correction capability of the spinal codes with Δ=2 is determined by the information blockmd-2.

By analogy,the error formula of spinal codes under different tail-biting parameters can be obtained,owing topi-1≤pi(1 ＜i≤d).Compared with the original structure,the lower bound of error probability and the error correction performance of the tail-biting spinal codes are effectively improved.

2.3 Performance analysis of tail-biting spinal codes

By observing the location distribution with error prone symbols,the appropriate Δ is selected.The simulation conditions are as follows: assume that the channel model is AWGN,the information isn,the segment lengthk=4,the number of passesL=8,the pruning parameterBof each layer is 32 by using the bubble algorithm,and the tail-biting parameter is Δ.

When 1 000 frames of message are transmitted,the relationship between the relative position of information block and the number of error symbols is shown in Fig.2.The error location of spinal codes is mainly concentrated in the tail,and its error correction performance becomes worse with the decline of SNRs.The information length is different,the error probability of the symbol in the front 3/4 position is lower,while the error probability of the information block in the last 1/4 position is higher.

Fig.2 Error location and numbers of messages for original spinal codes

Assume that 32 bits are transmitted per frame,the comparison between the original and the tail-biting spinal codes with parameter Δ=1 and Δ=2 is conducted.

The symbol error rate (SER) of spinal codes is shown in Fig.3.For different encoding structures,with the increase of SNRs,the SER decreases rapidly.In the same channel state,the SER of the designed structure is better than that of the original structure.And the error correction ability of the structure with two tail symbols in the head is more outstanding than that of the structure with one tail symbol.Therefore,the tail-biting spinal codes have the better performance.

Fig.3 SER comparison of spinal codes with different encoding structures

Because the number of transmission passes is reduced,the number of channel coding symbols required for correct decoding is reduced,and the transmission overhead is also reduced accordingly.

3.Improved decoding algorithms

3.1 Forward stack decoding algorithm

Based on the principle of the stack algorithm,the researcher proposes the FSD algorithm with lower decoding complexity.The FSD method divides the entire tree into several units.By dividing then/k-layer decoding tree inton/kDunits,the parameterD(D＜n) is the integer that decides the layer of each unit.

The search process of the FSD algorithm can be depicted in Fig.4.The FSD algorithm starts with the root node,searches the stack in the first basic unit,obtains the optimal node in this unit,and saves it.Then,according to the results of the first unit,the stack is carried out in the second unit to obtain the optimal node.With the same method,the last unit is searched and the optimal node path is output.Compared with the stack decoding algorithm,the FSD algorithm controls all units independently,restrains the large jump between nodes in the stack decoding process,and effectively reduces the search amount of invalid nodes.At the same time,the maximum number of storage nodesBis set in the path reservation stackBand the maximum number of searching nodesCis controlled in the search expansion of each unit.The storage requirement for the stack capacity is significantly reduced in the whole decoding process of spinal codes,which is conducive to the simplification of the decoding equipment in the specific engineering practice.

It can be seen from Fig.4 that obviously,the number of nodes in the reserved stackBremains unchanged after the search expansion of each unit is completed.By analyzing the complexity of the FSD algorithm,it can be seen that the number of reserved nodes per unit directly affects the computational complexity and BER performance of the spinal codes.When the channel conditions are relatively stable,the fixed nodes will cause the reservation of an invalid path and increase the overall decoding complexity of the decoding tree.When the channel states are bad,the optimal node expansion will lead to more error paths searched,which is not ideal for further reducing the decoding complexity of the spinal codes.Therefore,new decoding algorithms are needed.

Fig.4 Search process of FSD algorithm (D=2)

3.2 Adaptive forward stack decoding algorithm

In this subsection,an A-FSD algorithm is proposed.This algorithm can dynamically adjust the number of storage nodes by combining channel state information and reduce the decoding complexity of spinal codes.

The A-FSD algorithm designs a threshold to control the number of storage nodes per unit based on the FSD algorithm.The threshold is mainly determined by the minimum path metric of the current unit and the variance of intra-channel noise.Define a threshold of every uniti.It can be expressed as Γi=εi,min+2τ·f(SNR),where εi,minis the minimum metric in theith unit and τ represents a specific threshold control index.Thef(SNR)denotes the currently estimated channel SNRs function whose value is inversely proportional to SNR.That is,it is positively increased with channel interference and noise power.Therefore,in theith unit of the decoding tree,the cumulative path metrics of the nodes with a depth ofiDin search stackCare compared with the size of Γi.When the value is greater than Γi,the node is discarded.Judge whether the number of surviving nodes is less thanB.If it is,then all nodes are saved in stackB,and recode the number of actual nodes asBi.If not,only the firstBnodes with the greatest reliability are saved.

In the process of node selection using an adaptive method,the determination of threshold Γiis related to the decoding effect of spinal codes.The positive and negative effects vary greatly and cannot be ignored.If the threshold is too small,the bad effect is that the correct decoding path is easily discarded,and the information transmission becomes worse.On the contrary,the total decoding complexity will increase while the quality of information transmission is stable.In a word,for different channel conditions,different thresholds need to be set up,the size of thresholds should also be taken into account to minimize the loss of performance and reduces the complexity as much as possible.

The adaptive adjustment of the A-FSD decoder needs the cooperation of the channel estimation algorithm.Typical SNR estimation methods for AWGN channels include M2M4 estimation [27,28],singular value decomposition[29] and data fitting algorithm [30].In this paper,we adopt the data fitting algorithm with simple calculation and accurate estimation.

The adaptive property of the A-FSD algorithm is mainly reflected in blind channel estimation using received signals to control the number of nodes.Apparently,the complexity of the improved A-FSD algorithm is better than the FSD algorithm,because the number of storage nodes for the A-FSD algorithm is no more than the capacity of stackB.

3.3 Adaptive forward stack decoding with ET

Based on the principle of the A-FSD algorithm,a new algorithm named AFSD-ET is proposed.It can achieve a better tradeoff between performance and decoding complexity.

The main ideas of the improved AFSD-ET algorithm are as follows.Firstly,based on the FSD decoding structure,the search unit size is set toD.Therefore,the whole decoding tree is divided inton/kDunits,and then the divided decoding units are divided into two groups,set the grouping parameter toT,T∈{1,2,···,n/kD}.The first group is defined as the unit number less than or equal to the block parameterT,the decoding algorithm is based on the A-FSD decoder principle,and the remaining units are automatically divided into the second group.Secondly,the nodes stored in the reserved path stackBafter decoding in the first group are taken out and arranged in the order of path metrics.They are called pseudo root nodes and are used as the initial decoding nodes in the second group.The first pseudo root node (the minimum cumulative path metric) is regarded as the root node whose metric value is not zero,and then it is extended to the leaf node according to the A-FSD decoding principle.At this time,the path metric value of the optimal path is recorded as the threshold value Λmin.Eventually,the A-FSD algorithm is used to search for the second pseudo root node.Λminis used as the threshold in the process of searching.For nodes whose path metric value is greater than Λmin,the search is stopped by using the ET criterion.Only the nodes less than the threshold are searched until the leaf node is found.If the metric value of the optimal leaf node is less than Λmin,then the threshold Λminis updated by this metric value,and the remaining pseudo root nodes are detected in turn according to the above method.The path corresponding to Λminis taken as the decoding output.Fig.5 shows a decoding tree of the AFSD-ET algorithm,where the values ofTandDare set to be 2.

Fig.5 The AFSD-ET algorithm (Example of an 8-depth decoding tree with T=2 and D=2)

The proposed algorithm takes each pseudo root node as a whole and adopts the depth first search strategy to speed up the speed of decoding to the leaf node in the process of detecting the second group of search points in the decoding tree.At the same time,combined with the ET criterion,it can flexibly adjust the decoding search path,significantly reducing the number of search nodes.

The specific steps of the AFSD-ET decoding algorithm can be described as follows.

Step 1Initialize parameters.The messageMwith transmission length ofnbits is divided inton/kdepths inkbits.If the size of search unit isD,the whole decoding tree containsn/kDunits.The frontTunits (including theTth unit) are divided into the first group,and the remaining units are divided into the second group.

Step 2In the first group,the A-FSD algorithm is used to search from the root node to theDTth layer.In theDTth layer,all nodes stored in the reserved path stackBare taken out,and the number of nodes is counted asB1who are called pseudo root nodes according to the path metric value from small to large.It is marked asand its corresponding cumulative path measure is marked as

The detailed AFSD-ET algorithm is illustrated in Algorithm 1.

Algorithm 1The AFSD-ET

22 save the current optimal node,recode the cost metric as εminand the corresponding decoding is.

23end for

24 return

Before the start of the second group of decoding,the pseudo root nodes are sorted in advance,which increases the probability that the output path along the first candidate node becomes the maximum likelihood path,and by updating Λmin,the path metric value of the maximum likelihood path can be approached with greater probability.

3.4 Theoretical analysis of decoding complexity

4.Performance evaluation

To further evaluate the performance of the improved spinal codes,a serial of simulations are carried out.In this paper,the feedback delay from the decoder to the sender is neglected.All simulations use the AWGN channels,and the parameters of the spinal codes aren=32,k=4,L=8,D=2.The storage parameterBis 32.The maximum size of stackCis set to 4 096.

4.1 Parameters selection of the A-FSD algorithm

It can be seen from Fig.6 that the BER performance among the bubble,the FSD and the A-FSD algorithms are very close at τ=5.Thus it can be considered that they are consistent in error control ability of spinal codes.The performance of the A-FSD decoding algorithm with different values of τ is analyzed.Under the same channel environment,with the increase of τ value,the BER performance is closer to the other two algorithms.When a certain value is taken,the performance of A-FSD decoding is very different from that of the traditional spinal decoding algorithm.The main reason for the performance difference is that when τ is smaller,the threshold of the number of surviving control nodes is also smaller,which increases the probability of deleting the correct path,resulting in the degradation of the decoding performance of spinal codes.With the increase of τ value,the threshold is enlarged,and the node stored in the reserved stack of the A-FSD algorithm is close to that of the FSD algorithm,so its error correction performance is also improved.

Fig.6 BER for spinal codes with A-FSD algorithm

The complexity of different decoding methods refers to the average number of nodes accessed about a frame of information in the decoding process.Fig.7 simulates the calculation costs of different algorithms.Through comparison,it can be found that under the same SNRs,compared with the bubble decoding algorithm,the average number of access nodes of the FSD algorithm and the A-FSD algorithm is greatly reduced,but the calculation amount of the FSD algorithm and the A-FSD algorithm under lower SNRs is still high.With different parameter τ,the number of access nodes decreases in the whole SNR range,especially when the control parameters are small,the calculation amount of nodes is significantly reduced.To sum up,the proposed novel algorithm not only guarantees the transmission performance of spinal codes,but also optimizes the decoding complexity compared with the traditional decoding algorithm.

Fig.7 Computation cost for spinal codes

4.2 Parameters comparison of AFSD-ET algorithm

In the AFSD-ET algorithm,the value ofTdirectly affects where the second group begins to use depth first search and ET strategy to further optimize decoding.The simulation results with differentTare shown in Fig.8.At low SNRs,the performance of AFSD-ET is similar with different packet parameters.With the increase of SNRs,the performance difference gradually increases,and the maximum performance gap can reach 2.4 dB.Under the same threshold control parameters,whenT=4,the BER performance of the decoding algorithm is poor.With the decrease ofT,the error control ability of spinal codes is gradually improved.WhenT=1,the decoding performance is optimal.When τ=5,T=2 and τ=5,T=3,the performance gap of the AFSD-ET algorithm is very small.It can be seen that for the improved algorithm,when the first group of decoding tree contains similar units,its performance is closer.

Fig.8 BER of AFSD-ET decoding algorithms

It can be seen from Fig.9 that when τ=5,T=1,the AFSD-ET algorithm has the largest number of access nodes.The main reason is that the number of layers requiring depth first search is large,resulting in a large difference in path metrics.Starting from the second pseudo root node,it needs to be extended to deeper nodes to effectively use the ET strategy.Therefore,the number of search nodes is increased with smallerT.Whenτ=5,T=4,because A-FSD decoding structure is used in the whole decoding process,the depth first search and ET criteria are not used,so the decoding complexity is also large.When SNR ＜ 5 dB,the complexity ofT=3 is slightly better thanT=2,but the difference between the two cases is small;when SNR ＞ 5 dB,the complexity ofT=2 is lower thanT=3,and the number of nodes visited is different.It can be seen that the more similar the number of units contained in the two groups of the whole decoding tree,the better the advantages of depth first search and ET criteria can be achieved by setting the grouping parameters.When the performance is similar,the decoding complexity of spinal codes decreases faster.

Fig.9 Computation cost of AFSD-ET decoding algorithm

4.3 Comparison of four decoding algorithm

Fig.10 provides the BER comparison of two traditional decoding algorithms and two improved decoding algorithms.It can be found that with the increase of SNRs,the error correction performance of several decoding algorithms is improved.At the same time,it can be observed that the BER performance of the AFSD-ET algorithm proposed in the previous section is slightly improved in the whole SNR range.However,on the whole,the BER performance of the AFSD-ET algorithm is similar to that of other algorithms.

Fig.10 BER comparison of four decoding algorithms

The number of access nodes of four decoding algorithms with the same code rate are compared in Fig.11.The result shows that the complexity of the two improved algorithms proposed in this paper is lower than that of the traditional spinal codes,and the complexity of the AFSDET algorithm decreases more obviously.Therefore,it is verified that the use of depth first search and ET strategy can greatly reduce the decoding tree search.

Fig.11 Computation cost of four decoding algorithms

4.4 Performances of improved spinal codes

The BER performances of tail-biting spinal codes and comparable traditional spinal codes with bubble decoder or AFSD-ET decoder under the rate being 1 are shown in Fig.12.According to the simulation results,considering two different decoding algorithms separately,the reliability of the tail-biting encoding structure is better than that of the one without adding the tail symbol.Compared with the conventional decoding algorithm,the improved decoder provides better error control performance for the tail-biting scheme.We can see from the curves that the spinal codes perform the best by adding tail-biting symbols and using the novel AFSD-ET decoding method over the AWGN channel.Thus,the transmission of the messages by applying tail-biting spinal codes with the proposed decoding method exhibits better performance.

Fig.12 BER comparison for spinal codes

5.Conclusions

In this paper,firstly,to solve the problem that the error bits of spinal codes are always concentrated in the last several segments,a novel structure of spinal codes with the tail-biting is proposed.The proposed coding structure can effectively enhance the reliability in transmission.Secondly,in the light of the problem of high computation of the decoding algorithm,an adaptive algorithm is designed to control the number of stored nodes according to the threshold value,which needs to be set by the blind channel estimation algorithm to predict the SNR of the AWGN channel.The A-FSD reduces the computation to a certain extent.In order to further optimize calculations,the AFSD-ET decoder is proposed,which combines the depth-first search and ET criteria,and effectively controls the tradeoff between the error performance and calculation amount of Spinal codes.Moreover,the spinal codes perform well by using the tail-biting structures and adopting the novel AFSD-ET decoding method over the AWGN channel.