The technique of atomic span modification is used to construct non-minimal trellises for linear block codes. Non-minimal trellises may have properties like regularity and vertex localization that make the corresponding trellis-based decoding algorithms better-suited for VLSI or multiprocessor implementation. A simple class of “universal” trellises with a regular structure is defined, from which soft decision decoders can be built by parallel combination of identical trellis search processors. Coset decoding is proposed as a general soft-decision decoding technique for multiprocessor implementation, and algorithms for selecting a sub-code to achieve large speedup are described.