Coding for Delay-Insensitive Communication with Partial Synchronization

Abstract

Assume that information is transmitted in parallel among many lines in such a way that an electrical transition represents a 1 and an absence of a transition represents a 0. The propagation delay in the wires varies and results in asynchronous reception. The challenge is to find an efficient communication scheme that will be delay-insensitive. One of the common solutions to this problem is to use a handshake mechanism. Namely, the transmitter sends the next vector only after getting an acknowledgment that the current vector was received. A natural question is: how does the receiver know that reception of the current vector is complete? This problem was solved by Verhoeff by using the so-called unordered codes. However, in practice, it is common that the communication lines are arranged in pairs (double-rail) such that the propagation delay on the lines within a pair is identical. In general, the lines can be arranged in groups (of size larger than 1) where transmission within a group is synchronized. We have created a few delay-insensitive schemes that take advantage of partial synchronization within groups. To achieve that, we have generalized to arbitrary alphabets the following known results: Sperner's theorem on unordered sets, Henry-Knuth's construction of balanced codes, and Berger's con- struction of unordered codes. Finally, we have focused on practice, and constructed a code that uses double-rail channels but has the advantage that it is a rate 3/4code as opposed to the rate 1/2double-rail code (that is the common code being used in real systems). © 1994 IEEE