Browse Prior Art Database

Linear Recoverable Superimposed Codes

IP.com Disclosure Number: IPCOM000095113D
Original Publication Date: 1965-Sep-01
Included in the Prior Art Database: 2005-Mar-07
Document File: 6 page(s) / 30K

Publishing Venue

IBM

Related People

Chien, RT: AUTHOR [+2]

Abstract

A common problem in data processing contexts is as follows: Let V(max) be a (finite) set and D a (finite) collection of subsets of V such that d D absolute d absolute * = b. Let q be a distinguished subset of V such that absolute q absolute /- q.

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 22% of the total text.

Page 1 of 6

Linear Recoverable Superimposed Codes

A common problem in data processing contexts is as follows:

Let V(max) be a (finite) set and D a (finite) collection of subsets of V such that d D absolute d absolute * = b. Let q be a distinguished subset of V such that absolute q absolute </- b. Find a notation and an algorithm suitable for efficient automatic processing which enables one to represent the elements of D and decide, for each epsilon D, whether d >/- q.

A typical case of this problem is that in which V corresponds to a vocabulary of index terms and D to a collection of indexed documents. The term q then corresponds to a query, a set of index terms required to be present in the d for any desired document. For purposes of illustration, the problem is discussed relative to the area of document retrieval.

Three commonly encountered solutions to the problem as posed involve:

(i) Straightforward listing of some representation of the elements of each subset, d, and of q. The list corresponding to a given d is compared with that corresponding to q to determine if q </- d.

(ii) The listing, for each v epsilon V, of all subsets d such that v epsilon d. The intersection of the listings corresponding to all epsilon q then produces the desired d's. This is sometimes called an inverted file solution.

(iii) Representation of the elements of V by prime numbers, and of q and the elements of D by the appropriate products of primes. Then, q </- d if and only if the composite number representing q divides the composite representing d.

A fourth solution, which does not in general meet the constraints of the problem as posed here, proceeds by:

(iv) Choosing a binary m-tuple representation for each element of V and representing each subset d by the component-wise Boolean * absolute s absolute denotes the cardinality of s. union of the appropriate elements of V. With this approach, known as superimposed coding, a decision cannot usually be made from comparing the resulting representations of q and d whether d >/- q. There can be elimination or a subset of the cases q a d and acceptance of all others or testing further using some other representation.

The third solution listed, differs philosophically from the other in that an algebraic structure, the integers, is chosen whose algebraic relationships reflect the logical relationships inherent in the data. The elements of this algebraic structure are then used to represent the data. Processing of the data is carried out through algebraic manipulation of its representation. It is the same philosophy which underlies the solution here, although the present solution is mathematically more similar to the fourth solution. Recoverable Linear Superimposed Coding.

1

Page 2 of 6

The elements of V are represented by binary m-tuples, and the elements of d by mod-2 linear combinations of these m-tuples. Since the set of all such m- tuples is a vector space over GF (2), such linear combinations are well-defined. In o...