# Accession Number:

## AD0630625

# Title:

## CONVOLUTIONAL TRANSFORMATIONS OF BINARY SEQUENCES: BOOLEAN FUNCTIONS AND THEIR RESYNCHRONIZING PROPERTIES,

# Descriptive Note:

# Corporate Author:

## ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

# Personal Author(s):

# Report Date:

## 1966-03-01

# Pagination or Media Count:

## 41.0

# Abstract:

Non-feedback shift registers finite-memory encoders can be profitably adopted to perform transformations of binary sequences. The output sequence is convolutionally obtained by sliding the encoding device along the input sequence and producing a symbol at each shift. Invertible transformations are characterized and decoding schemes are analyzed. The crucial point in the decoding problem is that the simply finite-memory feedback decoder presents the undesirable well-known error propagation effect, while the non-feedback decoder contains, in general, an indefinite number of stages. Finite-memory non-feedback decoding is feasible, however, if some constraint is imposed on the input sequences, or, equivalently, if some decoding error is tolerated. The analysis is conducted through the concepts of resynchronizing states of Boolean functions. The algebraic properties of resynchronizing states are carefully analyzed it is shown that they can be assigned only in special sets, termed clusters, which form a lattice. Moreover, each cluster of resynchronizing states is possessed by a set of Boolean functions, which form a subspace of the vector space of all Boolean functions. The presented analysis provides a formal tool to relate finite-memory non-feedback decoding to the constraint imposed on the input generating source. Author

# Descriptors:

# Subject Categories:

- Cybernetics