Browse Prior Art Database

Method for Constructing (t1,t2) Skew Detecting and Skew Tolerant Codes

IP.com Disclosure Number: IPCOM000109962D
Original Publication Date: 1992-Oct-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 2 page(s) / 50K

Publishing Venue

IBM

Related People

Blaum, M: AUTHOR [+2]

Abstract

Disclosed is a method to construct codes that can either detect or correct skew, with less redundancy in general than previously known codes (*). Skew is a condition that occurs when two consecutive messages are transmitted over a parallel asynchronous pipelined communication medium without acknowledgement, and elements of the second message arrive at the destination before the first message is completed. t1 is defined as the greatest number of elements of the first message which may be missing when the first element of the second message arrives; t2 is defined as the greatest number of elements of the second message which may arrive before the last element of the first message is received.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 68% of the total text.

Method for Constructing (t1,t2) Skew Detecting and Skew Tolerant Codes

       Disclosed is a method to construct codes that can either
detect or correct skew, with less redundancy in general than
previously known codes (*).  Skew is a condition that occurs when two
consecutive messages are transmitted over a parallel asynchronous
pipelined communication medium without acknowledgement, and elements
of the second message arrive at the destination before the first
message is completed.  t1 is defined as the greatest number of
elements of the first message which may be missing when the first
element of the second message arrives; t2 is defined as the greatest
number of elements of the second message which may arrive before the
last element of the first message is received.

      The procedure involves adding three tails to the information
bits: the first tail encodes the information bits into an
(n',k,2t1+2) error-correcting code, where n' is the length of the
code, k is the dimension and 2t1+2 the minimum distance; the second
tail will be described below; the third tail unorders the code in a
way analogous to the generalization of Berger's construction given in
[*].

      Consider the s+1 vectors of length s w0, w1, ... ,ws, where wi
is the vector with i 0's followed by s-i 1's.

      Consider the following matrix, denoted B(w,s), with w rows
u0,u1, w-1 and s columns: row ui is given by vector wj, where j is
congruent to i modulo s+1. Our construction is...