A New Approach to Error-Correcting Codes

Abstract

A correspondence between linear (n,k,d) codes and algorithms for computing a system Ψ of k bilinear forms is established under which the codelength n is equal to the multiplicative complexity of the algorithm for computing Ψ, and the code distance d is underbounded by the minimum number of multiplications required to compute any linear combination of the k forms in Ψ. This hitherto unexplored approach to linear codes holds promise of a better understanding of the structure of existing codes as well as for methods of constructing new codes with prescribed rate and distance. © 1977, IEEE. All rights reserved.