CS522 F2004 Homework#6:  Coding, CRC, and ARQ

Goal: Assignment Date: 11/15/2004
Due Day:11/29/2004
Description:
  1. Bit Stuffing.
    Page 244. Chapter 3 problem 5.
    A bit string 011110 111110 111 1110 was sent from network layer to be transmitted at the data link layer. What is the string actually transmitted after bit stuffing?
  2. ECC.
    1. For a optimal double bit error correcting code CDECC, what is the hamming distance of this code, Hd(CDECC)?
    2. For single error correct codes, Richard Hamming proves m+r+1 <= 2r as the inequality for selecting optimal check bit size r. Derive the equivalent inequality formual for double bit error correcting codes to help select the optimal check bit size. Express it in terms of n (total number of bits in the code word) and r.
  3. CRC Encoding and Decoding.
    1. Can generator polynomial g1(x)=x^5+x^2+1, detect double bit errors? What is the longest codeword this generator can cover double bit errors.
      There is a chkprimitve.pl program you can use to verify this. Type "~cs522/public_html/src/crc/chkprimitive.pl 100101"
    2. For data bit pattern 10011101, if we use generator polynomial g2(x)=x+1, what will be the CRC codeword to be sent by the sender?
      There is a encode.pl program you can use to verify your answer. Type in the data bit pattern as first parameter and bit pattern of generator polynomial as 2nd parameter.
    3. With g2(x)=x+1, verify 111111110 is a CRC codeword. Let us introduce three bit errors at bit positions 3,4, 7. The garbled codeword becomes 111001100. Show the receiver can detect the 3 bit errors. Type "decode.pl 111001100 11" to verify this.
    4. Verify that G(x)=g1(x)*g2(x) is x^6+x^5+x^3+x^2+x+1 and show it can detect a double bits errors and an odd number of bits errors.
      • First pick a data bit pattern,
      • Generate a codeword with G(x) (you can use encode.pl to do that)
      • Garble any two bits in the codeword and use decode.pl to verify that double bit error is detected.
      • Garble any odd number of bits in the codeword and use decode.pl to verify that error is detected.

  4. ARQ
    1. Goback n ARQ.
      Example at the top of page 222 shows that with 3 bits as sequence number field, the Max_SEQ=2^3-1=7, and that we should not use 2^3=8 as the window size. If we do that, we will not be able to distinguish duplicate acknowledgement from new acknowledgement. We should reduce the window size to 7. With window size set ot 7, let us repeat the scenario.
      1. What will be the sequence numbers for the first batch of packets sent?
      2. Assume only one piggybacked acknowledgement is sent back for this batch and no channel error at this period, what will be the acknolwedgement RN field value?.
      3. What will be the sequence numbers for the 2nd batch of packets sent?
      4. Assume only one piggybacked acknowledgement is sent back for the 2ndbatch and no channel error at this period, what will be the acknolwedgement RN field value?
      5. Assume all 2nd batch of packets got garbled with CRC error. What will be the acknolwedgement RN field value in the piggybacked acknowledgement?
    2. Selective Repeat ARQ.
      Example at top of page 226 shows that with 3 bits as sequence number field, the Max_SEQ=2^3-1=7, and that we should not use 7 as the window size. If we do that, we will not be able to distinguish duplicate acknowledgement from new acknowledgement. We should reduce the window size to (7+1)/2=4. With window size set to 4, answer the five questions of 4.a in the context of selective repeat ARQ.