# An example of a code that is neither p-code or s-code but is uniquely decodable?

As the title says, code can't be a prefix-code and can't be a suffix-code, but it must be uniquely decodable. One possible code is this: {1, 101, 1001, ... }. Number of zeroes corresponds to the index of the letter in a given alphabet (starting from 0). Clearly it's not p-code and not a s-code and it's uniquely decodable. But I need to find another example of such code. And no, I wont accept {0, 010, 0110, ...}. By the way, code words must consist of 0 and 1, i.e. be binary.

• What did you try? What research did you do to try to find an answer yourself? – David Richerby Nov 11 '14 at 19:40
• I tried thinking and I tried googling. Doubt that this answer was of any use to you. But this might be useful, I just remembered an example of one possible code my prof. gave. I will edit the question – Guest Nov 11 '14 at 19:44

An easy way to get new codes of any size is to compose a prefix non-suffix code and a suffix non-prefix code. For instance, start with the prefix non-suffix code $X_5 = \{0, 10, 110, 1110, 1111\}$ and compose it with the suffix non-prefix code $\{0,01\}$, which consists to replace $1$ by $01$ in $X_5$ to get $$S_5= \{0, 010, 01010, 0101010, 01010101\}.$$ The resulting set is a code that is neither prefix nor suffix.

N.B. The advantage of this method is that you always get codes, no verification needed.

• Why do you replace 1 with 01 rather than concatenating (i.e. taking the cartesian product)? Also I'm sure this is obvious, but I actually came here trying to find help proving that the product of two prefix codes is itself a prefix code, as well as the prefix/suffix composition you describe. Are there any resources you could point me to? – jberryman Apr 2 '17 at 3:46
• Oh so this sort of composition is described in ch. 6 Berstel and Perrin's Theory of Codes. And what we're really doing is for each letter in X5's alphabet, substituting a corresponding codeword from the other code ({0,01}), so there's a redundant 0 for 0 mapping going on in the example above. They claim this mapping must be a bijection but it seems to me it only needs to be injective-only – jberryman Apr 15 '17 at 0:15

These lecture notes suggest that 0, 01, 011, 1110 is such an example. An even simpler example is (presumably, I didn't check) 0, 01, 110.

This link came up as the first result for the search uniquely decodable code examples on a popular search engine.

• How would this code look if I wanted to code alphabet of n symbols? This shows a code only for 4 symbols. – Guest Nov 11 '14 at 21:59
• I'm sure if you try hard you can generalize this example to $n$ symbols, the way I generalized it (conjecturally) to 3. But to know for sure that it works, you'll have to prove that these codes are actually uniquely decodable. – Yuval Filmus Nov 11 '14 at 22:11