# Linear Computation Coding: A Framework for Joint Quantization and Computing
## 3 State of the Art in Linear Computation Coding
### Scalar Functions  
The principles and benefits of computation coding are most easily explained for linear functions. Let us start with scalar linear functions, before we get to the multi-dimensional case. **Example 1**. : _Let \(x\in\mathbb{R}\) have unit variance and \(f(x)=tx,t\in[-1,+1]\). Let the computation encoding take the form_  
\[m(x)=\operatorname{sign}(t)\sum_{b=1}^{C-1}c_{b}2^{b-C}x \tag{1}\]  
_where the coefficients \(c_{b}\in\{0,1\}\) are the binary digits of the \((C-1)\)-bit unsigned integer approximation of \(|t|2^{C-1}\) starting to count with the least significant digit. There are only \(C-1\) bits available to approximate \(|t|\), as one bit is reserved for the sign. This is the standard way a linear function is implemented on a modern computer by means of additions and bit shifts. Considering \(t\) as a random variable with uniform distribution on \([-1,+1]\), the trade-off between average mean-squared distortion and bit-width \(C\) is well-known to be [13]_  
\[\operatorname*{\underline{\mathbb{E}}}_{x\in\mathbb{R}}[f(x)-m(x)]^{2}=\frac{4 ^{-C}}{3}, \tag{2}\]  
_i.e., every additional bit of resolution reduces the quantization error by 6 dB. The bit-width \(C\) is clearly a sensible measure for the computational cost. The variance of \(t\) is \(\frac{1}{3}\), so the signal-to-quantization noise ratio (SQNR) is given by \(4^{C}\)._  
Assuming that the coefficients \(c_{b}\) are independent random variables with a 50% chance to be one, the total number of nonzero coefficients \(i\) is binomially distributed with parameter \(\frac{1}{2}\). The number of additions given \(i\) is \(\max\{0,i-1\}\). Thus, we obtain the average number of additions in Example 1 as  
\[2^{1-C}\sum_{i=1}^{C-1}\binom{C-1}{i}(i-1)=\frac{C-3}{2}+2^{1-C} \tag{3}\]  
for \(C>2\). For 16-bit signed integer arithmetic, we need approximately 6.5 additions per multiplication. The multiplication of a \(4096\times 512\) matrix of 16-bit signed fixed-point numbers by an unknown column vector, thus, requires \(4096\cdot(512\cdot 6.5+511)\approx 15.7\) million additions, i.e., 7.5 additions per matrix entry, on average. It achieves an average distortion of \(4^{-16}/3\), which is equivalent to \(-101\) dB and a signal-to-quantization noise ratio (SQNR) of 96 dB. **Example 2**. : _Consider the setting of Example 1, except for the computation encoding to take [PERSON]'s canonical signed digit (CSD) form [14], i.e.,_  
\[m(x)=\sum_{b\in\mathcal{B}}c_{b}2^{b}x \tag{4}\]with \(\mathcal{B}\subset\mathbb{Z}\). Like in Example 1, the number \(t\) is approximated by a weighted sum of powers of 2. However, the weighting coefficients \(c_{b}\) are chosen from the set \(\{-1,+1\}\) instead of \(\{0,1\}\). For the optimum set \(\mathcal{B}\), the average mean-squared distortion is shown in Appendix A to be_  
\[\operatorname*{\mathbb{E}}_{x\in\mathbb{R}}[f(x)-m(x)]^{2}=\frac{28^{-| \mathcal{B}|}}{3}. \tag{5}\]  
_Every addition reduces the quantization error by 14.5 dB. The SQNR is given by \(28^{|\mathcal{B}|}\)._  
In Example 2, the average distortion of \(-101\) dB is achieved for \(|\mathcal{B}|=\log_{28}4^{16}\approx 6.66\), i.e., \(\approx 6.66\) additions per matrix entry. This is an \(11\%\) reduction in comparison to Example 1. [PERSON]'s CSD representation is useful, if the standard binary representation of Example 1 contains sequences of 3 or more 1-bits, e.g., in numbers like 7, which is more efficiently represented as \(8-1\) instead of \(4+2+1\). Modern VDHL compilers, e.g., use the CSD form automatically whenever useful. Therefore, the performance of the CSD form is used as benchmark in the sequel. For very high precision, i.e., very small distortion, more efficient algorithms are known from literature that are all based on some version of the Chinese Remainder Theorem [15; 16; 17; 18; 19; 20]. For precisions relevant in neural networks, however, these algorithms are not useful. There are various further improvements to computation coding of scalar linear functions in the literature, e.g., redundant logarithmic arithmetic [21; 22].