  Low density lattice codes (LDLC) are a family of lattice codes that can be
decoded efficiently using a message-passing algorithm. In the original LDLC
decoder, the message exchanged between variable nodes and check nodes are
continuous functions, which must be approximated in practice. A promising
method is Gaussian approximation (GA), where the messages are approximated by
Gaussian functions. However, current GA-based decoders share two weaknesses:
firstly, the convergence of these approximate decoders is unproven; secondly,
the best known decoder requires $O(2^d)$ operations at each variable node,
where $d$ is the degree of LDLC. It means that existing decoders are very slow
for long codes with large $d$. The contribution of this paper is twofold:
firstly, we prove that all GA-based LDLC decoders converge sublinearly (or
faster) in the high signal-to-noise ratio (SNR) region; secondly, we propose a
novel GA-based LDLC decoder which requires only $O(d)$ operations at each
variable node. Simulation results confirm that the error correcting performance
of proposed decoder is the same as the best known decoder, but with a much
lower decoding complexity.
