In this paper; we describe several methods which can improve the performance of the baseline H.263 encoder: All of our improvements were implemented in software using the Telenor ~2.0 codec. We begin by presenting results of our optimization of the Telenor software, which reduced the computation time of the encoder by four rimes its original value. Next, we characterize individual parts of the encoder and observe how the distribution of computation time varies with input sequence and motion search type. Based on our characterization, we then propose two methods to reduce computation in the motion estimator; discrete cosine transform, and quantizer; using a technique that detects all-zero coefficients in macrobIocks. Our combined results ultimately reduces the computational time of the original Telenor encoder by four to nine times its original value.