# Log-CCDM: Distribution Matching via Multiplication-free Arithmetic Coding

Yunus Can Gültekin, Frans M. J. Willems, Alex Alvarado  Information and
Communication Theory Lab, Eindhoven University of Technology, The Netherlands
Email<EMAIL_ADDRESS>
###### Abstract

Recent years have seen renewed attention to arithmetic coding (AC). This is
thanks to the use of AC for distribution matching (DM) to control the channel
input distribution in probabilistic amplitude shaping. There are two main
problems inherent to AC: (1) its required arithmetic precision grows linearly
with the input length, and (2) high-precision multiplications and divisions
are required. Here, we introduce a multiplication-free AC-based DM technique
via three lookup tables (LUTs) which solves both problems above. These LUTs
are used to approximate the high-precision multiplications and divisions by
additions and subtractions. The required precision of our approach is shown to
grow logarithmically with the input length. We prove that this approximate
technique maintains the invertibility of DM. At an input length of 1024
symbols, the proposed technique achieves negligible rate loss ($<0.01$
bit/sym) against the full-precision DM, while requiring less than 4 kilobytes
of storage.

##  I Introduction

Distribution matching (DM) converts a binary string into a symbol sequence
with the desired distribution. DM is an essential block in probabilistic
amplitude shaping (PAS) that controls the channel input distribution [1].
Thanks to this control, PAS achieves the capacity of the additive white
Gaussian noise (AWGN) channel [2, 3]. PAS has also become popular in wireless
[4, 5] and fiber optical communications [6, 7, 8, 9].

The DM technique used when PAS was introduced was constant composition
distribution matching (CCDM) [10]. In CCDM, binary strings—which are the data
sequences in this context—are converted into amplitude sequences with a fixed
composition. By selecting this composition such that the resulting amplitude
distribution resembles a one-sided Gaussian distribution and by selecting the
signs uniformly, a Gaussian-like channel input is obtained, which increases
the achievable rates for the AWGN channel [1] and optical channels [7].

When CCDM was first introduced [10], it was implemented using arithmetic
coding (AC) [11]. AC is a source coding algorithm that represents nonuniform
source sequences by subintervals of the unit interval [12, Sec. 6.2]. Since DM
is the dual operation to compression [13, p.222], AC can be used to realize DM
in an “inverted encoder-decoder pair” setup [14] as illustrated in Fig. 1:
matching is realized via AC decoding (decompression), dematching is realized
via AC encoding (compression).

There are two main problems inherent to AC. First, the required arithmetic
precision grows linearly with the input length, which makes AC very
challenging to realize for inputs longer than a thousand symbols. Long
blocklengths are necessary to decrease the rate loss of CCDM [10, Fig. 2].
Second, multiplications and divisions are necessary to realize the algorithm.
There is a large amount of research dedicated to solving these problems in the
context of source coding, see e.g., [15] and references therein. For DM, the
first problem is solved via a finite-precision implementation in [16]. To the
best of our knowledge, there is no study solving the second problem for DM.

Figure 1: Duality of source coding (top) and DM (bottom), and the effect of
having overlapping subintervals in arithmetic coding (middle).

In this paper, we introduce “Log-CCDM”, an approximate logarithmic (log)
domain AC-based algorithm that solves both problems above. Log-CCDM works
based on three lookup tables (LUTs). High-precision multiplications and
divisions required in AC are approximated by low-precision additions and
subtractions in the log domain. The required arithmetic precision of Log-CCDM
grows logarithmically with the input length. We prove that the invertibility
of DM is maintained. We demonstrate that the performance of this approximate
algorithm (in terms of rate) depends on the sizes of the LUTs. Requiring less
than a few kilobytes (kBs), the rate loss of Log-CCDM against full-precision
CCDM (FP-CCDM) is negligible, i.e., $<0.01$ bit/sym. This performance is
achieved using 20-bit arithmetic operations which is comparable to that of the
finite-precision algorithm of [16] that requires multiplications and
divisions.

##  II Distribution Matching via Arithmetic Coding

Consider a composition $C=[n_{0},n_{1},\dotsc,n_{A-1}]$ of symbols
$m\in\mathcal{A}=\\{0,1,\dotsc,A-1\\}$, resp., where
$\sum_{a\in\mathcal{A}}n_{a}=N$ and $\mathcal{A}$ the symbol alphabet. The
corresponding set $\mathcal{C}_{\text{cc}}$ of CC symbol sequences
$\underline{x}=(x_{1},x_{2},\dotsc,x_{N})$ consists of all sequences that have
$\sum_{i=1}^{N}\mathds{1}[x_{i}=a]=n_{a}$ for $a\in\mathcal{A}$. Here
$\mathds{1}[\cdot]$ is the indicator function which is $1$ when its argument
is true and $0$ otherwise. CCDM is a shaping technique that maps $k$-bit
strings (indices) $\underline{v}=(v_{1},v_{2},\dotsc,v_{k})$ to CC symbol
sequences $\underline{x}\in\mathcal{C}_{\text{cc}}$ [10]. This is called
matching, while the reverse operation is called dematching. The matching rate
is then defined as $k/N$ bit/sym. CCDM can be realized via AC.

In AC, the binary string $\underline{v}$ is represented by a number
$d(\underline{v})\in[0,1)$ which is defined as
$d(\underline{v})\stackrel{{\scriptstyle\Delta}}{{=}}\sum_{i=1}^{k}v_{i}2^{-i}$.
Further, each symbol sequence $\underline{x}$ corresponds to a subinterval
$I(\underline{x})$ of the interval $[0,1)$. These subintervals partition the
interval $[0,1)$. During arithmetic encoding, the interval $I(\underline{x})$
is found based on $\underline{x}$, then a number $d(\underline{v})\in
I(\underline{x})$ is determined. The outcome of this process is
$\underline{v}$. During arithmetic decoding, the input $\underline{v}$ is
mapped to sequence $\underline{x}$ if $d(\underline{v})\in I(\underline{x})$.

The interval $I(\underline{x})$ can be found based on the probability model
$p_{n}(a)\stackrel{{\scriptstyle\Delta}}{{=}}\Pr\\{X_{n}=a|X_{1},X_{2},\dotsc,X_{n-1}\\}$
for $n=1,2,\dotsc,N$ and $a\in\mathcal{A}$. The base $b_{N}$ and width $w_{N}$
of the interval $I(\underline{x})=[b_{N},b_{N}+w_{N})$ are computed via the
recursions

$\displaystyle b_{n}$ $\displaystyle=$ $\displaystyle
b_{n-1}+w_{n-1}\sum_{a<x_{n}}p_{n}(a),$ (1) $\displaystyle w_{n}$
$\displaystyle=$ $\displaystyle p_{n}(x_{n})w_{n-1},$ (2)

for $n=1,2,\dotsc,N$ where $b_{0}=0$ and $w_{0}=1$. From (2), we see that the
width $w_{N}=\prod_{n=1}^{N}p_{n}(x_{n})$ which is equal to $p(\underline{x})$
via the chain rule. Thus, recursions (1)–(2) result in intervals
$I(\underline{x})$ of length $p(\underline{x})$. Typically,
$d(\underline{v})\in I(\underline{x})$ is selected as the number that leads to
the $\underline{v}$ with the shortest representation [17, Sec. 5.2.3.1]. The
minimum length of $\underline{v}$ is $\left\lceil-\log
I(\underline{x})\right\rceil$ bits, and AC generates variable-length
$\underline{v}$ in general. Here, $\log$ denotes the binary logarithm.

In the case of CCDM, the order of coding operations is inverted. At the
transmitter, arithmetic decoding is used to map $\underline{v}$ to a
$\underline{x}\in\mathcal{C}_{\text{cc}}$, while arithmetic encoding is
realized for the reverse mapping at the receiver. For CCDM, the probability
model $p_{n}(a)$ can be obtained considering the composition $C$ of the
sequence $\underline{x}$ and the composition of already-processed symbols
$(x_{1},x_{2},\dotsc,x_{n-1})$. It is given by

$p_{n}(a)=\frac{n_{a}-\sum_{i=1}^{n-1}\mathds{1}[x_{i}=a]}{N-n+1}.$ (3)

