C0NV0LUTI0NAL TRANSFORMATIONS OF BINARY SEQUENCES: BOOLEAN FUNCTIONS AND THEIR RESYNCHRONIZING PROPERTIES

摘要

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 resynchronlzing states of Boolean func-tions. The algebraic properties of resynchronizlng states are carefully analyzed;it is shown that they can be assigned only in special sets, termed clusters, which form a lattice.