Computation Coding

利用乘法矩阵分解，简化了任意高维线性函数的重复计算。为此目的，利用与当前在信源和信道编码中使用的码本类似的码本。对于任何矩阵分解，一个矩阵因子可以被解释为码本，另一个矩阵因子可以被解释为指向码本的一组指针。如果使用可重构的计算机体系结构实现，这些指针只是定义了一个布线。在最先进的算法中，计算误差随计算次数呈指数衰减。与实际有用的最先进的算法相比，衰减指数不是恒定的，而是随着函数的维数无限增长。在初步测试中，没有乘法，只有1.6个加法和寄存器移位每个矩阵条目足以达到12×4096矩阵的16位定点运算的精度。对于低端应用，所需的加法和寄存器移位的数量远低于矩阵条目的数量。虽然分解算法的初步实现使用了压缩感知的思想，但它既不要求线性函数也不要求其自变量在任何域上都是稀疏的。拟议项目将建立计算编码的研究领域，并向多个方向探索：推广到非线性函数，码书的优化，新的分解算法，理论性能分析，以及在现场可编程门阵列上的实现。非线性函数通过深度神经网络的近似来解决。计算编码中的码本约束与信源和信道编码完全不同，构成了编码理论的一个新领域。当前的分解算法具有超立方复杂度。找到更快的方法，将使计算编码在更广泛的应用中具有吸引力。理论性能分析将利用申请人在有限长度随机编码的性能分析以及最大似然解码中的副本对称性破坏方面的最新突破。现场可编程门阵列上的实现将证明新方法的实际可行性，并为未来的改进提供重要的见解。

The repeated computation of arbitrarily large-dimensional linear functions is simplified by means of multiplicative matrix decompositions. For this purpose, codebooks similar to those that are currently used in source and channel coding are utilized. For any matrix decomposition, one matrix factor can be interpreted as a codebook, the other matrix factor as a set of pointers into the codebook. If implemented using reconfigurable computer architectures these pointers just define a wiring.As in state-of-the-art algorithms, the computation error decays exponentially with the number of computations. In contrast to practically useful state-of-the-art algorithms, the decay exponent is not constant, but grows unboundedly with the dimension of the function. In preliminary tests, no multiplications, only 1.6 additions and register shifts per matrix entry were sufficient to reach the accuracy of 16-bit fixed-point arithmetic for 12×4096 matrices. For low-end applications, the required number of additions and register-shifts is way below the number of matrix entries. Although a preliminary implementation of the decomposition algorithm uses ideas from compressive sensing, it neither requires the linear function nor its argument to be sparse in any domain.The proposed project shall establish the research field of computation coding and explore it into various directions: Generalization to nonlinear functions, optimization of the codebook, new decomposition algorithms, theoretical performance analysis, and implementation on field programmable gate arrays. Nonlinear functions are addressed by their approximations via deep neural networks. Codebook constraints in computation coding are entirely different from source and channel coding and constitute a novel area of coding theory. Current decomposition algorithms have super-cubic complexity. Finding faster ones, will make computation coding attractive for an even wider range of applications. Theoretical performance analysis will utilize a recent breakthrough of the applicant in performance analysis of finite-length random coding as well as replica symmetry breaking in maximum-likelihood decoding. The implementation on field programmable gate arrays shall demonstrate the practical feasibility of the novel approach and give important insights for future improvements.