Methods and devices for encoding and decoding data streams are disclosed. In some aspects, the data streams are multimedia data streams. One method disclosed includes obtaining, by a client device, a first multimedia data stream and a second multimedia data stream, the second multimedia data stream being a lower fidelity version of the first multimedia data stream, generating, by the client device, a third multimedia data stream based on differences between the first and second multimedia data streams, compressing, by the client device, the second multimedia data stream to generate a first compressed multimedia data stream, compressing, by the client device, the third multimedia data stream to generate a second compressed multimedia data stream; and transmitting, by the client device, the first and second compressed multimedia data steams to the server.