I've been given a generator matrix $G$ and for a linear code over $\mathbb{Z}_{2}$ and a message $m$ to encode. Now this seems simple enough because I know the encoded message $c$ should just be $c = mG$, but what I'm confused about is whether or not I need to convert $G$ to standard $I|S$ form first. The notes say I'm allowed to permute the columns of $G$ without "messing" anything up, and $G$ has all the columns of $I$ so I can easily put it into standard form by just switching a few columns around. However, the notes also say (or at least seem to say) that I can use Gaussian Elimination to convert $G$ to standard form. However, when I do this, I get a matrix with $-1$ for some elements, which is clearly not correct.
So do I even need to convert $G$ to standard form to encode a message, and if I do, is just permuting some columns a valid way of doing so?
edit: As I research this more on my own, I keep seeing statements along the lines of "We can assume $G$ is in reduced row echelon form" or "We can assume $G$ takes the simpler form $I|S$", but I don't understand what these mean? I'm looking at $G$ and it's very obviously not in reduced row echelon form, and while I can reduce it to something that looks like $I|S$, that's not equal to $G$. What do they mean I can "assume" it is?
When proving theorems about performane and properties of linear codes, we can always assume $G$ is in standard form because any $G$ can be converted to that form without affecting performance - permutations and linear row operations on $G$ results in an equivalent code, but not the same code!
Multiplying your information word $m$ with $G$ generates an overdetermined system of linear equations $c = mG$. Say you want to transmit over the binary erasure channel and some of the bits get erased. To decode, all you need to do is to find a subsystem $c = mG_s$ where $G_s$ is a full-rank square submatrix of $G$, and decode by matrix inversion: $m = cG^{-1}_s$. Note that permutations and elementary linear operations on $G$ does not affect invertability, which is essentially why code performance does not change.
(Clearly,if you want to be able to acually decode $m$, you need access to the same $G$ you used as for decoding, not some permuted version. But that's it.)