Bootstrap hybrid decoding for symmetrical binary input channels

Information and ControlPublished 1 April 1971

F. Jelinek, John Cocke

Citations24

TL;DR

A new method of decoding is presented that utilizes algebraic constraints across streams of convolutionally encoded information sequences to improve the performance of ordinary sequential decoding and over the older hybrid scheme developed by Falconer.

Abstract

A new method of decoding is presented that utilizes algebraic constraints across streams of convolutionally encoded information sequences. The scheme works for all channels that are symmetrical from the input. Theoretical performance curves are presented showing the improvement over ordinary sequential decoding and over the older hybrid scheme developed by Falconer. Some simulation results are also reported on.

Keywords

Computer ScienceEngineering

IEEE Transactions on Information TheoryLow-density parity-check codes

10,471 Citations1962Robert G. Gallager

A simple but nonoptimum decoding scheme operating directly from the channel a posteriori probabilities is described and the probability of error using this decoder on a binary symmetric channel is shown to decrease at least exponentially with a root of the block length.

The MIT Press eBooksLow-Density Parity-Check Codes

4,396 Citations1963Robert G. Gallager

IBM Journal of Research and DevelopmentFast Sequential Decoding Algorithm Using a Stack

538 Citations1969F. Jelinek

A new sequential decoding algorithm is introduced that uses stack storage at the receiver that is much simpler to describe and analyze than the Fano algorithm, and is about six times faster than the latter at transmission rates equal to Rcomp.

IEEE Transactions on Information TheoryA lower bound to the distribution of computation for sequential decoding

155 Citations1967I. M. Jacobs, Elwyn R. Berlekamp

The performance of systems using sequential decoding is limited by the computational and buffer capabilities of the decoder, not by the probability of making a decoding error.

IEEE Transactions on Information TheoryA construction technique for random-error-correcting convolutional codes

70 Citations1969Daniel J. Costello

It is shown how the above algorithm can be modified slightly to produce codes with known free distance, and a comparison of probability of error with sequential decoding is made among the best known constructive codes of constraint length.

IEEE Transactions on Information TheoryAn upper bound on moments of sequential decoding effort

63 Citations1969F. Jelinek

An infinite tree code ensemble upper bound is derived on the moments of the computational effort connected with sequential decoding governed by the Fano algorithm, which agrees qualitatively with the lower bounds of Jacobs and Berlekamp.

DSpace@MIT (Massachusetts Institute of Technology)A hybrid sequential and algebraic decoding scheme

19 Citations1967D.D. Falconer

This paper is intended to demonstrate the efforts of the Massachusetts Institute of Technology’s graduate students to improve the quality of their teaching and research in the field of electrical engineering.

View PDF

Bell System Technical JournalA Hybrid Coding Scheme for Discrete Memoryless Channels*

19 Citations1969D.D. Falconer

It is shown that the hybrid technique reduces the variability of the amount of sequential decoding computation, and asymptotic results for the probabilities of error and buffer overflow as functions of the system complexity are derived.

IRE Transactions on Communications SystemsChannel Coding with a Sequential Algebraic Coding Scheme

6 Citations1971F. L. Huband, F. Jelinek

In this paper a simple coding scheme utilizing both sequential and algebraic coding is proposed, and bounds on its performance are derived using theoretical bounds on the performance of sequential decoding.