Parity check codes. Let

I nk G=AF2 ,

where A F(nk)k and n k. Suppose that a k-bit message x Fk is encoded into an n-bit 22

n

codeword y = Gx F2 . This is an example of an (n, k) binary linear parity check code. In this context, G is referred to as a generator matrix of the code and its range R(G) is referred to as the set of codewords or the codebook. The additional n k bits, or parity bits, provide redundant information that can be used for correction (or detection) of errors that occur to the codewords.

(a) Find |R(G)| and interpret this value in terms of the codewords of the (n, k) code. (nk)n

2. (b) Let H = A I F2 . Show that HG = 0.

3. (c) Show that N(H) = R(G), namely, y is a codeword if and only if Hy = 0. For this

reason, H is referred to as a parity check matrix of the code.

(d) Consider the code with generator matrix H that encodes (n k)-bit messages into n- bit codewords. This (n, n k) code is said to be dual to the original (n, k) code with generator matrix G. Find a parity check matrix P of the dual code, that is, a matrix P that satisfies P y = 0 if and only if y is a codeword of the dual code.

Parity check codes. Let G= 11 Fyxk Fnxk 2 where A F2=k){k and n > k. Suppose that a k-bit message x E F is encoded into an n-bit codeword y = Gx E F. This is an example of an (n, k) binary linear parity check code. In this context, G is referred to as a generator matrix of the code and its range R(G) is referred to as the set of codewords or the codebook. The additional n k bits, or parity bits, provide redundant information that can be used for correction (or detection) of errors that occur to the codewords. (a) Find |R(G) and interpret this value in terms of the codewords of the (n, k) code. (b) Let H = [A I EFn-k)xn. Show that HG = 0. (c) Show that N(H) = R(G), namely, y is a codeword if and only if Hy = 0. For this reason, H is referred to as a parity check matrix of the code. (d) Consider the code with generator matrix H' that encodes (n k)-bit messages into n- bit codewords. This (n, n k) code is said to be dual to the original (n, k) code with generator matrix G. Find a parity check matrix P of the dual code, that is, a matrix P that satisfies Py = 0 if and only if y is a codeword of the dual code. Parity check codes. Let G= 11 Fyxk Fnxk 2 where A F2=k){k and n > k. Suppose that a k-bit message x E F is encoded into an n-bit codeword y = Gx E F. This is an example of an (n, k) binary linear parity check code. In this context, G is referred to as a generator matrix of the code and its range R(G) is referred to as the set of codewords or the codebook. The additional n k bits, or parity bits, provide redundant information that can be used for correction (or detection) of errors that occur to the codewords. (a) Find |R(G) and interpret this value in terms of the codewords of the (n, k) code. (b) Let H = [A I EFn-k)xn. Show that HG = 0. (c) Show that N(H) = R(G), namely, y is a codeword if and only if Hy = 0. For this reason, H is referred to as a parity check matrix of the code. (d) Consider the code with generator matrix H' that encodes (n k)-bit messages into n- bit codewords. This (n, n k) code is said to be dual to the original (n, k) code with generator matrix G. Find a parity check matrix P of the dual code, that is, a matrix P that satisfies Py = 0 if and only if y is a codeword of the dual code