Browse Prior Art Database

Totally Self Checking Error Checker for a K out of N Coded Data

IP.com Disclosure Number: IPCOM000079212D
Original Publication Date: 1973-May-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 4 page(s) / 44K

Publishing Venue

IBM

Related People

Carter, WC: AUTHOR

Abstract

The design of self-checking error checkers for K out of N coded data is generally known. Thus, in U. S. Patent 3,559,168, there is disclosed a self-checking error checker for K out of N coded data if the failure class considered is that comprising circuit lines, which are stuck at one (s-a-1) or stuck at zero (s-a-0). Other frequently used failure assumptions are logic gate inputs s-a-1 or s-a-0, logic gate outputs s-a-1 or s-a-0, and circuit inputs s-a-1 or s-a-0.

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

Page 1 of 4

Totally Self Checking Error Checker for a K out of N Coded Data

The design of self-checking error checkers for K out of N coded data is generally known. Thus, in U. S. Patent 3,559,168, there is disclosed a self- checking error checker for K out of N coded data if the failure class considered is that comprising circuit lines, which are stuck at one (s-a-1) or stuck at zero (s-a- 0). Other frequently used failure assumptions are logic gate inputs s-a-1 or s-a-0, logic gate outputs s-a-1 or s-a-0, and circuit inputs s-a-1 or s-a-0.

Employing the latter assumptions, there is described in the publication of D.
A. Anderson and G. Metze, "Design of Totally Self-Checking Check Circuits for K out of N Codes", 1972 International Symposium on Fault-Tolerant Computing, the proof that the wider failure assumptions are satisfied only if N = 2K, i.e., K out of 2K. In this Anderson, Metze publication there is also disclosed translation circuits to translate K out of N codes to 1 out of C/N/(K) codes, which are translated to the K out of 2K code. However, the translation circuits disclosed in the Anderson, Metze paper are quite unwieldy, using at least C/N/(K) extra circuits, when their method is valid.

There are, accordingly, described herein translation circuits which replace those described in the Anderson, Metze publication, and essentially comprise one or two gates which are added to the circuits disclosed in the aforementioned
U. S. Patent 3,559,168.

It is, of course, to be realized that a K out of N code represents data in N-bit bytes, each byte containing K 1's and (N-K) 0's. In the self-testing checkers described herein, the hits of the coded bytes are divided into two groups, viz.

A,B. Any division can be used, provided that each group contains at least one hit, although it has been found that the resulting circuit is generally simpler if the groups are approximately the same size. If they are unequal, the larger group is designated A. The number of bits in each group is designated as N(A), N(B). Thus, N(A) + N(B) = N (total number of bits in the code) and N(A) >/- N(B).

Each checker is designed such that, for valid code, it gives one value of its output, such as for example 01, when there is an even number of 1's in group A and the other value (10) when there is an odd number of 1's in group A. If the number of 1's in the entire code exceeds K, the output value assumes one of its error values, such as 11 for example. If the number of 1's is less than K, it assumes the other error value 00. The number of 1's occurring in each group is designated K(A), K(B). Thus, K(A) + K(B) = K for valid codes.

Each checker consists of two independent logic networks, each network having a single output whose values are referred to as c(1), c(2). The checkers employ "greater than" detection networks as follows:

(Image Omitted)

The cases considered have K </- N/2, as otherwise the circuit for K(1) = N - K is designed and complemented.

It is easy to prove...