3
$\begingroup$

Hi !

I have a parity check matrix $H$ for a code $C$
0 0 0 1 1 1 1 0
0 1 1 0 0 1 1 0
1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1

I am allowed to assume that
1) the dual of an $(n,k)$-code is an $[n,n-k]$-code
2) $(C^{\perp})^{\perp} = C$ (Here $\perp$ denotes the dual)

I want to prove that my code $C$ is self-dual. (ie that $C=C^{\perp}$)

Here is my logic:

I know that, since $H$ is a parity check matrix for $C$,
$H$ is a generator matrix for $C^{\perp}$.

Since $C^{\perp}$ is an $[n,n-k]$-code, the generator matrix $H$ is a matrix: $[n-k]$ x $ n$

So now looking at $H$, n=8 and k=4, so the corresponding $C$ code is a $8$x$4$ matrix.

Now let $G=[g_{i,j}]$ be the generator matrix for $C$.
$(GH^T)=0$ since every vector in the rowspace of $G$ is orthogonal to every vector in the rowspace of $H$;

Can anyone tell me what is missing to finish off my proof?

Note: i see that each row in $H$ has even number of entries and that the distance between any two rows is even. maybe this helps if I can right a definition of weight relating to duals...

$\endgroup$
4
  • 2
    $\begingroup$ If you can show that the rows of $C$ are orthogonal to each other, then every codeword in $C$ is a member of $C^{\perp}$ since any given codeword $x$ is orthogonal to all the codewords in $C$ and thus $x \in C^{\perp}$. Next, conclude from your given assertion that $C^{\perp}$ is a $[n, n-k] = [8, 4]$ code that there are no other codewords in $C^{\perp}$. $\endgroup$ Apr 30, 2012 at 17:45
  • 2
    $\begingroup$ >Can anyone tell me... What you have shown is that $C^{\perp}$ has generator matrix $H$. What you need to show is that all the codewords in $C^{\perp}$ are codewords in $C$ and vice versa. Proving inclusion in one direction and then asserting equality on the grounds that the two sets have the same cardinality works since we are dealing with finite sets. $\endgroup$ Apr 30, 2012 at 17:52
  • $\begingroup$ does it suffice to look at the generator matrix of C (for the inclusion part) ? $\endgroup$
    – Kiv Efehe
    Apr 30, 2012 at 18:06
  • $\begingroup$ >does it suffice? Yes it does, but see rschwieb's answer which shows one inclusion without having to look for (or look at) the generator matrix of $C$. $\endgroup$ Apr 30, 2012 at 18:58

1 Answer 1

3
$\begingroup$

The rows of $H$ generate $C^\perp$.

By definition of the parity check, $xH^\mathrm{T}=0$ iff $x\in C$.

What can you conclude from the fact that $HH^\mathrm{T}=[0]$?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .