Need assitance understanding Sardinas-Patterson algorithm (Algorithm and example provided)

Question

I am having difficulty understanding Sardinas- Patterson algorithm from the below slide:

How do we get C1 and C2???

I also got this information from the internet:

The algorithm is finite because all dangling suffixes added to the list are suffixes of a finite set of codewords, and a dangling suffix can be added at most once.

• { 0, 01, 11 }. The codeword 0 is a prefix of 01, so add the dangling suffix 1. { 0, 01, 11, 1 }. The codeword 0 is a prefix of 01, but the dangling suffix 1 is already in the list; the codeword 1 is a prefix of 11, but the dangling suffix 1 is already in the list. There are no other dangling suffixes, so conclude that the set is uniquely decodable.
• { 0, 01, 10 }. The codeword 0 is a prefix of 01, so add the dangling suffix 1 to the list. { 0, 01, 10, 1 }. The codeword 1 is a prefix of 10, but the dangling suffix 0 is a codewords. So, conclude that the code is not uniquely decodeable.

Answer 1

The wiki article is a great explanation

The C in your slide correspond to the S_i from the wiki article.

Here is description from me:

The important operation is taking two strings from C and if one of them is a prefix to the other you and to record the suffix that is left when the prefix is removed. This is how C₁ is obtained.

With the following C₂, C₃, etc. You again want to look for words from C which are prefixes to words from C_i and take the remaining suffix, but you also want to look at the words from C_i and remove and words from C which are prefixes. C_(i+1) is the union of those sets.

As soon as some C_i contains a word from C you know the code is not uniquely decodeable.

So:

C = 1, 011, 01110, 1110, 10011

C₁ = 110 (because (1)110 is in C), 0011 (because (1)0011 is inC), 10 (because (011)10 is in C)

C₂ = {10 (because (1)10 is in C₁), 0 (because (1)0 is in C₁)} union { 011, because (10)011 is in C }

Answer 2

C1 is found by seeing if any code word in C is a prefix of any other code word in C, if it is then the suffix is added to the set C1. e.g. 1 is a prefix of 1110 and hence you get the suffix 110 which is added to C1.

For C2, first you check to see if the code words in C is a prefix of any other code word in C1 if it is then make a set of all the "dangling suffix" , you then check if C1 is a prefix of any code words in C if it is then again make a set of all the "dangling suffix". Then you take the union of those two sets which results in C2.

Hopefully that kinda made sense.

Answer 3

The sets C1 and C2 correspond to S1 and S2 in this Wikipedia article.

Specifically, C1 is the set of words that can remain after we take a single word from C and remove some its prefix that is also in C.

For C2 we have the words that can remain after we take a word from C and remove a prefix from C1, or after we take a word from C1 and remove a prefix from C.

If we wanted to compute C3, we would take the words that can remain after we take a word from C and remove some its prefix that is in C2, and the words that can remain after we take a word from C2 and remove some its prefix that is in C.

Thus, C3 would be: {[empty word], 0, 011, 10, 11, 1110}. It contains the empty word, so the algorithm halts and determines that C is not uniquely decodable.