For encoding, each video frame is segmented into slices; each slice, into macroblocks; and each macroblock, into blocks. Encoded macroblock and block signals are generated corresponding to macroblock and block information of each slice, respectively. An encoded bitstream is generated in accordance with the encoded macroblock and block signals, wherein all of the macroblock signals for each slice precede all of the block signals for each slice. For decoding, an encoded bitstream is received, wherein (1) a portion of the encoded bitstream corresponding to each video frame corresponds to slices; and (2) a portion of the encoded bitstream corresponding to each slice comprises encoded macroblock signals followed by block signals for the entire slice. The macroblock and block signals of each slice are decoded and decoded video signals are generated in accordance with the decoded macroblock and block signals.