On Sequential Decoding of Linear Convolutional Codes

We analyze the complexity of the sequential decoding algorithm using a time- varying linear convolutional code. An asymptotic upper bound is obtained for the number of computations performed by the decoder in the initial node of the code trellis, which coincides up to a constant with the known bound for linear tree codes [T. Hashimoto and S. Arimoto, IEEE Trans. Inf. Theory, 1979, vol. 25, no. 5, pp. 584–591].