CODING FOR DELAY-INSENSITIVE COMMUNICATION WITH PARTIAL SYNCHRONIZATION

Assume that information is transmitted in parallel among many lines in such a way that an electrical transition represents a 1 and an absenc e of a transition represents a 0. The propagation delay in the wires v aries 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 mechanis m. Namely, the transmitter sends the next vector only after getting an acknowledgment that the current vector was received. A natural questi on is: how does the receiver know that reception of the current vector is complete? This problem was solved by Verhoeff by using the so-call ed unordered codes. However, in practice, it is common that the commun ication lines are arranged in pairs (double-rail) such that the propag ation delay on the lines within a pair is identical. In general, the l ines can be arranged in groups (of size larger than 1) where transmiss ion within a group is synchronized. We have created a few delay-insens itive schemes that take advantage of partial synchronization within gr oups. To achieve that, we have generalized to arbitrary alphabets the following known results: Sperner's theorem on unordered sets, Henry-Kn uth's construction of balanced codes, and Berger's construction of uno rdered 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/4 code as opposed to the rate 1/2 double-rail code (that is th e common code being used in real systems).