3
$\begingroup$

I was looking through these notes but I am not sure I can locate the answer to these questions of mine - it would be great if someone can just even point out what to look for!

  • So any set of binary vectors can be seen as "code"?

  • Let $M$ be a $d\times m$ matrix over $\mathbb{F}_2$ and let $X(M)$ be the graph on the binary vectors of length $d$, where two vectors are adjacent if their difference is a column of $M$. (does this mean that before comparing when one is taking a bit-wise difference of the vectors one is equating $-1$ to $1$ as would be inside $\mathbb{F}_2$?)

    Does this above construction have a name? Any motivations?

  • What is this NP-hard question about finding a "minimum weight code" among a set of binary vectors? Can someone kindly give the precise definition?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Please post only one question per post. $\endgroup$
    – Raphael ♦
    Apr 9 '15 at 20:44
5
$\begingroup$

  1. A binary code is a set of vectors in $\mathbb{F}_2^n$ for some $n$.

  2. Presumably the context in which you encountered this construction is a motivation for it. It's a particular case of a more general construction known as a Cayley graph, though perhaps this particular case has a specific name. You are right that all arithmetic is done in $\mathbb{F}_2$.

  3. There are several NP-complete problems related to codes; Madhu Sudan has an entire lecture on these. One of them is, given a generator matrix for a linear code, determine the minimum weight of a non-zero codeword (i.e., the minimum distance).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Raphael ♦
    Apr 9 '15 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.