Derive the ideal solution distribution. At the first

Derive the ideal solution distribution. At the first iteration(t = 0) let the number of packets of degree d be h0(d); show that (ford > 1) the expected number of packets of degree d that have their degreereduced to d -1 is h0(d)d=K; and at the tth iteration, when t of the K packets have been recovered and the number of packets of degree dis ht(d), the expected number of packets of degree d that have theirdegree reduced to d ?? 1 is ht(d)d=(K -t). Hence show that in orderto have the expected number of packets of degree 1 satisfy ht(1) = 1for all t 2 f0; : : :K ?? 1g, we must to start with have h0(1) = 1 andh0(2) = K=2; and more generally, ht(2) = (K – t)/2; then by recursion solve for h0(d) for d = 3 upwards.
This degree distribution works poorly in practice, because uctuationsaround the expected behavior make it very likely that at some point in the decoding process there will be no degree-one check nodes; and, furthermore, anew source nodes will receive no connections at all. A small modification fixes these problems. The robust solution distribution has two extra parameters, c and ; it is designed to ensure that the expected number of degree-one checks is about

rather than 1, throughout the decoding process. The parameter _ is a bound on the probability that the decoding fails to run to completion after a certain number K0 of packets have been received. The parameter c is a constant of order 1, if our aim is to prove Lucy’s main theorem about LT codes; in practice however it can be viewed as a free parameter, with a value somewhat smaller than 1 giving good results. We define a positive function

(see figure 50.2 and exercise 50.4 (p.594)) then add the ideal soliton distribution to T and normalize to obtain the robust soliton distribution, p:

where  The number of encoded packets required at the receiving end to ensure that the decoding can run to completion, with probability at leas