Video coding is an integral part of numerous real-time multimedia applications such as video telephony, telemedicine, video conferencing and video streaming. In real-time mul- timedia systems or power constrained systems, the coding performance of modern video coding standards such as High E ciency Video Coding (HEVC) and H.264/MPEG-4 Advanced Video Coding (AVC), is limited by computational complexity. This thesis presents research work to develop techniques to reduce the computational complexity of video encoders and to exploit their data and task level parallelism. These techniques aim to provide signi cant complexity saving as well as improving coding e ciency. A computationally e cient framework for macroblock prediction is developed to re- duce the computational complexity and overheads related to the macroblock prediction process in video encoding. The framework consists of several innovative techniques to exclude as many intra and inter prediction modes as possible prior to the RDO (rate distortion optimization) process. In the best case, the proposed framework selects one MB type either intra or inter and one corresponding near-optimal prediction mode, so that the complete RDO process is neglected. Simulation results show that the proposed framework achieves signi cant complexity savings without any signi cant degradation in video quality. In addition, a complexity reduction technique for motion compensation is developed to perform inter prediction. This addresses the computational complexity issues related to both interpolation and data manipulation modules of the motion compensation process. The end results of the experiments display that this method prominently decreases the computational complexity without loss in rate-distortion performance. Finally, an end-to-end hybrid hardware-software implementation scheme based on pipelin- ing and multitasking for advanced video coding is presented. This scheme exploits the task and data level parallelism in video encoders to improve their coding e ciency. The parallelism is exploited at both coarse-grain level andne-grain level. The coarse-grain level parallelism exploitation is done by concurrently executing multiple tasks on di er- ent processing cores whilene-grain level parallelism is achieved by using SIMD (single instruction multiple data) instructions. Such exploitation of parallelism also helps to better utilize the computational power o ered by advanced media processors. The out- comes of the experiments reveal that suggested scheme has resulted in enhancing the encoding rate and reducing power consumption. In theeld of video coding the main achievement of this research can be given in a nut shell as: (a) Development of computationally e cient techniques for macroblock predic- tion type and partition selection. (b) Development of complexity reduction algorithm based on intra and inter prediction mode selection. (c) Development of a computation- ally e cient scheme for motion compensation. Finally, (d) development of end-to-end vii hybrid implementation scheme for H.264/AVC encoder that exploits its data and task level parallelism to improve coding e ciency. These innovative techniques may prove handy in real-time implementation of H.264/AVC and HEVC video encoders in computationally constrained environments as is the case in general purpose computers and low-power mobile devices.