Learn how Hamming's
Single Error Correcting Code works.
Learn
how CRC detects multiple bit errors.
Assignment
Date: 10/23/2006
Due Day:10/30/2006
Description:
CDMA. Chapter 2.51. Page 181. Prove if S.T=0, then S.T=0 where T
is the complement chip sequence of T.
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?
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?
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.
ECC.
For an optimal double bit error correcting code CDECC, what
is the hamming distance of this code, Hd(CDECC)?
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.
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"
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.
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.
