Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Error Recovery System

IP.com Disclosure Number: IPCOM000074136D
Original Publication Date: 1971-Mar-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 4 page(s) / 44K

Publishing Venue

IBM

Related People

Liu, CN: AUTHOR [+2]

Abstract

This is an encoding and decoding scheme which facilitates the detection of errors caused by simultaneous inputs of different code words and enables a useful output to be obtained if the simultaneously entered code words are from the same source neighborhood.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 4

Error Recovery System

This is an encoding and decoding scheme which facilitates the detection of errors caused by simultaneous inputs of different code words and enables a useful output to be obtained if the simultaneously entered code words are from the same source neighborhood.

Where analog information is converted into digital code words in order to provide input for a digital data processing system, there may be instances when two or more different code words are simultaneously entered into the system. For example, if a graphic input tablet is employed to generate input data, the stylus may pick up signals from several points in the coordinate grid mesh of the tablet. These points may be in the same neighborhood, that is, clustered around the tip of the stylus, or they may be separated by an appreciable distance. Where the pickup points are clustered together, it is generally satisfactory if one of these points can be arbitrarily chosen as the source and the other points ignored. However, if the points are separated from each other, this indicates that the stylus is picking up a spurious signal from a location other than the one at which it is positioned, and in this case there is no accurate way to identify one or the other of the input words as representing the true source, in the absence of additional information that usually is not available.

The present system utilizes a coding scheme which facilitates the detection of errors caused by plural simultaneous entries of code words and enables a useful output to be obtained if the simultaneously entered code words originated in the same source neighborhood. This coding scheme has the following attributes:

1) It is composed of code words having the same "weight", that is, the same number of 1's.

2) The code words are ordered in a sequence such that if two code words are of distance 1 in this sequence (i.e., if they are adjacent in the sequence), they differ from each other by exactly 2 bits.

3) If two code words are of distance d in this sequence, then they differ from each other by d(h), which is no less than the lesser of 2d and a certain specified integer, d(min). (I.e., d(h)>/- min [2d, dMin])

4) When code words in the same neighborhood (i.e., d < d(min)/2) are logically combined (OR'ed or AND'ed), the resulting word has a weight that differs by less than an amount d(min)/2 from the weight of a "pure" code word.

5) When code words which are from different neighborhoods (i.e., d >/- d(min)/2) are logically combined, the resulting code word has a weight that differs by at least d(min)/2 from the weight of a pure code word.

Attributes 4 and 5 are consequences of attributes 1, 2 and 3.

An exemplary encoding table is set forth on the next page. This coding scheme comprises 46 code words, each containing 14 bits, 7 of which are 1 s. Thus each pure code word has a weight of 7. Adjacent

1

Page 2 of 4

code words do not differ from each other by more than two bits. If any two code wo...