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

Goal:

Learn how CRC detects multiple bit errors.
Learn Go back n and Selective Repeat ARQ.
Learn Bit Stuffing.

Assignment Date: 11/15/2004
Due Day:11/29/2004
Description:

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?
Ans: The output is 011110111110011111010.
|
ECC.
1. For an optimal double bit error correcting code C_DECC, what is the hamming distance of this code, Hd(C_DECC)?
  Ans: 5. Any double bit error from an legitimate codeword can be restored. Two legitimate codewords will then be separated by at least 4 illegitimate codewords. There Hd(CDECC)=4+1=5.
2. For single error correct codes, Richard Hamming proves m+r+1 <= 2^r 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.
  Ans: The number of illegitmate double bit error codewords for a legitimate codeword is C(n,2)=(n*(n-1))/2. If we group those illegitimate codewords with the legitimated codeword, the group has (n*(n-1))/2+1. Since for a codeword pattern with m data bits and r check bits, there are 2^m possible pattern in the data bit field of the legitimate codeword. Therefore ((n*(n-1))/2+1)*2^m <= 2^n.
  Since n=m+r, we get ((n*(n-1))/2+1)*2^m <= 2^(m+r).
  Cancel 2^m from both sides of the inequality, we get ((n*(n-1))/2+1)<= 2^r.
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"
  
  Ans: To check if a generator polynomial can detect bit error, we apply the rules 2a in the CRC coding handout page 13.
  
  2a. All double-bit errors E(x)=xⁱ+x^j=xⁱ(1+x^j-i), if G(x) is a primitive with degree of c and the length of codeword is less than 2^c-1. It implies that j-i <=2^c-1.
  
  g1(x) has a degree of 5. To check if g(x) is a primitive polynomial, we need to check if it is not a divsor of 1+x^m for any m<2⁵-1=31.
  We use the chkprimitive.pl for this. The result is shown in http://cs.uccs.edu/~cs522/hw/hwF2003/hw5ex4a.txt.
  
  It indicated that this is a primitive polynomial and therefore it can detect any double bit error up to a codeword length of 31.
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.
  Ans: blanca.uccs.edu> ../../src/crc/encode.pl 10011101 11
```
m(x)=10011101  g(x)=11
length(m(x))=8  length(g(x))=2
degree(m(x))=7 degree(g(x))=1

m(x)=x^7+x^4+x^3+x^2+1
g(x)=x^1+1
mx=1 0 0 1 1 1 0 1
len=1, indexmx=7

d(x)=1 0 0 1 1 1 0 1 0
dx=100111010
1 0 0 1 1 1 0 1 0
1 1

1 0 0 1 1 1 0 1 0
1 1
--------
  1 0
  1 1
  --------
    1 1
    1 1
    --------
      0 1
      0 0
      --------
        1 1
        1 1
        --------
          0 0
          0 0
          --------
            0 1
            0 0
            --------
              1 0
              1 1
              --------
                1

r(x)=  1
q(x)=1 1 1 0 1 0 0 1
codewordPacked=100111011
```
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.
  Ans:
  blanca.uccs.edu> ../../src/crc/decode.pl 111001100 11
```
c(x)=111001100  g(x)=11
length(c(x))=9  length(g(x))=2
degree(c(x))=8 degree(g(x))=1

c(x)=x^8+x^7+x^6+x^3+x^2
g(x)=x^1+1
d(x)=1 1 1 0 0 1 1 0 0
dx=111001100
1 1 1 0 0 1 1 0 0
1 1

1 1
1 1
--------
  0 1
  0 0
  --------
    1 0
    1 1
    --------
      1 0
      1 1
      --------
        1 1
        1 1
        --------
          0 1
          0 0
          --------
            1 0
            1 1
            --------
              1 0
              1 1
              --------
                1

r(x)=  1
q(x)=1 0 1 1 1 0 1 1
crc check detects error!
```
  r(x)<>1; crc check detects error!
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.
  Ans:
         g1(x)=x^5+x^2+1; g2(x)=x+1;
        x^5+                     x^2+          1
      *                                   x+      1
       x^5+                     x^2+           1
  x^6+                   x^3+       x
  x^6+x^5+           x^3+x^2+x+        1
  Yes, G(x)=g1(x)*g2(x)
  Assume we use the data bit pattern 11111111. Note that with g1(x) we can only cover double bit error up to 31 bits (not 2^6-1).
  Use encode.pl 11111111 1101111 we got codeword=1 1 1 1 1 1 1 1 1 0 1 0 0 0
  
  Assume we garble first and last bit. The garbled codedword is 0 1 1 1 1 1 1 1 1 0 1 0 0 1
  
  Use decode.pl 01111111101001 1101111
