GALLAGER: PERSPECTIVE ON MULTIACCESS CHANNELS
121
of (N, M, L) codes where each code word x,, 1 I m I M,
is independently selected according to the probability as-
signment
Q,(x)
= jfil
Q,txn>,
x = (X1,X2,“‘,
XN) (2.6)
and each code word w,, 1 I I I L is independently selected
according to
N
Q,(w) = Ii Q,twn)~
w = (w,,-,w,). (2.7)
n=l
For each code in the ensemble, the decoder uses maximum
likelihood decoding, and we want to upper bound the
expected value p, of P, for this ensemble. Define an error
event to be of type 1 if the decoded pair (I%, 1) and the
original source pair (m, Z) satisfy riz # m, i = 1. An error
event is type 2 if h = m and i # 1, and is of type 3 if
riz # m and ? # 1. Let Pei, 1 I i I 3, be the probability,
over the ensemble, of a type i error event; obviously
Fe = P,, + Pe2 + Pe3.
Taking the expected value of (2.11) over w, and then using
the product form of Q,,. Q2, and P again,
Cl s exp[~NR,l
~Q,(x)P(ylx~)“(‘+~) l-+’
I 1
N
x
(2.12)
Consider Pe3 first. Note that, when (m, I) enters the
encoder, there are M - 1 choices for riz and (L - 1)
choices for !, or (M - 1) (L - 1) pairs, that yield a type 3
error. For each such pair (riz, i), the code word pair xin, rq
is statistically independent of x,, w, over the ensemble of
codes. Thus, regarding (x, w) as a combined input to a
single input channel with input alphabet X
x
W, we can
directly apply the coding theorem [lo, Theorem 5.6.11
which asserts’ that, for all p, 0 I
p
I 1,
Applying the same argument to type 2 errors, for all
p,o 5 p I 1,
pe2 5 exp[~NR,l
~Q,(w)P(~Jxw)‘(‘+~) ‘+’ .
1
1
N
w
(2.13)
Pe3 I [(M - l)(L - l)] p
. c [ 1 Q,(x)Q,( w)P( ylx~)‘“~+“lIII.
(2.8)
Y
x,w
Putting (2.9), (2.12), and (2.13) in a form to emphasize
the exponential dependence on N, we have the following
theorem.
Theorem 2 (Slepian- Wolf): Consider an ensemble of
(N,M,L) codes in which {xl;..,xM} and {wI;~~,wL}
are independently chosen according to (2.6) and (2.7) for a
given probability assignment Q(xw) = QI(x)Q2(w). Then
the expected error probability over the ensemble satisfies
Using the product form of Q,, Q2, and P ((2.1), (2.6),
(2.7)), and the definition of rates in (2.2), this simplifies to
pe3 5 exd~N(R, +&)I
c Q,(x)Q,(w)P( JJ~xw)“(‘+~) I+’ .
I I
N
x,w
(2.9)
Next consider Pel, the probability that riz # m and I = i.
We first condition this probability on a particular message
1 entering the second encoder, and a choice of code with a
particular w, transmitted at the second input. Given w,, we
can view the channel as a single input channel with input
x, and with transition probabilities P( ylx,w,).
A maximum likelihood .decoder for that single input
channel will make an error (or be ambiguous) if
for at least one m * # m .
(2.10)
,l The statement of [lo, Theorem 5.6.11 assumes that all code words are
chosen independently, but the proof only uses pairwise independence
between the transmitted word (x, , W) and each other word ( xL , IV,-), P’+I #
m,i# I.
Since this event must occur whenever a type 1 error occurs,
the probability of a type 1 error, conditional on w[ being
sent, is upperbounded by the probability of error or
ambiguity on the above single input channel. Using [lo,
theorem 5.6.11 again for this single input channel, we have,
for anyp,O 5 p 5 1,
P [type 1 error I We]
I (M - 1)‘c xQ,(x)P( JJ)xw)“(‘+~)
[
1
l+P
. (2.11)
Y
*
Fe I P,, + P& + P&g
(2.14)
where
P,i I exp[-N[-PRi + Eoi<P,Q>]],
forallp,O<p<l,alli=1,2,3 (2.15)
In M
In L
R, = 7
R, = 7
R, = R, + R,
&,,<P,Q) =
(2.16)
I
l+P
-1n c Q,(w) ~Q,(-dPbl-d’(lfp’
(2.17)
Y3W
x
&<P,Q> =
1
l+P
-1n c Q,(x)
CQ2(w)P<~lxw)1”‘+P)
(2.18)
Y3X
w
&(P,Q) =
c Q,(x)Q,(w)P(ylx~)“(~+~)
1
l+P
. (2.19)
x,w