We present an a posteriori probability (APP) decoding algorithm for binary linear block codes over a Gilbert- Elliott channel (GEC) using generalized weight polynomials. The proposed approach is based on a single-sweep APP decoding technique that uses matrix multiplications. By fixing the crossover probability in the ‘bad’ state of the GEC at fifty percent, an APP decoding decision can be reached by evaluating trivariate polynomials without the need for the computationally more expensive matrix multiplications. In this case, the GEC is described by three variables, namely, the average fade to average connection time ratio, the burst factor, and the channel reliability factor. These variables can easily be deduced from error sequence measurements and hence can be related to many practical digital communication scenarios. The polynomial approach is demonstrated using a simple example and results of computer simulations are presented.