In this article, a novel class of fountain codes with feedback, called relative-entropy-based fountain (REF) codes, is proposed. The transmitter of REF codes adapts the degrees of encoded symbols to make the degree distribution at the receiver close to the robust soliton distribution, where the distance between two distributions is measured by relative entropy. The proposed REF codes are shown to achieve excellent intermediate performance over binary erasure channels (BECs), and binary-input additive white Gaussian noise channels (BI-AWGNCs) for both unicast, and multicast scenarios. For multicast, a non-uniform input symbol selection scheme is proposed to enhance the performance of REF codes. Furthermore, since the feedback is imprecise under noisy channels, the concept 'belief' is introduced to improve the reliability of REF codes. Theoretical analysis is performed for the proposed REF codes, with an upper bound, and an approximate lower bound of the intermediate performance of REF codes over BECs derived. Both theoretical analysis, and simulations show that the proposed REF codes outperform the state-of-the-art fountain codes with feedback, in terms of the intermediate performance, with low overhead.