Cryptography Reference
In-Depth Information
9.1.1 Parity check code
Definition
A parity equation, represented graphically by Figure 9.1, is an equation linking
n
binary data to each other by the
exclusive or
, denoted
⊕
operator. It is satisfied
if the total number of 1s in the equation is even or null.
Figure 9.1 - Graphic representation of a parity equation.
The circles represent the binary data
c
i
, also called
variables
. The rectangle con-
taining the
exclusive or
operator represents the parity equation (also called the
parity constraint, or parity). The links between the variables and the operator
indicate the variables involved in the parity equation.
Parity code with three bits
We consider that the binary variables
c
1
,
c
2
and
c
3
are linked by the parity
constraint
c
1
⊕
c
3
=0
, and that they make up the codeword
(
c
1
,c
2
,c
3
)
.We
assume that we know the log likelihood ratio (LLR)
L
(
c
1
)
and
L
(
c
2
)
of variables
c
1
and
c
2
: what can we then say about the LLR
L
(
c
3
)
of variable
c
3
?
We recall that
L
(
c
j
)
is defined by the equation:
L
(
c
j
)=ln
Pr
(
c
j
=1)
Pr
(
c
j
=0)
c
2
⊕
(9.1)
There are two codewords in which bit
c
3
is equal to 0: codewords (0,0,0) and
(1,1,0). Similarly, there are two codewords in which bit
c
3
is equal to 1: code-
words (1,0,1) and (0,1,1). We deduce from this the following two equations in
the probability domain:
Pr
(
c
3
=1)=
Pr
(
c
1
=1)
×
Pr
(
c
2
=0)+
Pr
(
c
1
=0)
×
Pr
(
c
2
=1)
(9.2)
Pr
(
c
3
=0)=
Pr
(
c
1
=0)
×
Pr
(
c
2
=0)+
Pr
(
c
1
=1)
×
Pr
(
c
2
=1)
Using the expression of each probability according to the likelihood ratio func-
tion, deduced from Equation (9.1):
⎧
⎨
exp(
L
(
c
j
))
1+exp(
L
(
c
j
))
Pr
(
c
j
=1)=
⎩
1
1+exp(
L
(
c
j
))
Pr
(
c
j
=0)=1
−
Pr
(
c
j
=1)=
