Write $m$ in binary. The lines where the number is odd corresponds to the bits that are $1$ in the binary expansion. In your example of $18 \times 37$ we have $18=10010_2=2^1+2^4,$ so $18 \times 37=(2+16) \times 37$, which are exactly the terms you added.
The condition $ k = 3n -1 $ gives you the number of times the two matrix will intersect with each other. For a by $ 4 \times 4 $ matrix you will have to intersect, multiply and accumulate 11 times. For instance, in this link you can see a short animation. You see that in fact, the process is done 11 times for the shown matrix: https://www.youtube.com/watch?v=sJltBQ4MOHA
Regarding your questions:
$[(i,j) \mapsto 0]$: This means an assigment of value zero to the element $(i,j)$ of the matrix.
$I' = [(i,j) \mapsto (i=0) ~ ? ~ X(k-j,j): I(i-1,j)] $: This means the following. For any element $(i,j)$ of matrix I', if the row index $ i = 0 $, then you assign the value of $ X(k-j,j) $ to I'(i,j). If not (by this I mean $ i \neq 0 $), you assign $ I(i-1,j) $ to $ I'(i,j) $.
$ I' $ is a temporary matrix that collects the elements of $ X $ that are at the intersection of the two matrices (elements ready for performing operations on them). Thus, the relevant input of $ X $ is denoted by $ I' $.
$A'$ is an accumulator as you can see in line 12. Each element $W(i,j)$ is being multiplied by each element of $ I'(i,j) $. Recall that $ I'(i,j) $ is obtained from $X$. Thus, we are multiplying $X$ and $W$ but in a different manner.
$O'$ is the output matrix. It is moving the accumulated values of $A'$ to their correct positions (as if we were multiplying matrices in the standard manner).
I would also recommend this other video, if you need to learn more: https://www.youtube.com/watch?v=cmy7LBaWuZ8.
Best Answer
I think that you’ve some misconceptions about both the workings of the algorithm and the reason it works.
Let’s look in detail at $37\cdot 15=555$. Here’s the correct table, in the arrangement that you used in your question, but with a little more detail. (Ignore the underlines and the $\text{Row}$ column for now.)
\begin{array}{c|cc} \text{Row}&\text{Half}&&\text{Double}&\text{Remainder}\\ \hline 0&37&\times&\underline{15}&1\\ 1&18&\times&30&0\\ 2&9&\times&\underline{60}&1\\ 3&4&\times&120&0\\ 4&2&\times&240&0\\ 5&1&\times&\underline{480}&1 \end{array}
There’s a remainder in the last line because $1$ would leave a remainder if you went on to halve it.
Ignore the $\text{Double}$ column for now. The first and last columns tell you that
$$\begin{align*} 37&=2\cdot 18+1\\ &=2(2\cdot 9+0)+1\\ &=2^2\cdot9+1\\ &=2^2(2\cdot4+1)+1\\ &=2^3\cdot4+2^2+1\\ &=2^3(2\cdot2+0)+2^2+1\\ &=2^4\cdot2+2^2+1\\ &=2^5+2^2+1\;. \end{align*}\tag{1}$$
In other words, they show how to express $37$ as a sum of powers of $2$, i.e., how to write it in binary (base two) notation: $37=1\cdot2^5+0\cdot2^4+0\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0$, so in binary it’s $100101$.
Now read the $\text{Remainder}$ column from bottom to top: $100101$. It’s exactly the same. And if you examine closely the calculations in $(1)$ and think about how they’re related to the original table, you’ll see that this will always work: the $\text{Remainder}$ column, read from bottom to top, gives you the binary representation of the number that you’re halving.
Now, finally, we’ll look at what’s happening in the $\text{Double}$ column. We want $37\cdot15$. We now know that $37=2^5+2^2+1$, so
$$\begin{align*} 37\cdot 15&=(2^5+2^2+1)\cdot 15\\ &=2^5\cdot15+2^2\cdot15+1\cdot15\;. \end{align*}$$
Now $2^5\cdot15=\underbrace{2\cdot2\cdot2\cdot2\cdot2}_{5\text{ twos}}\cdot15$ is what you get when you double $15$ five times, $2^2\cdot15$ is what you get when you double $15$ twice, and of course $1\cdot15$ is just the original $15$. The $\text{Row}$ column of the table shows how many doublings (and halvings) have been performed to get to a given row, so are the numbers that I underlined in the $\text{Double}$ column. Thus,
$$\begin{align*} 37\cdot 15&=(2^5+2^2+1)\cdot 15\\ &=2^5\cdot15+2^2\cdot15+1\cdot15\\ &=480+60+15\\ &=555\;. \end{align*}$$
Notice that these are also the numbers in the $\text{Double}$ column adjacent to $1$’s in the $\text{Remainder}$ column. That’s no accident: those $1$’s showed which powers of $2$ were needed to make up the multiplier $37$, and therefore which compound doublings of $15$ must be added to get the product.
The whole idea is use the repeated halving of the multiplier to write it as a sum of powers of two, because multiplying another number, like $15$, by a power of $2$ is easy: $2^na$ is what you get when you double $a$ $n$ times, and doubling is easy. The remainders of $1$ aren’t really lost: they tell you which powers of $2$ are actually needed in the binary representation of the multiplier and thereby tell you which doublings of the other number must be added together to get the product.