Abstract; Nowadays, most cellular phones are used beyond voice communication. Although the processing power of cellular phones is sufficient for most data applications, it is difficult to play video and audio contents in software because of their computational complexity and lack of basic tools for multimedia processing, so software-based multimedia processing on cellular phones is a challenging issue. Several transcoding methods are introduced to address this issue, but they are mainly of the DCT-domain conversion. Hence, they are only applicable to high-end cellular phones. To develop a solution for low-end and mid-tier cellular phones, we begin this paper by analyzing the complexity of existing video standards to see if it is possible to play them on cellular phones by software. Next, various coding profiles as combinations of subalgorithms are studied, and we select a profile that adapts its complexity to the processing power of cellular phones. Also, an efficient dithering algorithm called out-of-order dithering is developed. We implement the profile with out-of-order dithering in an actual cellular phone software environment and present the performance results. The performance results show that software based video/audio processing is indeed possible on low-end cellular phones.