EDIT:

Unfortunately, the example below was poorly chosen. Several people correctly pointed out that x2 is just a bit shift and doesn't actually require a multiplication. I'm aware of this but I overlooked it when attempting to devise a sufficiently simple example.

A better example would be to replace that 2 by an \$m\$, where \$m\$ is some integer that is not, in general, a power of 2.

---

I'm implementing the following difference equation in digital logic on an FPGA:
$$
a[n] = b[n] + c[n] + 2a[n-1],
$$
where \$n\$ denotes the sample number, and \$b\$ and \$c\$ are inputs.

I'm attempting to pipeline it such that each combinational path between registers has at most one operation (addition or multiplication). I believe this task is impossible. Am I correct?

To justify this claim, let's start with the simpler difference equation:
$$
a[n] = b[n] + c[n] + a[n-1],
$$
The following block diagram implements this:

[![enter image description here](https://i.stack.imgur.com/vz2ii.png)](https://i.stack.imgur.com/vz2ii.png)

I can use [SageMath](https://www.sagemath.org/) to verify this (I've 0-initialized r1 and r2):

```py
import numpy as np

n = np.arange(10)
b = list(var(f"b_{i}") for i in n)
c = list(var(f"c_{i}") for i in n)
x = var("x")

def maybe(a):
    if diff(a, x) != 0:
        return x
    return a

def r1(n):
    if n == 0:
        return 0
    return maybe(b[n - 1] + c[n - 1])

def r2(n):
    if n == 0:
        return 0
    return maybe(r1(n - 1) + r2(n - 1))

for i in n:
    print(f"{i}: {r2(i)}")

```

which yields,

```
0: 0
1: 0
2: b_0 + c_0
3: b_0 + b_1 + c_0 + c_1
4: b_0 + b_1 + b_2 + c_0 + c_1 + c_2
5: b_0 + b_1 + b_2 + b_3 + c_0 + c_1 + c_2 + c_3
6: b_0 + b_1 + b_2 + b_3 + b_4 + c_0 + c_1 + c_2 + c_3 + c_4
7: b_0 + b_1 + b_2 + b_3 + b_4 + b_5 + c_0 + c_1 + c_2 + c_3 + c_4 + c_5
8: b_0 + b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + c_0 + c_1 + c_2 + c_3 + c_4 + c_5 + c_6
9: b_0 + b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + b_7 + c_0 + c_1 + c_2 + c_3 + c_4 + c_5 + c_6 + c_7

```

Now, let's add back the x2. In order to meet the combinational path requirements, I have to add a register after this multiplication. A block diagram that incorrectly implements this is shown below.

[![enter image description here](https://i.stack.imgur.com/Hb1Ce.png)](https://i.stack.imgur.com/Hb1Ce.png)

This is incorrect because r3 time-misaligns \$c\$ and \$b\$ with the feedback data. However, the next block diagram shows why I believe it isn't possible to realign \$c\$ and \$b\$ in the correct way.

[![enter image description here](https://i.stack.imgur.com/pi6Uk.png)](https://i.stack.imgur.com/pi6Uk.png)

The right-most adder has two inputs. The sequential logic paths for these inputs are highlighted by the blue and red arrows. In the correct implementation (remove r3), the total delay of the red path is one sample period greater than that of the blue path. This makes sense, since we're adding the output one sample ago to the current inputs. r3 increases the red path delay by 1 sample period, invalidating the circuit. In order to rectify this we would need to add a delay to the blue path. But, that's not possible since any delay added to the blue path also adds the same delay to the red path.

Do I have any options here? Do I just have to accept that the feedback combinational path will have a multiplication and an addition? Anything else I can do?

Is there any mathematical or computer science theory that discusses/formalizes these notions? I spent a while skimming digital logic and FPGA textbooks and didn't find anything.