1.4)

a) (0,1,1,1) will not test for x1 stuck-at 0 because the value of x1 is 0
b) (1,1,1,1) will not test for x1 s-a-0 because the value of the correct
   circuit is 0 and the value of the faulty circuit is also 0
c) (1,1,0,1) will not test for x1 s-a-0 because the value of the correct
   circuit is 0 and the value of the faulty circuit is also 0
d) (1,0,1,0) will not test for x1 s-a-0 because the value of the correct
   circuit is 0 and the value of the faulty circuit is 0.


1.5) 

after some algebreic manipulation, the circuit becomes
                 __ __
f(x1,x2,x3,x4) = x1 x2 x3 x4

a) fault alpha: x3 s-a-0

Note that plugging x3=0 into f() yields f_alpha=0

so f XOR f_alpha = f.

So the tests for alpha are just the 1-points of f
T_alpha = {(0,0,1,1)}

b) fault beta: x2 s-a-0
         __
f_beta = x1 x3 x4              _________    ____________
                 __ __          __           __ __          __
f XOR f_beta =  (x1 x2 x3 x4) ( X1 x3 x4) + (x1 x2 x3 x4) ( X1 x3 x4) 

Using de'Morgan:
                __ __              __ __               __   __   __ 
f xor f_beta = (x1 x2 x3 x4) (x1 + x3 x4) + (x1 + x2 + x3 + x4) (x1 x3 x4)
               __
f xor f_beta = x1 x2 x3 x4

T_beta = { (0,1,1,1) }

c) fault gamma: x2 s-a-1

f_gamma = 0

f XOR f_gamma = f

T_gamma = T_alpha = {(0,0,1,1)}


1.6 b)

Circuit A)
      __ __         __
 f =  x1 x2 + x1 x2 x3

fault alpha: x2 s-a-1, x3 s-a-0

f_alpha = x1
                __ __      __   __        
f XOR f_alpha = x1 x2 + x1 x2 + x1 x2 + x3(x1 + x2)

T_alpha = {  (000) (100) (101) (010) (011) (111) }

Circuit B)
    __ __   __
f = x1 x2 + x3

f_alpha = 1
                _             
f XOR f_alpha = f  = (x1 + x2) x3

T_alpha = {(101)(011)(111)}


2.4)

              _   _
f = AB + CD + B + D

A) T = {(1,1,0,1)}

B) T = {(1,1,0,1)}

C) T = {(0,1,0,1)}

D) T = {(0,1,0,1)}


2.18)  Applying input (0,0,...,0) should produce output (1,0,0,...,0).  This will test for a stuck-at 1 fault on any of the inputs, for a stuck-at 1 fault on any but the first outputs, and for a stuck-at 0 fault on the first output.  Similarly, applying input (1,1,...,1) and testing for output (0,0,...,0,1) tests for a S-A-0 on any of the inputs, for a s-a-1 fault on any but the last outputs, and a s-a-0 fault on the outputs.  These two tests cover all possible faults on the inputs and the first and last outputs.  To test the remaining (S-A-0) faults on the outputs, we must attempt to make each output 1.  Thus the total set of tests is all 2^n possible inputs.  (So, the minimal set of tests is the same as just testing EVERYTHING).

2.19)  To test for a stuck-at fault on the output (Z) of a multiplexor, apply inputs y=(0,0,...,0) x=(1,1,...,1), and y=(0,0,...,0) x=(0,0,...,0) to test for a sa-0 and an sa-1 fault, respectively.  To test for all faults on the Y inputs, apply all 2^n binary inputs to the Y inputs, and all zeros to the X inputs except the one that corresponds to the number encoded in the y-inputs.  That way, if anything is stuck on the Y-inputs, Z will be 0 instead of 1.  Note that this test also tests for all stuck-at 0 faults on the x-inputs.  To test for all stuck-at 1 faults on the X-inputs, apply all 2^n binary inputs to the Y inputs, and all zeros to the X inputs.  The total set of tests is { (Y=(0,0,...,0)X=(1,1,...,1), Y=(0,0,...,0)X=(0,0,...,0,1), All possible Y and (0,0,...,1,...,0) where the only 1-entry in x corresponds to the value encoded in Y, All possible y and X=(0,0,...,0)}

3.20)  We didn't really go over this stuff in class, but here's my answer:


Here's the table I found based on the sequence:

      X
    0   1
  +---+---+
1 |2,0|3,0| 
2 |3,0|3,0|
3 |1,1|   |
  +---+---+

So a1=0, a2=0, a3=0, and a4=0

By the end of the sequence, we should be in state 3, so apply a 1 to see what the output of 3 is and then, two zeros to see what the state transition from 3 is:

remainder of checking sequence:

1  0  0
a1 a2 a3

here are the contingencies:

a1: output of state three, input 1
a2: if a2=1 then transition from 3 on input 1 is to state 3
a3: if a2=0 and a3=0 then transition from 3 on input 1 is to state 1
else if a2=0 and a3=1 then transitino from 3 on input 1 is to state 2


5.1) residue code, mod 3

0 1 0 1   1 0
   = 5    = 2

this is correct, 5 mod 3 = 2


0 1 1 1   1 0
  = 7     = 2

ERROR: 7 mod 3 = 1

clearly neither of the check bits are in error since 00 or 11 dont equal 1
The first info bit could not be in error, since 1 1 1 1 = 15 and 15 mod 3 = 0
the second info bit could not be in error, since 0 0 1 1 = 3 and 3 mod 3 = 0
the third info bit could be in error, since 0 1 0 1 = 5 and 5 mod 3 = 2
the fourth info bit could not be in error, since 0 1 1 0 = 6 and 6 mod 3 = 0

So, assuming a single-bit error, info bit 3 is incorrect, and the correct word is 0 1 0 1


0 1 1 0   0 1
 = 6      = 1

The last (check) bit could be in error since 6 mod 3 = 0

the last info bit could be in error since 0 1 1 1 = 7 and 7 mod 3 = 1
the third info bit could be in error since 0 1 0 0 = 4 and 4 mod 3 = 1
the second info bit could not be in error since 0 0 1 0 = 2 and 2 mod 3 = 2
the first info bit could not be in error since 1 1 1 0 = 15 and 15 mod 3 = 0

So either the second check bit, or the 4'th or 3'rd info bit is wrong


5.1 b) 7-bit hamming codes:

The following might be usefull: (here, + means XOR)

address:  000 001 010 011 100 101 110 111
bit:          c1  c2  i1  c3  i2  i3  i4

c1 + i1 + i2 + i4 = x
c2 + i1 + i3 + i4 = y
c3 + i2 + i3 + i4 = z

zyx = address of incorrect bit

A) 0 1 0 1 1 0 0
  (c c i c i i i)

X = 1
y = 1
z = 0

so the 3'rd bit, or i1 is wrong


B) 0 1 0 1 1 0 1
  (c c i c i i i)

X = 0
y = 0
z = 1

so the 4'th bit, or c3 is wrong

C) 0 1 1 1 1 0 1
  (c c i c i i i)

x = 1
y = 1
z = 1

so the 7'th bit, or i4 is wrong