Coding for Skew-Tolerant Parallel Asynchronous Communications

Abstract

Consider a communication channel that consists of several subchannels transmitting simultaneously and asynchronously. As an example of this scheme, consider a board with several chips. The subchannels represent wires connecting between the chips where differences in the lengths of the wires might result in asynchronous reception. In current technology, the receiver acknowledges reception of the message before the transmitter sends the following message. Namely, pipelined utilization of the channel is not possible. The main contribution is a scheme that enables to transmit without an acknowledgement of the message, therefore enabling pipelined communication and providing a higher bandwidth. Moreover, the scheme allows for a certain number of transitions from a second message to arrive before reception of the current message has been completed, a condition that we call skew. Necessary and sufficient conditions for codes that can detect skew as well as for codes that are skew-tolerant, i.e., they can correct the skew and allow continuous operation, are derived. Codes have been constructed that satisfy the necessary and sufficient conditions, their optimality studied, and efficient decoding algorithms devised. To the best of the authors’ knowledge, this is the first known scheme that permits efficient asynchronous communications without acknowledgement. Potential applications are in on-chip, on-board and board to board communications, enabling much higher communication bandwidth. © 1993 IEEE.