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.