This paper presents FaDA (Fast Deblocking Algorithm), a low complexity post-processing algorithm that improves the visual quality of MPEG-4 low bit rate videos displayed on mobile devices. Most of the algorithms proposed up to now to enhance the visual quality after the decoder are far too complex for this kind of devices, and unfortunately deblocking algorithms efficiency is tightly related to their complexity. FaDA achieves complexity reduction while maintaining quality thanks to two principles: 1- The artifact correction is driven by Human Visual System properties, 2- A particular attention has been paid on the design of the most consuming parts of the algorithm, following implementation guidelines. We present a complete complexity evaluation that considers not only computational charge, but also number and locality of memory accesses, data dependency, and internal data size requirements. Critical steps of the algorithm were implemented in C and optimized on a TriMedia DSP. The complexity evaluation reveals a reduction by a factor ranging between 2 and 3.5, compared to the reference MPEG-4 informative deblocking, depending on architecture and implementation. Extensive subjective tests performed on both mobile LCD screen and high resolution monitor show that FaDA average visual quality is equivalent to the reference algorithm.