A video encoding apparatus is a video encoding apparatus for subjecting a video image to motion compensated prediction coding, comprising an acquisition module to acquire available blocks of blocks having motion vectors from encoded blocks adjacent to a to-be-encoded block and number of the available blocks, an acquisition/selection module to select one selection block from the encoded available blocks, a selection information encoder to encode selection information specifying the selection block using a code table corresponding to the number of available blocks, and an image encoder to subject the to-be-encoded block to motion compensated prediction coding using a motion vector of the selection block.