A palette decoding apparatus includes a palette color storage device which stores palette colors, a color index storage device which stores color indices of pixels, and a palette value processing circuit which generates a palette value for each pixel by reading data from the color index storage device and the palette color storage device. A frame is divided into first coding units, and each first coding unit is sub-divided into one or more second coding units. Before a palette value of a last pixel in a first coding unit is generated by the palette value processing circuit, a palette value of a non-last pixel in the first coding unit is generated by the palette value processing circuit and used by a reconstruction circuit of the video decoder.