We present the theory and practice of permutation coding as a new tool for very low-bit-rate image compression. Conventional source coding deals with the data information of signals, while the permutation coding achieves compression through efficiently representing the positional information (i.e., position permutation) caused by ordering the data information into order statistics. A set of four theorems is presented. The first one reveals the information-theoretic relationship between data and permutation information and the rest solves the efficient coding problem. For this, novel tools from finite group theory are applied to derive a compact form of representation for permutation, called permutation-cyclic-representation (PCR) vectors, with which various regularities and constraints in the structure of positional information are displayed, whereby the coding is made very easy using a runlength and Huffman method. A block DCT-based permutation coding algorithm (the BCPC) is developed attempting to combine the DCT's excellent features of energy packing and magnitude ordering that are found to be amenable to permutation coding. This mutually beneficial characteristic significantly reduces the coding bit-rate. Simulation results are provided for real images, showing an improvement by 3-4 dB in the peak-SNR index as compared to those representing the state-of-the-art.