```
c(x)=01111111101001  g(x)=1101111
length(c(x))=14  length(g(x))=7
degree(c(x))=13 degree(g(x))=6

c(x)=+x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^3+1
g(x)=x^6+x^5+x^3+x^2+x^1+1
d(x)=0 1 1 1 1 1 1 1 1 0 1 0 0 1
dx=01111111101001
0 1 1 1 1 1 1 1 1 0 1 0 0 1
1 1 0 1 1 1 1

0 1 1 1 1 1 1
0 0 0 0 0 0 0
--------
  1 1 1 1 1 1 1
  1 1 0 1 1 1 1
  --------
    0 1 0 0 0 0 1
    0 0 0 0 0 0 0
    --------
      1 0 0 0 0 1 0
      1 1 0 1 1 1 1
      --------
        1 0 1 1 0 1 1
        1 1 0 1 1 1 1
        --------
          1 1 0 1 0 0 0
          1 1 0 1 1 1 1
          --------
            0 0 0 1 1 1 0
            0 0 0 0 0 0 0
            --------
              0 0 1 1 1 0 1
              0 0 0 0 0 0 0
              --------
                0 1 1 1 0 1

r(x)=  0 1 1 1 0 1
q(x)=0 1 0 1 1 1 0 0
crc check detects error!
```
  r(x) not zero. crc check detects double bit error!
  
  Now let us garble the first 5 bits (odd number of bits) and the garbled codeword becomes 0 0 0 0 0 1 1 1 1 0 1 0 0 0.
  Let us run > decode.pl 00000111101000 1101111
```
c(x)=00000111101000  g(x)=1101111
length(c(x))=14  length(g(x))=7
degree(c(x))=13 degree(g(x))=6

c(x)=+x^8+x^7+x^6+x^5+x^3
g(x)=x^6+x^5+x^3+x^2+x^1+1
d(x)=0 0 0 0 0 1 1 1 1 0 1 0 0 0
dx=00000111101000
0 0 0 0 0 1 1 1 1 0 1 0 0 0
1 1 0 1 1 1 1

0 0 0 0 0 1 1
0 0 0 0 0 0 0
--------
  0 0 0 0 1 1 1
  0 0 0 0 0 0 0
  --------
    0 0 0 1 1 1 1
    0 0 0 0 0 0 0
    --------
      0 0 1 1 1 1 0
      0 0 0 0 0 0 0
      --------
        0 1 1 1 1 0 1
        0 0 0 0 0 0 0
        --------
          1 1 1 1 0 1 0
          1 1 0 1 1 1 1
          --------
            0 1 0 1 0 1 0
            0 0 0 0 0 0 0
            --------
              1 0 1 0 1 0 0
              1 1 0 1 1 1 1
              --------
                1 1 1 0 1 1

r(x)=  1 1 1 0 1 1
q(x)=0 0 0 0 0 1 0 1
crc check detects error!
```
```
Therefore the G(x) can detect 5 bit error (odd number bit error). 
```
ARQ

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 acknowledgement 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 acknowledgement 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?
Ans:
1. The sequence numbers for the first batch of packets sent are 0, 1, 2, 3, 4, 5, 6.
2. The acknowledgement RN field value will be 7 (The receiver expects to receive frame with sequence number 7).
3. The sequence numbers for the second batch of packets sent are 7, 0, 1, 2, 3, 4, 5.
4. The acknowledgement RN field value will be 6.
5. The acknowledgement RN field value will be 7 (different from 6 above). Therefore the sender can distinguish the two cases.
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 5.a.
Ans:
1. The sequence numbers for the first batch of packets sent are 0, 1, 2, 3.
2. The acknowledgement RN field value will be 4 (The receiver expects to receive frame with sequence number 7).
3. The sequence numbers for the second batch of packets sent are 4, 5, 6, 7.
4. The acknowledgement RN field value will be 0.
5. The acknowledgement RN field value will be 4. NAK 4 wll be sent to selectively resend frame 4 if an out of order frame is received.