200
12 Cryptocurrencies
Fig. 12.1 A generic communication system with message source, encoder, transmission channel,
decoder, and receiver. The encoder produces a data stream of symbols x i with probabilities p i . This
stream is then corrupted by noise, parameterized by ε, on its way to the decoder
Fig. 12.2 Binary symmetric channel (bitflip channel) where the input symbols “1” and “0” (red)
are perturbed by flipping the bits with probability ε before they are received by the decoder using
the same symbols (magenta or almost red)
know that the transmitted stream originates from an encoder with uncertainty H [x],
by how much the uncertainty about x i is reduced by observing y j ? And under what
circumstances can we even restrict it to a single choice—the “real” value that was
transmitted. It should be apparent that the answer is buried in the probabilities that
one or the other alternative shows up in the decoder. Historically, all concepts were
developed in [2], but we loosely follow the modern discussion in [9].
Therefore, let us analyze the channel described in Fig. 12.2 in parallel to the
theoretical considerations. The encoder is characterized by the probabilities of the
symbols “1” and “0,” which can be read off from the figure as p x (1) = 1 − α and
p x (0) = α. Moreover, the channel is described by the conditional probabilities
p yx (y j |x i ), which describe the probabilities that a symbol y j is received, provided
that x i was transmitted. Reading off from Fig. 12.2, we find
p yx (1|1) p yx (1|0)
p yx (0|1) p yx (0|0)
=
1 − ε ε
ε 1 − ε
.
(12.8)
Note that we need the subscript on p as a marker to distinguish the probability
p yx (y j |x i ) of y j conditioned on x i , from the probability p xy (x i |y j ) of finding x i ,
conditioned on y j .
As a further refinement, we link the encoder, characterized by α, to the channel
by introducing the joint probability p xy (x i , y j ) of an event that that x i and y j occur
simultaneously. It can be expressed as
p xy (x i , y j ) = p yx (y j |x i ) p x (x i ) .
(12.9)
12 Cryptocurrencies
Fig. 12.1 A generic communication system with message source, encoder, transmission channel,
decoder, and receiver. The encoder produces a data stream of symbols x i with probabilities p i . This
stream is then corrupted by noise, parameterized by ε, on its way to the decoder
Fig. 12.2 Binary symmetric channel (bitflip channel) where the input symbols “1” and “0” (red)
are perturbed by flipping the bits with probability ε before they are received by the decoder using
the same symbols (magenta or almost red)
know that the transmitted stream originates from an encoder with uncertainty H [x],
by how much the uncertainty about x i is reduced by observing y j ? And under what
circumstances can we even restrict it to a single choice—the “real” value that was
transmitted. It should be apparent that the answer is buried in the probabilities that
one or the other alternative shows up in the decoder. Historically, all concepts were
developed in [2], but we loosely follow the modern discussion in [9].
Therefore, let us analyze the channel described in Fig. 12.2 in parallel to the
theoretical considerations. The encoder is characterized by the probabilities of the
symbols “1” and “0,” which can be read off from the figure as p x (1) = 1 − α and
p x (0) = α. Moreover, the channel is described by the conditional probabilities
p yx (y j |x i ), which describe the probabilities that a symbol y j is received, provided
that x i was transmitted. Reading off from Fig. 12.2, we find
p yx (1|1) p yx (1|0)
p yx (0|1) p yx (0|0)
=
1 − ε ε
ε 1 − ε
.
(12.8)
Note that we need the subscript on p as a marker to distinguish the probability
p yx (y j |x i ) of y j conditioned on x i , from the probability p xy (x i |y j ) of finding x i ,
conditioned on y j .
As a further refinement, we link the encoder, characterized by α, to the channel
by introducing the joint probability p xy (x i , y j ) of an event that that x i and y j occur
simultaneously. It can be expressed as
p xy (x i , y j ) = p yx (y j |x i ) p x (x i ) .
(12.9)