Past exam of the mathematics course of the University of Cambridge 2006 ii Paper 2 4G Solution Created 2026-09-24 Updated 2026-10-14
A decipherable code is one whose extension to finite strings by concatenation is injective: an encoded string has a unique sequence of source letters. In particular its codewords are distinct and nonempty. Put and . For strings of exactly source letters, let count the encoded strings of length . Unique decipherability gives , since distinct source strings yield distinct encoded strings. Expanding givesTaking th roots and letting proves the McMillan inequality
Add to the four specified binary words. None of the resulting seven words is a proper suffix of another: the longer words end in , and their shorter terminal strings never equal another of the specified longer words. Thus this is a suffix code. Reading from the right determines the last codeword uniquely; deleting it and repeating proves unique decipherability. Its length sum is , in agreement with the bound.