Via (3), the symbol probabilities are initialized as $p_{1}(a)=n_{a}/N$, and
recursively updated by decreasing $n_{a}$ whenever a symbol $x=a$ is
processed. From (3), we see that
$p(\underline{x})=\prod_{n=1}^{N}p_{n}(x_{n})=(\prod_{a=0}^{A-1}n_{a}!)/N!=1/|\mathcal{C}_{\text{cc}}|$
for all $\underline{x}\in\mathcal{C}_{\text{cc}}$. A one-to-one mapping from
$\underline{v}$ to $\underline{x}\in\mathcal{C}_{\text{cc}}$ is established if
each $I(\underline{x})$ contains at most one $d(\underline{v})$. Since the
intervals are of equal length $1/|\mathcal{C}_{\text{cc}}|$, the maximum $k$
which guarantees this is
$k=\left\lfloor\log|\mathcal{C}_{\text{cc}}|\right\rfloor$, and AC becomes
fixed-length coding.

######  Example 1.

(Binary-output CCDM) Consider the composition $C=[3,2]$ for
$\mathcal{A}=\\{0,1\\}$, i.e., we want to generate binary sequences of length
$N=5$ containing $2$ ones. There are $10$ such sequences and $k=3$. As an
example, let us find the CC sequence $\underline{x}$ that is mapped to
$\underline{v}=(1,1,0)$ ($d(\underline{v})=0.75$) which is written with blue
in Fig. 2. The first symbol $x_{1}$ partitions the interval $[0,1)$ in
fractions $p_{1}(0)=n_{0}/N=3/5$ and $p_{1}(1)=n_{1}/N=2/5$. Since
$d(\underline{v})=0.75\in[6/10,1)$, this interval is selected and $x_{1}=1$.
Then the second symbol $x_{2}$ partitions the interval $[6/10,1)$ in fractions
$p_{2}(0)=n_{0}/(N-1)=3/4$ and $p_{2}(1)=(n_{1}-1)/(N-1)=1/4$. Since
$d(\underline{v})=0.75\in[6/10,9/10)$, this interval is selected and
$x_{2}=0$. This procedure is repeated until $x_{5}$ and the final sequence
$\underline{x}=(1,0,0,1,0)$ is obtained.

Figure 2: CCDM for $C=[3,2]$ and $A=2$ via AC. Blue sequences
$\underline{x}=(1,0,0,1,0)$ and $\underline{v}=(1,1,0)$ (with
$d(\underline{v})=0.75)$ are mapped to each other. Base $b_{n}$ follows the
yellow path, while the width $w_{n}$ is the height of the red region, see
(1)–(2). Sequences $(0,1,0,1,0)$ and $(1,1,0,0,0)$ are not utilized since the
corresponding intervals $[0.4,0.5)$ and $[0.9,1.0)$ do not contain a number
$d(\underline{v})$ for a 3-bit $\underline{v}$.

Input: Index $\underline{v}$, composition $C=[n_{0},n_{1}]$

Output: Sequence $\underline{x}\in\\{0,1\\}^{N}$

1 Initialize: $w_{0}\leftarrow 1$, $I_{0}\leftarrow d(\underline{v})$,
$N\leftarrow n_{0}+n_{1}$

2 for  _$n=0,1,\dotsc,N-1$_ do

3 if  _$I_{n}\geq w_{n}n_{0}/(N-n)$_ then

4 $x_{n+1}\leftarrow 1$

5 $I_{n+1}\leftarrow I_{n}-w_{n}n_{0}/(N-n)$

6 $w_{n+1}\leftarrow w_{n}n_{1}/(N-n)$

7 $n_{1}\leftarrow n_{1}-1$

8

9 else

10 $x_{n+1}\leftarrow 0$

11 $I_{n+1}\leftarrow I_{n}$

12 $w_{n+1}\leftarrow w_{n}n_{0}/(N-n)$

13 $n_{0}\leftarrow n_{0}-1$

14 end if

15

16 end for

return _$\underline{x}=(x_{1},x_{2},\dotsc,x_{N})$_

Algorithm 1 FP-CCDM (Matching)

During matching, the interval $I(\underline{x})$ that includes
$d(\underline{v})$ can also be found without storing the base $b_{n}$, but
instead, by successively subtracting it from $d(\underline{v})$. The
corresponding dematching algorithm can also be realized straightforwardly. A
pseudo-code for this FP-CCDM is given in Algorithm 1 for
$\mathcal{A}=\\{0,1\\}$. The recursive subtraction of base from the input
index is realized in line 5 (highlighted in red). This algorithm can also be
realized in the log domain, which is the main idea behind Log-CCDM. Then the
width would be updated by an addition and a subtraction, instead of the
multiplication and the division in lines 6 and 11 (highlighted in blue).

##  III Log-CCDM with LUTs

We will explain Log-CCDM for the binary case for simplicity. Binary DM can be
used to approximately shape the channel inputs [18, 19, 20, 21, 22]. Extension
to nonbinary alphabets is possible for all the techniques discussed in this
section.

###  III-A Log-CCDM

We define an exponential function for positive integer $s$

$F(s)\stackrel{{\scriptstyle\Delta}}{{=}}\begin{cases}\left\lceil
M2^{-s/S}\right\rceil&\mbox{ if }\hskip 1.42271pt1\leq s\leq S,\\\ \left\lceil
M2^{-r/S}\right\rceil 2^{-d}\hfill&\mbox{ if }\hskip 1.42271pts=r+dS>S,\\\
\end{cases}$ (4)

where integers $r>0$, $d>0$. In (4), both $S$ and $M$ are positive integers.
We see from (4) that $F(s)$ can be computed for any positive integer $s$ by
storing $F(s)$ only for $s=1,2,\dotsc,S$. This requires a LUT with $S$
entries. For $s>S$, $F(s)$ can be computed only with shifts in base-2 thanks
to the $2^{-d}$ factor in (4). We assume that $M$ is an integer power of two,
and each entry of this LUT is stored with $\log M$ bits. Note that with $\log
M$ bits, only the nonnegative numbers below $M$ can be stored in an exact
manner. This, i.e., $F(s)<M$ for $1\leq s\leq S$, is ensured when $S<M$ from
(4). An example of $F(s)$ is shown in Fig. 3.

Consider Algorithm 1 realized in the binary domain. Here, $0\leq I_{n}<1$ and
$0\leq w_{n}<1$ for $n=0,1,\dotsc,N$ and hence, their integer parts are always
$0$. Thus, we neglect their integer part and focus on their fractional part.
We approximate the fractional part of $w_{n}$ by $F(s_{n})$ where
$s_{0}\stackrel{{\scriptstyle\Delta}}{{=}}1$. At step $n$ of Algorithm 1,
there are two possible choices for the width $w_{n+1}$ corresponding to
symbols $1$ and $0$, resp., see lines 6 and 11. We approximate these choices
by first defining

$s_{n+1}\stackrel{{\scriptstyle\Delta}}{{=}}\begin{cases}s_{n}-S\log(n_{1}/(n_{0}+n_{1}))\quad\mbox{if}\quad
x_{n+1}=1,\\\ s_{n}-S\log(n_{0}/(n_{0}+n_{1}))\quad\mbox{if}\quad
x_{n+1}=0.\\\ \end{cases}$ (5)

Then we observe from (4) that $F(r+dS)=2^{-d}F(r)$ which implies $F(r-S\log
K)=KF(r)$ for integer $S\log K$. Then

$F(s_{n+1})=\begin{cases}F\left(s_{n}-S\log\left(\frac{n_{1}}{n_{0}+n_{1}}\right)\right)\approx
F(s_{n})\frac{n_{1}}{n_{0}+n_{1}},\\\
F\left(s_{n}-S\log\left(\frac{n_{0}}{n_{0}+n_{1}}\right)\right)\approx
F(s_{n})\frac{n_{0}}{n_{0}+n_{1}},\\\ \end{cases}$ (6)

for $x_{n+1}=1,0$, resp., for $n=1,2,\dotsc,N$. In the context of Algorithm 1,
(5) corresponds to the width updates in lines 6 and 11. Updating $w_{n}$ to
$w_{n+1}$ using multiplications is equivalent to updating $s_{n}$ to $s_{n+1}$
using subtractions.

However, we observe that (5) requires the computation of $\log$ function with
FP which is typically no less complex than a multiplication.

$5$$10$$15$$20$$25$$30$$10$$15$$20$$25$$30$$s$$M2^{-s/S}$$F(s)$
(4)$\text{Lg}^{+}(n)$ (7)$\text{Lg}^{-}(n)$
(8)$5$$10$$15$$20$$25$$30$$0$$20$$40$$60$$80$$n$

Figure 3: Exponential function $F(s)$ for $1\leq s\leq 2S$, and log functions
$\text{Lg}^{+}$ and $\text{Lg}^{-}$ for $1\leq n\leq N$ where $S=16$, $M=32$,
and $N=32$. $F(s)$ can be computed for any positive integer $s$ by storing
$F(s)$ only for $1\leq s\leq S$ (filled circles) in a LUT. $\text{Lg}^{+}$ and
$\text{Lg}^{-}$ can be stored in two LUTs.

