CS522 F2006 hw4 Solution

CDMA. Chapter 2.51. Page 181.
Prove if S.T=0, then S.T=0 where T is the complement chip sequence of T.

Ans: S•T =

=0
S•T =

= -1 *

=-1*0=0.

CDMA. Chapter 2.53. Page 181. A CDMA receiver gets the following chips: (-1 +1 -3 +1 -1 -3 +1 +1). Assume the chip sequences defined in Figure. 2-45 (b), which stations transmited, and which bits did each one send?

Ans: Just compute the four normalized inner products between the signal and the four chip seuqnces:
-1+1-3+1-1-3+1+1)•(-1-1-1+1+1-1+1+1)/8=1     (-1-1-1+1+1-1+1+1) is A's chip sequence.
(-1 +1 -3 +1 -1 -3 +1 +1) • (-1 -1 +1 -1 +1 +1 +1 -1)/8 =-1    (-1 -1 +1 -1 +1 +1 +1 -1) is B's chip sequence.
(-1 +1 -3 +1 -1 -3 +1 +1) • (-1 +1 -1 +1 +1 +1 -1 -1)/8 = 0   (-1 +1 -1 +1 +1 +1 -1 -1) is C's chip sequence.
(-1+1-3+1-1-3+1+1) •(-1+1-1-1-1-1+1-1)/8=1      (-1+1-1-1-1-1+1-1) is D's chip sequence.
The result is that A and D sent bit-1s, B sent bit-0, and C was silent.

SECC encoding. Page 244. Chapter 3 problem 10.
An 8-bit byte with binary value 10101111 is to be encoded using an even-parity Hamming code. What is the binary value after encoding?

Ans: The binary value of the codeword is 101001001111. The detail of the encoding process is shown below.

1	2	3	4	5	6	7	8	9	10	11	12	Bit poisition
C0	C1	D1	C2	D2	D3	D4	C3	D5	D6	D7	D8	codeword pattern
		1		0	1	0		1	1	1	1	Data bits
1	1	¿										D1 contributes check bit pattern 11 (bit position 3)
	1		1		¿							D3 contributes check bit pattern 110 (bit position 6)
1							1	¿				D5 contributes check bit pattern 1001 (bit position 9)
	1						1		¿			D6 contributes check bit pattern 1010 (bit position 10)
1	1						1			¿		D7 contributes check bit pattern 1011 (bit position 11)
			1				1				¿	D8 contributes check bit pattern 1100 (bit position 12)
1	0		0				0					Calculate check bit using even parity bit
1	0	1	0	0	1	0	0	1	1	1	1	codeword generated

SECC decoding. Page 244. Chapter 3 problem 11. I added one additional question to be answered in terms of the data bits to be delivered.
A 12-bit Hamming code whose hexadecimal value is OxE4F arrives at a receiver.

What was the original codeword sent by the sender in hexadecimal? Assume that not more than I bit is in error.

What are the data bits that should be delivered to the upper layer of the receiver.

Ans: The original codeword set by the sender is 0xA4F. The data bit delivered to the upper layer of the receiver is 10101111. The detail of decoding process is shown below.

1	2	3	4	5	6	7	8	9	10	11	12	Bit position
C0	C1	D1	C2	D2	D3	D4	C3	D5	D6	D7	D8	codeword pattern
			E				4				F	receive bit patter in hexadecimal
1	1	1	0	0	1	0	0	1	1	1	1	receives bit pattern
		1		0	1	0		1	1	1	1	set aside received check bits
1	1	¿										D1 contributes check bit pattern 11 (bit position 3)
	1		1		¿							D2 contributes check bit pattern 110 (bit position 6)
1							1	¿				D5 contributes check bit pattern 1001 (bit position 9)
	1						1		¿			D6 contributes check bit pattern 1010 (bit position 10)
1	1						1			¿		D7 contributes check bit pattern 1011 (bit position 11)
			1				1				¿	D7 contributes check bit pattern 1100 (bit position 12)
1	0		0				0					Calculate check bit using even parity bit
	X											positions sent and rcvd check bit not the same
	2											sum of position weight=2 position 2 is garbled
	0											correct the bit.
1	0	1	0	0	1	0	0	1	1	1	1	correct codeword
			A				4				F	original codeword sent in hexadecimal.
		1		0	1	0		1	1	1	1	Data bits delivered to upper layer

What was the original codeword sent by the sender in hexadecimal? Assume that not more than I bit is in error.
Ans:

What are the data bits that should be delivered to the upper layer of the receiver.
Ans:

1 0 1 0 1 1 1 1

ECC.

For an optimal double bit error correcting code C_DECC, what is the hamming distance of this code, Hd(C_DECC)?

Ans: Error correcting code for correcting n bit error is 2n+1, where n is the number bits that have errors. Here n=2. Therefore Hd(C_DECC)=5.
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: Follow the same proving technique. The number of bit patterns in the group including a legitimate codeword and all the related double bit error pattterns is Np=C(n,2)+1=n*(n-1)/2 + 1. We have Ng=2^m such groups based on the legimate codeword pattern in the data bit field. Ideally we would like to design the code such that Np*Ng=2^n, i.e., all n bit patterns are used. (n*(n-1)/2+1)*2^m <= 2^n=2^(m+r). Cancel out 2^m terms on both sides, we get

(n*(n-1)/2+1) <= 2^r.

CRC Encoding and Decoding.

Can generator polynomial g1(x)=x^5+x^2+1, detect double bit errors? What is the longest codeword this generator can cover for double bit errors? Given an example that illustrates the use of g1(x) for detecting a double bit error.
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.

Repeat the following exercise shows that g2(x)=x+1 can detect odd number (in this case 3) of of bit errors.

Encode an 8 bit data bit using g2(x).
You can use encode.pl program in ~cs522/public_html/src/crc/ to verify your answer. Type in the data bit pattern as first parameter and bit pattern of generator polynomial as 2nd parameter.
Let us introduce three bit errors at bit positions 3,4, 7. What is the garbled codeword?

Show the receiver can detect the 3 bit errors in the garbled codeword.
Type "decode.pl <your garbled codeword> 11" to verify this.

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

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

Verify that G(x)=g1(x)*g2(x) is x^6+x^5+x^3+x^2+x+1 and show it can detect 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).

CS522 F2006 Homework#4: CDMA and SECC