We analyze the connection between viewer-perceived quality and encoding schemes. The encoding schemes depend on transmission bit-rate, MPEG compression depth, frame size and frame rate in a constant bit-rate (CBR) video transmission of a MPEG-2 video sequence. The compressed video sequence is transmitted over a lossy communication network with quality of service (QoS) and a certain Internet (IP) loss model. On the end-user side, viewer-perceived quality depends on changes in the network conditions, the video compression, and the video content complexity. We demonstrate that, when jointly considering the impact of coding bit rate, packet loss, and video complexity, there is an optimal encoding scheme, which also depends on the video content. We use a set of subjective tests to demonstrate that this optimal encoding scheme maximizes the viewer-perceived quality.