Computational moments for sequential decoding of convolutional codes

The long standing conjecture is established that, for a discrete memoryless channel, there exists a linear convolutional code with infinite constraint length such that the th moment of the number of -hypotheses in the Fano sequential decoding algorithm is bounded, provided that the transmission rate is less than , where is a distribution over the channel input alphabet. A new concept of independence for a finite set of message sequences plays an essential role in averaging a product of likelihood ratios over an ensemble of code sequences in a code tree. A simpler version of the method can be applied to the proof of the conjecture for general tree codes.