In this paper, a general reliability-updating formula is proposed for trellis-based soft-output decoding algorithms to optimize the tradeoff between performance and complexity. Based on the general formula, new algorithms are presented, and a concise interpretation is provided to relate new proposed algorithms and those reported previously. In addition, we devise a unified decoding structure with respect to the general formula. All trellis-based algorithms are mapped into a single decoding process under the unified structure, and different algorithms can be easily switched between one another. Owing to the modularity and flexibility, this unified structure is especially suitable for turbo decoders with programmable implementation.