# Linear Computation Coding: A Framework for Joint Quantization and Computing
## 4 Proposed Scheme for Linear Computation Coding
### Computational Cost  
To find a wiring matrix in practice, we need to measure computational cost. In the sequel, we do this by solely counting additions. Sign changes are cheaper than additions and their numbers are also often proportional to the number of additions. Shifts are much cheaper than additions. Fixed shifts are actually without cost on dedicated hardware such as ASICs and FPGAs. Multiplications are counted as multiple shifts and additions.  
We define the non-negative function csd: \(\mathbb{R}\mapsto\mathbb{Z}\) as follows:  
\[\text{csd}(t)=\min_{\mathcal{B}}\left|\left\{b\in\mathcal{B}:t=\sum_{b\in \mathcal{B}}c_{b}2^{b}\wedge c_{b}\in\{+1,-1\}\right\}\right| \tag{15}\]  
This function counts how many signed binary digits are required to represent the scalar \(t\), cf. Example 2. The number of additions to directly calculate the matrix-vector product \(\mathbf{\Omega}x\) via the CSD representation of \(\mathbf{\Omega}\in\mathbb{R}^{N\times K}\) is thus given by the function csda: \(\mathbb{R}^{N\times K}\mapsto\mathbb{Z}\) as  
\[\text{csda}(\mathbf{\Omega})=\sum_{n=1}^{N}\max\left\{0,-1+\sum_{k=1}^{K} \text{csd}(\omega_{n,k})\right\}. \tag{16}\]  
In (16), \(\omega_{k,n}\) denotes the \((n,k)\)th element of \(\mathbf{\Omega}\). The function \(\text{csda}(\cdot)\) is additive with respect to the rows of its argument. With respect to the column index, we have to consider that adding \(k>1\) terms only requires \(k-1\) additions. This means the function \(\text{csda}(\cdot)\) does not decouple columnwise (although it does decouple row-wise). For columnwise decoupled wiring optimization in Section 4.2.2, this means that \(\text{csda}(\tilde{\mathbf{W}})\
eq\text{csda}(\mathbf{W})\) in general.  
Setting  
\[C[\mathbf{\Omega}x]=\text{csda}(\mathbf{\Omega}) \tag{17}\]  
in (13), we measure computational cost in terms of element-wise additions. Our goal is to find algorithms, for which  
\[\text{csda}(\mathbf{W}_{1})+\text{csda}(\mathbf{W}_{2})<\text{csda}(\mathbf{W }_{1}\mathbf{W}_{2}). \tag{18}\]  
Although the optimization in (13) implicitly ensures this inequality, it is not clear how to implement such an algorithm in practice. Even if we restrict it to \(C[\langle\omega;x\rangle]=\text{csda}(\omega^{\mathsf{T}})\), the optimization (14) is still combinatorial in \(\text{csda}(\omega^{\mathsf{T}})\).  
If the matrix contains only zeros or signed powers of two, the function \(\text{csda}(\cdot)\) can be written as  
\[\text{csda}(\mathbf{\Omega}) =\sum_{n=1}^{N}\max\left\{0,-1+\sum_{k=1}^{K}\|\omega_{n,k}\|_{0}\right\} \tag{19}\] \[\approx\|\mathbf{\Omega}\|_{0}-N \tag{20}\]  
in terms of the zero norm. The approximation (20) was used in the preliminary conference versions of this work [4, 42, 43]. In the sequel, we continue with the exact number of additions as given in (16).  
While counting the number of additions by means of the zero norm is helpful to emphasize the similarities of linear computation coding with compressive sensing, it enforces one, though minor, unnecessary restriction: the constraint for the matrix \(\mathbf{\Omega}\) to contain signed powers of 2 as non-zero elements. The wiring matrix \(\mathbf{W}\) forms linear combinations of the columns of the codebook matrix \(\mathbf{B}\), cf. (6). If we form only linear combinations of _different_ codewords, the zero norm formulation in (19) is perfectly fine. If we do not want to be bound by the unnecessary constraint that codewords may not be used twice within one linear combination, we have to resort to the more general formulation in (16). While for large matrices the performance is hardly affected, for small matrices this does make a difference. This is one of several reasons why, in the preliminary conference versions of this work [4; 43; 42], the decomposition algorithm does not perform so well for small matrices.