Browse Prior Art Database

Decision Procedure

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

Publishing Venue

IBM

Related People

Bakis, R: AUTHOR

Abstract

In this pattern recognition system, patterns consisting of binary digits are compared to reference patterns. For each character of the alphabet, there is a reference pattern made up of as many digits as there are binary digits in the unknown character. The digits in the reference pattern need not be binary, however. For example, they can be 3-valued. Assume that the digits in the pattern to be recognized can assume the values either 1 or 0 while those in the reference pattern can have the values 0, 1, or x.

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

Page 1 of 4

Decision Procedure

In this pattern recognition system, patterns consisting of binary digits are compared to reference patterns. For each character of the alphabet, there is a reference pattern made up of as many digits as there are binary digits in the unknown character. The digits in the reference pattern need not be binary, however. For example, they can be 3-valued. Assume that the digits in the pattern to be recognized can assume the values either 1 or 0 while those in the reference pattern can have the values 0, 1, or x.

Now assume that the comparison is to be done by means of a distance. This is defined as the number of mismatches between the reference pattern and the unknown. An x in the reference pattern is not compared to the unknown, and cannot cause a mismatch. If some reference pattern contains a large number of x's, then the distance of any arbitrary pattern from it is likely to be less than from some other reference pattern which contains only a small number of x's. This procedure provides a method of overcoming this difficulty. Namely, a constant is added to each distance. This constant does not depend on the unknown pattern but only on the reference pattern. Thus, each reference pattern can be given a different constant, possibly depending on the number of x's in that pattern. The derivation of the correction constant is as follows. Bayes's Decision.

Let P(C(j)) be the a priori probability of character C(j). Let P(M(i) IC(j)) be the conditional probability of the measurement vector M(i), given the character C(j). According to the classical Bayes's formula, the a posteriori conditional probabilities for the characters C(j), given measurement vector M(i), are

(Image Omitted)

Since the denominator on the right-hand side of (1) is independent of j, this denominator can be ignored when only the relative magnitudes of P(C(j)/)M(i)) as a function of j are needed. Let these unnormalized probabilities be designated by p(C(j)/M(i)), so that

(Image Omitted)

Now assume that for every C(j) the components of the measurement vector are distributed independently, so that P(M(j)I C(j)) can be written as a product Here, m(hi) is the value of the h-th component of M(i). Substituting from (3) into
(2), and taking the logarithm of both sides of the resulting equation, there is obtained Ternary Minimum Distance Decision The ternary distance is defined by

(Image Omitted)

Here, a h(j) is the ternary weight for the h-th component in the reference pattern for the j-th character. It can take on the values -1, 0, or +1. The quantity m(hi) is the value of the h-th component in the measurement vector i. The m(hi) can assume the values 0 or 1. The additive constant b(j) is equal to the number of components ahj which are equal to -1 for the given value of j.

1

Page 2 of 4

In the language used here, the a(hi) are the components of the j-th ideal. A don't-care corresponds to a(hj) = 0. A one means a(hj) = -1, and a zcro is a(hj) = +1. The b(j) is e...