Question

Prove that the function $\mathit{f}\mathbf{:}\mathit{B}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{\to }\mathit{B}\mathbf{(}\mathit{n}\mathbf{-}\mathit{k}\mathbf{)}$in the proof of Theorem 16.9 is surjective. [Hint: if$\mathit{v}\mathbf{=}{\mathit{v}}_{\mathbf{1}}{\mathit{v}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{v}}_{\mathbf{n}\mathbf{-}\mathbf{k}}\mathbf{\in }\mathit{B}\mathbf{(}\mathit{n}\mathbf{-}\mathit{k}\mathbf{)}$, show that$\mathit{v}\mathbf{=}\mathit{f}\mathbf{\left(}\mathit{u}\mathbf{\right)}$, where$\mathit{u}\mathbf{=}\mathbf{000}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{0}{\mathit{v}}_{\mathbf{1}}{\mathit{v}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{v}}_{\mathbf{n}\mathbf{-}\mathbf{k}}\mathbf{\in }\mathit{B}\mathbf{\left(}\mathit{n}\mathbf{\right)}$.]

Short answer

It is proved that the function $f:B\left(n\right)\to B(n-k)$is surjective.

Step-by-step solution

Determine the codeword Theorem

Let C be an (n,k) code with standard generator matrix G and parity-check matrix H. Then an element w in B(n) is a code if and only if wH = 0.

Determine the Proof of function is surjective

Suppose that $u=000...010...0v_1{v}_2...v_{n-k}\in B\left(n\right)$and $v=v_1{v}_2...v_{n-k}\in B(n-k)$. Suppose c be the code number (n,k) that generated by the standard generator matrix and parity check matrix H.

By the codeword theorem, an element w can be considered a codeword if and only if wH = 0.

First, define a function $f:B\left(n\right)\to B(n-k)$where $f\left(w\right)=wH$. Now, w can be considered as codeword if and only if $w\in C$and also $w\in K$if and only if $wH=0$. So, from the previous statement is clear that C = K.

Using the definition of generator matrix, the form uG is considered to every element of C for some $u\in B\left(k\right)$. But, G H is zero matrix. So,

$\begin{array}{rcl}\left(uG\right)H& =& u\left(GH\right)\\ & =& 0\end{array}$

Therefore, $C\subseteq K$.

Now, we know that c is a group of order 2^k and K also has 2^k order. This means v = f(u).

Thus, the function $f:B\left(n\right)\to B(n-k)$is surjective.