[15] (a) Show that the function (x, y)=(x2 + 2xy +y2 + 3x+ y)/2 is a computable one-to-one mapping from N 2 onto N .

[15]

(a) Show that the function τ(x, y)=(x2 + 2xy +y2 + 3x+

y)/2 is a computable one-to-one mapping from N 2 onto N . Show that this is not a prefix-code.

(b) Show that τ (k) defined by τ (2) = τ and τ (k)(x1, x2,...,xk) = τ(τ (k−1)

(x1, x2,...,xk−1), xk) is a computable one-to-one mapping from N k onto N . Show that this is not a prefix-code.

(c) Let E : N→N be an effective prefix-code with E(x) the code word for source word x. Show that E(τ(x, y)), and also E(τ (k)(x1,...,xk)), for k > 2, are effective prefix-codes.

Comments. How good are these prefix-codes of k-tuples of integers in terms of density of the range of the code in N ? Clearly, Item

(c) is the best possible (in terms of fixed E).