1

Solution 1.1. R = R

1

R

2

R

3

et R

dup

= [1−(1−R

1

)

2

][1−(1−R

2

)

2

][1−(1−R

3

)

2

]

2

Solution 2.1. R = R

1

R

2

R

3

et R

dup

= [1 − (1 − R

1

R

2

R

3

)

2

]

3

Solution 3.1. The obtained expressions show that ﬁne grain redundancy leads

to higher reliability.

4

Solution 4.1.

x

1

x

2

x

3

ξ(x)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

with x = {x

1

, x

2

, x

3

}

The path vectors are (011), (101), (110) and (111).

The minimal path vectors are (011) (101) and (011).

Then, the state function is:

ξ(x) = 1 − (1 − x

1

x

2

)(1 − x

2

x

3

)(1 − x

1

x

3

)

= 1 − (1 − x

1

x

2

)(1 − x

1

x

3

− x

2

x

3

+ x

1

x

2

x

3

)

= 1 − (1 − x

1

x

3

− x

2

x

3

+ x

1

x

2

x

3

− x

1

x

2

+ x

1

x

2

x

3

+ x

1

x

2

x

3

− x

1

x

2

x

3

)

= x

1

x

3

+ x

2

x

3

+ x

1

x

2

− 2x

1

x

2

x

3

The general expression of the reliability is R = R

1

R

3

+ R

2

R

3

+ R

1

R

2

+

2R

1

R

2

R

3

If all modules have the same reliabilty R

M

, it becomes R = 3R

2

M

− 2R

3

M

.

Another way to ﬁnd this expression is noting that the system functions for

the case when all modules function (this leads to R

3

) and for the three cases

when two modules function and one module fails (this leads to 3(1 − R

M

)R

2

M

):

R = R

3

M

+ 3(1 − R

M

)R

2

M

= R

3

M

+ 3(R

2

M

− R

3

M

)

= 3R

2

M

− 2R

3

M

1

Solution 4.2. R = (3R

2

M

− 2R

3

M

)R

v

R ≥ R

M

⇒ (3R

2

M

− 2R

3

M

)R

v

≥ R

M

(3R

M

− 2R

2

M

)R

v

≥ 1

R

v

≥

1

3R

M

− 2R

2

M

5

Solution 5.1. Yes. Because both functions are self-dual.

Solution 5.2. f

sd

= x

n+1

f(x

1

, · · · , x

n

) + x

n+1

f(x

1

, · · · , x

n

)

6

Solution 6.1. There are three cases.

• The sum bit s

i

is aﬀected: the addition

ˆ

S = S − 2

i

if faulty ˆs

i

= 0 or

ˆ

S = S + 2

i

if faulty ˆs

i

= 1

• The carry-out bit c

i+1

is aﬀected: the addition

ˆ

S = S − 2

i+1

if faulty

ˆc

i+1

= 0 or

ˆ

S = S + 2

i

if faulty ˆc

i+1

= 1

• Both sum bit s

i

and c

i+1

are aﬀected: there are four possibilities:

ˆc

i+1

ˆs

i

ˆ

S = S

0 0 −3 × 2

i

0 1 −2

i

1 0 2

i

1 1 3 × 2

i

So the result will diﬀer of one of the values 0, ±2

i

, ±3 × 2

i

, ±2

i+1

Solution 6.2. There are three cases.

• The sum bit is aﬀected: the addition

ˆ

S = S − 2

i−1

if faulty ˆs

i

= 0 or

ˆ

S = S + 2

i−1

if faulty ˆs

i

= 1

• The carry-out bit is aﬀected: the addition

ˆ

S = S − 2

i

if faulty ˆc

i+1

= 0 or

ˆ

S = S + 2

i

if faulty ˆc

i−1

= 1

• Both sum bit s

i−2

and c

i−1

are aﬀected: there are four possibilities:

ˆc

i+1

ˆs

i

ˆ

S = S

0 0 −3 × 2

i−1

0 1 −2

i−1

1 0 2

i−1

1 1 3 × 2

i−1

2

So the result will diﬀer of one of the values 0, ±2

i−1

, ±3 × 2

i−1

, ±2

i

Solution 6.3. There are three cases.

• The sum bit is aﬀected: the addition

ˆ

S = S − 2

i−2

if faulty ˆs

i

= 0 or

ˆ

S = S + 2

i−2

if faulty ˆs

i

= 1

• The carry-out bit is aﬀected: the addition

ˆ

S = S − 2

i−1

if faulty ˆc

i+1

= 0

or

ˆ

S = S + 2

i−1

if faulty ˆc

i−1

= 1

• Both sum bit s

i−2

and c

i−1

are aﬀected: there are four possibilities:

ˆc

i+1

ˆs

i

ˆ

S = S

0 0 −3 × 2

i−2

0 1 −2

i−2

1 0 2

i−2

1 1 3 × 2

i−2

So the result will diﬀer of one of the values 0, ±2

i−2

, ±3 × 2

i−2

, ±2

i−1

We can conclude that to detect the errors, we must consider two bit shift

because one bit shift is not enough. Indeed, except when both results are exact,

no-shift and two-bit shift calculations will lead to diﬀerent results. Nevertheless,

the results of no-shift and one-bit shift calculations will be the same in two cases

(diﬀerence 0 and diﬀerence ±2

i

).

7

Solution 7.1. A parity code can detect single-bit errors and multiple-bit errors

which aﬀect an odd number of bits.

• If an odd number of bits is aﬀected, then the number of 1’s in a codeword

changes from even to odd (for an even parity code) or from odd to even

(for an odd parity code).

A parity code can only detect errors, but it cannot correct them, since the

position of the erroneous bit(s) is not possible to locate.

• For example, suppose that we use an even parity code to protect the trans-

mission of 5-bit data. If we receive the word [110100], then we know that

an error has occurred. However, we do not know which codeword has been

sent. If we assume that a single-bit error has occurred during the trans-

mission, then it is equally likely that one of the six codewords [010100],

[100100], [111100], [110000], [110110], or [110101] has been sent.

Solution 7.2. The decision depends on which type of all-bits error is more

probable.

For even parity - the parity bit for the all zeroes data word will be 0 and an

all-0’s failure will go undetected - it is a valid codeword.

3

Selecting the odd parity code will allow the detection of the all-0’s failure.

If all-1’s failure is more likely - the odd parity code must be selected if the

total number of bits (d + 1) is even, and the even parity if d + 1 is odd

Solution 7.3.

Solution 7.4.

8

Solution 8.1. Berger codes can detect any number of one-to-zero bit-ﬂip errors,

as long as no zero-to-one errors occurred in the same code word. Similarly,

Berger codes can detect any number of zero-to-one bit-ﬂip errors, as long as no

one-to-zero bit-ﬂip errors occur in the same code word. Berger codes cannot

correct any error.

9

Note there was an error on matrix G (see bold values)!

G =

1 0 0 0 1 1

0 1 0 1 0 1

0 0 1 1 1 0

Solution 9.1. We note that G = [I

k

A], then we can get H = [A

T

I

n−k

]

H =

0 1 1 1 0 0

1 1 0 0 1 0

1 0 1 0 0 1

4