To circumvent this complexity, we define two logarithmic functions (s.t. means
such that)

$\displaystyle\text{Lg}^{+}(n)$
$\displaystyle\stackrel{{\scriptstyle\Delta}}{{=}}$
$\displaystyle\max_{s=1,2,\dotsc,S}\min_{\begin{subarray}{c}\Delta=0,1,\dotsc\\\
F(s)\geq nF(s+\Delta)\end{subarray}}\\{\Delta\\},$ (7)
$\displaystyle\text{Lg}^{-}(n)$
$\displaystyle\stackrel{{\scriptstyle\Delta}}{{=}}$
$\displaystyle\min_{s=1,2,\dotsc,S}\max_{\begin{subarray}{c}\Delta=0,1,\dotsc\\\
F(s)\leq nF(s+\Delta)\end{subarray}}\\{\Delta\\},$ (8)

for $n=1,2,\dotsc,N$. This computation can be realized offline. The resulting
functions can be stored in two LUTs, each having $N$ entries. Examples of
$\text{Lg}^{+}(n)$ and $\text{Lg}^{-}(n)$ are shown in Fig. 3.

We approximate multiplications and divisions involving $F(s)$ and an integer
$n$ by

$\displaystyle nF(s)$ $\displaystyle\approx$ $\displaystyle
F\left(s-\text{Lg}^{+}(n)\right),$ (9) $\displaystyle\frac{F(s)}{n}$
$\displaystyle\approx$ $\displaystyle F\left(s+\text{Lg}^{-}(n)\right),$ (10)

resp. The relations in (9)–(10) are approximate due to the way $\text{Lg}^{+}$
and $\text{Lg}^{-}$ are defined in (7)–(8), and due to the ceiling operation
in (4). Finally, combining (6) and (9)–(10),

$F(s_{n+1})=\begin{cases}F\left(s_{n}-\text{Lg}^{+}(n_{1})+\text{Lg}^{-}(n_{0}+n_{1})\right),\\\
F\left(s_{n}-\text{Lg}^{+}(n_{0})+\text{Lg}^{-}(n_{0}+n_{1})\right),\end{cases}$
(11)

for symbols 1 and 0, resp. This way, the FP-CCDM in Algorithm 1 is converted
into the Log-CCDM in Algorithm 2 by: (1) representing the subinterval width
$w_{n+1}$ by $F(s_{n+1})$, and (2) keeping track of this width through
$s_{n+1}$ which is updated via (11) in lines 6 and 11 (highlighted in blue).
The rest of the algorithms are identical.

Input: Index $\underline{v}$, composition $C=[n_{0},n_{1}]$

Output: Sequence $\underline{x}\in\\{0,1\\}^{N}$

1 Initialize: $s_{0}\leftarrow 1$, $I_{0}\leftarrow d(\underline{v})$,
$N\leftarrow n_{0}+n_{1}$

2 for  _$n=0,1,\dotsc,N-1$_ do

3 if  _$I_{n}\geq
F\left(s_{n}-\text{Lg}^{+}(n_{0})+\text{Lg}^{-}(N-n)\right)$_ then

4 $x_{n+1}\leftarrow 1$

5 $I_{n+1}\leftarrow
I_{n}-F\left(s_{n}-\text{Lg}^{+}(n_{0})+\text{Lg}^{-}(N-n)\right)$

6 $s_{n+1}\leftarrow s_{n}-\text{Lg}^{+}(n_{1})+\text{Lg}^{-}(N-n)$

7 $n_{1}\leftarrow n_{1}-1$

8

9 else

10 $x_{n+1}\leftarrow 0$

11 $I_{n+1}\leftarrow I_{n}$

12 $s_{n+1}\leftarrow s_{n}-\text{Lg}^{+}(n_{0})+\text{Lg}^{-}(N-n)$

13 $n_{0}\leftarrow n_{0}-1$

14

15 end if

16

17 end for

return _$\underline{x}=(x_{1},x_{2},\dotsc,x_{N})$_

Algorithm 2 Log-CCDM (Matching)

###  III-B Representability of Data Sequences

When AC is used for compression, if the arithmetic operations are implemented
with finite-precision (or in any approximate way), the decodability of the
code becomes questionable. Decodability is ensured only when the subdivisions
do not create overlapping subintervals, which would make two different source
sequences (the red circles in Fig. 1) mapped to the same code sequence (the
blue circle). This makes uniquely decodability during decompression impossible
[23]. On the other hand, gaps between subintervals only decrease the
efficiency of the source code, i.e., increases its rate.

When AC is used for DM which is a dual of source coding, see Sec. I, the dual
of decodability is representability [14]. AC creates an invertible mapping
from data sequences to CC sequences only if the subintervals do not have gaps
in between. Overlaps are allowed. As discussed above via Fig. 1, overlaps make
two amplitude sequences mapped to the same data sequence. However, since
matching is realized first in the case of DM (at the transmitter), this does
not create a problem: some channel sequences are just never generated. This
only decreases the efficiency of the code, i.e., decreases its rate.

With an FP implementation, AC creates subintervals that neither overlap nor
have gaps, satisfying the decodability and representability criteria as in
Fig. 2. For our Log-CCDM algorithm, the representability, i.e., “no gaps”,
criterion can be expressed from (11) as [14, eq. (14)]

$\displaystyle F(s_{n})$ $\displaystyle\leq$ $\displaystyle
F\left(s_{n}-\text{Lg}^{+}(n_{1})+\text{Lg}^{-}(n_{0}+n_{1})\right)$ (12)
$\displaystyle+\hskip
2.84544ptF\left(s_{n}-\text{Lg}^{+}(n_{0})+\text{Lg}^{-}(n_{0}+n_{1})\right).$

######  Lemma 1.

The condition in (12) is satisfied for $F(s)$, $\text{Lg}^{+}(n)$, and
$\text{Lg}^{-}$ defined in (4), (7), and (8), resp.

###### Proof.

First, observe that the following inequalities are satisfied from (7)–(8) by
definition for any positive integer $s$:

$\displaystyle F(s-\text{Lg}^{+}(n))$ $\displaystyle\geq$ $\displaystyle
nF(s),$ (13) $\displaystyle F(s+\text{Lg}^{-}(n))$ $\displaystyle\geq$
$\displaystyle\frac{F(s)}{n}.$ (14)

Then for the first case in (11), we can write

$\displaystyle F(s_{n+1})$ $\displaystyle=$ $\displaystyle
F\left(s_{n}-\text{Lg}^{+}(n_{1})+\text{Lg}^{-}(n_{0}+n_{1})\right)$ (15)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:pluslogconsequence}}}{{\geq}}$
$\displaystyle n_{1}F\left(s_{n}+\text{Lg}^{-}(n_{0}+n_{1})\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:minuslogconsequence}}}{{\geq}}$
$\displaystyle\frac{n_{1}F\left(s_{n}\right)}{n_{0}+n_{1}}.$

Similarly, for the second case in (11), we can write

$F(s_{n+1})\geq\frac{n_{0}F\left(s_{n}\right)}{n_{0}+n_{1}}.$ (16)

Combined, (15) and (16) imply that (12) is satisfied. ∎

##  IV Properties of Log-CCDM

###  IV-A Input Length of the Matcher

The final width for any input in Algorithm 2 is $F(s_{N})$ where

$s_{N}=s_{0}+\underbrace{\sum_{i=1}^{n_{0}+n_{1}}\text{Lg}^{-}(i)-\sum_{j=1}^{n_{0}}\text{Lg}^{+}(j)-\sum_{t=1}^{n_{1}}\text{Lg}^{+}(t)}_{\stackrel{{\scriptstyle\Delta}}{{=}}\gamma}.$
(17)

Thus, all CC sequences are represented with an interval of identical width.
This allows us to represent each interval with a fixed length $k$-bit index as
discussed in Sec. II.

There are $F(s_{0})/F(s_{N})$ CC sequences, i.e.,
$|\mathcal{C}_{\text{cc}}|=F(s_{0})/F(s_{N})$. Then as in Sec. II,

