Non-binary low-density parity-check (NB-LDPC) codes usually exhibit much better performance than their binary counterparts. Among NB-LDPC decoding algorithms, the iterative reliability-based majority-logic decoding (MLGD) algorithms are attractive for their low computation complexity, at the cost of performance degradation. In this brief, based on the improved iterative soft reliability-based (IISRB)-MLGD algorithm, we propose a clipped-modified (CM)-IISRB algorithm, which achieves better decoding performance with lower computational complexity. First, two modifications are introduced to the IISRB algorithm, which considerably reduces the decoding complexity with negligible performance loss. Second, an unsaturated-clipping method that facilitates significant performance improvement is presented. Simulation results show that the new algorithm outperforms the IISRB by about 0.2dB for the 256-ary (255, 175) example code. Moreover, based on a new storage reduction method, an optimized architecture is developed for the CM-IISRB algorithm. Synthesis results demonstrate that the proposed decoder can achieve very low hardware complexity, comparable to that of the iterative hard reliability-based (IHRB) decoder.