An Improved Trellis Decoding Algorithm for Maximum Likelihood Decoding of Linear Block Codes

Abstract

Several researchers have presented techniques for decoding linear block codes that convert the decoding
problem into a problem of graph search on a trellis derived from the generator or the parity-check
matrices of the code. In this paper, we propose a new method for reducing the space complexity and the time complexity of the Local A∗ search method for MLD of block group codes. Authors method utilizes a well-known concept in data structures called “Thread”. This technique allows us to remove the data structure storage for nodes in list OPEN. The utilization of the “Thread” has led to significant reduction
in the space complexity and the time complexity. The proposed method has been tested on the AWGN
channel and the simulation results has shown the high efficiency of the proposed method, as compared to
the A∗ & Local A∗ search method, while maintaining the same probability of decoding error.