$\displaystyle k$ $\displaystyle=$
$\displaystyle\left\lfloor\log|\mathcal{C}_{\text{cc}}|\right\rfloor=\left\lfloor\log\frac{F(s_{0})}{F(s_{N})}\right\rfloor=\left\lfloor\log\frac{F(s_{0})}{F(s_{0}+\gamma)}\right\rfloor$
(18) $\displaystyle\stackrel{{\scriptstyle\eqref{eq:expfunc}}}{{=}}$
$\displaystyle\left\lfloor\log\frac{F(s_{0})}{2^{-\left\lfloor\gamma/S\right\rfloor}F(s_{0})}\right\rfloor=\left\lfloor\frac{\gamma}{S}\right\rfloor.$

The parameters $\gamma$ and $k$ can be computed offline.

###  IV-B Storage Complexity and Arithmetic Precision

The storage complexity of Log-CCDM is $S\log M+2N(\log S+\log\log N)$ bits. To
store $F(s)$ in (4), we need a LUT with $S$ entries, each stored with $\log M$
bits as discussed in Sec. III-A. Thus, the storage requirement of this LUT is
$S\log M$ bits. From (4) and (9)–(10), it can be shown that both
$\text{Lg}^{+}(n)$ and $\text{Lg}^{-}(n)$ are approximately equal to $S\log
n$. Therefore, the entries in the corresponding LUTs can be stored with
approximately $\log S+\log\log N$ bits assuming $S$ and $N$ are integer powers
of two. Thus, the total storage requirement of these two LUTs is $2N(\log
S+\log\log N)$ bits.

In line 5 of Algorithm 2 (highlighted in red), values of $F(\cdot)$ are
recursively subtracted from the input index. These subtractions require an
arithmetic precision of $\log M+\log N$ bits assuming again $N$ is an integer
power of two. The proof of this will consist of a lemma and a theorem.

######  Lemma 2.

If $I_{n}<F(s_{n})$, then Algorithm 2 guarantees that $I_{n+1}<F(s_{n+1})$.
This implies that if $I_{0}<F(s_{0})$, then all $I_{n}$ for $n=0,1,\dotsc,N$
satisfy $I_{n}<F(s_{n})$.

###### Proof.

We define
$s_{n,0}\stackrel{{\scriptstyle\Delta}}{{=}}s_{n}-\text{Lg}^{+}(n_{0})+\text{Lg}^{-}(N-n)$
and
$s_{n,1}\stackrel{{\scriptstyle\Delta}}{{=}}s_{n}-\text{Lg}^{+}(n_{1})+\text{Lg}^{-}(N-n)$
for $n=0,1,\dotsc,N-1$. Note that $s_{n,0}$ and $s_{n,1}$ are the candidates
for $s_{n+1}$ in lines 11 and 6 of Algorithm 2. We first observe that

$I_{n}<F(s_{n})\stackrel{{\scriptstyle\eqref{eq:overlapcondition}}}{{\leq}}F(s_{n,0})+F(s_{n,1}).$
(19)

Then there are two options at the $n^{\text{th}}$ step of Algorithm 2:

  * •

If $I_{n}\geq F(s_{n,0})$ (line 3), then $s_{n+1}=s_{n,1}$ and

$\displaystyle I_{n+1}$ $\displaystyle=$ $\displaystyle I_{n}-F(s_{n,0})$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:lemma1}}}{{<}}$ $\displaystyle
F(s_{n,0})+F(s_{n,1})-F(s_{n,0})=F(s_{n+1}).$

  * •

If $I_{n}<F(s_{n,0})$ (line 8), then $s_{n+1}=s_{n,0}$ and

$\displaystyle I_{n+1}=I_{n}<F(s_{n,0})=F(s_{n+1}).$

Since $I_{0}<1\leq F(s_{0}=1)$ due to (4) and Algorithm 2, we conclude that
$I_{n}<F(s_{n})$ for $n=0,1,\dotsc,N$. We note that this proof is similar to
the proof of [24, Lemma 1]. ∎

######  Theorem 1.

The subtraction $I_{n}-F(s_{n,0})$ in line 5 of Algorithm 2 requires an
arithmetic precision of at most $\log M+\log N$ bits assuming $N$ is an
integer power of two.

###### Proof.

First, observe from (15) that

$\frac{F(s_{n,0})}{F(s_{n})}\geq\frac{n_{0}}{n_{0}+n_{1}}\geq\frac{1}{N}.$
(20)

Thus, since $I_{n}<F(s_{n})$ from Lemma 2, the subtrahend of the subtraction
$I_{n}-F(s_{n,0})$ in line 5 of Algorithm 2 can be at most $N$ times smaller
than its minuend. Since each entry of the LUT of $F(\cdot)$ is $\log M$-bit
long, this subtraction requires an arithmetic precision of at most $\log
M+\log N$ bits. ∎

######  Remark 1.

Log-CCDM can be implemented with two $(\log M+\log N)$-bit shift registers.
The $k$-bit input index (and some trailing zeros if necessary) is gradually
loaded into the first register, which stores the minuend. The $\log M$-bit
$F(\cdot)$ values are loaded into the second register, which stores the
subtrahend. The dematching can be implemented with the same principle via
$(\log M+\log N)$-bit additions.

######  Remark 2.

It is not straightforward to evaluate the complexity of FP-CCDM [25, Sec. 6].
In this work, we have transformed FP-CCDM, which requires no storage but is
based on multiplications and divisions, into Log-CCDM, which requires a small
amount of storage but is based on additions and subtractions. Then the
selection among these two depends on how costly the multiplications and
divisions are in comparison to a certain amount of storage for given hardware.

###  IV-C Rate Loss

There are two sources of inaccuracies in Log-CCDM. The first is due to (4)
which leads to an imprecise representation of the log of the interval width.
The second is due to (7) and (8), and then to (13) and (14) which lead to
imprecise multiplications (with $n_{0}$ or $n_{1}$) and divisions (with
$n_{0}+n_{1}$). These two inaccuracies lead to overlapping intervals as
discussed in Sec. III-B. Thus, some CC sequences that would be generated by
FP-CCDM are never produced by Log-CCDM, which decreases the rate $k/N$,
causing a rate loss.

In Fig. 4, we show $k/N$ as a function of $N$ for a composition of
$C=[0.75N,0.25N]$ for FP-CCDM and Log-CCDM with different $(S,M)$ pairs.
First, we see that FP-CCDM is asymptotically optimum for large $N$ as shown in
[10]. This is in the sense that it has a matching rate
$\stackrel{{\scriptstyle\Delta}}{{=}}k_{\max}/N$ converging to the (binary)
entropy $H(0.75)=0.8113$ bits of the resulting distribution, see the black
curve in Fig. 4. However, Log-CCDM is suboptimal, i.e., it does not converge
to the entropy. By increasing $S$ and $M$, this rate can be made closer to the
entropy, while the required storage increases, see Sec. IV-B.

Next, we see that for increasing $S$ and $M$, the matching rate of Log-CCDM
gets closer to $k_{\max}/N$. When using LUTs with $S=512$ and $N\leq 1024$
entries (the red circles), the gap to $k_{\max}/N$ is around 0.007 bit/sym.
The gap increases to 0.03 bit/sym for LUTs with $S=128$ and $N\leq 1024$
entries (the blue curve with squares). Thus, there is a trade-off between the
rate loss with respect to $k_{\max}/N$ and the table sizes. Assume we operate
at $N=1024$, $S=512$, $M=1024$, and $k/N=0.7988<0.8063=k_{\max}/N$ bit/sym
(the filled red circle). Then the required storage for the three LUTs is
$S\log M+2N(\log S+\log\log N)=3.79$ kBs (bottom-right inset figure), and the
required arithmetic precision is $\log M+\log N=20$ bits (top-left inset
figure), see Sec. IV-B.

Figure 4: Rate $k/N$ of Log-CCDM with $(S,M)$. Top-left inset: Required
arithmetic precision in bits. Bottom-right inset: Required storage in kBs.

Last, we see that for $S=256$, the required storage is virtually identical
with $M=512$ and $1024$ (bottom-right inset figure). However, the rate loss of
$(S=256,M=1024)$ (dashed green) is smaller. For instance, the same rate loss
as $(S=512,M=1024,N=1024)$ (filled red circle) is obtained via
$(S=256,M=1024,N=1024)$ (dashed green), requiring $3.22$ kBs of storage
instead of $3.79$. This demonstrates that $M$ plays a more important role in
determining the rate loss. For a given $M$, a smaller $S$ can be chosen to
decrease the storage complexity, since the rate loss is relatively insensitive
to the changes in $S$.

##  V Conclusion

