2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What did you try? What research did you do to try to find an answer yourself? $\endgroup$ – David Richerby Nov 11 '14 at 19:40
  • $\begingroup$ 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 $\endgroup$ – Guest Nov 11 '14 at 19:44
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – jberryman Apr 2 '17 at 3:46
  • $\begingroup$ 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 $\endgroup$ – jberryman Apr 15 '17 at 0:15
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How would this code look if I wanted to code alphabet of n symbols? This shows a code only for 4 symbols. $\endgroup$ – Guest Nov 11 '14 at 21:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 11 '14 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.