We present an a-posteriori probability (APP) decoding algorithm for linear block codes over prime fields when used on non-binary Gilbert-Elliott channels (GECs). The proposed approach is based on a single-sweep APP decoding technique that uses matrix multiplications. The trellis-based decoding algorithm incorporates the channel-induced error process by modeling it as a stochastic automaton. It is applicable to high rate block codes over prime fields on channels with memory such as the non-binary GEC. It allows simple implementation in the spectral domain.