In this paper, we have introduced Log-CCDM: an approximate algorithm to
realize arithmetic-coding-based constant composition distribution matching.
Log-CCDM operates in the logarithmic domain and is based on three simple
lookup tables (LUTs). Thanks to these LUTs, it is possible to realize CCDM (1)
with an arithmetic precision that grows logarithmically with input length
(instead of linearly), and (2) only using additions and subtractions (instead
of multiplications and divisions). This decreases the computational
complexity, however, increases the storage complexity (to a few kilobytes) due
to the LUTs. The performance of Log-CCDM in terms of rate depends on the sizes
of these LUTs.

Acknowledgements: The work of Yunus Can Gültekin and Alex Alvarado has
received funding from the European Research Council under the European Union’s
Horizon 2020 research and innovation programme via the Starting grant FUN-
NOTCH (grant agreement ID: 757791) and via the Proof of Concept grant SHY-FEC
(grant agreement ID: 963945).

## References

  * [1] G. Böcherer, F. Steiner, and P. Schulte, “Bandwidth efficient and rate-matched low-density parity-check coded modulation,” _IEEE Trans. Commun._ , vol. 63, no. 12, pp. 4651–4665, Dec. 2015.
  * [2] G. Böcherer, “Probabilistic signal shaping for bit-metric decoding,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Honolulu, HI, USA, June 2014, pp. 431–435.
  * [3] Y. C. Gültekin, A. Alvarado, and F. M. J. Willems, “Achievable information rates for probabilistic amplitude shaping: An alternative approach via random sign-coding arguments,” _Entropy_ , vol. 22, no. 7: 762, July 2020.
  * [4] P. Schulte and F. Steiner, “Divergence-optimal fixed-to-fixed length distribution matching with shell mapping,” _IEEE Wireless Commun. Lett._ , vol. 8, no. 2, pp. 620–623, Apr. 2019.
  * [5] Y. C. Gültekin, W. J. van Houtum, A. Koppelaar, and F. M. J. Willems, “Enumerative sphere shaping for wireless communications with short packets,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 2, pp. 1098–1112, Feb. 2020.
  * [6] F. Buchali, F. Steiner, G. Böcherer, L. Schmalen, P. Schulte, and W. Idler, “Rate adaptation and reach increase by probabilistically shaped 64-QAM: An experimental demonstration,” _J. Lightw. Technol._ , vol. 34, no. 7, pp. 1599–1609, Apr. 2016.
  * [7] T. Fehenberger, A. Alvarado, G. Böcherer, and N. Hanik, “On probabilistic shaping of quadrature amplitude modulation for the nonlinear fiber channel,” _J. Lightw. Technol._ , vol. 34, no. 21, pp. 5063–5073, Nov. 2016.
  * [8] W. Idler, F. Buchali, L. Schmalen, E. Lach, R. Braun, G. Böcherer, P. Schulte, and F. Steiner, “Field trial of a 1 Tb/s super-channel network using probabilistically shaped constellations,” _J. Lightw. Technol._ , vol. 35, no. 8, pp. 1399–1406, Apr. 2017.
  * [9] A. Amari, S. Goossens, Y. C. Gültekin, O. Vassilieva, I. Kim, T. Ikeuchi, C. Okonkwo, F. M. J. Willems, and A. Alvarado, “Introducing enumerative sphere shaping for optical communication systems with short blocklengths,” _J. Lightw. Technol._ , vol. 37, no. 23, pp. 5926–5936, Dec. 2019.
  * [10] P. Schulte and G. Böcherer, “Constant composition distribution matching,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 1, pp. 430–434, Jan. 2016.
  * [11] T. V. Ramabadran, “A coding scheme for m-out-of-n codes,” _IEEE Trans. Commun._ , vol. 38, no. 8, pp. 1156–1163, Aug. 1990.
  * [12] D. J. MacKay, _Information Theory, Inference, and Learning Algorithms_. Cambridge, UK: Cambridge University Press, 2003.
  * [13] R. Fischer, _Precoding and Signal Shaping for Digital Transmission_. New York, NY, USA: John Wiley & Sons, 2002.
  * [14] G. N. N. Martin, G. G. Langdon, and S. J. P. Todd, “Arithmetic codes for constrained channels,” _IBM J. of Research and Develop._ , vol. 27, no. 2, pp. 94–106, Mar. 1983.
  * [15] T. Tjalkens, “Efficient and fast data compression codes for discrete sources with memory,” Ph.D. dissertation, Technische Universiteit Eindhoven, The Netherlands, 1987.
  * [16] M. Pikus, W. Xu, and G. Kramer, “Finite-precision implementation of arithmetic coding based distribution matchers,” in _Proc. IEEE Global Commun. Conf. (GLOBECOM)_ , Waikoloa, HI, USA, Dec. 2019.
  * [17] K. Sayood, _Lossless Compression Handbook_. Elsevier Science, 2002.
  * [18] A. Guillén i Fàbregas and A. Martinez, “Bit-interleaved coded modulation with shaping,” in _Proc. IEEE Inf. Theory Workshop_ , Dublin, Ireland, Aug.-Sep. 2010.
  * [19] M. Pikus and W. Xu, “Bit-level probabilistically shaped coded modulation,” _IEEE Commun. Lett._ , vol. 21, no. 9, pp. 1929–1932, Sep. 2017\.
  * [20] F. Steiner, P. Schulte, and G. Böcherer, “Approaching waterfilling capacity of parallel channels by higher order modulation and probabilistic amplitude shaping,” in _Proc. Conf. on Inf. Syst. and Sci. (CISS)_ , Princeton, NJ, USA, Mar. 2018.
  * [21] M. Pikus and W. Xu, “Arithmetic coding based multi-composition codes for bit-level distribution matching,” in _IEEE Wireless Commun. and Netw. Conf. (WCNC)_ , Marrakesh, Morocco, April 2019.
  * [22] Y. C. Gültekin, W. J. van Houtum, A. Koppelaar, and F. M. J. Willems, “Partial enumerative sphere shaping,” in _Proc. IEEE Veh. Technol. Conf. (VTC-Fall)_ , Honolulu, HI, USA, Sep. 2019.
  * [23] J. J. Rissanen and G. G. Langdon, “Arithmetic coding,” _IBM J. of Research and Develop._ , vol. 23, no. 2, pp. 149–162, Mar. 1979.
  * [24] Y. C. Gültekin, F. M. J. Willems, W. J. van Houtum, and S. Şerbetli, “Approximate enumerative sphere shaping,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Vail, CO, USA, June 2018, pp. 676–680.
  * [25] Y. C. Gültekin, T. Fehenberger, A. Alvarado, and F. M. J. Willems, “Probabilistic shaping for finite blocklengths: Distribution matching and sphere shaping,” _Entropy_ , vol. 19, no. 5: 581, May 2020.


# A Proposal for Foley Sound Synthesis Challenge

###### Abstract

“Foley” refers to sound effects that are added to multimedia during post-
production to enhance its perceived acoustic properties, e.g., by simulating
the sounds of footsteps, ambient environmental sounds, or visible objects on
the screen. While foley is traditionally produced by _foley artists_ , there
is increasing interest in automatic or machine-assisted techniques building
upon recent advances in sound synthesis and generative models. To foster more
participation in this growing research area, we propose a challenge for
automatic foley synthesis. Through case studies on successful previous
challenges in audio and machine learning, we set the goals of the proposed
challenge: rigorous, unified, and efficient evaluation of different foley
synthesis systems, with an overarching goal of drawing active participation
from the research community. We outline the details and design considerations
of a foley sound synthesis challenge, including task definition, dataset
requirements, and evaluation criteria.

Index Terms—  Foley, sound synthesis, generative models

##  1 Introduction

Foley, or foley sound, refers to the reproduction of everyday sound effects
that are added to multimedia to enhance the audio quality [1]. In professional
media production such as films and TV shows, the use of foley is widespread;
including sound events (footsteps, gunshots, cars, crowds) and environmental
effects (rain, wind, snow). To meet the demands for various acoustic events,
post-production studios usually own a large sound effect catalog. To obtain a
perfectly matched sound effect, it is common to edit the existing sound
effects or record a new one. The recording process may need to be creative or
even artistic. For example, a common trick of ‘Corn starch in a leather pouch
makes the sound of snow crunching’ is introduced in Wikipedia. As much as it
may sound interesting, it is a challenging and tedious process, yet necessary
to be done for many sound events in multimedia content.

The benefit of foley sound synthesis technology is evident; to make the
workflow more efficient. Recently, researchers started to apply deep neural
networks to generate foley sounds, motivated by the recent success in the
generation of speech and music signals [2, 3]. Nevertheless, It is in its
early days for the problem - there is no standard in problem definition,
dataset, and evaluation.

