Problem Statement

The convolution of two functions

F

{\displaystyle {\mathit {F}}}

and

H

{\displaystyle {\mathit {H}}}

of an integer variable is defined as the function

G

{\displaystyle {\mathit {G}}}

satisfying for all integers

n

{\displaystyle {\mathit {n}}}

. Assume

F ( n )

{\displaystyle F(n)}

can be non-zero only for

0

{\displaystyle 0}

≤

n

{\displaystyle {\mathit {n}}}

≤

|

F

|

{\displaystyle |{\mathit {F}}|}

, where

|

F

|

{\displaystyle |{\mathit {F}}|}

is the "length" of

F

{\displaystyle {\mathit {F}}}

, and similarly for

G

{\displaystyle {\mathit {G}}}

and

H

{\displaystyle {\mathit {H}}}

, so that the functions can be modeled as finite sequences by identifying

f

0

,

f

1

,

f

2

, …

{\displaystyle f_{0},f_{1},f_{2},\dots }

with

F ( 0 ) , F ( 1 ) , F ( 2 ) , …

{\displaystyle F(0),F(1),F(2),\dots }

, etc. Then for example, values of

|

F

|

= 6

{\displaystyle |{\mathit {F}}|=6}

and

|

H

|

= 5

{\displaystyle |{\mathit {H}}|=5}

would determine the following value of

g

{\displaystyle {\mathit {g}}}

by definition. We can write this in matrix form as: or For this task, implement a function (or method, procedure, subroutine, etc.) deconv to perform deconvolution (i.e., the inverse of convolution) by constructing and solving such a system of equations represented by the above matrix

A

{\displaystyle A}

for

h

{\displaystyle {\mathit {h}}}

given

f

{\displaystyle {\mathit {f}}}

and

g

{\displaystyle {\mathit {g}}}

.

h = [-8,-9,-3,-1,-6,7] f = [-3,-6,-1,8,-6,3,-1,-9,-9,3,-2,5,2,-2,-7,-1] g = [24,75,71,-34,3,22,-45,23,245,25,52,25,-67,-96,96,31,55,36,29,-43,-7]

Let's start with the solution:

object Deconvolution1D extends App {
  val (h, f) = (Array(-8, -9, -3, -1, -6, 7), Array(-3, -6, -1, 8, -6, 3, -1, -9, -9, 3, -2, 5, 2, -2, -7, -1))
  val g = Array(24, 75, 71, -34, 3, 22, -45, 23, 245, 25, 52, 25, -67, -96, 96, 31, 55, 36, 29, -43, -7)
  val sb = new StringBuilder

  private def deconv(g: Array[Int], f: Array[Int]) = {
    val h = Array.ofDim[Int](g.length - f.length + 1)

    for (n <- h.indices) {
      h(n) = g(n)
      for (i <- math.max(n - f.length + 1, 0) until n) h(n) -= h(i) * f(n - i)
      h(n) /= f(0)
    }
    h
  }

  sb.append(s"h = ${h.mkString("[", ", ", "]")}\n")
    .append(s"deconv(g, f) = ${deconv(g, f).mkString("[", ", ", "]")}\n")
    .append(s"f = ${f.mkString("[", ", ", "]")}\n")
    .append(s"deconv(g, h) = ${deconv(g, h).mkString("[", ", ", "]")}")
  println(sb.result())

}