In this paper, a mathematical framework for APP decoding of binary linear block codes on the Gilbert-Elliott channel (GEC) is developed. For this purpose, the theory of group representations and finite state machines are combined for deriving a `dual APP' algorithm for the GEC. The presented approach belongs to the class of single-sweep algorithms. As such, complexity benefits of the dual approaches are preserved while additional storage savings are obtained over other single-sweep algorithms. The presented APP decoding technique also takes account of the increasing demand for efficient utilization of bandwidth making higher rate codes more desirable.