A video decoder configured to decode an encoded video bitstream comprises a first parsing unit and a second parsing unit, each configured to independently parse the encoded video bitstream to derive parsing state information therefrom on which subsequent parsing of the encoded video bitstream at least partially depends and to identify macroblock information for decoding. The encoded video bitstream comprises frame header information defining a sequence of frames and each frame is composed of macroblocks represented by macroblock information. A control unit of the video encoder allocates each frame of macroblock information to one of the two parsing units to parse. The two parsing units are both configured to parse frame header information to thereby each derive parsing state information for the encoded video bitstream, and the two parsing unit are each configured to parse macroblock information allocated to them, skipping macroblock information allocated to the other parsing unit.