Gradient descent decoding of binary cyclic codes

It is well known that the maximum likelihood decoding of a binary (n,k,d) code is equivalent to finding the maxima (minima) of a polynomial form in k binary variables. We extend this method to the problem of permutation decoding of binary cyclic codes and give an implementation based on a Hopfield type neural network architecture. Using results from Baldi (1988), we show that a generalized Hopfield network whose connections are governed by the generator matrix of the code and the received word has a stable state corresponding to the transmitted codeword if t=[(d-1)/2] or fewer errors are introduced in the transmission process. An energy function is defined and the search for a global maxima is done through a selective updating of neurons( information bits). The value of the energy function call be related to the Hamming distance of the received word and to the codeword corresponding to the current state of the network so that if we come within the Hamming sphere of a codeword, successful decoding has been achieved. By utilizing the known permutation group of the code, the local maxima problem which plagues all optimization search is alleviated. We discuss the conditions under which the network will converge to the right codeword in the presence of random errors as well as various updating algorithms. Finally we conclude with simulation results for non-trivial cyclic codes such as the (63,30,13), the (127,64,2) and the (255,131,37) BCH codes using different approaches to searching the energy space