# Accession Number:

## AD0266879

# Title:

## SEQUENTIAL DECODING FOR BINARY CHANNELS WITH NOISE AND SYNCHRONIZATION ERRORS

# Descriptive Note:

# Corporate Author:

## MASSACHUSETTS INST OF TECH LEXINGTON LINCOLN LAB

# Personal Author(s):

# Report Date:

## 1961-10-27

# Pagination or Media Count:

## 1.0

# Abstract:

Consider a channel for which the input is a sequence of binary digits and for which the output is the same sequence with each digit independ ently modified in the following way with probability Pe, the digit is changed with probability Pd, the digit is deleted from the sequence and with probability Pi, the digit is replaced by two randomly chosen digits. The channel output gives no indication which digits were deleted or inserted. It is shown that convolutional coding and sequential decoding can be applied, with minor modifications, to this channel and bounds are derived on computation and error probability analogous to the bounds for the Binary Symmetric Channel. More precisely, a computational cut-off rate is defined. For code rates less than Rcomp bits per digit, the average decoding computation in the incorrect subset grows more slowly than linearly with the coding constraint length, and the probability of decoding error decreases exponentially with constraint length. For PdPi0, the above expression for Rcomp reduces to that derived by Wozencraft and Reiffen for the Binary Symmetric Channel. Author