0
$\begingroup$

$H$ is an $n \times n$ matrix with elements in $ \{ -1,0,1 \}$

$G$ is an $n \times k$ matrix with elements in $GF(2)$ and also upper triangular, invertable

$m$ is an $k \times 1$ vector with elements in $GF(2)$

How can we perceive the output of $HGm$ where $Gm$ multiplication is in $GF(2)$ and $H$ multiplication is a normal real multiplication. Actually I want to combine $HG$ transformation into one $P$ transformation. How can I multiply two matrices while elements in one are in $GF(2)$ and other is in $R$ ? (We can also restrict the entries in $H$ to be one of $-1$ and $1$ but the output can be in $R$).

Motivation: It is a digital communication problem. $Gm$ is output codeword with 1 being mapped to -1 and 0 bit being mapped to +1. This codeword is multiplied to a channel convolution matrix $H$ e.g.

write in MATLAB

H = [1 -1 0 0 0;0 1 -1 0 0; 0 0 1 -1 0; 0 0 0 1 -1; 0 0 0 0 1]'

Now I have the following questions?

  1. I want to know whether the whole transformation P = H(G) can be represented by an equivalent transformation P' in GF(2) ? In other words, does there exist a $M \in [GF(2)]^{n \times n}$ such that $P'=G; P=H(MG)$

  2. If above is not generally possible, do there exist sufficient conditions for $H$ such that above is even possible?

  3. Which branch of mathematics deals with the interaction of real matrices with matrices on finite fields?

  • 0
    $HGm$ makes little sense when $H$ is a real matrix and each entry of $Gm$ is an element of $\mathbb F_2$, that is, a residue class of $\mathbb Z$ modulo 2. Each of these residue classes is unchanged under multiplication by $1$ or $-1$.2011-11-10
  • 0
    Is $H$ a matrix with entries in $\{+1,-1\}$ or in $\{0,+1,-1\}$? You state the former while describing the set-up but your example uses the latter alphabet. Also, $Gm$ is a vector over $\mathbb F_2$. Are you mapping it to the alphabet $\{+1,-1\}$ using $x \to (-1)^x$?2011-11-10
  • 0
    I believe you simply take the matrix G and map its entries one by one: 0→−1 and 1→1. I've only seen 0→0 and 1→1, which is a very simple embedding used in decoding algorithms. Neither of these is a homomorphism, but they still end up being helpful in decoding.2011-11-10
  • 1
    Also posted to MO, http://mathoverflow.net/questions/79427/multiplication-of-matrices-in-gf2-and-r2011-11-10
  • 0
    you are right $H \in \{-1,0,+1\}^{n \times n}$ and No I am not mapping it to ${+1, -1}$. Instead, I am mapping it to $\{+1, 0\}$.2011-11-10
  • 0
    You are right Gerry! But they mentioned in the end that I should better ask it in dsp.stackexchange as it is not a research level math question!2011-11-10
  • 0
    Jack are you saying that I should think of transforming into an equivalent $P'$ where $P' \in \mathbb{R}^{n \times k}$ instead of going for an equivalent $P' \in [GF(2)]^{n \times k}$2011-11-10
  • 0
    Henning H is not a real matrix instead its elements are in $\{+1,0,-1 \}$. So, I thought this restriction could make the problem simpler and $H(Gm)$ starts making sense?2011-11-10
  • 0
    Yes, you were advised to ask it here, but you overlooked the common courtesy of letting people here know that it was posted there, thus creating the possibility of duplication of effort.2011-11-11
  • 0
    @Gerry You are right! I am new to stackexchange.com so don't know how it works here. I will take this in my mind next time!2011-11-11
  • 0
    @Aitezaz: $H(Gm)$ does not make sense, because the components of $Gm$ are elements of $GF(2)$, and components of $H$ are real numbers or integers. There is no$^{*)}$ way to treat an element of $GF(2)$ as an integer, and hence that multiplication is not defined. *) at least no such way that would respect the addition and multiplication, and those operations are needed for the matrix multiplication to make any sense.2011-11-15

1 Answers 1

1

The vector ${\mathbf x} = Gm \in \mathbb F_2^n$ is transformed into a vector $\mathbf y$ over the alphabet $\{-1, +1\}$ by mapping each component $x_i$ via $x_i\to (-1)^{x_i}$ since the OP says "output codeword with $1$ being mapped to $-1$ and $0$ bit being mapped to $+1$." But the product ${\mathbf z} = H{\mathbf y}$ is a $n$-tuple of real numbers from the set $\{-n, -n+1, \ldots, n-1, n\}$. So I suppose that the question is how to describe the map from $m \in \mathbb F_2^k$ to $\mathbf z$. One way would be to treat the elements of $\mathbb F_2$ as elements of $\mathbb Z$ and replace all additions $a\oplus b$ in $\mathbb F_2$ with $a + b - 2ab$ while computing the product $Gm$, map $\mathbf x$ to $\mathbf y$ as described above, and finally write the matrix multiplication.

All this might be describable purely in terms of operations in $\mathbb F_2$ with a final map from some $\mathbb F_2^N$ to $\{-n, -n+1, \ldots, n-1, n\}^n$, but I don't see the point of doing so.