An information coding apparatus, an information decoding apparatus, and a method and a program therefor are provided, which can represent a large amount of information with a small number of pixels. Information bits which are inputted are coded as a block of a two-dimensional image made up from m (where m is a natural number).times.n (where n is a natural number) pixels. Specifically, pixels which represent the information bits are arranged in a code area, which is an area of (m-o).times.(n-p) pixels within a code block of m.times.n pixels (where o and p are natural numbers which satisfy 0