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

Test Patterns for Parity Networks

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

Publishing Venue

IBM

Related People

Bossen, DC: AUTHOR [+3]

Abstract

The generation of tests for parity networks is a difficult task with existing general procedures. The following procedure rapidly and easily generates the minimum number of test patterns which will perform a functional test on every (Exclusive-OR) EX-OR gate in the arrangement. The number of tests required is 2/k/-1 where k is the maximum number of inputs to any EX-OR gate in the network. The procedure for generating tests uses the sequences that appear at each mode in the network. These sequences are taken from a Maximum Length Shift Register Code (MLSRC). The sequence W(i + 1) is a cyclic shift of the sequence W(i) for all i mode 2/k/-1.

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

Page 1 of 3

Test Patterns for Parity Networks

The generation of tests for parity networks is a difficult task with existing general procedures. The following procedure rapidly and easily generates the minimum number of test patterns which will perform a functional test on every (Exclusive-OR) EX-OR gate in the arrangement. The number of tests required is 2/k/-1 where k is the maximum number of inputs to any EX-OR gate in the network. The procedure for generating tests uses the sequences that appear at each mode in the network. These sequences are taken from a Maximum Length Shift Register Code (MLSRC). The sequence W(i + 1) is a cyclic shift of the sequence W(i) for all i mode 2/k/-1.

It is assumed that the Exclusive-OR network is constructed in the form of a tree by connecting m-input EX-OR gates where m may be any number such that m </- k. The test pattern generation algorithm has the following five steps:

1) Select any vector W(i) from a MLSRC of length 2 -1 as the output of the network.

2) Label the inputs to the last EX-OR as W(i+1), W(i+2),..., W(i+m+1), and W(1)W(i+1) --. W(i+m-1.)

3) Trace each of the above inputs back to the driving gate with the same vector. Repeat steps 1) and 2) to determine the proper inputs to the corresponding gates.

4) The vectors at the input lines to the EX-OR tree are then the test input vectors with the correct output as W(i).

5) An additional all 0 pattern as input to the network with 0 as correct output completes the test.

The test patterns, generated by the above algorithm provide a complete test for each EX-OR gate in the parity check tree.

Furthermore, any single gate failure will generate an erroneous sequence which will propagate to the output. This is due to the linearity of an EX-OR gate. Suppose one of its inputs is the sequence W(1) with a corresponding correct output sequence W(2). If the input W(1) is changed by an error vector W(1)+e, then the corresponding output is W(2)+ e. Clearly, the error will appear superimposed on the observed network output.

The test pattern generation pro...