A first-order-residual/second-order-residual (FOR/SOR) based video coding algorithm that incorporates the super macroblock (SMB) and the inter-frame stripe prediction (ISP) technique is proposed for high definition (HD) video coding in this work. We first examine the limitation of the SMB in high-bit-rate coding, and show that a simple extension of the block-size is not sufficient to get a significant improvement in coding performance. Then, we introduce the FOR/SOR coding technique to resolve this issue. For the FOR coding, we apply a larger quantization stepize and motion-predictive coding to remove the temporal correlation. Then, for the SOR coding, we propose an efficient prediction method, called the inter-frame stripe prediction (ISP) technique, to remove the structured residuals after the FOR coding to achieve a higher coding gain. It is demonstrated by experimental results that the proposed FOR/SOR algorithm outperforms H.264/AVC by a significant margin; namely, about 21.57% in the bit rate saving or 1.09dB in the PSNR improvement.