Invertible shift-invariant transformations on binary arrays

摘要

The invertibility and propagation properties of binary shift-invariant transformations are treated. Linear shift-invariant transformations can be modeled by polynomial multiplication modulo 1 + xn. Nonlinear transformations requirea more ad hoc approach. A distinction is made between “local” invertibility and “global” invertibility. Proofs of invertibility are given for a number of examples in the form of an algorithm to compute the inverse transformation. Multiplication modulo 2n – 1 by a constant is shown to be a shift-invariant transformation.