debugMinor
About codes over $\mathbb{F}_2$
Viewed 0 times
mathbbcodesaboutover
Problem
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?
-
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?
Solution
-
A binary code is a set of vectors in $\mathbb{F}_2^n$ for some $n$.
-
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$.
-
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).
A binary code is a set of vectors in $\mathbb{F}_2^n$ for some $n$.
-
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$.
-
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).
Context
StackExchange Computer Science Q#41033, answer score: 4
Revisions (0)
No revisions yet.