One effective way to make collective research progress is to establish a
challenge. Setting a standard problem definition and evaluation schemes is
already a success, which is naturally done during specifying a challenge.
Challenges also stimulate research communities by rewarding successful
research outcomes explicitly.

In this paper, we propose a foley sound synthesis challenge. Our goal is to
discuss ideas about the proposed challenge, which is relevant to DCASE, and
position this proposal to ultimately create an official challenge in the
upcoming DCASE workshops. We review recent machine learning challenges in
audio, speech, and music research in Section 2 and existing works and datasets
in Section 3. In Section 4, we provide a proposal for foley sound synthesis
challenge that includes problem definition, datasets, and evaluation metrics.
We conclude the paper in Section 5.

##  2 Case Study: Research Challenges

In this section, we review five existing research challenges: Blizzard
Challenge, CHiME, DCASE, Music Demixing challenge, and AI Song Contest. The
former three are relatively mature while the latter two started after 2020.
All of them started along with the increasing popularity of the research
problems and have contributed to the continued growth by defining the tasks,
providing common datasets, and performing reliable evaluation.

The Blizzard Challenge started in 2005 “in order to better understand
different speech synthesis techniques on a common dataset” [4]. In their first
challenge, the participants submitted synthesized speech on five text genres
including novels and news. To focus on speech synthesis techniques and not on
text analysis techniques, relatively simple texts were selected by the
organizers. The results were evaluated by three categories of listeners –
speech experts, volunteers (‘random’ users), and US undergraduates. The
evaluation was performed in a fully subjective manner. For simpler three
genres, the listeners were asked to rate them on a 5-point scale; while for
the other two genres, they were to transcribe what they hear so that the
speech intelligibility can be assessed. It remains to be an important annual
event in speech synthesis research until now.

The CHiME challenge on speech separation and recognition was proposed and
started in 2011 as a refined version of previous, similar challenges [5, 6].
The refinement includes modernization of the problem definition (types of
noise, signal mixing models, etc), adjustment of the difficulty, and
introduction of more realistic datasets/evaluation metrics. For researchers,
CHiME remains to be one of the most important venues where novel methods are
introduced and tested on their rigorously created datasets.

Detection and Classification of Acoustic Scenes and Events (DCASE) is one of
the most active and successful challenges in the field of audio research [7,
8]. As a part of IEEE AASP workshop, the first DCASE hosted two tasks –
acoustic scene classification and sound event detection – and accepted 21
systems. Six papers were presented in the DCASE poster session in WASPAA 2013
later. In 2016, DCASE started to host is own workshop along with the
challenge. In 2021, DCASE had 394 submissions for six tasks and is recognized
as the most relevant and prominent academic venue in acoustic scene analysis.
The scope of DCASE has been expanded towards some highly practical
applications (low-complexity acoustic scene classification and anomaly
detection for machine monitoring), bioacoustics (mammals and bird sound
understanding), and natural language understanding (audio captioning and
natural language queries).

Demixing challenge and AI Song Contest are founded 2021 and 2020 [9, 10]. In
Demixing challenge, participants submit their music source separation systems
with specifying whether external datasets were used or not. Although objective
metrics in source separation have limits in measuring perceptual quality, an
objective metric (signal-to-distortion ratio) was used to evaluate the systems
since it is known to represent the performance of source separation fairly
well. Conversely, in AI Song Contest, participants submit final tracks which
are then evaluated purely subjectively – by judges and online votes. Given the
artistic aspect of the task, it is a reasonable choice, although the details
such as the balance between judges and public votes may be subject to change.

##  3 Backgrounds

###  3.1 Previous Works on Foley Sound Synthesis

Foley sound synthesis (FSS) has been studied using traditional audio synthesis
approaches [11, 12, 13, 14]. The system introduced in [11] generates sounds
that are synchronized to motions in a virtual environment. In [12, 13, 14],
researchers focused on generating more realistic footstep sounds.

In the more recent, data-driven approaches, the target sound categories have
expanded significantly by researchers taking advantage of deep generative
models such as GANs and WaveNet [15, 2, 3]. The authors of [16] proposed the
first deep learning based system that generates the sounds in a video dataset,
‘The Greatest Hits’, which was also introduced in the same paper. This dataset
consists of recordings of special and artificial actions - hitting and
scratching a drum stick on various types of surfaces. Regarding the limited
variety of actions and acoustic events, the proposed system is a solution to a
simplified foley generation. Still, the system needs to learn the type and
timing of the visual events and generate a relevant audio signal.

There are also systems that generate a wider range of foley sounds, for
example, fireworks, dog barking, footsteps, gunshots, etc. These works are
based on more realistic datasets, such as AudioSet, VEGAS, and VGGSound [17,
18, 19], that consist of videos in the wild. For generating video-synchronized
FSS, GANs [20, 21, 22, 23] have been a popular method. They all have a similar
concept of generative model being conditioned by a visual encoder to
synthesize STFTs or waveforms. But there are some differences in the input
types of the sound generation models. In [20, 21], the sound generator modules
are conditioned by an embedding of the input video. Particularly in [21], the
sound generator is conditioned by a visual feature that is co-trained with the
corresponding audio feature, so that the visual model can learn to focus on
visual objects that are relevant to audio. In [22], the authors used the
visual action class and the visual action spectrogram to condition the sound
generator. In [23], the authors used a VQ-GAN model which is a combination of
VQ-VAE and an adversarial loss.

Majorities of the aforementioned works are based on visual queries, making the
system follow the workflow of foley artists. As a consequence, FSS systems are
often required to have a visual understanding module. In [24, 25], for
example, three modalities – text, vision, and audio – are combined using pre-
trained CLIP encoders [26], and these encoders are utilized for subtasks like
classification, retrieval, etc.

Based on the recent progress in models and datasets, there is strong evidence
for us to believe that the foley sound synthesis is at its tipping point.
There are many powerful audio generative models, e.g., auto-regressive models
[23], VAEs [27, 23], GANs [22, 20], and diffusion-based models [28]. Visual
understanding models are mature enough to be used in various applications.
Moreover, there are audio-visual datasets that have rich information as we
will review more deeply in the next section.

###  3.2 Existing Datasets

In this section, we first review four video datasets – AudioSet [17], VEGAS
[18], VGGSound [19] and The Greatest Hits [16]. These datasets have been used
in the previous FSS works [16, 18, 29, 22, 21]. We also review three more
datasets that are based on Freesound.org, an online sound database:
UrbanSound8k [30], FSDKaggle2018 [31], and Clotho [32].

Video datasets have been the main source of data in the previous FSS research.
AudioSet [17] is a 5800-hour video dataset from YouTube. It consists of
10-second clips which are manually labeled with 527 audio event classes. Since
all the videos are sampled from YouTube, low audio and video quality can be a
problem. VEGAS [18] is a curated subset of AudioSet, 55-hour in total and
7-second on average. Its creators selected 10 classes and filtered the items
to include videos that have a direct audio-visual relationship only. VGGSound
[19] has more than 550 hours of 10-second video clips that cover 310 classes
of sound events. Similar to VEGAS, the creators carefully selected samples to
remove videos that have a weak audio-visual relationship. The Greatest Hits
[16] is a dataset that consists of action-sound pair videos, hitting and
scratching a drum stick on various surfaces, as explained in Section 3.1.

Audio datasets without visual information can be also a good source of data
for the FSS task. Urbansound8k [30] is a sound dataset that includes 8,732
short audio segments. It has been a useful source for the acoustic event
classification task. However, the items in this dataset are 4-second segments
that were trimmed from longer audio files, which reduces the overall sound
diversity of the dataset. FSDKaggle2018 [31] contains 11,073 audio files that
are labeled with 41 classes, following the AudioSet ontology. The items were
sampled from Freesound and then manually annotated on MTurk. Clotho [32] is a
dataset that was created for the audio captioning task. Each audio file has 5
captions; i.e., its 4,981 audio files are provided with 24,905 audio captions.
Audio samples are 15 to 30 second in duration and captions are 8 to 20 words.
This can be potentially used to develop a text-query FSS system.

None of the existing datasets provides clean audio samples as desired when
using foley sounds. It may be possible to generate high-quality foley sounds
using noisy sounds. However, in the initial version of FSS challenge, we
believe it would be better to have a dataset with high quality foley sounds to
simplify the task.

##  4 Foley Sound Synthesis Challenge

###  4.1 Consideration on FSS Problem Definition

A FSS problem can be defined by specifying several aspects. In this section,
we first review those aspects, which are followed by the details of our
proposal. We propose to initiate the challenge with a narrow and strict
version while leaving definitions of more complicated systems for the future.

