Coding Method for Skewed Transition Correction in Parallel Asynchronous Communication Systems

1. For use in a parallel asynchronous information communication system in which binary electrical signals are transformed and transmitted as unordered ECC codewords in sequences of contemporaneous electrical transitions over n parallel channels without requiring acknowledgement, a decoder comprising: a set processor for (i) generating sets A from transitions that arrive prior to receipt of a last transition in a then current codeword and are not repeated arrivals but belong in the next following codeword and (ii) storing as a set B up to a preselected number of transitions constituting repeated arrivals of transitions belonging to said next codeword, said set processor also separately outputting as binary electrical signals k information bits and (n-k) redundancy bits from the codewords as received from the channels; and a reset circuit operative when the k information bits are determined to be skew free to release the union of sets A and B from the processor as a first received vector for said next codeword and reset set B to an empty set.

2. The decoder of claim 1, including: an encoder for encoding the k bits output by the set processor into an unordered ECC codeword with k information bits and (n-k) redundancy bits; a comparator for issuing a compare signal if the (n-k) bits output by the set processor and by the encoder are equal; circuitry responsive to the compare signal to output as skew free the k information bits as encoded by the encoder; and wherein said reset circuit is responsive to the compare signal to release the union of sets A and B from the processor and reset set B.

3. The decoder of claim 1, wherein said codewords are selected to provide a (t.sub.1,t.sub.2) skew-tolerant code in which: t.sub.1 is the preselected maximum number of transitions that may be missing from the current codeword when a transition arrives from said next codeword; and t.sub.2 is the preselected maximum number of transitions which may arrive from said next codeword before all of the transitions arrive from said current codeword; and at least one of the following conditions occurs for each arbitrary pair of codewords X and Y in the set: (a) min{N(X,Y), N(Y,X)}.gtoreq.t+1, or (b) min{N(X,Y), N(Y,X)}.gtoreq.1 and max{N(X,Y), N(Y,X)}.gtoreq.t.sub.1 +t.sub.2 +1, where t=min(t.sub.1,t.sub.2), and N(X,Y) is the number of coordinates in which X is 1 and Y is 0.

4. The decoder of claim 1, wherein the codewords are constructed from a standard error correcting code having sufficient word length to accommodate the number of information bits to be transmitted and also having a minimum distance between each arbitrary pair of codewords of (t.sub.1 +t.sub.2 +t+1).

5. In a parallel asynchronous information communication system for transmitting information as sequences of contemporaneous transitions over n parallel channels without requiring acknowledgement, apparatus for detecting and correcting skewed transitions comprising: a first encoder for transforming a series of k transitions constituting information bits into sets of unordered ECC codewords, each consisting of k information bits and (n-k) redundancy bits; an asynchronous receiver; a transmitter for transmitting the codewords over the n channels to the receiver; and a decoder comprising: (a) a set processor for (i) generating sets A from transitions that arrive prior to receipt of the last transition in a current codeword and are not repeated arrivals but belong in the next codeword, and (ii) storing as a set B up to a preselected number of transitions constituting repeated arrivals of transitions belonging to said next codeword, said set processor also separately outputting k bits and (n-k) bits of the codeword as received from the channels; (b) a second encoder for encoding k bits output by the set processor into an unordered ECC codeword with k information bits and (n-k) redundancy bits; (c) a comparator for issuing a compare signal if the (n-k) bits output by the set processor and by the second encoder are equal; (d) circuitry responsive to the compare signal to output as skew free the k bits as encoded by the second encoder; and (e) a reset circuit responsive to the compare signal to (i) send back from the processor to the receiver the union of sets A and B as a first-received vector for said next codeword and (ii) reset set B to an empty set.

6. The apparatus of claim 5, wherein the codewords are selected to provide a (t.sub.1,t.sub.2) skew-tolerant code in which: t.sub.1 is the preselected maximum number of transitions that may be missing from the current codeword when a transition arrives from said next codeword; and t.sub.2 is the preselected maximum number of transitions which may arrive from said next codeword before all of the transitions arrive from said current codeword; and at least one of the following conditions occurs for each arbitrary pair of codewords X and Y in the set: (a) min{N(X,Y), N(Y,X)}.gtoreq.t+1, or (b) min{N(X,Y), N(Y,X)}.gtoreq.1 and max{N(X,Y), N(Y,X)}.gtoreq.t.sub.1 +t.sub.2 +1, where t=min(t.sub.1,t.sub.2), and N(X,Y) is the number of coordinates in which X is 1 and Y is 0.

7. The apparatus of claim 5, wherein the codewords are constructed from a standard error-correcting code having sufficient word length to accommodate the number of information bits to be transmitted and also having a minimum distance between each arbitrary pair of codewords of (t.sub.1 +t.sub.2 +t+1).

8. The apparatus of claim 5, wherein both the first encoder and second encoder comprise: means for determining the weight of each of the ECC codewords and dividing said weight by the quantity (t.sub.1 +t.sub.2 +t+1) and generating the integer part thereof expressed in binary representation; and means for complementing the binary representation to produce said redundancy bits.