  A characterization of systematic network coding over multi-hop wireless
networks is key towards understanding the trade-off between complexity and
delay performance of networks that preserve the systematic structure. This
paper studies the case of a relay channel, where the source's objective is to
deliver a given number of data packets to a receiver with the aid of a relay.
The source broadcasts to both the receiver and the relay using one frequency,
while the relay uses another frequency for transmissions to the receiver,
allowing for a full-duplex operation of the relay. We analyze the decoding
complexity and delay performance of two types of relays: one that preserves the
systematic structure of the code from the source; another that does not. A
systematic relay forwards uncoded packets upon reception, but transmits coded
packets to the receiver after receiving the first coded packet from the source.
On the other hand, a non-systematic relay always transmits linear combinations
of previously received packets. We compare the performance of these two
alternatives by analytically characterizing the expected transmission
completion time as well as the number of uncoded packets forwarded by the
relay. Our numerical results show that, for a poor channel between the source
and the receiver, preserving the systematic structure at the relay (i) allows a
significant increase in the number of uncoded packets received by the receiver,
thus reducing the decoding complexity, and (ii) preserves close to optimal
delay performance.