Type of sound \- Foley can be categorized into two classes: i) one that
belongs to a single acoustic event (e.g., gunshot) or ii) one that determines
the atmosphere/ambience of a scene (e.g., rain or room tone).

Reality of acoustic event \- Some foley sounds are bound to realistic objects
or acoustic events, e.g., honks of existing car models, dog barks, door
closing sounds, etc. Others are rather outcomes of human imagination, e.g.,
laser guns or dinosaurs. Due to the lack of reference, the generation of the
sound of the latter is rather an art, making it difficult to evaluate either
objectively or subjectively.

Type of input query \- It may seem natural for FSS systems to take video as
input as human sound engineers and foley artists do. However, there is a
drawback if the FSS problem is formulated in such a way. Automatic video-to-
sound generation is a combination of multiple machine learning problems that
include not only audio synthesis but also video understanding. This would make
evaluation more complicated than audio quality assessment, which is our
primary focus. A simpler alternative is text-to-sound where the text may be a
description of a scene or a sound. Even further, the simplest problem
formulation is perhaps a system that takes a sound category as input (e.g. a
one-hot-vector).

Final audio format \- The simplest form of generated foley sound would be an
anechoic single-channel audio signal. One can also consider adding more audio
processing such as multi-channel mixing and reverberation.

###  4.2 Our Suggestion: Progressive Approach

After taking those considerations into account, we suggest a progressive
approach as described below, starting from the simplest problem definition and
moving towards complicated ones as the challenge evolves over years.

Level 1: Categorical sound generation

The most simplified form of the foley generation problem consists of
generating individual sound clips from categorical identifiers (_footsteps_ ,
_rain_ , etc). This formulation is useful for constructing or expanding a
sample library from which foley artists could select clips to use in a
particular scene. Systems would be evaluated by (perceptual) quality of
generated audio and diversity of generated samples for each category.

Level 2: Sequential generation from text description

Expanding from level 1, this formulation would provide a textual description
of the scene as input, from which systems would generate corresponding audio
clips. This is intended to model both the clip generation task from level 1
and the composition of individual clips into a plausible acoustic scene. Each
textual prompt would contain one or more sound events, and systems would be
evaluated by the criteria of level 1, and by relevance and coverage in
response to the prompt.

Level 3: Sequential generation from video

The next more advanced formulation would work directly from the video
sequence, bypassing categorical and textual description entirely. This can be
seen as a minimal ‘fully automated’ foley system in the sense that no manual
intervention is necessary to describe or compose the scene. Systems would be
evaluated along similar criteria to level 2.

Level 4: Mixed soundtrack generation

The final level expands upon level 3 by incorporating multi-channel mixing
(stereo, 5.1, etc.) into the generation process. In addition to the evaluation
criteria of previous levels, subjective measures of stereo separation and
spatial immersion will be included.

###  4.3 Consideration on the Official Dataset

Simulated sound \- The foley is often an audio signal that is recorded and
edited to give a certain acoustic impression, regardless of how an actual
acoustic event would sound. For example, a good foley of ‘body hitting’ would
be a loud and exaggerated version of low-frequency impulsive sounds rather
than an actual recording of body hitting which is barely audible.

Accompanied information \- As we discussed in Section 3.2, the dataset may or
may not have visual cues. This will depend on how the problem is formulated.

###  4.4 Our Suggestion: Official Dataset

In this section, we propose the dataset specification that is compatible with
the FSS problem definition at level 1 in Section 4.2. In Gaudio Lab, where
some of the authors are affiliated, there are in-house foley artists and the
company is willing to provide audio files to create the official dataset.

Number of category \- In the same spirit of narrowing down the problem in
level 1 definition, the number of categories would be limited to a small
number. Still, the categories should be chosen to cover diverse foley sounds.
For example, four categories can be selected; footsteps and gunshots
(impulsive sounds), dog barking (tonal sounds), and swooshes (airborne sounds
with a varying duration).

Number of item \- It can be critical to the performance of the FSS systems. We
assume that the number of items should be larger than a hundred per category
but this is subject to change and would need more discussion in the future.

Audio quality \- full-bandwidth (44.1 kHz) signals would be desired
considering the users of foley sound, which are, professional content
creators.

Visual cue \- Following the problem definition of level 1 in Section 4.2, in
the first version of the official dataset, there would not be visual
information.

###  4.5 Consideration on Evaluation

Evaluation of generative models or synthesized samples is a difficult task in
general, yet very important particularly when organizing a challenge.
Objective evaluation is convenient, but it often disagrees with human
perception. It may be also ‘gamed’, which would be undesirable for a
challenge. As an alternative, human-engaged evaluation has been widely used as
a way of benchmarking to compare performance for different audio generation
models [33]. In practice, however, subjective evaluation may not be preferred
in a large-scale evaluation due to the low time- and cost-efficiency. In this
section, we discuss the objective and subjective metrics to evaluate
generative models.

####  4.5.1 Objective Evaluation Metrics

Inception score (IS) has gained popularity after its introduction to evaluate
implicit generative models such as GANs. IS is defined with the posterior
distribution of auxiliary classifier models. IS is often interpreted as
multiplication of sharpness and diversity, which represent the confidence of
the classifier in its output labels and the class diversity of the generated
samples, respectively. In other words, IS is able to sensitively reflect the
quality of class identity and diversity. However, it does not capture the mode
inconsistency, i.e. mode addition or dropping.

Fréchet inception distance (FID) is another widely used metric for generative
models. Instead of using outputs of an auxiliary model as done in IS, the
calculation of FID relies on hidden representations of an auxiliary model. The
auxiliary model does not need to be a classifier, and it is assumed that FID
is robust to choice of representation space. Recently, FID was adopted for
audio generation using an audio classifier and named Fréchet audio distance
(FAD) [34].

FID (as well as FAD) is calculated from sets of hidden representations of
generated and real samples. Each set of representation is fitted to a
multivariate Gaussian distribution, and the Fréchet distance of these two
distributions becomes the FID score of the generated samples. Since it
directly models the distribution of hidden representations, FID is sensitive
to mode changes including spurious mode addition or dropping [35].

Likelihood is worth discussing, although we do not recommend using it. It is
one of the most straightforward metric for evaluation of generative models.
For density estimation, likelihood is a key metric as it directly shows how
the model estimates the target distribution. However, we suggest not using
likelihood for two reasons. First, it is often not aligned with perceptual
quality [36]. Second, it has limited applicability since calculation of
likelihood is not possible for some generative models such as including GANs,
VAEs or diffusion probabilistic models.

####  4.5.2 Subjective Evaluation Metrics

Perhaps the most common scheme of subjective evaluation is to ask the mean
opinion score (MOS). In a MOS test, human raters are guided to evaluate a
sample into five-point scale where 1 means very bad and 5 means very natural.
Usually, there are various aspects that affect the overall perceptual quality
such as fidelity, degree of artifacts, and naturalness. To measure them
separately, it is common to design multiple questions for each sample.

###  4.6 Our Suggestion: Two-Phase Evaluation

To combine advantages of objective and subjective evaluation, we suggest a
two-phase evaluation scheme as follows:

  * •

Phase 1: All participants will be evaluated only with objective metrics. All
metrics will be publicly announced and considered simultaneously in the public
leader board. The participating systems will be scored with respect to each
objective metric. The scores will be standardized over all the evaluators, and
the standardized scores will be summed to yield the final score of a system.

  * •

Phase 2: Only the top-$N$ submissions from phase 1 will be evaluated on five-
point scale (MOS). Human evaluators will be asked to focus on various aspects
of the generated samples, e.g., fidelity, coincidence with class label, and
temporal alignment. The final ranking will be decided by an average MOS.

In the first phase, inception score (IS) and Fréchet inception distance (FID)
will be used to determine ranks of the participants. In order to detect severe
memorization of training samples, which can happen as a result of overfitting,
we will use the memorization-aware version of FID [37].

In the second phase, we suggest the following criteria in the subjective
evaluation.

  * •

Fidelity of generated audio

  * •

Distortions and artifacts of generated audio

  * •

Coincidence to the given conditions, e.g. class labels, text descriptions, or
video frames

The evaluators do not need to be an experienced audio engineers. However, it
will be important to ensure that the quality of the testing environment
(headphones and the listening room) meets some criteria.

##  5 Conclusion

