T. Uyematsu, EFFICIENT MAXIMUM-LIKELIHOOD DECODING ALGORITHMS FOR LINEAR CODES OVER Z-CHANNEL, IEICE transactions on fundamentals of electronics, communications and computer science, E76A(9), 1993, pp. 1430-1436
This paper presents two new maximum likelihood decoding (MLD) algorith
ms for linear codes over Z-channel, which are much more efficient than
conventional exhaustive algorithms for high rate codes. In the propos
ed algorithms, their complexities are reduced by employing the project
ing set C(s) of the code, which is determined by the ''projecting'' st
ructure of the code. Space and computational complexities of algorithm
s mainly depend upon the size of C(s) which is usually several times s
maller than the total number of code-words. It is shown that the upper
bounds on computational complexities of decoding algorithms are in pr
oportion to the number of parity bits and the distance between an init
ial estimate of the codeword and the received word, respectively, whil
e space complexities of them are equal to the size of C(s). Lastly, nu
merical examples clarify the average computational complexities of the
proposed algorithms, and the efficiency of these algorithms for high
rate codes is confirmed.