Proof of code unique decipherability condition

From: Kevin Saff (google.com_at_kevin.saff.net)
Date: 09/28/04 

Date: Tue, 28 Sep 2004 15:55:45 GMT

I'm working my way through Robert B. Ash's _Information_Theory_ (Dover, ISBN
0-486-66521-6) and I found his proof of the condition for a code's unique
decipherability, as he himself admits, "somewhat cumbersome". He suggests
there is a cleaner proof by Sardinas and Patterson using semigroups:

Sardinas, A.A. and G.W. Patterson (1950), A Necessary and Sufficient
Condition for Unique Decomposition of Coded Messages, /Research Division
Report/ 50-27, Moore School of Electrical Engineering, University of
Pennsylvania, Pa.

-or- (presumably an easier to find copy/revision)

Sardinas, A.A. and G.W. Patterson (1953), A Necessary and Sufficient
Condition for Unique Decomposition of Coded Messages, /IRE Convention
Record/ Part 8, 104-108.

I haven't tracked either down yet. Does anyone know a reference for a good
proof of this theorem?

The theorem states that a code is uniquely decipherable iff after definining
the sets S_n as follows, no S_n != S_0 contains a code word.

Let S_0 be the set of code words.
Let S_1 be all A s.t. VA = W, where V and W are code words (in S_0).
Let S_n be {all A s.t. there exists WA in S_n-1 so that W in S_0}
    U {all A s.t. there exists B in S_n-1 so that BA is in S_0} 

-- 
+---- Kevin C. Saff ----+   F-15 |   |Eagle
| Engineer in St. Louis |   _____|_^_|_____
| Tracking/Fleet Support|   * + [_(x)_] + *