A new treatment of priority-first search maximum-likelihood soft-decision decoding of linear block codes

In this correspondence we present a new method to convert the maximum-likelihood soft-decision decoding problem for linear block codes into a graph search problem where the generalized Dijkstra's algorithm can still be applied to the decoding procedure. The cost assigned to every branch in the graph is based on a generalization of the Wagner rule which is an equivalent form of the maximum-likelihood decoding rule. The new decoding algorithm uses the properties of error patterns to reduce the search space.