Successively Solvable Shift-Add Systems — a Graphical Characterization

In order to reduce computational complexity in data encoding, one can use bitwise shifts and logical XOR operations instead of more costly calculations, and apply a fast decoding method called zigzag decoding. Existing works on zigzag decoding usually design special generator matrices that enable certain zigzag solving algorithms. In this paper, we study this class of fast decoding methods holistically. The shift operations are represented by a shift matrix, whose entries are integers or a special infinity symbol. A negative entry signifies that some symbols are truncated, and an infinity symbol means that the corresponding input sequence is not involved in the encoding process. Two notions of solvability, called successive solvability and zigzag solvability, are formulated. The former is employed in most of the existing works on zigzag decoding, and is a special case of the latter one. We prove in this paper that these two notions of solvability are equivalent when the shift matrix have no negative entries. An equivalent condition for a successively solvable shift-XOR system is derived in terms of a directed graph, when the shift matrix has only finite entries. This characterization reveals the structure and the interconnections between the problem instances.