Compression of multispectal images is of great importance in an environment where resources such as computational power and memory are scarce. To that end, we propose a new extremely lowcomplexity encoding approach for compression of multispectral images, that shifts the complexity to the decoding. Our method combines principles from compressed sensing and distributed source coding. Specifically, the encoder compressively measures blocks of the band of interest and uses syndrome coding to encode the bitplanes of the measurements. The decoder has access to side information, which is used to predict the bitplanes and to decode them. The side information is also used to guide the reconstruction of the image from the decoded measurements. Our experimental results demonstrate significant improvement in the rate-distortion trade-off when compared to coding schemes with similar complexity.