CONVOLUTIONAL TRANSFORMATIONS OF BINARY SEQUENCES: BOOLEAN FUNCTIONS AND THEIR RESYNCHRONIZING PROPERTIES,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1966
- Accession Number
- AD0630625
Entities
People
- Franco P. Preparata
Organizations
- University of Illinois Urbana–Champaign