Colour-and-Forward: Relaying “what the destination needs” in the zero-error primitive relay channel

Zero-error communication over a primitive relay channel is for the first time proposed and studied. This model is used to highlight how one may exploit the channel structure to design a relaying strategy that explicitly provides “what destination needs”. We propose the Colour-and-Forward relaying scheme which constructs a graph G_R of relay outputs based on the joint conditional distribution of the relay and destination outputs given the channel input. The colours of this graph G_R are sent over the out-of-band link in the primitive relay channel and are shown to be information lossless in the zero-error sense; they result in the same confusability graph as if the destination had the relay´s received signal. This allows us to obtain an achievable zero-error communication rate for the primitive relay channel, which may be shown to be capacity for a class of channels.