Minimum basis search algorithm for nearly maximum likelihood decoding of block codes

With any parity check matrix H of a code C(n,k,d) one may associate a graph whose vertices represent distinct bases, i.e., sets of n-k independent columns of H. Such basis specifies a unique error pattern. A search is carried out over a limited part of the bases graph for an error pattern having the minimum confidence value. Properties of the bases graph are utilized to reduce the complexity of the search procedure. Bounds are derived for the worst case computational complexity as well as for the correct-decoding probability.