Uniquely decodable codes for deterministic relay channels

The deterministic relay channel is analyzed and explicit code constructions for all binary and all ternary/binary channels are given. An explicit set of equivalence conditions is used to make a classification of all such relay channels, for which also the capacity is evaluated. The coding problem is then reduced to finding all possible output sequences of a certain finite-state channel determined by the relay coding strategy. The channel states correspond to the possible relay memory contents. For some relay channels capacity is reached by using simple uniquely decodable codes, thus establishing the zero-error capacity of those channels with finite-memory relay strategies. For other relay channels the relay memory must be arbitrarily large to achieve zero-error rates arbitrarily close to capacity. One such code construction is given. It is not known whether there exist relay channels for which the zero-error capacity is strictly smaller than the average-error capacity. The code construction problem for the semideterministic relay channel and for the nonsynchronized relay channel is briefly considered