In this paper, we proposed a new challenge in audio research – foley sound
synthesis. We reviewed several recent challenges including their goals,
progresses, and impacts. We also reviewed the existing research and datasets
in foley sound synthesis. Based on these reviews, we presented a brief
proposal on foley sound synthesis challenge including our suggestion on
problem definition, datasets, and evaluation. We hope this paper triggers
discussion that leads to initiation of the proposed challenge, and ultimately,
progress in foley sound synthesis.

## References

  * [1] J. Stinson, “Real-time sound effects: the foley way,” _Videomaker Magazine_ , 1999.
  * [2] A. v. d. Oord, S. Dieleman, H. Zen, K. Simonyan, O. Vinyals, A. Graves, N. Kalchbrenner, A. Senior, and K. Kavukcuoglu, “Wavenet: A generative model for raw audio,” _arXiv preprint arXiv:1609.03499_ , 2016.
  * [3] Y. Wang, R. Skerry-Ryan, D. Stanton, Y. Wu, R. J. Weiss, N. Jaitly, Z. Yang, Y. Xiao, Z. Chen, S. Bengio, _et al._ , “Tacotron: Towards end-to-end speech synthesis,” _arXiv preprint arXiv:1703.10135_ , 2017.
  * [4] A. Black and K. Tokuda, “The blizzard challenge 2005: Evaluating corpus-based speech synthesis on common databases,” in _Proceedings of interspeech_ , 2005, pp. 77–80.
  * [5] D. Kolossa, R. Fernandez_Astudillo, A. Abad, S. Zeiler, R. Saeidi, P. Mowlaee, J. P. d. S. Neto, and R. Martin, “Chime challenge: Approaches to robustness using beamforming and uncertainty-of-observation techniques,” in _Machine Listening in Multisource Environments_ , 2011.
  * [6] J. Barker, E. Vincent, N. Ma, H. Christensen, and P. Green, “The pascal chime speech separation and recognition challenge,” _Computer Speech & Language_, vol. 27, no. 3, 2013.
  * [7] D. Giannoulis, E. Benetos, D. Stowell, M. Rossignol, M. Lagrange, and M. D. Plumbley, “Detection and classification of acoustic scenes and events: An ieee aasp challenge,” in _2013 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics_. IEEE, 2013, pp. 1–4.
  * [8] D. Stowell, D. Giannoulis, E. Benetos, M. Lagrange, and M. D. Plumbley, “Detection and classification of acoustic scenes and events,” _IEEE Transactions on Multimedia_ , vol. 17, no. 10, pp. 1733–1746, 2015.
  * [9] Y. Mitsufuji, G. Fabbro, S. Uhlich, and F.-R. Stöter, “Music demixing challenge 2021,” _arXiv preprint arXiv:2108.13559_ , 2021.
  * [10] C.-Z. A. Huang, H. V. Koops, E. Newton-Rex, M. Dinculescu, and C. J. Cai, “Ai song contest: Human-ai co-creation in songwriting,” _arXiv preprint arXiv:2010.05388_ , 2020.
  * [11] J. K. Hahn, H. Fouad, L. Gritz, and J. W. Lee, “Integrating sounds and motions in virtual environments,” _Presence_ , vol. 7, no. 1, pp. 67–77, 1998.
  * [12] P. R. Cook, “Modeling bill’s gait: Analysis and parametric synthesis of walking sounds,” in _Audio engineering society conference: 22nd international conference: Virtual, synthetic, and entertainment audio_. Audio Engineering Society, 2002.
  * [13] F. Fontana and R. Bresin, “Physics-based sound synthesis and control: crushing, walking and running by crumpling sounds,” in _Proc. colloquium on musical informatics_ , 2003.
  * [14] L. Turchet, “Footstep sounds synthesis: design, implementation, and evaluation of foot–floor interactions, surface materials, shoe types, and walkers’ features,” _Applied Acoustics_ , vol. 107, pp. 46–68, 2016.
  * [15] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” _Advances in neural information processing systems_ , vol. 27, 2014.
  * [16] A. Owens, P. Isola, J. McDermott, A. Torralba, E. H. Adelson, and W. T. Freeman, “Visually indicated sounds,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2405–2413.
  * [17] J. F. Gemmeke, D. P. Ellis, D. Freedman, A. Jansen, W. Lawrence, R. C. Moore, M. Plakal, and M. Ritter, “Audio set: An ontology and human-labeled dataset for audio events,” in _2017 IEEE international conference on acoustics, speech and signal processing (ICASSP)_. IEEE, 2017, pp. 776–780.
  * [18] Y. Zhou, Z. Wang, C. Fang, T. Bui, and T. L. Berg, “Visual to sound: Generating natural sound for videos in the wild,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 3550–3558.
  * [19] H. Chen, W. Xie, A. Vedaldi, and A. Zisserman, “Vggsound: A large-scale audio-visual dataset,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 721–725.
  * [20] S. Liu, S. Li, and H. Cheng, “Towards an end-to-end visual-to-raw-audio generation with gan,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 32, no. 3, pp. 1299–1312, 2021.
  * [21] P. Chen, Y. Zhang, M. Tan, H. Xiao, D. Huang, and C. Gan, “Generating visually aligned sound from videos,” _IEEE Transactions on Image Processing_ , vol. 29, pp. 8292–8302, 2020.
  * [22] S. Ghose and J. J. Prevost, “Foleygan: Visually guided generative adversarial network-based synchronous sound generation in silent videos,” _arXiv preprint arXiv:2107.09262_ , 2021.
  * [23] V. Iashin and E. Rahtu, “Taming visually guided sound generation,” _arXiv preprint arXiv:2110.08791_ , 2021.
  * [24] A. Guzhov, F. Raue, J. Hees, and A. Dengel, “Audioclip: Extending clip to image, text and audio,” in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 976–980.
  * [25] H.-H. Wu, P. Seetharaman, K. Kumar, and J. P. Bello, “Wav2clip: Learning robust audio representations from clip,” in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 4563–4567.
  * [26] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, _et al._ , “Learning transferable visual models from natural language supervision,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 8748–8763.
  * [27] P. Dhariwal, H. Jun, C. Payne, J. W. Kim, A. Radford, and I. Sutskever, “Jukebox: A generative model for music,” _arXiv preprint arXiv:2005.00341_ , 2020.
  * [28] Z. Kong, W. Ping, J. Huang, K. Zhao, and B. Catanzaro, “Diffwave: A versatile diffusion model for audio synthesis,” _arXiv preprint arXiv:2009.09761_ , 2020.
  * [29] S. Ghose and J. J. Prevost, “Autofoley: Artificial synthesis of synchronized sound tracks for silent videos with deep learning,” _IEEE Transactions on Multimedia_ , vol. 23, pp. 1895–1907, 2020.
  * [30] J. Salamon, C. Jacoby, and J. P. Bello, “A dataset and taxonomy for urban sound research,” in _22nd ACM International Conference on Multimedia (ACM-MM’14)_ , Orlando, FL, USA, Nov. 2014, pp. 1041–1044.
  * [31] E. Fonseca, X. Favory, J. Pons, F. Font, M. Plakal, D. P. W. Ellis, and X. Serra, “Fsdkaggle2018,” Jan. 2019. [Online]. Available: https://doi.org/10.5281/zenodo.2552860
  * [32] K. Drossos, S. Lipping, and T. Virtanen, “Clotho dataset,” May 2021. [Online]. Available: https://doi.org/10.5281/zenodo.4783391
  * [33] T. Hayashi, R. Yamamoto, K. Inoue, T. Yoshimura, S. Watanabe, T. Toda, K. Takeda, Y. Zhang, and X. Tan, “Espnet-tts: Unified, reproducible, and integratable open source end-to-end text-to-speech toolkit,” in _ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020, pp. 7654–7658.
  * [34] K. Kilgour, M. Zuluaga, D. Roblek, and M. Sharifi, “Fréchet audio distance: A reference-free metric for evaluating music enhancement algorithms.” in _INTERSPEECH_ , 2019.
  * [35] M. S. M. Sajjadi, O. Bachem, M. Lucic, O. Bousquet, and S. Gelly, “Assessing generative models via precision and recall,” in _NeurIPS_ , vol. 31. Curran Associates, Inc., 2018\.
  * [36] L. Theis, A. van den Oord, and M. Bethge, “A note on the evaluation of generative models,” in _International Conference on Learning Representations_ , Apr 2016. [Online]. Available: http://arxiv.org/abs/1511.01844
  * [37] C.-Y. Bai, H.-T. Lin, C. Raffel, and W. C.-w. Kan, “On training sample memorization: Lessons from benchmarking generative modeling with a large-scale competition,” in _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, 2021, pp. 2534–2542.