  In this paper, we consider the decoding of fountain codes where the received
symbols may have errors. It is motivated by the application of fountain codes
in DNA-based data storage systems where the inner code decoding, which
generally has undetectable errors, is performed before the outer fountain code
decoding. We propose a novel and efficient decoding algorithm, namely
basis-finding algorithm (BFA), followed by three implementations. The key idea
of the BFA is to find a basis of the received symbols, and then use the most
reliable basis elements to recover the source symbols with the inactivation
decoding. Gaussian elimination is used to find the basis and to identify the
most reliable basis elements. As a result, the BFA has polynomial time
complexity. For random fountain codes, we are able to derive some theoretical
bounds for the frame error rate (FER) of the BFA. Extensive simulations with
Luby transform (LT) codes show that, the BFA has significantly lower FER than
the belief propagation (BP) algorithm except for an extremely large amount of
received symbols, and the FER of the BFA generally decreases as the average
weight of basis elements increases.
