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 fine 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 find 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 affected: 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 affected: 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 affected: 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 differ 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 affected: 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 affected: 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 affected: 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 differ 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 affected: 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 affected: 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 affected: 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 differ 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 different results. Nevertheless,
the results of no-shift and one-bit shift calculations will be the same in two cases
(difference 0 and difference ±2
i
).
7
Solution 7.1. A parity code can detect single-bit errors and multiple-bit errors
which affect an odd number of bits.
• If an odd number of bits is affected, 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-flip 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-flip errors, as long as no
one-to-zero bit-flip 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
