Linear codes: In coding theory, we have a linear codes where a message is passed through an encoder to get a code. A linear code is the situation where a message $u=(u_1,\dots,u_k)\in\{0,1\}^k$ (notice that this is a row vector) is passed through a linear encoder to give $x=uG\,(\text{mod 2})\in\{0,1\}^n$ where (mod 2) just means that operations are done in modulo-2 arithmetic and $G\in\{0,1\}^{k\times n}$ here is the encoding matrix.
Question: Can I rewrite the above setup such that I get the following:
- I no longer need the requirement for operations to be done in modulo-2 arithmetic, just normal arithmetic that we are used to (i.e., no need to take remainders etc).
- Entries of $x$ are in $\{-1,+1\}$ instead of $\{0,1\}$. Can this be done through redefining how we represent $u$ and $G$, and by using some other mathematical function?
- You are allowed to write $x=f(uG)$, where $f(\cdot)$ is a function (that applies element wise to the vector) up to your choosing, except those that involve floor and ceiling functions. Otherwise, we can write $x_i=\boldsymbol{1}\{\lceil uG_j/2\rceil=\lfloor uG_j/2 \rfloor+1\}$, where $G_j$ is the $j$th column of $G$.
- Essentially, you are free to do anything as long as the modulo-2 arithmetic can be removed.
Attempt: I was thinking maybe to keep $G\in\{0,1\}^{k\times n}$ and change the entries of $u$ to be in $\{-1,+1\}$ with $0$ being mapped to $-1$, and $1$ being mapped to $+1$. Then we can have $x=\text{sign}(uG)$, where $\text{sign}(\cdot)$ is defined as \begin{align*} \text{sign}(\theta)= \begin{cases} +1 \text{ if $\theta\geq0$}\\ -1 \text{ otherwise.}\\ \end{cases} \end{align*} and applied element wise to the vector $uG$. But on further thought this is wrong. I am wondering if I can do something similar to get my goal...
Motivation: I am just curious if the linear coding model can be represented as something similar to that of compressed sensing (or specifically one-bit compressed sensing) -- without the need for the nasty modulo-2 arithmetic. Thanks for the help.
The mapping $a\rightarrow (-1)^a$ is indeed used in coding and sequence design applied to vectors. This gives the pleasing property that if two vectors $x,y \in \{0,1\}^n$ satisfy $d(x,y)=n/2,$ assuming $n$ even, we get two orthogonal vectors $u,v$ if we define $$ u=(u_i)_i^n\quad \mathrm{ with }\quad u_i=(-1)^{x_i},\quad v=(v_i)_i^n\quad \mathrm{ with }\quad v_i=(-1)^{y_i}. $$
However, the $GF(2)$ based algebraic theory of code generation via with parity check and generator matrices does not have a straightforward conversion to a space of real and more generally complex linear algebra. The crucial part is that we have finite arithmetic in $GF(2)$ or other finite fields.
Once noise is added to the picture (after converting to the $\{\pm 1\}$ alphabet then the continuous point of view is more helpful, with probability also playing a major part.
A nice book that covers this area with lots of applications is Schroeder, M. R. (2009). Number theory in science and communication : with applications in cryptography, physics, digital information, computing, and self-similarity Springer Verlag.