A CODING THEORY PROBLEM ********************* How can one encode binary words with binary words never having more than 4 consecutive 1s? Suppose we allow tables of size 100, 1000, 10000. What is the efficiency of the coding? Q1. The regular expression for such words over an alphabet A={a,b} (a is for 0, b is for 1) is: R=B.(aB)* where B=eps+b+bb+bbb+bbb It is unambiguous. Thus as OGFs > B:=add(z^j,j=0..4); > R:=normal(B/(1-z*B)); > series(R,z=0,15); We see for instance that: There are 61 words in R with length 6 this is enough to encode all the 32=2^5 possible blocks of length 5. Loss is 20%. Table size is 32. You can discuss other table configurations, with size 10^4, 10^5, etc. Does the efficiency of your schemes seem to reach a limit? Q2. What is the optimum coding rate? This needs finding the poles of R. Under full screen versions of Maple, one can try variants of > plot(R,z=-2..2); and so on. or better: > fsolve(denom(R),z,complex); Let alpha be the root of smallest modulus. Then the best efficiency one can attain is -log(2.0)/log(alpha), that is a loss of about 2.5%. Q4. What happens if we allow at most 3 consecutive "b"s? What about the problems where blocks of a and b should not exceed 4, or 3? ****************** Q1. Suppose there are $r$ days in the year. How many people do we need to let enter a room on average till we have a birthday colision? till we have a complete birthday collection? > Birth:=proc(r) evalf(int((1+x/r)^r*exp(-x),x=0..infinity)); end; > Coupon:=proc(r) evalf(int(1-(1-exp(-x/r))^r,x=0..infinity); end; Try: > Birth(365); > Coupon(365); What is the value? > Coupon(366)-Coupon(365) Q2. Try the same thing for a double birthday collision and for a double collection. (Note: you may wish to try it for small values of "r" since the procedures appeal to symbolic integration and may become costly for large "r".) Q3. For r=10..100, try to guess the laws corresponding to Q1 and Q2. Hint, for Q1. Consider doing in the case of Birth: > for r from 10 by 5 to 100 do Birth(r)^2/r od, Try to guess the shape of the next term in an asymptotic expansion and come up with a reasonable numerical formula that matches the facts near r=100. Compare your predictions with Birth(365); ************************