1,050 views
2 votes
2 votes
A block of bits with $n$ rows and $m$ columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an expression for the probability that the error will be detected.

2 Answers

0 votes
0 votes
$\frac{(n^2-1)*(m^2-1)}{(n*m)(n*m-1)(n*m-2)(n*m-3)}$
0 votes
0 votes
Describe an error pattern as a matrix of n rows by k columns. Each of the
correct bits is a 0, and each of the incorrect bits is a 1. With four errors per
block, each block will have exactly four 1s. How many such blocks are
there? There are nk ways to choose where to put the first 1 bit, nk − 1 ways
to choose the second, and so on, so the number of blocks is
nk(nk − 1)(nk − 2)(nk − 3). Undetected errors only occur when the four 1
bits are at the vertices of a rectangle. Using Cartesian coordinates, every 1 bit
is at a coordinate (x, y), where 0 ≤ x < k and 0 ≤ y < n. Suppose that the bit
closest to the origin (the lower-left vertex) is at (p, q). The number of legal
rectangles is (k − p − 1)(n − q − 1). The total number of rectangles can be
found by summing this formula for all possible p and q. The probability of an
undetected error is then the number of such rectangles divided by the number
of ways to distribute the 4 bits:

k-2     n-2
Σ        Σ     (k − p − 1)(n − q − 1)

p =0   q=0

------------------------------------------------------------

nk(nk-1)(nk-2)(nk-3)

Related questions

1 votes
1 votes
0 answers
1
go_editor asked Jun 1, 2016
512 views
A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source...
16 votes
16 votes
1 answer
3
go_editor asked Jun 1, 2016
1,660 views
A system has $4$ processes $A$, $B$, $C$, $D$ and $5$ allocatable resources $R_1, \: R_2,\: R_3, \: R_4,\: R_5$. The maximum resource requirement for each process and its...